1

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)

user650437
  • 11
  • At the options you can choose if the Bland’s anti-cycling rule will be applied or not. This could be the problem. – callculus42 Nov 29 '16 at 19:26

1 Answers1

1

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.

Marcello Sammarra
  • 385