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

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

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

Теорема. Если — точка локального минимума дифференцируемой функции , то при ограничениях , удовлетворяющих некоторому условию регулярности, для функции Лагранжа

существует вектор множителей Лагранжа такой, что

Замечания. 1.Множители Лагранжа имеют произвольные знаки.

2. Если f и выпуклы, то необходимые условия (4.4.), (4.5.) являются и достаточными для существования решения задачи (4.1.), (4.2.).

3. Требование регулярности связано с существованием решения системы (4.4.), (4.5.).

Метод множителей Лагранжа позволяет отыскивать максимум или минимум функции при ограничениях–равенствах, т.е. в (4.1) все ограничения являются равенствами. Основная идея метода заключается в переходе от задачи на условный экстремум к задаче отыскания безусловного экстремума некоторой специально построенной функции Лагранжа.

Составим функцию Лагранжа следующего вида:

Для того чтобы вектор являлся решением задачи (4.6.), (4.7.) , необходимо существование такого вектора , чтобы пара векторов удовлетворяла системе уравнений:

Пример 11. В двух цехах предприятия нужно изготовить 20 изделий некоторой продукции. Затраты, связанные с изготовлением х₁ изделий в 1-м цехе, равны руб., а затраты при изготовлении х₂ изделий во 2-м цехе равны руб. Составить план производства изделий в двух цехах с минимальными затратами.

Решение. Математическая модель задачи:

Для данной точки получим в точке экстремума:

Исследуем характер функции f в окрестности точки , для этого находим

Так как и , то функция выпукла, и точка — точка минимума.

Ответ: Оптимальный план изделий.

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

Имеется задача нелинейного программирования с ограничениями-неравенствами:

Допустим, что функции и все , выпуклы по Х. Такая задача носит название выпуклого программирования и множество решений , определяемое условиями (4.9), является выпуклым. Для задачи (4.8), (4.9) справедлива теорема Куна-Таккера.

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

Последнее условие называется условием дополняющей нежесткости.

Если функции и — выпуклы по Х, то условия оптимальности (4.10), (4.11) будут не только необходимыми, но и достаточными. В этом случае условие существования решения Х и , удовлетворяющего (4.10), (4.11), которое называют условием регулярности, примет вид

Пользуясь теоремой Куна-Таккера, задачу нелинейного программирования решают следующим образом.

Шаг 1. Составляют функцию Лагранжа

Шаг 2. Составляют систему уравнений вида (4.10), (4.11).

Шаг 3. Находят ее решение . В отличие от задачи с ограничениями-равенствами вектор должен в этом случае удовлетворять условию неотрицательности.

Часто в задачах исследования операций приходится решать задачи, в которых переменные , должны удовлетворять условию .

Основные положения теории могут быть легко распространены на этот случай. Тогда к ограничению (4.9) следует добавить следующее ограничение:

Это ограничение в общем виде можно записать как

Задача представлена в каноническом виде. Применим к ней теорему Куна-Таккера, для чего составим функцию Лагранжа

где — множители, связанные с ограничениями (4.12). Условия теоремы Куна-Таккера выглядят так:

Последнее соотношение представляет собой условия дополняющей нежесткости для ограничений неотрицательности.

Теорема. Пусть задача нелинейного программирования имеет вид

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

Пример 12. Предприятие выпускает два вида изделий А и Б. Норма расхода на производство каждого вида изделий приведены в таблице. При этом известно, что сырья имеется 12 т, а оборудования — 30 станко-часов.

Источник

Графический метод решения задач нелинейного программирования

В задаче нелинейного программирования в общей ее постановке система ограничений определяет в n – мерном пространстве некоторую область, которая является областью допустимых решений задачи. Аналогично задачам ли­нейного программирования, задачи нелинейного программирования можно решать гра­фически, когда целевая функция и система ограничений содержат только две управляющие переменные, а ограничения представляют собой неравенства.

Решить задачу нелинейного программирования графически – значит найти точку области допустимых решений, через которую проходит линия наиболь­шего (наименьшего) уровня целевой функции: . Причем, в отличие от задачи линейного программи­рования, указанная точка может находиться как на границе, так и внутри области допустимых решений.

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

Шаг 1. На плоскости строят область допустимых реше­ний, опреде­ляемую ограничениями. Если она пуста, т.е. если ограни­чения несовместны, то задача не имеет решений. В противном случае переходят к шагу 2.

Шаг 2. Строят линию уровня целевой функции: , где C – неко­торая константа. Переходят к шагу 3.

Шаг 3. Определяют направление возрастания (при задаче на максимум) или убывания (при задаче на минимум) целевой функции посредством вычисле­ния координат и построения вектора градиента целевой функции.

Шаг 4. Находят точку области допустимых решений, через которую про­ходит линия уровня целевой функции с наибольшим (при решении задач на мак­симум), или наименьшим (при решении задач на минимум) значением конс­танты C, или устанавливают неограни­ченность целевой функции на области до­пустимых решений.

