«Нелинейное программирование с сепарабельными функциями»

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

Основные частные задачи работы:

1) Анализ теоретических основ метода Дэвидона-Флетчера-Пауэлла.

2) Выбор прикладной оптимизационной задачи.

3) Реализация метода решения оптимизационной задачи вручную.

4) Реализация метода решения оптимизационной задачи на ЭВМ.

5) Анализ полученных результатов.

Наиболее существенные положения, выдвигаемые для защиты:

1) Анализ применимости математических методов для оптимизации различных видов деятельности в условиях развития рыночной экономики является весьма актуальным.

2) Метод Дэвидона-Флетчера-Пауэлла может быть использован в качестве универсального средства поиска оптимальных решений в хлебопекарном производстве.

3) За счет минимизации влажности муки увеличение хлебопекарного производства достижимо при заданных исходных данных на 3%.

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

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

В зависимости от вида целевой функции задачи делятся на:

a) задача линейного программирования

b) задача квадратичного программирования

c) задача дробно – линейного программирования

d) задача сепарабельного программирования

e) задача нелинейного программирования

f) и другие виды задач.

Подавляющее число численных методов оптимизации относится к классу итерационных, в частности метод Дэвидона – Флетчера – Пауэлла, т. е. порождающих последовательность точек в соответствии с предписанным набором правил, включающим критерий окончания. При создании начальной точки x0 методы генерируют последовательность x0 , x1 …. Преобразование точки xk в xk+1 представляет собой итерацию [3].

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

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

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

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

Наиболее развиты методы решения задач выпуклого программирования. К этому классу относятся задачи НП с выпуклым допустимым множеством и выпуклой целевой функцией при минимизации или вогнутой при максимизации. Допустимое множество выпуклое, если все функции линейные и выпуклы при неравенстве  или вогнуты при . Например, условие x12+x22  r2 порождает выпуклое множество, пересечение которого с прямой x1+x2=0 дает тоже выпуклое множество. Очевидно, что задачи ЛП относятся к этому классу. Главная особенность задач выпуклого программирования в том, что они унимодальны, то есть любой их локальный оптимум является глобальным. Для ряда задач выпуклого программирования с дифференцируемыми функциями разработаны точные методы. Наибольшие сложности возникают при решении многоэкстремальных задач, которые по определению не относятся к классу выпуклых. Важным классом НП являются задачи квадратичного программирования. В них целевая функция представляет собой сумму линейной и квадратичной форм, а все условия линейные. При выпуклости (вогнутости) квадратичной формы они являются частным случаем задач выпуклого программирования. В нелинейном программировании выделяют также задачи сепарабельного программирования. Это задачи, в которых все функции сепарабельны. Функция сепарабельна, если она представляется в виде сумы функций отдельных переменных. Линейная функция – частный случай сепарабельной. Сепарабельная задача может быть одновременно и задачей выпуклого программирования. Задачи геометрического программирования составляют отдельный класс НП. Все функции в таких задачах являются позиномами. В общем виде позиномом называется функция ,

в которой kj – любые действительные числа. Задачи геометрического программирования ставятся только на минимум: Такие задачи чаще возникают в конструкторских разработках. Для них разработаны специальные методы.

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

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

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

Условия оптимальности Важным свойством задач НП является дифференцируемость функций критерия и ограничений. Для таких задач получены условия оптимальности, на основе которых строится ряд методов НП. Пусть дана задача в виде (8.2) Обобщенный метод множителей Лагранжа применим и к условиям-неравенствам. Запишем функцию Лагранжа (регулярную) для задачи (8.2) . (8.3) В теории НП показано, что эта функция имеет седловую точку (X*,*) c максимумом по X и минимумом по : F(X, *)  F(X*, *)  F(X*, ). (8.4) Поэтому задача (8.2) сводится к отысканию седловой точки функции (8.3).Теорема Пусть f, i и k – дифференцируемые функции и справедливо свойство Слейтера (то есть найдутся такие ХD, что неравенства i будут строгими). F(X, ) – соответствующая функция Лагранжа. Тогда для того чтобы вектор Х* являлся решением общей задачи максимизации (8.2) необходимо выполнение условий

1) по X:

Xj*  0;

2) по :

Приведенные условия оптимальности называются условиями Куна-Таккера. Опуская строгое доказательство, приведем логическое обоснование выражений (8.5)-(8.9). По существу они являются обобщением классических условий экстремума, определяющих стационарные точки. Условие (8.5) содержит неравенство, так как неотрицательность вектора X означает, что максимум может быть либо при положительном X и тогда производная F по X обязательно равна нулю (случай 1 на рис. 8.3), либо при X=0 и тогда эта производная может быть как равной нулю, так и отрицательной (случаи 2 и 3 на рис. 8.3). Этим же объясняются условия дополняющей нежесткости (8.6): в точке максимума равны нулю либо X, либо производная, либо вместе. Выражения (8.7)-(8.9) можно обосно–вать аналогично, если учесть, что по  рассматривается минимум F и .[4]

Применив условия Куна-Таккера к задаче ЛП, получим равенства второй основной теоремы двойственности как частный случай условий

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

2. Выполните не более пяти итераций метода наискорейшего спуска (подъема) для каждой из следующих задач. Во всех случаях положите Х° = О.

a) min/(Х) = (*2-*?)*+(1-х,)*.

b) max/(X) = сХ + ХГАХ, где

с = (1,3, 5),

с) min/(X) = X[-х2 +xf-х,х2.

3. Решение прикладной оптимизационной задачи

3.1. Строгая постановка задачи

При формулировании строгой постановки задачи будем исходить из того, что:

1) функция, характеризующая влажность муки имеет вид:

2) при решении задачи методом Дэвидона – Флетчера – Пауэлла в состав исходных данных следует включить - начальное значение , - начальное значение , - малая величина, определяющая окончание операций, - предельное число итераций.

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

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

Реализация метода решения оптимизационной задачи вручную

Для реализации метода Дэвидона – Флетчера – Пауэлла решения задачи вручную и на ЭВМ зададим конкретные значения исходных данных:

Найдем градиент функции в произвольной точке :

.

Положим

Вычислим .

Проверим выполнение условия (т.е. критерий окончания) :

Расчет окончен в точке

Следовательно, влажности при таком температурном режиме:

3.3. Реализация решения задачи на ЭВМ

Программная реализация метода Дэвидона–Флетчера–Пауэлла с помощью программы MathCAD для решения задачи минимизации влажности муки в хлебопекарном производстве приведена в приложении [4].