Пример решения задачи двойственным симплекс-методом
Решить задачу ЛП двойственным симплекс-методом:
Приводим задачу к каноническому виду:
Знаки в ограничениях заменили противоположными для того, чтобы переменные и можно было взять в качестве базисных. Симплексная таблица имеет вид
b | ||||
L | 0 | -1 | -1 | 0 |
-2 | -1 | 1 | -1 | |
-1 | -2 | -1 | 1 |
Таблица двойственно-допустимая, но не оптимальная. Выбираем ведущую строку – это строка переменной , ведущий столбец – это столбец переменной . После преобразования таблица принимает вид
b | ||||
L | 0 | -1 | -1 | 0 |
2 | 1 | -1 | -1 | |
-3 | -3 | 0 | 1 |
Так как в столбце b есть отрицательная переменная , то эту строку выбираем ведущей, а столбец переменной будет ведущим столбцом. После преобразования получаем таблицу:
b | ||||
L | 1 | -1/3 | -1 | -1/3 |
1 | 1/3 | -1 | -2/3 | |
1 | -1/3 | 0 | -1/3 |
которая является оптимальной. Соответствующее оптимальное решение имеет вид .
Двойственность в ЛП
Постановка задачи
Рассмотрим пару задач ЛП вида:
(I) (II)
… …
… …
… …
… …
Задачу (I) называют прямой задачей ЛП, а (II) – двойственной. Неравенства задач (I) и (II), соответствующие друг другу (по стрелке), называются сопряженными. Заметим, что задача двойственная к (II), есть исходная прямая задача, т. е. соотношение двойственности взаимное. Поэтому можно из такой пары задач любую считать прямой, а другую – двойственной.
|
|
Пример построения двойственной задачи
Построить двойственную задачу к следующей задаче ЛП:
Прежде чем приступать к построению двойственной задачи, необходимо упорядочить запись исходной: согласовать знаки неравенств в ограничениях задачи с целевой функцией. Так как ЦФ минимизируется, то неравенства должны быть записаны с помощью знака « ». Для этого второе неравенство умножим на -1:
Теперь, вводя двойственные переменные , запишем в соответствии с указанным правилом пару двойственных задач:
Задача слева – исходная прямая задача, задача справа – двойственная к исходной задаче.
Теоремы двойственности
Двойственность является одним из фундаментальных понятий в теории ЛП. Исключительно важную роль играют следующие утверждения, получившие названия теорем двойственности [1,3].
Первая теорема двойственности. Если одна из пары двойственных задач (I) и (II) разрешима, то разрешима и другая задача, причем оптимальные значения целевых функций прямой и двойственной задач совпадают:
|
|
где – оптимальные планы задач (I) и (II) соответственно.
Говорят, что допустимые решения x, y удовлетворяют условиям дополняющей нежесткости (УДН), если при подстановке этих векторов в ограничения задач (I) и (II) хотя бы одно из любой пары сопряженных неравенств обращается в равенство.
Вторая теорема двойственности. оптимальны в задачах (I) и (II) тогда и только тогда, когда они удовлетворяют УДН.
Дата добавления: 2021-12-10; просмотров: 25; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!