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