Градиент 11782
.docx
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x5 |
42 |
17 |
0 |
-6 |
0 |
1 |
|
x4 |
10 |
5 |
0 |
-2 |
1 |
0 |
|
x2 |
9 |
3 |
1 |
-1 |
0 |
0 |
|
F(X1) |
-54 |
-14 |
0 |
6 |
0 |
0 |
Представим расчет каждого элемента в виде таблицы:
|
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
-7 : -1/6 |
-25/6 : -1/6 |
0 : -1/6 |
1 : -1/6 |
0 : -1/6 |
-1/6 : -1/6 |
|
-4-(-7 • -1/3):-1/6 |
-2/3-(-25/6 • -1/3):-1/6 |
0-(0 • -1/3):-1/6 |
0-(1 • -1/3):-1/6 |
1-(0 • -1/3):-1/6 |
-1/3-(-1/6 • -1/3):-1/6 |
|
2-(-7 • -1/6):-1/6 |
1/6-(-25/6 • -1/6):-1/6 |
1-(0 • -1/6):-1/6 |
0-(1 • -1/6):-1/6 |
0-(0 • -1/6):-1/6 |
-1/6-(-1/6 • -1/6):-1/6 |
|
-12-(-7 • 1):-1/6 |
3-(-25/6 • 1):-1/6 |
0-(0 • 1):-1/6 |
0-(1 • 1):-1/6 |
0-(0 • 1):-1/6 |
1-(-1/6 • 1):-1/6 |
В базисном столбце все элементы положительные.
Переходим к основному алгоритму симплекс-метода.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (42 : 17 , 10 : 5 , 9 : 3 ) = 2
Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (5) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
min |
|
x5 |
42 |
17 |
0 |
-6 |
0 |
1 |
28/17 |
|
x4 |
10 |
5 |
0 |
-2 |
1 |
0 |
2 |
|
x2 |
9 |
3 |
1 |
-1 |
0 |
0 |
3 |
|
F(X1) |
-54 |
-14 |
0 |
6 |
0 |
0 |
0 |
Представим расчет каждого элемента в виде таблицы:
|
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
|
42-(10 • 17):5 |
17-(5 • 17):5 |
0-(0 • 17):5 |
-6-(-2 • 17):5 |
0-(1 • 17):5 |
1-(0 • 17):5 |
|
10 : 5 |
5 : 5 |
0 : 5 |
-2 : 5 |
1 : 5 |
0 : 5 |
|
9-(10 • 3):5 |
3-(5 • 3):5 |
1-(0 • 3):5 |
-1-(-2 • 3):5 |
0-(1 • 3):5 |
0-(0 • 3):5 |
|
-54-(10 • -14):5 |
-14-(5 • -14):5 |
0-(0 • -14):5 |
6-(-2 • -14):5 |
0-(1 • -14):5 |
0-(0 • -14):5 |
Получаем новую симплекс-таблицу:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x5 |
8 |
0 |
0 |
4/5 |
-17/5 |
1 |
|
x1 |
2 |
1 |
0 |
-2/5 |
1/5 |
0 |
|
x2 |
3 |
0 |
1 |
1/5 |
-3/5 |
0 |
|
F(X1) |
-26 |
0 |
0 |
2/5 |
14/5 |
0 |
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x5 |
8 |
0 |
0 |
4/5 |
-17/5 |
1 |
|
x1 |
2 |
1 |
0 |
-2/5 |
1/5 |
0 |
|
x2 |
3 |
0 |
1 |
1/5 |
-3/5 |
0 |
|
F(X2) |
-26 |
0 |
0 |
2/5 |
14/5 |
0 |
Оптимальный план можно записать так:
x1 = 2
x2 = 3
F(X) = 4*2 + 6*3 = 26
Решим двойственную задачу:
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5.
Решим систему уравнений относительно базисных переменных: y4, y5
Полагая, что свободные переменные равны 0, получим первый опорный план:
Y1 = (0,0,0,4,6)
Базисное решение называется допустимым, если оно неотрицательно.
|
Базис |
B |
y1 |
y2 |
y3 |
y4 |
y5 |
|
y4 |
4 |
3 |
1 |
1 |
1 |
0 |
|
y5 |
6 |
1 |
2 |
6 |
0 |
1 |
|
Z(Y0) |
0 |
-9 |
-8 |
-12 |
0 |
0 |
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной y3, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3 и из них выберем наименьшее: min (4 : 1 , 6 : 6 ) = 1
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (6) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
B |
y1 |
y2 |
y3 |
y4 |
y5 |
min |
|
y4 |
4 |
3 |
1 |
1 |
1 |
0 |
4 |
|
y5 |
6 |
1 |
2 |
6 |
0 |
1 |
1 |
|
Z(y1) |
0 |
-9 |
-8 |
-12 |
0 |
0 |
0 |
Представим расчет каждого элемента в виде таблицы:
|
B |
y 1 |
y 2 |
y 3 |
y 4 |
y 5 |
|
4-(6 • 1):6 |
3-(1 • 1):6 |
1-(2 • 1):6 |
1-(6 • 1):6 |
1-(0 • 1):6 |
0-(1 • 1):6 |
|
6 : 6 |
1 : 6 |
2 : 6 |
6 : 6 |
0 : 6 |
1 : 6 |
|
0-(6 • -12):6 |
-9-(1 • -12):6 |
-8-(2 • -12):6 |
-12-(6 • -12):6 |
0-(0 • -12):6 |
0-(1 • -12):6 |
Получаем новую симплекс-таблицу:
|
Базис |
B |
y1 |
y2 |
y3 |
y4 |
y5 |
|
y4 |
3 |
17/6 |
2/3 |
0 |
1 |
-1/6 |
|
y3 |
1 |
1/6 |
1/3 |
1 |
0 |
1/6 |
|
Z(Y1) |
12 |
-7 |
-4 |
0 |
0 |
2 |
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной y1, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (3 : 25/6 , 1 : 1/6 ) = 11/17
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (25/6) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
B |
y1 |
y2 |
y3 |
y4 |
y5 |
min |
|
y4 |
3 |
25/6 |
2/3 |
0 |
1 |
-1/6 |
11/17 |
|
y3 |
1 |
1/6 |
1/3 |
1 |
0 |
1/6 |
6 |
|
Z(Y2) |
12 |
-7 |
-4 |
0 |
0 |
2 |
0 |
Представим расчет каждого элемента в виде таблицы:
|
B |
y 1 |
y 2 |
y 3 |
y 4 |
y 5 |
|
3 : 25/6 |
25/6 : 25/6 |
2/3 : 25/6 |
0 : 25/6 |
1 : 25/6 |
-1/6 : 25/6 |
|
1-(3 • 1/6):25/6 |
1/6-(25/6 • 1/6):25/6 |
1/3-(2/3 • 1/6):25/6 |
1-(0 • 1/6):25/6 |
0-(1 • 1/6):25/6 |
1/6-(-1/6 • 1/6):25/6 |
|
12-(3 • -7):25/6 |
-7-(25/6 • -7):25/6 |
-4-(2/3 • -7):25/6 |
0-(0 • -7):25/6 |
0-(1 • -7):25/6 |
2-(-1/6 • -7):25/6 |
Получаем новую симплекс-таблицу:
|
Базис |
B |
y1 |
y2 |
y3 |
y4 |
y5 |
|
y1 |
18/17 |
1 |
4/17 |
0 |
6/17 |
-1/17 |
|
y3 |
14/17 |
0 |
5/17 |
1 |
-1/17 |
3/17 |
|
Z(Y2) |
330/17 |
0 |
-40/17 |
0 |
42/17 |
27/17 |
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной y2, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: min (11/17 : 4/17 , 14/17 : 5/17 ) = 24/5
Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (5/17) и находится на пересечении ведущего столбца и ведущей строки.
|
Базис |
B |
y1 |
y2 |
y3 |
y4 |
y5 |
min |
|
y1 |
11/17 |
1 |
4/17 |
0 |
6/17 |
-1/17 |
41/2 |
|
y3 |
14/17 |
0 |
5/17 |
1 |
-1/17 |
3/17 |
24/5 |
|
Z(Y3) |
197/17 |
0 |
-26/17 |
0 |
28/17 |
110/17 |
0 |
Представим расчет каждого элемента в виде таблицы:
|
B |
y 1 |
y 2 |
y 3 |
y 4 |
y 5 |
|
11/17-(14/17 • 4/17):5/17 |
1-(0 • 4/17):5/17 |
4/17-(5/17 • 4/17):5/17 |
0-(1 • 4/17):5/17 |
6/17-(-1/17 • 4/17):5/17 |
-1/17-(3/17 • 4/17):5/17 |
|
14/17 : 5/17 |
0 : 5/17 |
5/17 : 5/17 |
1 : 5/17 |
-1/17 : 5/17 |
3/17 : 5/17 |
|
197/17-(14/17 • -26/17):5/17 |
0-(0 • -26/17):5/17 |
-26/17-(5/17 • -26/17):5/17 |
0-(1 • -26/17):5/17 |
28/17-(-1/17 • -26/17):5/17 |
110/17-(3/17 • -26/17):5/17 |
Получаем новую симплекс-таблицу:
|
Базис |
B |
y1 |
y2 |
y3 |
y4 |
y5 |
|
y1 |
2/5 |
1 |
0 |
-4/5 |
2/5 |
-1/5 |
|
y2 |
14/5 |
0 |
1 |
17/5 |
-1/5 |
3/5 |
|
Z(Y3) |
26 |
0 |
0 |
8 |
2 |
3 |
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
|
Базис |
B |
y1 |
y2 |
y3 |
y4 |
y5 |
|
y1 |
2/5 |
1 |
0 |
-4/5 |
2/5 |
-1/5 |
|
y2 |
14/5 |
0 |
1 |
17/5 |
-1/5 |
3/5 |
|
Z(Y3) |
26 |
0 |
0 |
8 |
2 |
3 |