4.4 Схема алгоритма метода CiclePr
4.5 Схемы алгоритма метода searchCycle
4.6 Схемы алгоритма метода firstPlan
5 РУЧНОЙ ПРОСЧЕТ
Даны сходные данные:
B1 | B2 | B3 | B4 | B5 | ai | ||||||
A1 | 2 | 4 | 7 | 10 | 8 | ||||||
A2 | 8 | 3 | 10 | 1 | 2 | ||||||
A3 | 5 | 4 | 6 | 7 | 9 | ||||||
A4 | 1 | 10 | 7 | 5 | 3 | ||||||
A5 | 4 | 8 | 9 | 2 | 1 | ||||||
bi |
B1 | B2 | B3 | B4 | B5 | ai | ||||||
A1 | 2 | 4 | 7 | 10 | 8 | ||||||
A2 | 8 | 3 | 10 | 1 | 2 | ||||||
A3 | 5 | 4 | 6 | 7 | 9 | ||||||
A4 | 1 | 10 | 7 | 5 | 3 | ||||||
A5 | 4 | 8 | 9 | 2 | 1 | ||||||
bi |
B1 | B2 | B3 | B4 | B5 | ai | ||||||
A1 | 2 | 4 | 7 | 10 | 8 | ||||||
A2 | 8 | 3 | 10 | 1 | 2 | ||||||
A3 | 5 | 4 | 6 | 7 | 9 | ||||||
A4 | 1 | 10 | 7 | 5 | 3 | ||||||
A5 | 4 | 8 | 9 | 2 | 1 | ||||||
bi |
B1 | B2 | B3 | B4 | B5 | ai | ||||||
A1 | 2 | 4 | 7 | 10 | 8 | ||||||
A2 | 8 | 3 | 10 | 1 | 2 | ||||||
A3 | 5 | 4 | 6 | 7 | 9 | ||||||
A4 | 1 | 10 | 7 | 5 | 3 | ||||||
A5 | 4 | 8 | 9 | 2 | 1 | ||||||
bi |
B1 | B2 | B3 | B4 | B5 | ai | ||||||
A1 | 2 | 4 | 7 | 10 | 8 | ||||||
A2 | 8 | 3 | 10 | 1 | 2 | ||||||
A3 | 5 | 4 | 6 | 7 | 9 | ||||||
A4 | 1 | 10 | 7 | 5 | 3 | ||||||
A5 | 4 | 8 | 9 | 2 | 1 | ||||||
bi |
B1 | B2 | B3 | B4 | B5 | ai | ||||||
A1 | 2 | 4 | 7 | 10 | 8 | ||||||
A2 | 8 | 3 | 10 | 1 | 2 | ||||||
A3 | 5 | 4 | 6 | 7 | 9 | ||||||
A4 | 1 | 10 | 7 | 5 | 3 | ||||||
A5 | 4 | 8 | 9 | 2 | 1 | ||||||
bi |
B1 | B2 | B3 | B4 | B5 | ai | ||||||
A1 | 2 | 4 | 7 | 10 | 8 | ||||||
A2 | 8 | 3 | 10 | 1 | 2 | ||||||
A3 | 5 | 4 | 6 | 7 | 9 | ||||||
A4 | 1 | 10 | 7 | 5 | 3 | ||||||
A5 | 4 | 8 | 9 | 2 | 1 | ||||||
bi |
B1 | B2 | B3 | B4 | B5 | ai | ||||||
A1 | 2 | 4 | 7 | 10 | 8 | ||||||
A2 | 8 | 3 | 10 | 1 | 2 | ||||||
A3 | 5 | 4 | 6 | 7 | 9 | ||||||
A4 | 1 | 10 | 7 | 5 | 3 | ||||||
A5 | 4 | 8 | 9 | 2 | 1 | ||||||
bi |
B1 | B2 | B3 | B4 | B5 | ai | ||||||
A1 | 2 | 4 | 7 | 10 | 8 | ||||||
A2 | 8 | 3 | 10 | 1 | 2 | ||||||
A3 | 5 | 4 | 6 | 7 | 9 | ||||||
A4 | 1 | 10 | 7 | 5 | 3 | ||||||
A5 | 4 | 8 | 9 | 2 | 1 | ||||||
bi |
Таблица 5.1 – Опорный план
|
|
Стоимость плана
|
|
14*2+18*4+4*7+1*10+12*1+33*6+26*1+10*2+32*1=426
Для каждой свободной клетки построим цикл и определим его стоимость
Y21 = 15 >0 Y53 = 10 >0
Y31 = 4 >0 Y34 = -2 <0
Y51 = 10 >0 Y44 = -4 <0
Y22 = 8 >0 Y15 = -1 <0
Y52 = 12 >0 Y25 = 2 >0
Y23 = 12 >0 Y43 = 1 >0
Y32 = 1 >0 Y45 = -1 <0
Построим цикл для {1;5}
B1 | B2 | B3 | B4 | B5 | ai | ||||||
A1 | 2 | 4 | 7 | 10 | + | 8 | |||||
A2 | 8 | 3 | 10 | 1 | 2 | ||||||
A3 | 5 | 4 | 6 | 7 | 9 | ||||||
A4 | 1 | 10 | 7 | 5 | 3 | ||||||
A5 | 4 | 8 | 9 | 2 | 1 | ||||||
bi |
Стоимость плана = 426-1=425
Построим цикл для {1;5}
B1 | B2 | B3 | B4 | B5 | ai | ||||||
A1 | 2 | 4 | 7 | 10 | 8 | ||||||
A2 | 8 | 3 | 10 | 1 | 2 | ||||||
A3 | 5 | 4 | 6 | + | 7 | 9 | |||||
A4 | 1 | 10 | 7 | 5 | 3 | ||||||
A5 | 4 | 8 | 9 | 2 | 1 | ||||||
bi |
Стоимость плана = 425- 1=424
Построим цикл для {1;5}
B1 | B2 | B3 | B4 | B5 | ai | ||||||
A1 | 2 | 4 | 7 | 10 | 8 | ||||||
A2 | 8 | 3 | 10 | 1 | 2 | ||||||
A3 | 5 | 4 | 6 | 7 | 9 | ||||||
A4 | 1 | 10 | 7 | + | 5 | 3 | |||||
A5 | 4 | 8 | 9 | 2 | 1 | ||||||
bi |
Стоимость плана = 424-1=423
Построим цикл для {4;5}
B1 | B2 | B3 | B4 | B5 | ai | ||||||
A1 | 2 | 4 | 7 | 10 | 8 | ||||||
A2 | 8 | 3 | 10 | 1 | 2 | ||||||
A3 | 5 | 4 | 6 | 7 | 9 | ||||||
A4 | 1 | 10 | 7 | 5 | + | 3 | |||||
A5 | 4 | 8 | 9 | 2 | 1 | ||||||
bi |
Стоимость плана = 424-1=422
B1 | B2 | B3 | B4 | B5 | ai | ||||||
A1 | 2 | 4 | 7 | 10 | 8 | ||||||
A2 | 8 | 3 | 10 | 1 | 2 | ||||||
A3 | 5 | 4 | 6 | 7 | 9 | ||||||
A4 | 1 | 10 | 7 | 5 | 3 | ||||||
A5 | 4 | 8 | 9 | 2 | 1 | ||||||
bi |
T.к. для всех клеток цены циклов положительны, то дальнейшее улучшение плана невозможно, что означает, что мы нашли оптимальный план.
План оптимален.
B1 | B2 | B3 | B4 | B5 | ai | ||||||
A1 | 4 | 8 | 9 | 2 | 1 | ||||||
A2 | 8 | 3 | 10 | 1 | 2 | ||||||
A3 | 5 | 4 | 6 | 7 | 9 | ||||||
A4 | 1 | 10 | 7 | 5 | 3 | ||||||
A5 | 2 | 4 | 7 | 10 | 8 | ||||||
bi |
Таблица 5.7 – Оптимальный план
Листинг программы приведен в приложении А, а результаты её выполнения – в приложении Б.