вариант 4. Решение Шаг 1

• Название: Решение Шаг 1
• Дата: 26.04.2018
• Размер: 0.65 Mb.
• Имя файла: вариант 4.doc
• Тип: Решение; #42260
• страница: 5 из 8

Рис. 1

При минимизации целевой функции оптимальным решением задачи является точка области допустимых решений, наиболее приближенная к линии нулевого уровня в направлении противоположном направлению вектора-градиента целевой функции. В нашей задаче это точка А с координатами (0;7) В результате получим оптимальное решение на минимум целевой функции: х₁*=0; х₂*=7. Целевая функция принимает в точке (0;7) минимальное значение f(х*) = 5*0+2*7=14. Для любой другой точки либо не будут выполняться одновременно все неравенства ограничений, либо целевая функция будет иметь большее значение.

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

x₁ + 5x₂≥8

2x₁ + 3x₂≥21

4x₁ + 4x₂≥16

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

1x₁ + 5x₂-1x₃ + 0x₄ + 0x₅ = 8

2x₁ + 3x₂ + 0x₃-1x₄ + 0x₅ = 21

4x₁ + 4x₂ + 0x₃ + 0x₄-1x₅ = 16

Умножим все строки на (-1) и будем искать первоначальный опорный план.

-1x₁-5x₂ + 1x₃ + 0x₄ + 0x₅ = -8

-2x₁-3x₂ + 0x₃ + 1x₄ + 0x₅ = -21

-4x₁-4x₂ + 0x₃ + 0x₄ + 1x₅ = -16

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Решим систему уравнений относительно базисных переменных:

x₃, x₄, x₅,

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

X1 = (0,0,-8,-21,-16)

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

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

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

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

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

Базис	B	x1	x2	x3	x4	x5
x3	27	21/3	0	1	-12/3	0
x2	7	2/3	1	0	-1/3	0
x5	12	-11/3	0	0	-11/3	1
F(X0)	-14	32/3	0	0	2/3	0

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

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

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

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

Базис	B	x1	x2	x3	x4	x5
x3	27	21/3	0	1	-12/3	0
x2	7	2/3	1	0	-1/3	0
x5	12	-11/3	0	0	-11/3	1
F(X1)	-14	32/3	0	0	2/3	0

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

x₂ = 7

F(X) = 2•7 = 14

Составим двойственную задачу к прямой задаче.

y₁ + 2y₂ + 4y₃≤5

5y₁ + 3y₂ + 4y₃≤2

8y₁ + 21y₂ + 16y₃ → max

y₁ ≥ 0

y₂ ≥ 0

y₃ ≥ 0

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

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

Из теоремы двойственности следует, что Y = C*A^-1.

Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных.

Тогда Y = C*A^-1 =
Оптимальный план двойственной задачи равен:

y₁ = 0

y₂ = ²/₃

y₃ = 0

Z(Y) = 8*0+21*²/₃+16*0 = 14