ІНСТИТУТ ТРАНСПОРТУ ТА ЗВ'ЯЗКУ
ФАКУЛЬТЕТ КОМП'ЮТЕРНИХ НАУК ТА ЕЛЕКТРОНІКИ
Курсова робота
Тема: "Рішення транспортної задачі"
Виконала: Долгополова Анастасія 4902BD
Рига
2010
Зміст
1. Постановка завдання
2. Формулювання завдання
3. Теоретичне обгрунтування. Загальні питання
4. Опис алгоритму знаходження потоку мінімальної вартості
5. Рішення індивідуального завдання по кроках
6. Програма (Mathcad)
7. Вихідні дані
8. Результат програми
9. Кінцеві результати
Висновок
1. Постановка завдання
Математична постановка задачі. Загальна постановка транспортної задачі полягає у визначенні оптимального плану перевезень деякого однорідного вантажу k-пунктів відправлення а 1 , а 2 , ... а i в m пунктів призначення b 1 , b 2 , ... b j . При цьому в якості критерію оптимальності зазвичай береться або мінімальна вартість всього вантажу, або мінімальний час його доставки. Дана транспортна задача була розглянута, де в якості критерію оптимальності була взята мінімальна вартість перевезень всі вантажу. Були введені наступні позначення:
k - Число постачальників;
m - число споживачів;
i - індекс виробника i = 1, до
j - індекс споживача j = 1, m
а 1 - Можливості i-ro виробника
bj - попит j-ro споживача
з i , j - транспортні витрати (витрати) за доставку продукції від i до j.
x i , j - Обсяги перевезень від i до j.
Потрібно скласти план перевезень для якого:
1. всі споживачі задоволені
2. загальні транспортні витрати мінімальні
Потрібно мінімізувати функцію:
Обмеження по виробництву:
Загальна сума виробленої продукції більше або дорівнює попиту:
Отже c i , j тарифи перевезень одиниці вантажу з i-го пункту відправлення в j-й пункт призначення, через a i - запаси вантажу в i-м пункті відправлення, через b j - потреби у вантажі в j-му пункті призначення, а через х i , j - кількість одиниць вантажу, перекладного з i-го пункту визначень в j-й пункт призначення. Тоді математична постановка транспортної задачі полягає в визначенні мінімального значення функції.
2. Формулювання завдання
Число виробників
k = 3
а 1 = 38
Обсяг виробленої продукції
а 2 = 45
а 3 = 97
Число споживачів
m = 4
b 1 = 42
b 2 = 35
Потреби споживачів:
b 3 = 63
B 4 = 15
Виробники
Споживачі
j = 1
j = 2
j = 3
j = 4
i = 1
10
11
18
32
i = 2
16
14
20
25
i = 3
26
28
22
30
Рис. 1
На малюнку 1 показано вихідний граф, який ілюструє транспортну задачу. Для вирішення даної завдання потрібно використовувати стандартну форму фіксованого джерела і стоку. Кожен виробник зв'язаний з кожним споживачем. Джерело не може мати зв'язки зі споживачем, але зате кожний споживач, у свою чергу, пов'язаний з фіктивним стоком. У позначенні дуги присутній два параметри. Перший параметр вказує пропускну здатність дуги, другий параметр показує вартість пересилання одиниці потоку на дузі. Так, наприклад, з джерела виходять дуги містять обмеження по пропускній здатності, тому дана величина характеризує продуктивну можливість кожного постачальника, вартість даної дуги дорівнює нулю, тому джерело - фіксований елемент нашого графа. Така ж ситуація з дугами, які втікають в стік. Дуги, які виходять з i-их вершин (виробники) і входять j-ті вершини (споживачі), тобто з'єднують постачальника зі складок, характеризуються теж двома параметрами. Тільки в цьому випадку, для даних дуг, в якості першого параметра береться пропускна здатність дуги рівна нескінченності, а другий показник - вартість пересилки одиниці потоку.
3. Теоретичне обгрунтування. Загальні питання
Мережа (Транспортна мережа) - окремий випадок орієнтованого графа. Транспортна мережа G = ( V, E) - Орієнтований граф, в якому кожне ребро має неотрицательную пропускну здатність. Виділяються дві вершини: джерело v і стік u такі, що будь-яка інша вершина мережі лежить на шляху з v в u. v - Це єдина вершина (v - Джерело), ​​яка не містить вхідних дуг, а містить тільки виходять дуги. u - це єдина вершина (u - стік), яка не містить виходять дуг. Всі інші вершини - проміжні вершини. Для будь проміжної вершини існує шлях з джерела в стік. Мережа не містить контурів. Якщо для мережі вказані пропускні спроможності, то така мережа називається транспортною мережею.
Потік - це певна величина на дузі тобто Потік в мережі G = ( V, E) - Це функція f, задана на дугах мережі, значення на дузі е - це величина на дузі тобто Для всіх проміжних вершин відповідає сума величин потоків на дугах входять у вершину w, яка дорівнює виходить з вершини потоку.
Величина потоку в мережі.
Величина всього потоку в мережі модуля дорівнює сумі величин потоку виходять з джерела або сумі вхідних величин потоку входять до стік.
Потік мінімальної вартості - задача про потік мінімальної вартості полягає в знаходженні самого дешевого способу передачі певної кількості потоку через транспортну мережу.
Позначення:
Для всіх дуг є пропускна здатність:
Вартість пересилання одиниці потоку по дузі e: C (e)
Накладаються наступні умови:
1. Обмеження пропускної спроможності. Потік не може перевищити пропускну спроможність.
2. Антисиметрична: . Потік з u в v повинен бути протилежний потоку з v в u.
4. Опис алгоритму знаходження потоку мінімальної вартості
Вхід: транспортна мережа G = (V, E) з пропускною здатністю дуг B (e)
Вихід: максимальний потік з мінімальною вартістю.
Ідея: Кожна ітерація ставить своєю метою збільшити потік в мережі. Для цих цілей призначений інкрементальний граф, який дозволяє збільшити потік на деяку фіксовану величину. Наявність прямих дуг дозволяє збільшити потік на відповідній дузі мережі. Зворотній дуга зменшує потік. Алгоритм закінчується коли в инкрементальное графі немає шляху від джерела до стоку.
Алгоритм:
Крок 0
Даний крок здійснюється тільки один раз. Спочатку ми присвоюємо всім дугам нульовий потік:
Крок 1
Для поточного потоку будується інкрементальний граф. Прямі дуги є, якщо потік на цій дузі менше, ніж пропускна здатність:
Зворотні дуги (дуги протилежні по відношенню до орієнтації прямих дуг) є, якщо на дугах мається потік.
Кожній дузі переписуємо вартість дуги. Якщо е пряма, то довга, ...
