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

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

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

им. И. Канта

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

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

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

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

ТЕМА: №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 или 

     Условие (1.12) означает равенство нулю скалярного произведения градиентов функции f точках x^(q+1) и x^(q). Геометрически оно может быть интерпретировано как перпендикулярность векторов градиентов функции f в указанных точках, что и показано на рис. 1.2. Продолжая геометрическую интерпретацию метода наискорейшего спуска, отметим, что в точке x^(q+1) вектор f(x^(q+1)), будучи градиентом, перпендикулярен линии уровня, проходящей через данную точку. Стало быть, вектор f(x^(q)) является касательным к этой линии. Итак, движение в направлении градиента f(x^(q)) следует продолжать до тех пор, пока он пересекает линии уровня оптимизируемой функции.

     После того как точка x^(q+1) найдена, она становится текущей для очередной итерации. На практике признаком достижения стационарной точки служит достаточно малое изменение координат точек, рассматриваемых на последовательных итерациях. Одновременно с этим координаты вектора Δf(x^(q)) должны быть близки к нулю.

     Метод дробления шага

     Для нахождения шага λ в методе наискорейшего спуска требуется решить уравнение (1.12), которое может оказаться достаточно сложным. Поэтому часто ограничиваются «подбором» такого значения λ, что φ(λ) > φ(0). Для этого задаются некоторым начальным значением λ₁, (например, λ₁=l) и проверяют условие φ(λ₁) >φ(0). Если оно не выполняется, то полагают 

     λ₂ = 1/2 λ₁ 

     и т. д. до тех пор, пока не удается найти  подходящий шаг, с которым переходят к следующей точке x^(q+1). Критерий завершения алгоритма, очевидно, будет таким же, как и в методе наискорейшего спуска.

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

     в случае градиентных методов, может  быть осуществлен за счет подбора  соответствующих начальных приближений х⁽⁰⁾.

     Однако  существует один класс функций, для  которых градиентные методы приводят к нахождению глобального оптимума. Это выпуклые функции.

     F Функция f(x) = f (x₁, x₂, …, x_n) называется выпуклой в области D, если для любых двух точек х⁽¹⁾, х⁽²⁾ Î D и любого λ Î [0,1] выполняется неравенство

