Имеем некоторую задачу линейного программирования с целевой функцией v, ограничениями a с вектором 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\\ x_1,x_2,…,x_8\ge0 \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]

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

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)
0 - 3 итерации симплекс-метода
0 - 3 итерации симплекс-метода
5 и 6 итерации симплекс-метода
5 и 6 итерации симплекс-метода

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

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

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

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

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

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

\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}

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

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

Применяя полученную теорию, пересчитаем нашу задачу. Наша задача уже является лексикографически допустимой.

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 файл статьи:

Комментарии (3)


  1. Rsa97
    27.11.2023 13:53
    +2

    В целевую функцию входят только x₅-x₈, а в каждом из ограничивающих уравнений есть отдельный независимый член x₁-x₄.
    Так что, при отсутствии прочих ограничений, решением будет
    x₅ →+∞
    x₆ →+∞
    x₇ →−∞
    x₈ →−∞
    x₁ = −19x₅ / 2 − 5x₆ / 2 + 38x₇ + 2x₈ / 3
    x₂ = 8x₅ + 2x₆ − 30x₇ − x₈ / 2
    x₃ = 1 − 40x₅ + 3x₆ − 90x₇ − x₈
    x₄ = 1 − x₈


    1. Happynood Автор
      27.11.2023 13:53

      Спасибо за конструктивную критику. И правда забыл включить ограничение.


  1. redreem
    27.11.2023 13:53
    +1

    в заголовке "п" пропустили.