Answer to Question #169270 in Operations Research for gFg

Question

10. A can of cat food, guaranteed by the manufacturer to contain at least 10 units of protein, 20 units of mineral matter, and 6 units of fat, consists of a mixture of four different ingredients. Ingredient A contains 10 units of protein, 2 units of mineral matter, and 1 2 unit of fat per 100g. Ingredient B contains 1 unit of protein, 40 units of mineral matter, and 3 units of fat per 100g. Ingredient C contains 1 unit of protein, 1 unit of mineral matter, and 6 units of fat per 100g. Ingredient D contains 5 units of protein, 10 units of mineral matter, and 3 units of fat per 100g. The cost of each ingredient is Birr 3, Birr 2, Birr 1, and Birr 4 per 100g, respectively. How many grams of each should be used to minimize the cost of the cat food, while still meeting the guaranteed composition? (Hint: Solve through simplex model)

Answer 1

$10A+B+C+5D≥10,$

$2A+40B+C+10D≥20,$

$12A+3B+6C+3D≥6,$

$F = 3A+2B+C+4D~\rightarrow min,$

$\begin{cases} -10A-B-C-5D+K=-10\\ -2A-40B-C-10D+L=-20\\ -12A-3B-6C-3D+M=-6 \end{cases}$ $\def \arraystretch{1.5} \begin{array}{c:c:c:c:c:c:c:c:c} C& 3 & 2&1&4&0&0&0&0 \\ \hline bas& A & B&C&D&K&L&M&b\\ \hline K & -10 & -1&-1&-5&1&0&0&-10\\ \hline L&-2&-40&-1&-10&0&1&0&-20\\ \hline M&-12&-3&-6&-3&0&0&1&-6\\\hline \end{array}$ $|b|_{max}=|-20|$

$\def \arraystretch{1.5} \begin{array}{c:c:c:c:c:c:c:c:c} C& 3 & 2&1&4&0&0&0&0 \\ \hline bas& A & B&C&D&K&L&M&b\\ \hline K & -\frac{199}{20}& 0&-\frac{39}{40}&-\frac{19}{4}&1&-\frac{1}{40}&0&-\frac{19}{2}\\ \hline B&\frac{1}{20}&1&\frac{1}{40}&\frac 14&0&-\frac{1}{40}&0&\frac 12\\ \hline M&-\frac{237}{20}&0&-\frac{237}{40}&-\frac 94&0&-\frac{3}{40}&1&-\frac 92\\\hline \end{array}$ $|b|_{max}=|-\frac{19}{2}|$

$\def \arraystretch{1.5} \begin{array}{c:c:c:c:c:c:c:c:c} C& 3 & 2&1&4&0&0&0&0 \\ \hline bas& A & B&C&D&K&L&M&b\\ \hline A & 1& 0&\frac{39}{398}&\frac{95}{199}&-\frac{20}{199}&\frac{1}{398}&0&\frac{190}{199}\\ \hline B&0&1&\frac{4}{199}&\frac {45}{199}&\frac{1}{199}&-\frac{5}{199}&0&\frac {90}{199}\\ \hline M&0&0&-\frac{948}{199}&\frac {678}{199}&-\frac{237}{199}&-\frac{9}{199}&1&\frac {1356}{199}\\\hline \end{array}$

$\def \arraystretch{1.5} \begin{array}{c:c:c:c:c:c:c:c:c} C& 3 & 2&1&4&0&0&0&0 \\ \hline bas& A & B&C&D&K&L&M&b\\ \hline A & 1& 0&\frac{39}{398}&\frac{95}{199}&-\frac{20}{199}&\frac{1}{398}&0&\frac{190}{199}\\ \hline B&0&1&\frac{4}{199}&\frac {45}{199}&\frac{1}{199}&-\frac{5}{199}&0&\frac {90}{199}\\ \hline M&0&0&-\frac{948}{199}&\frac {678}{199}&-\frac{237}{199}&-\frac{9}{199}&1&\frac {1356}{199}\\\hline \Delta&0&0&-\frac{265}{398}&-\frac {421}{199}&-\frac{58}{199}&-\frac{17}{398}&0&\frac {750}{199}\\\hline \end{array}$

$A=\frac{190}{199}, B =\frac{ 90}{199}, C = 0, D = 0,$

$F=3\cdot \frac{190}{199}+2\cdot \frac{90}{199}+1\cdot 0+4\cdot 0=3\frac{153}{199}\approx3.7688~\text{Birr}.$