0
$\begingroup$

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. enter image description here

enter image description here

$\endgroup$
  • $\begingroup$ Are you familiar with the "künstliche Variable". It is commonly use if the constraint is a $\geq$ or a $=$ constraint. $\endgroup$ – callculus May 7 '17 at 3:33
  • $\begingroup$ 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. $\endgroup$ – callculus May 7 '17 at 4:25
3
$\begingroup$

See picture below:

enter image description here

Hope this helps !

$\endgroup$
  • $\begingroup$ Thank you very much for your help! Maybe you can shortly explain your calculation steps? Because I don't understand why you calculated it like that. $\endgroup$ – cnmesr May 6 '17 at 20:56
  • $\begingroup$ @cnmesr I've tried to find a way to get only one coefficient for each row. This was obvious for the second row, but I must agree that I had to search a little bit for the other rows. $\endgroup$ – Curious May 7 '17 at 5:17
  • $\begingroup$ In class we have never talked about your way, but it seems very fast :) Is it still simplex algorithm though? Tyvm. $\endgroup$ – cnmesr May 8 '17 at 20:44
  • $\begingroup$ @cnmesr Have you read my comments ? $\endgroup$ – callculus May 9 '17 at 4:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.