- •Методичні вказівки
- •1. Опис дисципліни Мета і завдання вивчення дисципліни
- •До виконання курсового проекту Завдання на курсовий проект
- •Методичні вказівки до виконання курсового проекту
- •Опорний план за методом мінімального вузла
- •Опорний план за методом мінімального вузла
- •Опорний план за методом мінімального вузла
- •Опорний план за методом випадкового
- •Перша ітерація тт
- •Друга ітерація тт
- •Третя ітерація тт
- •Четверта ітерація тт
- •П’ята ітерація тт
- •Шоста ітерація тт
- •Вихідна тт
- •Тт після розподілу вантажу у клітинку а1в4
- •5. Угорський метод розв’язання транспортної задачі про призначення
- •5.1. Постановка завдання
- •5.2. Розв’язання завдання
- •5.3. Приклад розв’язання задачі за допомогою угорського методу
- •Тт з оптимальним планом перевезень вантажу
- •Перша ітерація
- •6. Матрично-мережева модель управління
- •Масив відстаней між сусідніми вузлами тм
- •Матриця транспортних кореспонденцій між всіма вузлами тм
- •Матриця найкоротших відстаней на тм
- •Опорний план перевезень
- •Тт з потенціалами
- •7. Література
- •Варіанти завдань по курсового проекту
- •Обсяги поставок і замовлень продукції до структур тм з номерами варіантів від 1-го до 15-го
- •Обсяги поставок і замовлень продукції до структур тм з номерами варіантів від 16-го до 30-го
- •Вартість перевезення одиниці вантажу між сусідніми вузлами тм
- •Матриця Пij – продуктивності виконання I–м тз j–ї тр
- •Завдання на курсову роботу студента
Методичні вказівки до виконання курсового проекту
Сучасні міжнародні умови, до яких прагне Україна, вимагають в галузі логістики вантажних перевезень усе більшої уваги, стрімкого зростання та вдосконалення. Ефективність та якість вантажних перевезень значно залежать від оптимізації процесів координації роботи різних видів транспорту, раціонального розподілу між ними обсягів перевезень, своєчасного формування необхідних управлінських рішень. Найперше, особливу увагу при цьому потрібно звернути на два найважливіших показники транспортного обслуговування – вартість здійснення транспортних перевезень та строки виконання замовлень на доставку вантажів.
Аналіз наявних у вітчизняній і світовій практиці підходів до оптимізації перевезень пасажирів і вантажів у ТС виявив низку недоліків:
неспроможність планувати перевезення пасажирів і вантажів із довільно орієнтованою матрицею транспортних кореспонденцій;
наявність істотних обмежень на розмірність розв'язуваних транспортних завдань;
недостатнє використання в перевізному процесі технологій спільної взаємодії різних видів транспорту;
неможливість чіткої математичної формалізації більшості методів оптимізації перевезень на ТМ, що у свою чергу приводить до неможливості використання сучасних засобів інформаційних технологій.
Більшу частини перерахованих вище недоліків по оптимальному плануванню і маршрутизації вантажних перевезень у ТС знято за допомогою використання МММ представлення й управління вантажними перевезеннями на ТМ. Вирішення цього завдання має сприяти розв'язанню такої важливої проблеми національної економіки як підвищення ефективності управління вантажними перевезеннями у ТС України.
Розглянемо необхідні теоретичні відомості для використання МММ представлення й управління вантажними перевезеннями на ТМ.
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 |
4 x11
|
7 x12
|
2 x13
|
5 x14
|
100 |
A2 |
3 x21
|
6 x22
|
1 x23
|
8 x24
|
120 |
A3 |
9 x31
|
3 x32
|
6 x33
|
2 x34
|
140 |
Заявки bj |
80 |
100 |
110 |
70 |
360 |
Заповнення обсягів перевезень починаємо з самої верхній лівої клітинки (звідси назва методу). Принцип заповнення: задовольнити максимально можливий обсяг замовлення; якщо обсягуне вистачає, беремо частину від, якщо вщось залишається, віддаємо рештудоі т.д. Для розглянутого випадку робимо наступне:
Задовольнимо за рахунокА1, решту відправимо доB2 (див. табл. 2). (Нижній індекс у обсягах перевезень показує черговість розподілу вантажу, а символ прочерку “–“ у деяких клітинках ТТ означає відсутність у них перевезень вантажу.);
Таблиця 2
ТТ з розподілом запасів А1
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 801
|
7 202
|
2 –
|
5 –
|
100 |
100-80=20 20-20=0 |
A2 |
3 –
|
6
|
1
|
8
|
120 |
|
A3 |
9 –
|
3
|
6
|
2
|
140 |
|
Заявки bj |
80 |
100 |
110 |
70 |
360 |
|
bj' |
80-80=0 |
100-20=80 |
|
|
|
|
Оскільки В2 ще не задовольнили, додамо необхідний обсяг за рахунок (ще 80); рештувідправимо доВ3 (див. табл. 3);
Таблиця 3
ТТ з розподілом запасів А2
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 801
|
7 202
|
2 –
|
5 –
|
0 |
|
A2 |
3 –
|
6 803
|
1 404
|
8 –
|
120 |
120-80=40 40-40=0 |
A3 |
9 –
|
3 –
|
6
|
2
|
140 |
|
Заявки bj |
0 |
80 |
110 |
70 |
260 |
|
bj' |
|
80-80=0 |
110-40=70 |
|
|
|
Щоб повністю задовольнити В3, додамо необхідний обсяг за рахунок А3 (ще 70). Решту відправимо до В4, задовольнив таким чином його повністю (див. табл. 4).
Таблиця 4
ТТ з розподілом запасів А3
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 801
|
7 202
|
2 –
|
5 –
|
0 |
|
A2 |
3 –
|
6 803
|
1 404
|
8 –
|
0 |
|
A3 |
9 –
|
3 –
|
6 705
|
2 706
|
140 |
140-70=70 70-70=0 |
Заявки bj |
0 |
0 |
70 |
70 |
140 |
|
bj' |
|
|
70-70=0 |
70-70=0 |
|
|
Підрахуємо кількість ненульових перевезень (зайнятих клітинок). Таких є 6, що відповідає обов'язкової умові (m + n – 1) = (3 + 4 – 1) = 6. Оскільки суми перевезень по рядах і колонках відповідають і, отриманий план перевезень є можливим і опорним, тому що цей план є початковим. Для отриманого плану можливо підрахувати загальні витрати на здійснення всіх перевезень, тобто
умовних грошових одиниць (у.г.о.).
3.2. Метод північна – східного кута
Процес пошуку опорного плану перевезень за методом північна – східного кута розглянемо на тому же самому прикладі (див. табл. 1).
Заповнення обсягів перевезень починаємо з самої верхній правої клітинки (звідси назва методу). Принцип заповнення: задовольнити максимально можливий обсяг замовлення; якщо обсягуне вистачає, беремо частину від, якщо вщось залишається, віддаємо рештудоі т.д. Для розглянутого випадку робимо наступне:
Задовольнимо за рахунокА1, решту відправимо доB3 (див. табл. 5). (Нижній індекс у обсягах перевезень показує черговість розподілу вантажу, а символ прочерку “–“ у деяких клітинках ТТ означає відсутність у них перевезень вантажу.);
Оскільки В3 ще не задовольнили, додамо необхідний обсяг за рахунок А2 (ще 80); решту відправимо доВ2 (див. табл. 6);
Щоб повністю задовольнити В2, додамо необхідний обсяг за рахунок А3 (ще 60). Решту відправимо доВ1, задовольнив таким чином його повністю (див. табл. 7).
Підрахуємо кількість ненульових перевезень (зайнятих клітинок). Таких є 6, що відповідає обов'язкової умові (m + n – 1) = (3 + 4 – 1) = 6. Оскільки суми перевезень по рядах і колонках відповідають і, отриманий план перевезень є можливим і опорним, тому що цей план є початковим. Для отриманого плану можливо підрахувати загальні витрати на здійснення всіх перевезень, тобто
у.г.о.
Таблиця 5
ТТ з розподілом запасів А1
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7 –
|
2 302
|
5 701
|
100 |
100-70=30 30-30=0 |
A2 |
3
|
6
|
1
|
8 –
|
120 |
|
A3 |
9
|
3
|
6
|
2 –
|
140 |
|
Заявки bj |
80 |
100 |
110 |
70 |
360 |
|
bj' |
|
|
110-30=80 |
70-70=0 |
|
|
Таблиця 6
ТТ з розподілом запасів А2
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7 –
|
2 302
|
5 701
|
0 |
|
A2 |
3 –
|
6 404
|
1 803
|
8 –
|
120 |
120-80=40 40-40=0 |
A3 |
9
|
3
|
6 –
|
2 –
|
140 |
|
Заявки bj |
80 |
100 |
80 |
0 |
260 |
|
bj' |
|
100-40=60 |
80-80=0 |
|
|
|
Таблиця 7
ТТ з розподілом запасів А3
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7 –
|
2 302
|
5 701
|
0 |
|
A2 |
3 –
|
6 404
|
1 803
|
8 –
|
0 |
|
A3 |
9 806
|
3 605
|
6 –
|
2 –
|
140 |
140-60=80 80-80=0 |
Заявки bj |
80 |
60 |
0 |
0 |
140 |
|
bj' |
80-80=0 |
60-60=0 |
|
|
|
|
3.3. Метод південна – західного кута
Процес пошуку опорного плану перевезень за методом південна – західного кута розглянемо на тому же самому прикладі (див. табл. 1).
Заповнення обсягів перевезень починаємо з самої ніжній лівої клітинки (звідси назва методу). Принцип заповнення: задовольнити максимально можливий обсяг замовлення; якщо обсягуне вистачає, беремо частину від, якщо вщось залишається, віддаємо рештудоі т.д. Для розглянутого випадку робимо наступне:
Задовольнимо за рахунокА3, решту відправимо доB2 (див. табл. 8). (Нижній індекс у обсягах перевезень показує черговість розподілу вантажу, а символ прочерку “–“ у деяких клітинках ТТ означає відсутність у них перевезень вантажу.);
Оскільки В2 ще не задовольнили, додамо необхідний обсяг за рахунок А2 (ще 40); решту відправимо доВ3 (див. табл. 9);
Щоб повністю задовольнити В3, додамо необхідний обсяг за рахунок А1 (ще 30). Решту відправимо доВ4, задовольнив таким чином його повністю (див. табл. 10).
Таблиця 8
ТТ з розподілом запасів А3
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7
|
2
|
5
|
100 |
|
A2 |
3 – |
6
|
1
|
8
|
120 |
|
A3 |
9 801
|
3 602
|
6 –
|
2 –
|
140 |
140-80=60 60-60=0 |
Заявки bj |
80 |
100 |
110 |
70 |
360 |
|
bj' |
80-80=0 |
100-60=40 |
|
|
|
|
Таблиця 9
ТТ з розподілом запасів А2
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7 –
|
2
|
5
|
100 |
|
A2 |
3 – |
6 403
|
1 804
|
8 –
|
120 |
120-40=80 80-80=0 |
A3 |
9 801
|
3 602
|
6 –
|
2 –
|
0 |
|
Заявки bj |
0 |
40 |
110 |
70 |
220 |
|
bj' |
|
40-40=0 |
110-80=30 |
|
|
|
Підрахуємо кількість ненульових перевезень (зайнятих клітинок). Таких є 6, що відповідає обов'язкової умові (m + n – 1) = (3 + 4 – 1) = 6. Оскільки суми перевезень по рядах і колонках відповідають і, отриманий план перевезень є можливим і опорним, тому що цей план є початковим. Для отриманого плану можливо підрахувати загальні витрати на здійснення всіх перевезень, тобто
у.г.о.
Таблиця 10
ТТ з розподілом запасів А1
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7 –
|
2 305
|
5 706
|
100 |
100-30=70 70-70=0 |
A2 |
3 – |
6 403
|
1 804
|
8 –
|
0 |
|
A3 |
9 801
|
3 602
|
6 –
|
2 –
|
0 |
|
Заявки bj |
0 |
0 |
30 |
70 |
100 |
|
bj' |
|
|
30-30=0 |
70-70=70 |
|
|
3.4. Метод південна – східного кута
Процес пошуку опорного плану перевезень за методом південна – східного кута розглянемо на тому же самому прикладі (див. табл. 1).
Заповнення обсягів перевезень починаємо з самої ніжній правої клітинки (звідси назва методу). Принцип заповнення: задовольнити максимально можливий обсяг замовлення; якщо обсягуне вистачає, беремо частину від, якщо вщось залишається, віддаємо рештудоі т.д. Для розглянутого випадку робимо наступне:
Задовольнимо за рахунокА3, решту відправимо доB3 (див. табл. 11). (Нижній індекс у обсягах перевезень показує черговість розподілу вантажу, а символ прочерку “–“ у деяких клітинках ТТ означає відсутність у них перевезень вантажу.);
Оскільки В3 ще не задовольнили, додамо необхідний обсяг за рахунок А2 (ще 40); решту відправимо доВ2 (див. табл. 12);
Щоб повністю задовольнити В2, додамо необхідний обсяг за рахунок А1 (ще 20). Решту відправимо доВ1, задовольнив таким чином його повністю (див. табл. 13).
Таблиця 11
ТТ з розподілом запасів А3
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4
|
7
|
2
|
5 – |
100 |
|
A2 |
3
|
6
|
1
|
8 –
|
120 |
|
A3 |
9 –
|
3 –
|
6 702
|
2 701
|
140 |
140-70=70 70-70=0 |
Заявки bj |
80 |
100 |
110 |
70 |
360 |
|
bj' |
|
|
110-70=30 |
70-70=0 |
|
|
Таблиця 12
ТТ з розподілом запасів А2
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4
|
7
|
2 –
|
5 – |
100 |
|
A2 |
3 –
|
6 802
|
1 403
|
8 –
|
120 |
140-40=80 80-80=0 |
A3 |
9 –
|
3 –
|
6 702
|
2 701
|
0 |
|
Заявки bj |
80 |
100 |
40 |
0 |
220 |
|
bj' |
|
100-80=20 |
40-40=0 |
|
|
|
Підрахуємо кількість ненульових перевезень (зайнятих клітинок). Таких є 6, що відповідає обов'язкової умові (m + n – 1) = (3 + 4 – 1) = 6. Оскільки суми перевезень по рядах і колонках відповідають і, отриманий план перевезень є можливим і опорним, тому що цей план є початковим. Для отриманого плану можливо підрахувати загальні витрати на здійснення всіх перевезень, тобто
у.г.о.
Таблиця 13
ТТ з розподілом запасів А1
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 806
|
7 205
|
2 – |
5 – |
100 |
100-20=80 80-80=0 |
A2 |
3 –
|
6 804
|
1 403
|
8 –
|
0 |
|
A3 |
9 –
|
3 –
|
6 702
|
2 701
|
0 |
|
Заявки bj |
80 |
20 |
0 |
0 |
100 |
|
bj' |
80-80=0 |
20-20=0 |
|
|
|
|
3.5. Метод найменшого елемента строки ТТ
Цей метод укладається в тім, що першої заповнюють клітинку ТТ з найменшим значенням у першої строчці матриці, причому, а запаси1-го постачальника зменшаться до і заявкиj-го споживача до . При цьому, якщо, те з розгляду з таблиці викреслюється повністю1-й рядок (всі запаси 1-го постачальника використані), у противному випадку j-й стовпець (всі заявки j-го споживача задоволені). Якщо ж , то викреслюється і1-й рядок і j-й стовпець одночасно. Потім аналогічним способом заповнюється клітинка ТТ з найменшим зі значень у другої строчці матриці, і т.д. до останньої строки. Цей процес буде повторятися до тих пір, поки не буде одержано (m + n - 1) перевезень.
Розглянемо побудову опорного плану методом найменших елементів строки ТТ на нашому прикладі з таблиці 1.
На першому кроці заповнюємо клітинку з найменшим значенням= 2 у першої строчці ТТ; одержуємо нові значення= 100 – 100 = 0 і= 110 – 100 = 10. Викреслюємо в таблиці знаком “-“ з подальшого розгляду1-у строку (див. табл. 14).
Таблиця 14
ТТ з розподілом вантажу у клітинку А2В3
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7 –
|
2 1001
|
5 –
|
100 |
100-100=0 |
A2 |
3
|
6
|
1
|
8
|
120 |
|
A3 |
9
|
3
|
6
|
2
|
140 |
|
Заявки bj |
80 |
100 |
110 |
70 |
360 |
|
bj' |
|
|
110-100=10 |
|
|
|
Найменшим значенням у другої строчці ТТ володіє клітка(); одержуємо нові значення= 120 – 10 = 110 і= 10 – 10 =0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 3-й стовпець (див. табл. 15).
Найменшим значенням у третьої строчці таблиці володіє клітка(); одержуємо нові значення = 140 – 70 = 70 і= 70 – 70 = 0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 4-й стовпець (див. табл. 16).
Починаємо процес спочатку – з першої строки. Але запаси вантажу у першого постачальника А1 вичерпали, тому перейдемо до другої строки ТТ. Наступним найменшим значенням у другої строчці таблиці володіє клітка () ;одержуємо нові значення= 110 – 80 = 30 і= 80 – 80 = 0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 1-й рядок (табл. 17).
Таблиця 15
ТТ з розподілом вантажу у клітинку А3В4
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7 –
|
2 1001
|
5 –
|
0 |
|
A2 |
3
|
6
|
1 102
|
8
|
120 |
120-10=110 |
A3 |
9
|
3
|
6 –
|
2
|
140 |
|
Заявки bj |
80 |
100 |
10 |
70 |
260 |
|
bj' |
|
|
10-10=0 |
|
|
|
Таблиця 16
ТТ з розподілом вантажу у клітинку А2В1
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7 –
|
2 1001
|
5 –
|
0 |
|
A2 |
3
|
6
|
1 102
|
8 –
|
110 |
|
A3 |
9
|
3
|
6 –
|
2 703
|
140 |
140-70=70 |
Заявки bj |
80 |
100 |
0 |
70 |
250 |
|
bj' |
|
|
|
70-70=0 |
|
|
Наступним найменшим значенням у третьої строчці таблиці володіє клітка () ;одержуємо нові значення= 70 – 70 = 0 і= 100 – 70 = 30 (див. табл. 18).
Починаємо процес спочатку – з першої строки. Але запаси вантажу у першого постачальника А1 вичерпали, тому перейдемо до другої строки ТТ. Останнім незаповненим значенням у таблиці володіє клітка(); одержуємо нові значення= 30 – 30 = 0 і= 30 – 30 = 0 (див. табл. 19).
Таблиця 17
ТТ з розподілом вантажу у клітинку А3В2
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7 –
|
2 1001
|
5 –
|
0 |
|
A2 |
3 804 |
6
|
1 102
|
8 –
|
110 |
110-80=30 |
A3 |
9 –
|
3
|
6 –
|
2 703
|
70 |
|
Заявки bj |
80 |
100 |
0 |
70 |
180 |
|
bj' |
80-80=0 |
|
|
|
|
|
Таблиця 18
ТТ з розподілом вантажу у клітинку А1В1
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7 –
|
2 1001
|
5 –
|
0 |
|
A2 |
3 804 |
6
|
1 102
|
8 –
|
30 |
|
A3 |
9 –
|
3 705 |
6 –
|
2 703
|
70 |
170-70=0 |
Заявки bj |
0 |
100 |
0 |
70 |
100 |
|
bj' |
|
100-70=30 |
|
|
|
|
Одержали (m + n – 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:
у.г.о.
Таблиця 19
ТТ з розподілом вантажу у клітинку А1В2
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7 –
|
2 1001
|
5 –
|
0 |
|
A2 |
3 804 |
6 306
|
1 102
|
8 –
|
30 |
30-30=0 |
A3 |
9 –
|
3 705 |
6 –
|
2 703
|
0 |
|
Заявки bj |
0 |
30 |
0 |
70 |
100 |
|
bj' |
|
30-30=0 |
|
|
|
|
3.6. Метод найменшого елемента стовпця ТТ
Цей метод укладається в тім, що першої заповнюють клітинку ТТ з найменшим значенням у першому стовпці матриці, причому, а запасиi-го постачальника зменшаться до і заявки1-го споживача до . При цьому, якщо, те з розгляду з таблиці викреслюється повністюi-а строка (всі запаси i-го постачальника використані), у противному випадку 1-й стовпець (всі заявки 1-го споживача задоволені). Якщо ж , то викреслюється іi-й рядок і 1-й стовпець одночасно. Потім аналогічним способом заповнюється клітинка ТТ з найменшим зі значень у другому стовпці матриці, і т.д. до останнього стовпця. Цей процес буде повторятися до тих пір, поки не буде одержано (m + n - 1) перевезень.
Розглянемо побудову опорного плану методом найменших елементів стовпця ТТ на нашому прикладі з таблиці 1.
На першому кроці заповнюємо клітинку з найменшим значенням= 3 у першому стовпці ТТ; одержуємо нові значення= 120 – 80 = 40 і= 80 – 80 = 0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду1-й стовпець (див. табл. 20).
Таблиця 20
ТТ з розподілом вантажу у клітинку А2В3
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7
|
2
|
5
|
100 |
|
A2 |
3 801
|
6
|
1
|
8
|
120 |
120-80=40 |
A3 |
9 –
|
3
|
6
|
2
|
140 |
|
Заявки bj |
80 |
100 |
110 |
70 |
360 |
|
bj' |
80-80=0 |
|
|
|
|
|
Найменшим значенням у другому стовпці ТТ володіє клітка(); одержуємо нові значення= 140 – 100 = 40 і= 100 – 100 =0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 2-й стовпець (табл. 21).
Таблиця 21
ТТ з розподілом вантажу у клітинку А3В4
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7 –
|
2
|
5
|
100 |
|
A2 |
3 801
|
6 –
|
1
|
8
|
40 |
|
A3 |
9 –
|
3 1002
|
6
|
2
|
140 |
140-100=40 |
Заявки bj |
0 |
100 |
110 |
70 |
280 |
|
bj' |
|
100-100=0 |
|
|
|
|
Найменшим значенням у третьому стовпці таблиці володіє клітка(); одержуємо нові значення = 40 –40 = 0 і =110 – 40 = 70. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 2-у строку (табл. 22).
Таблиця 22
ТТ з розподілом вантажу у клітинку А2В1
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7 –
|
2
|
5
|
100 |
|
A2 |
3 801
|
6 –
|
1 403
|
8 –
|
40 |
40-40=0 |
A3 |
9 –
|
3 1002
|
6
|
2
|
40 |
|
Заявки bj |
0 |
0 |
110 |
70 |
180 |
|
bj' |
|
|
110-40=70 |
|
|
|
Найменшим значенням у четвертому стовпці таблиці володіє клітка(); одержуємо нові значення = 40 –40 = 0 і = 70 –40 = 30. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 3-у строку (табл. 23).
Таблиця 23
ТТ з розподілом вантажу у клітинку А3В2
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7 –
|
2
|
5
|
100 |
|
A2 |
3 801
|
6 –
|
1 403
|
8 –
|
0 |
|
A3 |
9 –
|
3 1002
|
6 –
|
2 404
|
40 |
40-40=0 |
Заявки bj |
0 |
0 |
70 |
70 |
140 |
|
bj' |
|
|
|
70-40=30 |
|
|
Починаємо процес спочатку – з першого стовпця. Але заявки вантажу у першого і другого споживача вже задоволені, тому перейдемо до третього стовпця ТТ. Наступним найменшим значенням у3-у стовпці ТТ володіє клітка () ;одержуємо нові значення= 100 – 70 = 30 і= 70 – 70 = 0 (табл. 24).
Таблиця 24
ТТ з розподілом вантажу у клітинку А1В1
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7 –
|
2 705
|
5
|
100 |
100-70=30 |
A2 |
3 801
|
6 –
|
1 403
|
8 –
|
0 |
|
A3 |
9 –
|
3 1002
|
6 –
|
2 404
|
0 |
|
Заявки bj |
0 |
0 |
70 |
30 |
100 |
|
bj' |
|
|
70-70=0 |
|
|
|
Наступним і останнім найменшим значенням у третьому стовпці таблиці володіє клітка () ;одержуємо нові значення= 30 – 30 = 0 і= 30 – 30 = 0 (табл. 25).
Таблиця 25
ТТ з розподілом вантажу у клітинку А1В2
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 –
|
7 –
|
2 705
|
5 306
|
30 |
30-30=0 |
A2 |
3 801
|
6 –
|
1 403
|
8 –
|
0 |
|
A3 |
9 –
|
3 1002
|
6 –
|
2 404
|
0 |
|
Заявки bj |
0 |
0 |
0 |
30 |
30 |
|
bj' |
|
|
|
30-30=0 |
|
|
Одержали (m + n – 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:
у.г.о.
3.7. Метод найменшого елемента ТТ
Цей метод укладається в тім, що першої заповнюють клітку з найменшим значенням у всій матриці, причому, а запасиi-го постачальника зменшаться до і заявкиj-го споживача до . При цьому, якщо, те з розгляду з таблиці викреслюється повністюі-й рядок (всі запаси i-го постачальника використані), у противному випадку j-й стовпець (всі заявки j-го споживача задоволені). Якщо ж , то викреслюється іi-й рядок і j-й стовпець одночасно. Потім аналогічним способом заповнюється клітка з найменшим зі значень , що залишилися в таблиці , і т.д. до одержання (m + n - 1) перевезень.
Розглянемо побудову опорного плану методом найменших елементів на нашому прикладі з таблиці 1.
На першому кроці заповнюємо клітку з найменшим значенням= 1; одержуємо нові значення= 120 – 110 = 10 і= 110 – 110 = 0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 3-й стовпець (див. табл. 26).
Наступним найменшим значенням у таблиці володіє клітка();одержуємо нові значення= 140 – 70 = 70 і= 70 – 70 =0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 4-й стовпець (див. табл. 27).
Таблиця 26
ТТ з розподілом вантажу у клітинку А2В3
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4
|
7
|
2 –
|
5
|
100 |
|
A2 |
3
|
6
|
1 1101
|
8
|
120 |
120-110=10 |
A3 |
9
|
3
|
6 –
|
2
|
140 |
|
Заявки bj |
80 |
100 |
110 |
70 |
360 |
|
bj' |
|
|
110-110=0 |
|
|
|
Таблиця 27
ТТ з розподілом вантажу у клітинку А3В4
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4
|
7
|
2 –
|
5 –
|
100 |
|
A2 |
3
|
6
|
1 1101
|
8 –
|
10 |
|
A3 |
9
|
3
|
6 –
|
2 702
|
140 |
140-70=70 |
Заявки bj |
80 |
100 |
0 |
70 |
250 |
|
bj' |
|
|
|
70-70=0 |
|
|
Наступним найменшим значенням у таблиці володіє клітка() і клітка() – беремо першу з них, тобто; одержуємо нові значення = 10 – 10 = 0 і= 80 – 10 = 70 (див. табл. 28).
Наступним найменшим значенням у таблиці володіє клітка() ;одержуємо нові значення= 70 – 70 = 0 і= 100 – 70 = 30. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 3-й рядок (табл. 29).
Таблиця 28
ТТ з розподілом вантажу у клітинку А2В1
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4
|
7
|
2 –
|
5 –
|
100 |
|
A2 |
3 103
|
6 –
|
1 1101
|
8 –
|
10 |
10-10=0 |
A3 |
9
|
3
|
6 –
|
2 702
|
70 |
|
Заявки bj |
80 |
100 |
0 |
0 |
180 |
|
bj' |
80-10=70 |
|
|
|
|
|
Таблиця 29
ТТ з розподілом вантажу у клітинку А3В2
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4
|
7
|
2 –
|
5 –
|
100 |
|
A2 |
3 103
|
6 –
|
1 1101
|
8 –
|
0 |
|
A3 |
9 –
|
3 704
|
6 –
|
2 702
|
70 |
70-70=0 |
Заявки bj |
70 |
100 |
0 |
0 |
170 |
|
bj' |
|
100-70=30 |
|
|
|
|
Наступним найменшим значенням у таблиці володіє клітка() ;одержуємо нові значення= 100 – 70 = 30 і= 70 – 70 = 0. Викреслюємо в таблиці знаком “-“ з подальшого розгляду 1-й стовпець (див. табл. 30).
Останнім найменшим значенням у таблиці володіє клітка() ;одержуємо нові значення= 30 – 30 = 0 і= 30 – 30 = 0 (див. табл. 31).
Таблиця 30
ТТ з розподілом вантажу у клітинку А1В1
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 705
|
7
|
2 –
|
5 –
|
100 |
100-70=30 |
A2 |
3 103
|
6 –
|
1 1101
|
8 –
|
0 |
|
A3 |
9 –
|
3 704
|
6 –
|
2 702
|
0 |
|
Заявки bj |
70 |
30 |
0 |
0 |
100 |
|
bj' |
70-70=0 |
|
|
|
|
|
Таблиця 31
ТТ з розподілом вантажу у клітинку А1В2
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
ai' |
A1 |
4 705
|
7 306
|
2 –
|
5 –
|
30 |
30-30=30 |
A2 |
3 103
|
6 –
|
1 1101
|
8 –
|
0 |
|
A3 |
9 –
|
3 704
|
6 –
|
2 702
|
0 |
|
Заявки bj |
0 |
30 |
0 |
0 |
30 |
|
bj' |
|
30-30=0 |
|
|
|
|
Одержали (m + n – 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:
у.г.о.
3.8. Метод мінімального вузла відправлення вантажу ТТ
Метод мінімального вузла відправлення вантажу побудови опорного плану перевезень, який поєднує кращі якості перерахованих вище методів також розглянемо на конкретному прикладі (див. табл. 1).
Спочатку знайдемо суми вартостей перевезення одиниці вантажу окремо по рядках (Сі , i = 1,m) ТТ і відсортуємо отримані величини у порядку їх зростання (табл. 32). Порядкові номери зростання сум проставлені у вигляді нижніх індексів відповідних величин.
Таблиця 32
Вихідна ТТ
|
B1 |
B2 |
B3 |
B4 |
Запаси ai |
Ci
|
A1 |
4 x11
|
7 x12
|
2 x13
|
5 x14
|
100 |
181
|
A2 |
3 x21
|
6 x22
|
1 x23
|
8 x24
|
120 |
182
|
A3 |
9 x31
|
3 x32
|
6 x33
|
2 x34
|
140 |
203
|
Заявки bj |
80 |
100 |
110 |
70 |
360 |
|
Заносити обсяги перевезень починаємо з вузла, який має найменшу суму вартостей одиниці перевезень вантажу по окремому рядку – вузлу відправлення вантажу (звідси і назва методу). Подальший процес формування опорного плану буде відбуватися у відповідності з порядковими номерами зростання сум вартостей перевезень одиниці вантажу вузлів відправлення, що залишилися і т.д., до одержання (m + n - 1) перевезень. Принцип заповнення клітинок ТТ у самому рядку буде наступним: максимально задовольнити весь обсяг замовлення вантажу в першу чергу за рахунок найменших вартостей перевезень одиниці вантажу.
У нашому прикладі процес побудови опорного плану методом мінімального вузла відправлення вантажу відображений у табл. 33, причому нижній індекс у обсягах перевезень вказує на черговість розподілу вантажу.
Таблиця 33