1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you know the SIMPLEX algorithm? Or if it weren't a course assignment, you could just enter it into an online LP optimizer. $\endgroup$ – Mark L. Stone Oct 5 '19 at 13:55
1
$\begingroup$

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. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.