Особенности задач нелинейного программирования

Особенности задач нелинейного программирования

 

 

 

 

Оглавление

Введение 3

Глава I. Постановка задачи. Методы решения 5

1.1. Постановка  задачи математического программирования 5

1.2. Методы  решения 7

1.2.1. Градиентные  методы 7

1.2.2 Методы  Монте-Карло 8

1.2.3. Методы  выпуклого программирования 9

1.2.4. Теорема  Куна-Таккера 10

1.2.5. Квадратичное  программирование. Метод Вулфа-Фрэнка 12

1.2.5. Дробно-линейное  программирование 17

Глава II. Решение  задачи нелинейного программирования средствами электронных таблиц 20

2.1. Постановка  задачи 20

2.2. Решение  задачи методом Франка-Вульфа 21

2.3. Решение  задачи средствами электронных  таблиц MS Excel 25

Заключение 27

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

 

Введение

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

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

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

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

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

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

Объект исследования: нелинейное программирование

Предмет исследования: методы решения задача нелинейного  программирования.

 

Глава I. Постановка задачи. Методы решения

1.1. Постановка  задачи математического программирования

Задачи математического  программирования формулируются следующим  образом: найти экстремум некоторой  функции многих переменных f (x1, x2,…, xn) при ограничениях gi (x1, x2,…, xn) bi, где gi – функция, описывающая ограничения, а bi – действительное число, i = 1,…, m. Функция f называется функцией цели (целевой функцией).

В общем, виде задача нелинейного программирования состоит в определении максимального (минимального) значения функции f(x1, x2, …, xn) при условии, что ее переменные удовлетворяют соотношениям:

 

где f и g – некоторые известные функции n переменных, а bi – заданные числа.

В результате решения задачи будет определена точка Х*= (x1*, x2*, …, xn*), координаты которой удовлетворяют соотношениям и такая, что для всякой другой точки Х= (x1, x2, …, xn), удовлетворяющей условиям, выполняется неравенство f (x1*, x2*, …, xn*) ≥ f (x1, x2, …, xn) [f (x1*, x2*, …, xn*) ≥ f (x1, x2, …, xn)].

Если f и gi – линейные функции, то задача является задачей линейного программирования.

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

В евклидовом пространстве Еn система ограничений определяет область решений задачи. В отличие от задачи линейного программирования она не всегда является выпуклой.

Если определена область допустимых решений, то нахождение решения задачи сводится к определению  такой точки этой области, через  которую проходит гиперповерхность наивысшего (наименьшего) уровня: f (x1, x2, …, xn) = h. Указанная точка может находиться как на границе области допустимых решений, так и внутри неё.

Существующие  методы нелинейного программирования можно подразделить на следующие  основные классы.

 

1.2. Методы  решения 

1.2.1. Градиентные  методы

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

Так при отсутствии ограничений одна из простейших разновидностей градиентных  методов - метод наискорейшего спуска предлагает выбрать некоторую точку (план) 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]. Очередной переход приводит в точку с большим значением функции и приходится еще уменьшать шаг и т.д.

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

