Обратная матрица в оптимуме прямой задачи
Метод 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, уг > -М (уг - свободная переменная).
Итерация | Базис | | | | | | | Решение |
| | -5-2М | -12 + М | -4-ЗМ | | | | |
| | | | | | | | |
| | | | | | | | |
| | -7/3 | -40/3 | | | 43 + М | | 32/3 |
| | | | | | -1/3 | | 22/3 |
| | | -1/3 | | | | | |
| | -3/7 | | | 40 7 | -43 + М | | 368/7 |
| | | | | | -1/7 | | 22/7 |
| | | | | | | | 26/7 |
| | | | | | -2/5 + М | | 274/5 |
| | | | -1/5 | | -1/5 | | 12/5 |
| | | | | | | | 26/5 |
Г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.
В следующей таблице представлены симплекс-итерации решения прямой задачи.
Отметим, что каждое уравнение включает только одну неизвестную, поэтому решение двойственной задачи существует всегда и находится легко. Так бывает всегда, когда ограничения двойственной задачи связаны с начальными базисными переменными.
Конечно же, ничего не мешает использовать другие переменные при построении уравнений, необходимых для определения значений переменных двойственной задачи. Например, ограничения, ассоциируемые с переменными хх и х3, порождают следующие уравнения (проверьте!):
у, + 2у2-5 = 0, у, + Зу2-4=.
Решение этой системы уравнений также приводит к оптимальным значениям двойственной задачи у, = 29/5 и у2 = -2/5. Однако эти уравнения уже не так просты, как уравнения, ассоциируемые с переменными xt и R. (Убедитесь самостоятельно, что уравнения, ассоциированные с любыми двумя переменными из множества xv х2, х3, xt, R, дают одни и те же значения переменных двойственной задачи.)
УПРАЖНЕНИЯ 4.2.3
1. С помощью программы TORA решите двойственную к следующей задачу ЛП и затем найдите оптимальное решение прямой задачи.
Минимизировать z = 5х, + 6х2 + Зх3
при ограничениях
5*, + Ьх2 + Зх3 > 50, х, + хг - хг > 20, 7х, + 6х2 - 9х, > 30, 5х,+ 5х2 + 5х3>35, 2х, + 4х2- 15х3>10,
12х,+ юх2>90,
х2 - 10х3 > 20, х„ хг, х3>0.
2. Дана следующая задача линейного программирования.
Максимизировать z = Ьхх + 2хг + Зх3
при ограничениях
х,+ 5х2 + 2Хз = 30, х, - 5х2 - 6х3 < 40, х„ х2, х3>0.
Оптимальное решение этой задачи удовлетворяет уравнению (получено из z-строки симплекс-таблицы)
z + 0х, + 23х2 + 7х3 + (5 + M)xt + 0х5 = 150,
где искусственная переменная х4 и дополнительная переменная х6 входили в начальное базисное решение. Запишите соответственную двойственную задачу и найдите ее оптимальное решение, исходя из приведенного уравнения.