Lexicographic simplex method

We have some linear programming problem with an objective function vrestrictions a with vector b.

$\begin{equation*} 300x_5+80x_6-1219x_7-x_8 \rightarrow max \\ x_2-8x_5-2x_6+30x_7+\frac{1}{2}x_8 = 0 \\ x_1+\frac{19}{2}x_5+\frac {5}{2}x_6-38x_7-\frac{2}{3}x_8=0 \\ x_3+40x_5-3x_6+90x_7+x_8=1 \\ x_4+x_8=1 \end{equation*}$

import pandas as pd #необходимо для оформления симлекс-таблиц
import copy

v = [0.,0.,0.,0.,300.,80.,-1219.,-1.]
a = [[0,1,0,0,-8,-2,30,1/2],
     [1,0,0,0,19/2,5/2,-38,-2/3],
     [0,0,1,0,40,-3,90,1],
     [0,0,0,1,0,0,0,1]
]
b = [0,0,1,1]

Let’s construct a problem using row vectors.

def rev(lst):
    return [ -i for i in lst ]

lin_prog = a
lin_prog.insert(4,rev(v))
lin_prog[4].insert(0,0)
for x in range(4):
  lin_prog[x].insert(0,b[x])
task = pd.DataFrame(columns = ['X_','X1','X2','X3','X4','X5','X6','X7','X8'],data = lin_prog)
print(task)

Let’s try the usual simplex method and get our expected looping. Let’s run a loop with our simplex tables stored in memory to detect the beginning of a loop.

def iter(a):
  max_x = 0
  max_y = 0
  while a[4][max_x]>=0:
    max_x+=1
    if max_x>8: 
      print('Оптимальное решение найдено')
      return a
  for x in range(max_x,9):
    if abs(a[4][x])>abs(a[4][max_x]) and a[4][x]<0 and a[4][x]!=0 and  a[1][x]>=0 and  a[2][x]>=0 and  a[3][x]>=0 : 
      max_x = x
  while a[max_y][max_x]<=0:
    max_y+=1
  for y in range(5):
    if a[y][max_x] <=0: continue
    if a[y][max_x]>0 and abs(a[y][0]/a[y][max_x])<abs(a[max_y][0]/a[max_y][max_x]): max_y = y
  b = copy.deepcopy(a)
  for i in range(5):
    for j in range(9):
      if i==max_y:
        b[i][j]= a[i][j]/a[max_y][max_x]
      if i!=max_y: b[i][j]=a[i][j]- a[i][max_x]*a[max_y][j]/a[max_y][max_x]
  return b

lin_prog_iter = copy.deepcopy(lin_prog)
for x in range(7):
  print(str(x)+' ITERATION\n')
  df = pd.DataFrame(columns = ['X_','X1','X2','X3','X4','X5','X6','X7','X8'],data = lin_prog_iter)
  print(df,'\n\n')
  lin_prog_iter=iter(lin_prog_iter)

0 - 3 iterations of the simplex method — 0 – 3 iterations of the simplex method

5th and 6th iterations of the simplex method

On 7 iterations received a simplex table identical to the table of the starting iteration, that is, what happened looping. The reason for this is the appearance in the column X_ zero values that set simplex differences to zero.

One effective solution to the looping problem is lexicographic simplex method. To begin, we need to introduce a few definitions.

Vector q – lexicographically positive (q>0) if its first non-zero element is positive.

Vector q lexicographically more vector p (q>p), if qp>0.

A simplex table in which all rows are lexicographically positive will be called lexicographically valid.

Лемма: If the simplex table is lexicographically admissible, and the numbers of the vectors input and output from the basis are such that the condition is satisfied:

$\begin{align} \vec{\mathbf{S}}_r= (\frac{\mathbf{X}r0}{\mathbf{X}rs}, ..., \frac{\mathbf{X}r0} {\mathbf{X}rs}) & = lexmin_{x_{sk>0}}\{\vec{\mathbf{S}}_k\}\\ (1) \end{align}” src=”https://habrastorage.org/getpro/habr/upload_files/7e7/610/b63/7e7610b63e1e9aa41a328aedfd6c2619.svg” width=”354″ height=”69″/>then the new simplex table will also be lexicographically valid.<code>Теорема:</code> If at each step of the simplex method, when selecting vectors input and output from the basis, condition (1) is satisfied, then the number of steps that must be completed before stopping on the basis of optimality or unboundedness of the objective function from above is finite.Applying the resulting theory, we recalculate our problem. Our problem is already lexicographically valid.<pre><code class=$ def iter_lex(a): max_x = 0 max_y = 0 while a[4][max_x]>=0: max_x+=1 if max_x>8: print('Оптимальное решение найдено') return a for x in range(max_x,9): if abs(a[4][x])>abs(a[4][max_x]) and a[4][x]<0 and a[4][x]!=0 and a[1][x]>=0 and a[2][x]>=0 and a[3][x]>=0 : max_x = x while a[max_y][max_x]<=0: max_y+=1 for y in range(5): if a[y][max_x] <=0: continue if a[y][max_x]>0 and abs(a[y][0]/a[y][max_x])<abs(a[max_y][0]/a[max_y][max_x]): max_y = y if a[y][max_x]>0 and abs(a[y][0]/a[y][max_x])==abs(a[max_y][0]/a[max_y][max_x]): for i in range(1,5): if a[y][max_x]>0 and abs(a[y][i]/a[y][max_x])==abs(a[max_y][i]/a[max_y][max_x]): pass if a[y][max_x]>0 and abs(a[y][i]/a[y][max_x])<abs(a[max_y][i]/a[max_y][max_x]): max_y = y break b = copy.deepcopy(a) for i in range(5): for j in range(9): if i==max_y: b[i][j]= a[i][j]/a[max_y][max_x] if i!=max_y: b[i][j]=a[i][j]- a[i][max_x]*a[max_y][j]/a[max_y][max_x] return b

lin_prog_iter = copy.deepcopy(lin_prog)
for x in range(4):
  print(str(x)+' ITERATION\n')
  df = pd.DataFrame(columns = ['X_','X1','X2','X3','X4','X5','X6','X7','X8'],data = lin_prog_iter)
  print(df,'\n\n')
  lin_prog_iter=iter_lex(lin_prog_iter)

Iterations of the lexicographic simplex method

The optimal solution has been found!

Conclusion: A relatively simple and convenient option for solving the problem of looping is the lexicographic simplex method, suitable for manually solving linear programming problems with a pre-prepared table.

ipynb article file:

GitHub – Happynood/lin_prog: Implementation of the lexicographic simplex method in Python

github.com