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}=\left\{{\begin{array}{ll}1&{\text{Truck i is assigned to route j}},\\0&{\text{otherwise}}.\end{array}}\right.$

The objective:

$minimizez=\sum _{i,j}c_{i,j}x_{ij}$.

The constraints:

$\sum _{j}x_{ij}\leq 1{\text{ for }}i=1,2,$

$\sum _{i}x_{ij}\leq 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}\\subject\ to&2x_{1}+3x_{2}+x_{3}\leq 6,\\&4x_{1}+x_{2}+2x_{3}\leq 11,\\&3x_{1}+4x_{2}+2x_{3}\leq 8\\&x_{1},x_{2},x_{3}\geq 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}\\subject\ to&2x_{1}+3x_{2}+x_{3}\leq 6,\\&4x_{1}+x_{2}+2x_{3}\leq 11,\\&3x_{1}+4x_{2}+2x_{3}\leq 8\\&x_{1},x_{2},x_{3}\geq 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}\\subject\ to&2x_{1}+3x_{2}+x_{3}\leq 6,\\&4x_{1}+x_{2}+2x_{3}\leq 11,\\&3x_{1}+4x_{2}+2x_{3}\leq 8\\&x_{1},x_{2},x_{3}\geq 0,\\&x_{1}\leq 2.\end{array}}$

And problem 3: ${\begin{array}{ll}maximize&5x_{1}+4x_{2}+3x_{3}\\subject\ to&2x_{1}+3x_{2}+x_{3}\leq 6,\\&4x_{1}+x_{2}+2x_{3}\leq 11,\\&3x_{1}+4x_{2}+2x_{3}\leq 8\\&x_{1},x_{2},x_{3}\geq 0,\\&x_{1}\geq 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)$.