Материал: Материалы по курсу (часть 2)

Таблица 6.2.

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

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

(6.3)

Таким образом, преобразованные элементы разрешающей строки найдены. Составим правило преобразования остальных строк. Для этого подставим в первое уравнение (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)

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

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

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

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

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

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

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

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

,

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

,

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

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

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

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

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

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

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

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

8. Отыскание опорного решения задачи лп на основе табличного алгоритма замены переменных.

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

Пусть имеется ОЗЛП (осн. задача лин. програм.) с ограничениями-равенствами, в следующей форме:

• Первое пробное решение x₁ = x₂ = ... = x_n = 0. Если все b_i ³ 0, то это допустимое решение, следовательно, оно опорное.

Если какие-либо b_i < 0, то это решение не допустимое и не опорное.

• Для нахождения ОР нужно шаг за шагом обменивать базисные и свободные переменные, пока не найдем его, либо убедимся, что система уравнений несовместима с неравенствами x₁ ³ 0, x₂ ³ 0,..., x_n ³ 0; y₁ ³ 0, y₂ ³ 0,..., y_m ³ 0.

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

Способ выбора разрешающего элемента для приближения к опорному решению

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

Ищем в этой строке отрицательный a_ij. Если они все положительные (значит все a_ij < 0)) и данная базисная никогда не будет положительной.

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

Рассмотрим только те элементы столбца, которые имеют один знак со свободным членом.

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

ПРИМЕР: (найти опорное решение задачи ЛП)

(элементы записываем не по строкам, а по столбцам!)

Видим, что есть отрицательный свободный член (-5) – это плохо. Значит нужно производить замену. Выберем разрешающий элемент:

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

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

_{Произведем замену} y₃ « x_1.

_{Получаем:}

Видим, что есть отрицательный свободный член (-1) – это плохо. Значит нужно производить замену. Выберем разрешающий элемент:

Проводим аналогичные действия.

Минимум для строк y2 и y4. Из них можно выбрать любой.

_{Производим замену} y₂ « x_3.

_{Получаем:}