Question 9 of 9: LP Formulation — Multi-Modal Wheat Shipment to Rotterdam
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.
Given. 6000 tons across 5 silos; rail departs the morning of day 7; deadline = Rotterdam arrival by day 21 (3 weeks). Rail transit times (days) and each port's single sailing:
Port A
Port B
Port C
Port D
Silo 1
5
2
1
4
Silo 2
2
1
6
2
Silo 3
1
4
2
3
Silo 4
6
3
5
1
Silo 5
4
1
3
4
Ship departure day
10
8
11
9
Ship arrival day (Rotterdam)
19
17
21
17
Silo supplies $a_i$, rail costs $r_{ik}$/ton, ship capacities $Cap_k$, ship costs $s_k$/ton, early-delivery incentive $e$ $/ton/day and port storage cost $g_k$ $/ton/day are named parameters (not tabulated numerically in the exam text).
Find. An LP model (over the correct feasible silo–port routings only) that derives the tonnage to send from each silo via each port to minimize total net cost while meeting the 6000-ton Rotterdam order by day 21.
Figure 3 — Only the 9 silo→port arcs that meet each port's single sailing date survive the day-7-start / rail-time feasibility check; all others are infeasible and dropped from the LP.
Approach. First use the travel-time table to test which of the $5\times4=20$ silo–port pairs can actually make that port's one sailing (rail leaves day 7, must land at the port on or before the ship's departure day); build the LP only over the surviving feasible arcs, with cost terms for rail, shipping, storage while waiting for the ship, and an early-delivery credit.
Feasibility filter. Grain railed from silo $i$ to port $k$ arrives day $7+\tau_{ik}$ (with $\tau_{ik}$ from the table); it makes port $k$'s only sailing iff $7+\tau_{ik}\le\delta_k$ (ship departure day). Checking all 20 pairs:
$$\begin{aligned}
&\text{Silo 1: only }7{+}1{=}8\le11\ (\text{Port C}).\\
&\text{Silo 2: }7{+}2{=}9\le10\ (A);\ 7{+}1{=}8\le8\ (B);\ 7{+}2{=}9\le9\ (D).\\
&\text{Silo 3: }7{+}1{=}8\le10\ (A);\ 7{+}2{=}9\le11\ (C).\\
&\text{Silo 4: only }7{+}1{=}8\le9\ (\text{Port D}).\\
&\text{Silo 5: }7{+}1{=}8\le8\ (B);\ 7{+}3{=}10\le11\ (C).
\end{aligned}$$
Every other pairing misses its sailing and is infeasible. That leaves exactly the 9 feasible arcs $(i,k)\in\{(1,C),(2,A),(2,B),(2,D),(3,A),(3,C),(4,D),(5,B),(5,C)\}$ shown in Figure 3. All four ports' arrival days (19, 17, 21, 17) are $\le21$, so the 3-week deadline is automatically satisfied by any feasible routing.
Decision variables. $x_{ik}\ge0$ = tons shipped from silo $i$ via port $k$, defined only for the 9 feasible pairs from step 1.
Cost per ton on arc $(i,k)$. Rail $r_{ik}$ + ship $s_k$ + storage while the grain waits at the port for its sailing, $g_k\big(\delta_k-7-\tau_{ik}\big)$ days $\times g_k$ — minus an early-delivery credit for arriving ahead of the day-21 deadline, $e\big(21-\alpha_k\big)$, where $\alpha_k$ is port $k$'s Rotterdam arrival day:
$$\text{unit cost}_{ik}=r_{ik}+s_k+g_k\big(\delta_k-7-\tau_{ik}\big)-e\big(21-\alpha_k\big).$$
Constraints. Supply: $\sum_{k:(i,k)\text{ feasible}}x_{ik}\le a_i$ for each silo $i$. Ship capacity: $\sum_{i:(i,k)\text{ feasible}}x_{ik}\le Cap_k$ for each port $k$. Order fulfilment: $\sum_{(i,k)}x_{ik}=6000$.
Complete LP.
$$\boxed{\min Z=\sum_{(i,k)\,\text{feasible}} x_{ik}\Big[r_{ik}+s_k+g_k(\delta_k-7-\tau_{ik})-e(21-\alpha_k)\Big]}$$
subject to the supply, ship-capacity and 6000-ton demand constraints of step 4, with $x_{ik}\ge0$ defined only on the 9 feasible arcs.
Ties (Silo 2→Port B and Silo 2→Port D both land exactly on the ship's departure day) are treated as feasible, consistent with the paper's note that ships "depart late in the day, providing plenty of time to load" a same-day rail arrival.
