0
$\begingroup$

Minimize -10𝑥1−12x2-12x3

Subject to :

x1+2x2+2x3+x4=20

2x1+x2+2x3+x5 =20

2x1+2x2+x3+x6 =20

xi >= 0

With x4,x5,x6 the slack variables which we take as our basic variable and all equal to 20 for our full tableau implementation.
As you can see in the Z-row, all coefficients -10 and -12 are negative.

According to a video on Youtube (Dr.Salimian's) you take the most negative, in this case being -12, but when I do that I encounter the following problem : the coefficients of at least one of the basic variable (or their R.H.S) are negative. I calculated the low-ratios and took the smallest for the entering variable.

My question is : do we always take the most negative? And if we have two variable with the most negative ratios do we just pick one randomly?

$\endgroup$
1
$\begingroup$

During the simplex algorithm you have eventually two kind of choices:

  1. Decide which basis variable should enter the base (multiple negative cost values)
  2. Decide which non-basis variable should leave the base (same ratios)

These choices lead to different pivoting strategies, i.e. take the biggest negative value or just the variable with smallest index (Blands rule) and so on.

In the YouTube Video he used one specific pivoting rule.

There is no universal pivoting strategy known, which outperforms the others.

$\endgroup$
  • $\begingroup$ but when I applied the same rule that he used in the video to this problem, it did not work. $\endgroup$ – Yasmine Guemouria Feb 17 at 22:27
  • $\begingroup$ In the first step you have two choices (with your rule from the video): $x_2$ or $x_3$ should enter the base (both have reduced cost $-12$. In the second step you have again two choices: the ratio of the first and third row is $\frac{20}{2}=10$. $\endgroup$ – sqlman Feb 17 at 22:49

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.