РЕШЕНИЕ ДВОЙСТВЕННЫХ ЗАДАЧ И ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Рассмотрим решение прямой и двойственной задач на примере задачи определения оптимального ассортимента продукции.
ПРИМЕР 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,
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= . Эта сумма имеет смысл общих затрат на производство, ее сравнивают с прибылью С, полученной от реализации единицы этой продукции. Если S > C, то данную продукцию производить не выгодно. Например, предприятие планирует выпускать еще два изделия E и D. Затраты ресурсов и прибыль для них следующие:
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 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= + → 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.
Значение неизвестного параметра а взять равным номеру варианта.
Отчет должен содержать найденные на ЭВМ оптимальные значения переменных и целевой функции.
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Двойственность в нелинейном программировании
Рассмотримнекоторые фундаментальные моменты теории нелинейного программирования. Исходной точкой для них является распространение метода Лагранжа для решения ЗИП с ограничениями в форме неравенств:
где X — некоторая область в пространстве .
Определим для задачи (28) функцию Лагранжа:
Определение.Пара векторов называется седловой точкойфункции некоторой области , если для любых
Неравенства (30) также называют неравенствами седловой точки.
В качестве примера седловой точки может быть приведена точка для функции определенной на множестве Действительно, а для любых и выполняются неравенства и .
На Рис. 2.7изображен график функции (гиперболический параболоид), и, как видно, в окрестности точки он действительно по форме напоминает седло, чем и объясняется происхождение соответствующего термина.
Теорема Куна-Таккера.Центральное место в теории нелинейного программирования занимает теорема Куна — Таккера, которая связывает решение ЗНП с наличием седловой точки у соответствующей функции Лагранжа.
Теорема 2.3.(Достаточное условие экстремума).Если — седловая точка функции Лагранжа, в области , , mo является оптимальным планом задачи (28), причем справедливо так называемое правило дополняющей нежесткости
По определению седловой точки имеем
при всех Из второго неравенства в (32) следует, что
Однако (33) может иметь место только тогда, когда при всех . Действительно, если существует такое k, что , то, положив для всех и выбрав достаточно большое , можно добиться того, что значение
окажется больше постоянного выражения
Из того, что для всех выполняются неравенства следует, что является допустимым планом задачи (28).
Если в левую часть неравенства (33) подставить значения .то получим, что
С другой стороны из того что, и , следует оценка
Совместное рассмотрение последних двух неравенств приводит к правилу дополняющей нежесткости в точке :
Тогда на основании левой части неравенства седловой точки (32) имеем, что для всех (в том числе и для )
По условию ЗИП для любых верны неравенства , что, в сочетании с условием , позволяет записать
Окончательно получаем, что для любых справедливо соотношение , т.е. — оптимальный план задачи (28).
Утверждение, обратное теореме (3), т. е. необходимое условие экстремума в ЗНП, оказывается верным только при выполнении дополнительных условий, которым должна удовлетворять задача (28). Важнейшим из них является так называемое условие регулярности Слейтера:
Говорят, что функция , задающая ограничение в задаче (28), удовлетворяет условию регулярности Слейтера, если существует такая точка , принадлежащая области допустимых, планов D, что
т. е. является внутренней точкой относительно ограничения . Поэтому данное условие также называют условием телесности.
Вообще говоря, существуют разные варианты необходимого условия Куна-Таккера. Приведем один из них.
Теорема 2.4.(Необходимое условие наличия экстремума) Если является задачей выпуклого программирования с решением , ее целевая функция и функции ограничений — дифференцируемы, нелинейные ограничения в форме неравенств удовлетворяют условию регулярности Слейтера, то существует такой вектор , что — седловая точка функции Лагранжа
Значение теоремы Куна-Таккера состоит в том, что она позволяет связать процесс решения оптимизационной задачи с поиском седловых точек функции Лагранжа, т. е., грубо говоря, с максимизацией этой функции по х и минимизацией по и.
Определим какфункцию, ставящую в соответствие каждому значению х минимальное значение функции по и:
Рассмотрим задачу отыскания максимума функции
Отсюда следует, что максимум находится в допустимой области D и совпадает с максимумом целевой функции задачи (28):
Таким образом, задача (34), в определенном смысле, равносильна (28). Аналогичные выводы могут быть получены и для (35). Задачи (34) и (35) образуют двойственную пару. Очевидно, данное отношение является обобщением отношения двойственности для задач линейного программирования. Соответственно, при определенных условиях пара двойственных задач нелинейного программирования обладает свойствами, аналогичными свойствам двойственных линейных задач. В частности, при любых
Условие (36) находит широкое применение при построении оценок в итеративных методах решения оптимизационных задач. Например, если имеется возможность приблизительно решить прямую и двойственную задачи и получить последовательности приближений и , то с помощью неравенств вида
можно определить момент остановки вычислительной процедуры.
В заключение отметим, что возможен вариант вывода выражений для целевых функций и ограничений пары двойственных задач линейного программирования из общего определения отношения двойственности для нелинейных задач. Также отметим, что в процессе формирования нелинейных двойственных задач существует большая неоднозначность: их вид можно варьировать, включая в множество X часть ограничений .
Дата добавления: 2017-04-05 ; просмотров: 1554 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