Summary: Chapter 12 Linear Programming

Table of Contents
1. Linear Programming
2. Linear Programming Problem (LPP) - Key Parts
3. Basic Definitions and Results
4. Graphical Methods
5. Working Rule to Mark Feasible Region
6. Convexity and Geometric Concepts
7. Key Properties for LPP and Convex Sets
View more

Linear Programming

• Linear Programming is an optimization method to maximize or minimize a linear expression subject to linear restrictions.

Linear Programming Problem (LPP) - Key Parts

• Linear Programming Problem (LPP): Optimize a linear objective function subject to linear constraints and non-negative restrictions.
• Objective Function: z = c₁x₁ + c₂x₂ + ... + c_nx_n.
• Constraints: a set of linear equations/inequations involving x₁, x₂, ..., x_n.
• Non-negative Restrictions: x_i ≥ 0 for all decision variables.
• Slack and Surplus Variables: Add positive slack to ≤ constraints; subtract positive surplus from ≥ constraints to convert to equalities.

Basic Definitions and Results

• Solution of a LPP: Any values of x₁,...,x_n that satisfy the constraints.
• Feasible Solution: A solution that also satisfies non-negative restrictions.
• Optimal Solution: A feasible solution that optimizes the objective function.
• Graphical Solution: Solution obtained by drawing constraint lines and the feasible region on the plane.
• Unbounded Solution: When the objective function can increase or decrease indefinitely.
• Fundamental Extreme Point Theorem: If an optimum exists, it occurs at an extreme (corner) point of the convex feasible region.

Graphical Methods

• Corner Point Method - procedure:
  • Treat each constraint as an equation and plot its line.
  • Identify the common region satisfying all constraints and x ≥ 0 (feasible region, convex polygon).
  • List the vertices (extreme points) of the feasible region.
  • Evaluate the objective function at each vertex; the best value gives the optimal solution.
• Iso-profit / Iso-cost Method - procedure:
  • Plot the constraint lines and find the feasible region.
  • Choose a convenient value k and draw the line Z = k.
  • For maximization, slide lines parallel to Z = k away from the origin until the last line touching the feasible region is found.
  • For minimization, slide toward the origin until the first touching line is found; the touching point is optimal.

Working Rule to Mark Feasible Region

• For ax + by ≤ c (c > 0): draw ax + by = c; the feasible side is the side containing the origin.
• For ax + by ≥ c (c > 0): draw ax + by = c; the feasible side is the side not containing the origin.

Convexity and Geometric Concepts

• Point Sets: Points or vectors in Eⁿ or Rⁿ.
• Hypersphere: {x : |x - a| = ∈} with centre a and radius ∈ > 0.
• ∈-neighbourhood: Points inside a hypersphere about a point.
• Interior Point: A point with some ∈-neighbourhood contained in the set.
• Boundary Point: Every ∈-neighbourhood contains points both in and out of the set.
• Open Set: Contains only interior points. Closed Set: Contains its boundary points.
• Line: {x : x = λx₁ + (1 - λ)x₂, for all real λ}.
• Line Segment: {x : x = λx₁ + (1 - λ)x₂, 0 ≤ λ ≤ 1}.
• Hyperplane: c₁x₁ + ... + c_nx_n = z (not all c_i = 0).
• Open half spaces: {x : cx > z}, {x : cx < z}; closed half spaces: {x : cx ≤ z}, {x : cx ≥ z}.
• Parallel Hyperplanes: c₁ = λ c₂ for nonzero λ give same unit normals.
• Convex Combination: x = λ₁x₁ + ... + λ_nx_n, λ_i ≥ 0, Σλ_i = 1.
• Convex Set: Line segment joining any two points in the set lies in the set.
• Extreme Point: A point in a convex set that cannot be written as a convex combination of two distinct points of the set.
• Convex Hull: Set of all convex combinations of points from a given set.
• Convex Function: f(λx₁ + (1 - λ)x₂) < λf(x₁) + (1 - λ)f(x₂) for 0 < λ < 1. Concave if -f is convex.
• Convex Polyhedron: Convex combinations of a finite number of points.

Key Properties for LPP and Convex Sets

• A hyperplane and half spaces are convex sets.
• Intersections (finite or arbitrary) of convex sets are convex.
• The feasible solution set of a LPP (if non-empty) is convex.
• Every basic feasible solution of Ax = b, x ≥ 0 is an extreme point of the feasible set and conversely.
• If the feasible set is a convex polyhedron, at least one extreme point gives an optimal solution.
• If the objective function is optimal at more than one extreme point, every convex combination of those points is also optimal.