Training Industrial Engineering Linear Programming — Formulation & Graphical Method
1 / 5

Linear Programming — Formulation & Graphical Method

24 min Industrial Engineering

Linear Programming — Formulation & Graphical Method

Linear programming (LP) finds the optimal value of a linear objective function subject to linear constraints. It is a cornerstone of operations research.

Standard LP Form

$$\text{Maximize (or Minimize)} \quad Z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n$$

Subject to:

$$a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{in}x_n \le b_i \quad (i = 1, 2, \ldots, m)$$

$$x_j \ge 0 \quad (j = 1, 2, \ldots, n)$$

Corner Point Theorem

The optimal solution to an LP occurs at a corner point (vertex) of the feasible region.

Example 1

Maximize $Z = 5x + 4y$ subject to: $x + y \le 10$, $2x + y \le 14$, $x \ge 0$, $y \ge 0$.

Corner points: $(0,0)$, $(7,0)$, $(4,6)$, $(0,10)$.

$Z(0,0)=0$, $Z(7,0)=35$, $Z(4,6)=44$, $Z(0,10)=40$.

Maximum: $Z = 44$ at $(4, 6)$.

Example 2

Minimize $C = 3x + 2y$ subject to: $x + 2y \ge 8$, $3x + 2y \ge 12$, $x \ge 0$, $y \ge 0$.

Corner points of the feasible region: $(0,6)$, $(2,3)$, $(8,0)$.

$C(0,6)=12$, $C(2,3)=12$, $C(8,0)=24$.

Minimum: $C = 12$ at both $(0,6)$ and $(2,3)$ — multiple optima along the edge.

Example 3

A factory makes chairs and tables. Chairs yield \$20 profit, tables \$30. Each chair takes 2 hrs assembly + 1 hr finishing; each table takes 3 hrs assembly + 2 hrs finishing. Available: 120 hrs assembly, 80 hrs finishing. How many of each?

Let $x$ = chairs, $y$ = tables.

Maximize $Z = 20x + 30y$ subject to $2x + 3y \le 120$, $x + 2y \le 80$, $x,y \ge 0$.

Corner points: $(0,0), (60,0), (0,40), (24,24)$. Checking the intersection of $2x+3y=120$ and $x+2y=80$: $x=24, y=24$.

$Z(24,24) = 480+720 = 1{,}200$. Maximum profit: \$1,200.

Practice Problems

1. Max $Z = 3x + 5y$ subject to $x + y \le 8$, $x + 3y \le 18$, $x,y \ge 0$.
2. Min $C = 2x + 3y$ subject to $x + y \ge 6$, $2x + y \ge 8$, $x,y \ge 0$.
3. A company makes products A (\$4 profit) and B (\$6 profit). A needs 1 hr machine + 2 hrs labor; B needs 2 hrs machine + 1 hr labor. Available 10 hrs each. Maximize profit.
4. Identify all corner points: $x \le 6$, $y \le 5$, $x + y \le 9$, $x,y \ge 0$.
5. What happens if the feasible region is empty?
6. What happens if the feasible region is unbounded and you maximize?
7. Sensitivity: in Example 1, if assembly hours increase to 130, how does the optimal solution change?
8. Dual: write the dual of the LP in Problem 1.
9. Integer LP: Max $Z = 7x + 5y$ subject to $2x + y \le 10$, $x \ge 0$, $y \ge 0$, $x,y$ integer. Find the optimal integer solution.
10. A diet problem: minimize cost $= 2x + 3y$ subject to $x + y \ge 10$ (protein), $x + 2y \ge 14$ (fiber), $x,y \ge 0$.
11. Transportation: 2 sources, 3 destinations. Formulate as an LP.
12. Max $Z = x + y$ s.t. $x + y \le 10$, $x - y \le 4$, $y \le 7$, $x,y \ge 0$.
Show Answer Key

1. Corners: $(0,0),(8,0),(3,5),(0,6)$. $Z(3,5)=34$, $Z(8,0)=24$, $Z(0,6)=30$. Max $Z=34$ at $(3,5)$.

2. Corners: $(0,8),(2,4),(6,0)$. $C(0,8)=24$, $C(2,4)=16$, $C(6,0)=12$. Min $C=12$ at $(6,0)$. Verify feasibility.

3. $x+2y \le 10$, $2x+y \le 10$, max $4x+6y$. Corners include $(10/3, 10/3)$. $Z \approx 33.3$ at that point.

4. $(0,0),(6,0),(6,3),(4,5),(0,5)$

5. The LP is infeasible — no solution exists.

6. The LP is unbounded — $Z \to \infty$.

7. Re-solve with the new constraint $2x+3y \le 130$; the optimal shifts.

8. Min $W = 8u + 18v$ s.t. $u+v \ge 3$, $u+3v \ge 5$, $u,v \ge 0$.

9. Continuous optimum at $(5,0)$ gives $Z=35$. Check $(4,2)$: $Z=38$; $(3,4)$: $Z=41$, but $2(3)+4=10$ ✓. Max $Z=41$ at $(3,4)$.

10. Corners: $(0,10),(6,4),(14,0)$. Note $(6,4)$: cost $=24$; $(0,10)$: cost $=30$. Check feasibility to find the optimal corner.

11. Decision variables $x_{ij}$: amount shipped from source $i$ to destination $j$. Supply and demand constraints.

12. Corners: $(0,0),(4,0),(7,3),(3,7),(0,7)$. $Z(3,7)=10$, $Z(7,3)=10$. Max $Z=10$.

Statistical Process Control