Оптимізація планом перевезення поштовий відправлень ділянки Магістральної мережі за крітерієм мінімуму витрат на оброблення транзиту
Таблиця 1. Вихідні дані для виконан розрахунково-гарфічної роботи
№ варіантаВіхідній пункт маршрутуМіста прізначенняІснуючій зв язок между містамі (автомобільні дороги) Відстань, кмПропускна здатність, ПВ2ДніпропетровськДонецьк Луганськ Полтава Харків ЧеркасіДніпропетровськ - Донецьк252456Дніпропетровськ - Полтава196867Дніпропетровськ - Харків2131298Полтава - Харків141439Донецьк - Луганськ148908Луганськ - Харків333654Донецьк - Харків335378Черкасі - Полтава279532Черкасі - Дніпропетровськ324801
Завдання №1
Вікорістовуючі алгоритм Флойда, візначіті найкоротші маршрути между Вузли перевезень ПОШТА, если відомі місця Розташування вузлів поштового зв язку та відстані между ними.
За Даними табліці 1 будую граф (рис. 1) для розв язку задачі:
Рис. 1.
будую матрицю Довжина:
будую матрицю Довжина при k=1:
C 23=min [C 23; З 21 + З 13]=min [148; 252 +?]=148. C 24=min [C 24; З 21 + З 14]=min [?; 252 + 196]=448.
C 25=min [C 25; З 21 + З 15]=min [375; 252 + 213]=335. C 26=min [C 26; З 21 + З 16]=min [?; 252 + 324]=576.
C 34=min [C 34; З 31 + З 14]=min [?;? + 196]=?. C 35=min [C 35; З 31 + З 15]=min [333;? + 213]=333.
C 36=min [C 36; З 31 + З 16]=min [?;? + 324]=?. C 45=min [C 45; З 41 + З 15]=min [141; 196 + 213]=141.
C 46=min [C 46; З 41 + З 16]=min [279; 196 + 324]=279. C 56=min [C 56; З 51 + З 16]=min [?; 213 + 324]=537.
будую матрицю Довжина при k=2:
C 13=min [C 13; З 12 + З 23]=min [?; 252 + 148]=400. C 14=min [C 14; З 12 + З 24]=min [196; 252 + 448]=196.
C 15=min [C 15; З 12 + З 25]=min [213; 252 + 335]=213.C 16=min [C 16; З 12 + З 26]=min [324; 252 + 576]=324.
C 34=min [C 34; З 32 + З 24]=min [?; 148 + 448]=596. C 35=min [C 35; З 32 + З 25]=min [333; 148 + 335]=333.
C 36=min [C 36; З 32 + З 26]=min [?; 148 + 576]=724. C 45=min [C 45; З 42 + З 25]=min [141; 448 + 335]=141.
C 46=min [C 46; З 42 + З 26]=min [279; 448 + 376]=279.C 56=min [C 56; З 52 + З 26]=min [537; 335 + 576]=537.
будую матрицю Довжина при k=3:
C 12=min [C 12; З 13 + З 32]=min [252; 400 + 148]=252.C 14=min [C 14; З 13 + З 34]=min [196; 400 + 596]=196.
C 15=min [C 15; З 13 + З 35]=min [213; 400 + 333]=213.C 16=min [C 16; З 13 + З 36]=min [324; 400 + 724]=324.
C 24=min [C 24; З 23 + З 34]=min [448; 148 + 596]=596.C 25=min [C 25; З 23 + З 35]=min [335; 148 + 333]=335.
З 26=min [C 26; З 23 + З 36]=min [576; 148 + 724]=576.C 45=min [C 45; З 43 + З 35]=min [141; 596 + 333]=141.
C 46=min [C 46; З 43 + З 36]=min [279; 596 + 724]=279.C 56=min [C 56; З 53 + З 36]=min [537; 333 + 724]=537.
будую матрицю Довжина при k=4:
C 12=min [C 12; З 14 + З 42]=min [252; 196 + 448]=252.C 13=min [C 13; З 14 + З 43]=min [400; 196 + 448]=400.
C 15=min [C 15; З 14 + З 45]=min [213; 196 + 141]=213.C 16=min [C 16; З 14 + З 46]=min [324; 196 + 279]=324.
C 23=min [C 23; З 24 + З 43]=min [148; 448 + 596]=148.C 25=min [C 25; З 24 + З 45]=min [335; 448 + 141]=335.
З 26=min [C 26; З 24 + З 46]=min [576; 448 + 279]=576.C 35=min [C 35; З 34 + З 45]=min [335; 596 + 141]=333.
C 36=min [C 36; З 34 + З 46]=min [724; 596 + 279]=724.C 56=min [C 56; З 54 + З 46]=min [537; 141 + 279]=420.
будую матрицю Довжина при k=5:
C 12=min [C 12; З 15 + З 52]=min [252; 196 + 335]=252.C 13=min [C 13; З 15 + З 53]=min [400; 213 + 333]=400.
C 14=min [C 14; З 15 + З 54]=min [196; 213 + 141]=196.C 16=min [C 16; З 15 + З 56]=min [324; 213 + 420]=324.
C 23=min [C 23; З 25 + З 53]=min [148; 335 + 333]=148.C 24=min [C 24; З 25 + З 54]=min [448; 335 + 141]=448.
З 26=min [C 26; З 25 + З 56]=min [576; 335 + 420]=576.C 34=min [C 34; З 35 + З 54]=min [596; 333 + 141]=474.
C 36=min [C 36; З 35 + З 56]=min [724; 333 + 420]=724.C 46=min [C 46; З 45 + З 56]=min [279; 141 + 420]=279.
будую матрицю Довжина при k=6:
