РЕШЕНИЕ ДВОЙСТВЕННЫХ ЗАДАЧ И ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯЦель: научиться составлять и решать двойственные ЗЛП. Используя теорию двойственности, научиться методам анализа экономических задач. Получить навыки решения задач нелинейного программирования на ЭВМ. Рассмотрим решение прямой и двойственной задач на примере задачи определения оптимального ассортимента продукции. ПРИМЕР 3.1. Предприятие выпускает 2 вида продукции А и В, затрачивая на это три вида ресурсов: Труд, Сырье и Оборудование. Прочие условия приведены в таблице:
Составить прямую и двойственную задачу, провести анализ решения. Пусть x 1 - количество продукции А, x 2 - количество продукции В. Математическая модель прямой ЗЛП имеет вид: x 1 ≥ 0, x 2 ≥ 0, 2 x 1 + 4 x 2 ≤ 2000; 4 x 1 +x 2 ≤ 1400; 2 x 1 +x 2 ≤ 800; 40 x 1 + 60 x 2 → max. После решения задачи (решите ее самостоятельно на ЭВМ) получаемоптимальные значения переменных x 1 = 200, x 2 = 400, целевая функция при этом равна 32000. Таким образом, рационально выпускать 200 единиц продукции А и 400 единиц продукции В, при этом суммарная прибыль составит 32000. Составляем двойственную задачу. Введем переменные y 1, y 2, y 3, которые назовем двойственными оценками ресурсов Труд, Сырье и Оборудование соответственно. Они имеют смысл предельных стоимостей единицы каждого вида сырья в случае, если предприятие решит реализовать его вместо готовой продукции. Тогда математическая модель двойственной задачи есть: y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0, 4 y 1+ y 2+ y 3≥ 60; 2 y 1+4 y 2 +2 y 3 ≥ 40; 2000 y 1+ 1400 y 2+ 800 y 3→ min; Решив данную ЗЛП на ЭВМ (проделать это самостоятельно, перейдя на новыйлист электронной таблицы Excel), получаем результаты y 1 = 13.3333, y 2 = 0, y 3 = 6.6666. Целевая функция, как и должно быть, совпадает с оптимальным значением прямой ЗЛП и составляет 32000. Оптимальные значения переменных также позволяют определитьоценки ценности ресурсов. Дефицитный ресурс, полностью используемый в оптимальном плане, имеет положительную ценность. Недефицитный ресурс имеет нулевую ценность, в нашем примере это Сырье, т.к. y 2 = 0. В результате производства недефицитные ресурсы остаются, а дефицитные вырабатываются полностью. Среди дефицитных ресурсов более ценным является тот, у которого двойственная оценка выше. В нашем примере Труд дефицитнее, чем Оборудование, т.к. y 1 = 13.3333> y 3 = 6.6666. Двойственные оценки также позволяют определять целесообразность включения в ассортимент новых видов продукции. Для решения этой задачи нужно рассчитать сумму произведений затратпроизводственных ресурсов ai на их двойственные оценки S=
Для изделия E: S = 13.3333*6+0*2 +6.6666*3 = 100, C = 80, S > C, следовательно, продукцию С выпускать не выгодно. Для изделия D: S = 13.3333*4+0*1 +6.6666*1 = 60, C = 70, S < C, следовательно, продукцию D выпускать выгодно. Задание 3.1. Предприятие выпускает три вида продукции А, В и С. Для выпуска затрачиваются ресурсы: Труд, Сырье и Энергия. Остальные характеристики приведены в таблице:
Значение неизвестного параметра а взять равным номеру варианта. Составить и решить прямую и двойственную задачи, провести анализ решения. Проанализировать ценности ресурсов. Определить, целесообразно ли включать в план продукцию четвертого вида, если цена единицы этой продукции составляет 70 у.е., а на ее производство расходуется по 2 ед. ресурсов каждого вида. Отчет должен содержать математическую модель прямойзадачи, полученные на ЭВМ из ее решения значения переменных и целевой функции, математическую модель двойственной задачи, оптимальные значения ее переменных и значение целевой функции. Сделать выводы: 1) сколько продукции каждого вида следует выпускать и чему при этом будет равна прибыль; 2) какая оценка ценности каждого ресурса, какие ресурсы дефицитные, а какие нет; 3) какие общие затраты на производство продукции четвертого вида и целесообразно ли планировать ее выпуск.
Рассмотрим теперь методы решения задач нелинейного программирования на ЭВМ. Такие задачи могут содержать как внутри целевой функции, так и внутри ограничений нелинейные выражения относительно неизвестных переменных. Для решения нелинейных задач также используют надстройку «Поиск решения». Методы численного решения нелинейных задач почти ни чем не отличаются от методов решения ЗЛП, единственное отличие в том, что при вводе целевой функции и ограничений в ячейках электронной таблицы могут использоваться нелинейные функции. ПРИМЕР 3.2. Найти максимум функции Z = 3 при ограничениях 4 x 1 + 3 x 2 + 2 x 3 ≤ 8; x 1, 2, 3 -целые, положительные. Вводим на отдельном листе в ячейки А1-С1 произвольныезначения, например единицы. В ячейку А2 вводим целевую функцию«=3*A1*A1–4*B1+3*C1*C1*C1» (кавычки не вводить), в ячейку А3вводим левую часть основного ограничения «=4*A1+3*B1+2*C1».Выбираем «Сервис/Поиск решения». Ссылка на целевуюячейку – А2, стремится к максимуму. Изменяемыеячейки– А1-С1. Ограничения: $А$3≤ 8; $A$1: $C$1≥ 0; $A$1: $C$1 – целое (int) (см. рис.3.1).
Рисунок 3.1 Окно «Поиск решения» примера 3.2 Нажимаем «Выполнить», получаем оптимальное решение x 1 = 0; x 2 = 0; x 3 = 4.Целевая функция при этом равна Z * = 192. Результаты решения на рис.3.2 (курсор в ячейке А2).
Рисунок 3.2 Решение примера 3.2 Задание 3.2. Найти условные экстремумы целевой функции Z, при заданных ограничениях: а) б) в) Z= x 1 x 2 → max; Z=
Значение неизвестного параметра а взять равным номеру варианта. Отчет должен содержать найденные на ЭВМ оптимальныезначения переменных и целевой функции.
|
. Эта сумма имеет смысл общих затрат на производство, ее сравнивают с прибылью С, полученной от реализации единицы этойпродукции. Если S > C, то данную продукцию производить не выгодно. Например, предприятие планирует выпускать еще два изделия E и D. Затраты ресурсов и прибыль для них следующие:
– 4 
+ 3 
,
+ 
→ max; Z= а x 1 +x 2 → min;
= a, x 1 + а x 2 =2, x 1, x 2 ≥ 0, 1/ x 1 + 1/ x 2=1.
