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

Содержание

Введение--------------------------------------------------------------------------------------3

1. Теоретические аспекты-----------------------------------------------------------------5

1.1. Общие сведения о численных методах оптимизации---------------------5

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

1. 3. Алгоритмы решения задач с ограничениями------------------------------9

1.4. Сепарабельное программирование-------------------------------------------10

1.5. Описание метода Дэвидона – Флетчера – Пауэлла--------------------18

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

2.1Сущность и актуальность задачи---------------------------------------------23

2.2. Предварительная постановка задачи---------------------------------------23

3. Строгая постановка и решение прикладной оптимизационной задачи-----24

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

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

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

4. Анализ результатов решения оптимизационной задачи и оценка степени достижения цели---------------------------------------------------------------------------26

Заключение---------------------------------------------------------------------------------27

Список литературы------------------------------------------------------------------------28

Приложение. Листинг программы-----------------------------------------------------29

Введение

В данной курсовой работе рассматривается метод Дэвидона–Флетчера–Пауэлла, который применяется для решения задачи выбора оптимального варианта условий хранения сырья в хлебопекарном производстве с целью увеличения выхода готовой продукции. Первоначально этот метод был предложен Дэвидоном (Davidon [1959]), а затем развит Флетчером и Пауэллом (Fletcher, Powell [1963]). Метод Дэвидона-Флетчера-Пауэлла называют также и методом переменной метрики. Он попадает в общий класс квазиньютоновских процедур.

Цель работы: повышение объема хлебопекарного производства.

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

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

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

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

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

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

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

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

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

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

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

Выдержка из текста работы

1. Теоретические аспекты

1.1. Общие сведения о численных методах оптимизации

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

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

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

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

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].

Заключение

Задача оптимизации хлебопекарного производства является весьма актуальной, так как хлеб – это жизненно необходимый продукт. Качество и количество хлеба находится в прямой зависимости от качества сырья, следовательно, одним из важнейших показателей является влажность муки. Примененный метод Дэвидона–Флетчера–Пауэлла не часто встречается экономистами и практиками для решения задач в хлебопекарном производстве. В данной курсовой работе была предпринята попытка реализовать его на практике, которая доказала, что этот метод может быть использован в качестве универсального средства поиска оптимальных решений в хлебопекарном производстве.

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

Список литературы

1. Аттетков А.В., Галкин С.В., В.С. Зарубин. Методы оптимизации: Учеб. для вузов / Под ред. В.С. Зарубина, А.П. Крищенко. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.

2. А.В. Пантелеев, А.С. Бортаковский. Теория управления в примерах и задачах М: Изд-во «Высшая школа», 2003.

3. Соболь И.М., Свешников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. – М.: Наука, 1981, 110с.

4. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. «Наука», 1980 г.