Составьте двойственную задачу к данной задаче линейного программирования и найдите решения обеих задач симплекс-методом.
F(X) = 4x1+3x2+x3 → min
3x1+2x2+x3≥7,-x1+3x2+x3≥1,11x1+7x2+4x3≤27,x1≥0,
x2≥0,
x3≥0.
Решение
Определим минимальное значение целевой функции Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).В 1-м неравенстве смысла (≥) вводим базисную переменную x4 со знаком минус. В 2-м неравенстве смысла (≥) вводим базисную переменную x5 со знаком минус. В 3-м неравенстве смысла (≤) вводим базисную переменную x6.
3x1+2x2+x3-x4 = 7-x1+3x2+x3-x5 = 111x1+7x2+4x3+x6 = 27Расширенная матрица системы ограничений-равенств данной задачи:
3 2 1 -1 0 0 7
-1 3 1 0 -1 0 1
11 7 4 0 0 1 27
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x4.
Получаем новую матрицу:
-3 -2 -1 1 0 0 -7
-1 3 1 0 -1 0 1
11 7 4 0 0 1 27
2
. В качестве базовой переменной можно выбрать x5.Получаем новую матрицу:
-3 -2 -1 1 0 0 -7
1 -3 -1 0 1 0 -1
11 7 4 0 0 1 27
3. В качестве базовой переменной можно выбрать x6.
Т.к. в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,5,6).
Выразим базисные переменные через остальные:
x4 = 3x1+2x2+x3-7x5 = -x1+3x2+x3-1x6 = -11x1-7x2-4x3+27Подставим их в целевую функцию:F(X) = 4x1+3x2+x3
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x4 следует ввести переменную x3.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Базис B x1 x2 x3 x4 x5 x6
x3 7 3 2 1 -1 0 0
x5 6 4 -1 0 -1 1 0
x6 -1 -1 -1 0 4 0 1
F(X0) -7 1 1 0 1 0 0
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x6 следует ввести переменную x2.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Базис B x1 x2 x3 x4 x5 x6
x3 5 1 0 1 7 0 2
x5 7 5 0 0 -5 1 -1
x2 1 1 1 0 -4 0 -1
F(X1) -8 0 0 0 5 0 1
Выразим базисные переменные через остальные:x3 = -x1-7x4-2x6+5x5 = -5x1+5x4+x6+7x2 = -x1+4x4+x6+1
Подставим их в целевую функцию:F(X) = 4x1+3(-x1+4x4+x6+1)+(-x1-7x4-2x6+5)илиF(X) = 5x4+x6+8x1+x3+7x4+2x6=55x1-5x4+x5-x6=7x1+x2-4x4-x6=1
При вычислениях значение Fc = 8 временно не учитываем.
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = 1 0 1 7 0 2
5 0 0 -5 1 -1
1 1 0 -4 0 -1
Решим систему уравнений относительно базисных переменных: x3, x5, x2
Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,1,5,0,7,0)
Базис B x1 x2 x3 x4 x5 x6
x3 5 1 0 1 7 0 2
x5 7 5 0 0 -5 1 -1
x2 1 1 1 0 -4 0 -1
F(X0) 0 0 0 0 -5 0 -1
Т.к
Задать вопрос
на новый заказ в Автор24.
