Question

Consider the following product mix problem:

Three machine shops A, B, C produces three types of products X, Y, Z respectively. Each product involves operation of each of the machine shops. The time required for each operation on various products is given as follows:

Machine shops

Products                    A      B       C               Profit per unit X                                10      7        2                Birr 12 Y                                  2      3        4                Birr 3 Z                                  1      2        1                Birr 1 Available Hours       100   77       80 Make the Mathematical model of the above primal problem to maximise the profit and then make the dual problem

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