Linear Programming: Word Problems and Applications

A store sells two types of toys, A and B. The store owner pays \( $8 \) and \( $14 \) for each unit of toy A and B respectively. One unit of toy A yields a profit of \( $2 \), while a unit of toy B yields a profit of \( $3 \). The store owner estimates that no more than 2,000 toys will be sold every month, and he does not plan to invest more than \( $20,000 \) in inventory. How many units of each type of toy should be stocked to maximize total monthly profit?

---

Solution

Let \( x \) be the number of toys A and \( y \) the number of toys B. Since quantities cannot be negative:

\[ x \ge 0 \quad \text{and} \quad y \ge 0 \]

The total volume constraint (no more than 2000 toys):

\[ x + y \le 2000 \]

The total investment constraint ($8 for A, $14 for B, budget $20,000):

\[ 8x + 14y \le 20000 \]

The objective function to maximize profit \( P \):

\[ P = 2x + 3y \]

Combining these, we graph the feasible region and find its vertices:

Vertices of the feasible region:

• Point A: \( (0, 0) \)
• Point B: \( (0, 1428.57) \) — from \( 14y = 20000 \)
• Point C: Intersection of \( x + y = 2000 \) and \( 8x + 14y = 20000 \): \[ \begin{cases} x + y = 2000 \\ 8x + 14y = 20000 \end{cases} \] From the first: \( y = 2000 - x \). Substitute: \( 8x + 14(2000 - x) = 20000 \implies 8x + 28000 - 14x = 20000 \implies -6x = -8000 \implies x = \frac{4000}{3} \approx 1333.33 \), \( y = 2000 - 1333.33 = \frac{2000}{3} \approx 666.67 \). So \( C \approx (1333.33, 666.67) \).
• Point D: \( (2000, 0) \)

Testing the continuous vertices (for reference):

\[ P(A) = 0, \quad P(B) = 2(0) + 3(1428.57) = 4285.71, \quad P(C) = 2(1333.33) + 3(666.67) = 4666.67, \quad P(D) = 4000 \]

Since we must sell whole toys (integer values), we evaluate the closest integer coordinates inside the feasible region near the theoretical maximum at Point C.

Testing integer point \( (1334, 666) \):

• Total toys: \( 1334 + 666 = 2000 \le 2000 \) (Valid)
• Total cost: \( 8(1334) + 14(666) = 10672 + 9324 = 19996 \le 20000 \) (Valid)
• Profit: \( P = 2(1334) + 3(666) = 2668 + 1998 = \mathbf{4666} \)

Testing integer point \( (1333, 667) \):

• Total toys: \( 1333 + 667 = 2000 \le 2000 \) (Valid)
• Total cost: \( 8(1333) + 14(667) = 10664 + 9338 = 20002 > 20000 \) (Invalid)

Conclusion: The maximum achievable profit with integer inventory is $4,666, which occurs when the store stocks 1,334 units of toy A and 666 units of toy B.

A company produces two types of tables, T1 and T2. For T1, it takes 2 hours for parts, 1 hour to assemble, and 2 hours to polish. For T2, it takes 4 hours for parts, 2.5 hours to assemble, and 1.5 hours to polish. Monthly available hours are: 7,000 for parts, 4,000 for assembly, and 5,500 for polishing. The profit is \( $90 \) for T1 and \( $110 \) for T2. How many of each should be produced to maximize profit?

---

Solution

Let \( x \) = number of T1 tables, and \( y \) = number of T2 tables. The objective function for profit is:

\[ P(x, y) = 90x + 110y \]

We graph the system of constraints:

\[ \begin{cases} x \ge 0, \quad y \ge 0 \\ 2x + 4y \le 7000 \quad \text{(parts)} \\ x + 2.5y \le 4000 \quad \text{(assembly)} \\ 2x + 1.5y \le 5500 \quad \text{(polishing)} \end{cases} \]

Vertices of the feasible region:

