Math340/Solution6

Question 1 (Tuesday June 16)

There are two different trucks $T_1,T_2$ and three routes $r_1,r_2,r_3$. $T_1$ can only be used for the first two routes, while $T_2$ can be used for all three, so we have the decision variables (corresponding to edges):

$x_{11},x_{12},x_{21},x_{22},x_{23}.$ These are all binary variables, that is:

$x_{ij}=\{\begin{array}{ll}1& \text{Truck i is assigned to route j},\\ 0& \text{otherwise}.\end{array}$

The objective:

$minimizez=\sum _{i,j}{c}_{i,j}{x}_{ij}$.

The constraints:

$\sum _j{x}_{ij}\le 1\text{ for }i=1,2,$

$\sum _i{x}_{ij}\le 1\text{ for}j=1,2,3.$

Question 2 (Wednesday, June 17)

Our problem here would be:

$\begin{array}{ll}maximize& 5x_1+4x_2+3x_3\\ subjectto& 2x_1+3x_2+x_3\le 6,\\ & 4x_1+x_2+2x_3\le 11,\\ & 3x_1+4x_2+2x_3\le 8\\ & x_1,x_2,x_3\ge 0,\\ & x_1,x_2,x_3\text{ integers}.\end{array}$

The LP relaxation is the same thing without the integer constraints:

$\begin{array}{ll}maximize& 5x_1+4x_2+3x_3\\ subjectto& 2x_1+3x_2+x_3\le 6,\\ & 4x_1+x_2+2x_3\le 11,\\ & 3x_1+4x_2+2x_3\le 8\\ & x_1,x_2,x_3\ge 0.\\ \end{array}$

And we computed in the previous homework that the solution to this is:

$z=13\frac{1}{3}\text{ and }{x}_1=2\frac{2}{3},x_2=0,x_3=0$.

This isn't integer, so we branch into problem 2: $\begin{array}{ll}maximize& 5x_1+4x_2+3x_3\\ subjectto& 2x_1+3x_2+x_3\le 6,\\ & 4x_1+x_2+2x_3\le 11,\\ & 3x_1+4x_2+2x_3\le 8\\ & x_1,x_2,x_3\ge 0,\\ & x_1\le 2.\end{array}$

And problem 3: $\begin{array}{ll}maximize& 5x_1+4x_2+3x_3\\ subjectto& 2x_1+3x_2+x_3\le 6,\\ & 4x_1+x_2+2x_3\le 11,\\ & 3x_1+4x_2+2x_3\le 8\\ & x_1,x_2,x_3\ge 0,\\ & x_1\ge 3.\end{array}$

These you can solve in your favourite method (I used a web solver) to get:

The solution for problem 2 is $z=13,x=(2,0,1)$, while problem 3 is infeasible. So, the optimal solution is the solution to problem 2, $x=(2,0,1)$.