1
$\begingroup$

I am using pythons linprog to solve the following linear program. I am using a callback to have linprog display the tableau on each iteration below. I don't understand how the last tableau is calculated. I would think the pivot would be 1 (row [0],col [1]) but it seems like linprog selects -2(row[1],col[1]). I thought in a linear program the pivot had to be greater than 0? And actually linprog prints out (nan,nan) for pivot but it seems as though the -2 is used to reduce the problem.

x[1] + x[2] <= 10
-x[1] + x[2] <= -10
max f = x[1] + 2*x[2]

[[ 1. 1. 1. 0. 0. 10.] [ 1. -1. -0. -1. 1. 10.] [ -1. -2. 0. 0. 0. 0.] [ -1. 1. 0. 1. 0. -10.]] (0, 0) [[ 1. 1. 1. 0. 0. 10.] [ 0. -2. -1. -1. 1. 0.] [ 0. -1. 1. 0. 0. 10.] [ 0. 2. 1. 1. 0. 0.]] (nan, nan)

[[ 1. 0. 0.5 -0.5 10. ] [ -0. 1. 0.5 0.5 -0. ] [ 0. 0. 1.5 0.5 10. ]] (nan, nan)

$\endgroup$
  • $\begingroup$ At the options you can choose if the Bland’s anti-cycling rule will be applied or not. This could be the problem. $\endgroup$ – callculus Nov 29 '16 at 19:26
1
$\begingroup$

It is a degenerate pivot operation, that is quite usual when the first phase of the simplex algorithm is applied. As in your sample, when the first phase ends (second tableau) with an optimal solution equal to zero, but with one or more artificial variables still basic, the value of these variables is necessarily zero. To start the second phase the artificial variables must exit the basis. This can be done performing a pivot operation even if the pivot is negative because the feasibility and the optimality is preserved.

$\endgroup$

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.