эффициенты на главной диагонали равны 1, а все внедиагональные - 0). Сохраняя ту же структуру таблицы, после серии симплекс-преобразований методом Га-усса-Жордана получим то, что называется обратной матрицей. Как будет показано далее в этой главе, обратная матрица играет ключевую роль при вычислении всех элементов симплекс-таблиц.

z-строка целевой функции

Начальные базисные переменные

Столбцы коэффициентов < ограничений

□

(Начальная таблица)

Единичная матрица

z-строка целевой функции

Начальные базисные переменные

Столбцы коэффициентов < ограничений

Обратная матрица

□

(Общая таблица)

Рис. 4.1. Схематическое представление начальной и общих симплекс-таблиц

УПРАЖНЕНИЯ 4.2.2

1. Вернитесь к таблице с оптимальным решением примера 3.3.1.

a) Определите в этой таблице обратную матрицу.

b) Покажите, что вектор значений в столбце Решение (без значения z-строки) равен произведению обратной матрицы на вектор правых частей исходных ограничений.

2. Повторите упражнение 1 для последней таблицы примера 3.4.1.

4.2.3. Оптимальное решение двойственной задачи

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

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

Обратная матрица в оптимуме прямой задачи

Метод 1

. ( Вектор-строка исходных

I Оптимальные значения)

ч коэффициентов целевой функции

двойственных -

при базисных переменных

переменных )

{ в оптимуме прямой задачи Элементы в вектор-строке исходных коэффициентов целевой функции должны быть перечислены в таком порядке, в каком базисные переменные перечислены встолбце Базис в симплекс-таблице. Этот метод рассмотрен в примере 4.2.1.

Метод 2

Оптимальное решение двойственной задачи можно получить из следующего уравнения.

Коэффициент при j-й 4 переменной в z-строке прямой задачи

Разность между левой и правой4 частями j-то неравенства двойственной задачи

Поскольку двойственной к двойственной задаче будет прямая задача (проверьте!), эти методы симметричны относительно прямой и двойственной задач. Их можно использовать для определения оптимального решения одной задачи непосредственно из симплекс-таблицы, содержащей оптимальное решение другой. Данное обстоятельство обусловливает возможность проведения вычислений именно по той задаче (прямой или двойственной), которая требует меньших вычислительных ресурсов (меньший объем вычислений имеет задача с меньшим количеством ограничений). После нахождения оптимального решения решаемой задачи оптимальное решение обратной задачи определяется одним из описанных методов (см. упражнение 4.2.3.1).

Пример 4.2.1

Рассмотрим следующую задачу ЛП.

Максимизировать z = Ьхх + 12х2 + 4х3

при ограничениях

х1 + 2х2+х3<10, 2хх -х2 + Зх3 = 8, хг,х2, х3>0.

Чтобы подготовить задачу к решению симплекс-методом, надо добавить дополнительную остаточную переменную xt в первое ограничение и искусственную переменную R во второе. В результате прямая задача и соответствующая ей двойственная будут определены следующим образом.

Прямая задача

Максимизировать г = 5xi +12хг + 4хз -MR при ограничениях

xi +2x2 + Хз + х4 = 10,

2х1-х2 + Зх3 + Я=8,

xiI *2, *3, Хд, Я> 0.

Двойственная задача

Минимизировать w= 10yi + 8уг при ограничениях yi + 2у2 > 5, 2у, -у2> 12, yi + Зу2 > 4,

yi > 0, уг > -М (уг - свободная переменная).

Г2/5 -1/54!

Обратная матрица симплекс-таблицы с оптимальным решением имеет вид I j .

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

Метод 1. Заметим, что базисные переменные в оптимальной симплекс-таблице в столбце Базис записаны в таком порядке, что сначала идет х2, а затем хх. Поэтому в вектор-строке первоначальных коэффициентов целевой функции коэффициенты этих двух переменных должны идти в том же порядке:

(вектор коэффициентов) = (коэффициент при х2, коэффициент при хг) = (12, 5).

Оптимальное решение двойственной задачи вычисляется так:

(2/5 -\/5\

(у у2) = (вектор коэффициентов) х (обратная матрица) = (12,5) =(29/5,-2/5).

V V 2/5 J

Метод 2. Поскольку двойственная задача имеет две переменные, необходимо два уравнения, чтобы найти их значения. Сначала посмотрим, как ограничения двойственной задачи связаны с переменными х4 и R, составляющими первоначальный базис прямой задачи.

Переменная х4: у,>0, Переменная R: у2 > -М. Из симплекс-таблицы с оптимальным решением имеем

коэффициент в z-строке при xt = 29/5, коэффициент в z-строке при R = -2/5 + М. Теперь, следуя методу 2, получаем систему уравнений 29/5 = у,-0 => у, = 29/5,

-2/5+М = у2-(-М) у2 = -2/5.

В следующей таблице представлены симплекс-итерации решения прямой задачи.