Контрольная работа по Методы оптимизации на тему Контрольная по оптимизации

Задача 1
Если в оптимальном плане ресурс используется полностью и оценка единицы этого ресурса больше нуля, то такой ресурс называют дефицитным.
Задача 2
Найти два опорных решения системы
{█(x_1+x_2-3x_5=2@3x_1+x_4+x_5=1@2x_1+x_2-2x_5=3)┤
Ответы первого опорного решения: 1) 0 X1 = (0; 2; 1; 3; 0); 0 X1 = (2; 1; 3; 0; 0) 3) 0 X1 = (2; 1; 0; 0; 3); 4) 0 X1 = (1; 3; 2; 0; 0); 5) 0 X1 = (1; 0; 0; 3; 2).
Решение
{█(x_1+x_2-3x_5=2@3x_1+x_4+x_5=1@3x_1+2x_2-5x_5=5)┤
{█(x_1+x_2-3x_5=2@3x_1+x_4+x_5=1@2x_2-x_4-6x_5=4)┤
x_2=2+x_4/2+3x_5
x_1=2-2+x_4/2+3x_5+3x_5=x_4/2+6x_5
X=(█(x_4/2+6x_5@2+x_4/2+3x_5@x_3@x_4@x_5 ))=x_3 (█(0@0@1@0@0))+x_4 (█(1/2@1/2@0@1@0))+x_5 (█(6@1@0@0@1))+(█(0@2@0@0@0))
x_3=1,x_4=0,x_5=0,x_1=0,x_2=2
x_3=1,x_4=2,x_5=0,x_1=1,x_2=3


Задача 3
Решить исходную задачу симплексным методом, составить к ней модель двойственной задачи, найти оптимальный план двойственной задачи
Z=-x_1-x_2-x_3→max
x_1-x_4+2x_6=6
x_2+2x_4-3x_5+x_6=4
x_3-x_5+2x_6=6
x_j≥0
Решение
Выразим базисные переменные через остальные:
x4 = -5/9x1-2/9x2+2/3x3+2/9
x5 = -4/9x1+2/9x2+1/3x3-2/9
x6 = -2/9x1+1/9x2-1/3x3+28/9
Подставим их в целевую функцию:
F(X) = -x1-x2-x3
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x5 следует ввести переменную x3. Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Базис B x1 x2 x3 x4 x5 x6
x4 2/3 -1/3 2/3 0 1 -2 0
x3 2/3 -4/3 2/3 1 0 -3 0
x6 8/3 2/3 -1/3 0 0 1 1
F(X0) 2/3 -7/3 -1/3 0 0 -3 0
Представим расчет каждого элемента в виде таблицы:
B x1 x2 x3 x4 x5 x6
2/9-(-2/9• -2/3):-1/3 5/9-(4/9 • -2/3):-1/3 2/9-(-2/9• -2/3):-1/3 -2/3-(-1/3• -2/3):-1/3 1-(0 • -2/3):-1/3 0-(1 • -2/3):-1/3 0-(0 • -2/3):-1/3
-2/9 : -1/3 4/9 : -1/3 -2/9 : -1/3 -1/3 : -1/3 0 : -1/3 1 : -1/3 0 : -1/3
28/9-(-2/9• 1/3):-1/3 2/9-(4/9 • 1/3):-1/3 -1/9-(-2/9• 1/3):-1/3 1/3-(-1/3 • 1/3):-1/3 0-(0 • 1/3):-1/3 0-(1 • 1/3):-1/3 1-(0 • 1/3):-1/3
Выразим базисные переменные через остальные:
x4 = 1/3x1-2/3x2+2x5+2/3
x3 = 4/3x1-2/3x2+3x5+2/3
x6 = -2/3x1+1/3x2-x5+22/3
Подставим их в целевую функцию:
F(X) = -x1-x2-(4/3x1-2/3x2+3x5+2/3)
или
F(X) = -7/3x1-1/3x2-3x5-2/3
-1/3x1+2/3x2+x4-2x5=2/3
-4/3x1+2/3x2+x3-3x5=2/3
2/3x1-1/3x2+x5+x6=22/3
При вычислениях значение Fc = -2/3 временно не учитываем.
Решим систему уравнений относительно базисных переменных: x4, x3, x6
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,2/3,2/3,0,22/3)
Базис B x1 x2 x3 x4 x5 x6
x4 2/3 -1/3 2/3 0 1 -2 0
x3 2/3 -4/3 2/3 1 0 -3 0
x6 8/3 2/3 -1/3 0 0 1 1
F(X0) 0 7/3 1/3 0 0 3 0
Переходим к основному алгоритму симплекс-метода.
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис B x1 x2 x3 x4 x5 x6
x4 2/3 -1/3 2/3 0 1 -2 0
x3 2/3 -4/3 2/3 1 0 -3 0
x6 8/3 2/3 -1/3 0 0 1 1
F(X1) 0 7/3 1/3 0 0 3 0
Оптимальный план можно записать так:
x1 = 0, x2 = 0, x3 = 2/3, x4 = 2/3, x5 = 0, x6 = 22/3
F(X) = -1*0 -1*0 -1*2/3 = -2/3
Анализ оптимального плана.
Значение 21/3> 0 в столбце x1 означает, что использование x1 - не выгодно.
Значение 1/3> 0 в столбце x2 означает, что использование x2 - не выгодно.
Значение 0 в столбце x3 означает, что использование x3 - выгодно.
Значение 0 в столбце x4 означает, что использование x4 - выгодно.
Значение 3> 0 в столбце x5 означает, что использование x5 - не выгодно.
Значение 0 в столбце x6 означает, что использование x6 - выгодно.
y1≥-1
y2≥-1
y3≥-1
y1+2y2≥0
-3y2-y3≥0
2y1+y2+2y3≥0
6y1+4y2+6y3 → min
y1 любое число
y2 любое число
y3 любое число
Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
y1=, y2=, y3=
Это же решение можно получить, применив теоремы двойственности.
Из теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
A = (A4, A3, A6) = 1 0 2
2 0 1
0 1 2


Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:
D = A-1 = -1/3 2/3 0
-4/3 2/3 1
2/3 -1/3 0


Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных.
Тогда Y = C*A-1 =