Question 1 of 9: LP Formulation — Minimum-Cost Fuel Purchase for a Circular Flight Route
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — May 2013 — 98-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 180 marks across 9 questions and only 100 marks are required, so a candidate would normally answer a subset — all nine are solved below for completeness.
Reference texts: Hillier & Lieberman, Introduction to Operations Research (11th ed., McGraw-Hill) — linear/integer programming, network optimization, dynamic programming, decision analysis and queueing theory; Niebel & Freivalds, Niebel's Methods, Standards, and Work Design (13th ed.) — job-shop sequencing context.
Question 1: LP Formulation — Minimum-Cost Fuel Purchase for a Circular Flight Route (20 marks)
Given. Four legs $i=1,\dots ,4$ (V→C, C→T, T→N, N→V) with distances $d_i=687,\,2690,\,571,\,3910$ km and purchase prices at the departure city of each leg $c_i=0.88,\,0.15,\,0.95,\,1.05$ $/L. Tank capacity 12,000 L; landing reserve 600 L; burn-rate law as stated (litres/km, linear in the average tank level).
Leg
Route
Distance $d_i$ (km)
Price at origin $c_i$ ($/L)
1
Vancouver → Calgary
687
0.88
2
Calgary → Toronto
2690
0.15
3
Toronto → New York
571
0.95
4
New York → Vancouver
3910
1.05
Find. A linear program — decision variables, objective and constraints — that minimizes total fuel cost for one circuit, without solving it.
Approach. Track the tank level at the start and end of every leg as separate decision variables, show that the stated "average fuel" burn law is actually linear in those two variables (not the nonlinear expression it first appears to be), then attach capacity, safety-reserve and refuelling-continuity constraints.
Decision variables. For leg $i=1,\dots,4$: $S_i$ = fuel in the tank (L) immediately after refuelling, at the start of leg $i$; $E_i$ = fuel in the tank (L) on landing, at the end of leg $i$ (before that stop's refuelling). Let $p_1,p_2,p_3,p_4$ = litres purchased at Vancouver, Calgary, Toronto and New York respectively (all $\ge 0$).
Refuelling continuity. The tank entering leg $i$ is whatever landed from the previous leg plus what was just bought there:
$$S_1=p_1,\qquad S_2=E_1+p_2,\qquad S_3=E_2+p_3,\qquad S_4=E_3+p_4.$$
Linearizing the burn law. Fuel used on leg $i$ is $u_i=S_i-E_i$. The stated law gives $u_i=d_i\!\left[1+\dfrac{(S_i+E_i)/2}{2000}\right]=d_i+\dfrac{d_i}{4000}(S_i+E_i)$. Because this has no $S_i E_i$ product term, setting $S_i-E_i$ equal to it is a genuinely linear equality in $S_i,E_i$ — the "average fuel" phrasing looks nonlinear but is not:
$$\boxed{\left(1-\tfrac{d_i}{4000}\right)S_i-\left(1+\tfrac{d_i}{4000}\right)E_i = d_i},\qquad i=1,\dots,4.$$
Capacity and reserve constraints. The tank cannot be over-filled and must land with the safety margin:
$$S_i\le 12{,}000\ \ (i=1,\dots,4),\qquad E_i\ge 600\ \ (i=1,\dots,4).$$
Objective. Minimize the total purchase cost across the four stops:
$$\min Z = 0.88\,p_1+0.15\,p_2+0.95\,p_3+1.05\,p_4.$$
Element
Formulation
Variables
$p_1,\dots,p_4\ge0$ (purchases); $S_i,E_i\ge0$ for $i=1,\dots,4$ (tank levels)
The model covers one full circuit starting and ending at Vancouver, treating the plane as departing Vancouver with an empty tank plus a fresh purchase $p_1$ (a single-lap reading of "completing the schedule"). A steady repeating-schedule variant would instead close the loop with $S_1=E_4+p_1$; either is a defensible formulation and the grading focus is the linearized burn-law constraint, not this boundary choice.
