Вариант выбора
проверим на оптимальность. Для этого вычислим потенциалы и оценки.Отсюда вычислим потенциалы:
Для небазисных переменных вычислим оценки по соответствующей формуле:
И так далее расчеты по соответствующим формулам и данным приведены в таблице 5.2.
Таблица 5.2
Х0 | 28 | 13 | 19 | 41 | 10 | 44 | 38 | 29 |
31 | 13 | 11 | 41 | 10 | 17 | 38 | 25 | |
0 | 0(7) | 0(13) | 1(8) | |||||
Оценка1 | -3 | 0 | 8 | 27 | 4 | |||
35 | 20 | 26 | 8 | 17 | 14 | 38 | 36 | |
7 | 0(11) | 0(14) | 0(12) | 1(15) | 0(7) | 0(10) | ||
Оценка2 | 40 | 37 | ||||||
8 | 12 | 37 | 38 | 49 | 38 | 22 | 10 | 13 |
1(1) | ||||||||
Оценка3 | 24 | -16 | -11 | -20 | 30 | 36 | 24 | |
29 | 28 | 21 | 48 | 43 | 44 | 29 | 26 | 12 |
1(4) | ||||||||
Оценка4 | 29 | 21 | 27 | -5 | 44 | 41 | 46 | |
37 | 22 | 39 | 46 | 26 | 20 | 44 | 49 | |
20 | 1(2) | |||||||
Оценка5 | 11 | 11 | 0 | 15 | 4 | 44 | 14 | |
22 | 49 | 19 | 2 | 20 | 30 | 45 | 16 | |
36 | 1(3) | |||||||
Оценка6 | 42 | 36 | 75 | 26 | 50 | 29 | 49 | |
45 | 27 | 5 | 21 | 30 | 21 | 34 | 23 | |
17 | 1(6) | |||||||
Оценка7 | 3 | 31 | 37 | -3 | 40 | 21 | 23 | |
43 | 33 | 20 | 29 | 3 | 46 | 33 | 21 | |
2 | 1(5) | |||||||
Оценка8 | -6 | -11 | 8 | -19 | 16 | 7 | 17 |
Cреди вычисленных оценок имеются отрицательные, это означает, что выбранный вариант назначения не является оптимальным. Наименьшая из отрицательных оценок
Строим цикл пересчета: (3,5), (2,5), (1,7), (1,4), (3,5) замыкающийся на разрешающей клетке. Вычислим величину корректировки . Базисный нуль 03,5 перемещается в клетку (1,7), переменная х1,7 включается в базис, а переменная х3,5 выходит из базиса. Получим новую комбинацию расстановки единиц и нулей (Табл. 5.3). Суммарная эффективность равна: условных единиц эффективностиТаблица 5.3
Х0 | 28 | 13 | 19 | 41 | 10 | 44 | 38 | 29 |
31 | 13 | 11 | 41 | 10 | 17 | 38 | 25 | |
0 | 1(7) | 0(13) | 0(8) | |||||
Оценка1 | -3 | 0 | 8 | 27 | 4 | |||
35 | 20 | 26 | 8 | 17 | 14 | 38 | 36 | |
7 | 0(11) | 0(14) | 0(12) | 0(15) | 1(7) | 0(10) | ||
Оценка2 | 40 | 37 | ||||||
28 | 12 | 37 | 38 | 49 | 38 | 22 | 10 | 13 |
1(7) | ||||||||
Оценка3 | 44 | 4 | 9 | 20 | 50 | 56 | 44 | |
29 | 28 | 21 | 48 | 43 | 44 | 29 | 26 | 12 |
1(4) | ||||||||
Оценка4 | 29 | 21 | 27 | -5 | 44 | 41 | 46 | |
37 | 22 | 39 | 46 | 26 | 20 | 44 | 49 | |
20 | 1(2) | |||||||
Оценка5 | 11 | 11 | 0 | 15 | 4 | 44 | 14 | |
22 | 49 | 19 | 2 | 20 | 30 | 45 | 16 | |
36 | 1(3) | |||||||
Оценка6 | 42 | 36 | 75 | 26 | 50 | 29 | 49 | |
45 | 27 | 5 | 21 | 30 | 21 | 34 | 23 | |
17 | 1(6) | |||||||
Оценка7 | 3 | 31 | 37 | -3 | 40 | 21 | 23 | |
43 | 33 | 20 | 29 | 3 | 46 | 33 | 21 | |
2 | 1(5) | |||||||
Оценка8 | -6 | -11 | 8 | -19 | 16 | 7 | 17 |
Заново вычисляем потенциалы и оценки.
Отсюда вычислим потенциалы:
Для небазисных переменных вычислим оценки в таблице 5.3.
Среди вычисленных оценок имеются отрицательные, это означает, что выбранный вариант назначения не является оптимальным. Наименьшая из отрицательных оценок
Строим цикл пересчета: (8,4), (2,4), (2,2), (8,2),(8,4) замыкающийся на разрешающей клетке. Вычислим величину корректировки . Базисная переменная х2,2=0 перемещается в клетку (8,4), переменная х8,4 включается в базис, а переменная х2,2 выходит из базиса. (Табл. 5.4).Таблица 5.4
Х1 | 28 | 13 | 19 | 41 | 10 | 44 | 38 | 29 |
31 | 13 | 11 | 41 | 10 | 17 | 38 | 25 | |
0 | 1(7) | 0(13) | 0(8) | |||||
Оценка1 | -3 | 0 | 8 | 27 | 4 | |||
35 | 20 | 26 | 8 | 17 | 14 | 38 | 36 | |
7 | 0(11) | 0(12) | 0(15) | 1(7) | 0(10) | |||
Оценка2 | 40 | 37 | ||||||
28 | 12 | 37 | 38 | 49 | 38 | 22 | 10 | 13 |
1(7) | ||||||||
Оценка3 | 44 | 4 | 9 | 20 | 50 | 56 | 44 | |
29 | 28 | 21 | 48 | 43 | 44 | 29 | 26 | 12 |
1(4) | ||||||||
Оценка4 | 29 | 21 | 27 | -5 | 44 | 41 | 46 | |
37 | 22 | 39 | 46 | 26 | 20 | 44 | 49 | |
20 | 1(2) | |||||||
Оценка5 | 11 | 11 | 0 | 15 | 4 | 44 | 14 | |
22 | 49 | 19 | 2 | 20 | 30 | 45 | 16 | |
36 | 1(3) | |||||||
Оценка6 | 42 | 36 | 75 | 26 | 50 | 29 | 49 | |
45 | 27 | 5 | 21 | 30 | 21 | 34 | 23 | |
17 | 1(6) | |||||||
Оценка7 | 3 | 31 | 37 | -3 | 40 | 21 | 23 | |
43 | 33 | 20 | 29 | 3 | 46 | 33 | 21 | |
2 | 0(14) | 1(5) | ||||||
Оценка8 | -6 | -11 | 8 | -19 | 16 | 7 | 17 |
Суммарная эффективность не изменилась и равна:
условных единиц эффективностиЗаново вычисляем потенциалы и оценки. Расчеты оценок приведены в таблице 5.5.
Среди вычисленных оценок имеются отрицательные, это означает, что выбранный вариант назначения не является оптимальным. Наименьшая из отрицательных оценок
Строим цикл пересчета: (2,4), (2,5), (5,5), (5,2),(2,2) замыкающийся на разрешающей клетке. Вычислим величину корректировки . Базисная переменная х5,2=0 перемещается в клетку (2,4), переменная х2,4 включается в базис, а переменная х5,2 выходит из базиса. (Табл. 5.5).Таблица 5.5
Х2 | 28 | 13 | 19 | 41 | 10 | 44 | 38 | 29 |
31 | 13 | 11 | 41 | 10 | 17 | 38 | 25 | |
0 | 1(7) | 0(13) | 0(8) | |||||
Оценка1 | -3 | 0 | 8 | 27 | 4 | |||
35 | 20 | 26 | 8 | 17 | 14 | 38 | 36 | |
7 | 0(11) | 0(12) | 0(15) | 1(7) | 0(10) | |||
Оценка2 | 40 | 37 | ||||||
28 | 12 | 37 | 38 | 49 | 38 | 22 | 10 | 13 |
1(7) | ||||||||
Оценка3 | 44 | 4 | 9 | 20 | 50 | 56 | 44 | |
29 | 28 | 21 | 48 | 43 | 44 | 29 | 26 | 12 |
1(4) | ||||||||
Оценка4 | 29 | 21 | 27 | -5 | 44 | 41 | 46 | |
37 | 22 | 39 | 46 | 26 | 20 | 44 | 49 | |
20 | 1(2) | |||||||
Оценка5 | 11 | 11 | 0 | 15 | 4 | 44 | 14 | |
22 | 49 | 19 | 2 | 20 | 30 | 45 | 16 | |
36 | 1(3) | |||||||
Оценка6 | 42 | 36 | 75 | 26 | 50 | 29 | 49 | |
45 | 27 | 5 | 21 | 30 | 21 | 34 | 23 | |
17 | 1(6) | |||||||
Оценка7 | 3 | 31 | 37 | -3 | 40 | 21 | 23 | |
43 | 33 | 20 | 29 | 3 | 46 | 33 | 21 | |
21 | 0(14) | 1(5) | ||||||
Оценка8 | 6 | 11 | 20 | 29 | 26 | 29 |
Заново вычисляем потенциалы и оценки. Расчеты оценок приведены в таблице 5.5.