Лексикографический симплекс-метод

Имеем некоторую задачу линейного программирования с целевой функцией v, ограничениями a с вектором b.

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]

Построим задачу по вектор-строкам.

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])<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)

На 7 итерации получили симлекс-таблицу идентичную таблице стартовой итерации, то есть произошло зацикливание. Причиной этому является появление в столбце X_ нулевых значений, обнуляющих симплекс-разности.

Одним из эффективных решений проблемы зацикливания является лексикографический симплекс-метод. Для начала необходимо ввести несколько определений.

Вектор q – лексикографически положителен (q>0), если его первый отличный от нуля элемент положителен.

Вектор q лексикографически больше вектора p (q>p), если q-p>0.

Симплекс-таблицу, все строки которой лексикографически положительны, будем называть лексикографически допустимой.

Лемма: Если симплекс-таблица лексикографически допустима, а номера вводимого и выводимого из базиса векторов таковы, что выполняется условие:

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)

Оптимальное решение найдено!

Вывод: относительно простым и удобным вариантом решения проблемы зациливания является лексикографический симплекс-метод, подходящий для ручного решения задач линейного программирования с заранее подготовленной таблицей.

ipynb файл статьи: