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


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

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

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

  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), есть исходная прямая задача, т. е. соотношение двойственности взаимное. Поэтому можно из такой пары задач любую считать прямой, а другую – двойственной.



Дата добавления: 2020-10-01; просмотров: 414;


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

Воспользовавшись поиском можно найти нужную информацию на сайте.

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

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.011 сек.