Симплекс-метод. Простое объяснение

Причины создания этого учебника

править

В интернете опубликовано множество объяснений алгоритма симплекс-метода, про которые можно смело сказать «лучше ничего, чем это». Они написаны крайне заумным языком и доставляют множество страданий всем, кто пытается с их помощью изучить этот метод линейного программирования.

Целью данного учебника является создание простого и доступного описания алгоритма симплекс-метода, которое можно понять, что называется, «с ходу».

Задача линейного программирования

править

Задача линейного программирования в стандартной форме заключается в том, чтобы найти экстремум функции

 

при заданных ограничениях:

 

 

 

 

Симплекс-таблица

править

Запишем симплекс-таблицу:

     
         
         
         
       

Алгоритм

править

Первый шаг алгоритма состоит в том, чтобы найти минимальный элемент в последней строке ( ). Номер этого элемента определит разрешающий столбец.

На втором шаге определяется разрешающая строка. Для этого нужно найти симплекс отношение: в каждой строке элемент последнего столбца делится на соответствующий элемент разрешающего столбца. Так получается столбец симплекс-отношений. Минимальный элемент в этом столбце и определяет разрешающую строку.

Приступаем к построению новой симплекс-таблицы. Метки   и   для разрешающей строки и столбца соответственно меняются местами:   обозначает теперь столбец, а   — строку. Элемент на пересечении разрешающего столбца и разрешающей строки возводим в степень  . Все элементы разрешающей строки, кроме того, что на пересечении, делим на этот элемент на пересечении. Все элементы разрешающего столбца, кроме того, что на пересечении, делим на этот элемент на пересечении и умножаем на  .

Остальные элементы новой симплекс таблицы высчитываются по правилу прямоугольника:

  ……………………………………. <пересч. элемент  >

<элемент на пересечении   > …  


  новый =  

Вышеуказанные операции выполняются для всех элементов, включая  ,   и   и повторяются до тех пор, пока в строке   будут отрицательные элементы.

Если же отрицательных элементов в строке больше нет, значит, оптимальное решение достигнуто. Оно будет находиться в последнем столбце  , его будут обозначать соответствующие метки « » строк.

Подставив найденные   в целевую функцию, находим оптимальное решение.