Linear Programming

Linear programming solves optimization problems with linear constraints. Imagine a factory that produces two products. Each product requires labor and materials, and profit differs between them. Subject to limits on labor and materials, what combination maximizes profit? Or, a hospital must schedule staff to cover all shifts while minimizing payroll. These real-world problems—maximize profit, minimize cost, allocate resources—reduce to linear programs: maximize or minimize a linear objective function subject to linear inequality constraints. This chapter develops graphical and algebraic methods to find optimal solutions.

Understanding Linear Programs

A linear program has the form:

- a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁ - a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂ - ... (more constraints) - xᵢ ≥ 0 (non-negativity constraints)

• Objective: Maximize (or minimize) Z = c₁x + c₂x + ... + cₙx (linear function)
• Subject to constraints:

Variables (x₁, x₂, ...): quantities to determine (e.g., units of products to produce)

Objective function Z: total value to maximize or minimize (e.g., profit, cost)

Constraints: limitations on variables (e.g., resource limits, demand bounds)

Feasible region: all points satisfying all constraints simultaneously

Optimal solution: feasible point where objective function is maximized or minimized

Building from Class 11

In Class 11, you studied systems of linear inequalities and graphed solutions in 2D. This chapter applies those ideas to optimization: graph the feasible region and find the point within it that optimizes the objective.

Graphical Method (2D)

For problems with two variables, graphical solution is intuitive:

1. Graph each constraint inequality (equality gives a line; inequality gives a half-plane)
2. Identify feasible region (intersection of all half-planes and non-negativity constraints)
3. Find corner points of feasible region (vertices where constraint lines intersect)
4. Evaluate objective at each corner point
5. Select the corner with best objective value (maximum or minimum)

Key insight: For linear programs, the optimal solution occurs at a corner of the feasible region, not in the interior.

Example: Maximize Z = 3x + 2y subject to:

• x + y ≤ 4
• 2x + y ≤ 7
• x, y ≥ 0

Feasible region is a polygon with corners (0,0), (0,4), (3,1), (3.5,0). Evaluate Z at each:

• Z(0,0) = 0
• Z(0,4) = 8
• Z(3,1) = 11 ← maximum
• Z(3.5,0) = 10.5

Optimal solution: x = 3, y = 1, giving Z = 11

Graphical Method Justification

Why corners are optimal: The objective function Z = c₁x + c₂x + ... represents level curves (lines in 2D) where Z is constant. As we increase Z, these lines shift. The last level curve to touch the feasible region touches at a corner.

Why interior points can't be optimal: If the optimal point is interior, we can move along the direction that increases Z (perpendicular to level curves) until hitting a corner, which gives better Z.

Simplex Method (Algebraic Approach)

For problems with many variables, the graphical method is impractical. The simplex method is an algorithm that:

1. Converts inequalities to equalities using slack variables (sᵢ ≥ 0)
2. Sets up a tableau (table of coefficients)
3. Iteratively improves the solution by pivoting (row operations)
4. Stops when optimality condition is satisfied

Slack variables: For constraint aᵢ₁x₁ + aᵢ₂x₂ ≤ bᵢ, add slack sᵢ ≥ 0:

aᵢ₁x₁ + aᵢ₂x₂ + sᵢ = bᵢ

The slack variable represents unused resources.

Standard Form

Before solving, convert to standard form:

• All variables ≥ 0
• All constraints are equalities (using slack variables)
• Objective is to maximize (convert minimization to maximization by negating coefficients)

Example: Minimize C = 2x + 3y subject to x + y ≥ 2, x + 2y ≥ 3, x, y ≥ 0

Convert:

- x + y - s₁ = 2 - x + 2y - s₂ = 3 - x, y, s₁, s₂ ≥ 0

• Maximize Z = -2x - 3y
• Introduce slacks for ≥ constraints (subtract slack variables):

Duality and Shadow Prices

Each linear program has a dual problem that provides insights:

• If the primal maximizes profit given resource constraints, the dual minimizes resource cost given production requirements
• Shadow price of a resource is how much the maximum profit increases if one more unit of that resource becomes available

Dual problems and sensitivity analysis help managers understand which constraints are most restrictive and worth relaxing.

Applications and Real-World Problems

• Production planning: Maximize profit producing multiple products with limited labor/materials
• Blending problems: Minimize cost of mixing ingredients meeting nutritional requirements
• Transportation: Minimize shipping cost moving goods from suppliers to customers
• Workforce scheduling: Minimize payroll covering all shifts
• Diet problems: Find cheapest diet meeting nutritional requirements

Connections to Other Topics

• Class 11 Linear Inequalities: Graphing and solving inequalities in 2D
• chapter-03-matrices and chapter-04-determinants: Simplex method uses matrix row operations (connections to linear algebra)
• chapter-06-application-of-derivatives: Optimization; calculus handles non-linear programs
• chapter-12-linear-programming: Constraint satisfaction and resource allocation

Socratic Questions

1. Why must the optimal solution of a linear program always occur at a corner (vertex) of the feasible region? What property of linear functions makes this true?

1. If the objective function Z = 3x + 2y is parallel to one of the constraint boundaries, what happens? Can there be multiple optimal solutions? Give a concrete example.

1. When we introduce slack variables to convert inequalities to equalities, what does a slack variable represent in the context of a business problem? When would you prefer slack to be zero?

1. The simplex method involves pivoting operations that resemble Gaussian elimination from linear algebra. Why is the simplex method guaranteed to reach an optimal solution, and why must we check specific conditions (the optimality test) to know when to stop?

1. In the dual problem, the "shadow price" of a resource tells you how much the maximum profit increases if one more unit becomes available. How would you use this information to decide whether it's worthwhile to purchase additional resources at a given market price?