# Solving this linear programming takes forever… is there a more efficient way to solve it?

I'm supposed to solve the following LP:

$(P_2) \text{ } \text{max}\left\{ 33x_1+13x_2+18x_3 \mid \begin{matrix} 8x_1+3x_2+4x_3 \leq 32\\ 12x_1+5x_2+7x_3 \leq 51\\ 5x_1+2x_2+3x_3 \leq 21\\ x_1+x_2+x_3 \geq 3 \end{matrix} \right\}$

I have formed the inequations to equations:

$8x_1+3x_2+4x_3+y_1=32$

$12x_1+5x_2+7x_3+y_2=51$

$5x_1+2x_2+3x_3+y_3=21$

$-x_1-x_2-x_3+y_4=-3$

And the solution problem (on my paper "Zielfunktion") is $33x_1+13x_2+18x_3$

I'm supposed to solve it by using simplex algorithm. As you will see below, my solution is very long... I needed about 8 tables and our teacher said that it's solvable with maybe 3 tables. But how? :(

The yellow marks are the pivot elements.

• Are you familiar with the "künstliche Variable". It is commonly use if the constraint is a $\geq$ or a $=$ constraint. – callculus May 7 '17 at 3:33
• There is an easier method to calculate the values for the next table. See here math.stackexchange.com/questions/2182662/… Your method is too time-consuming. – callculus May 7 '17 at 4:25