β 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