[Python] Cycling of Lexicographic simplex method

I am studying the cycling of simplex method. I know that there is a lexicographic rule to prevent looping of the simplex method, and I also know that this rule should be applied to a lexicographically valid simplex table (this is a table in which the first non-zero coefficients are positive). But I know that there is a way to loop the lexicographic simplex method, for this you need to select the appropriate lexicographically invalid simplex table. Can you please help with this task to find such table (I also know that at least such a table has a dimension of 3 (constraints) by 7 (variables))

I tried to find such a table by iteration (given the fact that such a table starts with 3 constraints and 7 variables). Ideally, I expect to get such a table

I have this code:

import pandas as pd
import copy
import math

pd.set_option('display.max_colwidth', None)
pd.set_option('display.max_columns', None)
pd.set_option('display.width', None)

Bi = [1, 0, 0]
vectorC = [0, 0, 0, 2.2361, -2, 0, -4, -3.6180, -3.236, -3.6180, -0.764]
coeficients_Aij = [
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0.3090, -0.6180, -0.8090, -0.3820, 0.8090, 0.3820, 0.3090, 0.6180],
[0, 0, 1, 1.4635, 0.3090, 1.4635, -0.8090, -0.9045, -0.8090, 0.4635, 0.309],
]

def is_Lexicographic(matrix):
flag = True
for i in matrix:
for j in i:
if j == 0:
continue
elif j > 0:
break
elif j < 0:
return False
return flag

spCol = []
strNum = len(Bi)
xNum = len(coeficients_Aij[0])
spBasises = []
spBasises.append([i for i in range(xNum - strNum + 1, xNum + 1)])

spCol.append("_X_")
for i in range(xNum):
spCol.append(f"X{i + 1}")

def isclose(a, b, rel_tol=1e-09, abs_tol=0.0):
return abs(a-b) <= max(rel_tol * max(abs(a), abs(b)), abs_tol)
def isTableValide(matrix_Aij):
flag = True
for i in range(xNum + 1):
if matrix_Aij[strNum] < 0:
count = 0
for j in range(strNum):
if not (isclose(matrix_Aij[j], 0)) and matrix_Aij[j] > 0:
count += 1
if count == 0:
print("FLAG")
print(matrix_Aij[0][0])
print(matrix_Aij[strNum][xNum])
return False
return True

def reverseC(vectorC):
result = []
for i in vectorC:
result.append(-i)
return result


print("START TABLE:")
symplex_Table = coeficients_Aij
symplex_Table.insert(strNum, reverseC(vectorC))
symplex_Table[strNum].insert(0, 0)
for i in range(strNum):
symplex_Table.insert(0, Bi)
init_Symplex_Table = pd.DataFrame(columns=spCol, data=symplex_Table)
print(init_Symplex_Table)

def lexicSymplexMethod(matrix_Aij):
Max_Xj = 0
Max_Yi = 0

if not(isTableValide(matrix_Aij)):
print("There is no solution due to the unlimited function")
return 1

while matrix_Aij[strNum][Max_Xj] >= 0:
Max_Xj += 1
if Max_Xj > xNum:
print('FIND OPTIMAL SOLUTION')
return [matrix_Aij, 2]
for Xj in range(Max_Xj, xNum + 1):
flag = True
c = 1
if abs(matrix_Aij[strNum][Xj]) > abs(matrix_Aij[strNum][Max_Xj]) and matrix_Aij[strNum][Xj] != 0 and \
matrix_Aij[strNum][Xj] < 0:
while c <= len(matrix_Aij) - 2:
if not (matrix_Aij[c][Xj] >= 0):
flag = False
break
c = c + 1
if flag:
Max_Xj = Xj
#while matrix_Aij[Max_Yi][Max_Xj] <= 0:
while isclose(matrix_Aij[Max_Yi][Max_Xj], 0) or matrix_Aij[Max_Yi][Max_Xj] < 0:
Max_Yi += 1
if Max_Yi > strNum:
print("There is no solution due to the unlimited function")
return 1
for Yi in range(strNum + 1):
if matrix_Aij[Yi][Max_Xj] <= 0:
continue
if matrix_Aij[Yi][Max_Xj] > 0 and abs(matrix_Aij[Yi][0] / matrix_Aij[Yi][Max_Xj]) < abs(
matrix_Aij[Max_Yi][0] / matrix_Aij[Max_Yi][Max_Xj]):
Max_Yi = Yi
if matrix_Aij[Yi][Max_Xj] > 0 and abs(matrix_Aij[Yi][0] / matrix_Aij[Yi][Max_Xj]) == abs(
matrix_Aij[Max_Yi][0] / matrix_Aij[Max_Yi][Max_Xj]):
for i in range(1, strNum + 1):
if matrix_Aij[Yi][Max_Xj] > 0 and abs(matrix_Aij[Yi] / matrix_Aij[Yi][Max_Xj]) == abs(
matrix_Aij[Max_Yi] / matrix_Aij[Max_Yi][Max_Xj]):
pass
if matrix_Aij[Yi][Max_Xj] > 0 and abs(matrix_Aij[Yi] / matrix_Aij[Yi][Max_Xj]) < abs(
matrix_Aij[Max_Yi] / matrix_Aij[Max_Yi][Max_Xj]):
Max_Yi = Yi
break
Copy_matrix_Aij = copy.deepcopy(matrix_Aij)
for Yi in range(strNum + 1):
for Xj in range(xNum + 1):
if Yi == Max_Yi:
Copy_matrix_Aij[Yi][Xj] = matrix_Aij[Yi][Xj] / matrix_Aij[Max_Yi][Max_Xj]
if Yi != Max_Yi:
Copy_matrix_Aij[Yi][Xj] = matrix_Aij[Yi][Xj] - matrix_Aij[Max_Yi][Xj] * matrix_Aij[Yi][Max_Xj] / \
matrix_Aij[Max_Yi][Max_Xj]
return Copy_matrix_Aij


iterated_Symplex_Table = copy.deepcopy(symplex_Table)
i = 0
while True:
print(f"Iteration № {i}")
i += 1
outCurrent_Symplex_Table = pd.DataFrame(columns=spCol, data=iterated_Symplex_Table)
print(outCurrent_Symplex_Table)
print()
print()
print()
iterated_Symplex_Table = lexicSymplexMethod(iterated_Symplex_Table)
if iterated_Symplex_Table == 1:
print("NO SOLUTION!!!")
break
if len(iterated_Symplex_Table) == 2 and iterated_Symplex_Table[1] == 2:
print('FIND OPTIMAL SOLUTION')
break



In fact, the task is to select such values in the variables : coeficients_Aij , Bi, VectorC, so that the program loops

In trying to find an answer to this question, I relied on the following sources:
theory about simplex algorithms;
theory about lexicographical simplex metod;
Visualizing cycles in simplex method - for to understand and represent the looping process;
here is an example of the code and an example of the implementation of the usual simplex method and the lexicographic simplex method and the principle of their operation is explained

Continue reading...