Автор работы: Пользователь скрыл имя, 15 Декабря 2013 в 19:19, курсовая работа
Метою даної роботи є створення універсальної програми, яка знаходить оптимальний результат розв’язку задач що зводяться до транспортної.
Сама програма буде створена за допомогою засобів програмування мови Turbo Paskal.
Для даної роботи поставлено три задачі:
Перша: Аналізувати задачі, що зводяться до розв’язання транспортної моделі (задачі), формалізувати зміст задач та обґрунтувати вибір методу їх розв’язку.
Друга: Побудовати алгоритм розв’язку ТЗ та проаналізувати його роботу.
Вступ…………………………………………………………………………………..4
Розділ І. Аналіз задач, що зводяться до розв’язання транспортної моделі (задачі), формалізація змісту задачі та розгляд методів її розв’язку............6
Розгляд задач, що трапляються в житті, і які зводяться до розв’язання транспортних ………………………………………………….…………..6
Початкові розв’язки ТЗ, опис методів, які дають початкові наближені результати………………………………………………………………...10
Метод потенціалів, як найбільш доцільніший та практичний метод розв’язку ТЗ………………..………………………………………….….16
Роздііл ІІ. Побудова алгоритму роботи програми для вирішення ТЗ……...21
2.1 Стандартний алгоритм розв’язку транспортної задачі…..……………..21
2.2 Загальний алгоритм роботи програми ………………….……………....23
2.3 Допоміжні алгоритми ………….………………………...………….…...25
Розділ ІІІ. Програмна реалізація алгоритму…………………….……………...26
3.1. Обгругтування вибіру мови………...………………………………….. 26
3.2. Опис роботи програми………………..…………….…………………..27
3.3. Допоміжні процедури та функції ………………...…………………….28
3.4. Інструкція користувача, аналіз роботи програми…………….………..29
3.5. Ідеї та методи вдосконалення програми……………………….……….30
Висновки……………………………………………………………………………..30
Використана література…………………………………………………….…….....32
Рисунок 5. – вартість перевезень
Сформулюємо лінійну модель ТЗ:
Min z = 80x11+215x12+100x21+108x22+
x11+x12=1000
x21+x22=1500
x31+x32=1200
x11+x21+x31=2300
x12+x22+x32=1400
xij≥0, i=1,2,3; j=1,2.
Знайти початковий розв’язок транспортної задачі можна трьома методами:
Різниця між цими методами полягає в якості відшукання початкового розв’язку, тобто наскільки початковий результат буде близьким до оптимального. Найчастіше метод Фогеля дає найкращий розв’язок, але метод північно-західного кута потребує менше обчислень.
Метод північно-західного кута[1]
Алгоритм починається з верхнього лівого кута транспортної таблиці, тобто з елемента X11.
Крок 1. Змінній X11 присвоюємо максимальне значення, яке допус- кається обмеженнями на попит та пропозицію.
Крок 2. Викреслюємо рядок з повністю вичерпаною пропозицією, або стовпчик з використаним попитом. У викресленому рядку або стовпчику не будемо присвоювати значення іншим змінним. Якщо одночасно використати і попит, і пропозицію, то викреслюється або рядок або стовпчик.
Крок 3. Якщо не викреслено тільки один рядок або один стовпчик, то процес завершуємо. В іншому випадку переходимо в комірку справа від викресленого стовпчика, або в нижнюю, якщо викреслено рядок. Повертаємося на крок 1.
Приклад. Транспортна компанія займається перевезенням зерна від трьох елеваторів до чотирьох млинів. В таблиці задані можливі пропозиції елеваторів та потреби чотирьох млинів, а також вартість перевезень зерна(Рис 6):
1 2 3 4 Пропозиція
10 X11 |
2 X12 |
20 X13 |
11 X14 |
|
12 X21 |
7 X22 |
9 X23 |
20 X24 |
|
4 X31 |
14 X32 |
16 X33 |
18 X34 |
1
15
Елеватори 2
25
3
10
Попит 5 15 15 15
Рисунок 6. – Попит-пропозиція
Якщо
застосувати процедуру
10
|
2 |
20 |
11 |
12 |
7
|
9
|
20 |
4 |
14 |
16 |
18 |
Цьому розв’язку відповідає
Сумарна вартість перевезень
Z=5*2+10*2+5*7+15*9+ +5*25+10*18=520$
Рисунок 7. – Метод ПЗ кута
Метод найменшої вартості[1]
Даний метод знаходить кращий початковий розв’язок, ніж метод північно-західного кута, оскільки обирає зміні, яким відповідають найменші вартості. Спочатку в транспортній таблиці шукаємо комірку з найменшою вартістю. Потім змінній в цій комірці присвоюємо найбільше допустиме значення, яке обмежено попитом та пропозицією. Якщо таких змінних декілька то вибір довільний. Далі викреслюємо відповідний стовпчик або рядок. Якщо одночасно виконуються обмеження і по попиту і по пропозиції, то викреслюємо або рядок або стовпчик. Потім переглядаються комірки, що залишилися і обирається нова комірка з мінімальною вартістю. Процес продовжується поки не залишиться один не викреслений рядок або стовпчик.
Застосуємо даний метод до попередньої задачі (Рис 8):
Крок 1. Комірка (1,2) має найменшу вартість (2$). Найбільше значення яке можна присвоїти цій комірці це 15. В цьому випадку задовольняються обмеження і по рядку і по стовпчику, тому пропозиція першого рядка і попит другого приймають нульові значення. Викреслюємо другий стовпчик.
Крок 2. Наступна комірка з найменшою вартістю буде (3,1). Присвоюємо цій комірці значення 5. Викреслюємо перший стовпчик, пропозиція в третьому рядку дорівнює 10-5=5.
Крок 3. Наступна комірка з найменшою вартістю (2,3). Зміна отримує значення 15, викреслюємо 3-й стовпчик. Далі йде комірка (1,4) зі значен- ням 0, викреслюємо 1-й рядок. Потім знаходимо змінні (3,4) та (2,4) і присвоюємо 5 та 10 відповідно.
1 2 3 4 Пропозиція
10
|
2
|
20
|
11
|
12
|
7 |
9
|
20
|
4 |
14 |
16 |
18 |
1
15
Елеватори 2
25
3
10
Попит 5 15 15 15
Рисунок 8. – Метод найменшої вартості
Початковий базисний розв'язок: X12=15, X14=0, X23=15, X24=10, X31=5, X34=5. Цьому розв’язкові відповідає сумарна вартість перевезень:
Z=15*2+5*4+15*9+11*0+10*20+5*
Метод Фогеля[1]
Метод Фогеля є варіацією метода найменшої вартості і дає кращий початковий розв'язок.
Крок 1. Для кожного рядка (стовпчика), якому відповідає строго додатня пропозиція (попит), обчислюємо штраф шляхом вінімання найменшої вартості із наступної по величині вартості в даному рядку (стовпчику).
Крок 2. Виділяємо рядок та стовпчик з найбільшим штрафом. Якщо таких декілька, то вибір довільний. Із виділеного рядка або стовпчика вибираємо зміну, якій відповідає мінімальна вартість, і їй присвоюємо найбільше допустиме значення. У відповідності з присвоєним значенням коректуємо величини попиту та пропозиції. Рядок або стовпчик, який відповідає обмеженню – викреслюємо. Якщо одночасно виконуються обмеженняі по попиту, і по пропозиції, то викреслюємо або рядок , або стовпчик, а рядку чи стовпчику, який залишиться – присвоюємо нульове значення.
Крок 3.
а) Якщо не викреслено лише один рядок чи стовпчик з нульовими пропозицією або попитом, то обчислення завершуються.
б) Якщо не викреслено лише один рядок чи стовпчик з додатнім значенням, то в цьому рядку (стовпчику) методом найменшої вартості знаходяться базисні розв'язки.
в) Якщо всім не викресленим рядкам або стовпчикам відповідають нульві значення, то методом найменшої вартості знаходяться нульові базисні зміні і обчислення завершуються.
г) В усіх інших випадках перехлдимо на крок 1.
Застосуємо метод Фогеля до попередньої задачі (Рис10):
1 2 3 4 Штрафи для рядків
10 |
2 |
20 |
11 |
12 |
7 |
9 |
20 |
4 5 |
14 |
16 |
18 |
1 10-2=8
15
2 9-7=2
25
3 14-4=10
10
5 15 15 15
10-4=6 7-2=5 16-9=7 18-11=7
Штрафи для стовпчиків
Рисунок 10. – Метод Фогеля
Оскільки третій рядок має найбільший штраф (10) і в цьому рядку найменша вартість в комірці (3,1), то змінній X31:=5 і перший стовпчик викреслюємо. Знову рахуємо штрафи:
1 2 3 4 Штрафи для рядків
10 |
2 15 |
20 |
11 |
12 |
7 |
9 |
20 |
4 5 |
14 |
16 |
18 |
1 11-2=9
15
2 9-7=2
25
3 16-14=2
10
0 15 15 15
7-2=5 16-9=7 18-11=7
Штрафи для стовпчиків
Рисунок 11. – Метод Фогеля 2
Перший рядок має найбільший штраф (9), тому змінній X12, якій відповідає найменша вартість присвоюємо значання 15, яке одночасно задовольняє обмеження і рядка, і стовпчика. Викреслюємо другий стовпчик, поклавши обсяг пропозицій, що відповідає першому рядку, рівним нулю.
Продовжуючи цей процес, знаходимо, що на наступному кроці другий рядок буде мати найбільший штраф (20-9=11). Тому змінній X23 присвоюємо значення 15. У результаті буде викреслено третій стовпець, у другому рядку залишиться нереалізованим пропозиція обсягом у 10 одиниць. Залишається не викресленим тільки четвертий стовпець з позитивним незадоволеним попитом обсягом у 15 одиниць. Застосовуючи метод найменшої вартості до цього стовпця, послідовно одержуємо X14=0, X34=5 i X24=10. Відповідне значення цільової функції дорівнює:
Z=15*2+0*11+15*9+10*20+5*4+5*
У даному випадку значення цільової функції таке ж, як і при застосуванні методу найменшої вартості. Але зазвичай метод Фогеля дає кращий початковий розв’язок транспортної задачі.
Після визначення
початкового розв’язку
Розглянемо цю ж задачу про транспортну компанію, використавши початковий розв’язок, отриманий методом північно-західного кута (Рис 12):
10 - |
2 + |
20 |
11 |
12 |
7 - |
9
|
20 + |
|
4 + |
14 |
16 |
18 - |
Информация о работе Розробка програми розв'язку транспортної задачі