Теория двойственности

Контроль знаний

1. Как построить первоначальный опорный план задачи линейного программирования и проверить его на оптимальность?

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

3. Как определяется вектор для включения в базис, если первоначальный план не является оптимальным?

4. Как определить вектор подлежащий исключению из базиса? 5. Какой элемент называется генеральным?

6. Какой метод решения систем линейных уравнений лежит в основе симплекс-метода? 7. Зачем в системе ограничений необходим единичный базис.

8. Какую простейшую геометрическую интерпретацию можно дать симплекс-методу?

Лабораторная работа № 4

Тема: МодельоптимальногораспределенияресурсовЦельработы:

ƒ освоить построение пар симметричных двойственных задач;

ƒ решить исходную задачу и найти результаты для двойственной задачи; ƒ выполнить анализ результатов с последующей корректировкой модели.

Времяработы: 4 часа

Задание

1. Провести моделирование в соответствии с исходными данными;

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

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

1. направление экстремума целевой функции двойственной задачи противоположно на-правлению экстремума исходной задачи;

{ }

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

AT = aji;

3. число переменных yi в двойственной задаче равно числу ограничений исходной задачи, и наоборот;

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

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

Управляемые переменные для пары двойственных задач могут быть интерпретиро-ваны следующим образом:

1. Переменные исходной задачи:

– основные переменные xj – количество производимой продукции j -го вида;

– дополнительные переменные xi +1 – остатки неизрасходованного i -го ресурса. 2. Переменные двойственной задачи:

– основные переменные yi интерпретируются следующим образом: а. предельная цена единицы i -го ресурса;

б. дефицитность (теневая цена) i -го ресурса. Теневая цена – это дополнительная прибыль, которая может быть получена от привлечения в производство еди-ницы дефицитного i -го ресурса (при условии наличия остатков других ресур-сов);

– дополнительная переменная vj – редуцированная (нормированная) стоимость еди-ницы продукции j -го вида. Редуцированная стоимость показывает размер потерь от выпуска единицы нерентабельной продукции.

Дата добавления: 2014-11-25