На каждый день | Линейное программирование

ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Естественной формулировке прямой задачи (формула 5 - "Формулировка задач линейного программирования") соответствует двойственная задача с m+s переменными - по числу равенств и неравенств прямой задачи. Целесообразно эти переменные разделить на две группы u=(u₁, u₂, …, u_m)' - m-мерный вектор (по числу равенств) и v=(v₁, v₂, ..., v_s)' - s-мерный вектор (по числу неравенств прямой задачи). Целевой функцией двойственной задачи является линейная форма

Ограничения двойственной задачи следующие

Здесь переменные u_i(i=1, 2, ..., m) являются свободными, а переменные v_i≥0 (i=1, 2, …, s) - несвободными.

Если х* - оптимальный план прямой задачи, а u* и v* - оптимальный план двойственной задачи, то

НОРМАЛЬНОЙ ФОРМЕ ПРЯМОЙ ЗАДАЧИ соответствует двойственная задача, заключающаяся в определении минимума линейной формы

при ограничениях только в виде неравенств

несвободных переменных v≥0 (v_i≥0, i=1, 2, ..., s).

Здесь число неизвестных s равно числу неравенств в прямой задаче, а число ограничений - неравенств равно числу неизвестных в прямой задаче. Для оптимальных планов прямой и двойственной задач равенство целевых функций будет:

КАНОНИЧЕСКОЙ ФОРМЕ ПРЯМОЙ ЗАДАЧИ соответствует задача на минимум линейной формы

при ограничениях - неравенствах

и всех свободных переменных u_i(i=1, 2, ..., m).

Для оптимальных планов обеих задач равенство целевых функций

обсудить на форуме

объявления: стройка и ремонт

Поделитесь ссылкой в социальных сетях