LPP

 

 

PEML3001 — DECISION MAKING AND OPTIMIZATION LABORATORY

LINEAR PROGRAMMING PROBLEM

Complete Integrated Solution

The Super Fast Manufacturing Company — Product-Mix Problem

Graphical Method · Simplex Method · Sensitivity Analysis · Branch & Bound

Prepared by: Vimal Noble

M.Tech — Project Engineering and Management (2024–26)

Birsa Institute of Technology (BIT) Sindri

Affiliated to Jharkhand University of Technology (JUT), Ranchi

 

1. Problem Statement

The Super Fast Manufacturing Company produces two items, P and V. Both items pass through three processes — Lathe, Grinder and Polishing — and both consume steel as raw material. Item P additionally requires polishing time; item V does not.

Resource	Product P	Product V	Availability
Steel	400 g/unit	350 g/unit	250,000 g (250 kg)
Lathe	85 min/unit	50 min/unit	30% × 1,450 hrs = 26,100 min
Grinder	55 min/unit	30 min/unit	50% × 1,450 hrs = 43,500 min
Polishing	20 min/unit	0 min/unit	20% × 1,450 hrs = 17,400 min
Profit/unit	₹40	₹30	Maximize Z

 

Market restriction: the company cannot sell more units of P than of V — i.e., production of P must not exceed production of V.

2. Decision Variables

•      x₁ = number of units of Product P produced per week

•      x₂ = number of units of Product V produced per week

3. Mathematical Formulation

Objective Function (Maximize Profit)

Maximize  Z = 40x₁ + 30x₂

Constraints

Constraint	Mathematical Form	Type
Steel	400x₁ + 350x₂ ≤ 250,000	≤
Lathe	85x₁ + 50x₂ ≤ 26,100	≤
Grinder	55x₁ + 30x₂ ≤ 43,500	≤
Polishing	20x₁ ≤ 17,400  →  x₁ ≤ 870	≤
Market Rule	x₁ ≤ x₂   (i.e., x₁ − x₂ ≤ 0)	≤
Non-negativity	x₁ ≥ 0, x₂ ≥ 0	—

 

Simplified Form (dividing common factors)

•      Steel:  8x₁ + 7x₂ ≤ 5,000   (÷50)

•      Lathe:  17x₁ + 10x₂ ≤ 5,220   (÷5)  — the bottleneck

•      Grinder:  11x₁ + 6x₂ ≤ 8,700   (÷5)

•      Polishing:  x₁ ≤ 870

•      Market:  x₁ − x₂ ≤ 0

 

4. Constraint Lines — Intercepts for Graphing

To plot each constraint as a straight line, set x₂ = 0 to obtain the x₁-intercept, and x₁ = 0 to obtain the x₂-intercept.

Constraint Line	x₁-intercept	x₂-intercept
Steel: 8x₁+7x₂=5,000	625	714.28
Lathe: 17x₁+10x₂=5,220	307.06	522
Grinder: 11x₁+6x₂=8,700	790.9	1,450
Polishing: x₁=870	870	— (vertical line)
Market: x₁=x₂	origin, slope 45°	origin, slope 45°

5. Graphical Method — Solution

Step A: Locate the Bottleneck

Compare profit generated per minute of the scarcest resource (Lathe):

Resource	Profit/min — P	Profit/min — V
Lathe (bottleneck)	40/85 = 0.47	30/50 = 0.60 ✅

 

Product V yields more profit per minute of Lathe time — the scarcest resource. The optimal strategy therefore favours maximising V production.

Step B: Corner Points of the Feasible Region

•      O (0, 0) — origin

•      A (0, 522) — intersection of the y-axis (x₁ = 0) and the Lathe line: 10x₂ = 5,220

•      B (193.33, 193.33) — intersection of Market line (x₁ = x₂) and Lathe line: 27x₁ = 5,220

Step C: Evaluate the Objective Function at Each Vertex

Corner Point	Coordinates (x₁, x₂)	Z = 40x₁ + 30x₂
O	(0, 0)	₹0
B	(193.33, 193.33)	₹13,533
A	(0, 522)	₹15,660  ★ MAXIMUM

 

Figure 1: Feasible region O–B–A with the optimal point A(0, 522)

Graphical Conclusion

The optimal solution lies uniquely at extreme point A(0, 522), giving a maximum weekly profit of ₹15,660.

 

6. Simplex Method — Algebraic Proof

Convert the LP to standard form by adding slack variables s₁…s₅:

•      8x₁ + 7x₂ + s₁ = 5,000

•      17x₁ + 10x₂ + s₂ = 5,220

•      11x₁ + 6x₂ + s₃ = 8,700

•      x₁ + s₄ = 870

•      x₁ − x₂ + s₅ = 0

Initial basic feasible solution: x₁ = 0, x₂ = 0, Z = 0.

Iteration 1 — Entering Variable

x₂ has the largest positive coefficient (30) in Z. Ratio test (RHS ÷ coefficient of x₂):

Row	Constraint	Ratio
s₁	7x₂ ≤ 5,000	714.28
s₂	10x₂ ≤ 5,220	522 ← minimum (pivot)
s₃	6x₂ ≤ 8,700	1,450
s₅	−x₂ ≤ 0	ignored (negative)

 

Pivot on row s₂: x₂ enters, s₂ leaves. New row:  x₂ = 522 − 1.7x₁ − 0.1s₂

Substituting into the objective function:

Z = 15,660 − 11x₁ − 3s₂

Optimality Check

All non-basic variables (x₁, s₂) carry negative coefficients in the Z-row ⇒ the current solution is optimal.

