Допомога у написанні освітніх робіт...
Допоможемо швидко та з гарантією якості!

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

КонтрольнаДопомога в написанніДізнатися вартістьмоєї роботи

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

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

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

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

№ варіанта

Вихідний пункт маршруту

Міста призначення

Існуючий зв’язок між містами (автомобільні дороги)

Відстань, км

Пропускна здатність, ПВ

Дніпропетровськ

Донецьк Луганськ Полтава Харків Черкаси

Дніпропетровськ — Донецьк

Дніпропетровськ — Полтава

Дніпропетровськ — Харків

Полтава — Харків

Донецьк — Луганськ

Луганськ — Харків

Донецьк — Харків

Черкаси — Полтава

Черкаси — Дніпропетровськ

Задача № 1

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

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

Рис. 1.

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

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

C23=min[C23; С2113]=min [148; 252+?]=148. C24=min[C24; С2114]=min [?; 252+196]=448.

C25=min[C25; С2115]=min [375; 252+213]=335. C26=min[C26; С2116]=min [?; 252+324]=576.

C34=min[C34; С3114]=min[?;?+196]=?. C35=min[C35; С3115]=min [333;?+213]=333.

C36=min[C36; С3116]=min[?;?+324]=?. C45=min[C45; С4115]=min [141; 196+213]=141.

C46=min[C46; С4116]=min [279; 196+324]=279. C56=min[C56; С5116]=min [?; 213+324]=537.

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

C13=min[C13; С1223]=min [?; 252+148]=400. C14=min[C14; С1224]=min [196; 252+448]=196.

C15=min[C15; С1225]=min [213; 252+335]=213.C16=min[C16; С1226]=min [324; 252+576]=324.

C34=min[C34; С3224]=min [?; 148+448]=596. C35=min[C35; С3225]=min [333; 148+335]=333.

C36=min[C36; С3226]=min [?; 148+576]=724. C45=min[C45; С4225]=min [141; 448+335]=141.

C46=min[C46; С4226]=min [279; 448+376]=279.C56=min[C56; С5226]=min [537; 335+576]=537.

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

C12=min[C12; С1332]=min [252; 400+148]=252.C14=min[C14; С1334]=min [196; 400+596]=196.

C15=min[C15; С1335]=min [213; 400+333]=213.C16=min[C16; С1336]=min [324; 400+724]=324.

C24=min[C24; С2334]=min [448; 148+596]=596.C25=min[C25; С2335]=min [335; 148+333]=335.

С26=min[C26; С2336]=min [576; 148+724]=576.C45=min[C45; С4335]=min [141; 596+333]=141.

C46=min[C46; С4336]=min [279; 596+724]=279.C56=min[C56; С5336]=min [537; 333+724]=537.

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

C12=min[C12; С1442]=min [252; 196+448]=252.C13=min[C13; С1443]=min [400; 196+448]=400.

C15=min[C15; С1445]=min [213; 196+141]=213.C16=min[C16; С1446]=min [324; 196+279]=324.

C23=min[C23; С2443]=min [148; 448+596]=148.C25=min[C25; С2445]=min [335; 448+141]=335.

С26=min[C26; С2446]=min [576; 448+279]=576.C35=min[C35; С3445]=min [335; 596+141]=333.

C36=min[C36; С3446]=min [724; 596+279]=724.C56=min[C56; С5446]=min [537; 141+279]=420.

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

C12=min[C12; С1552]=min [252; 196+335]=252.C13=min[C13; С1553]=min [400; 213+333]=400.

C14=min[C14; С1554]=min [196; 213+141]=196.C16=min[C16; С1556]=min [324; 213+420]=324.

C23=min[C23; С2553]=min [148; 335+333]=148.C24=min[C24; С2554]=min [448; 335+141]=448.

С26=min[C26; С2556]=min [576; 335+420]=576.C34=min[C34; С3554]=min [596; 333+141]=474.

C36=min[C36; С3556]=min [724; 333+420]=724.C46=min[C46; С4556]=min [279; 141+420]=279.

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

C12=min[C12; С1662]=min [252; 324+576]=252.C13=min[C13; С1663]=min [400; 324+724]=400.

C14=min[C14; С1664]=min [196; 324+279]=196.C15=min[C15; С1665]=min [213; 324+420]=213.

C23=min[C23; С2663]=min [148; 576+724]=148.C24=min[C24; С2664]=min [448; 576+279]=448.

С25=min[C25; С2665]=min [335; 576+420]=335.C34=min[C34; С3664]=min [474; 724+279]=474.

C35=min[C35; С3665]=min [333; 724+420]=333.C45=min[C45; С4665]=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.

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

G14=0+0=0; G16=0+10=10; G23=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 від кожного елемента цього стовпця. Отримую матрицю наступного вигляду:

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

1226+185+56=1467.

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

G12=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. Для цього у шостому стовпці попередньої матриці віднімаю 10 від кожного елемента цього рядка матриці. Отримую матрицю наступного вигляду:

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

1467+10=1477.

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

G35=0+22=22; G45=0+0=0; G46=0+141=141;

G54=0+27=27; G61=0+10=10; G64=0+0=0.

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

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

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

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

G35=22+141=163; G54=27+141=168;

G61=22+141=163.

Вибираю максимальний G54=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.

Показати весь текст
Заповнити форму поточною роботою