Simplex method – full tableau negative coefficients for basic variable

linear programmingoptimizationsimplex

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?

Best Answer

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.

Related Question