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

 

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ 4

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

1.1 Конусы возможных направлений в угловых точках допустимого множества задачи ЛП 5

5

1.2 Конусы, сопряженные к конусам возможных направлений в угловых точках допустимого множества задачи ЛП 6

1.3 Проверка условия оптимальности Куна – Таккера в угловых точках допустимого множества задачи ЛП 6

1.4 Найти точку безусловного экстремума (минимума) методом наискорейшего спуска и методом Ньютона 7

1.5 Метод Нелдера-Мида 11

ОБЩИЙ ВЫВОД 18

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 19

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

В данной работе рассмотрены  различные классы задач математического  программирования и методы их решения:

- первая группа – задачи нелинейного программирования, решаемые различными методами (методом Куна-Таккера, методом наискорейшего спуска, методами Ньютона и Нелдера-Мида);

- ко второй группе задач  относятся – транспортная задача на сети, метод Дворника-Стеклоочистителя.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

Общая задача нелинейного  программирования (ОЗНП) определяется как задача нахождения максимума (или минимума) целевой функции f(x_{, х₂,…, х_п) на множестве D, определяемом системой ограничений где хотя бы одна из функций f  или g_i является нелинейной.

Исходные данные к выполнению курсовой работы:

f=(x₁-10)²+(x₂-12)²+(x₁-10)*(x₂-12)→min

Начальная точка x(0) =(2;5)

Безусловный минимум х* =(10;12)

13x₁+16x₂≤208

x₂≤10

x₁≥0; x₂≥0

1. Конусы возможных направлений в угловых точках допустимого множества задачи ЛП

2

4

6

8

10

12

14

2

4

6

8

10

12

14

y₁

у₂

х₂

х₁

 

 

 

 

 

 

 

 

 

Рисунок 1.1.1

2

4

6

8

10

12

14

2

4

6

8

10

12

14

y₁

у₂

х₂

х₁

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

 

 

 

 

 

 

 

 

 

 

Рисунок 1.1.2

2. Проверка условия оптимальности Куна – Таккера в угловых точках допустимого множества задачи ЛП

Докажем, что существует такая точка λ≥0, при которой  в точке х^* = (10;12) выполняется условие Куна – Таккера.

Экстремум ЦФ находится в точке (48/13;10), *₁=-7,68, *₂=1,124.

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

Проверяем точки: (0;0), (16;0), (0;10), (48/13;10), (2;5),(10;12).

Таблица 1.3.1

	(0;0)	(0;10)	(16;0)	(48/13;10)	(2;5)	(10;12)
	-	+	-	+	-	+
	-	-	+	+	-	+
	+	+	-	+	+	-
	+	+	+	+	+	-

Условие Куна – Таккера выполняется в одной точке (48/13;10).

3. Найти точку безусловного экстремума (минимума) методом наискорейшего спуска и методом Ньютона

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

Таблица 1.4.1

Номер шага	Координаты	Значение функции	Решение
1	(2;5)	169
2	(3;6)	127
3	(5;8)	61
4	(9;12)	1
5	(17;20)	169

 

Оценим точность полученного  решения с помощью метода Золотого сечения.    Точка содержится на отрезке  заменяем на Точка а₀ имеет координаты (3;6), b₀ имеет координаты (17;20).

Шаг 1:

Для оптимального решения  задачи, * должна находится в интервалах 0≤*≤0,5 или 0,5<*≤1, но так как *=1,124, то:

Пусть *=0,6

Т.к. , то минимум функции находятся не на данном отрезке.

Шаг 2:

Т.к. , то минимум функции находятся не на данном отрезке.

 

Шаг 3:

Т.к. , то минимум функции находятся не на данном отрезке.

Шаг 4:

Т.к.  , то минимум функции находятся не на данном отрезке.

Шаг 5:

Т.к.    , то минимум функции находятся не на данном отрезке.

Шаг 6:

Т.к.    , то минимум функции находятся не на данном отрезке.

Шаг 7:

Т.к.    , то минимум функции находятся на данном отрезке.

Найдем точку безусловного экстремума (минимума) методом Ньютона.

Для решения берем вторые частные производные.

           

  

           

 

С помощью метода Ньютона мы получили точку (10;12), которая совпадает с точкой безусловного минимума.

4. Метод Нелдера-Мида

Идея метода состоит в  сравнении значений функции в (n + 1) вершинах симплекса и перемещении  симплекса в направлении оптимальной  точки с помощью итерационной процедуры.

В методе симплекс перемещается с помощью трех основных операций: отражения, растяжения и сжатия.

Шаг 1: Найдем значения функции f₁=f(x₁),f₂=f(x₂) ... f_n+1=f_(хn+1) в вершинах симплекса.

Шаг 2: Найдем наибольшее значение функции f_h, следующее за наибольшим значением функции f_g наименьшее значение функции f_l и соответствующие им точки x_h, x_g, x_l.

Шаг 3: Найдем центр тяжести всех точек, за исключением точки хh. Пусть центром тяжести будет

 

и вычислим f_(x0)=f₀.

Шаг 4:  Удобнее всего начать перемещение от точки x_h. Отразив точку x_h относительно точки х₀, получим точку х_r и найдем f_(xr) = f_r.

 

Рисунок 1.5.1

Шаг 5: Сравним значения функций f_r и f_l.

а. Если f_r < f_l, то мы получили наименьшее значение функции. Направление из точки x₀ в точку x_r наиболее удобно для перемещения. Таким образом, мы производим растяжение в этом направлении и находим точку x_e и значение функции f_e = f_(xe).

 

Рисунок 1.5.2

Если f_e < f_l, то заменяем точку x_h на точку x_e и проверяем (n + 1) -ую точку симплекса на сходимость к минимуму (см. шаг 8). Если сходимость достигнута, то процесс останавливается; в противном случае возвращаемся на шаг 2.

Если f_e > f_l, то отбрасываем точку x_e. Очевидно, мы переместились слишком далеко от точки x₀ к точке x_r. Поэтому следует заменить точку x_h на точку x_r, в которой было получено улучшение (шаг 5, а), проверить сходимость и, если она не достигнута, вернуться на шаг 2.

б. Если f_r > f_l, но f_r < f_g, то x_r является лучшей точкой по сравнению с другими двумя точками симплекса и мы заменяем точку x_h на точку x_r и, если сходимость не достигнута, возвращаемся на шаг 2, т.е. выполняем пункт описанный выше.

в. Если f_r > f_l и f_r > f_g, перейдем на шаг 6.

Коэффициенты в процедуре являются соответственно коэффициентами отражения, сжатия и растяжения.

Шаг 6: Сравним значения функций f_r и f_h.

а. Если f_r > f_h, то переходим непосредственно к шагу сжатия (ниже).

Если f_r < f_h, то заменяем точку x_h на точку x_r и значение функции f_h на значение функции f_r. Запоминаем значение f_r > f_g из шага 4,б, приведенного выше. Затем переходим на шаг 5,б.

б. В этом случае f_r > f_h, поэтому ясно, что мы переместились слишком далеко от точки x_h к точке x₀. Попытаемся исправить это, найдя точку x_c (а затем f_c ) с помощью шага сжатия, показанного на рисунке ниже. Если f_r > f_h, то сразу переходим к шагу сжатия и находим точку x_c из соотношения

 

Рисунок 1.5.3

Если f_r < f_h, то сначала заменим точку x_h на точку x_r, а затем произведем сжатие. Тогда точку x_c найдем из соотношения

 

Рисунок 1.5.4

Шаг 7: Сравним значения функций f_c и f_h.

а. Если f_c < f_h, то заменяем точку x_h на точку x_c и если сходимость не достигнута, то возвращаемся на шаг 2.

б. Если f_c > f_h, то очевидно, что все наши попытки найти значение меньшее f_h закончились неудачей, поэтому мы переходим на шаг 3.

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

Таким образом, точка x_j заменяется на точку

Затем вычисляем f_i для i = 1, 2, ...,(n+1), проверяем сходимость и, если она не достигнута, возвращаемся на шаг 3.

8. Проверка сходимости  основана на том, чтобы стандартное  отклонение (n + 1) -го значения функции было меньше некоторого заданного малого значения е. В этом случае вычисляется

, где

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

Итерация 1

Шаг 1. В качестве вершины многогранника выбираем точки (0;10), (0;10), (16;0). Отражение α=1, сжатие β=0,5, растяжение γ=2.

Шаг 2. Считаем значение функции в выбранных точках и по значениям определяем «наилучшую», «наихудшею» и среднюю:

(0; 10) f(x¹)=(0-10)²+(10-12)²+(0-10)(10-12)=124 – x^g

(0; 0) f(x²)=(0-10)²+(0-12)²+(0-10)(0-12)=244 – x^h

(16; 0) f(x³)=(16-10)²+(0-12)²+(16-10)(0-12)=108 – x^l

Шаг 3. Определяем центр тяжести x⁰:

х⁰ =0,5(x^l+x^g)=0,5(x³+x¹)=(8;5)

f(x⁰)=67

Шаг 4. Выполняем отражение x^h:

x_r= (1+α)x₀-αx_h=(16;10)

f(x_r)= 28

Шаг 5. Т. к. f(x_r)< f(x^l), то выполняем растяжение

x_e= =(24;15)

f(x_e)=247, т.к. f(x_e)≥f(x^l), то x_r=x^h.

Дальнейшие вычисления будут занесены в таблицы 1.5.1 – 1.5.9

Таблица 1.5.1

	Координаты	Значение функции	Итерация 2	f=	56,4
xh	(0;10)	124		sigma=	1335
xg	(16;0)	108
xl	(16;10)	28
х0=	(16;5)	43
хr=	(32;0)	364
xc=	(8;7,5)	33,25