Шаг 5. Определяют значения координат для точки, найденной на шаге 4, а также значение целевой функции в этой точке, т.е. при найденных зна­чениях координат этой точки.

ПРИМЕР: Найдите графическим методом оптимальные решения задачи нелинейного программирования, заданной математической моделью вида:

В соответствии с алгоритмом построим на плоскости об­ласть допустимых решений. Ограничения выделяют первую чет­верть. Границей полуплоскости по первому ограничению является гипербола с уравнением: , причем неравенство ограничения выполняется для точек, лежащих выше этой гиперболы. Второй границей является окружность, точнее ее четвер­тая часть в первой четверти, с радиусом 3 и центром в начале координат. На рис. 5 область допустимых решений задачи выделена штрихов­кой.

Очевидно, что вектор градиента целевой функции определяется координа­тами: и, следовательно, направлен вправо вверх, как указано стрел­кой. Как известно, целевая функция возрастает в направлении вектора гра­диента и убывает в направлении вектора антиградиента, и, кроме того, любая линия уровня целевой функции перпендикулярна этому вектору. Поэтому мак­симум целевой функции достигается в точке В, а минимум – в точке А. И задача сводится к нахождению координат этих точек.

Заметим, что в точке В совпадают тангенсы углов наклона касательной к окружности и прямой – линии уровня целевой функции к оси , а также, что эти тангенсы численно равны производным этих функций (вычисленным в точке В). Для линии уровня угловой коэффициент (тангенс угла наклона) очевидно равен: , а для окружности угловой коэффициент касательной равен: , поэтому можно записать уравнение: . Если к этому уравнению добавить уравнение окружности, то получится система уравнений вида:

Решения системы и являются координатами точки В, и, следовательно, являются оптимальными решениями задачи на максимум целевой функции, при этом: .

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

Метод множителей Лагранжа

Пусть требуется решить задачу нелинейного программирования, заданную математической моделью в каноническом виде:

Причем в этой модели функции и непрерывны вместе со своими частными производными по всем управляющим переменным: .

Для решения поставленной задачи может быть применен метод множите­лей Лагранжа, пошаговый алгоритм которого состоит в следующем.

Шаг 1. Составляют функцию Лагранжа:

где переменные называются множителями Лагранжа.

Шаг 2. Находят частные производные функции Лагранжа по всем перемен­ным и приравнивают их к нулю:

Шаг 3. Решают систему уравнений, полученную на шаге 2, и находят ста­ционарные точки, т.е. точки, в которых функция F (и, следовательно, исходя из структуры функции F, целевая функция f) может иметь экстремум.

Шаг 4. Проверяют полученные на шаге 3 стационарные точки на наличие в них экстремума и находят экстремальное значение целевой функ­ции задачи в найденной точке условного (в смысле не глобального) экстрему­ма.

ПРИМЕР: Фирма реализует автомобили двумя способами: через магазин и через торговых агентов. При реализации автомобилей через магазин расходы на реализацию составляют: условных единиц, а при продаже автомобилей через торговых агентов расходы составляют условных единиц. Найти оптимальный способ реа­лизации автомобилей, обеспечивающий минимум суммарных расходов, если общее число автомобилей, предназначенных для продажи, составляет 200 штук.

Очевидно, что математическая модель задачи будет иметь вид:

Анализ модели показывает, что налицо задача нелинейного программиро­вания с нелинейной целевой функцией и линейным ограничением. Для расчета модели, т.е. для решения задачи, приме­ним метод множителей Лагранжа.

В рассматриваемом случае функция Лагранжа будет иметь вид:

Вычислив частные производные и приравняв их нулю, полу­­чим следующую систему уравнений:

Решив эту систему, получим: и . Этим зна­че­ниям управляющих переменных соответствует значение целевой функции, равное: .

Для того чтобы убедиться в том, что найденные значения управляющих переменных действительно доставляют минимум целевой функции, вычислим значения вторых частных производных функции F в стационарной точке и сос­тавим определитель:

Поскольку найденный определитель больше нуля, в найденной ста­ционарной точке есть экстремум, а т.к. , то это минимум. Следова­тельно, в этой точке целевая функция задачи имеет условный минимум.

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

При решении задач нелинейного программирования методом множителей Лагранжа значения этих множителей не вычисляют, а при решении соответствующей системы уравнений выражают их через управляющие переменные, т.е. исключают.

Рекомендуемая литература по теме 4: [1 ÷ 4].

ВОПРОСЫ для самопроверки знаний по теме 4:

1. Для решения каких экономических задач чаще всего приме­няются нелиней­ные математические модели?

2. При каких условиях задача нелинейного программирования может быть решена графическим методом?

3. В каком виде должна быть записана математическая модель задачи нелинейного программирования для решения ее методом множителей Лагранжа?

4. В чем заключается основная идея метода множителей Лагранжа?

Источник