Answer to Question #210809 in Operations Research for Lemi Tesema

Question

A firm uses three machines in the manufacture of three products. Each unit of product A requires 3 hours on machine I, two hours on machine II, and one hour on machine III. While each unit of product B requires four hours on machine I, one hour on machine II, and three hours on machine III. While each unit of product C requires two hours on each of the three machines. The contribution margin of the three products is birr 30, birr 40 and birr 35 per unit respectively. The machine hours available on the three machines are 90, 54, and 93 respectively. a. Formulate the above problem as a linear programing model b. Obtain optimal solution to the problem by using the simplex method. Which of the three products shall not by produced by the firm? Why? c. Calculate the unused capacity if any.

Answer 1

The linear program is

$Maximize:z=30x_1+40x_2+35x_3\\Subject to:\\3x_1+4x_2+2x_3\le90\\2x_1+x_2+2x_3\le54\\x_1+3x_2+2x_3\le43$

with all variables non-negative.

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

$Maximize:z=30x_1+40x_2+35x_3+0x_4+0x_5+0x_6\\Subject to:\\3x_1+4x_2+2x_3+x_4\le90\\2x_1+x_2+2x_3+x_5\le54\\x_1+3x_2+2x_3+x_6\le43$

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\\ &30&40&35&0&0&0 \\ \hline x_4 (0) & 3 &4&2&1&0&0&90\\x_5 (0) & 2 &1&2&0&1&0&54\\x_6 (0) & 1 &3&2&0&0&1&43\\ & -30 &-40&-35&0&0&0&0 \end{matrix}$

Next we locate the most negative number in the bottom row(-40). 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_2 (40) & \frac{3}{4} &1&\frac{1}{2}&\frac{1}{4}&0&0&\frac{45}{2}\\x_5 (0) & \frac{5}{4} &0&\frac{3}{2}&\frac{-1}{4}&1&0&\frac{63}{2}\\x_6 (0) & \frac{-5}{4} &0&\frac{1}{2}&\frac{-3}{4}&0&1&\frac{51}{2}\\& 0 &0&-15&10&0&0&900 \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_2 (40) & \frac{1}{3} &1&0&\frac{1}{3}&\frac{-1}{3}&0&12\\x_3 (35) & \frac{5}{6} &0&1&\frac{-1}{6}&\frac{2}{3}&0&21\\x_6 (0) & \frac{-5}{3} &0&0&\frac{-2}{3}&\frac{2}{3}&1&15\\&\frac{75}{6} &0&0&\frac{25}{4}&10&0&1215 \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=40,x_3=35,x_4=0,x_5=0,x_6=0.$

The product A shouldn't be produced the value of its decision variable is 0