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

Содержание
ВВЕДЕНИЕ………………………………………………………………..4
1 ОБЩАЯ ЧАСТЬ.…………………………………...……………..……..5
1.1 Математическое программирование .………...................................5
1.2. Нелинейное программирование ………………………………...…5
1.3 Методы нелинейного программирования……………..………..….9
2 СПЕЦИАЛЬНАЯ ЧАСТЬ ПРОЕКТА ..……………………………….14
2.1.Постановка задачи………………………………. …………………14
2.2 Алгоритм метода наискорейшего спуска………………………….15
2.3 Алгоритм в виде блок-схемы……………… ………………………15
2.4 Решение задачи моделирования максимального
товарного производства продукции предприятия ……………………..16
ЗАКЛЮЧЕНИЕ…………………………………………………………...20
БИБЛИОГРАФИЯ………………………………………………………...21
ВВЕДЕНИЕ
Современный этап развития человечества отличается тем, что на смену века энергетики приходит век информатики. Происходит интенсивное внедрение новых технологий во все сферы человеческой деятельности. Встает реальная проблема перехода в информационное общество, для которого приоритетным должно стать развитие образования. Изменяется и структура знаний в обществе. Все большее значение для практической жизни приобретают фундаментальные знания, способствующие творческому развитию личности. Важна и конструктивность приобретаемых знаний, умение их структурировать в соответствии с поставленной целью. На базе знаний формируются новые информационные ресурсы общества. Формирование и получение новых знаний должно базироваться на строгой методологии системного подхода, в рамках которого отдельное место занимает модельный подход. Возможности модельного подхода крайне многообразны как по используемым формальным моделям, так и по способам реализации методов моделирования. Физическое моделирование позволяет получить достоверные результаты для достаточно простых систем.
В настоящее время нельзя назвать область человеческой деятельности, в которой в той или иной степени не использовались бы методы моделирования. Особенно это относится к сфере управления различными системами, где основными являются процессы принятия решений на основе получаемой информации.
1 ОБЩАЯ ЧАСТЬ
1.1 Математическое программирование
Математическое программирование ("планирование") – это раздел математики, занимающийся разработкой методов отыскания экстремальных значений функции, на аргументы которой наложены ограничения. Методы математического программирования используются в экономических, организационных, военных и др. системах для решения так называемых распределительных задач. Распределительные задачи (РЗ) возникают в случае, когда имеющихся в наличии ресурсов не хватает для выполнения каждой из намеченных работ эффективным образом и необходимо наилучшим образом распределить ресурсы по работам в соответствии с выбранным критерием оптимальности.
1.2 Нелинейное программирование
Многообразие методов решения линейных программ имеет в своей основе идею упорядоченного перебора опорных планов (вершин) исходной или сопряженной задачи. Для нелинейных же программ простого метода решения, подобного симплексному, нет по многим причинам.
Во-первых, множество планов может оказаться невыпуклым или иметь бесконечное количество "вершин".
Во-вторых, искомые экстремумы могут достигаться как на границе множества планов, так и внутри его.
В-третьих, в нелинейных программах возникает проблема поиска глобального экстремума среди множества локальных.
Как мы показали ранее, ни использование аппарата производных, ни прямое табулирование целевой функции над множеством планов не решают проблему в случае более трех переменных. Поэтому каждая нелинейная программа требует индивидуального подхода, учитывающего ее специфику.
Существующие методы нелинейного программирования можно подразделить на следующие основные классы.
Градиентные методы, в основе которых лежит свойство градиента функции в точке (вектора частных производных, вычисленного в точке) как указателя направления наибольшего роста функции в окрестности точки.
Так при отсутствии ограничений одна из простейших разновидностей градиентных методов - метод наискорейшего спуска предлагает выбрать некоторую точку (план) Xk и начальный шаг Hk, вычислить градиент функции в выбранной точке grad F(Xk) и осуществить переход по градиенту (при максимизации) с выбранным шагом. Если значение функции в новой точке больше предыдущего, новая точка принимается за исходную и повторяется такая же процедура. При попадании в точку с меньшим значением уменьшается шаг (например, вдвое) и переход повторяется от исходной точки. Переходы продолжаются до достаточно малого шага .
Например, если нужно решить систему уравнений
(X2+1)(Y-1)=3,Y=ln(X+1),
то можно заменить эту задачу задачей минимизации функции F(X,Y)=[(X2+1)(Y-2)-3]2+[Y-ln(X+1)]2 (если система имеет решение, то искомый минимум равен нулю).
Градиент этой функции определяется вектором
Grad F(X,Y) = {2[(X2+1)(Y-2)-3] 2X (Y-2) - 2[Y-ln(X+1)]/(X+1),
2 [(X2+1)(Y-2)-3](X2+1) - 2[Y-ln(X+1)]}.
Выбираем начальную точку M0(2,1) и шаг h=1.Здесь значение функции F(M0)=64, градиент в этой точке grad F(M0) =[ 64.066, -80.197], нормированный градиент (вектор единичной длины, составленный из компонент, деленных на корень из суммы их квадратов) gradн F(M0) = [0.62, -0.78]. Смещаемся в направлении, обратном градиенту (ищем минимум), с выбранным шагом в точку М1=М0-h gradн F(M0)=(2-1 0.62, 1+1 0.78)=(1.38, 1.78) и обнаруживаем, что F(M1)=14 < F(M0).
Аналогичный переход с учетом gradн F(M1) = [0.19, -0.98] приводит в точку М2(1.19, 2.76), где F(M2) 5.26, gradн F(M2) = [-0.96, -0.27]. Переход в очередную точку М3(2.15, 3.03) дает F(M3) 11.33 > F(M2).Соответственно уменьшаем шаг вдвое (h=0.5) и получаем точку М4(2.15, 3.03), где F(M4)=3.78, gradн F(M2) = [0.12, 0.99]. Очередной переход приводит в точку с большим значением функции и приходится еще уменьшать шаг и т.д.
Есть и более эффективные переходы по градиенту, связанные с выбором различного шага по разным координатам или с автоматическим определением шага (при каждом переходе решается задача поиска экстремума функции в заданном направлении). Однако, гарантии нахождения глобального экстремума нет (при разных начальных точках или шагах можно получить разные решения для многоэкстремальных функций).
Градиентные методы для задач с ограничениями, где при смещениях по градиенту приходится сталкиваться с опасностью "выскочить" за пределы допустимого множества решений, существенно усложняются (модифицированный метод Ньютона, методы возможных направлений Зойтендейка, сопряженных градиентов, проектируемых градиентов Розена и др. [43]).
Существует обширная литература по численному анализу, где значительное внимание уделяется градиентным и другим итерационным методам, но тем не менее решение нелинейных задач оптимизации при наличии ограничений иногда весьма затруднительно.
Методы Монте-Карло. Здесь отыскивается n - мерный параллелепипед, включающий в себя множество планов, и затем моделируются N случайных точек с равномерным законом распределения в параллелепипеде (практически во всех программных средах предусмотрено наличие соответствующих датчиков псевдослучайных чисел).
В точках, попавших во множество планов, вычисляются значения функции и запоминается точка текущего экстремума. После этого берется параллелепипед меньших размеров с центром в найденной точке, и в нем вновь моделируются N случайных точек. Процесс такого стохастического моделирования заканчивается при малых размерах параллелепипеда. Методы Монте-Карло имеют преимущество над моделированием на детерминированной сетке, так как их точность имеет порядок
1/ и не зависит от размерности задачи. Естественно, этими методами никто не пользуется при ручном счете; они просты для программной реализации и обычно используются при поиске начального приближения для градиентных методов.
Методы динамического программирования, сводящие многомерную задачу оптимизации к последовательности задач меньшей размерности.
Методы выпуклого программирования, реализующие поиск минимума выпуклой функции или максимума вогнутой на выпуклом множестве планов. Если множество планов - выпуклый многогранник, то эти методы допускают использование симплексного метода.
Наиболее эффективно эти и другие методы решения действуют для так называемых сепарабельных функций, т.е. функций, представимых в виде суммы функций одной переменной
F(X1, X2, .. ,Xn) = f1(X1) + f2(X2) + ... + fn(Xn).
При решении многих задач нелинейного программирования определенный эффект дает метод множителей Лагранжа.
Пусть требуется найти экстремумы функции F(X) при условиях fi(X)=0 (i = 1 .. m).
Функция называется функцией Лагранжа и коэффициенты i - множителями Лагранжа.
Можно доказать, что необходимым условием экстремума исходной задачи является обращение в нуль всех частных производных функции Лагранжа.
Например, при поиске максимума F(X1, X2) = X1+X2 при единственном условии X12+X22=1 строится функция Лагранжа
Строим систему уравнений решение которой дает и экстремальные значения целевой функции .
Для определения типа найденного экстремума можно построить матрицу вторых производных F(X), вычисленных в экстремальной точке, и определить знаки главных ее миноров. Если все они положительны, то найден минимум; если они чередуются, начиная с минуса, то найден максимум (правило Сильвестра).
Сам по себе метод множителей Лагранжа не дает существенного эффекта из-за необходимости решать, как правило, нелинейную систему уравнений; не гарантирует тип отыскиваемого экстремума, кроме глобальных дает и множество локальных экстремумов, но полезен при генерации идей и создании методов нелинейного программирования.
1.3 Методы нелинейного программирования
Суть данного метода заключается в том, что с помощью упомянутого ранее метода покоординатного спуска осуществляется поиск из заданной точки в направлении, параллельном одной из осей, до точки минимума в данном направлении. Затем поиск производится в направлении, параллельном другой оси, и т.д. Направления, конечно, фиксированы. Кажется разумным попытаться модифицировать этот метод таким образом, чтобы на каждом этапе поиск точки минимума производился вдоль "наилучшего" направления. Не ясно, какое направление является "наилучшим", но известно, что направление градиента является направлением наискорейшего возрастания функции. Следовательно, противоположное направление является направлением наискорейшего убывания функции. Это свойство может быть обосновано следующим образом.
Предположим, что осуществляется перемещение из точки x в следующую точку х + hd, где d - некоторое направление, a h - шаг некоторой длины. Следовательно, перемещение производится из точки (x1, х2, ..., хn) в точку (x1 + zx1, x2 + zх2, ..., хn + zхn), где
с точностью до первого порядка zxi, причем частные производные вычисляются в точке x. Как следует выбрать направления di, удовлетворяющие уравнению (1.2), чтобы получить наибольшее значение изменения функции df? Здесь возникает задача максимизации с ограничением. Применим метод множителей Лагранжа, с помощью которого определим функцию .....