1
$\begingroup$

Could someone explain to me how using the smallest subscript rule causes a cycling LP to terminate?

At the moment it looks to me that a program would use it to determine whether the matrix from the current iteration is the same as the original matrix as the smallest subscript rule allows the matrix to return to its original self. Or is it something else?

I don't see how the smallest subscript rule actually causes the method to terminate and stop cycling unless something like the above was implemented.

Degenerate LP Example:

z   x1    x2   x3   x4   s1   s2   s3 | RHS | Basic Variables| Ratio | 
--------------------------------------|-----|----------------|-------|
1  -10    57    9   24    0    0    0 |  0  |        z       |       |
0  1/2 -11/2 -5/2    9    1    0    0 |  0  |       s1       |       |
0  1/2  -3/2 -1/2    1    0    1    0 |  0  |       s2       |       |
0    1     0    0    0    0    0    1 |  1  |       s3       |       |
----------------------------------------------------------------------

If someone could use this to demonstrate how the rule works I would be very grateful

$\endgroup$
0
$\begingroup$

It was introduced in 1977 by Bland - just have a look at original paper, the proof is not that long

$\endgroup$
  • $\begingroup$ Thanks for the answer Ryan. Could you perhaps go through an example of this rule being applied on the following degenerate LP (added to question) $\endgroup$ – Harry Apr 30 '14 at 9:21

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.