Training Optimization Linear Programming
3 / 5

Linear Programming

24 min Optimization

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$.

Corners: $(0,0)$, $(7,0)$, $(4,6)$, $(0,10)$.

$z(0,0)=0$, $z(7,0)=21$, $z(4,6)=24$, $z(0,10)=20$.

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$.

Corners of feasible region: $(0,4)$, $(3,1)$, $(6,0)$.

$z(0,4) = 8$, $z(3,1) = 5$, $z(6,0) = 6$.

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?

$z = 25x + 40y$; $2x+3y \leq 120$, $x+2y \leq 80$, $x,y \geq 0$.

Corners: $(0,0)$, $(60,0)$, $(0,40)$, ... 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$. Try $(60,0)$ and $(0,40)$.

$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)

Applied Max-Min Problems Lagrange Multipliers