• \( A(0, 0) \)
• \( B(0, 1600) \) (from assembly: \( 2.5y = 4000 \))
• \( C(1500, 1000) \) (Intersection of parts \( 2x + 4y = 7000 \) and assembly \( x + 2.5y = 4000 \))
• \( D(2300, 600) \) (Intersection of parts \( 2x + 4y = 7000 \) and polishing \( 2x + 1.5y = 5500 \))
• \( E(2750, 0) \) (from polishing: \( 2x = 5500 \))

Evaluating the profit at each vertex:

\[ \begin{aligned} P(A) &= 90(0) + 110(0) = \$0 \\ P(B) &= 90(0) + 110(1600) = \$176{,}000 \\ P(C) &= 90(1500) + 110(1000) = \$245{,}000 \\ P(D) &= 90(2300) + 110(600) = \mathbf{\$273{,}000} \\ P(E) &= 90(2750) + 110(0) = \$247{,}500 \end{aligned} \]

Conclusion: To achieve the maximum profit of $273,000, the company should produce 2,300 T1 tables and 600 T2 tables.

A farmer mixes two types of food. Food A costs \( $10/bag \) (40 units protein, 20 minerals, 10 vitamins). Food B costs \( $12/bag \) (30 units protein, 20 minerals, 30 vitamins). Minimum daily requirements: 150 protein, 90 minerals, 60 vitamins. How many bags of each should be used daily to minimize cost?

---

Solution

Let \( x \) = bags of Food A, and \( y \) = bags of Food B. Objective function to minimize cost:

\[ C(x, y) = 10x + 12y \]

Nutritional constraints:

\[ \begin{cases} x \ge 0, \quad y \ge 0 \\ 40x + 30y \ge 150 \quad \text{(protein)} \\ 20x + 20y \ge 90 \quad \text{(minerals)} \\ 10x + 30y \ge 60 \quad \text{(vitamins)} \end{cases} \]

Vertices of the feasible (unbounded) region:

• \( A(6, 0) \) (from vitamins line: \( 10x = 60 \))
• \( B(3.75, 0.75) \) (Intersection of vitamins \( 10x + 30y = 60 \) and minerals \( 20x + 20y = 90 \))
• \( C(1.5, 3) \) (Intersection of minerals \( 20x + 20y = 90 \) and protein \( 40x + 30y = 150 \))
• \( D(0, 5) \) (from protein line: \( 30y = 150 \))

Evaluate the cost at each vertex:

\[ \begin{aligned} C(A) &= 10(6) + 12(0) = \$60.00 \\ C(B) &= 10(3.75) + 12(0.75) = 37.50 + 9.00 = \mathbf{\$46.50} \\ C(C) &= 10(1.5) + 12(3) = 15 + 36 = \$51.00 \\ C(D) &= 10(0) + 12(5) = \$60.00 \end{aligned} \]

Conclusion: The minimum daily cost is $46.50, achieved by mixing 3.75 bags of Food A and 0.75 bags of Food B.

John has \( $20,000 \) to invest in three funds: F1 (2% return, low risk), F2 (4% return, medium risk), F3 (5% return, high risk). He will invest no more than $3,000 in F3 and at least twice as much in F1 as in F2. How much should he invest in each fund to maximize annual return?

---

Solution

Let \( x \) = amount in F1, \( y \) = amount in F2, \( z \) = amount in F3. We eliminate \( z \) using \( x + y + z = 20000 \implies z = 20000 - (x + y) \).

The return \( R \) function is:

\[ R = 0.02x + 0.04y + 0.05z = 0.02x + 0.04y + 0.05(20000 - x - y) = 1000 - 0.03x - 0.01y \]

Constraints mapping strictly to \( x \) and \( y \):

\[ \begin{cases} x \ge 0, \quad y \ge 0 \\ x + y \le 20000 \quad (\text{since } z \ge 0) \\ x + y \ge 17000 \quad (\text{since } z \le 3000) \\ x \ge 2y \end{cases} \]

