2. Тема: «Теория двойственности в анализе оптимальных решений и задачи целочисленного программирования»

0. Пример решения двойственной задачи при помощи инструмента «Поиск решения» в Ms Excel

Сформулируем двойственную задачу к задаче, рассмотренной в первой части методической разработки (задача о коврах).

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

Y₁ – двойственная оценка ресурса «труд», или «теневая цена» труда;

Y2 – двойственная оценка ресурса «сырье»;

Y3 – двойственная оценка ресурса «оборудование», или «цена» оборудования.

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

g (Y) = 80Y₁+480Y₂ + 130 Y₃  min (2.1.1)

В ходе решения двойственной задачи необходимо найти такие «цены» на ресурсы (Y_i), чтобы общая стоимость использования ресурсов была минимальной.

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

Левая часть ограничения определяет стоимость ресурсов, затраченных на производство единицы продукции. Каждое ограничение соответствует определенному виду продукции. Знак ограничения меняется на противоположный. В результате получаем следующую систему ограничений двойственной задачи:

7 *Y₁+5*Y₂+2*Y₃  3 (2.1.2)

2*Y₁+8*Y₂+4*Y₃  4

2*Y₁+4*Y₂+Y₃  3

6*Y₁+3*Y₂+8*Y₃  1

Y₁, Y₂,Y₃  0

Одним из самых простых способов нахождения решения двойственной задачи является выбор типа отчета «Устойчивость» в диалоговом окне «Результаты поиска решения» (см. рис.1.1.6). Поэтому можно повторно запустить «Поиск решения» и выбрать данный тип отчета, который будет содержать решение двойственной задачи. Содержание отчета по устойчивости приведено на рис. 2.1.1.

Рис. 2.1.1. Отчет по устойчивости

Решение двойственной задачи в отчете по устойчивости указано только для дефицитных ресурсов и присутствует в столбце «теневая цена».

0. Задания для выполнения индивидуальной работы по теме «Теория двойственности в анализе оптимальных решений и задачи целочисленного программирования»

Требования по выполнению и оформлению индивидуального задания

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

Сформулировать по правилам двойственную к ней задачу и записать модель двойственной задачи в формализованном виде.

Найти решение двойственной задачи, используя инструмент «Поиск решения» и сформировать отчет «по устойчивости», который содержит решение двойственной задачи.

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

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

Третье задание контрольной работы