Циклизация лексикографического симплексного метода ⇐ Python

[Anonymous]

Я изучаю цикличность симплексного метода. Я знаю, что существует лексикографическое правило, предотвращающее зацикливание симплексного метода, и я также знаю, что это правило следует применять к лексикографически допустимой симплексной таблице (это таблица, в которой первые ненулевые коэффициенты положительны). Но я знаю, что есть способ зациклить лексикографический симплексный метод, для этого нужно выбрать соответствующую лексикографически недействительную симплексную таблицу. Помогите, пожалуйста, с задачей найти такую ​​таблицу (я также знаю, что как минимум такая таблица имеет размерность 3 (ограничения) на 7 (переменные))
Я пытался найти такую ​​таблицу итерацией (с учетом того, что такая таблица начинается с 3 ограничений и 7 переменных). В идеале я рассчитываю получить такую ​​таблицу.
У меня есть такой код:

Код: Выделить всё

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)  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[i].insert(0, Bi[i])
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 = 0):
flag = False
break
c = c + 1
if flag:
Max_Xj = Xj
#while matrix_Aij[Max_Yi][Max_Xj]  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 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][i] / matrix_Aij[Yi][Max_Xj]) == abs(
matrix_Aij[Max_Yi][i] / matrix_Aij[Max_Yi][Max_Xj]):
pass
if matrix_Aij[Yi][Max_Xj] > 0 and abs(matrix_Aij[Yi][i] / matrix_Aij[Yi][Max_Xj]) <  abs(
matrix_Aij[Max_Yi][i] / 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

На самом деле задача состоит в том, чтобы выбрать в переменных такие значения: coeficients_Aij, Bi, VectorC, чтобы программа зациклилась
При попытке Чтобы найти ответ на этот вопрос, я опирался на следующие источники:

теория симплексных алгоритмов;

теория лексикографического симплексного метода;

Визуализация циклы в симплекс-методе - для понимания и представления процесса зацикливания;

здесь пример кода и пример реализации обычного симплекс-метода и лексикографического симплекс-метода и принцип их работы операция объяснена

Подробнее здесь: https://stackoverflow.com/questions/792 ... lex-method