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

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

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

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

0X1	+	3X2	-	2X3		=	3
-4X1	-	2X2	+	1X3		≥	-18
-3X1	+	0X2	-	2X3		≤	-15
4X1	-	1X2	+	3X3		≤	33

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

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

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

0X1	+	3X2	-	2X3	+R1	=	3
4X1	+	2X2	-	1X3	+X4	=	18
-3X1	+	0X2	-	2X3	+X5	=	-15
4X1	-	1X2	+	3X3	+X6	=	33

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

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

Таблица 2.1

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

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

Базисные переменные	Свободные члены	X5	X2	X3
R1	3	0	3	-2
X4	-2	1.333	2	-3.667
X1	5	-0.333	0	0.667
X6	13	1.333	-1	0.333
F	-5	0.333	-3	4.333
M	-3	0	-3	2

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

Базисные переменные	Свободные члены	X5	X2	X4
R1	4.091	-0.727	1.909	-0.545
X3	0.545	-0.364	-0.545	-0.273
X1	4.636	-0.091	0.364	0.182
X6	12.818	1.455	-0.818	0.091
F	-7.364	1.909	-0.636	1.182
M	-4.091	0.727	-1.909	0.545

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

Базисные переменные	Свободные члены	X5	X4
X2	2.143	-0.381	-0.286
X3	1.714	-0.571	-0.429
X1	3.857	0.048	0.286
X6	14.571	1.143	-0.143
F	-6	1.667	1
M	0	0	0

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

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

x₆=14.571; x₃ =1.714; x₂=2.143; x₁=3.857; F_max=-6.