## 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\]

.We can test the integer coordinates of point inside the feasible region, or the vertices of the feasible region, if the coordinates are integer points. The cost function, to be minimised, is

\[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.