- •Методичні вказівки
- •1. Опис дисципліни Мета і завдання вивчення дисципліни
- •2. Структура курсової роботи
- •На тему “розробка програмного комплексу по оптимізації вантажних перевезень на транспортної мережі”
- •До виконанні курсової роботи Завдання на курсову роботу
- •Методичні вказівки до виконання курсової роботи
- •Опорний план за методом мінімального вузла
- •Опорний план за методом мінімального вузла
- •Опорний план за методом мінімального вузла
- •Опорний план за методом випадкового
- •Перша ітерація тт
- •Друга ітерація тт
- •Третя ітерація тт
- •Четверта ітерація тт
- •П’ята ітерація тт
- •Шоста ітерація тт
- •Тт після розподілу вантажу у клітинку а3в2
- •Тт після розподілу вантажу у клітинку а1в4
- •Тт після розподілу вантажу у клітинку а2в1
- •Тт після розподілу вантажу у клітинку а1в4
- •Перша ітерація тт
- •Друга ітерація тт
- •Модифікований метод дейкстри (метод new) зведення сітьового представлення перевезень вантажу на тм до табличного виду – тт
- •1. Задача пошуку найкоротшого шляху між двома заданими вершинами
- •2. Задача пошуку найкоротших шляхів між заданими множинами вершин
- •Результуюча матриця найкоротших відстаней
- •Матрично-мережева модель управління перевезеннями вантажів в тс
- •Масив відстаней між сусідніми вузлами тм
- •Матриця транспортних кореспонденцій між всіма вузлами тм
- •Матриця найкоротших відстаней на тм
- •Опорний план перевезень
- •Тт з потенціалами
- •4. Література
- •Варіанти завдань по курсовій роботі
- •Обсяги поставок і замовлень продукції до структур тм з номерами варіантів від 1-го до 15-го
- •Обсяги поставок і замовлень продукції до структур тм з номерами варіантів від 16-го до 30-го
- •Вартість перевезення одиниці вантажу між сусідніми вузлами тм
- •Вантажу методом північна – західного кута
- •Текст процедури побудови опорного плану перевезень вантажу методом північна – східного кута
- •Текст процедури побудови опорного плану перевезень вантажу методом південна – західного кута
- •Текст процедури побудови опорного плану перевезень вантажу методом південна – східного кута
- •Текст процедури побудови опорного плану перевезень
- •Текст процедури побудови опорного плану перевезень
- •Текст процедури побудови опорного плану перевезень
- •Текст процедури побудови опорного плану перевезень
- •Текст процедури побудови опорного плану перевезень
- •Текст процедури побудови опорного плану перевезень
- •Текст процедури побудови опорного плану перевезень
- •Текст процедури побудови опорного плану перевезень
- •Текст програми на мові Delphi, яка реалізує симплексний метод рішення тз
- •Текст процедури на мові Pascal, яка реалізує алгоритм Дейкстри
- •Текст процедури на мові Delphy, яка реалізує метод графів
- •Завдання на курсову роботу студента
Тт після розподілу вантажу у клітинку а2в1
|
B1 |
B2 |
B3 |
B4 |
Запасиai |
A1 |
4 70
|
7
|
2
|
5 30
|
100 |
A2 |
3 10
|
6
|
1 110
|
8
|
120 |
A3 |
9
|
3 100
|
6
|
2 40
|
140 |
Заявки bj |
80 |
100 |
110 |
70 |
360 |
Більшість методів оптимізації транспортних задач, у тому числі і розподільний, використовують у процесі своєї роботи побудову замкнутих контурів по перерозподілу вантажопотоків. Необхідною умовою побудови таких контурів є наявність у транспортній таблиці m + n – 1 зайнятих кліток, а достатнім – їхнє спеціальне розташування в ній. Тому транспортні задачі, що мають вироджені опорні плани розподільним методом вирішені бути не можуть.
На рис. 4 представлена вихідна форма роботи програмного комплексу по побудові опорного плану розглянутої транспортної задачі методом північно-західного кута, а на рис. 4 – вихідна форма оптимального плану, побудованого розподільним методом.
Рис. 4. Вихідна форма з опорним планом транспортної задачі
Рис. 5. Вихідна форма з оптимальним планом транспортної задачі
3. Метод потенціалів оптимізації транспортних перевезень
Більш простим методом оптимізації плану перевезень є метод потенціалів, суть якого полягає у наступному.
1. Приймаємо будь-яке значення початкового потенціалу для i-го ряду транспортної таблиці; шукаємо заповнену клітку (ij), для якої і визначаємо відповідний потенціал по наступній формулі: Робимо аналогічні розрахунки для решти рядів і колонок таблиці, спираючись на вже розраховані транспортні потенціали.
2. Після визначення всіх i (;) перевіряємо нерівність для всіх (ij) незайнятих кліток таблиці (тобто для ). Якщо ця нерівність має місце для усіх без виключення незайнятих кліток, план перевезень є оптимальним.
3. Якщо у будь якій незайнятій клітці, то складений план перевезень не є оптимальним і підлягає корегуванню. Корегування полягає в заповненні незайнятих кліток, що мають , згідно правил перерозподілу вантажу по клітках, що вже застосовувалась раніше, при розгляданні розподільчого методу оптимізації плану перевезень. У тому випадку, коли таких незайнятих кліток виявиться декілька, то перевага віддається тієї з них, у якої добуток перевищення над на величину вантажу, що перерозподіляється по контуру, у цю клітку виявиться більшим.
При умові для незайнятої клітинки () означає, що перерозподіл вантажу в цю клітинку можливий, але це не поліпшує, ні погіршує план перевезень. Це означає, що є ще один план, еквівалентний по вартості перевезень. Тому в подальшому домовимось вважати, що клітинка залишається незайнятою при .
Наприклад, є певний опорний план перевезень (табл. 58). Відмітимо, що для отриманого плану маємо L1 = 30×7 + 70×2 + 80×3 + 40×1 + 70×3 + 70×2 = 980 у.г.о.
Розрахуємо потенціали і , використовуючи саме зайняті клітинки, і занесемо їх в додаткові стовпчик і рядок.
Приймаємо , тоді ; . Використовуючи вже отримані потенціали, визначаємо решту потенціалів:
; ;
; .
Перевіряємо опорний план на оптимальність, використовуючи отримані потенціали. Для цього перевіряємо умову оптимальності для всіх незайнятих клітинок плану, тобто :
; ; ;
; ; .
Таблиця 58
Вихідна ТТ
|
B1 |
B2 |
B3 |
B4 |
ui |
Запасиai |
A1 |
4
|
7 30
|
2 70 |
5 +
|
0 |
100 |
A2 |
3 80
|
6
|
1 40
|
8
|
-1 |
120 |
A3 |
9
|
3 70 +
|
6
|
2 70
|
-4 |
140 |
vj |
4 |
7 |
2 |
6 |
|
|
Заявки bj |
80 |
100 |
110 |
70 |
|
360 |
Опорний план не є оптимальним, тому що для клітинки . Це означає, що ця клітинка, як кажуть, є потенційною і має бути завантажена.
Для цього шукаємо контур, що містить у решті кутів зайняті клітинки. Це контур: (див. табл. 58). Оскільки ми завантажуємо , присвоюємо їй знак “+”, потім, пересуваючись по контуру, послідовно міняємо знаки. Мінімальне абсолютне значення від'ємного обсягу знаходиться в клітинці і дорівнює xп = 30 в.о. Пересуваємо цей обсяг по контуру з урахуванням знаків і отримуємо новий план перевезень (див. табл. 59), при цьому вартість його реалізації буде дорівнювати:
L2 = 70×2 + 30×5 + 80×3 + 40×1 + 100×3 + 40×2 = 950 у.г.о.
Порахуємо для нового плану перевезень нові значення потенціалів і , для цього знову приймаємо , тоді ; . Використовуючи вже отримані потенціали, визначаємо решту потенціалів: ; ;
.
Перевіряємо побудований план на оптимальність, використовуючи отримані потенціали, а саме:
; ; ;
; ; .
Таблиця 59