Линейное программирование

 

 

 

 

 

 

 

 

 

 

 

 

Для нахождения ведущей строки найдем максимальный по модулю отрицательный свободный  член (-3). Ведущая строка - Y₆. В строке Y₆ так же найдем максимальный по модулю отрицательный свободный член (-3). Столбец Y₁- ведущий.

 
Пересчитаем таблицу

Базисные  переменные	Свободные  члены	Y7	Y2	Y5	Y1
Y3	1.5	0	0	-0.25	-0.25
Y6	0.08	-0.053	-0.158	0.092	-0.013
Y4	-0.45	-0.2	0.11	0.144	-0.592
F	79.7	-0.16	5.53	-8.75	0.71

 

Для нахождения ведущей строки найдем максимальный по модулю отрицательный свободный  член (-3). Ведущая строка - Y₆. В строке Y₆ так же найдем максимальный по модулю отрицательный свободный член (-3). Столбец Y₁- ведущий.

 
Пересчитаем таблицу

Базисные  переменные	Свободные  члены	Y7	Y2	Y5	Y4
Y3	1.69	0.08	-0.05	-0.31	-0.42
Y6	0.09	-0.049	-0.16	0.089	-0.022
Y1	0.76	0.338	-0.186	-0.243	-1.689
F	79.2	-0.4	5.66	-8.58	1.2

 

Так как  в столбце свободных членов нет  отрицательных элементов, то найдено  допустимое решение. Так как в  строке F есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца  найдем максимальный по модулю отрицательный элемент в строке F (-9). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца. Столбец Y₁- ведущий.

 

Y₃=1.69; y₆=0.9; y₁=0.76; F_min=79.2.

 

F_max(x)=F_min(y)=79.2

 

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

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

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

F(x)= -3x₁²-6x₂²-4x₁x₂+1x₁-3x₂ (min).

3x₁ -8x₂ +8  £0

x₁+8x₂-40£0

 x_1,2³ 0

x⁰=[3;2].

    

 

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

 

 

 

 

 

 

 

 

 

6

 

 

4

 

 

 

2

 

 

 

 

0

9

7

6

3

 

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

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

 

x⁰=(3;2).

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

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

F(x)= -3x₁²-6x₂²-4x₁x₂+1x₁-3x₂ (min).

3x₁ -8x₂ +8  £0

x₁+8x₂-40£0

 x_1,2³ 0

x⁰=[3;2].

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

 

 

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

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

 

.

 

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

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

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

 

=

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

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

       

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

Второй шаг: 

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

 

=

Третий шаг:

=

 

F_min = 0.793

 

 

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

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

F(x)= -3x₁²-6x₂²-4x₁x₂+1x₁-3x₂ (min).

x⁰=[3;2].

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

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

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

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

.

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

Тогда AdjH=

H^-1= , где detH– определитель матрицы H.

detH = -6∙(-12) – (-4)∙(-4) = 72 – 16 = 56.

 

H^-1 = ;

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

;

 

F_max = 0.793;

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

 

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

 

 

3.3.1  Метод линейных комбинаций

F(x)= -3x₁²-6x₂²-4x₁x₂+1x₁-3x₂ (min).

3x₁ -8x₂ +8  £0

x₁+8x₂-40£0

 x_1,2³ 0

x⁰=[3;2].

Первая итерация.

Зададимся точностью 

Вычисляется вектор-градиент

Осуществляется линеаризация F(x) относительно точки x⁰ в соответствии с выражением

Решается задача ЛП

min{-25x₁-39x₂ |3x₁ -8x₂£-8; x₁+8x₂£ 40;x_1,2³0}.

 

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

 

 

БП	СЧ	НП
		x1	x2
x3	-8	3	-8
x4	40	1	8
F	0	-25	-39

 

 

БП	СЧ	НП
		X4	X2
X3	1	-0.375	-0.125
X1	32	4	1
F	39	-39.6	-4.875

 

БП	СЧ	НП
		X4	X3
X2	4	-0.094	-0.031
X1	8	0.25	-0.25
F	355.8	9.9	5.025

 

 

 

Найдено оптимальное решение

_{Wmin=355.8; x=[8   4]}

Далее производится корректировка  найденного решения в соответствии с выражением

Или

 

Так как значение в шаге не может превышать 1 по абсолютному значению, то примем

 

3.3.2 Условия теоремы Куна-Таккера

F(x)= -3x₁²-6x₂²-4x₁x₂+1x₁-3x₂ (min).

3x₁ -8x₂ +8  £0

x₁+8x₂-40£0

 x_1,2³ 0

x⁰=[3;2].

Прежде, чем  составить функцию Лагранжа, нужно  привести ограничения к нулевой  правой части. Анализируем экстремум: так как в условии минимум, то будет минимум по x и максимум по λ.

Тогда и и

g₁(x)= 3x₁ -8x₂+8 £0

g₂(x)= x₁+8x₂-40£0

Тогда L(x, λ)= -6x₁²-12x₂²-4x₁x₂+1x₁-3x₂ + λ₁ (3x₁ -8x₂+8)+ λ₂ (x₁+8x₂-40)

Найдем 

 

 

-4x₂-6x₁+3λ₁-8λ₂ +1v₁=0             4x₂+6x₁ -3λ₁+8λ₂ +v₁=8  

-12x₁+4x₂+λ₁ +8λ₂ -3v₂=56               12x₁+4x₂-8λ₁ +3λ₂+v₂=-40

3x₁-8x₂+w₁=-8      3x₁-8x₂+w₁=-8

x₁+8x₂+w₂=40     x₁+8x₂+w₂=40

 

СЛАУ с неизвестными x₁, x₂, λ₁, λ₂, v₁, v₂, w₁, w₂.

x_1,2 ³0; λ_1,2³0; v_1,2³0; w_1,2³0.

 Решив эту систему с помощью  симплекс-метода, мы можем найти  допустимое базисное решение и то решение, которое удовлетворяет  x^Tv=0 и λ^Tw=0 или         x₁ v₁= x₂v₂=0

                           λ₁ w₁=λ₂w₂=0

 

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

БП	СЧ	НП
		x1	x2
v1	1	6	4	-3	8
v2	-3	12	4	-8	3
w1	-8	3	-8	0	0
w2	40	1	8	0	0

 

БП	СЧ	НП
		x1	W1
v1	-3	7.5	0.5	-3	8
v2	-7	10.5	0.5	-8	3
X2	1	-0.375	-0.125	0	0
w2	32	4	1	0	0

 

БП	СЧ	НП
		x1	W1	v2
v1	0	1.5	0.3	-0.375	6.9
	0.875	-1.3	-0.06	-0.125	-0.375
X2	1	-0.375	-0.125	0	0
w2	32	4	1	0	0

 

Таким образом, получили решение:

W₂ = 0, v₁ =0.875, v₂ =1, x₂= 32.

Исходя из полученного решения, определим экстремум функции:

F_min = .