Solutions of Linear Programming Problems

Solutions of Linear Programming Problems

The graphical method is used to solve linear programming problems with two decision variables.

Key Terminology

1. Solution: A set of values for the decision variables that satisfies all constraints.
2. Feasible Region: The common region satisfying all constraints, including non-negativity restrictions. Feasible regions can be bounded (completely enclosed) or unbounded (infinite solutions).
3. Corner Points: The vertices of the feasible region. Found by inspecting the graph or solving for intersections of boundary lines.
4. Optimal Solution: A point in the feasible region that yields the optimal value (maximum or minimum) of the objective function. If an optimal solution exists, it will occur at one or more corner points.
5. Optimal Value: The maximum or minimum value of the objective function over the feasible region.

Steps for Solving LPPs Graphically

1. Summarize Information: Create a table summarizing the given data.
2. Identify Decision Variables: Define the unknowns (e.g., $x$, $y$).
3. Formulate the Objective Function: Express the quantity to be maximized or minimized as a linear function.
4. Write the Constraints: Express the limitations as linear inequalities.
5. Graph the Constraints: Draw the graph to determine the feasible region.
6. Identify Corner Points: Find the coordinates of the vertices of the feasible region.
7. Test Corner Points: Substitute the coordinates of each corner point into the objective function.
8. Conclude: State the optimal solution and optimal value based on the problem's requirements.

Examples

Example 1: Counterbook purchase

Clement has Tsh 7,200 to buy counterbooks. They cost Tsh 480 at the school shop (12 available) and Tsh 720 at the stationery store. Maximize the number of counterbooks Clement can buy.

Place	Cost (Tsh)	Available
School Shop	480	12
Stationery Store	720
Total Cash	7200

Solution:

1. Decision Variables: $x$ = counterbooks from school shop, $y$ = counterbooks from stationery store.

2. Objective Function: Maximize $f(x,y) = x + y$

3. Constraints:

   • $480x + 720y \le 7200 \Rightarrow 2x + 3y \le 30$
   • $x \le 12$
   • $x \ge 0$
   • $y \ge 0$

4. Graph: (See below)

5. Corner Points: $O(0,0)$, $A(0,10)$, $B(12,2)$, $C(12,0)$

6. Test Corner Points:

   Corner Point	$f(x,y) = x + y$
   $A(0,10)$	10
   $B(12,2)$	14
   $C(12,0)$	12
   $O(0,0)$	0

7. Conclusion: Clement can buy a maximum of 14 counterbooks (12 from the school shop and 2 from the stationery store).

Example 2: Nutrient requirements

A person needs minimum daily requirements of vitamin, protein, and fat. Two food items, $F_1$ and $F_2$, have the following contents and costs:

Nutrient	Food $F_1$	Food $F_2$	Minimum Requirement
Vitamin	20	50	800
Protein	40	20	1000
Fat	30	40	1200
Cost (Tsh)	5000	3000

a) Formulate the LPP. b) Find the combination that satisfies the requirements at the least cost.

Solution:

1. Decision Variables: $x$ = units of $F_1$, $y$ = units of $F_2$.

2. Objective Function: Minimize $f(x,y) = 5000x + 3000y$

3. Constraints:

   • $20x + 50y \ge 800 \Rightarrow 2x + 5y \ge 80$
   • $40x + 20y \ge 1000 \Rightarrow 2x + y \ge 50$
   • $30x + 40y \ge 1200 \Rightarrow 3x + 4y \ge 120$
   • $x \ge 0$
   • $y \ge 0$

4. Graph and Corner Points: (See below) Corner points: $A(0,50)$, $B(16,18)$, $C(40,0)$

5. Test Corner Points:

   Corner Point	$f(x,y) = 5000x + 3000y$
   $A(0,50)$	150,000
   $B(16,18)$	134,000
   $C(40,0)$	200,000

6. Conclusion: To minimize cost (Tsh 134,000), use 16 units of $F_1$ and 18 units of $F_2$.

Example 3: Curtain production

A firm makes ordinary and deluxe curtains. Ordinary curtains take 1.5 hours and 12 meters of material; deluxe curtains take 3 hours and 14 meters of material. 30 labor hours and 180 meters of material are available. Profits are Tsh 18,500 for ordinary and Tsh 25,500 for deluxe curtains.

a) Formulate the LPP. b) How many of each type should be made to maximize profit?

Curtain Type	Time (hours)	Material (meters)	Profit (Tsh)
Ordinary	1.5	12	18,500
Deluxe	3	14	25,500
Total Available	30	180

Solution:

1. Decision Variables: $x$ = ordinary curtains, $y$ = deluxe curtains.

2. Objective Function: Maximize $f(x,y) = 18500x + 25500y$

3. Constraints:

   • $1.5x + 3y \le 30 \Rightarrow x + 2y \le 20$
   • $12x + 14y \le 180 \Rightarrow 6x + 7y \le 90$
   • $x \ge 0$
   • $y \ge 0$

4. Graph and Corner Points: (See below) Corner points: $O(0,0)$, $A(0,10)$, $B(8,6)$, $C(15,0)$

5. Test Corner Points:

   Corner Point	$f(x,y) = 18500x + 25500y$
   $O(0,0)$	0
   $A(0,10)$	255,000
   $B(8,6)$	301,000
   $C(15,0)$	277,500

6. Conclusion: Maximum profit (Tsh 301,000) is achieved by making 8 ordinary and 6 deluxe curtains.

Example 5: Retail shop orders

A retail shop received orders from customers C1 and C2 for food packages. C1's package: 50 kg beans, 30 kg rice, 70 kg maize. C2's package: 25 kg beans, 45 kg rice. Stock: 850 kg beans, 810 kg rice, 980 kg maize. C1's package costs Tsh 2,100, C2's Tsh 1,800.

a) Formulate the LPP. b) How many packages should be supplied to maximize sales? c) How much stock remains?

Customer	Beans (kg)	Rice (kg)	Maize (kg)	Cost (Tsh)
C1	50	30	70	2,100
C2	25	45	0	1,800
Stock	850	810	980

Solution:

1. Decision Variables: $x$ = packages for C1, $y$ = packages for C2.

2. Objective Function: Maximize $f(x,y) = 2100x + 1800y$

3. Constraints:

   • $50x + 25y \le 850 \Rightarrow 2x + y \le 34$
   • $30x + 45y \le 810 \Rightarrow 2x + 3y \le 54$
   • $70x \le 980 \Rightarrow x \le 14$
   • $x \ge 0$
   • $y \ge 0$

4. Graph and Corner Points: (See below) Corner points: $O(0,0)$, $A(0,18)$, $B(12,10)$, $C(14,6)$, $D(14,0)$

5. Test Corner Points:

   Corner Point	$f(x,y) = 2100x + 1800y$
   $O(0,0)$	0
   $A(0,18)$	32,400
   $B(12,10)$	43,200
   $C(14,6)$	38,400
   $D(14,0)$	29,400

6. Conclusion (b): To maximize sales (Tsh 43,200), supply 12 packages to C1 and 10 packages to C2.

7. Stock Remaining (c):

   • Beans: $(12 \times 50) + (10 \times 25) = 600 + 250 = 850$ kg (All beans used)
   • Rice: $(12 \times 30) + (10 \times 45) = 360 + 450 = 810$ kg (All rice used)
   • Maize: $(12 \times 70) + (10 \times 0) = 840$ kg. Stock remaining: $980 - 840 = 140$ kg