Integer Programming
\[W_1, \: W_2\]
and three outlets \[O_1, \: O_2, \: O_3\]
. . Stock is to be sent from warehouse to outlet so that each outlet is fully stocked and each warehouse is fully utilised, with all stock being sent to some outlet. \[W_1, \: W_2\]
have capacities of 12 and 8 respectively and outlets \[O_1, \: O_2, \: O_3\]
require 8, 7 and 5 units respectively. The cost of transporting a unit from each warehouse to each outlet is summarised in the table below.| Outlet | |||||
| \[O_1\] | \[O_2\] | \[O_3\] | Capacity | ||
| \[W_1\] | 3 | 5 | 3 | 12 | |
| Needs | \[W_2\] | 2 | 7 | 1 | 8 |
| 8 | 7 | 5 |
\[W_1-O_1\]
take \[x\]
units, then the route \[W_2-O_1\]
must take at most \[8-x\]
units, hence \[0 \le (8-x) \le 8 \rightarrow 0 \le x \le 8\]
.We can let the route
\[W_1-O_2\]
take \[y\]
units, then the route \[W_2-O_2\]
must take at most \[7-y\]
units hence \[0 \le (7-y) \le 8 \rightarrow 0 \le y \le 7\]
.We can let the route
\[W_1-O_3\]
take \[z\]
units, then the route \[W_2-O_3\]
must take at most \[5-z\]
units hence \[0 \le (5-z) \le 5 \rightarrow 0 \le z \le 5\]
.By considering the warehouses, we have
\[x+y+z=12 \rightarrow z=12-x-y\]
and \[(8-x)+(7-y)+(5-z)=8 \rightarrow x+y+z=12\]
.We can eliminate a variable from these constraints. Suppose we choose to eliminate hence
\[z\]
, then from the last, and hence \[0 \le z \le 5\]
, we have hence \[x+y \ge 7\]
.Now we can sketch the constraints
\[x \le 8, \: y \le 7, 7 \le x+y \le 12\]
.
\[3x+5y+3(12-x-y)+2(8-x)+7(7-y)+1(x+y-7)=94-x-4y\]
.Test each vertex.
\[(0,7): \: 94-0-4 \times 7=66\]
\[(5,7): \: 94-5-4 \times 7=61\]
\[(8,4): \: 94-8-4 \times 4=70 \]
\[(8,9): \: 94-8-4 \times 0=86 \]
\[(7,0): \: 94-7-4 \times 0=87 \]
The minimum cost solution is
\[(5,7)\]
, corresponding to sending 5,7, 3 and 5 units on routes \[W_1-O_1, \: W_1-O_2, \: W_2-O_1\]
and \[W_2-O_3\]
respectively. 
