Методы нелинейной и дискретной оптимизации

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

1.4. Методы нелинейной  и дискретной оптимизации……....................... 3

2.4. Задача ....................................................................................................11

3.4. Задача ............................................................................................15

4.4. Задача …………............................................................................ 18

5.4. Задача………………………………………………………………..20

Литература ................................................................................................ 22

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.4. Методы нелинейной и дискретной оптимизации

В общем виде задача нелинейного  программирования состоит в определении  максимального (минимального) значения функции

   (1)

при условии

 (2)

где   –  некоторые известные функции n переменных, а   – заданные числа.

Класс задач нелинейного  программирования шире класса задач  линейного программирования. Подробное  изучение практических задач, которые  условились считать линейными, показывает, что они в действительности являются нелинейными. Существующие методы позволяют  решать узкий класс задач, ограничения  которых имеют вид  , а целевая функция является сепарабельной (суммой n функций  ), или квадратической. 

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

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

находят частные производные

и рассматривают систему n + m  уравнений

 (3)

с  n + m   неизвестными   ,   . Решив   систему  уравнений (3), получают все точки, в которых функция (1) может иметь экстремальные значения. Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума. Метод множителей Лагранжа имеет ограниченное применение, так как система (3), как правило, имеет несколько решений.

Пример. Найти точку условного  экстремума функции   при ограничениях

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

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

       

 Из второго и третьего  уравнений следует, что  ; тогда

Решив данную систему, получим:

  и    Функция  , заданная на выпуклом множестве Х, называется  выпуклой,  если  для любых двух точек   из Х и любого   выполняется соотношение         

. (4)

Функция  , заданная на выпуклом множестве Х, называется  вогнутой,  если  для любых  двух  точек   из Х и любо-

го   выполняется соотношение     

      . (5)

Если  неравенства  (15.4)  и  (15.5)  считать  строгими  и  они  выполняются при  , то функция   является строго выпуклой (строго вогнутой). Выпуклость и вогнутость функций определяется только относительно выпуклых множеств.

          

                        

 Рисунок 1. 

Если  , – выпуклые (вогнутые) функции на некотором выпуклом множестве  , то функция   - также выпуклая (вогнутая) на Х.

Основные свойства выпуклых и вогнутых функций:         

1. Множество точек минимума  выпуклой функции, заданной на  выпуклом множестве, - выпукло.

2. Пусть   - выпуклая функция, заданная на замкнутом выпуклом множестве  . Тогда локальный минимум   на Х является и глобальным.

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

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

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

6. Множество точек глобальных (следовательно, и локальных) минимумов  выпуклой функции  , заданной на ограниченном замкнутом выпуклом множестве Х, включает хотя бы одну крайнюю точку; если множество локальных минимумов включает в себя хотя бы одну внутреннюю точку множества Х, то    является функцией-константой.

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

                        (6)                                               

                    (7)                                                         

                                (8)

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

Говорят, что множество допустимых решений задачи (6) – (8) удовлетворяет условию регулярности, или условию Слейтера, если существует по крайней мере одна точка  , принадлежащая области допустимых решений такая, что  . Задача (6) – (8)  называется задачей выпуклого программирования, если функция   является вогнутой (выпуклой), а функции   – выпуклыми. Функцией Лагранжа задачи выпуклого программирования (6) – (8)  называется функция

       

где   – множители Лагранжа.

Точка   называется седловой точкой функции Лагранжа, если

       

для всех   и  . 

Частным случаем задачи нелинейного  программирования является задача квадратичного программирования, в которой ограничения

являются линейными, а  функция   представляет собой сумму линейной и квадратичной функции (квадратичной формы)

 

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

Функция   представляет собой сумму линейной функции (которая является и выпуклой, и вогнутой) и квадратичной формы. Если последняя является вогнутой (выпуклой), то задачи отыскания максимума (минимума) целевой функции могут быть успешно решены. Вопрос о том, будет ли квадратичная форма вогнутой или выпуклой, зависит от того, является ли она отрицательно-определенной, отрицательно-полуопределенной, положительно-определенной, положительно-полуопределенной или вообще неопределенной.

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

                                                                       

                                                                             

                               

Xj – целые неотрицательные.

Существуют различные  методы решения дискретной оптимизации. Эти методы делятся на три группы:

- метод отсечения;

- метод дерева решений;

- эвристические  (приближенные) методы.

Метод отсечения ориентированы на использования в задачах целочисленного линейного программирования (ЦЛП). Идея отсечения состоит в том,  что однократное решение задачи  ЦЛП сводится к многократному решению некоторой последовательности задач ЛП. Каждый раз решается новая ЗЛП, полученная из предыдущей дополнением к ней нового ограничения, обладающего двумя свойствами:

  - только что полученное нецелочисленное оптимальное решение ЗЛП не удовлетворяет новому ограничению;

- любое целочисленное  решение (не только оптимальное)  ему удовлетворяет.

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

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

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

 

2.4. Фермер планирует засеять кукурузой и соей 400 га земли. Затраты на сев и уборку кукурузы составят 200 ден. ед./га, сои –100 ден. ед./га. На покрытие расходов, связанных с севом и уборкой урожая, фермер получил кредит в размере 60 тыс. ден. ед. Фермер планирует получить: кукурузы – 30 ц/га, сои – 60 ц/га. Фермер заключил договор на продажу кукурузы по 3 ден. ед./ц и сои по 6 ден. ед./ц. Однако согласно данному договору он обязан хранить убранное зерно в течение нескольких месяцев на складе, максимальная вместимость которого – 21 тыс. ц.

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

Решение:

Обозначим через х1 сколько гектаров нужно засеять кукурузы, через х2 – сои. Так как у фермера всего имеется 400 га земли, то первое ограничение задачи имеет вид: х1+ х2 ≤ 400. Найдем общие затраты на сев и уборку кукурузы и сои: (200х1+100х2) ден. ед. Фермер получил на расходы ссуду в 60 тыс. ден., поэтому следующее ограничение имеет вид: 200х1+100х2 ≤ 60 000. Найдем, сколько центнеров зерна соберет фермер: (30х1+60х2) ц. Вместимость склада составляет 21 тыс. центнеров, поэтому следующее ограничение имеет вид: 30х1+60х2 ≤ 21 000. на все переменные наложено ограничение x  1,2 ≥ 0

Построим экономико-математическую модель задачи:

max f(X) = 90x1+120x2

х1+ х2 ≤ 400

200х1+100х2 ≤ 60 000

30х1+60х2 ≤ 21 000

x1,2 ≥ 0

Решим задачу графическим  методом.

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

Этап 1. Определим множество решений первого неравенства. Оно состоит из решения уравнения и строгого неравенства. Решением уравнения служат точки прямой x1+x2-400=0. Построим прямую по двум точкам (0;400) и (400;0), которые легко получить в результате последовательного обнуления одной из переменных. На рисунке обозначим ее цифрой I.

Множество решений строгого неравенства — одна из полуплоскостей, на которую делит плоскость построенная  прямая. Какая из них является искомой, можно выяснить при помощи одной контрольной точки. Если в произвольно взятой точке, не принадлежащей прямой, неравенство выполняется, то оно выполняется и во всех точках той полуплоскости, которой принадлежит контрольная точка, и не выполняется во всех точках другой полуплоскости. В качестве такой точки удобно брать начало координат. Подставим координаты (0; 0) в неравенство x1+x2-400<0, получим -400 < 0, т.е. оно выполняется. Следовательно, областью решения неравенства служит нижняя полуплоскость.