Методичні вказівки до виконання курсового проекту 1 страница
Сучасні міжнародні умови, до яких прагне Україна, вимагають в галузі логістики вантажних перевезень усе більшої уваги, стрімкого зростання та вдосконалення. Ефективність та якість вантажних перевезень значно залежать від оптимізації процесів координації роботи різних видів транспорту, раціонального розподілу між ними обсягів перевезень, своєчасного формування необхідних управлінських рішень. Найперше, особливу увагу при цьому потрібно звернути на два найважливіших показники транспортного обслуговування – вартість здійснення транспортних перевезень та строки виконання замовлень на доставку вантажів.
Аналіз наявних у вітчизняній і світовій практиці підходів до оптимізації перевезень пасажирів і вантажів у ТС виявив низку недоліків:
– неспроможність планувати перевезення пасажирів і вантажів із довільно орієнтованою матрицею транспортних кореспонденцій;
– наявність істотних обмежень на розмірність розв'язуваних транспортних завдань;
– недостатнє використання в перевізному процесі технологій спільної взаємодії різних видів транспорту;
– неможливість чіткої математичної формалізації більшості методів оптимізації перевезень на ТМ, що у свою чергу приводить до неможливості використання сучасних засобів інформаційних технологій.
Більшу частини перерахованих вище недоліків по оптимальному плануванню і маршрутизації вантажних перевезень у ТС знято за допомогою використання МММ представлення й управління вантажними перевезеннями на ТМ. Вирішення цього завдання має сприяти розв'язанню такої важливої проблеми національної економіки як підвищення ефективності управління вантажними перевезеннями у ТС України.
Розглянемо необхідні теоретичні відомості для використання МММ представлення й управління вантажними перевезеннями на ТМ.
3. МЕТОДИ ПОБУДОВИ ОПОРНИХ ПЛАНІВ ПЕРЕВЕЗЕНЬ ВАНТАЖУ
Перш ніж розпочинати оптимізацію транспортних перевезень вантажів, тобто застосувати один зі стандартних методів, необхідно побудувати опорний план перевезень, що надалі буде поступово поліпшуватися. Серед безлічі методів побудови опорних планів уваги заслуговують наступні – північно-західного кута (через свою простоту), найменшого елемента в усій транспортній таблиці (через свою економічність) і апроксимації Фогеля (через свою результативність). Розглянемо застосування усіх запропонованих у завданні на курсову роботу методів побудови опорних планів вантажу.
3.1. Метод північно-західного кута
Процес пошуку опорного плану перевезень у транспортної задачі розглянемо на конкретному прикладі. Відмітимо також, що всі без винятку спрощені методи розв’язання транспортної задачі базуються на транспортній таблиці (табл. 1).
В центрі кожної клітинки перехрестя (постачальники) і (споживачі) проставляються обсяги відповідних перевезень ( ), у її верхньому правому куті – відповідна вартість перевезення одиниці вантажу від до , тобто .
Із застосуванням транспортних таблиць транспортна задача формулюється наступним чином: визначити такі позитивні значення обсягів перевезень , сума яких по кожному і –му ряду ( ) дорівнює , і сума яких по кожній j-й колонці ( ) дорівнює , при цьому сума добутків ( ) по всіх клітинках буде мінімальною.
Згідно таблиці 1 маємо:
m = 3; n = 4.
а1 = 100; а2 = 120; а3 = 140;
b1 = 80; b2 = 100; b3 = 110; b4 = 70.
Таблиця1
Вихідна ТТ
B1 | B2 | B3 | B4 | Запаси ai | |
A1 | x11 | x12 | x13 | x14 | |
A2 | x21 | x22 | x23 | x24 | |
A3 | x31 | x32 | x33 | x34 | |
Заявки bj |
Заповнення обсягів перевезень починаємо з самої верхній лівої клітинки (звідси назва методу). Принцип заповнення: задовольнити максимально можливий обсяг замовлення ; якщо обсягу не вистачає, беремо частину від , якщо в щось залишається, віддаємо решту до і т.д. Для розглянутого випадку робимо наступне:
1. Задовольнимо за рахунок А1, решту відправимо до B2 (див. табл. 2). (Нижній індекс у обсягах перевезень показує черговість розподілу вантажу, а символ прочерку “–“ у деяких клітинках ТТ означає відсутність у них перевезень вантажу.);
Таблиця2
ТТ з розподілом запасів А1
B1 | B2 | B3 | B4 | Запаси ai | ai' | |
A1 | 801 | 202 | – | – | 100-80=20 20-20=0 | |
A2 | – | |||||
A3 | – | |||||
Заявки bj | ||||||
bj' | 80-80=0 | 100-20=80 |
2. Оскільки В2 ще не задовольнили, додамо необхідний обсяг за рахунок (ще 80); решту відправимо до В3 (див. табл. 3);
Таблиця3
ТТ з розподілом запасів А2
B1 | B2 | B3 | B4 | Запаси ai | ai' | |
A1 | 801 | 202 | – | – | ||
A2 | – | 803 | 404 | – | 120-80=40 40-40=0 | |
A3 | – | – | ||||
Заявки bj | ||||||
bj' | 80-80=0 | 110-40=70 |
3. Щоб повністю задовольнити В3, додамо необхідний обсяг за рахунок А3 (ще 70). Решту відправимо до В4, задовольнив таким чином його повністю (див. табл. 4).
Таблиця4
ТТ з розподілом запасів А3
B1 | B2 | B3 | B4 | Запаси ai | ai' | |
A1 | 801 | 202 | – | – | ||
A2 | – | 803 | 404 | – | ||
A3 | – | – | 705 | 706 | 140-70=70 70-70=0 | |
Заявки bj | ||||||
bj' | 70-70=0 | 70-70=0 |
Підрахуємо кількість ненульових перевезень (зайнятих клітинок). Таких є 6, що відповідає обов'язкової умові (m + n – 1) = (3 + 4 – 1) = 6. Оскільки суми перевезень по рядах і колонках відповідають і , отриманий план перевезень є можливим і опорним, тому що цей план є початковим. Для отриманого плану можливо підрахувати загальні витрати на здійснення всіх перевезень, тобто
умовних грошових одиниць (у.г.о.).
3.2. Метод північно-східного кута
Процес пошуку опорного плану перевезень за методом північно-східного кута розглянемо на тому же самому прикладі (див. табл. 1).
Заповнення обсягів перевезень починаємо з самої верхній правої клітинки (звідси назва методу). Принцип заповнення: задовольнити максимально можливий обсяг замовлення ; якщо обсягу не вистачає, беремо частину від , якщо в щось залишається, віддаємо решту до і т.д. Для розглянутого випадку робимо наступне:
1. Задовольнимо за рахунок А1, решту відправимо до B3 (див. табл. 5). (Нижній індекс у обсягах перевезень показує черговість розподілу вантажу, а символ прочерку “–“ у деяких клітинках ТТ означає відсутність у них перевезень вантажу.);
2. Оскільки В3 ще не задовольнили, додамо необхідний обсяг за рахунок А2 (ще 80); решту відправимо до В2 (див. табл. 6);
3. Щоб повністю задовольнити В2, додамо необхідний обсяг за рахунок А3 (ще 60). Решту відправимо до В1, задовольнив таким чином його повністю (див. табл. 7).
Підрахуємо кількість ненульових перевезень (зайнятих клітинок). Таких є 6, що відповідає обов'язкової умові (m + n – 1) = (3 + 4 – 1) = 6. Оскільки суми перевезень по рядах і колонках відповідають і , отриманий план перевезень є можливим і опорним, тому що цей план є початковим. Для отриманого плану можливо підрахувати загальні витрати на здійснення всіх перевезень, тобто
у.г.о.
Таблиця5
ТТ з розподілом запасів А1
B1 | B2 | B3 | B4 | Запаси ai | ai' | |
A1 | – | – | 302 | 701 | 100-70=30 30-30=0 | |
A2 | – | |||||
A3 | – | |||||
Заявки bj | ||||||
bj' | 110-30=80 | 70-70=0 |
Таблиця6
ТТ з розподілом запасів А2
B1 | B2 | B3 | B4 | Запаси ai | ai' | |
A1 | – | – | 302 | 701 | ||
A2 | – | 404 | 803 | – | 120-80=40 40-40=0 | |
A3 | – | – | ||||
Заявки bj | ||||||
bj' | 100-40=60 | 80-80=0 |
Таблиця7
ТТ з розподілом запасів А3
B1 | B2 | B3 | B4 | Запаси ai | ai' | |
A1 | – | – | 302 | 701 | ||
A2 | – | 404 | 803 | – | ||
A3 | 806 | 605 | – | – | 140-60=80 80-80=0 | |
Заявки bj | ||||||
bj' | 80-80=0 | 60-60=0 |
3.3. Метод південно-західного кута
Процес пошуку опорного плану перевезень за методом південно-західного кута розглянемо на тому же самому прикладі (див. табл. 1).
Заповнення обсягів перевезень починаємо з самої ніжній лівої клітинки (звідси назва методу). Принцип заповнення: задовольнити максимально можливий обсяг замовлення ; якщо обсягу не вистачає, беремо частину від , якщо в щось залишається, віддаємо решту до і т.д. Для розглянутого випадку робимо наступне:
1. Задовольнимо за рахунок А3, решту відправимо до B2 (див. табл. 8). (Нижній індекс у обсягах перевезень показує черговість розподілу вантажу, а символ прочерку “–“ у деяких клітинках ТТ означає відсутність у них перевезень вантажу.);
2. Оскільки В2 ще не задовольнили, додамо необхідний обсяг за рахунок А2 (ще 40); решту відправимо до В3 (див. табл. 9);
3. Щоб повністю задовольнити В3, додамо необхідний обсяг за рахунок А1 (ще 30). Решту відправимо до В4, задовольнив таким чином його повністю (див. табл. 10).
Таблиця8
ТТ з розподілом запасів А3
B1 | B2 | B3 | B4 | Запаси ai | ai' | |
A1 | – | |||||
A2 | – | |||||
A3 | 801 | 602 | – | – | 140-80=60 60-60=0 | |
Заявки bj | ||||||
bj' | 80-80=0 | 100-60=40 |
Таблиця9
ТТ з розподілом запасів А2
B1 | B2 | B3 | B4 | Запаси ai | ai' | |
A1 | – | – | ||||
A2 | – | 403 | 804 | – | 120-40=80 80-80=0 | |
A3 | 801 | 602 | – | – | ||
Заявки bj | ||||||
bj' | 40-40=0 | 110-80=30 |
Підрахуємо кількість ненульових перевезень (зайнятих клітинок). Таких є 6, що відповідає обов'язкової умові (m + n – 1) = (3 + 4 – 1) = 6. Оскільки суми перевезень по рядах і колонках відповідають і , отриманий план перевезень є можливим і опорним, тому що цей план є початковим. Для отриманого плану можливо підрахувати загальні витрати на здійснення всіх перевезень, тобто
у.г.о.
Таблиця10
ТТ з розподілом запасів А1
B1 | B2 | B3 | B4 | Запаси ai | ai' | |
A1 | – | – | 305 | 706 | 100-30=70 70-70=0 | |
A2 | – | 403 | 804 | – | ||
A3 | 801 | 602 | – | – | ||
Заявки bj | ||||||
bj' | 30-30=0 | 70-70=70 |
3.4. Метод південно-східного кута
Процес пошуку опорного плану перевезень за методом південно-східного кута розглянемо на тому же самому прикладі (див. табл. 1).
Заповнення обсягів перевезень починаємо з самої ніжній правої клітинки (звідси назва методу). Принцип заповнення: задовольнити максимально можливий обсяг замовлення ; якщо обсягу не вистачає, беремо частину від , якщо в щось залишається, віддаємо решту до і т.д. Для розглянутого випадку робимо наступне:
1. Задовольнимо за рахунок А3, решту відправимо до B3 (див. табл. 11). (Нижній індекс у обсягах перевезень показує черговість розподілу вантажу, а символ прочерку “–“ у деяких клітинках ТТ означає відсутність у них перевезень вантажу.);
2. Оскільки В3 ще не задовольнили, додамо необхідний обсяг за рахунок А2 (ще 40); решту відправимо до В2 (див. табл. 12);
3. Щоб повністю задовольнити В2, додамо необхідний обсяг за рахунок А1 (ще 20). Решту відправимо до В1, задовольнив таким чином його повністю (див. табл. 13).
Таблиця11
ТТ з розподілом запасів А3
B1 | B2 | B3 | B4 | Запаси ai | ai' | |
A1 | – | |||||
A2 | – | |||||
A3 | – | – | 702 | 701 | 140-70=70 70-70=0 | |
Заявки bj | ||||||
bj' | 110-70=30 | 70-70=0 |
Таблиця12
ТТ з розподілом запасів А2
B1 | B2 | B3 | B4 | Запаси ai | ai' | |
A1 | – | – | ||||
A2 | – | 802 | 403 | – | 140-40=80 80-80=0 | |
A3 | – | – | 702 | 701 | ||
Заявки bj | ||||||
bj' | 100-80=20 | 40-40=0 |
Підрахуємо кількість ненульових перевезень (зайнятих клітинок). Таких є 6, що відповідає обов'язкової умові (m + n – 1) = (3 + 4 – 1) = 6. Оскільки суми перевезень по рядах і колонках відповідають і , отриманий план перевезень є можливим і опорним, тому що цей план є початковим. Для отриманого плану можливо підрахувати загальні витрати на здійснення всіх перевезень, тобто
у.г.о.
Таблиця13
ТТ з розподілом запасів А1
B1 | B2 | B3 | B4 | Запаси ai | ai' | |
A1 | 806 | 205 | – | – | 100-20=80 80-80=0 | |
A2 | – | 804 | 403 | – | ||
A3 | – | – | 702 | 701 | ||
Заявки bj | ||||||
bj' | 80-80=0 | 20-20=0 |
3.5. Метод найменшого елемента строки ТТ