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

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