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\ge x_1,x_1+x_2\ge 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\ge 2$, and $2+2\ge 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)\left(\begin{array}{cc}1& 5\\ 4& -2\end{array}\right)=\left(\begin{array}{cc}{x}_1+4x_2,& 5x_1-2x_2\end{array}\right)=\left(\begin{array}{cc}v,& v\end{array}\right)$

Which yields $x_1=\frac{3}{5},x_2=\frac{2}{5}$.

c. The corresponding LP problem is:

$\begin{array}{ll}maximize& w\\ subjectto& w\le x_1+4x_2,\\ & w\le 5x_1-2x_2,\\ & x_1+x_2=1,\text{(note this can be replaced by}{x}_1+x_2\le 1)\\ & x_1,x_2\ge 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}$