Контрольная 1, вариант 3 Задание Введите переменные

• Название: Контрольная 1, вариант 3 Задание Введите переменные
• Дата: 13.02.2018
• Размер: 147.28 Kb.
• Имя файла: Kontrolnaya_1.docx
• Тип: Решение; #36389
• страница: 4 из 7

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

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

Базис	B	x1	x2	x3	x4	x5	x6	min
x4	0	0	4	0	1	3	0	0
x1	10	1	-1	0	0	-1	0	-
x6	70	0	0	1	0	0	1	-
F(X1)	0	0	-2	0	0	-3	0	0

Вместо переменной x₄ в план 1 войдет переменная x₅.

Строка, соответствующая переменной x₅ в плане 1, получена в результате деления всех элементов строки x₄ плана 0 на разрешающий элемент РЭ=3.

Представим расчет каждого элемента в виде таблицы:

B	x1	x2	x3	x4	x5	x6
0 : 3	0 : 3	4 : 3	0 : 3	1 : 3	3 : 3	0 : 3
10-(0 • -1):3	1-(0 • -1):3	-1-(4 • -1):3	0-(0 • -1):3	0-(1 • -1):3	-1-(3 • -1):3	0-(0 • -1):3
70-(0 • 0):3	0-(0 • 0):3	0-(4 • 0):3	1-(0 • 0):3	0-(1 • 0):3	0-(3 • 0):3	1-(0 • 0):3
0-(0 • -3):3	0-(0 • -3):3	-2-(4 • -3):3	0-(0 • -3):3	0-(1 • -3):3	-3-(3 • -3):3	0-(0 • -3):3

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6
x5	0	0	4/3	0	1/3	1	0
x1	10	1	1/3	0	1/3	0	0
x6	70	0	0	1	0	0	1
F(X1)	0	0	2	0	1	0	0

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи

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

Базис	B	x1	x2	x3	x4	x5	x6
x5	0	0	4/3	0	1/3	1	0
x1	10	1	1/3	0	1/3	0	0
x6	70	0	0	1	0	0	1
F(X2)	0	0	2	0	1	0	0

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

x₁ = 10, x₂ = 0, x₃ = 0

F(X) = 3•10 -1•0 = 30

Задание №6. Решить двойственным симплексным методом задачу линейного программирования:

в) Z(X)=x1+4x2+x3→min x1+ 2x2+3x3≥1, -3x1+x3≤2, -x1- x2+4x3≥1, x1, x2, x3≥0.

Решение

Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).

Определим минимальное значение целевой функции F(X) = x₁+4x₂+x₃ при следующих условиях-ограничений.

-x₁-2x₂-3x₃≤-1

-3x₁+x₃≤2

x₁+x₂-4x₃≤-1

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных

-x₁-2x₂-3x₃+x₄ = -1

-3x₁+x₃+x₅ = 2

x₁+x₂-4x₃+x₆ = -1

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

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

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

Базис	B	x1	x2	x3	x4	x5	x6
x4	-1	-1	-2	-3	1	0	0
x5	2	-3	0	1	0	1	0
x6	-1	1	1	-4	0	0	1
F(X0)	0	-1	-4	-1	0	0	0

Среди отрицательных значений базисных переменных выбираем наибольший по модулю.

Ведущей будет 1-ая строка, а переменную x₄ следует вывести из базиса.

Минимальное значение θ соответствует 3-му столбцу, т.е. переменную x₃ необходимо ввести в базис.

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

Базис	B	x1	x2	x3	x4	x5	x6
x4	-1	-1	-2	-3	1	0	0
x5	2	-3	0	1	0	1	0
x6	-1	1	1	-4	0	0	1
F(X0)	0	-1	-4	-1	0	0	0
θ		-1 : (-1) = 1	-4 : (-2) = 2	-1 : (-3) = 1/3	-	-	-

Выполняем преобразования симплексной таблицы

Базис	B	x1	x2	x3	x4	x5	x6
x3	1/3	1/3	2/3	1	-1/3	0	0
x5	5/3	-10/3	-2/3	0	1/3	1	0
x6	1/3	7/3	11/3	0	-4/3	0	1
F(X0)	1/3	-2/3	-10/3	0	-1/3	0	0

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

Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.

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

Базис	B	x1	x2	x3	x4	x5	x6
x3	1/3	1/3	2/3	1	-1/3	0	0
x5	5/3	-10/3	-2/3	0	1/3	1	0
x6	1/3	7/3	11/3	0	-4/3	0	1
F(X1)	1/3	-2/3	-10/3	0	-1/3	0	0

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

x₁ = 0, x₂ = 0, x₃ = ¹/₃

F(X) = 1•0 + 4•0 + 1•¹/₃ = ¹/₃