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)

с новым  последним базисом , который подлежит исследованию симплекс-методом.

Но указанных значений  может оказаться и много. Одна из цепочек может и не привести к нужному результату. Необходимо произвести перебор всех цепочек. Отметим, что сам перебор цепочек становится громоздким.

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