Задания (стр. 2 )

Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5	x6
x2	2	0	1	0	1	-1	0
x3	2	1	0	1	-2	3	0
x6	3	2	0	0	1	-2	1
F(X3)	-30	-6	0	0	0	-5	0

Оптимальный план можно записать так:

x2 = 2

x3 = 2

x6 = 3

F(X) = -10•2 + -5•2 = -30

3. Решить задачу с помощью двойственной и методом добавления искусственного базиса

Решение:

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

Определим минимальное значение целевой функции F(X) = 2x1+8x2+2x3-6x4 при следующих условиях-ограничениях:

-x1+x2+x3-3x4=1

x1+x2-2x3-2x4=-2

Введем искусственные переменные x: в 1-м равенстве вводим переменную x5; в 2-м равенстве вводим переменную x6;

-1x1 + 1x2 + 1x3-3x4 + 1x5 + 0x6 = 1

1x1 + 1x2-2x3-2x4 + 0x5 + 1x6 = -2

Для постановки задачи на минимум целевую функцию запишем так:

F(X) = 2x1+8x2+2x3-6x4+Mx5+Mx6 => min

Из уравнений выражаем искусственные переменные:

x5 = 1+x1-x2-x3+3x4

x6 = -2-x1-x2+2x3+2x4

которые подставим в целевую функцию:

F(X) = (2)x1+(8-2M)x2+(2+1M)x3+(-6+5M)x4+(-1M) => min

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Решим систему уравнений относительно базисных переменных:

x5, x6,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,0,1,-2)

Базис	В	x1	x2	x3	x4	x5	x6
x5	1	-1	1	1	-3	1	0
x6	-2	1	1	-2	-2	0	1
F(X0)	-1M	-2	-8+2M	-2-1M	6-5M	0	0

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-2).

Базис	В	x1	x2	x3	x4	x5	x6
x5	1	-1	1	1	-3	1	0
x6	-2	1	1	-2	-2	0	1
F(X0)	-1M	-2	-8+2M	-2-1M	6-5M	0	0
θ	0	-	-			-	-

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис	В	x1	x2	x3	x4	x5	x6
x5	0	-0.5	1.5	0	-4	1	0.5
x3	1	-0.5	-0.5	1	1	0	-0.5
F(X0)	2	-3-0.5M	-9+1.5M	0	8-4M	0	-1-0.5M

В базисном столбце все элементы положительные.

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент.

Вычислим значения Di по строкам как частное от деления: bi / ai2

и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (1.5) и находится на пересечении ведущего столбца и ведущей строки.

Базис	В	x1	x2	x3	x4	x5	x6	min
x5	0	-0.5	1.5	0	-4	1	0.5	0
x3	1	-0.5	-0.5	1	1	0	-0.5	0
F(X1)	2	-3-0.5M	-9+1.5M	0	8-4M	0	-1-0.5M	0

После преобразований получаем новую таблицу:

Базис	В	x1	x2	x3	x4	x5	x6
x2	0	-0.33	1	0	-2.67	0.67	0.33
x3	1	-0.67	0	1	-0.33	0.33	-0.33
F(X1)	2	-6	0	0	-16	6-1M	2-1M

Конец итераций: индексная строка не содержит положительных элементов - найден оптимальный план