если  же

     то  функция называется вогнутой. 

     Геометрический  смысл понятий выпуклости и вогнутости для случая функции одной переменной представлен на рис.1.3. Из него, в частности, видно, что график выпуклой функции лежит ниже отрезка, соединяющего точки (х⁽¹⁾, f(x(¹⁾)) и (х⁽²⁾, f(x⁽²⁾)), а график вогнутой — выше. 

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

     Метод допустимых направлений. Данный метод также называется методом возможных направлений или же по имени автора—методом Зойтендейка. Его основную идею будет удобно продемонстрировать на примере ЗНП с ограничениями в форме неравенств: 

     В указанном методе так же, как и  в градиентных методах, находится последовательность точек х⁽⁰⁾ х⁽¹⁾,..., х^(q)..., таких, что f(х^(q+1)) ≥ f(x^(q)) . При этом переход от точки x^(q))  к точке х^(q+1)) происходит по некоторому выбранному направлению s^(q) с шаговым множителем λ_q:

     По  отношению к векторам, задающим направления  перемещения, вводятся два фундаментальных понятия.

     F Направление s называется допустимым (возможным) в точке x^(q) Î D, если существует такое  λ > 0, что x^(q+1) = x^(q) + λs Î D.

     F Направление s называется прогрессивным в точке x^(q) Î D, если существует такое λ >0, что   f(x^(q) + λs)> > f(x^(q)) для задачи максимизации и f(x^(q) + λs) < f(x^(q)) для задачи минимизации.

     На  основе данных определений достаточно просто сформулировать критерий проверки оптимальности точки (так называемый критерий оптимальности в терминах допустимых и прогрессивных направлений):

     F точка х* является оптимальным планом задачи, если в ней ни одно допустимое направление не является прогрессивным.

     В алгоритме метода допустимых направлений  правила выбора точки х^(q+1), к которой происходит очередной переход, различаются в зависимости от того, где находится текущая точка х^(q). Принципиально возможны две ситуации.

     1°.  Точка х^(q)  лежит внутри области D, т. е. для всех i Î 1: m g_i(х^(q)) < 0 (см. рис. 1.4). Очевидно, что для внутренней точки любое направление будет допустимым (при выборе достаточно малого шага), поэтому естественным представляется движение в сторону «гарантированного» возрастания значения функции, а именно в направлении градиента. Значит, для внутренней точки х^(q) целесообразно выбрать s^(q) = f(х^(q)).

     Шаговый множитель λ_q выбирается так, чтобы, с одной стороны, новая точка х^(q+1) принадлежала D, а с другой — значение целевой функции в ней f(х^(q+1)) было как можно большим. 

     С этой целью сначала найдем промежуток [0, ] из условия для чего необходимо решить систему неравенств: 

     Зная  промежуток [0, ], определяем значение шагового множителя λ_q из условия максимизации значения функции в направлении s^(q): 

      Вновь найденная точка x^(q+1) может находиться или внутри области D, или на ее границе. В первом случае (на рис. 1.4 ему соответствует точка ^(q+1) переходим к началу данного пункта и повторяем вышеописанные действия, а во втором (точка ^(q+1)  на рис. 1.4) — действуем по рассматриваемой далее схеме.

     2°.  Точка x^(q) находится на границе области (см. рис. 1.5). Это означает, что одно или несколько неравенств из системы ограничений задачи (1.15) выполняются как строгие равенства: g_i(x^(q)) = 0. Например, на рис.1.5 и g₁(x^(q)) = 0 и g₃(x^(q)) = 0.

     Ограничение, которое в текущей точке выполняется  как равенство, называют активным. Множество номеров активных ограничений в точке x^(q) будем обозначать как I(x^(q)). В примере, изображенном на рис. 1.5, I(x^(q)) = {1, 3}. Также из рисунка видно, что все допустимые направления, исходящие из точки x^(q), должны образовывать тупые углы с векторами градиентов функций, задающих активные ограничения в данной точке. Последнее условие может быть выражено через задание ограничений на значения скалярных произведений вектора направления s на градиенты функции ограничений: 

     где I_л — множество номеров индексов линейных ограничений, I_н — множество номеров индексов нелинейных ограничений. Соответственно, I(x^(q))◠I_л —номера линейных активных ограничений, а I(x^(q))◠I_н — номера нелинейных активных ограничений. Отличие условий (1.19) от условий (1.20) заключается в том, что в случае линейного ограничения направление, образующее прямой угол с градиентом ограничивающей функции (т. е. их скалярное произведение равно нулю), будет заведомо допустимым, а в случае нелинейного ограничения — возможно, нет.

     Все возможные направления в точке  x^(q) образуют так называемый конус допустимых направлений, и из них для следующего перехода, очевидно, нужно выбрать прогрессивное. Если такового не существует, то согласно сформулированному выше критерию точка x^(q) является оптимальной! Для ускорения максимизации функции желательно, чтобы угол между искомым допустимым прогрессивным направлением s^(q) и градиентом целевой функции ∇f(x^(q)) был как можно меньше или, что то же самое, как можно большей была бы проекция s на ∇f(x^(q)) (при условиях нормировки вектора s^(q)). Иными словами, желательно, чтобы неравенство s^(q)∇f(x^(q))+σ≥0 выполнялось при минимально возможном σ ∈ R. Тогда задачу отыскания наилучшего допустимого прогрессивного направления s^(q) можно свести к задаче минимизации параметра σ: 

     при условиях

     где s₁² +s₂² +...+s_n², ≤ l —условие нормировки, обеспечивающее ограниченность решения;

             τ — некоторое достаточно малое число, характеризующее «строгость» выполнения неравенств.  

     В отличие от всех остальных, последнее условие в системе (1.22) является нелинейным, что существенно усложняет процесс решения задачи (1.21)-(1.22). Поэтому на практике для определения направления s^(q) (возможно, не лучшего) переходят от данной задачи к задаче линейного программирования путем замены указанных выше условий нормировки на ограничения вида –l ≤ s_j, ≤ 1: 

     После того как прогрессивное направление  s^(q) найдено, шаговый множитель определяется по методу, описанному в п. 1°.

     В заключение отметим, что при практических расчетах алгоритм завершается при достижении такой точки х*, в которой |∇f(x*)|<ε, где ε —достаточно малое число. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2. Практическая  часть.

  Задача №2.2

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

    А).                                          Б).

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

Решение:

А)

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

              (1)

Запишем систему ограничений в каноническом виде:

Решаем  симплекс- методом: