3.4 Fundamental theorem of linear programming

Linear programming is all about finding the best solution within a set of constraints. The fundamental theorem is the backbone of this process, stating that the optimal solution always occurs at a corner point of the feasible region.

This theorem simplifies the search for optimal solutions, allowing us to focus on a finite set of extreme points rather than an infinite number of possibilities. It's the reason why methods like simplex work so efficiently in solving linear programming problems.

Fundamental Theorem of Linear Programming

Core Statement and Applicability

• Fundamental theorem of linear programming states optimal solution exists at a vertex (extreme point) of the feasible region
• Applies to maximization and minimization problems in linear programming
• Based on optimal solution occurring at corner point of feasible region formed by constraint equation intersections
• Holds true for problems with any number of variables and constraints in standard form
• Crucial for developing efficient algorithms (simplex method)
• Reduces search space from infinite points to finite set of extreme points
• Provides theoretical foundation for considering only extreme points when solving problems graphically or algebraically

Mathematical Implications

• Optimal solution found by evaluating objective function at extreme points of feasible region
• Guarantees optimal solution at vertices if it exists, eliminating need to search entire feasible region
• Allows development of efficient algorithms moving from one extreme point to another
• Multiple optimal solutions cases have at least one at an extreme point
• Supports concept of basic feasible solutions where each extreme point corresponds to a basic feasible solution
• Basis for sensitivity analysis examining changes in extreme points
• Emphasizes importance of feasible region shape and vertices in geometric interpretation

Implications of the Fundamental Theorem

Algorithmic Efficiency

• Justifies corner point methods in graphical solutions of two-variable linear programming problems
• Enables simplex method to focus on moving between adjacent extreme points with improved objective function value
• Facilitates development of algorithms efficiently searching through extreme points for optimal solution
• Reduces computational complexity of large-scale problems by focusing on finite set of extreme points
• Proves convergence to optimal extreme point solution in interior point methods
• Applies to branch and bound algorithms for integer programming in linear programming relaxations at each node
• Implemented in software packages to ensure optimal solution search focuses on extreme points

Problem-Solving Strategies

• Utilizes extreme points as intersections of constraint lines or planes in feasible region
• Represents basic feasible solutions in algebraic representation of linear programming problems
• Finite number of extreme points even in unbounded feasible regions
• Crucial in determining solution existence, uniqueness, or multiplicity
• Identifies degeneracy when more constraints than necessary intersect at an extreme point, affecting algorithm behavior
• Generalizes to vertices of polyhedra in higher-dimensional problems
• Extends to advanced optimization problems (integer programming, nonlinear programming)

Applying the Fundamental Theorem

Graphical Solutions

• Apply corner point method to two-variable problems
  • Identify feasible region boundaries
  • Find intersection points of constraint lines
  • Evaluate objective function at each extreme point
  • Select point with optimal objective value
• Example: Maximize $z = 3x + 2y$ subject to $x + y ≤ 4$, $x ≤ 3$, $y ≤ 2$, $x, y ≥ 0$
  • Extreme points: (0,0), (3,0), (3,1), (2,2), (0,2)
  • Optimal solution at (3,1) with z = 11

Algebraic Solutions

• Implement simplex method using tableau
  • Start at initial basic feasible solution (extreme point)
  • Iteratively move to adjacent extreme points
  • Stop when optimal solution reached
• Example: Minimize $z = 2x + 3y$ subject to $x + y ≥ 3$, $x + 2y ≥ 4$, $x, y ≥ 0$
  • Initial tableau with slack variables
  • Pivot to reach optimal solution at extreme point

Significance of Extreme Points

Geometric Interpretation

• Represent corners of feasible region in two-dimensional problems
• Vertices of polyhedron in higher-dimensional problems
• Intersections of constraint hyperplanes in n-dimensional space
• Example: In 3D problem, extreme points are vertices of a polyhedron (cube, tetrahedron)

Algebraic Significance

• Correspond to basic feasible solutions in standard form problems
• Represent unique solutions to system of linear equations
• Number of non-zero variables equals number of binding constraints
• Example: In a problem with 4 variables and 2 constraints, extreme points have 2 non-zero variables