Решение двойственных задач и задач нелинейного программирования

Цель: научиться составлять и решать двойственные ЗЛП.

Используя теорию двойственности, научиться методам анализа экономических задач. Получить навыки решения задач нелинейного программирования на ЭВМ.

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

ПРИМЕР 3.1. Предприятие выпускает 2 вида продукции А и В, затрачивая на это три вида ресурсов: Труд, Сырье и Оборудование.

Прочие условия приведены в таблице:

Ресурсы	Затраты ресурсов на ед. продукции	Наличие ресурсов
продукция А	продукция В
Труд
Сырье
Оборудование
Прибыль на ед. продукции

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

Пусть x ₁ - количество продукции А, x ₂ - количество продукции В. Математическая модель прямой ЗЛП имеет вид:

x ₁ ≥ 0, x ₂ ≥ 0,

2 x ₁ + 4 x ₂ ≤ 2000;

4 x ₁ + x ₂ ≤ 1400;

2 x ₁ + x ₂ ≤ 800;

40 x ₁ + 60 x ₂ → max.

После решения задачи (решите ее самостоятельно на ЭВМ) получаем оптимальные значения переменных x ₁ = 200, x ₂ = 400, целевая функция при этом равна 32000. Таким образом, рационально выпускать 200 единиц продукции А и 400 единиц продукции В, при этом суммарная прибыль составит 32000.

Составляем двойственную задачу. Введем переменные y ₁, y ₂, y ₃, которые назовем двойственными оценками ресурсов Труд, Сырье и Оборудование соответственно. Они имеют смысл предельных стоимостей единицы каждого вида сырья в случае, если предприятие решит реализовать его вместо готовой продукции. Тогда математическая модель двойственной задачи есть:

y ₁ ≥ 0, y ₂ ≥ 0, y ₃ ≥ 0,

4 y ₁+ y ₂+ y ₃≥60;

2 y ₁+4 y ₂ +2 y ₃ ≥40;

2000 y ₁+ 1400 y ₂+ 800 y ₃→ min;

Решив данную ЗЛП на ЭВМ (проделать это самостоятельно, перейдя на новый лист электронной таблицы Excel), получаем результаты

y ₁ = 13.3333, y ₂ = 0, y ₃ = 6.6666.

Целевая функция, как и должно быть, совпадает с оптимальным значением прямой ЗЛП и составляет 32000.

Оптимальные значения переменных также позволяют определить оценки ценности ресурсов. Дефицитный ресурс, полностью используемый в оптимальном плане, имеет положительную ценность. Недефицитный ресурс имеет нулевую ценность, в нашем примере это Сырье, т.к. y ₂ = 0.

В результате производства недефицитные ресурсы остаются, а дефицитные вырабатываются полностью. Среди дефицитных ресурсов более ценным является тот, у которого двойственная оценка выше. В нашем примере Труд дефицитнее, чем Оборудование, т.к. y ₁ = 13.3333> y ₃ = 6.6666. Двойственные оценки также позволяют определять целесообразность включения в ассортимент новых видов продукции.

Для решения этой задачи нужно рассчитать сумму произведений затрат производственных ресурсов a_i на их двойственные оценки S= . Эта сумма имеет смысл общих затрат на производство, ее сравнивают с прибылью С, полученной от реализации единицы этой продукции. Если S > C, то данную продукцию производить не выгодно. Например, предприятие планирует выпускать еще два изделия E и D. Затраты ресурсов и прибыль для них следующие:

Ресурс	Оценки ценности ресурсов	Затраты ресурсов ai
изделие E	изделие D
Труд	13.3333
Сырье
Оборудование	6.6666
Прибыль на одно изделие, С

Для изделия 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. Предприятие выпускает три вида продукции А, В и С. Для выпуска затрачиваются ресурсы: Труд, Сырье и Энергия.

Остальные характеристики приведены в таблице:

Тип ресурса	Нормы затрат на ед. продукции	Наличие ресурсов
А	В	С
Труд	a /15
Сырье				100+2 а
Энергия
Прибыль на ед. продукции	40+ а

Значение неизвестного параметра а взять равным номеру варианта.

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

Отчет должен содержать математическую модель прямой задачи, полученные на ЭВМ из ее решения значения переменных и целевой функции, математическую модель двойственной задачи, оптимальные значения ее переменных и значение целевой функции. Сделать выводы:

1) сколько продукции каждого вида следует выпускать и чему при этом будет равна прибыль;

2) какая оценка ценности каждого ресурса, какие ресурсы дефицитные, а какие нет;

3) какие общие затраты на производство продукции четвертого вида и целесообразно планировать ее выпуск.

 

Рассмотрим теперь методы решения задач нелинейного программирования на ЭВМ. Такие задачи могут содержать как внутри целевой функции, так и внутри ограничений нелинейные выражения относительно неизвестных переменных. Для решения нелинейных задач также используют надстройку «Поиск решения».

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

ПРИМЕР 3.2. Найти максимум функции Z = 3 – 4 + 3 ,

при ограничениях

4 x ₁ + 3 x ₂ + 2 x ₃ ≤ 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 ₁ = 0; x ₂ = 0; x ₃ = 4. Целевая функция при этом равна Z * = 192. Результаты решения на рис.3.2 (курсор в ячейке А2).

Рисунок 3.2 Решение примера 3.2

Задание 3.2. Найти условные экстремумы целевой функции Z,

при заданных ограничениях:

а) б) в)

Z= x ₁ x ₂ → max; Z= + → max; Z= а x ₁ +x ₂ → min;

+ = a, x ₁ + а x ₂ =2, x ₁ ,x ₂ ≥ 0, 1/ x ₁ + 1/ x ₂=1.

Значение неизвестного параметра а взять равным номеру варианта.

Отчет должен содержать найденные на ЭВМ оптимальные значения переменных и целевой функции.

Работа № 4