Оптимізація плану перевезення поштових відправлень ділянки магістральної мережі за критерієм мінімуму витрат на оброблення транзиту

Оптимізація плану перевезення поштових відправлень ділянки магістральної мережі за критерієм мінімуму витрат на оброблення транзиту

Таблиця 1. Вихідні дані для виконання розрахунково-гарфічної роботи

Задача № 1

Використовуючи алгоритм Флойда, визначити найкоротші маршрути між вузлами перевезень пошти, якщо відомі місця розташування вузлів поштового зв’язку та відстані між ними.

За даними таблиці 1 будую граф (рис. 1) для розв’язку задачі:

Рис. 1.

Будую матрицю довжин:

Будую матрицю довжин при k=1:

C₂₃=min[C₂₃; С₂₁+С₁₃]=min [148; 252+?]=148. C₂₄=min[C₂₄; С₂₁+С₁₄]=min [?; 252+196]=448.

C₂₅=min[C₂₅; С₂₁+С₁₅]=min [375; 252+213]=335. C₂₆=min[C₂₆; С₂₁+С₁₆]=min [?; 252+324]=576.

C₃₄=min[C₃₄; С₃₁+С₁₄]=min[?;?+196]=?. C₃₅=min[C₃₅; С₃₁+С₁₅]=min [333;?+213]=333.

C₃₆=min[C₃₆; С₃₁+С₁₆]=min[?;?+324]=?. C₄₅=min[C₄₅; С₄₁+С₁₅]=min [141; 196+213]=141.

C₄₆=min[C₄₆; С₄₁+С₁₆]=min [279; 196+324]=279. C₅₆=min[C₅₆; С₅₁+С₁₆]=min [?; 213+324]=537.

Будую матрицю довжин при k=2:

C₁₃=min[C₁₃; С₁₂+С₂₃]=min [?; 252+148]=400. C₁₄=min[C₁₄; С₁₂+С₂₄]=min [196; 252+448]=196.

C₁₅=min[C₁₅; С₁₂+С₂₅]=min [213; 252+335]=213.C₁₆=min[C₁₆; С₁₂+С₂₆]=min [324; 252+576]=324.

C₃₄=min[C₃₄; С₃₂+С₂₄]=min [?; 148+448]=596. C₃₅=min[C₃₅; С₃₂+С₂₅]=min [333; 148+335]=333.

C₃₆=min[C₃₆; С₃₂+С₂₆]=min [?; 148+576]=724. C₄₅=min[C₄₅; С₄₂+С₂₅]=min [141; 448+335]=141.

C₄₆=min[C₄₆; С₄₂+С₂₆]=min [279; 448+376]=279.C₅₆=min[C₅₆; С₅₂+С₂₆]=min [537; 335+576]=537.

Будую матрицю довжин при k=3:

C₁₂=min[C₁₂; С₁₃+С₃₂]=min [252; 400+148]=252.C₁₄=min[C₁₄; С₁₃+С₃₄]=min [196; 400+596]=196.

C₁₅=min[C₁₅; С₁₃+С₃₅]=min [213; 400+333]=213.C₁₆=min[C₁₆; С₁₃+С₃₆]=min [324; 400+724]=324.

C₂₄=min[C₂₄; С₂₃+С₃₄]=min [448; 148+596]=596.C₂₅=min[C₂₅; С₂₃+С₃₅]=min [335; 148+333]=335.

С₂₆=min[C₂₆; С₂₃+С₃₆]=min [576; 148+724]=576.C₄₅=min[C₄₅; С₄₃+С₃₅]=min [141; 596+333]=141.

C₄₆=min[C₄₆; С₄₃+С₃₆]=min [279; 596+724]=279.C₅₆=min[C₅₆; С₅₃+С₃₆]=min [537; 333+724]=537.

Будую матрицю довжин при k=4:

C₁₂=min[C₁₂; С₁₄+С₄₂]=min [252; 196+448]=252.C₁₃=min[C₁₃; С₁₄+С₄₃]=min [400; 196+448]=400.

C₁₅=min[C₁₅; С₁₄+С₄₅]=min [213; 196+141]=213.C₁₆=min[C₁₆; С₁₄+С₄₆]=min [324; 196+279]=324.

C₂₃=min[C₂₃; С₂₄+С₄₃]=min [148; 448+596]=148.C₂₅=min[C₂₅; С₂₄+С₄₅]=min [335; 448+141]=335.

С₂₆=min[C₂₆; С₂₄+С₄₆]=min [576; 448+279]=576.C₃₅=min[C₃₅; С₃₄+С₄₅]=min [335; 596+141]=333.

