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

Содержание:

Введение

1. Условия оптимальности. Теорема Куна-Таккера

2. Методы условной оптимизации. Метод Вульфа

3. Метод проектирования градиента

4. Метод штрафных функций

5. Метод барьерных функций

6. Другие методы условной оптимизации

7. Примеры методов нелинейного программирования

8. Примеры методов нелинейного программирования

Вывод

Литература

Введение

Реферат посвящен решению задач исследования операций с помощью нелинейного программирования.

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

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

(1.1)

Если хотя бы одна функция в модели (1.1) нелинейная, имеем задачу нелинейного программирования (НП). Размерность задачи характеризуется размерностью вектора переменных n и числом условий m1+m2. Однако сложность задачи определяется не столько размерностью, сколько свойствами функций цели и ограничений.

Разнообразие задач НП очень велико. Универсальных методов решения таких задач не существует. Имеется весьма ограниченное число точных методов и намного больше приближенных.

Наиболее развиты методы решения задач выпуклого программирования. К этому классу относятся задачи НП с выпуклым допустимым множеством и выпуклой целевой функцией при минимизации или вогнутой при максимизации. Допустимое множество выпуклое, если все функции линейные и выпуклы при неравенстве £ или вогнуты при ³. Например, условие x12+x22 £ r2 порождает выпуклое множество, пересечение которого с прямой x1+x2=0 дает тоже выпуклое множество. Очевидно, что задачи НП относятся к этому классу. Главная особенность задач выпуклого программирования в том, что они унимодальные, то есть любой их локальный оптимум является глобальным. Для ряда задач выпуклого программирования с дифференцируемыми функциями разработаны точные методы. Наибольшие сложности возникают при решении многоэкстремальных задач, которые по определению не относятся к классу выпуклых.

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

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

Кусочно-линейное программирование включает специальные методы решения задач с кусочно-линейными функциями. В частности, такими являются функции и если все fi(x) – линейные функции. Первая из них – выпуклая (рис. 1.1), вторая – вогнутая. Задачи с такими функциями могут входить в класс задач выпуклого программирования. Их решение строится на преобразовании модели к линейному виду с последующим применением методов ЛП.

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

1. Условия оптимальности. Теорема Куна-Таккера

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

Пусть дана задача в виде

(1.2)

Обобщенный метод множителей Лагранжа применим и к условиям-неравенствам. Запишем функцию Лагранжа (регулярную) для задачи (1.2)

. (1.3)

В теории НП показано, что эта функция имеет седловую точку (X*,L*) c максимумом по X и минимумом по L:

F(X, L*) £ F(X*, L*) £ F(x*, L). (1.4)

Поэтому задача (1.2) сводится к отысканию седловой точки функции (1.3).

Теорема. Пусть f, ji и yk – дифференцируемые функции и справедливо свойство Слейтера (то есть найдутся такие XÎD, что неравенства ji будут строгими). F(X, L) – соответствующая функция Лагранжа. Тогда для того чтобы вектор X* являлся решением общей задачи максимизации (1.2) необходимо выполнение условий

1) по X:

(1.5)

(1.6)

"Xj* ³ 0;

2) по L:

(1.7)

(1.8)

(1.9)

Приведенные условия оптимальности называются условиями Куна-Таккера. Опуская строгое доказательство, приведем логическое обоснование выражений (1.5)–(1.9).

По существу они являются обобщением классических условий экстремума, определяющих стационарные точки. Условие (1.5) содержит неравенство, так как неотрицательность вектора X означает, что максимум может быть либо при положительном X и тогда производная F по X обязательно равна нулю (случай 1 на рис. 1.2), либо при X=0 и тогда эта производная может быть как равной нулю, так и отрицательной (случаи 2 и 3 на рис. 1.2). Этим же объясняются условия дополняющей нежесткости (1.6): в точке максимума равны нулю либо x, либо производная, либо вместе.

Выражения (1.7)–(1.9) можно обосновать аналогично, если учесть, что по L рассматривается минимум F и .

Применив условия Куна-Таккера к задаче НП, получим равенства второй основной теоремы двойственности как частный случай условий дополняющей нежесткости, а двойственные переменные – как частный случай l.

Особую роль условия Куна-Таккера играют в решении задач выпуклого программирования, так как для них они являются не только необходимыми, но и достаточными.

2. Методы условной оптимизации. Метод Вульфа

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

 Скачать реферат