§ 3. СИМПЛЕКС-МЕТОД

Симплекс-метод. Симплекс-метод для задач линейного программирования был разработан Данцигом. В изложенном ниже простом методе одновременного решения двух взаимно двойственных канонических задач мы следуем Холлу [27]. Рассмотрим взаимно двойственные канонические задачи.

К. Найти решение системы

которое минимизирует линейную форму

К*. Найти решение системы

которое максимизирует линейную форму u:

Симплекс-метод есть метод одновременного решения обеих взаимно двойственных канонических задач К и К.

Пусть матрица системы уравнений (I). Ниже мы будем предполагать, что ранг матрицы А равен это предположение несколько упрощает схему изложения симплекс-метода. Общий случай легко может быть сведен к этому случаю.

Рассмотрим таблицу

Эта таблица удобна для одновременного представления двух систем линейных уравнений. Она представляет линейную систему по строкам:

и по столбцам:

Осевое преобразование таблицы с ведущим элементом а — это такое преобразование, которое заменяет исходную таблицу таблицей, соответствующей решению системы (1) относительно и решению системы (2) относительно

Решив уравнение системы (1), содержащее ведущий элемент а, относительно , имеем

Подставив это выражение для в другие уравнения системы (1), получим:

Аналогично, решая систему (2) относительно , получим

Таким образом, осевое преобразование таблицы с ведущим элементом а заменяет исходную таблицу следующей таблицей: соответствующей решению системы (1) по строкам относительно и системы (2) по столбцам относительно

Обе взаимно двойственные канонические задачи К и К представляет таблица

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

В результате приходим к таблице вида

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

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

Таблицу Т называют допустимой по строкам, если выполнены условия

Эти условия означают, что вектор является допустимым вектором задачи К, т. е. удовлетворяет системе (I). Предположим, что таблица Т допустима по строкам, т. е. выполнены условия (1).

Цель следующего этапа решения задачи состоит в том, чтобы по таблице, полученной из Т в результате цепочки осевых преобразований, найти допустимые векторы обеих задач (К и К, которые удовлетворяют условиям

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

Введем обозначения: — неотрицательное число, — неположительное число. Допустим, что мы, исходя из таблицы Т, сможем перейти к таблице вида

Тогда, придавая свободным переменным значения, равные нулю, получим допустимые векторы для обеих задач (К и К, которые являются оптимальными векторами этих задач.

Рассмотрим влияние осевого преобразования с ведущим элементом на столбец свободных членов и на значение линейной формы v, подлежащей минимизации:

Мы предполагаем, что в таблице (слева) элементы р; столбца свободных членов неположительны, т. е.

Мы хотим, чтобы новое значение линейной формы v не было больше предыдущего, т. е. . Это неравенство выполняется, если выполняются условия

При выполнении этих условий новое значение линейной формы v не больше предыдущего, причем новое значение формы v при строго меньше предыдущего.

Кроме того, мы хотим, чтобы новые элементы столбца свободных членов были неположительны, т. е.

При выполнении условий (а) и при это неравенство выполняется. Если же то неравенство можно записать в виде

Таким образом, мы приходим к следующему правилу выбора ведущего элемента осевого преобразования таблицы, которая допустима по строкам.

Пусть таблица допустима по строкам. В качестве ведущего элемента (при осевом преобразовании) следует выбирать элемент если выполнены условия:

Выбор ведущего элемента в соответствии с этим правилом обеспечивает допустимость новой таблицы по строкам и при дает новое значение линейной формы v (подлежащей минимизации), строго меньшее, чем предыдущее.

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

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

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

Первые строк этой таблицы будем рассматривать как таблицу, допустимую по строкам, и постараемся минимизировать . Если на каком-либо шаге мы достигнем неположительного значения для получим допустимых строк или больше. Продолжаем процесс аналогичным образом, стремясь представить в допустимой форме как можно больше строк.

Если при этом в таблице появится плюсовая строка, т. е. (недопустимая) строка вида то это будет означать, что задача К недопустима, так как невозможно удовлетворить условию — .

Если же окажется, что минимальное значение положительно, то появляется таблица вида

В этом случае в качестве ведущего выбираем элемент, отмеченный стрелкой. Легко проверить, что такой выбор дает допустимых строк или еще больше.

Таким образом, описан способ нахождения допустимого решения задачи К во всех возможных случаях.

Задача. Найти решение системы

которое минимизирует линейную форму

Задача, двойственная данной, формулируется так: найти решение системы

которое максимизирует линейную форму и,

Обе эти задачи представляет следующая таблица:

Будем искать одновременно решения обеих задач. Вначале исключим неизвестные . Исключая при помощи осевого преобразования с ведущим элементом 1, отмеченным жирным шрифтом, получим

Теперь исключим осевым преобразованием с ведущим элементом 4 в первом столбце:

Из первого и пятого столбцов видно, что выражаются через следующим образом:

Исключая первый и пятый столбцы в предыдущей таблице, получим

Эта таблица допустима по строкам. В соответствии с правилом выбора ведущего элемента выбираем элемент 2 во втором столбце и, произведя осевое преобразование, приходим к таблице

В полученной таблице выбираем элемент 7/8 в первом столбце в качестве ведущего элемента и, произведя осевое преобразование, приходим к таблице

Эта таблица допустима как по строкам, так и по столбцам. Полагая «свободные» переменные равными нулю, получим:

Подставляя найденные значения в формулы (III), получим Следовательно, вектор (0, 4/7, 12/7, 0, 0) есть решение первой задачи, а вектор (23/7, — 50/7) — решение двойственной задачи. При этом , т. е. минимальное значение линейной формы v и максимальное значение линейной формы и равно