кщо для всіх заповнених клітин дотримується умова
? vj - ui, (3)
то рішення оптимально і кожне знайдене число vj дає найкоротший відстані від пункту Ai до відповідного пункту Aj (j=1, 2, ... m). При наявності хоча б однієї клітини з величиною lij < vj - ui, рішення неоптимально і обчислення необхідно продовжити.
Визначимо найкоротша відстань від пункту А1 до всіх інших по мережі, даної в завданні і представленої у додатку. Використовуючи дані мережі складемо табл. 2.1.
Таблиця 2.1
ПунктыВспомогаельныеПунктыА 1 А 2 А 3 Б 1 Б 2 Б 3 Б 4 Б 5 АТП Строка/столбец076662253А 1 06223 А 2 78586 А 3 667 544 Б 1 67948 Б 2 68973 Б 3 22547 Б 4 225 434 Б 5 5843 АТП336834
Індекс u1 приймаємо рівним нулю. Далі відповідно до правила (1) знаходимо через клітини А1А3, А1Б3, А1Б4, А1АТП індекси v3, v6, v7, v9:
v3=u1 + l13=0 + 6=6, u3=v3=6,=u1 + l16=0 + 2=2, u6=v6=2,=u1 + l17=0 + 2=2, u7=v7=2,=u1 + l19=0 + 3=3, u9=v9=3.
Знайдені індекси записуємо в таблицю (див. табл. 2.1), після чого обчислюю індекс v8, через заповнені клітини А3Б5, Б4Б5:
v8=min (u3 + l38=6 +4=10; u7 + l78=2 + 3=5)=5,=v8=5.=min (u7 + l72=2 +5 =7; u7 + l82=5 + 8=13; u9 + l92=3 + 6=9)=7,
u2=v2=7.
v4=min (u3 + l34=6 +7=13; u6 + l64=2 + 4=6; u9 + l94=3 + 8=11)=6,=v4=6. =min (u2 + l25=7 + 8=15; u4 + l45=6 + 9=15; u6 + l65=2 + 7=9;
u9 + l95=3 + 3=6)=6,=v5=6.
Всі індекси знайдені, перевіряємо кожну заповнену клітину таблиці, порівнюючи її lij с (vj - ui). Тут дотримується умова оптимальності, тобто всі відстані менше різниці відповідних їм індексів, рішення є оптимальним і, отже, найкоротша відстань від А1 до всіх інших пунктів задано числами v1, v2, v3, v4, v5, v6, v7, v8, v9, тобто від А1 до А2 - 7 км, до А3 - 6 км, до Б1 , Б2 - 6 км, до Б3, Б4 - 2 км, до Б5 - 5 км, до АТП - 3 км.
Проробивши такі обчислення послідовно для кожного пункту А2, А3, Б1, АТП, приймаючи послідовно u2=0, потім u3=0 і т. д. отримаємо матрицю lij найкоротших відстаней (табл. 2.2) по мережі між двома пунктами.
Таблиця 2.2
ПунктиПунктиА 1 А 2 А 3 Б 1 Б 2 Б 3 Б 4 Б 5 АТПА 1 76662253А 2 791389586А 3 697115448Б 1 6137948118Б 2 681197793Б 3 29547475Б 4 25487434Б 5 584119937АТП36883547
3. ОПТИМІЗАЦІЯ вантажопотоків
Знаходження оптимальних вантажопотоків може бути виконано за допомогою транспортної задачі. Вирішити транспортну задачу - значить побудувати план перевезень таким чином, щоб потреба у вантажі всіх пунктів споживання була задоволена, весь вантаж з пунктів виробництва був вивезений і при цьому був забезпечений мінімум транспортної роботи в тонно-кілометрах.
Рішення транспортної задачі починається з прикріплення споживачів вантажу до постачальників.
.1 Побудова оптимального плану організації транспортного процесу
Оптимізації підлягає транспортна робота, тому в якості витрат в матрицю вводиться відстань між усіма пунктами. По кожному виду вантажу складається оптимальний план перевезень.
...
