Happynood 27 ноя 2023 в 16:16

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

Простой

3 мин

Python*Big Data*Математика*Машинное обучение*

Имеем некоторую задачу линейного программирования с целевой функцией 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)

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

GitHub - Happynood/lin_prog: Implementation of the lexicographic simplex method in Python

github.com

Теги:

Хабы:

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

Публикации

Истории

Работа

Ближайшие события