Линейное программирование

информатики и информационных таможенных технологий
Ростов- на -Дону
2014г.
Часть II
Автор: М.М.

Цвиль, доцент, кандидат физико-математических наук, доцент

задаче ЛП (исходной) можно поставить в соответствие другую, которая называется

двойственной или сопряжённой. Они образуют пару двойственных ( или сопряжённых ) задач ЛП .
Составим двойственную к задаче использования сырья (1.2).
Имеется m видов сырья в количестве , которые используются для изготовления n видов продукции. Известно: расход i-го вида сырья на единицу j-й продукции; Cj прибыль от реализации единицы j-го вида продукции. Составить план выпуска продукции, обеспечивающий максимальную прибыль. Математическая модель данной задачи имеет вид (в матричной форме):

(2.1.1)

том, что:
коэффициенты целевой функции исходной задачи являются свободными

членами системы ограничений двойственной задачи,
свободные члены системы ограничений исходной задачи служат коэффициентами целевой функции двойственной задачи,
матрица коэффициентов системы ограничений двойственной задачи является транспонированной матрицей коэффициентов системы ограничений исходной задачи.

задачи свободные члены должны находиться в правой части, а члены

с неизвестными – в левой.

Правило 2. Ограничения-неравенства исходной задачи должны быть записаны так, чтобы знаки неравенств у них были направлены в одну сторону.

Правило 3. Если знаки неравенств в ограничениях исходной задачи « ≤ », то целевая функция Z (X) → max , а если « ≥», то Z (X) → min .

Правило 4. Каждому ограничению исходной задачи соответствует не-известное в двойственной задаче, при этом неизвестное, отвечающее ограничению-неравенству, должно удовлетворять условию неотрицательности, а неизвестное, отвечающее ограничению-равенству, может быть любого знака.

функция F (Y) должна оптимизироваться противоположным по сравнению с Z

(X) образом.

двойственности. Теоремы двойственности позволяют установить взаимосвязь между оптимальными решениями пары

двойственных задач. Решив одну из пары двойственных задач, можно или найти оптимальное решение другой задачи, не решая ее, или установить его отсутствие. Возможны следующие случаи:
- обе задачи из пары двойственных имеют оптимальные решения;
- одна из задач не имеет решения в виду неограниченности целевой функции, а другая не имеет решения ввиду несовместности системы ограничений.

2.2. Одновременное решение прямой
и двойственной задач

Теорема 2.2.1 (1-я теорема двойственности). Если одна из задач взаимно двойственной пары разрешима, то разрешима и другая задача, при этом оптимальные значения целевых функций совпадают. Если целевая функция одной из задач не ограничена (сверху – для задачи максимизации, снизу – для задачи минимизации), то множество допустимых планов другой задачи пусто.

двойственных задач

модель