Training Optimization Linear Programming
3 / 5

Linear Programming

24 min Optimization
Linear programming (LP) optimizes a linear objective function z = c₁x₁ + c₂x₂ + ⋯ + cₙxₙ subject to linear inequality constraints. In two dimensions, the constraints define a convex polygonal feasible region, and the Fundamental Theorem of Linear Programming guarantees that the optimum occurs at a vertex (corner point). The graphical method evaluates the objective at each vertex to find the optimum. For larger problems, the simplex algorithm systematically moves from vertex to adjacent vertex, improving the objective at each step. LP models scheduling, blending, transportation, and resource allocation across industries. Sensitivity analysis examines how changes in constraint coefficients or resource availability affect the optimal solution.

Linear Programming

Linear Program (LP)

Optimize a linear objective function subject to linear constraints:

$$\text{Maximize } z = c_1x_1 + c_2x_2$$

subject to $\; a_{i1}x_1 + a_{i2}x_2 \leq b_i$, $\; x_1, x_2 \geq 0$.

Corner-Point Theorem

If an LP has an optimal solution, it occurs at a vertex (corner point) of the feasible region.

Graphical Method
  1. Graph each constraint as a line; shade the feasible region
  2. Identify all corner points
  3. Evaluate the objective at each corner
  4. The largest (or smallest) value is the optimum
Example 1

Maximize $z = 3x + 2y$ subject to: $x + y \leq 10$, $2x + y \leq 14$, $x,y \geq 0$.

  1. Corners: $(0,0)$, $(7,0)$, $(4,6)$, $(0,10)$.
  2. $z(0,0)=0$, $z(7,0)=21$, $z(4,6)=24$, $z(0,10)=20$.
  3. Maximum $z = 24$ at $(4, 6)$.
Example 2

Minimize $z = x + 2y$ subject to $x + y \geq 4$, $x + 3y \geq 6$, $x,y \geq 0$.

  1. Corners of feasible region:
  2. $(0,4)$, $(3,1)$, $(6,0)$.
  3. $z(0,4) = 8$, $z(3,1) = 5$, $z(6,0) = 6$.
  4. Minimum $z = 5$ at $(3,1)$.
Example 3

A factory makes chairs ($\$25$ profit) and tables ($\$40$ profit). Each chair needs 2 hrs carpentry and 1 hr finishing. Each table needs 3 hrs carpentry and 2 hrs finishing. Available: 120 hrs carpentry, 80 hrs finishing. How many of each to maximize profit?

  1. $z = 25x + 40y$; $2x+3y \leq 120$, $x+2y \leq 80$, $x,y \geq 0$.
  2. Corners: $(0,0)$, $(60,0)$, $(0,40)$, ...
  3. Solve intersection: $(2x+3y=120, x+2y=80)$ → $(x,y)=(0,40)$ or check: subtract → $y=40, x=0$ ... actually $x=80-2(40)=0$.
  4. Try $(60,0)$ and $(0,40)$.
  5. $z(60,0) = 1500$, $z(0,40) = 1600$. Max profit $= \$1{,}600$ with $0$ chairs, $40$ tables.

Practice Problems

1. Maximize $z = 5x + 4y$: $x+y \leq 8$, $2x+y \leq 12$, $x,y \geq 0$.
2. Minimize $z = 3x + 5y$: $x + 2y \geq 6$, $x \geq 0$, $y \geq 0$.
3. What is a feasible region?
4. Can the optimal solution be in the interior of the feasible region?
5. What if the feasible region is unbounded?
6. Diet problem: food A ($\$2$, 3g protein), food B ($\$3$, 5g protein). Need $\geq 30$g protein. Minimize cost.
7. How many corner points does $x+y \leq 5$, $x,y \geq 0$ have?
8. What happens when optimal value occurs at two corners?
9. Maximize $z = x + y$: $x \leq 4$, $y \leq 3$, $x+y \leq 6$, $x,y \geq 0$.
10. Define: slack variable.
11. How many variables can an LP have?
12. Is $z = x^2 + y$ a linear objective?
Show Answer Key

1. Corners: $(0,0),(6,0),(4,4),(0,8)$. $z(4,4)=36$. Max $= 36$.

2. Corner $(6,0)$: $z=18$; $(0,3)$: $z=15$. Min $= 15$ at $(0,3)$.

3. Set of all points satisfying all constraints

4. No (Corner-Point Theorem)

5. May have no finite optimum (for maximization) — check direction

6. $2x+3y$, $3x+5y \geq 30$, $x,y \geq 0$. Corner $(10,0)$: $\$20$; $(0,6)$: $\$18$. Min $= \$18$.

7. 3: $(0,0)$, $(5,0)$, $(0,5)$

8. Every point on the edge between them is also optimal (multiple optima)

9. Corners include $(4,2)$, $(3,3)$. $z(3,3)=6$, $z(4,2)=6$. Max $= 6$.

10. Variable added to convert $\leq$ inequality to equality: $x+y+s=10$, $s \geq 0$

11. Any number — but graphical methods work for 2

12. No ($x^2$ is nonlinear)

📊 2-Variable LP Solver
Optimal (x*, y*)
z* (max value)
Binding constraints
Applied Max-Min Problems Lagrange Multipliers