C₃₆=min[C₃₆; С₃₄+С₄₆]=min [724; 596+279]=724.C₅₆=min[C₅₆; С₅₄+С₄₆]=min [537; 141+279]=420.

Будую матрицю довжин при k=5:

C₁₂=min[C₁₂; С₁₅+С₅₂]=min [252; 196+335]=252.C₁₃=min[C₁₃; С₁₅+С₅₃]=min [400; 213+333]=400.

C₁₄=min[C₁₄; С₁₅+С₅₄]=min [196; 213+141]=196.C₁₆=min[C₁₆; С₁₅+С₅₆]=min [324; 213+420]=324.

C₂₃=min[C₂₃; С₂₅+С₅₃]=min [148; 335+333]=148.C₂₄=min[C₂₄; С₂₅+С₅₄]=min [448; 335+141]=448.

С₂₆=min[C₂₆; С₂₅+С₅₆]=min [576; 335+420]=576.C₃₄=min[C₃₄; С₃₅+С₅₄]=min [596; 333+141]=474.

C₃₆=min[C₃₆; С₃₅+С₅₆]=min [724; 333+420]=724.C₄₆=min[C₄₆; С₄₅+С₅₆]=min [279; 141+420]=279.

Будую матрицю довжин при k=6:

C₁₂=min[C₁₂; С₁₆+С₆₂]=min [252; 324+576]=252.C₁₃=min[C₁₃; С₁₆+С₆₃]=min [400; 324+724]=400.

C₁₄=min[C₁₄; С₁₆+С₆₄]=min [196; 324+279]=196.C₁₅=min[C₁₅; С₁₆+С₆₅]=min [213; 324+420]=213.

C₂₃=min[C₂₃; С₂₆+С₆₃]=min [148; 576+724]=148.C₂₄=min[C₂₄; С₂₆+С₆₄]=min [448; 576+279]=448.

С₂₅=min[C₂₅; С₂₆+С₆₅]=min [335; 576+420]=335.C₃₄=min[C₃₄; С₃₆+С₆₄]=min [474; 724+279]=474.

C₃₅=min[C₃₅; С₃₆+С₆₅]=min [333; 724+420]=333.C₄₅=min[C₄₅; С₄₆+С₆₅]=min [141; 279+420]=141.

Відповідь: найкоротші маршрути між вузлами перевезень пошти, якщо відомі місця розташування вузлів поштового зв’язку та відстані між ними представлені в матриці вигляду:

Задача № 2

Визначити максимальний потік в мережі поштового зв’язку, якщо відома структура мережі та максимальна пропускна здатність шляхів, що існують між відділеннями поштового зв’язку.

За даними таблиці 1 будую граф (рис. 2) для розв’язку задачі:

Рис. 2.

Будую матрицю пропускних здатностей мережі:

— К=0;

— К=1=111110;

— К=10=111101;

— К=11=111100;

— К=100=111011;

— К=101=111010;

— К=110=111001;

— К=111=111000;

— К=1 000=110111;

— К=1 001=110110;

— К=1 010=110101;

— К=1 011=110100;

— К=1 100=110011;

— К=1 101=110010;

— К=1 110=110001;

— К=1 111=110000;

— К=10 000=101111;

— К=10 001=101110;

— К=10 010=101101;

— К=10 011=101100;

— К=10 100=101011;

— К=10 101=101010;

— К=10 110=101001;

— К=10 111=101000;

— К=11 000=100111;

— К=11 001=100110;

— К=11 010=100101;

— К=11 011=100100;

— К=11 100=100011;

— К=11 101=100010;

— К=11 110=100001;

— К=11 111=10000.

Відповідь: максимальний потік в мережі поштового зв’язку, якщо відома структура мережі та максимальна пропускна здатність шляхів, що існують між відділеннями поштового зв’язку представлений у наступній матриці:

Задача № 3

пошта відправлення зв’язок На основі аналізу найкоротших маршрутів та шляхів із максимальними потоками поштових відправлень між вузлами перевезень пошти скласти оптимальний маршруту перевезень поштових відправлень від вихідного пункту маршруту (у відповідності до завдання) до найбільш віддаленого відділення поштового зв’язку (найбільш віддаленого за кількістю проміжних вузлів та відстанню). План повинен містити мінімальну кількість транзитних вузлів (алгоритм Літла).

Виходячи з розрахунків задачі№ 1 матриця матиме вигляд (проте замість 0 у головній діагоналі поставимо ?):

Визначаю мінімальну довжину маршруту комівояжера. Для цього в кожному рядку (потім стовпці) вибираю мінімальне число і віднімаю це число від кожного з чисел в цьому рядку (стовпці). Сума цих вибраних чисел і буде довжиною маршруту комівояжера.

Нижня границя, мінімальна довжина маршруту комівояжера буде дорівнювати:

