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

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

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

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

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

Вообще, можно было бы для каждой новой системы уравнений проводить переразрешение заново, т.е. для замены .

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

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

(6.1)

Обозначая

получим:

(6.2)

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

Вместо того чтобы полностью записывать уравнения (6.2), можно ограничиться заполнением стандартной таблицы, где указаны только свободные члены и коэффициенты при переменных. Первый столбец таблицы мы отведем под свободные члены, второй, третий, четвертый и пятый – под коэффициенты при переменных х₁,х₂,х₃,х₄ в стандартной форме (6.2). Стандартная таблица для системы (6.2) имеет следующий вид (Табл.6.1).

Таблица.1

	Свободный член

Мы хотим произвести замену

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

Таблица 6.2

	Свободный член

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

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

Таким образом, преобразованные элементы разрешающей строки найдены. Составим правило преобразования остальных строк. Для этого подставим в первое уравнение (6.2) вместо х₂ его выражение (6.3). После проведения подобных членов получим

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

Таблица 6.3

	Свободный член

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

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

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

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

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

Покажем, как последнее правило применяется, хотя бы на примере элемента, стоящего в первой строке и втором столбце табл. 6.3. Новый элемент равен прежнему (α₁₁) плюс произведение прежнего элемента разрешающей строки α₃₁, стоящего в том же столбце, что α₁₁, нового элемента разрешающего столбца –((α₁₂/α₃₂)), стоящего в той же строке, что и преобразуемый элемент.

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

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

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

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

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

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

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

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

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

- х_j на у_i и обратно;

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

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

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

(6.4)

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

Таблица 6.4

	Cвободный член
	-5	-1		-2
		-2
	-1		-2

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

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

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

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

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

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

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

,

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

,

где γ₁=-с₁; γ₂=-с₂;…; γ_n=-с_n, получим еще одну строку (добавочную) стандартной таблицы, которая отличается от остальных только тем, что в ней никогда не выбирается разрешающий элемент, а все остальные действия совершаются те же.

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

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

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

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

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

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

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