Технические средства автоматизизированных систем управления в строительстве (стр. 4 из 5)
Получаем: до перераспределения условные затраты на перевозку
12*5+5*17+30*1+12*13+28*8=555;
После перераспределения условные затраты на перевозку составили
17*2+18*1+12*7+40*8=456.
Таблица 6 – Оптимизированный базисный план.
| J | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ∑= |
| i | 40 | 55 | 45 | 30 | 35 | 35 | 42 | 282 |
| 1 | 20 |       +5 | 9 | 6 | 12 | 7 (3) | +2 (17) | 13 |
| 2 | 25 | 12 | 13 | +3 (25) | 9 | 8 | 10 | 11 |
| 3 | 40 | 8 (40) | 9 | 10 | 13 | 19 | 7 | 9 |
| 4 | 35 | 9 | ++4 (35) | 7 | 8 | +6 | 12 | 10 |
| 5 | 50 | 10 | 11 | 9 | 12 (8) | 15 | 5 | ++2 (42) |
| 6 | 30 | 7 | 16 | ++1 (20) | +5 (10) | 9 | 17 | 10 |
| 7 | 30 | 17 | 14 | 9 | 7 (12) | 11 | ++1 (18) | 4 |
| 8 | 52 | 13 | ++4 (20) | 19 | 8 | 7 (32) | 15 | 12 |
| ∑= | 282 |
Проверяем количество заполненных клеток для оптимизированного плана, которое должно быть равно m+n-1, т.е. суммарному количеству строк и столбцов без единицы.
8+7-1=14, количество заполненных клеток N=13, условие не выполняется, поэтому вводим фиктивную перевозку ∆1,1 равную 0.
Таблица 6 – Оптимизированный базисный план.
| J | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ∑= | |
| i | 40 | 55 | 45 | 30 | 35 | 35 | 42 | 282 | |
| 1 | 20 | +5 (0) | 9 | 6 | 12 | 7 (3) | +2 (17) | 13 | 0 |
| 2 | 25 | 12 | 13 | +3 (25) | 9 | 8 | 10 | 11 | -1 |
| 3 | 40 | 8 (40) | 9 | 10 | 13 | 19 | 7 | 9 | -3 |
| 4 | 35 | 9 | ++4 (35) | 7 | 8 | +6 | 12 | 10 | 0 |
| 5 | 50 | 10 | 11 | 9 | 12 (8) | 15 | 5 | ++2 (42) | -4 |
| 6 | 30 | 7 | 16 | ++1 (20) | +5 (10) | 9 | 17 | 10 | 3 |
| 7 | 30 | 17 | 14 | 9 | 7 (12) | 11 | ++1 (18) | 4 | 1 |
| 8 | 52 | 13 | ++4 (20) | 19 | 8 | 7 (32) | 15 | 12 | 0 |
| ∑= | 282 | 5 | 4 | 2 | 8 | 7 | 2 | -2 |
Целевая функция плана:
Проверяем условия оптимальности плана.
Подбор потенциалов начинаем с первой строки. Принимаем U1=0.
| U1=0 | V1=0+5=5 |
| U2=2-3=-1 | V2=1+4=5 |
| U3=5-8=-3 | V3=3-1=2 |
| U4=4-4 | V4=1+7=8 |
| U5=8-12=-4 | V5=0+7=7 |
| U6=8-5=3 | V6=0+2=2 |
| U7=2-1=1 | V7=-4+2=-2 |
| U8=7-7=2 |
Далее производим проверку условия для свободных клеток по формуле:
 |  |  |
 |  |  |
 |  |  |
 |  |  |
 |  |  |
 |  |  |
 |  |  |
 |  |  |
 |  |  |
 |  |  |
 |  |  |
 |  |  |
 |  |  |
 |  |  |
Таким образом, проверка показала, что план не является оптимальным, так как условия для отдельных свободных клеток не выполняются.
Итерация 2.
Для клетки ∆5,6 строим контур перераспределения.
Получаем: до перераспределения условные затраты на перевозку
8*12+12*7+18*1=198;
После перераспределения условные затраты на перевозку составили
8*5+20*7+10*1=190.
Таблица 7 – Оптимизированный базисный план.
| J | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ∑= |
| i | 40 | 55 | 45 | 30 | 35 | 35 | 42 | 282 |
| 1 | 20 | +5 (0) | 9 | 6 | 12 | 7 (3) | +2 (17) | 13 |
| 2 | 25 | 12 | 13 | +3 (25) | 9 | 8 | 10 | 11 |
| 3 | 40 | 8 (40) | 9 | 10 | 13 | 19 | 7 | 9 |
| 4 | 35 | 9 | ++4 (35) | 7 | 8 | +6 | 12 | 10 |
| 5 | 50 | 10 | 11 | 9 |  12 | 15 | 5 (8) | ++2 (42) |
| 6 | 30 | 7 | 16 | ++1 (20) | +5 (10) | 9 | 17 | 10 |
| 7 | 30 | 17 | 14 | 9 | 7 (20) | 11 | ++1 (10) | 4 |
| 8 | 52 | 13 | ++4 (20) | 19 | 8 | 7 (32) | 15 | 12 |
| ∑= | 282 |
Для клетки ∆4,5 строим контур перераспределения.