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

Решить задачу ЛП двойственным симплекс-методом:

Приводим задачу к каноническому виду:

Знаки в ограничениях заменили противоположными для того, чтобы переменные и можно было взять в качестве базисных. Симплексная таблица имеет вид

  b
L -1 -1
-2 -1 -1
-1 -2 -1

 

Таблица двойственно-допустимая, но не оптимальная. Выбираем ведущую строку – это строка переменной , ведущий столбец – это столбец переменной . После преобразования таблица принимает вид

  b
L -1 -1
-1 -1
-3 -3

 

Так как в столбце b есть отрицательная переменная , то эту строку выбираем ведущей, а столбец переменной будет ведущим столбцом. После преобразования получаем таблицу:

 

 

  b
L -1/3 -1 -1/3
1/3 -1 -2/3
-1/3 -1/3

 

которая является оптимальной. Соответствующее оптимальное решение имеет вид .

 

Двойственность в ЛП

Постановка задачи

Рассмотрим пару задач ЛП вида:

(I) (II)

… …

… …

… …

… …

.

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








Дата добавления: 2017-09-19; просмотров: 559;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.