196+148+148+141+141+279+45+128=1226.

Визначаю коефіцієнти для кожного з нулів матриці. Коефіцієнт дорівнює сумі мінімальних елементів того рядка і стовпця на перетині яких він знаходиться:

G₁₄=0+0=0; G₁₆=0+10=10; G₂₃=192+59=251; G₃₂=185+56=241;

G₄₅=17+10=27; G₅₄=0+27=27; G₆₁=0+10=10; G₆₄=0+0=0.

Вибираю максимальний G₂₃=251, викреслюю з попередньої матриці 2 рядок і 3 стовпець, на місце (3; 2) ставлю ?.

Отримаю матрицю наступного вигляду:

Роблю так, щоб в кожному рядку і кожному стовпці матриці був хоча б один 0. Для цього у третьому рядку попередньої матриці віднімаю 185 від кожного елемента цього рядка матриці і в другому стовпці попередньої матриці віднімаю 56 від кожного елемента цього стовпця. Отримую матрицю наступного вигляду:

Нижня границя, мінімальна довжина маршруту комівояжера буде дорівнювати:

1226+185+56=1467.

Визначаю коефіцієнти для кожного з нулів матриці. Коефіцієнт дорівнює сумі мінімальних елементів того рядка і стовпця на перетині яких він знаходиться:

G₁₂=0+138=138; G₁₄=0+0=0; G₁₆=0+10=10; G₃₅=0+22=22;

G₄₅=0+10=10; G₅₄=0+27=27; G₆₁=0+10=10; G₆₄=0+0=0.

Вибираю максимальний G₁₂=138, викреслюю з попередньої матриці 1 рядок і 2 стовпець.

Отримаю матрицю наступного вигляду:

Роблю так, щоб в кожному рядку і стовпці матриці був хоча б один 0. Для цього у шостому стовпці попередньої матриці віднімаю 10 від кожного елемента цього рядка матриці. Отримую матрицю наступного вигляду:

Нижня границя, мінімальна довжина маршруту комівояжера буде дорівнювати:

1467+10=1477.

Визначаю коефіцієнти для кожного з нулів матриці. Коефіцієнт дорівнює сумі мінімальних елементів того рядка і стовпця на перетині яких він знаходиться:

G₃₅=0+22=22; G₄₅=0+0=0; G₄₆=0+141=141;

G₅₄=0+27=27; G₆₁=0+10=10; G₆₄=0+0=0.

Вибираю максимальний G₄₆=141, викреслюю з попередньої матриці 4 рядок і 6 стовпець, на місце (6; 4) ставлю ?.

Отримаю матрицю наступного вигляду:

Нижня границя, мінімальна довжина маршруту комівояжера не зміниться і буде дорівнювати: 1477.

Визначаю коефіцієнти для кожного з нулів матриці. Коефіцієнт дорівнює сумі мінімальних елементів того рядка і стовпця на перетині яких він знаходиться:

G₃₅=22+141=163; G₅₄=27+141=168;

G₆₁=22+141=163.

Вибираю максимальний G₅₄=168, викреслюю з попередньої матриці 5 рядок і 4 стовпець.

Отримаю матрицю наступного вигляду:

Нижня границя, мінімальна довжина маршруту комівояжера буде дорівнювати: 1477.

Знаходжу ребра графу, ними будуть ті ребра, які викреслювались з матриць на попередніх етапах і що залишилися в останній матриці:

(2; 3), (1; 2), (4; 6), (5; 4), (3; 1), (3; 5), (6; 1), (6; 5).

Будую граф з даними ребрами рис. 3:

Рис. 3.

Відповідь: нижня межа, мінімальна довжина маршруту комівояжера складатиме 1477. Граф, що зображений на рис. 3 буде оптимальним, при підсумовуванні ребер (що залишилися в ході розв’язку задачі) графа на рис. 3. вони дадуть значення, яке дорівнює 1477.

Список використаної літератури

1. Скляренко С. М. поштовий зв’язок: Підруч. Для вищ. навч. закл. Для спеціальностей за напрямом «Телекомунікації» / С. М. Скляренко, В. К. Стеклов, Л. Н. Беркман; за заг. ред. В. К. Стеклова. — 2-ге вид., стереотип. — К.: Техніка, 2004. — 904 с.

2. Ящук Л. О., Кріль С.С. Мережі та системи поштового зв’язку / О.: ОНАЗ ім. О. С. Попова, 2008. — 224 с.

3. Брагін А. С. Петрова В.М. Шматко В. С. Основи поштового зв’язку та його технології: Навч. посібник для студ. вищих навч. закл., які навч. за напрямом «Телекомунікації». — К.: Політехніка, 2004. — 439 c.