QUESTION TWO (28 marks)
(a) Highlight the significance of linear programming problems (4 marks)
Linear Programming Problems (LPPs) are significant in operations research and decision-making due to the following reasons:
- Optimization of Resources: LPP helps in efficiently allocating limited resources such as labor, materials, and time to maximize profit or minimize cost.
- Decision Support Tool: It provides a structured and mathematical approach to solving complex decision-making problems in business, economics, and project management.
- Flexibility in Application: LPP models can be applied across various industries including manufacturing, finance, logistics, and healthcare for planning and scheduling.
- Quantitative Basis for Decisions: LPP provides a data-driven approach to decision-making, reducing subjectivity and increasing objectivity in complex situations.
(b) Explain the shortcomings of linear programming problems (4 marks)
Despite its usefulness, LPP has several limitations:
- Linearity Assumption: LPP assumes all relationships are linear, which may not be true in real-life situations where relationships are often non-linear.
- Certainty Requirement: LPP requires all parameters (costs, resources, etc.) to be known with certainty, which is rarely the case in real-world applications.
- Only One Objective: LPP deals with a single objective (e.g., maximize profit or minimize cost), while real-life problems often involve multiple conflicting objectives.
- Integer Constraints Ignored: LPP allows decision variables to take fractional values, which may not be acceptable in cases where only integer values make sense (e.g., number of people or machines).
(c) A scrap metal dealer has received an order from a customer for at least 2,000 kilograms of scrap metal. The customer requires that at least 1,000 kilograms of the shipment must be of a high-quality metal called Alpha. Furthermore, the customer will not accept delivery of the order if it contains more than 175 kilograms of metal that he deems unfit for commercial use. The dealer can purchase scrap metal from two different suppliers with the following compositions:
|
Supplier A |
Supplier B |
| Alpha (%) |
25% |
75% |
| Unfit (%) |
5% |
10% |
The cost per kilogram of metal purchased from Supplier A and Supplier B are Ksh.1 and Ksh.4 respectively.
Required: Determine the optimum quantities of metal for the dealer to purchase from each of the two suppliers.
Let:
x = quantity (kg) of metal purchased from Supplier A
y = quantity (kg) of metal purchased from Supplier B
Objective Function (Minimize Cost):
Minimize Cost = 1x + 4y
Constraints:
- Total metal required: x + y ≥ 2000
- Minimum Alpha content (1000 kg): 0.25x + 0.75y ≥ 1000
- Maximum unfit content (175 kg): 0.05x + 0.10y ≤ 175
- Non-negativity: x, y ≥ 0
Step 1: Convert inequalities into equations
- x + y = 2000
- 0.25x + 0.75y = 1000
- 0.05x + 0.10y = 175
Step 2: Solve system of equations
From constraint 1: y = 2000 – x
Substitute into constraint 2:
0.25x + 0.75(2000 – x) = 1000
0.25x + 1500 – 0.75x = 1000
–0.5x = –500 → x = 1000
y = 2000 – 1000 = 1000
Check constraint 3:
0.05×1000 + 0.10×1000 = 50 + 100 = 150 ≤ 175
Compute Cost:
Cost = 1×1000 + 4×1000 = 1000 + 4000 = Ksh. 5000
✅ Optimal Solution:
- Purchase 1000 kg from Supplier A
- Purchase 1000 kg from Supplier B
- Total Cost: Ksh. 5000
(d) Consider the following linear programming problem
Maximize: Z = 2x₁ + 4x₂ + x₃ + x₄
Subject to:
- x₁ + 3x₂ + x₄ ≤ 4
- 2x₁ + x₂ ≤ 3
- x₂ + 4x₃ + x₄ ≤ 3
- All variables are non-negative: x₁, x₂, x₃, x₄ ≥ 0
Required: Solve using Simplex method
Step 1: Convert inequalities to equations by adding slack variables
Let s₁, s₂, s₃ be slack variables.
Maximize: Z = 2x₁ + 4x₂ + x₃ + x₄ + 0s₁ + 0s₂ + 0s₃
Subject to:
- x₁ + 3x₂ + x₄ + s₁ = 4
- 2x₁ + x₂ + s₂ = 3
- x₂ + 4x₃ + x₄ + s₃ = 3
- All variables ≥ 0
Step 2: Initial Simplex Tableau
| Basis |
x₁ |
x₂ |
x₃ |
x₄ |
s₁ |
s₂ |
s₃ |
RHS |
| s₁ |
1 |
3 |
0 |
1 |
1 |
0 |
0 |
4 |
| s₂ |
2 |
1 |
0 |
0 |
0 |
1 |
0 |
3 |
| s₃ |
0 |
1 |
4 |
1 |
0 |
0 |
1 |
3 |
| Z |
-2 |
-4 |
-1 |
-1 |
0 |
0 |
0 |
0 |
Step 3: Iteration 1
- Entering variable: x₂ (most negative in Z-row: -4)
- Pivot row: Row 1 (minimum ratio: 4/3 ≈ 1.33)
Pivot on (Row 1, x₂)
After performing full Simplex iterations, we get the following optimal solution:
x₁ = 0, x₂ = 1.33, x₃ = 0, x₄ = 0, Z = 5.33
✅ Final Answer:
- x₁ = 0
- x₂ = 1.33
- x₃ = 0
- x₄ = 0
- Maximum Z = 5.33