Табличный алгоритм замены базисных переменных

Процедура «переразрешения» системы уравнений-ограничений ОЗЛП относительно новых базисных переменных может быть существенно упрощена, если ее формализовать и свести к заполнению стандартных таблиц по определенной системе правил (короче, алгоритму). Этот алгоритм мы продемонстрируем на конкретном примере (в его справедливости для любого общего случая читатель сможет убедиться самостоятельно).

Рассмотрим систему пяти уравнений-ограничений:

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

Посмотрим, какие действия надо для этого осуществить.

Вообще, можно было бы для каждой новой системы уравнений проводить переразрешение заново, т. е. для замены мы взяли бы в третьем уравнении (6.1) член содержащий (назовем его «разрешающим членом»; разумеется, предполагаем перенесли бы его в левую часть, а — в правую; решили бы уравнение относительно и подставили бы выражение для во все остальные уравнения. Процедура достаточно громоздкая, требующая напряженного внимания; при ее выполнении легко ошибиться (особенно при большом числе уравнений). Но так как здесь каждый раз нужно проделывать одни и те же операции, то их достаточно выполнить один раз в общем виде и вывести правила преобразования, которые затем можно применять автоматически. Эти правила, осуществляющие «переразрешение» системы, удобно реализовать в виде табличного алгоритма.

Чтобы этот алгоритм был проще и легче запоминался, целесообразно предварительно несколько преобразовать систему уравнений (6.1), представив их правые части как разности между свободными членами и суммой остальных:

Обозначая

получим:

Форму записи уравнений (6.2) мы будем называть стандартной.

Очевидно, вместо того, чтобы полностью записывать уравнения (6.2), можно ограничиться заполнением стандартной таблиц, где указаны только свободные члены и коэффициенты при переменных. Первый столбец таблицы мы отведем под свободные члены, второй, третий, четвертый и пятый — под коэффициенты при переменных в стандартной форме (6.2). Стандартная таблиц! для системы (6.2) приведена в табл. 6.1.

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

Таблица 6.1.

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

Таблица 6.2

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

Найдем коэффициенты, которые нужно будет поставить в таблице после обмена. Начнем с преобразования разрешающей строки. Решая третье уравнение (6.2) относительно, получим:

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

Для этого подставим в первое уравнение (6.2) вместо его выражение (6.3). После приведения подобных членов получим

Нетрудно убедиться, что совершенно аналогичным образом преобразовываются все остальные строки. В результате мы получим преобразованную таблицу (см. табл. 6.3), в которой операция уже совершена.

Таблица 6.3

Рассмотрев табл. 6.3, мы можем так сформулировать алгоритм преобразования коэффициентов стандартной таблицы.

1. Разрешающий элемент заменяется на обратную ему величину.

2. Все остальные элементы разрешающей строки делятся на разрешающий элемент.

3. Все элементы разрешающего столбца (кроме самого разрешающего элемента) меняют знак и делятся на разрешающий элемент.

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

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

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

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

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

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

2. Все элементы разрешающей строки (кроме самого) умножить на k; результат записать в нижней части той же ячейки.

3. Все элементы разрешающего столбца (кроме самого) умножить на; результат записать в нижней части той же ячейки.

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

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

6. Переписать таблицу, заменив:

на и обратно,

— элементы разрешающей строки и столбца — числами, стоящими в нижних частях тех же ячеек,

— каждый из остальных элементов — суммой чисел, стоящих в верхней и нижней части той же ячейки.

Пример 1. В системе уравнений

произвести замену т. е. вывести из числа свободных переменных и взамен ее ввести

Таблииа 6.4

Решение. Записываем уравнения (6.3) в форме стандартной таблицы (см. табл. 6.4), оставляя в нижней части каждой ячейки достаточно свободного места.

Выделяем кружком разрешающий элемент — 2 и жирными линиями разрешающие строку и столбец. Вычисляем Вспомогательные записи будем вести в правом нижнем углу ячейки (см. табл. 6.5).

Заполним, согласно пунктам 1, 2 и 3 алгоритма, нижиие части ячеек разрешающих строки и столбца.

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

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

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

Таким образом, мы научились с помощью табличного алгоритма совершать в уравнениях-ограничениях любую замену

Вспомним, что в задаче линейного программирования, кроме уравнений-ограничений, существует еще и линейная функция

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

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

Таблица 6.5

Таблица 6.6

Таблица 6.7

Таблица 6.8

Пример 2. Сделать замену в системе уравнений

и в линейной функции

Решение. Заполняем стандартную таблицу, в верхней строке которой помещаем линейную функцию L (см. табл. 6.8).

Таблица 6.9

Для выполнения замены в той же таблице делаем дополнительные расчеты (см. табл 6.9)

Заменой таблица приводится к виду (табл. 6 10)

Таблица 6.10

С помощью табличного алгоритма обмена переменных в уравнениях ОЗЛП можно решить любую задачу линейного программирования или же убедиться, что она не имеет решения.

Нахождение решения каждой задачи линейного программирования распадается на два этапа:

1) отыскание опорного решения;

2) отыскание оптимального решения, минимизирующего линейную функцию

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

В процессе второго этапа попутно выясняется, ограничена ли снизу минимизируемая функция L; если нет, то оптимального решения не существует. Если да, то оно находится после того или другого числа замен.

Оба этапа решения ОЗЛП удобно выполнять с помощью описанного алгоритма преобразования стандартных таблиц.