2.2 Examples of Linear Programming Problems

Understanding real-world applications of linear programming through classic examples.

Diet Problem
Find the minimum cost diet that satisfies nutritional requirements
$2.00
$5.00
$1.50
$4.00
$3.00
Nutritional Requirements
Protein
≥ 50g/day
Carbs
≥ 200g/day
Fat
≥ 30g/day
Find the minimum cost combination of foods that meets all nutritional requirements
Manufacturing Problem
Maximize profit by allocating resources to different products
Product A$100/unit
Product B$150/unit
Product C$200/unit
Resource Constraints
Labor
≤ 1000 hours
Machine Time
≤ 800 hours
Materials
≤ 500 units
Maximize revenue while staying within resource constraints
Transportation Problem
Minimize shipping costs between sources and destinations
Factory ASupply: 100
Factory BSupply: 150
Factory CSupply: 200
Shipping Routes
Warehouse X
Demand: 120
Warehouse Y
Demand: 180
Warehouse Z
Demand: 150
Minimize total shipping costs while meeting supply and demand constraints
Maximal Flow Problem
Find the maximum flow from source to sink in a capacitated network
Network Flow
Source
Sink
Node 2
Node 3
Node 4
Capacity: 5
Capacity: 3
Capacity: 4
Flow Conservation
Source
Net outflow = f
Sink
Net inflow = f
Find the maximum flow from source to sink while respecting capacity constraints
Warehousing Problem
Optimize warehouse operations by buying and selling stock to maximize profit
Warehousing Problem
Optimize warehouse operations by buying and selling stock to maximize profit over time
Warehouse Capacity: C
Period 1
p₁
Period 2
p₂
Period 3
p₃

Stock Variables

  • xᵢ: Stock level at beginning of period i
  • uᵢ: Amount bought during period i
  • sᵢ: Amount sold during period i
  • zᵢ: Slack variable for capacity constraint

Parameters

  • C: Warehouse capacity
  • r: Holding cost per unit per period
  • pᵢ: Price in period i
  • n: Number of time periods

Mathematical Formulation

Objective: Maximize ∑i=1n(pᵢ(sᵢ - uᵢ) - rxᵢ)
Subject to:
  • xi+1 = xᵢ + uᵢ - sᵢ for i = 1, 2, ..., n-1
  • 0 = xn + un - sn
  • xᵢ + zᵢ = C for i = 2, ..., n
  • x₁ = 0, xᵢ > 0, uᵢ > 0, sᵢ > 0, zᵢ > 0

Interactive Learning

Interactive Diet Problem

Step 1: Understanding the Problem

Food Selection

Rice$2/unit
Quantity: 0 units
Beans$3/unit
Quantity: 0 units
Chicken$5/unit
Quantity: 0 units
Vegetables$2/unit
Quantity: 0 units

Nutritional Requirements

protein0/50
carbs0/200
fat0/20
vitamins0/30

Total Cost: $0.00

Infeasible Solution
Interactive Manufacturing Problem

Step 1: Understanding the Problem

Product Selection

Product A$100/unit
Quantity: 0 units
Product B$150/unit
Quantity: 0 units
Product C$200/unit
Quantity: 0 units

Resource Usage

labor0/40
materials0/60
energy0/50
time0/30

Total Revenue: $0.00

Feasible Solution
Interactive Transportation Problem

Step 1: Understanding the Problem

Shipping Routes

Factory A → Store X$5/unit
Quantity: 0 units
Factory A → Store Y$7/unit
Quantity: 0 units
Factory A → Store Z$6/unit
Quantity: 0 units
Factory B → Store X$4/unit
Quantity: 0 units
Factory B → Store Y$5/unit
Quantity: 0 units
Factory B → Store Z$8/unit
Quantity: 0 units
Factory C → Store X$6/unit
Quantity: 0 units
Factory C → Store Y$4/unit
Quantity: 0 units
Factory C → Store Z$5/unit
Quantity: 0 units

Supply Usage

Factory A0/100
Factory B0/150
Factory C0/200

Demand Satisfaction

Store X0/120
Store Y0/180
Store Z0/150

Total Cost: $0.00

Infeasible Solution
Maximal Flow Problem Interactive
Find the maximum flow from source (S) to sink (T) while respecting capacity constraints

How to Play

  1. Rearrange the network: Drag nodes to position them for better visualization.
  2. Select an edge: Click on any edge (line) to select it for flow adjustment.
  3. Adjust flow: Use the slider to set the flow value for the selected edge (cannot exceed capacity).
  4. Check solution: Click "Check Solution" to verify if flow conservation is maintained at intermediate nodes.
  5. Goal: Find a valid flow that maximizes the total flow from source (S) to sink (T).
  6. Reset: Click "Reset" to start over with zero flows.
Warehousing Problem Interactive
Optimize warehouse operations by buying and selling stock to maximize profit

How to Play

  1. Understand the problem: You manage a warehouse with capacity 100 units and holding cost $1 per unit per period.
  2. Make decisions: For each period, decide how much to buy and sell based on the price.
  3. Constraints: Stock cannot be negative or exceed capacity. Final stock must be zero.
  4. Goal: Maximize total profit across all periods.
  5. Progress: Use the "Next Period" button to move through time periods.
  6. Reset: Click "Reset" to start over.
Period: 1 of 3
Total Profit: $0.00
Period 1
Price: $10
Buy Amount0 units
Cost: $0
Sell Amount0 units
Revenue: $0
Current Stock
0 units
Period Profit
$0.00
PeriodPriceBuySellStockProfit
1$10000$0.00
2$15000$0.00
3$12000$0.00