Математические методы исследования операций в экономике (стр. 16 из 37)
Общая задача нелинейного программирования (ОЗНП) определяется как задача нахождения максимума (или минимума) целевой функцииf(x1,х2,...,xn) на множествеD, определяемом системой ограничений
где хотя бы одна из функций f илиgi является нелинейной.
По аналогии с линейным программированием ЗНП однозначно определяется парой (D, f) и кратко может быть записана в следующем виде
Также очевидно, что вопрос о типе оптимизации не является принципиальным. Поэтому мы, для определенности, в дальнейшем по умолчанию будем рассматривать задачи максимизации.
Как и в ЗЛП, вектор х* = (x1*,x2*,...,xn*) Î D называется допустимым планом, а если для любого x Î D выполняется неравенствоf(x*) ≥ f(x), то х* называют оптимальным планом. В этом случае х* является точкой глобального максимума.
С точки зрения экономической интерпретацииf(x) может рассматриваться как доход, который получает фирма (предприятие) при плане выпуска х, а gi(х) ≤ 0 как технологические ограничения на возможности выпуска продукции. В данном случае они являются обобщением ресурсных ограничений в ЗЛП (аiх– bi ≤ 0).
Задача (2.2) является весьма общей, т. к. допускает запись логических условий, например:
или запись условий дискретности множеств:
Набор ограничений, определяющих множество D, при необходимости всегда можно свести либо к системе, состоящей из одних неравенств:
либо, добавив фиктивные переменные у, к системе уравнений:
Перечислим свойства ЗНП, которые существенно усложняют процесс их решения по сравнению с задачами линейного программирования:
1. Множество допустимых плановD может иметь очень сложную структуру (например, быть невыпуклым или несвязным).
2. Глобальный максимум (минимум) может достигаться как внутри множества D, так и на его границах (где он, вообще говоря, будет не совпадать ни с одним из локальных экстремумов).
3. Целевая функция f может быть недифференцируемой, что затрудняет применение классических методов математического анализа.
В силу названных факторов задачи нелинейного программирования настолько разнообразны, что для них не существует общего метода решения.
2.1.2. Решение задач условной оптимизации методом Лагранжа. Одним из наиболее общих подходов к решению задачи поиска экстремума (локального максимума или минимума) функции при наличии связующих ограничений на ее переменные (или, как еще говорят, задачи условной оптимизации) является метод Лагранжа. Многим читателям он должен быть известен из курса дифференциального исчисления. Идея данного метода состоит в сведении задачи поиска условного экcтремума целевой функции
на множестве допустимых значения D, описываемом системой уравнений
к задаче безусловной оптимизации функции
гдеuÎRm— вектор дополнительных переменных, называемых множителями Лагранжа. Функцию Ф(х,и), где xÎRn, u ÎRn, называют функцией Лагранжа. В случае дифференцируемости функций f иgi справедлива теорема, определяющая необходимое условие существования точки условного экстремума в задаче (2.3)-(2.4). Поскольку она непосредственно относится к предмету математического анализа, приведем ее без доказательства.
Теорема 2.1. Если х* является точкой условного экстремума функции (2.3) при ограничениях (2.4) и ранг матрицы первых частных производных функций
равен т, то существуют такие и1*, и2*,...,иm*, не равные одновременно нулю, при которых
Из теоремы (2.1) вытекает метод поиска условного экстремума, получивший название метода множителей Лагранжа, или просто метода Лагранжа. Он состоит из следующих этапов.
1. Составление функции Лагранжа Ф(х,и).
2. Нахождение частных производных
3. Решение системы уравнений
относительно переменныхx и u.
4. Исследование точек, удовлетворяющих системе (2.7), на максимум (минимум) с помощью достаточного признака экстремума.
Присутствие последнего (четвертого) этапа объясняется тем, что теорема (2.1) дает необходимое, но не достаточное условие экстремума. Положение дел с достаточными признаками условного экстремума обстоит гораздо сложнее. Вообще говоря, они существуют, но справедливы для гораздо более частных ситуаций (при весьма жестких предпосылках относительно функций f иgi) и, как правило, трудноприменимы на практике.
Еще раз подчеркнем, что основное практическое значение метода Лагранжа заключается в том, что он позволяет перейти от условной оптимизации к безусловной и, соответственно, расширить арсенал доступных средств решения проблемы. Однако нетрудно заметить, что задача решения системы уравнений (2.7), к которой сводится данный метод, в общем случае не проще исходной проблемы поиска экстремума (2.3)-(2.4). Методы, подразумевающие такое решение, называются непрямыми. Они могут быть применены для весьма узкого класса задач, для которых удается получить линейную или сводящуюся к линейной систему уравнений (2.7). Их применение объясняется необходимостью получить решение экстремальной задачи в аналитической форме (допустим, для тех или иных теоретических выкладок). При решении конкретных практических задач обычно используются прямые методы, основанные на итеративных процессах вычисления и сравнения значений оптимизируемых функций.
2.1.3. Градиентные методы решения задач безусловной оптимизации. Ведущее место среди прямых методов решения экстремальных задач занимает градиентный метод (точнее, семейство градиентных методов) поиска стационарных точек дифференцируемой функции. Напомним, что стационарной называется точка, в которой
f(x)=0 и которая в соответствии с необходимым условием оптимальности является «подозрительной» на наличие локального экстремума. Таким образом, применяя градиентный метод, находят множество точек локальных максимумов (или минимумов), среди которых определяется максимум (или минимум) глобальный.Идея данного метода основана на том, что градиент функции указывает направление ее наиболее быстрого возрастания в окрестности той точки, в которой он вычислен. Поэтому, если из некоторой текущей точки х(1) перемещаться в направлении вектора
f(x(1)), то функция f будет возрастать, по крайней мере, в некоторой окрестности х(1). Следовательно, для точки х(2) = х(1) +λ f(x(1)), (λ>0), лежащей в такой окрестности, справедливо неравенствоf(x(1))≤ f(x(2)). Продолжая этот процесс, мы постепенно будем приближаться к точке некоторого локального максимума (см. рис. 2.1).Однако как только определяется направление движения, сразу же встает вопрос о том, как далеко следует двигаться в этом направлении или, другими словами, возникает проблема выбора шага λ в рекуррентной формулe
задающей последовательность точек, стремящихся к точке максимума.
В зависимости от способа ее решения различают различные варианты градиентного метода. Остановимся на наиболее известных из них.