In: Advanced Math
A shipping company ShipCo supplies four destinations (D1,D2,D3,D4) from four sources (S1,S2,S3,S4). The shipping cost (in dollars) per shipment from each source to each destination is given below.
D1 | D2 | D3 | D4 | |
S1 | 7 | 8 | 5 | 2 |
S2 | 2 | 9 | 1 | 4 |
S3 | 4 | 5 | 3 | 1 |
S4 | 2 | 1 | 4 | 3 |
The four sources make 10, 20, 20, and 10 shipments per month,
respectively. The four destinations need to receive 20, 10, 10, and
20 shipments per month, respectively. The manager of ShipCo now
wants to determine the best plan for how many shipments to send
from each source to each destination each month. The objective is
to minimize the total shipping cost. Answer the following
questions:
(a) Formulate this transportation problem as an LP. Clearly explain
your variables and constraints.
(b) Use the Northwest corner method to find an initial BFS.
(c) Starting from the initial BFS in part (b), apply the
transportation algorithm to solve this problem.