Нелинейное программирование

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

 

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

 

Пример 3

 Минимизировать  

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

 Решение. 

 Записав  данную задачу в виде задачи  нелинейного  программирования, получим 

 

 

 

 

 Уравнение  ,  входящее в состав условий   Куна—Таккера, принимает следующий вид:

 

 откуда 

 

 Неравенства  и уравнения задачи Куна — Таккера в данном случае записываются в виде

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

      

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

 Таким образом, этой задачи условия  Куна—Танкера записываются в следующем виде:

 

5. КВАДРАТИЧНОЕ   ПРОГРАММИРОВАНИЕ

 

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

,

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

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

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

 

6. ГРАДИЕНТНЫЕ   МЕТОДЫ

 

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

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

Метод Франка - Вульфа. Пусть требуется найти максимальное значение вогнутой функции

    (9)

при условиях

,    (10)

        (11)

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

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

,

строят линейную функцию

.    (12)

Находят максимум функции (12) при ограничениях (10) и (11). Пусть решение данной задачи определяется точкой . За новое допустимое решение исходной задачи принимают координаты точки , которые находят по формулам

,

где - некоторое число, называемое шагом вычислений . За принимают наименьший корень уравнения или выбирают произвольно, если он не принадлежит интервалу (0; 1).

Метод штрафных функций. Рассмотрим задачу нелинейного программирования (6) -(8), где  - выпуклые функции.

Вместо того, чтобы решать эту задачу, находят  максимум функции 

,

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

,

где      

 

 а - некоторые постоянные числа, представляющие собой весовые коэффициенты.

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

,

где - шаг вычислений .

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

 

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

В качестве начальных  значений   берут произвольные неотрицательные числа.

 

7. ОСОБЕННОСТИ ЗАДАЧ  НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

• Задачи нелинейного программирования значительно ближе к реальным ситуациям, чем линейные.
• Задачи нелинейного программирования могут быть с ограничениями или без них.
• Решение задач нелинейного программирования намного сложнее, чем задач линейного программирования. Не существует универсального метода решения задач нелинейного программирования.
• В задачах нелинейного программирования могут существовать локальные и глобальные минимумы (максимумы).
• Наличие нескольких экстремумов целевой функции обуславливает множественность решений задачи выбора, что существенно затрудняет вещественную интерпретацию результатов.
• При создании нелинейных моделей в интересах обоснования рациональных решений целесообразно предусмотреть возможность уменьшения числа локальных решений: число закладываемых в модель ограничений m должно соотноситься с размерностью задачи n как 2<=m<=(n+1), модели должны строиться так, чтобы обеспечить возможность применения методов выпуклого анализа.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

II Краткая характеристика метода конфигураций Хука-Дживса. Алгоритм Хука-Дживса. Задача на данный алгоритм.

 

1. МЕТОД КОНФИГУРАЦИЙ ХУКА-ДЖИВСА.

 

Стратегия поиска. Метод представляет собой комбинацию исследующего поиска с циклическим изменением переменных и ускоряющего поиска по образцу. Цель исследующего поиска – выявление локального поведения целевой функции и определение направления ее убывания. Эта информация используется при поиске по образцу вдоль направления убывания целевой функции.

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

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

Обозначим через – координатные направления:

 Отметим,  что при поиске по направлению меняется только переменная , а остальные переменные остаются зафиксированными.

 

2. АЛГОРИТМ МЕТОДА ХУКА-ДЖИВСА.

 Шаг  1.  Задать начальную точку , число - для остановки алгоритма, начальные значения приращений по координатным приращениям , ускоряющий множитель  

 Шаг 2.  Провести исследующий поиск по выбранному координатному направлению:

 

 Шаг  3.  Проверить условия:

а) если i < n, то положить i= i+1 и перейти к шагу 2. (продолжить исследующий поиск по оставшимся направлениям);

б) если i = n, проверить  успешность исследующего поиска:

- если , перейти к шагу 4.

- если , перейти к шагу 5.

 Шаг  4.  Провести поиск по образцу.

В точке провести исследующий поиск, в результате которого получается точка

Если , то точка становится точкой нового базиса, а - точкой старого базиса. Перейти к шагу 5. .

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

Шаг 5.  Проверить условие окончания счета:

а) если все  , то поиск закончить ;

б) для тех i, для которых  , уменьшить величину шага и перейти к шагу 2.

 

 Пример.

Найти минимум  функции 

 Решение. 

 Зададим начальную точку ; число . Положим i=1, k=0.

, то шаг неудачен. , то шаг удачен.

Поскольку i=1 <2=n, то положим i=2 и перейдем к шагу 2.

, то шаг неудачен.

,то шаг удачен 

 Поскольку i=2=n и  , то перейдем к шагу 4.

 Проведем поиск по  образцу из точки Положим i=1, k= k+1=1. и перейдем к шагу 2.

 Выполняем исследующий поиск из точки . , то шаг неудачен. Т.к. , то шаг удачен.

 Поскольку i=1 <2=n, то положим i= i+1=2 и перейдем к шагу 2.

, то шаг неудачен. , то шаг неудачен.

  , то поиск по образцу на шаге 40 прошел успешно.

Точка становится новым базисом, а точка становится старым базисом. Выполним поиск по образцу из нового базиса. Перейдем к шагу 4.

 Положим i=1, k=k+1=2. 

и перейдем к  шагу 2.

, то шаг удачен.

 Поскольку i=1 <2=n, то положим i= i +1=2 и перейдем к шагу 2.

, то шаг удачен.

 Т.к. i=2=n и f(4,5)=5 > f(5,5)=1, то поиск по образцу на прошел неудачно. Переходим к шагу 5.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

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