Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — December 2013 — 98-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 200 marks across 10 questions and only 100 marks are required, so a candidate would normally answer a subset — all ten 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; Nahmias, Production and Operations Analysis — inventory models with planned backorders.
Given. Four "Leave" (Toronto→New York) flights on days 2, 10, 16, 25 and four "Return" (New York→Toronto) flights on days 6, 12, 20, 26 (December, Sunday=day 1). Discount tiers (best applicable, not combinable): 35% if the ticket's date span $\ge21$ days; else 30% if $\ge10$ days; else 20% if the span includes a Saturday or Sunday; else full $500 fare. Any Leave flight may be paired with any Return flight to form one return ticket, regardless of which city is "shown as the starting point."
Find. A minimum-cost network flow model — nodes, arcs, arc costs, supplies/demands — whose optimal flow assigns each of the 4 Leave flights to exactly one Return flight (4 tickets covering all 8 flights). Do not solve (i.e. do not select the actual 4 pairs).
Approach. Recognize that every valid ticket pairs one Toronto-origin flight with one New-York-origin flight, so this is a transportation-type min-cost flow: a source supplying 1 unit to each Leave-flight node, a sink drawing 1 unit from each Return-flight node, and an arc (with a discount-rule cost) between every Leave/Return pair.
Bipartite min-cost flow network: every Leave flight (source side) can pair with every Return flight (sink side) through an arc costed by the discount rule.
Nodes. A source node $s$; one node for each Leave flight $L\in\{2,10,16,25\}$; one node for each Return flight $R\in\{6,12,20,26\}$; a sink node $t$.
Arcs and capacities. $s\to L$ for each Leave node (capacity 1, cost 0); $L\to R$ for every Leave/Return pair (capacity 1, cost $c_{LR}$, defined next); $R\to t$ for each Return node (capacity 1, cost 0). Supply at $s$ = demand at $t$ = 4.
Arc-cost function. For a ticket pairing dates $L,R$ with span $g=|R-L|$ days, and "spans a weekend" true if the interval $[\min(L,R),\max(L,R)]$ contains a Saturday or Sunday:
$$c_{LR}=500\times\begin{cases}0.65,&g\ge21\\0.70,&10\le g<21\\0.80,&g<10\text{ and spans a weekend}\\1.00,&\text{otherwise}\end{cases}$$
Resulting cost matrix (computed directly from the given dates — this is model data, not a solved assignment):
Leave \ Return
6
12
20
26
2
$500 (g4)
$350 (g10, wk)
$350 (g18, wk)
$325 (g24)
10
$400 (g4, wk)
$500 (g2)
$350 (g10, wk)
$350 (g16, wk)
16
$350 (g10, wk)
$400 (g4, wk)
$500 (g4)
$350 (g10, wk)
25
$350 (g19, wk)
$350 (g13, wk)
$400 (g5, wk)
$500 (g1)
Model (flow-balance form). Let $x_{LR}\in\{0,1\}$ = 1 if the ticket pairing $L$ with $R$ is bought:
$$\boxed{\min\sum_{L}\sum_{R}c_{LR}\,x_{LR}\quad\text{s.t.}\quad\sum_{R}x_{LR}=1\ \forall L,\quad \sum_{L}x_{LR}=1\ \forall R,\quad x_{LR}\ge0}$$
(the unimodular transportation-polytope structure guarantees an integer optimum even with $x_{LR}\ge0$ relaxed, so no explicit integrality constraint is needed).
