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

ФГБОУ ВПО

Сибирский государственный университет путей сообщения

Кафедра   «Системный анализ и управление проектами»

 

Решение задач линейного программирования,

и задач транспортного типа

 

РГР 5

по дисциплине «Экономико-математические модели в логистике»

 

 

 

            

                   Руководитель                                                                               Разработал

                        доцент                                                                                     студент гр. МЛ-213

 

                   ________________Зайцева Т.С.             __________________Массон О.Д.

                        (подпись)                     (подпись)

                   _____________                                                    __________

     (дата проверки)                                                      (дата сдачи на проверку)

 

Краткая рецензия:

____________________________________________________________________

____________________________________________________________________

____________________________________________________________________

____________________________________________________________________

____________________________________________________________________

____________________________________________________________________

____________________________________________________________________

 

 

 

 

 

_________________________________

        (запись о допуске к защите)

________________________________        _________________________________

        (оценка по  результатам защиты)                         (подписи преподавателей)

 

 

2014 год

Содержание

1. Введение                                                                      5

2. Общая задача нелинейного программирования              6

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

4. Метод наискорейшего спуска                                                 10

5. Метод золотого сечения                                                          12

6. Метод Ньютона                                                                         16

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Задача нелинейного программирования встречается в естественных науках, технике, экономике, математике, в науке управления государством.

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

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

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

Целью расчётно-аналитической работы является решение задач нелинейного программирования различными методами для проведения анализа поведения этих методов на выбранных математических моделях нелинейного программирования.

Для достижения поставленной цели необходимо выполнить следующее:

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

- проверить условие оптимальности  Куна-Таккера в угловых точках ДМЗ;

- найти точку безусловного  экстремума для заданной ЦФ  и начальной точки;

- найти решение задачи  выпуклого программирования методом  Нелдора-Мида.

МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

                    1.Общая задача нелинейного программирования

Как известно, общая задача математического программирования формулируется следующим образом: найти вектор Х=(х1, х2, ..., хn) удовлетворяющий системе ограничений gi (х1, х2, ..., хn)=bi, i=l, 2, ..., k; gi(х1, х2, ..., хn)£bi, i=k+l, k+2, ..., m    и доставляющий экстремум функции Z=f(х1, х2, ..., хn).  При этом предполагается, что известны функции gi(х1, х2, ..., хn) и f(х1, х2, ..., хn). Обычно на некоторые переменные х1, х2, ..., хn накладывается условие неотрицательности. Кроме того, ограничением может служить условие целочисленности решения для ряда переменных. Если gi(х1, х2, ..., хn)=, i=1, 2, ..., m,    (2.3) и Z=f(х1, х2, ..., хn) .  где aij и Cj - известные константы, то при условии неотрицательности решения получаем задачу линейного программирования. Любую другую задачу математического программирования, не удовлетворяющую вышеуказанным условиям, условимся считать нелинейной. Класс задач нелинейного программирования шире класса задач линейного программирования. Подробное изучение практических задач, которые условились считать линейными, показывает, что они в действительности являются нелинейными. Возникает задача нахождения эффективных методов решения задач нелинейного программирования. Существующие методы позволяют решать узкий класс задач, ограничения которых имеют вид gi(х1, х2, ..., хn)=, i=1, 2, ..., m, а целевая функция сепарабельная (является суммой n функций jj(xj)) или квадратическая. Даже если область допустимых решений выпуклая, то в ряде задач целевая функция может иметь несколько локальных экстремумов. С помощью большинства же вычислительных методов можно найти точку локального оптимума, но нельзя установить, является она точкой глобального (абсолютного) оптимума или нет. Если в задачах линейного программирования точка экстремума является вершиной многогранника решений, то в задачах нелинейного программирования она может лежать в вершине многогранника, на ребре (грани) или внутри области. Если задача содержит нелинейные ограничения, то область допустимых решений не является выпуклой, и кроме глобального оптимума могут существовать точки локального оптимума.  
В краткой форме задачу Н. п. можно записать так:

F (x) → max при условиях g (x) ≤ b, x ≥ 0,

где x — вектор искомых переменных; F (x) — целевая функция; g (x) — функция ограничений (непрерывно дифференцируемая); b — вектор констант ограничений (выбор знака ≤ в первом условии здесь произволен, его всегда можно изменить на обратный).

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

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

