Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2001/ib/paper-4/14d/solution

Measure quantities in thousands of copies. Use five supply rows: initial inventory, regular production in month 1, overtime in month 1, regular production in month 2, overtime in month 2. Their supplies/capacities are . The three demand columns are the two due dates and a dummy column for unused capacity, with demands , balancing the total supply .
The transportation problem has cost matrix
An infinite entry prohibits delivering a later month's production to an earlier deadline. The extra in the second column of the early rows accounts for holding stock through the first month. For production rows, the dummy column represents capacity not used, not copies actually printed. Initial inventory assigned to the dummy column would instead remain in stock through both months, costing ; this distinguishes physical inventory from optional production capacity. No gratuitous disposal is needed in the optimum.
Let have the stated row and column sums, with the forbidden entries zero, and minimize . A feasible solution is
Thus regular production is in each month; overtime is zero then ; first-month closing inventory is , and final inventory is zero. Its total production-plus-holding cost is
To prove optimality, use transportation dual potentials for rows and for columns. Every allowed edge satisfies . Multiplying by any feasible shipment and summing gives the lower bound
The proposed shipment attains it, so the schedule is optimal. The dual calculation certifies the minimum without depending on an unshown transportation-simplex iteration.

New to topics? Read the docs here!