Лексикографический симлекс-метод
Имеем некоторую задачу линейного программирования с целевой функцией v, ограничениями a с вектором b.
import pandas as pd #необходимо для оформления симлекс-таблиц
import copyv = [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]Построим задачу по вектор-строкам.
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)
Вывод программы
Попробуем обычный симплекс-метод и получим наше ожидаемое зацикливание. Запустим цикл с занесением в память наших симплекс-таблиц для обнаружения начала зацикливания.
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])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 итерации симлекс-метода
5 и 6 итерации симлекс-метода
На 7 итерации получили симлекс-таблицу идентичную таблице стартовой итерации, то есть произошло зацикливание. Причиной этому является появление в столбце X_ нулевых значений, обнуляющих симплекс-разности.
Одним из эффективных решений проблемы зацикливания является лексикографический симлекс-метод. Для начала необходимо ввести несколько определений.
Вектор q — лексикографически положителен (q>0), если его первый отличный от нуля элемент положителен.
Вектор q лексикографически больше вектора p (q>p), если q-p>0.
Симплекс-таблицу, все строки которой лексикографически положительны, будем называть лексикографически допустимой.
Лемма: Если симплекс-таблица лексикографически допустима, а номера вводимого и выводимого из базиса векторов таковы, что выполняется условие:
Итерации лексикографического симлекс-метода Оптимальное решение найдено! Вывод: относительно простым и удобным вариантом решения проблемы зациливания является лексикографический симлекс-метод, подходящий для ручного решения задач линейного программирования с заранее подготовленной таблицей. ipynb файл статьи: GitHub — Happynood/lin_prog: Implementation of the lexicographic simplex method in Pythondef 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])
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)
