Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Прямая задача | Двойственная задача |
не ограничен в знаке |
Теорема 1. Пусть – планы соответственно прямой и двойственной ЗЛП, тогда:
. | (4.12) |
Теорема 2. Пусть – планы соответственно прямой и двойственной ЗЛП и , тогда – решения соответственно прямой и двойственной задач.
Теорема 3. Если прямая (двойственная) ЗЛП имеет конечное решение, то и двойственная (прямая) ЗЛП имеет решение, причем
(4.13)
Если прямая (двойственная) ЗЛП не имеет решения, то и двойственная (прямая) ЗЛП не имеет решения.
Теорема 4. Планы соответственно прямой и двойственной ЗЛП являются оптимальными тогда и только тогда, когда:
(4.14)
Условия (4.14) называются условиями дополнительнойнежесткости.
Примечание 1. Для основной ЗЛП и двойственной к ней ЗЛП условия нежесткости имеют вид:
(4.15)
Примечание 2. Если прямая ЗЛП записана не в канонической форме, то условия дополнительной нежесткости для этой ЗЛП и двойственной к ней ЗЛП могут быть записаны в следующем виде:
если хj* > 0, то
если то yi* = 0,
если yi* > 0, то
если , то хj* = 0. (4.16)
Получение оптимального плана двойственной задачи на основании теоремы 4
Пример 4.5. Рассмотрим задачу:
(4.17)
Ее решение . Найдем решение задачи, двойственной к (4.17), используя теорему 4. Запишем двойственную к (4.17) задачу:
(4.18)
Применяем соотношение (4.16). Так как х1* = 3/2 > 0, то 3у1* + 4у2* + у3* = 2. Далее, так как 3х1* + х2* = 9/2 + 0 > 3, то у1* = 0, и так как х1* + 2х2* = 3/2 + 0 < 3, то у3* = 0. В итоге имеем:
3у1* + 4у2* + у3* = 2, у1* = у3* = 0,
т.е. вектор является решением задачи (2.18) наосновании теоремы 4. Вычислим , что соответствует утверждению теоремы 3.
Пример 4.6. Найти решение прямой и двойственной задач.
Прямая задача | Двойственная задача | |
max = 5Х1 + 12Х2 + 4Х3 Х1 + 2Х2 +Х3 ≤ 10 2Х1 – Х2 + 3Х3 = 8 Х2,3 ≥ 0 Х 1 не ограничена в знаке | min = 10Y1 + 8Y2 Y1 +2Y2 = 5 2Y1 – Y2 ≥ 12 Y1 + 3Y2 ≥ 4 Y1 ≥ 0 У 2 не ограничена в знаке | (а) (б) (в) (г) |
Двойственная задача содержит две переменные, т.е. ее можно решать графически (рис. 4.1).
Рис. 4.1
Как видно из рис. 4.1, область допустимых решений – планов двойственной ЗЛП – Q представляет собой отрезок АВ, лежащий на прямой Y1 + 2Y2 = 5, так как первое ограничение задается в виде равенства. Передвигая линию уровня функции 10Y1 + 8Y2 = const в направлении, противоположном вектору = (10; 8), получаем точку А, в которой достигается минимум функции . Находим координаты точки А, которая является пересечением двух прямых:
Y1 + 2 Y2 = 5,
2 Y1 – Y2 = 12,
откуда
= 29/5; = -2/5 и = 54 .
Ипользуя теорему 4, находим решение исходной задачи. Так как > 0 и < 0, то оба ограничения прямой задачи имеют вид строгих равенств.
Х1 + 2Х2 + 3Х3 = 10;
2Х1 – Х2 + 3Х3 = 8. (4.19)
Так как третье ограничение двойственной задачи выполняется в виде строгого неравенства (29/5 – 6/5 = 24/5 > 4), то = 0. Решая систему (4.19), получаем:
= 26/5; = 12/5; = 0; f() = 54,8.
Получение оптимального решения двойственной задачи из симплекс-таблицы решения прямой задачи
Пусть прямая задача имеет вид основной ЗЛП
(2.20)
Двойственная к ней ЗЛП имеет вид
;
. (4.21)
Предположим, что ЗЛП (4.20) имеет решение. Решения обеих задач могут быть записаны в виде:
= ; = ,
где = = (, …, )
матрица, обратная для базисной подматрицы . Матрица подматрицы расположена на месте единичной подматрицы в исходной матрице .
Кроме того, можно показать, что
, , (4.22)
откуда следует, что i-я компонента решения двойственной ЗЛП есть (n + i)-я симплекс-разность матрицы , определяющей оптимальный план исходной ЗЛП, а j-я симплекс-разность матрицы () равна разности между левой и правой частями ограничений двойственной ЗЛП:
= . (4.23)
Пример 4.7. Решить следующую ЗЛП:
max (4Х1 + Х2 + 2Х3 + 3Х4);
Х1 +2Х2 + 3Х3 – Х5 + Х7 = 50;
–3Х2 +Х3 + Х4 +2Х5 + 4Х7 = 10;
4Х2 + Х5 + Х6 – 1/2 Х7 = 24;
. (4.24)
Найти решение задачи, двойственной к ЗЛП (4.24).
Так как расширенная матрица
=
системы линейных уравнений (4.24) является К-матрицей, то ЗЛП (4.24) можно решить симплекс-методом. Результаты решенияприведены в таблице:
–3 | –1 | –1/2 | – | |||||||
= 230 | –2 | |||||||||
–3/2 11/4 1/4 | –1/2 3/4 1/4 | 5/4 29/8 –1/8 | ||||||||
= 242 | 5/2 | 1/2 | 63/4 |
На первой итерации получен оптимальный план ЗЛП (4.24).
= (1, 4, 2); = (38, 28, 6),
= (38, 6, 0, 28, 0, 0, 0); f () = 242.
Запишем задачу, двойственную к (2.24):
min(50Y1 + 10Y2 +24Y3); Y1 ≥ 4; 2Y1 – 3Y2 + 4Y3 ≥ 1; 3Y1 + Y2 + ≥ 2. | (4.25) |
Y2 ≥ 3; –Y1 +2Y2 + Y3 ≥ 0; Y3 ≥ 0; Y1 + 4Y2 – 1/2 Y3 ≥ 0. | (4.26) |
не ограничены в знаке. | (4.27) |
Ограничения (4.27) являются избыточными, следовательно, их можно отбросить.
Находим решение ЗЛП (2.25) по формуле
= = (4, 3, 1) = (4, 3, 1/2)
или (4.22):
= (0 + 4, 0 + 3, + 0) = (4, 3, );
= 50´4 + 10´3 + 24 ´ = 242.
Дата публикования: 2015-10-09; Прочитано: 524 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!