Assignment 6 — Assignment & Transportation Formulation
Three flight-pairing assignment problems (one with a turnaround time, one unbalanced) and two transportation problems (one unbalanced, one profit-maximising) — each formulated, counted, and then solved to the optimum.
- Assignment problems: build the cost (idle-time) matrix — rows = outbound flights, columns = return flights, cell = hours the aircraft waits; roll to the next day when the return leaves before the aircraft is ready, and use 24 when the gap is exactly zero. Rows = columns ⟹ balanced; otherwise add a dummy row/column of zeros.
- Transportation problems: rows = sources with supply, columns = destinations with demand. Σ supply = Σ demand ⟹ balanced; otherwise add a dummy source (if demand is larger) or dummy destination (if supply is larger) with zero cost.
- LPP form: Xᵢⱼ = amount (or 1/0 for assignment) from i to j; Min Z = ΣΣ cᵢⱼXᵢⱼ (or Max for profit); one constraint per row and one per column; non-negativity (or Xᵢⱼ ∈ {0, 1}).
- Counts: variables = m × n; constraints = m + n (excluding non-negativity) — after balancing.
Formulation rules and examples: Unit 3 · Transportation & Assignment.
- Profit version: net profit per unit = selling price − (processing + procurement + transport). Build that matrix first, then Max Z.
- Variables multiply, constraints add. 4 × 5 = 20 variables, 4 + 5 = 9 constraints — the pair most often swapped under pressure.
- Turnaround time (Q2): idle cost = gap − 0.5 h; a gap of 0.5 h or less cannot be flown, so the aircraft takes the same flight next day (+24 h).
- Hungarian check: the minimum number of lines covering all zeros must equal n; if not, subtract the smallest uncovered number from all uncovered cells and add it at the intersections.
Assignment Q1 — Mumbai–Delhi flights (2 hours)
| Flight | Mumbai → Delhi | Flight | Delhi → Mumbai |
|---|---|---|---|
| 301 | 8 AM | 401 | 7 AM |
| 302 | 11 AM | 402 | 12 PM |
| 303 | 3 PM | 403 | 5 PM |
| 304 | 4 PM | 404 | 8 PM |
Pair the flights to minimise aircraft idle time. Formulate in assignment and LPP form; balanced? number of constraints and variables.
Assignment 6 p. 1
- Step 1 — When does each aircraft reach Delhi? 301 → 10:00, 302 → 13:00, 303 → 17:00, 304 → 18:00 (departure + 2 h)
- Step 2 — Idle-time matrix (hours waiting in Delhi)
Arrives ↓ / Returns → 401 (07:00) 402 (12:00) 403 (17:00) 404 (20:00) 301 (10:00) 21 2 7 10 302 (13:00) 18 23 4 7 303 (17:00) 14 19 24 3 304 (18:00) 13 18 23 2 Sample: 301 lands 10:00; 401 leaves 07:00 next day ⟹ 21 h. 303 lands 17:00 and 403 leaves 17:00 — a zero gap cannot be flown, so it waits a full day: 24.
- Step 3 — Balanced? Counts 4 outbound × 4 return ⟹ balanced (m = n = 4) Variables = 4 × 4 = 16; constraints = 4 + 4 = 8
- Step 4 — LPP form Let Xᵢⱼ = 1 if outbound flight i is paired with return flight j, else 0 (i = 301…304, j = 401…404) Min Z = ΣᵢΣⱼ tᵢⱼXᵢⱼ (tᵢⱼ from the matrix) Σⱼ Xᵢⱼ = 1 for each i — every aircraft gets one return Σᵢ Xᵢⱼ = 1 for each j — every return is flown once Xᵢⱼ ∈ {0, 1}
- Step 5 — Solve (Hungarian method)
Row-reduced (− 2, 4, 3, 2) 401 402 403 404 301 19 0 5 8 302 14 19 0 3 303 11 16 21 0 304 11 16 21 0 Column-reduced (− 11, 0, 0, 0) 401 402 403 404 301 8 0 5 8 302 3 19 0 3 303 0 16 21 0 304 0 16 21 0 Four lines (columns 401 and 404, rows 301 and 302) cover every zero — 4 = n, so the table is optimal.
- Step 6 — Answer 301 → 402 (2 h), 302 → 403 (4 h), and either 303 → 401 (14 h) + 304 → 404 (2 h) or 303 → 404 (3 h) + 304 → 401 (13 h) Minimum total idle time = 22 hours — two optimal pairings
Assignment Q2 — Delhi–Chennai with a 30-minute turnaround
| Flight | Delhi → Chennai | Flight | Chennai → Delhi |
|---|---|---|---|
| 701 | 7:00 AM | 801 | 9:30 AM |
| 702 | 11:30 AM | 802 | 12:30 PM |
| 703 | 3:00 PM | 803 | 6:00 PM |
| 704 | 6:30 PM | 804 | 9:30 PM |
Flight time 2.5 h; a turnaround of at least 30 minutes is needed before the return. Pair the flights to reduce idle time.
Assignment 6 p. 1 — the same question as Re-Exam Q5B
- Step 1 — Arrivals in Chennai 701 → 9:30, 702 → 14:00, 703 → 17:30, 704 → 21:00
- Step 2 — Idle time net of the 30-minute turnaround
Arrives ↓ / Returns → 801 (9:30) 802 (12:30) 803 (18:00) 804 (21:30) 701 (9:30) 23.5 2.5 8 11.5 702 (14:00) 19 22 3.5 7 703 (17:30) 15.5 18.5 24 3.5 704 (21:00) 12 15 20.5 24 Cost = gap − 0.5 h. Where the gap is 0.5 h or less (701→801, 703→803, 704→804) the aircraft cannot make it and flies the same service next day. This matches the Re-Exam key cell for cell Key p. 5.
- Step 3 — Balanced, LPP form, counts 4 × 4 ⟹ balanced; 16 variables, 8 constraints Min Z = ΣΣ tᵢⱼXᵢⱼ, Σⱼ Xᵢⱼ = 1 (each i), Σᵢ Xᵢⱼ = 1 (each j), Xᵢⱼ ∈ {0, 1}
- Step 4 — Optimal pairing (solved) 701 → 802 (2.5 h), 702 → 803 (3.5 h), 703 → 804 (3.5 h), 704 → 801 (12 h) — total 21.5 hours beyond turnaround
Assignment Q3 — Hyderabad–Kolkata with an extra flight (unbalanced)
| Flight | Hyderabad → Kolkata | Flight | Kolkata → Hyderabad |
|---|---|---|---|
| 901 | 8:00 AM | 1001 | 10:30 AM |
| 902 | 1:00 PM | 1002 | 2:30 PM |
| 903 | 5:30 PM | 1003 | 7:45 PM |
| 904 | 9:00 PM | 1004 | 11:15 PM |
| 905 | 11:30 PM | — | — |
Flight time 2 h 15 min. Hyderabad has one extra late-night flight (905) with no return. Suggest how to balance the network and minimise overnight idle time.
Assignment 6 p. 1 — the same question as Final Q5B
- Step 1 — Idle-time matrix (hours in Kolkata)
Arrives ↓ / Returns → 1001 (10:30) 1002 (14:30) 1003 (19:45) 1004 (23:15) 901 (10:15) 0.25 4.25 9.5 13 902 (15:15) 19.25 23.25 4.5 8 903 (19:45) 14.75 18.75 24 3.5 904 (23:15) 11.25 15.25 20.5 24 905 (01:45) 8.75 12.75 18 21.5 - Step 2 — Balance it 5 outbound × 4 return ⟹ UNBALANCED Add a dummy return flight (column of zeros) ⟹ 5 × 5 Variables = 25; constraints = 5 + 5 = 10
- Step 3 — LPP form Xᵢⱼ = 1 if outbound i pairs with return j (j includes the dummy), else 0 Min Z = ΣΣ tᵢⱼXᵢⱼ; Σⱼ Xᵢⱼ = 1 (5 rows); Σᵢ Xᵢⱼ = 1 (5 columns); Xᵢⱼ ∈ {0, 1}
- Step 4 — Solve and interpret
901 → 1001 (0.25 h), 902 → 1003 (4.5 h), 903 → 1004 (3.5 h), 904 → Dummy, 905 → 1002 (12.75 h) — minimum idle 21 h
The dummy picks up flight 904: that aircraft has no paired return. To balance the network the airline should add one Kolkata → Hyderabad service timed for it — the aircraft reaches Kolkata at 23:15, so an early-morning return keeps its overnight idle time short. (The Final Q5B key prints a few cells of this matrix wrongly — rows 902, 903 and 904; the values above are checked against the timetable.)
Transportation Q1 — Four sources, five markets — unbalanced
| A | B | C | D | E | Supply | |
|---|---|---|---|---|---|---|
| 1 | 6 | 4 | 6 | 4 | 8 | 100 |
| 2 | 6 | 6 | 4 | 10 | 8 | 200 |
| 3 | 11 | 10 | 7 | 14 | 7 | 120 |
| 4 | 15 | 12 | 6 | 14 | 9 | 80 |
| Demand | 80 | 120 | 150 | 70 | 90 |
Formulate in transportation format and LPP form; balanced? number of constraints and variables.
Assignment 6 p. 1
- Step 1 — Balanced? Σ supply = 100 + 200 + 120 + 80 = 500 Σ demand = 80 + 120 + 150 + 70 + 90 = 510 Demand exceeds supply by 10 ⟹ UNBALANCED — add a dummy source 5 with supply 10 and zero costs
- Step 2 — Transportation format (balanced)
A B C D E Supply 1 6 4 6 4 8 100 2 6 6 4 10 8 200 3 11 10 7 14 7 120 4 15 12 6 14 9 80 Dummy 0 0 0 0 0 10 Demand 80 120 150 70 90 510 - Step 3 — LPP form Let Xᵢⱼ = units shipped from source i (1–4, dummy 5) to market j (A–E) Min Z = 6X₁A + 4X₁B + 6X₁C + 4X₁D + 8X₁E + 6X₂A + … + 9X₄E (dummy terms cost 0) Supply: X₁A + X₁B + X₁C + X₁D + X₁E = 100, …, X₅A + … + X₅E = 10 Demand: X₁A + X₂A + X₃A + X₄A + X₅A = 80, …, X₁E + … + X₅E = 90 Xᵢⱼ ≥ 0
- Step 4 — Counts Original 4 × 5: 20 variables, 9 constraints After balancing 5 × 5: 25 variables, 10 constraints
- Going further — the optimal plan
Minimum cost = ₹2840
1→B 30; 1→D 70; 2→A 70; 2→B 90; 2→C 40; 3→C 30; 3→E 90; 4→C 80; Dummy→A 10
The dummy's 10 units go to market A, i.e. market A is the one left 10 units short.
Transportation Q2 — Dairy — maximise profit
| Plant 1 | Plant 2 | Plant 3 | |
|---|---|---|---|
| Processing cost (₹/L) | 6 | 5 | 4 |
| Procurement cost (₹/L) | 8 | 7 | 6 |
| Capacity (L/day) | 100 | 150 | 200 |
| Market | Transport P1, P2, P3 | Selling price | Demand |
|---|---|---|---|
| A | 4, 5, 6 | 25 | 120 |
| B | 6, 8, 5 | 28 | 150 |
| C | 5, 7, 6 | 24 | 100 |
| D | 7, 6, 8 | 30 | 80 |
Formulate in transportation format and LPP form; balanced? constraints and variables.
Assignment 6 p. 2 — the same data as Final Q7B
- Step 1 — Total cost per litre at each plant P1 = 6 + 8 = ₹14, P2 = 5 + 7 = ₹12, P3 = 4 + 6 = ₹10
- Step 2 — Net profit per litre = price − plant cost − transport
Plant ↓ / Market → A (₹25) B (₹28) C (₹24) D (₹30) Capacity P1 25−14−4 = 7 28−14−6 = 8 24−14−5 = 5 30−14−7 = 9 100 P2 25−12−5 = 8 28−12−8 = 8 24−12−7 = 5 30−12−6 = 12 150 P3 25−10−6 = 9 28−10−5 = 13 24−10−6 = 8 30−10−8 = 12 200 Demand 120 150 100 80 450 ✓ This is exactly the matrix in the Final Q7B key Key p. 7.
- Step 3 — Balanced? Counts Σ capacity = 450 = Σ demand ⟹ balanced Variables = 3 × 4 = 12; constraints = 3 + 4 = 7
- Step 4 — LPP form Xᵢⱼ = litres from plant i to market j Max Z = 7X₁A + 8X₁B + 5X₁C + 9X₁D + 8X₂A + 8X₂B + 5X₂C + 12X₂D + 9X₃A + 13X₃B + 8X₃C + 12X₃D X₁A + X₁B + X₁C + X₁D = 100; X₂A + … = 150; X₃A + … = 200 X₁A + X₂A + X₃A = 120; … B = 150; … C = 100; … D = 80 Xᵢⱼ ≥ 0
- Going further — the optimal plan Maximum profit = ₹4470 per day P1→A 50; P1→C 50; P2→A 70; P2→D 80; P3→B 150; P3→C 50