# Write LPP in canonical form

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

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