Question 7 of 8: LP Formulation — Airline Fuel-Purchasing (Tankering)
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — May 2017 — 98-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 160 marks across 8 questions (each worth 20) and only 100 marks are required, so a candidate would normally answer 5 — all eight are solved below for completeness.
Given. 4-leg cycle V→C→T→N→V with distances 687/2690/571/3910 km; per-litre prices 0.88/0.15/0.95/1.05 (V/C/T/N); purchase cap 10,000 l/stop; tank capacity 12,000 l; minimum reserve 600 l on landing; burn rate $1+\text{avg}/2000$ l/km.
Find. An LP (decision variables, linear constraints, objective) that determines how much fuel to buy at each city to minimize total fuel cost for one circuit.
The 4-leg route V→C→T→N→V with each leg's distance.
Approach. Track fuel level at departure and arrival of each city; write the fuel-burn rule as a linear equality relating the departure and arrival levels of each leg (it is linear because the "average" is itself linear in the two endpoints), then minimize total purchase cost subject to the safety-reserve and tank-capacity bounds.
Decision and state variables. For each city $X\in\{V,C,T,N\}$: $f_X\ge0$ = fuel purchased at $X$ ($\le10{,}000$); $d_X\ge0$ = fuel level at departure from $X$ ($\le12{,}000$); $a_X\ge0$ = fuel level at arrival into $X$ ($\ge600$, except the very first arrival into Vancouver, which starts the schedule with an empty tank).
Linearized burn-rate equality for a leg of distance $\ell$ from city $X$ to city $Y$. Fuel used $=d_X-a_Y$ by conservation, and by the given rule fuel used $=\ell\big(1+\tfrac{d_X+a_Y}{4000}\big)$; setting these equal gives a linear equality in $d_X,a_Y$ (all other terms are constants):
$$d_X-a_Y=\ell+\frac{\ell}{4000}(d_X+a_Y)\qquad\Longrightarrow\qquad d_X\Big(1-\tfrac{\ell}{4000}\Big)-a_Y\Big(1+\tfrac{\ell}{4000}\Big)=\ell$$
one such equality per leg (V→C, $\ell=687$; C→T, $\ell=2690$; T→N, $\ell=571$; N→V, $\ell=3910$).
Departure/purchase linking at every city except the schedule's first departure (Vancouver, tank empty before purchase, so $d_V=f_V$):
$$d_X=a_X+f_X,\qquad X\in\{C,T,N\}$$
Objective and bounds:
$$\boxed{\min Z=0.88f_V+0.15f_C+0.95f_T+1.05f_N}$$
subject to Steps 2–3, $0\le f_X\le10{,}000$, $d_X\le12{,}000$, and $a_Y\ge600$ for every arrival $Y$.
Check: solving the formulated model exposes a genuine data inconsistency worth flagging rather than papering over. At a full 12,000 l departure and the 600 l minimum reserve, the burn-rate equality above gives a maximum single-leg range of only $\ell_{\max}=(12000-600)/(1+(12000+600)/4000)\approx2{,}747$ km — the Vancouver–Calgary (687 km), Calgary–Toronto (2,690 km) and Toronto–New York (571 km) legs all fit comfortably within this, but the New York–Vancouver leg (3,910 km) cannot be flown nonstop under the stated 12,000 l tank capacity and burn-rate formula, regardless of how the LP's fuel purchases are chosen (the formulated equality has no feasible $a_V\ge600$ for that leg). The formulation above is nonetheless complete and correct as requested; the infeasibility is a property of the exam's stated tank capacity for that specific leg, not of the modeling technique, and is the kind of numeric inconsistency the project treats as a flagged data artifact rather than something to force into a false "solved" answer.
Final results — Question 7
Item
Value
Decision variables
$f_X,d_X,a_X\ge0$ for $X\in\{V,C,T,N\}$ (12 total)
