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

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

2.1 Математическая модель задачи. Нахождение оптимального плана  х* и экстремального значения  функции

 

Найти минимальное значение функции  F(X)=-6X₁-2X₂-6X₃ (max)

при следующих  ограничениях:

 

0X1	+	2X2	-	6X3		=	-12
0X1	-	5X2	-	4X3		≥	-27
-4X1		-3X2	+	2X3		≤	-15
1X1	+	2X2	-	4X3		≤	-3

x_j³0 (j=1...3)

 

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

Для начала необходимо привести ограничения к  виду равенств. Для этого необходимо ввести дополнительные переменные x₄, x₅, x₆ и искусственную переменную R₁.

0X1	+	2X2	-	6X3	+R1	=	-12
0X1	-	5X2	-	4X3	+X4	=	27
-4X1	-	3X2	+	2X3	+X5	=	-15
1X1	+	2X2	-	4X3	+X6	=	-3

x_j³0 (j=1...3)

 

 

Пусть R, x₄, x₅, x₆ – базисные переменные, а x₁, x₂, x₃ – небазисные. Функция цели            F(X)= 3X₁+0X₂+2X₃  -M·R₁ (min)

Составим  симплекс таблицу

Таблица 2.1

Базисные  переменные	Свободные  члены	X1	X2	X3
R1	-12	0	2	-6
X4	27	0	-5	-4
X5	-15	-4	-3	2
X6	-3	1	2	-4
F	42	6	2	6
M	12	0	-2	6

 

 

 

 

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

Базисные  переменные	Свободные  члены	X5	X2	X3
R1	-12	0	2	-6
X4	27	0	-5	-4
X1	3.75	-0.25	0.75	-0.5
X6	-6.75	0.167	1.25	-3.5
F	64.5	1.5	-2.5	9
M	12	0	-2	6

 

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

Базисные  переменные	Свободные  члены	X6	X2
Х3	2	0	-0.333
X4	35	0	-6.333
X1	4.75	-0.25	0.583
X6	0.25	0.167	0.083
F	46.5	1.5	0.5
M	0	0	0

 

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

Тогда решение  данной задачи:

X₁=4.75; x₃ =2; x₄=35;  x₆=0.25; F_max=46.5.

 

 

2.2 Построение и решение  задачи, двойственной к исходной. Сравнение решения прямой и двойственной задач

 

Рассмотрим соотношение  прямой и двойственной задач:

 

                                              (2.2)

 

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

 

Исходная  задача:

 

Найти максимальное значение функции  F(X)=-6X₁-2X₂-6X₃ (max)

 

 

0X1	+	2X2	-	6X3	+R1	=	-12
0X1	-	5X2	-	4X3	+X4	=	27
-4X1	-	3X2	+	2X3	+X5	=	-15
1X1	+	2X2	-	4X3	+X6	=	-3

x_j³0 (j=1...3)

 

 

Строим двойственную задачу:

Так как в  прямой задаче требуется найти минимум  функции, то приведем первоначальное условие  к виду 
{F(x) = B^T x| A^T x≥C, x_j ≥0, j = 1,m}

Для достижения нужного вида домножим 2-e неравенство на -1 
В результате получим следующие матрицы:

Транспонируем матрицу A:

Поменяем  местами вектора B и C:

 

Двойственная  задача будет иметь 4 переменные, так  как прямая содержит 4 ограничения. В соответствии запишем двойственную задачу в виде: 

 

 

 

F(Y)=-12Y₁+27Y₂-15Y₃-3Y₄ (max)

 

 

Так как  в прямой задаче есть ограничение  равенство, то на у₁, соответствующая переменная двойственной задачи, не накладывается условие неотрицательности.

Ограничения:

0Y1	+	0Y2	-	4Y3	+	1Y4		≥	0
2Y1	-	5Y2	-	3Y3	+	2Y4		≥	0
-6Y1	-	4Y2	+	2Y3	-	4Y4		≥	0

Y1	≥	0
Y2	≥	0
Y3	≥	0
Y4	≥	0

 

Введем дополнительные переменные Y₅, Y₆, Y₇.  
Ограничения примут вид:

0Y1

+

0Y2

-

4Y3

+

1Y4

+ Y5

≥

0

2Y1

-

5Y2

-

3Y3

+

2Y4

+ Y6

≥

0

-6Y1

-

4Y2

+

2Y3

-

4Y4

+ Y7

≥

0

Y_i≥0 
Составим симплекс-таблицу:

Базисные  переменные	Свободные  члены	Y1	Y2	Y3	Y4
Y5	-6	0	0	-4	1
Y6	-2	2	-5	-3	2
Y7	-6	-6	-4	2	-4
F	42	-12	27	-15	-3

 

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

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

Базисные  переменные	Свободные  члены	Y7	Y2	Y3	Y4
Y5	-6	0	0	-4	1
Y6	-4	0.333	-6.333	-2.333	0.667
Y1	1	-0.167	-0.667	0.333	-0.667
F	54	-2	35	-19	5

 

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

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

Базисные  переменные	Свободные  члены	Y7	Y2	Y5	Y4
Y3	1.5	0	0	-0.25	-0.25
Y6	-0.5	0.333	-6.333	-0.583	0.084
Y1	-0.5	-0.167	-0.667	0.083	-0.584
F	82.5	-2	35	-4.75	0.25

 

 

 

 

 

 

 

 

 

 

 

 

Для нахождения ведущей строки найдем максимальный по модулю отрицательный свободный  член (-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 = .