Vertices:

• \( A(20000, 0) \) (from \( x + y = 20000 \) and \( y = 0 \))
• \( B(17000, 0) \) (from \( x + y = 17000 \) and \( y = 0 \))
• \( C\left(\frac{34000}{3}, \frac{17000}{3}\right) \approx (11333.33, 5666.67) \) (Intersection of \( x = 2y \) and \( x + y = 17000 \))
• \( D\left(\frac{40000}{3}, \frac{20000}{3}\right) \approx (13333.33, 6666.67) \) (Intersection of \( x = 2y \) and \( x + y = 20000 \))

Evaluating the return \( R \):

\[ \begin{aligned} R(A) &= 1000 - 0.03(20000) - 0.01(0) = 1000 - 600 = \$400.00 \\ R(B) &= 1000 - 0.03(17000) - 0.01(0) = 1000 - 510 = \$490.00 \\ R(C) &= 1000 - 0.03(11333.33) - 0.01(5666.67) = 1000 - 340 - 56.67 = \mathbf{\$603.33} \\ R(D) &= 1000 - 0.03(13333.33) - 0.01(6666.67) = 1000 - 400 - 66.67 = \$533.33 \end{aligned} \]

Conclusion: The maximum return is $603.33, found by investing $11,333.33 in F1, $5,666.67 in F2, and the remaining $3,000.00 in F3.

A store owner can spend at most \( $100,000 \) monthly on PCs and laptops. A PC costs \( $1,000 \) and yields \( $400 \) profit; a laptop costs \( $1,500 \) and yields \( $700 \) profit. At least 15 PCs but no more than 80 are sold monthly. Laptop sales are at most half of PC sales. How many of each should be sold to maximize profit?

---

Solution

Let \( x \) = number of PCs, \( y \) = number of laptops. Objective function:

\[ P = 400x + 700y \]

Constraints:

\[ \begin{cases} 15 \le x \le 80 \\ y \ge 0 \\ y \le 0.5x \\ 1000x + 1500y \le 100000 \implies 2x + 3y \le 200 \end{cases} \]

Vertices of the continuous region:

• \( A(15, 0) \)
• \( B(15, 7.5) \) (from \( y = 0.5x \) at \( x = 15 \))
• \( C\left(\frac{400}{7}, \frac{200}{7}\right) \approx (57.14, 28.57) \) (Intersection of \( y = 0.5x \) and \( 2x + 3y = 200 \))
• \( D\left(80, \frac{40}{3}\right) \approx (80, 13.33) \) (Intersection of \( x = 80 \) and budget line \( 2x + 3y = 200 \))

Because units must be integers, we cannot sell fractional PCs. The maximum profit occurs near \( C(57.14, 28.57) \). We must test valid integer coordinates slightly inside the boundaries.

Testing nearby integers:

• If \( x = 57 \), the budget gives \( 3y \le 200 - 2(57) = 86 \implies y \le 28.67 \). Maximum integer \( y = 28 \). Check \( y \le 0.5(57) = 28.5 \) ✓. Profit: \( P = 400(57) + 700(28) = 22800 + 19600 = \$42{,}400 \).
• If \( x = 58 \), the budget gives \( 3y \le 200 - 2(58) = 84 \implies y \le 28 \). Maximum integer \( y = 28 \). Check \( y \le 0.5(58) = 29 \) ✓. Profit: \( P = 400(58) + 700(28) = 23200 + 19600 = \mathbf{\$42{,}800} \).
• If \( x = 59 \), the budget gives \( 3y \le 200 - 2(59) = 82 \implies y \le 27.33 \). Maximum integer \( y = 27 \). Profit: \( P = 400(59) + 700(27) = 23600 + 18900 = \$42{,}500 \).

Conclusion: To strictly respect budget constraints and sell whole units, the maximum integer solution yields $42,800 when the owner sells 58 PCs and 28 laptops.