βœ… 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)

Chocolate
Milk (units)
Cocoa (units)
Profit per unit

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

  1. Milk constraint: x+y ≀ 5

  2. Cocoa constraint: 3x+2y ≀ 12

  3. 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:

  1. x+y=5

  2. 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