Двойственная задача линейного программирования как решать

Двойственная задача линейного программирования

Теорема Если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет решение, причем для экстремальных значений целевых функций обоих задач выполняется соотношение: maxИсходной =minДвойственной и наоборот.

Следствие. Если целевая функция одной из задач не ограничена, то другая задача решения не имеет.

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

Существуют симметричные и несимметричные пары задач. В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а двойственной – в виде неравенств, причем в последней переменные могут быть и отрицательными.

В симметричных двойственных задачах системы ограничений обоих задач задаются неравенствами, причем на двойственные переменные налагается условие неотрицательности.

При построении двойственной задачи используют следующие правила:

Ø число переменных двойственной задачи должно быть равно числу основных ограничений исходной;

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

Ø вид экстремума двойственной задачи противоположен экстремуму исходной;

Ø матрица основных ограничений двойственной задачи получается транспортированием аналогичной матрицы исходной задачи;

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

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

По условиям дана следующая математическая модель исходной задачи:

Приведем ее к каноническому виду через ввод дополнительных переменных.

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

Решаем исходную задачу двойственным симплекс-методом. Для получения базиса следует умножить третье уравнение из системы ограничений на (-1).

Переменные у4. у5. у6 составляют базис. Можно составить исходную симплекс-таблицу.

Двойственная задача имеет следующий результат:

Вопросы для самопроверки

1. Отличие линейного программирования от линейной алгебры.

2. Что такое область допустимых решений задачи линейного программирования.

3. Как находить оптимальное решение задачи с минимумом или максимумом целевой функции.

4. В чем достоинства и недостатки графического решения задачи линейного программирования.

5. Постановка задачи выбора оптимального промыслово-технологического режима работы добывающего судна.

6. Получение первой симплекс-матрицы задачи линейного программирования.

7. Правила преобразования симплекс-матриц при итеративном процессе.

8. Использование результатов преобразования симплекс-матриц.

9. Понятие о двойственной задаче линейного программирования.

© studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам. Ваш ip: 212.92.234.204



двойственная задача линейного программирования как решать:Двойственная задача линейного программирования Теорема Если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет решение, причем для экстремальных значений целевых