Пример решения задачи двойственным симплекс-методом
Решить задачу ЛП двойственным симплекс-методом:
Приводим задачу к каноническому виду:
Знаки в ограничениях заменили противоположными для того, чтобы переменные 
и 
можно было взять в качестве базисных. Симплексная таблица имеет вид
| 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; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!