A prototypical IP: knapsack problem

You want to pack any number each of three items in your knapsack so as to maximize their

value without exceeding a $10$ kilogram limit$.$ Note that the decisions here are of the "how

many" type: how many food packs, how many bottles of water, how many tents. Since we

have three decisions to be made, we need as many integer variables: x$1,$x$2,$x$3.$

Solution:

The knapsack problem can be formulated as the following IP$.$

max $7$x$1+8$x$2+11$x$3$

$3$x$1+4$x$2+6$x$3<=10$

x$1,$x$2,$x$3>=0$

x$1,$x$2,$x$3$ integer.

item weight value

food pack $37$

large bottle of water $48$

tent $611$

Table $1\mathrm{.}1$: Table for Problem $1$

$1$

Factory $($million $$)$

Location Profit Capital

LA $96$

SF $53$

Table $2\mathrm{.}1$: Table for Problem $2$

Warehouse $($million $$)$

Location Profit Capital

LA $65$

SF $42$

Table $2\mathrm{.}2$: Table for Problem $2$