Градиентные методы для задач с ограничениями, где при смещениях по градиенту  приходится сталкиваться с опасностью "выскочить" за пределы допустимого  множества решений, существенно  усложняются (модифицированный метод  Ньютона, методы возможных направлений  Зойтендейка, сопряженных градиентов, проектируемых градиентов Розена и др.

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

 

1.2.2 Методы  Монте-Карло

В данных методах  отыскивается n - мерный параллелепипед, включающий в себя множество планов, и затем моделируются N случайных точек с равномерным законом распределения в параллелепипеде (практически во всех программных средах предусмотрено наличие соответствующих датчиков псевдослучайных чисел).

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

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

 

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

Эти методы реализуют  поиск минимума выпуклой функции  или максимума вогнутой на выпуклом множестве планов. Если множество  планов - выпуклый многогранник, то эти  методы допускают использование  симплексного метода.

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

F(X1, X2, .. ,Xn) = f1(X1) + f2(X2) + ... + fn(Xn).

При решении  многих задач нелинейного программирования определенный эффект дает метод множителей Лагранжа.

Пусть требуется  найти экстремумы функции F(X) при  условиях fi(X)=0 (i = 1 .. m).

Функция называется функцией Лагранжа и коэффициенты li - множителями Лагранжа.

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

Например, при  поиске максимума F(X1, X2) = X1+X2 при единственном условии X12+X22=1 строится функция Лагранжа

Строим систему  уравнений, решение которой дает и экстремальные значения целевой  функции. Для определения типа найденного экстремума можно построить матрицу  вторых производных F(X), вычисленных  в экстремальной точке, и определить знаки главных ее миноров. Если все  они положительны, то найден минимум; если они чередуются, начиная с  минуса, то найден максимум (правило  Сильвестра).

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

 

1.2.4. Теорема  Куна-Таккера

Пусть стоит  задача минимизации F(X) при условиях:

 

где X - n-мерный вектор, F(X) и fi(X) - выпуклые функции, что обеспечивает выпуклость множества планов и единственность искомого минимума (напомним, что мы считаем функцию выпуклой в некоторой точке, если главные миноры матрицы вторых производных положительны).

Введем функцию  Лагранжа

 

Теорема Куна-Таккера утверждает, что вектор X*³0 является решением поставленной задачи тогда и только тогда, когда существует вектор l* ³0 такой, что при всех X ³ 0, l³0

Так как функция  Лагранжа в точке (X*, l*) принимает минимум по X и максимум по l, то эта точка называется седловой и эта теорема называется теоремой о седловой точке или теоремой о минимаксе.

Достаточность условий этой теоремы доказывается сравнительно просто. Доказательство их необходимости предполагает выполнение условий регулярности, т.е. существования  хотя бы одной допустимой точки X, где  fi(X) < 0 при всех i.

Если F(X) и  fi(X) дифференцируемы, то условия теоремы эквивалентны «локальным» условиям, утверждающим, что в точке (X*, l*)

 

Остановимся на частных случаях задачи.

Если в  поставленной задаче отсутствуют требования неотрицательности (2), то путем замены X разностью двух неотрицательных векторов можно показать, что условие (5) упрощается к виду (если нет требования неотрицательности для одной из компонент X, то обратится в нуль производная Ф(X) по соответствующей переменной).

Если fi(X) = 0 при некотором i, то заменой этого равенства системой неравенств fi(X) £ 0, -fi(X) £ 0 обнаруживаем, что в (6) соответствующая производная обращается в нуль и исчезает условие неотрицательности по i; если fi(X) = 0 при всех i, то (6) упрощается к виду

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

Так при минимизации CTX при условиях AX ³ B, X ³ 0 функция Лагранжа имеет вид

Ф(X, l) = CTX + lT(AX - B)

и условия  Куна-Таккера

 

Отсюда получаем с учетом XTC = CTX, lTB = BTl, XTAT l = lTAX, что в седловой точке достигается минимум по X и максимум по , причем

CTX = BTl,

AX ³ B, ATl £ C,

X ³ 0, l ³ 0.

 

1.2.5. Квадратичное  программирование. Метод Вулфа-Фрэнка

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

 

где A - матрица  размерности m на n , C, X - n-мерные векторы, B - m-мерный вектор, D - положительно-определенная n-мерная квадратная матрица (матрица называется положительно определенной, если положительны ее главные миноры). Так целевая функция

 

представится  в виде (1), где 

 

Положительная определенность матрицы D и линейность ограничений (множество планов выпукло) позволяют использовать теорему  Куна-Таккера.

Функция Лагранжа здесь имеет вид:

 

и условия  Куна-Таккера приводятся к форме:

 

Если ввести векторы ослабляющих переменных, то (4) - (5) примут вид:

 

С учетом неотрицательности переменных можно поставить задачу минимизации (до нуля) функции

 

 

при условиях

 

Если обозначить

 

то (7) - (9) приведутся к виду:

 

где

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

Здесь отыскивается некоторый опорный план W0. Если g(W0) = 0, то этот план оптимален. В противном случае отыскивается градиент

 

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