✅ Why do we need Linear Programming?
To optimize use of limited resources To help in strategic decision-making Common in manufacturing, transportation, finance, and logistics
📦 Example Problem: Chocolate Manufacturing Company
🟤 Produces Two Chocolates: A and B
Each unit of A and B requires:
Milk and Cocoa (quantities shown below)
A
1
3
₹6
B
1
2
₹5
Total resources available:
Milk: 5 units
Cocoa: 12 units
✅ Step 1: Define Variables
Let:
x = number of units of chocolate A
y = number of units of chocolate B
✅ Step 2: Objective Function
Maximize Profit:
Z=6x+5y
✅ Step 3: Constraints
Milk constraint: x+y ≤ 5
Cocoa constraint: 3x+2y ≤ 12
Non-negativity: x≥0, y≥0
✅ Step 4: Find Corner Points
Let’s solve the system manually by checking intercepts and intersections:
🔹 Constraint 1: x+y=5
If x=0 , then y=5
If y=0, then x=5
Line passes through (0, 5) and (5, 0)
🔹 Constraint 2: 3x+2y=12
If x=0x = 0x=0, then 2y=12⇒y=62y = 12 \Rightarrow y = 62y=12⇒y=6
If y=0y = 0y=0, then 3x=12⇒x=43x = 12 \Rightarrow x = 43x=12⇒x=4
Line passes through (0, 6) and (4, 0)
🔹 Find Point of Intersection
Solve:
x+y=5
3x+2y=12
Substitute y=5−x into 2:
3x+2(5−x)=123x+10−2x=12x=2⇒y=33x + 2(5 - x) = 12 \\ 3x + 10 - 2x = 12 \\ x = 2 \Rightarrow y = 33x+2(5−x)=123x+10−2x=12x=2⇒y=3
🟢 Intersection point: (2,3)
✅ Step 5: Evaluate Profit at Feasible Points
Check all corner points of the feasible region:
Point
Check x+y≤5x + y \leq 5x+y≤5
3x+2y≤123x + 2y \leq 123x+2y≤12
Z=6x+5yZ = 6x + 5yZ=6x+5y
(0, 0)
✅
✅
0
(0, 5)
✅
3(0)+2(5)=10≤123(0) + 2(5) = 10 \leq 123(0)+2(5)=10≤12 ✅
25
(5, 0)
✅
3(5)=15>123(5) = 15 > 123(5)=15>12 ❌
-
(4, 0)
✅
✅
24
(2, 3)
✅
✅
6×2+5×3=12+15=276×2 + 5×3 = 12 + 15 = 276×2+5×3=12+15=27 ✅
✅ Final Answer:
Optimal solution: x=2, y=3x = 2,\ y = 3x=2, y=3
Produce:
2 units of Chocolate A
3 units of Chocolate B
Maximum Profit: ₹27
// Some code
import matplotlib.pyplot as plt
import numpy as np
# Define new constraints
x = np.linspace(0, 10, 400)
y1 = 5 - x # From x + y <= 5 (milk constraint)
y2 = (12 - 3*x) / 2 # From 3x + 2y <= 12 (cocoa constraint)
# Setup plot
plt.figure(figsize=(8, 6))
# Plot constraint lines
plt.plot(x, y1, label=r'$x + y \leq 5$', color='blue')
plt.plot(x, y2, label=r'$3x + 2y \leq 12$', color='green')
# Fill feasible region
y_feasible = np.minimum(y1, y2)
plt.fill_between(x, 0, y_feasible, where=(y_feasible >= 0), color='skyblue', alpha=0.5, label='Feasible Region')
# Plot feasible corner points
points = {
"A (0,0)": (0, 0),
"B (0,5)": (0, 5),
"C (4,0)": (4, 0),
"D (2,3)": (2, 3), # Intersection point
}
for label, (px, py) in points.items():
plt.plot(px, py, 'ro')
plt.text(px + 0.2, py + 0.2, label, fontsize=10)
# Highlight optimal point (2, 3)
plt.plot(2, 3, 'ko', markersize=8, label='Optimal Solution (2, 3)')
# Chart decorations
plt.xlim(0, 8)
plt.ylim(0, 8)
plt.xlabel('Units of Chocolate A (x)')
plt.ylabel('Units of Chocolate B (y)')
plt.title('Feasible Region - Chocolate Production (Updated Constraints)')
plt.grid(True)
plt.legend()
plt.tight_layout()
plt.show()
Last updated