Answer to Question #211473 in Operations Research for Ejisco

Question

Placid company makes 3 production components A, B, C using 3 machines Cutting, Polishing and Packaging whose allocated and available hours are not more than 96hrs, 40hrs and 60hrs respectively. Product A spends 6 hours on cutting machine, 2 hours on polishing and 5 hours on packaging machine. Product B goes through 8 hours of cutting, 1 hour of polishing and 3 hours of packaging. Product C takes 4 hours on cutting machine, 4 hours of polishing and 2 hours of packaging. Contribution margins for each component product are N2, N5 and N8.

Use the Simplex Algorithm to determine how many of each component the Placid Company will make to maximize contribution

Answer 1

$\text{Let }x_1 \text{ represents the number of A}$

$\text{Let }x_2 \text{ represents the number of B}$

$\text{Let }x_3 \text{ represents the number of C}$

The linear program is

$Maximize:z=2x_1+5x_2+8x_3\\Subject to:\\6x_1+8x_2+4x_3\le90\\2x_1+x_2+4x_3\le40\\5x_1+3x_2+2x_3\le60$

with all variables non-negative.

Next we compute the optimal solution, to do this we put the linear program in standard form:

$Maximize:z=2x_1+5x_2+8x_3+0x_4+0x_5+0x_6\\Subject to:\\6x_1+8x_2+4x_3+x_4\le96\\2x_1+x_2+4x_3+x_5\le40\\5x_1+3x_2+2x_3+x_6\le60$

with all variables non-negative.

Subsequently, we obtain our Tableau 1

$\begin{matrix} &x_1 & x_2 &x_3 &x_4&x_5&x_6\\ &2&5&8&0&0&0 \\ \hline x_4 (0) & 6 &8&4&1&0&0&96\\x_5 (0) & 2 &1&4&0&1&0&40\\x_6 (0) & 5 &3&2&0&0&1&60\\ & -5&-8&0&0&0&0&0 \end{matrix}$

Next we locate the most negative number in the bottom row(-8). Then we compute ratios of positive numbers in our work column. Therefore our pivot element is 4. Using row reduction method, we reduce our pivot element to 1 and every other elements in the work column to 0, thereby generating Tableau 2.

$\begin{matrix} &x_1 & x_2 &x_3 &x_4&x_5&x_6\\ &30&40&35&0&0&0 \\ \hline x_3 (8) & 4 &7&0&1&-1&0&56\\x_5 (0) & \frac{1}{2} &\frac{1}{4}&1&0&\frac{1}{4}&0&10\\x_6 (0) & 4 &\frac{5}{2}&0&0&\frac{-1}{2}&1&40\\& 2 &-3&0&0&2&0&80 \end{matrix}$

We notice there is still a negative element in the last row therefore repeating the process above we obtain Tableau 3.

$\begin{matrix} &x_1 & x_2 &x_3 &x_4&x_5&x_6\\ &30&40&35&0&0&0 \\ \hline x_3 (8) & \frac{4}{7} &1&0&\frac{1}{9}&\frac{-1}{7}&0&8\\x_2 (5) & \frac{5}{7} &0&1&\frac{-1}{28}&\frac{2}{7}&0&8\\x_6 (0) & \frac{18}{7} &0&0&\frac{-5}{18}&\frac{-6}{7}&1&20\\&\frac{26}{7} &0&0&\frac{3}{7}&\frac{11}{7}&0&104 \end{matrix}$

Since there are no negative values in our last row. The solution is optimal. The optimal solution is $x_1=0,x_2=5,x_3=8,x_4=0,x_5=0,x_6=0.$

Placid should produce 5 of product B and 8 of Product B