justify"> C 12=min [C 12; З 16 + З 62]=min [252; 324 + 576]=252.C 13=min [C 13; З 16 + З 63]=min [400; 324 + 724]=400.
C 14=min [C 14; З 16 + З 64]=min [196; 324 + 279]=196.C 15=min [C 15; З 16 + З 65]=min [213; 324 + 420]=213.
C 23=min [C 23; З 26 + З 63]=min [148; 576 + 724]=148.C 24=min [C 24; З 26 + З 64]=min [448; 576 + 279]=448.
З 25=min [C 25; З 26 + З 65]=min [335; 576 + 420]=335.C 34=min [C 34; З 36 + З 64]=min [474; 724 + 279]=474.
C 35=min [C 35; З 36 + З 65]=min [333; 724 + 420]=333.C 45=min [C 45; З 46 + З 65]=min [141; 279 + 420]=141.
Відповідь: найкоротші маршрути между Вузли перевезень ПОШТА, если відомі місця Розташування вузлів поштового звязку та відстані между ними представлені в матриці вигляд:
Завдання №2
Візначіті максимальний потік в мережі поштового звязку, если відома структура мережі та максимальна пропускна здатність Шляхів, что існують между відділеннямі поштового звязку.
За Даними табліці 1 будую граф (рис. 2) для розвязка задачі:
Рис. 2.
будую матрицю пропускних здатностей мережі:
- К=000000;
- К=000001=111110;
- К=000010=111101;
- К=000011=111100;
- К=000100=111011;
- К=000101=111010;
- К=000110=111001;
- К=000111=111000;
- К=001000=110111;
- К=001001=110110;
- К=001010=110101;
- К=001011=110100;
- К=001100=110011;
- К=001101=110010;
- К=001110=110001;
- К=001111=110000;
- К=010000=101111;
- К=010001=101110;
- К=010010=101101;
- К=010011=101100;
- К=010100=101011;
- К=010101=101010;
- К=010110=+101001;
- К=010111=101000;
- К=011000=100111;
- К=011001=100110;
- К=011010=100101;
- К=011011=100100;
- К=011100=100011;
- К=011101=100010;
- К=011110=100001;
- К=011111=10000.
Відповідь: максимальний потік в мережі поштового звязку, если відома структура мережі та максимальна пропускна здатність Шляхів, что існують между відділеннямі поштового звязку уявлень у наступній матриці:
Завдання №3
пошта відправлення звязок
На Основі АНАЛІЗУ найкоротшіх маршрутів та Шляхів Із Максимальний потік поштовий відправлень между Вузли перевезень Пошто Скласти оптимальний маршрут перевезень поштовий відправлень від вихідного пункту маршруту (у відповідності до Завдання) до найбільш віддаленого відділення поштового зв язку (найбільш віддаленого за кількістю проміжніх вузлів та відстанню). План винен містіті мінімальну Кількість транзитних вузлів (алгоритм Літла).
Віходячі з розрахунків задачі№1 матриця матіме вигляд (проти вместо 0 у головній діагоналі поставімо?):
визначавши мінімальну Довжину маршруту комівояжера. Для цього в кожному рядку (потім стовпці) вибираю мінімальне число и віднімаю це число від шкірного з чисел в цьом рядку (стовпці). Сума ціх Вибраного чисел І буде довжина маршруту комівояжера.
Нижня межа, Мінімальна довжина маршруту комівояжера буде дорівнюваті:
+ 148 + 148 + 141 + 141 + 279 + 45 + 128=1226.
визначавши КОЕФІЦІЄНТИ для шкірного з нулів матриці. Коефіцієнт дорівнює сумі мінімальніх елементів того рядка и стовпця на перетіні якіх ВІН находится:
G14=0 + 0=0; G16=0 + 10=10; G 23 =192 + 59=251 ; G32=185 + 56=241;
G45=17 + 10=27; G54=0 + 27=27; G61=0 + 10=10; G64=0 + 0=0.
Вибирай максимальний G23=251, вікреслюю з попередньої матриці 2 рядок и 3 стовпець, на місце (3; 2) ставлю?.
получил матрицю следующего вигляд:
Роблю так, щоб в шкірному рядку и шкірному стовпці матриці БУВ хоча б одна 0. Для цього у третіх рядку попередньої матриці віднімаю 185 від шкірного елемента цього рядка матриці и в іншому стовпці попередньої матриці віднімаю 56 від шкірного елемента цього стовпця. Отримайте матрицю следующего вигляд:
Нижня межа, Мінімальна довжина маршруту комівояжера буде дорівнюваті:
+ 185 + 56=1467.
визначавши КОЕФІЦІЄНТИ для шкірного з нулів матриці. Коефіцієнт дорівнює сумі мінімальніх елементів того рядка и стовпця на перетіні якіх ВІН находится:
G 12 =0 + 138=138 ; G14=0 + 0=0; G16=0 + 10=10; G35=0 + 22=22;
G45=0 + 10=10; G54=0 + 27=27; G61=0 + 10=10; G64=0 + 0=0.
Вибирай максимальний G12=138, вікреслюю з попередньої матриці 1 рядок і 2 стовпець .
получил матрицю следующего вигляд:
Роблю так, щоб в шкірному рядку и стовпці матриці БУВ хоча б одна 0. Для цього у шостому стовпці попередньої матриці в...