2.3. Построение   конусов возможных направлений и конусов, сопряжённых к конусам возможных направлений

Алгоритм построения:

1. Находим ОДР задачи ЛП.
2. Строим конусы в угловых точках допустимого множества задачи ЛП так, чтобы ребра конуса были перпендикулярно пересекающимся линиям.

 φ(х) = (х1-10)2 +(х2 -5)2 + (х1-10)*( х2-5)        min

11х1 + 12х2 ≥ 132

х1 ≥6

Х1≥0, х2≥0

                      

 

 

 

 

 

График 1

 

График 2

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

Необходимым и достаточным условием оптимальности Куна-Таккера для задачи НЛП является:

 x(0) λ(0) ≤ 0

 x(0) λ(0) ≤ 0

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

Условие линейной независимости всегда выполняется для задач нелинейного программирования, обладающих следующими свойствами:

• все ограничения в виде равенств и неравенств содержат линейные функции;
• все ограничения в виде неравенств содержат вогнутые функции, все ограничения-равенства – линейные функции, а также существует по крайней мере одна допустимая точка х, которая расположена во внутренней части области, определяемой ограничениями-неравенствами. Другими словами, существует такая точка , что

Если условие линейной независимости в точке оптимума не выполняется, то задача Куна – Таккера может не иметь решения.

Замечание. Нарушение условия линейной независимости не обязательно означает, что точка Куна – Таккера не существует.

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

Имеем из дано целевую функцию:

φ(х) = (х1-10)2 +(х2 -5)2 + (х1-10)*( х2-5)        min

11х1 + 12х2 ≤ 132

х1 ≤6

Х1≥0, х2≥0

 

= 2x1 + x2 -25;

= 2x2 + x1 -20;

= 11х1 +12х2-132  ;

= х1 -6 ;                                                             

Проверяем усл.Куна-Таккера на выполнение условия:

 ≤ 0;   ≥ 0

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

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

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

Таблица 4.1

	(0;5)	(10;5)	(0;11)	(5,5;6)
	+	+	+	+
	+	+	-	+
	-	+	+	+
	-	+	-	-

 

 

Вывод: при проверке условия Куна-Таккера выяснилось, что условие выполняется в точках с координатами (10;5).

 

5.  Метод наискорейшего  спуска

 

Стратегия решения задачи состоит в построении последовательности точек  , k=0, 1, 2, ... таких, что  , k=0, 1, 2, .... Точки последовательности  вычисляются по правилу: 
 

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

Алгоритм метода. 
Начальный этап:

- Задать  , . 
- Найти градиент функции в произвольной точке  
 
Положить k=0. 
Основной этап: 
Шаг 1. Вычислить 

Шаг 2. Проверить выполнение критерия останова

а) если критерий выполнен, расчет окончен,

б) если критерий не выполнен, то перейти к шагу 3.

Шаг 3. Вычислить величину шага    из условия

Шаг 4. Вычислить

Шаг 5. Положить k= k +1 и перейти к шагу 1

№ итерации	Расчеты	Результат
1	Х0 = (0;5) (0-10)2+(5-5)2+(0-10)(5-5) =	(0;5) 100
2	H = 20   (1;6) (1-10)2+(6-5)2+(1-10)(6-5) =	(1;6) 73
3	H = 21 (3;8) (3-10)2+(8-5)2+(3-10)(8-5) =	(3;8) 37
4	H = 22 (7;12) (7-10)2+(12-5)2+(7-10)(12-5)=	(7;12) 42
5	H = 23 (15;20) (15-10)2+(20-5)2+(15-10)(20-5)	(15;20) 325

 

Вывод: значение целевой функции до 3 итерации уменьшается, а после  3 итерации  увеличилось. Точка минимума находится на интервале между точками (1;6) и (7;12), при этом значение целевой функции 73 и 42 соответсвенно. Точка минимума целевой функции имеет координаты (3;8).

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

5.1. Метод золотого  сечения

Метод золотого сечения — метод поиска экстремума действительной функции одной переменной на заданном отрезке. В основе метода лежит принцип деления отрезка в пропорциях золотого сечения. Является одним из простейших вычислительных методов решения задач оптимизации. Впервые представлен Джеком Кифером в 1953 году.