28.5. Симплекс-метод.
Реальные задачи линейного программирования содержат, как правило, большое число ограничений и неизвестных. Поэтому естественно, что решение таких задач связано с большим объемом вычислений. Это затруднение преодолевается с помощью быстродействующих электронно-вычислительных машин (ЭВМ). Для каждой задачи разрабатываются алгоритм и программа, и затем ЭВМ в короткий срок дает решение поставленной задачи.
Существуют и другие общие методы, позволяющие найти решение любой задачи линейного программирования в обозримое число шагов.
Таким является симплекс-метод. Опишем идею этого метода.
Пусть надо найти минимум линейной функции
(11)
Среди значений
, удовлетворяющих равенствам
. (4)
Неотрицательные решения системы (4)
мы условимся называть допустимыми, а точку
- допустимой точкой. Покажем, как эту задачу можно решить, применяй симплекс-метод.
Пусть ранг матрицы
равен
(
- ранг
). Будем считать, что система (4) разрешима относительно
:
, (12)
и числа
неотрицательны
.
В этом случае говорят, что переменные
образуют базис - базис
. Остальные переменные называются свободными или небазисными. Следует обратить внимание, что здесь понятие базиса не совпадает с понятием базиса из § 16.
Вопрос о возможности перехода от системы (4) к системе (12) будет рассмотрен ниже в п. 28.8.
Системы (4) и (12) равносильны, поэтому допустимая точка
системы (4) есть допустимая точка системы (12), и обратно.
Очевидно, точка
допустимая, ее называют базисным решением, отвечающим базису
. Будем писать
. В силу равенств (12) функцию
можно записать в виде линейной функции от переменных
:
. (13)
Очевидно, что
.
Первый этап симплекс-метода связан с рассмотрением функции
, определяемой равенством (13), и системы ограничений в виде равенств (12).
Рассмотрим четыре возможных случая
.
Случай
. Пусть
для всех
. Тогда минимум
, определяемой равенством (13), относительно всех
, будет равен
:

Этот минимум остается тем же для допустимых
. Этим задача на минимум решена.
Случай
. Пусть для некоторого
и все коэффициенты
матрицы
неположительны:
.
Тогда при любом
точка
. (14)
где
вычисляются по формулам (12), будет допустимой, и если ее подставить в
, то получим
при
. Поэтому
,
и нашу задачу о минимуме можно считать решенной.
Случай
. Пусть для некоторого
коэффициент
функции
положительный
и имеются положительные коэффициенты
в
- м столбце матрицы
:
, (15)
где
- множество индексов
, для которых выполняется неравенство (15).
Пусть
. (16)
Элемент
называется разрешающим элементом.
Рассмотрим отдельно случай
и
, которые будем обозначать через
, и
соответственно.
Случай
. Точка (14) для значений
, удовлетворяющих неравенствам
, допустимая. В самом деле, в силу (12) при
непосредственно видно, что
,
а при
в силу соотношений (15), (16) имеем
.
Если
непрерывно возрастает от
до
, то все
, а
к тому же непрерывно убывает от
до
. При дальнейшем возрастании
переменная
становится отрицательной и точка (14) перестает быть допустимой.
Функция

при возрастании
от
до
убывает от
до
, где
(17)
и
стоит на
- м месте.
Таким образом,
.
Отметим, что координата
в (17) равна нулю:
.
Так как
, то
- е уравнение системы (12) можно решить относительно
:
(18)
Мы выразили
через
и остальные переменные
. Можно выразить через эти переменные также любую переменную
, если подставить выражение (18) вместо
в равенства (12), соответствующие любым
.
Итак, в случае
удается решить систему (12) относительно переменных
(19)
Условно запишем соответствующую систему равенств так:
, (20)
хотя на самом деле в этих равенствах только переменные
остались прежними, а переменные
и
поменялись местами.
Покажем, что свободные члены
. (21)
В самом деле, если
, то 
.
Если же
, то

и неравенства (21) доказаны.
Итак, переменные
в системе (20) образуют базис - базис
(см. также (19)).
Для базисного решения 
.
Базис
отличен от базиса
, и для него можно начать второй этап рассуждений (случай
). Таким образом, случай
, рассмотрен.
Случай
. Пусть
для
. В этом случае
(см. (16)) и равенство с номером
в (12) имеет вид
. (22)
Если в равенстве (22) все коэффициенты
положительные, то система (12) имеет единственное допустимое решение
. Значение функции
на этом базисном решении будет:
. Задача на минимум функции
в этом случае решена.
Допустим, что в (22) имеются коэффициенты
для некоторого значения
. Тогда, как и в случае
, переходим к новому базису
(вводим в базис переменную
и выводим из него
,
- разрешающий элемент). Отметим, что в этом случае значение
.
Итак, рассматривая базис
, мы либо решим нашу задачу на минимум, либо придем к новому базису
. К базису
снова применяем наш метод - это приведет к решению задачи либо к новому базису
. Продолжая этот процесс, получим цепочку базисов
. (23)
Если для некоторого
будет иметь место случай
или
, то цепочка на этом
оборвется и задача будет решена. Иначе от базиса
, переходим к базису
.
Однако может случиться цикл. Он заключается в том, что хотя каждый последующий базис цепочки и отличается от предыдущего, но для некоторых
и
будет происходить совпадение базисов:
.
Разберемся, что здесь происходит. Для базиса
, произошел случай
, т. е. оказалось, что существует
и такое
, что
, (24)
и это привело к базису
.
Но пара чисел
, вообще говоря, неединственна, и какая-то другая пара
, для которой выполняются свойства (24), может привести к базису, отличному от базиса
. Это на самом деле и имеет место, как учит теория (см. ниже теорему 1 и замечания к ней).
Таким образом, если для некоторых
и
случится цикл, то его можно устранить. В этом случае для базиса
надо перебрать всевозможные пары
, обладающие свойствами (24). Каждая такая пара приводит к некоторому базису. Среди них есть отличный от базисов
.
28.6. Устранение цикла.
На практике циклы бывают очень редко. Все же объясним, как их можно «разорвать» (устранить).
Отметим теорему, доказательство которой будет намечено в п. 28.7.
Теорема 1. От любого базиса
существует путь, ведущий к решению задачи на минимум, т. е. существует цепочка базисов, получаемых симплекс-методом, приводящая к минимуму (или к
).
Итак, пусть имеем цикл
.
Тогда, очевидно,
.
Пусть
- наименьшее неотрицательное целое число, для которого

Очевидно, для базисов
(25)
имеет место случай
. Переход от любого из этих базисов
к последующему совершается посредством разрешающего элемента
. Но базису
может соответствовать и другой разрешающий элемент, который переводит
, в базис
, отличный от
.
Может случиться, что для любого
базис
содержится в цепочке (25). Тогда все базисы (25) решают задачу на минимум, т. е.
. Ведь по теореме 1 существует путь, ведущий от
к минимуму. Но в данном случае все пути от
ведут к базисам цепочки (25).
Однако может случиться, что для некоторого
разрешающий элемент базиса
переводит
в базис
, не входящий в цепочку (25). Тогда мы получим новую цепочку
(26)
с новым последним базисом
, который подлежит исследованию симплекс-методом.
Но указанных значений
может оказаться и много. Одна из цепочек может и не привести к нужному результату. Необходимо произвести перебор всех цепочек. Отметим, что сам перебор цепочек становится громоздким.
Если произошел цикл, то можно порекомендовать специальный метод выбора разрешающего элемента. Этот метод связан с дополнительными вычислениями, но зато последовательное его применение необходимо приводит к решению задачи без зацикливания (без образования циклов).