Math340/Solution 1

Question 1

a. Decision variables: $x_{1}$= number of yam rolls, $x_{2}$= number of avocado rolls, $x_{3}$= number of salmon rolls (Note: defining the variables is very important when writing down an answer).

Objective: minimize the total cost $z=4*x_{1}+3*x_{2}+5.5*x_{3}$.

Constraints: $x_{3}\geq x_{1},x_{1}+x_{2}\geq 4.$

b. We can guess, for example: $x_{1}=2,x_{2}=2,x_{3}=2$. For this to be feasible we need it to satisfy the two inequalities, which it does: $2\geq 2$, and $2+2\geq 4$.

Question 2

For Alice plays pure, Alice chooses the row with the larger minimal value, which is the first row. The value of the game is then this minimal value- 1.

Betty plays pure- Betty chooses the column with the smallest maximal value, which is the first column. The value of the game is that value which equals 4.

Question 3

a. Duality gap= Betty plays pure -Alice plays pure= 4-1=3.

b. We find Alice's optimal strategy by:

$(x_{1},x_{2}){\begin{pmatrix}1&5\\4&-2\end{pmatrix}}={\begin{pmatrix}x_{1}+4x_{2},&5x_{1}-2x_{2}\end{pmatrix}}={\begin{pmatrix}v,&v\end{pmatrix}}$

Which yields $x_{1}={\frac {3}{5}},x_{2}={\frac {2}{5}}$.

c. The corresponding LP problem is:

${\begin{array}{ll}maximize&w\\subject\ to&w\leq x_{1}+4x_{2},\\&w\leq 5x_{1}-2x_{2},\\&x_{1}+x_{2}=1,\ {\text{(note this can be replaced by}}\ x_{1}+x_{2}\leq 1)\\&x_{1},x_{2}\geq 0.\end{array}}$

Question 4 (Friday, May 15)

The slack variables:

${\begin{array}{l}x_{3}=5-x_{1}-x_{2},\\x_{4}=8-x_{1}-2x_{2},\\x_{5}=8-2x_{1}-x_{2}.\\\end{array}}$

And the first dictionary:

${\begin{array}{cccrr}x_{3}&=&5&-x_{1}&-x_{2}\\x_{4}&=&8&-x_{1}&-2x_{2}\\x_{5}&=&8&-2x_{1}&-x_{2}\\z&=&&4x_{1}&+5x_{2}\end{array}}$