Optimal BFS:  x₁ = 0,  x₂ = 522,  Z = ₹15,660

 

7. Binding, Non-Binding & Redundant Constraints

Substituting the optimal solution (x₁ = 0, x₂ = 522) into every constraint:

Constraint	LHS at Optimum	RHS	Slack	Status
Lathe	10(522) = 5,220	5,220	0	Binding
Steel	7(522) = 3,654	5,000	1,346	Slack
Grinder	6(522) = 3,132	8,700	5,568	Slack
Polishing	0	870	870	Redundant
Market	0 ≤ 522	0	522	Slack

 

Why Polishing is Redundant

The feasible region is strictly bounded by x₁ ≤ 193.33 (intersection of Market and Lathe constraints), which never approaches the Polishing limit of x₁ ≤ 870. Removing the Polishing constraint entirely does not alter the optimal solution or the shape of the feasible region.

8. Unique vs Multiple Optimal Solutions

Multiple optima exist only if the objective function's slope equals the slope of a binding constraint that forms a boundary edge in the direction of optimal movement.

Line	Slope
Objective: Z = 40x₁+30x₂  →  x₂ = −4/3 x₁ + Z/30	−1.333
Binding Lathe: 17x₁+10x₂=5,220  →  x₂ = −1.7x₁+522	−1.700

 

Since −1.333 ≠ −1.700, the objective function is not parallel to the binding constraint.

Conclusion: The optimal solution is UNIQUE — no alternate optima exist.

 

9. Infeasibility and Unboundedness Check

Infeasibility

A problem is infeasible only if no point satisfies every constraint simultaneously. Here, the origin (0,0) satisfies all five constraints (0 ≤ 5,000; 0 ≤ 5,220; 0 ≤ 8,700; 0 ≤ 870; 0 ≤ 0). A feasible point exists, so infeasibility is absent.

Unboundedness

A maximization LPP is unbounded only if Z can be increased indefinitely within the feasible region. Here x₁ is capped by 870 and the Market rule, while x₂ is capped by the Lathe limit (522). The feasible region is a closed, bounded polygon (O–B–A) — unboundedness is absent.

10. Convex Sets and the Extreme-Point Theorem

The feasible region formed by the intersection of the linear constraints is a convex polyhedron — any line segment joining two points inside the region lies entirely within it.

•      The optimal solution A(0, 522) is an extreme point (corner/vertex) of this convex set.

•      By the Extreme Point Theorem (Fundamental Theorem of LP), if an optimal solution exists, at least one extreme point achieves it.

•      This is why evaluating only the finite corner points O, B, A — instead of the infinite interior — is sufficient to guarantee the global optimum.

 

11. Sensitivity Analysis — Shadow Prices

Since Lathe is the only binding constraint, its dual (shadow) price represents the maximum premium the firm should pay for one additional minute of Lathe time.

Shadow Price (Lathe) = 30 / 50 = ₹0.60 per minute (≈ ₹36/hour)

Constraint	Shadow Price
Lathe (binding)	₹0.60 / min
Steel, Grinder, Polishing, Market (all slack)	₹0 — surplus capacity, non-restrictive

 

Managerial Interpretation

•      Bottleneck: Lathe machine time is the single limiting resource driving the production plan.

•      Overcapacity: Steel, Grinder and Polishing carry large idle capacities and could be reduced or diverted without affecting profit.

•      Outsourcing decision: Paying up to ₹0.60/minute (₹36/hour) to acquire extra Lathe capacity remains profitable; paying more erodes net profit.

•      Market strategy: The rule x₁ ≤ x₂ is not currently restrictive — Product P should only be considered once demand for V is exhausted.

 

12. Branch and Bound (Integer Verification)

Branch & Bound (B&B) confirms integer feasibility for Integer Linear Programming. It first solves the LP relaxation, then branches only if the result is fractional.

Step 1 — LP Relaxation

x₁ = 0,  x₂ = 522,  Z = ₹15,660

Step 2 — Integrality Check

Both 0 and 522 are already integers, so the LP relaxation is itself the integer-optimal solution. No branching is required:

•      Root Node (LP Relaxation): x₁ = 0, x₂ = 522, Z = 15,660 → Feasible & Integer → solution accepted, search tree pruned.

 

(If the optimum had instead been fractional, e.g. x₁ = 193.33, B&B would branch on x₁ ≤ 193 and x₁ ≥ 194, solving each sub-LP and discarding infeasible or dominated branches until an integer optimum is isolated.)

 

13. Consolidated Summary

Criterion	Finding
Optimal Production	x₁ = 0 units of P;  x₂ = 522 units of V
Maximum Profit	₹15,660 per week
Method Used	Graphical (corner-point) + Simplex (algebraic proof)
Binding Constraint	Lathe machine — fully utilised (0 slack)
Non-Binding Constraints	Steel, Grinder, Market Rule
Redundant Constraint	Polishing (x₁ ≤ 870)
Optimality Type	Unique — no multiple optima
Feasibility	Feasible (origin satisfies all constraints)
Boundedness	Bounded — closed polygon O–B–A
Shadow Price (Lathe)	₹0.60/minute (₹36/hour)
Convexity	Feasible region is convex; optimum at extreme point A
Integer Check (B&B)	LP optimum already integer — no branching needed

 

Final Takeaway

The Lathe machine is the decisive bottleneck. The optimal strategy is to abandon Product P entirely and dedicate all Lathe capacity to Product V, producing exactly 522 units for a weekly profit of ₹15,660. Steel and Grinder capacity remain substantially idle, indicating the firm should consider reallocating or reducing procurement of these resources, or investing in additional Lathe capacity to scale production further.