2.3 Получение целочисленного решения путем введения дополнительных ограничений по методу Гомори

Если решение хотя бы одной из задач не целочисленное найти целочисленное решение задачи используя алгоритм Гомори. Найдем частично целочисленное решение для двойственной задачи. Дополнительное ограничение построим по строке y₃, так как ее свободный член имеет наибольшую дробную часть.

Базисные переменные	Свободные члены	Y6	Y7	Y5	Y4
Y3	1.667	0.381	0.571	-0.048	-1.143
Y1	0.333	-0.524	-0.286	0.19	-0.429
Y2	1	0.286	0.429	-0.286	0.143
F	6	2.143	1.714	3.857	14.571
Y8	-0.667	-0.381	-0.571	-0.096	-0.286

Базисные переменные	Свободные члены	Y6	Y8	Y5	Y4
Y3	1	0	1	-0,144	-1,429
Y1	0,667	-0,33	-0.5	0,238	-0,285
Y2	0.5	0	0.75	-0,358	-0,071
F	4	1	3	3,569	13,712
Y7	1.168	0.667	-1.751	0,168	0,5

С помощью алгоритма Гомори построения дополнительных ограничений для частично целочисленных задач получили следующее частично целочисленное решение:

y₂=0,5; y₁=0,667; y₃=1; y₇=1,168; F_min=-4.

3 Нелинейное программирование

3.1 Построение ОДЗП, выбор начальной точки поиска

Целевая функция имеет вид:

F(x)= x₁²+x₂²-x₁x₂-8x₁+7x₂ (min).

3x₁ -x₂-40

x₁+3x₂-180

x_1,20

x⁰=[1;5].

Построим ОДЗП:

Рисунок 3.1 - ОДЗП

Внутри области допустимых значений выбираем точку x⁰, которая в дальнейшем будет являться начальной в процессе поиска экстремума:

x⁰=(1;5).

3.2 Нахождение экстремального значения функции F(x) без учета ограничений на переменные

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

F(x)= x₁²+x₂²-x₁x₂-8x₁+7x₂ (min).

3x₁ -x₂-40

x₁+3x₂-180

x_1,20

x⁰=[1;5].

В методе наискорейшего спуска (подъема) очередная точка при поиске максимума функции вычисляется по формуле:

где направление движения задается вектором антиградиента функцииF(x), вычисленном в точке, а величина шага перемещения определяется числовым параметром.

Найдем градиент :

.

Осуществляем движение из точки x ⁰ вдоль градиента F(x⁰) в новую точку x¹.

Подставляем координаты точки x¹ в функцию F(x),

Затем найдем , в которой функцияF(x) будет иметь экстремум. Для этого найдем производную :

В результате после первого шага координаты очередной точки

получаются равными:

Продолжаем поиск по тому же алгоритму.

Второй шаг:

x ²= x ¹ +α¹F(x ¹)

Третий шаг:

F_min = -18.995

Так как значение градиента уменьшается то реальный экстремум может быть достигнут на следующих шагах.

Графическая интерпретация:

Рисунок 3.2 – Графическая интерпретация метода наискорейшего спуска

3.2.2 Метод Ньютона-Рафсона

Условие задания:

F(x)= x₁²+x₂²-x₁x₂-8x₁+7x₂ (min).

x⁰=[1;5].

Очередная точка вычисляется в соответствии с выражением

x ^k+1= x ^k –H^-1(x ^k)F(x ^k),

где H(x ) – матрица Гессе функции F(x);

H^-1(x) – обратная по отношению к H(x) матрица.

Найдем градиент функции в точке x ⁰: F(x ⁰)=[-11;16].

Запишем матрицу Гессе:

Найдем очередную точку x ¹:

Найдем градиент в точке x ¹

F (x ¹)^T=[0;0].

Следовательно, в точке x ¹ функция F(х) достигает минимума. F_min = -19.