A health food store packages a nut sampler consisting of walnuts, pecans, and almonds. Suppose that each ounce of walnuts contains $\color{red}{\text{$12$ units of protein}}$ and $\color{blue}{\text{$3$ units of iron}}$ and costs $\color{orange}{\text{$12$ cents}}$, that each ounce of pecans contains $\color{red}{\text{$1$ unit of protein}}$ and $\color{blue}{\text{$3$ units of iron}}$ and costs $\color{orange}{\text{$9$ cents}}$, and that each ounce of almonds contains $\color{red}{\text{$2$ units of protein}}$ and $\color{blue}{\text{$1$ unit of iron}}$ and costs $\color{orange}{\text{$6$ cents}}$. If each package of the nut sampleris to contain at least $\color{red}{\text{$24$ units of protein}}$ and at least $\color{blue}{\text{$18$ units of iron}}$, how many ounces of each type of nut should be used to minimize the cost of the sampler$?$
Hint: you will need to intriduce two slack/surplus variables $s$ and $t$
So it want to minimize the cost of the sampler
Let $x_1$ be ounce of walnuts, $x_2$ be ounce of pecans, $x_3$ be ounce of almonds.
Minimize $$z=12x_1+9x_2+6x_3$$
subject to $$12x_1+1x_2+2x_3\ge24$$ $$3x_1+3x_2+1x_3\ge18$$ $$x_1,x_2,x_3\ge0$$
My attempts
Minimize $$z=12x_1+9x_2+6x_3$$
subject to $$-12x_1-1x_2-2x_3+s=-24$$ $$-3x_1-3x_2-1x_3+t=-18$$ $$x_1,x_2,x_3,s,t\ge0$$
Now this is in canonical form, how do I solve this, maybe use matrix$?$
Thanks for your help.
Best Answer
We can use simplex. Start with $(x_1,x_2)$ as a basis, then solve $Bx=b$ where $B$ is the matrix formed by the colums of $x_1$ and $x_2$ and $b$ the RHS of the constraints: \begin{align} -12x_1 -x_2 &=-24\\ -3x_1 -3x_2 &= -18 \end{align} which yields $x_1=\frac{18}{11}$, $x_2=\frac{48}{11}$. Compute the reduced costs $r_n^T= c_N^T - c_B^TB^{-1}A_N$ where the subscript $N$ denotes the elements of $c$ and columns of $A$ that are non-basic: \begin{align} \begin{bmatrix} r_3&r_s&r_t\end{bmatrix} &= \begin{bmatrix}6&0&0\end{bmatrix} - \begin{bmatrix}12&9\end{bmatrix}\begin{bmatrix}-12&-1\\-3&-3\end{bmatrix}\begin{bmatrix}-2&1&0\\-1&0&1\end{bmatrix}\\ &= \begin{bmatrix}-351&171&15\end{bmatrix}. \end{align} Because we are minimizing, we choose the first non-basic variable with a negative reduced cost to enter the basis - $x_3$. We now choose the exiting variable $x_r$ by the ratio test \begin{align} \frac{b_r}{a_{rs}} = \min_i \left\{\frac{b_i}{a_{is}}\mid a_{is}>0 \right\} = \min\left\{ \frac{18/11}{-2},\frac{48/11}{-1}\mid a_{is}>0\right\}. \end{align} Since there are no non-basic variables with a positive ratio, there is no candidate for an entering variable, and therefore our solution is optimal, with objective value $$ c_B^Tx_B = \begin{bmatrix}12&9\end{bmatrix}\begin{bmatrix}\frac{18}{11}\\\frac{48}{11} \end{bmatrix}= \frac{648}{11} \approx 58.90909. $$