Модели нелинейного программирования

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

РОССИЙСКИЙ  ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

им. И. Канта

Кафедра управления хозяйством

Экономический факультет 
 
 
 
 

Контрольная работа по дисциплине

«Экономико-математическое моделирование.» 
 
 

ТЕМА: №6 «Модели нелинейного программирования.»

Решение задач №№ 2.2; 6.1; 8.3 
 
 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 

г Калининград 

2010 год 
 
 
 

                       CОДЕРЖАНИЕ 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1. Теоретическая часть.

 

    МОДЕЛИ  НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Классические методы оптимизации (методы определения экстремумов, метод множителей Лагранжа).

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

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

     Допустим, что среди ограничений 

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

                (1.1)

       и обращающие в максимум (минимум) целевую функцию

                                                   (1.2)

       Такие задачи в принципе можно решать классическими  методами дифференциального вычисления. На этом пути встречаются вычислительные трудности, которые делают необходимым поиск других методов решения.

       В условиях НЛП, когда число переменных n не меньше 2 вводится понятие условного экстримума.

       Теорема 1.1 (теорема существования экстремума).

       Если - непрерывная функция, определенная на замкнутом и ограниченном множестве, то она достигает на этом множестве, по крайней мере один раз, своих максимального и минимального значений.

       Предположим, что     дважды дифференцируема в точке и в некоторой ее окрестности. Если для всех точек Х этой окрестности  то говорят, что функция f(x) имеет экстримум в Х* (соответственно максимум или минимум).

       Точка Х*,  в которой все частные производные функции   z = f(x) равны 0, называется стационарной точкой.

       Необходимое условие экстримума. Если в точке Х* функция z=f(x) имеет экстримум, то частные производные функции в этой точке равны нулю:      

       Следовательно, точки экстримума функции  z=f(x) удовлетворяют системе уравнений:

                                                                    (1.3)

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

       

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

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

 

, где

     Функция z=f(x) имеет в точке   заданной области D глобальный максимум (наибольшее значение) или глобальный минимум (наименьшее значение), если неравенство или  соответственно выполняется для любой точки 

     Если  область D замкнута и ограничена, то дифференцируемая функция z=f(x) достигает в этой области своих наибольшего и наименьшего значений или в стационарной точке, или в граничной точке области (теорема Вейерштрасса)

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

     

     на  множестве допустимых значения D, описываемом системой уравнений

     

      к задаче безусловной оптимизации  функции

  

     где u Î R^m — вектор дополнительных переменных, называемых множителями Лагранжа. Функцию Ф(х,и), где x Î Rⁿ, u Î Rⁿ, называют функцией Лагранжа.  

     Теорема 1.2. Если х* является точкой условного экстремума функции (1.4) при ограничениях   (1.5) и ранг матрицы первых частных производных функций

     

     равен т, то существуют такие и₁^*, и₂^*,...,и_m^*, не равные одновременно нулю, при которых 

       

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

     1. Составление функции Лагранжа Ф(х,и).

     2. Нахождение частных производных

     

     3. Решение системы уравнений

     

     относительно  переменных x и u.

     4. Исследование точек, удовлетворяющих  системе, на максимум (минимум) с помощью достаточного признака экстремума.

     Присутствие последнего (четвертого) этапа объясняется тем, что теорема дает необходимое, но не достаточное условие экстремума. Положение дел с достаточными признаками условного экстремума обстоит гораздо сложнее. Вообще говоря, они существуют, но справедливы для гораздо более частных ситуаций (при весьма жестких предпосылках относительно функций f и g_i) и, как правило, трудноприменимы на практике.

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

     Модели  выпуклого программирования: производная по направлению и градиент, выпуклые функции, задача выпуклого программирования. Приближенное решение задач выпуклого программирования методом кусочно-линейной аппроксимации. Методы спуска. Приближенное решение задач выпуклого программирования градиентным методом.

     Производной   функции f(x)=f(x1, …, xn) по направлению L в точке Х называется предел

     

     Ведущее место среди прямых методов решения экстремальных задач занимает градиентный метод (точнее, семейство градиентных методов) поиска стационарных точек дифференцируемой функции. Напомним, что стационарной называется точка, в которой f(x)=0 и которая в соответствии с необходимым условием оптимальности является «подозрительной» на наличие локального экстремума. Таким образом, применяя градиентный метод, находят множество точек локальных максимумов (или минимумов), среди которых определяется максимум (или минимум) глобальный.

     Идея  данного метода основана на том, что  градиент функции указывает направление ее наиболее быстрого возрастания в окрестности той точки, в которой он вычислен. Поэтому, если из некоторой текущей точки х⁽¹⁾ перемещаться в направлении вектора f(x⁽¹⁾), то функция f будет возрастать, по крайней мере, в некоторой окрестности х⁽¹⁾. Следовательно, для точки х⁽²⁾ = х⁽¹⁾ +λ f(x⁽¹⁾), (λ>0), лежащей в такой окрестности, справедливо неравенство f(x⁽¹⁾)≤ f(x⁽²⁾).

     В зависимости от способа решения  различают различные варианты градиентного метода. Остановимся на наиболее известных из них.

     Метод наискорейшего спуска

     Название  метода можно было бы понимать буквально, если бы речь шла о минимизации целевой функции. Тем не менее по традиции такое название используется и при решении задачи на максимум.

     Пусть f(x)=f(x₁,x₁,...x_n) —дифференцируемая функция, заданная на Rⁿ, а х^(q) = (x₁^(q),x₂^(q),...,x_n^(q)) —   некоторая текущая точка. Оговоримся, что каких-либо общих рекомендаций, касающихся выбора исходной точки (или, как еще говорят, начального приближения) х⁽⁰⁾, не существует, однако по возможности она должна находиться близко от искомого оптимального плана х*. Если х^(q) — нестационарная точка (т. е. |f(x^(q))|>0), то при движении в направлении f(x^(q)) функция f(х) на некотором промежутке обязательно будет возрастать. Отсюда возникает естественная идея такого выбора шага, чтобы движение в указанном направлении продолжалось до тех пор, пока возрастание не прекратится. Для этого выразим зависимость значения f(x) от шагового множителя λ > 0. полагая х = х^(q) + λ f(x^(q))

     или, в координатной форме, 

       

     Чтобы добиться наибольшего из возможных значений f при движении по направлению f(x^(q)), нужно выбрать такое значение , которое максимизирует функцию φ(λ) (φ( )= max(φ(λ)). Для вычисления , используется необходимое условие экстремума dφ(λ)/dλ = 0. Заметим, что если для любого λ>0 dφ( )/dλ> 0, то функция f(х) не ограничена сверху (т. е. не имеет максимума). В противном случае, на основе (1.9) получаем

     

     что, в свою очередь, дает 

       

     Если  считать, что следующая точка  х^(q+1) соответствует оптимальному значению λ= , то в ней должно выполняться условие dφ( )/dλ = 0, и следует находить из условия f(x^(q+1)) f(x^(q))=0 или