1. Формулювання завдання та вихідні дані
Є 5 постачальників (відправників) вантажу і 10получателей (споживачів) вантажу, з відомою кількістю вантажу в кожного з постачальників і потреби в ньому кожного одержувача (Таблиця 1.1 та 1.2). Визначено також відстані між ними (Таблиця 1.3).
Необхідно отримати оптимальний варіант закріплення одержувачів за постачальниками таким чином, щоб мінімізувати вантажообіг перевезень (тобто отримання найкоротших відстаней доставки вантажу).
Таблиця 1.1 - Обсяг відправлення вантажів
Таблиця 1.2 - Обсяг споживання вантажів, т
Таблиця 1.3 - Відстані між відправниками та споживачами, км
2. Рішення транспортної задачі розподільчим методом
Методика розрахунку
1) Розподіляємо вантаж по кожному стовпців клітці з найменшою відстанню. Після розподілу такі клітини називаються завантаженими (Таблиця 2.1).
2) Для перевірки оптимальності отриманого розподілу визначаємо спеціальні індекси (потенціали), які проставляємо в клітини допоміжної рядка і стовпця. Індекси визначають за наступним правилом: спочатку в клітці стовпця рядка В1 проставляємо нуль, а інші індекси розраховуємо виходячи з того, що їх сума повинна дорівнювати
відстані кожної завантаженої клітини. Потім визначаємо потенціали інших стовпців і рядків, виходячи з того, що u + v = c, при цьому визначаємо потенціали тільки рядків і стовпців, що містять завантажені клітини. У випадку, якщо кількість завантажених клітин виявиться меншою від кількості m + n-1 (де m-число рядків, n-число стовпців), то необхідно штучно завантажити відсутню кількість клітин, для цього в них проставляють нуль завантаження і після цього з такою клітиною оперують як із завантаженою. Доцільно нуль ставити в таку клітку, для якої один з індексів вже визначений, а також по можливості в клітку з найменшою відстанню.
3) Після цього знаходимо такі незавантажені клітини, в яких сума індексів більше, ніж зазначено у відповідних клітинах - такі клітини називаються потенційними. Цифру різниці між сумою індексів і відстанню називають потенціалом. Потенціал записуємо у відповідну незавантажених клітку в круглих дужках.
4) Знаходимо клітину з найбільшим потенціалом (ця умова є необов'язковим). Для вибраної потенційної клітини «будуємо» контур - замкнуту лінію, що складається з прямих горизонтальних і вертикальних ліній, всі вершини цієї лінії повинні знаходитися в завантажених клітинах, а також у вибраній потенційної. Контур будуємо за правилом - від обраної потенційної клітини веду пряму горизонтальну або вертикальну лінію до такої завантаженої клітини, якій під прямим кутом відповідає ще одна закачана клітка, і так до тих пір, поки лінія не замкнеться у вихідній потенційної клітці.
5) Після цього всім вершин контуру поперемінно присвоюємо знаки «-» і «+», починаючи з обраної потенційної.
6) З завантажень, позначених знаком «+», вибираємо найменшу.
7) Дану величину віднімаємо від завантажень зі знаком «+» і додаємо до Завантаженнями зі знаком «-».
Таблиця 2.1 - Первісне розподіл обсягу перевезень між відправниками та споживачами
8) Отримані нові значення завантажень записуємо в іншу таблицю (покращена значення). Після цього знову розраховуємо
спеціальні індекси, будуємо контур і так до тих пір, поки не буде потенційних клітин.
Таблиця 2.2 - Друге розподіл обсягу перевезень між відправниками та споживачами
Таблиця 2.3 - Третє розподіл обсягу перевезень між відправниками та споживачами
Таблиця 2.4 - Четверте розподіл обсягу перевезень між відправниками та споживачами
Таблиця 2.5 - П'яте розподіл обсягу перевезень між відправниками та споживачами
Таблиця 2.6 - Шосте розподіл обсягу перевезень між відправниками та споживачами
Таблиця 2.7 - Сьоме і остаточний розподіл обсягу перевезень між відправниками та споживачами
9) Після отримання остаточного розподілу обсягу перевезень між відправниками та споживачами вантажу визначаємо вантажообіг за такою залежністю:
n
Р = ΣQ i l i, т-км
i = 1
де Q i - обсяг i-ої перевезення вантажу, т; l i - відстань i-ої перевезення вантажу, км;
Р = 380 * 8 +150 * 3 +230 * 5 +190 * 2 +300 * 10 +60 * 8 +40 * 6 +200 * 5 +140 * 6 +
60 * 2 +150 * 6 +330 * 14 +870 * 9 +720 * 10 = 31250 т-км
3. Рішення транспортної задачі з використанням MS Excel
Спочатку готуємо необхідні таблиці на робочому листі MS Excel.
Таблиця 3.1 - Змінні в процесі рішення осередку
Є 5 постачальників (відправників) вантажу і 10получателей (споживачів) вантажу, з відомою кількістю вантажу в кожного з постачальників і потреби в ньому кожного одержувача (Таблиця 1.1 та 1.2). Визначено також відстані між ними (Таблиця 1.3).
Необхідно отримати оптимальний варіант закріплення одержувачів за постачальниками таким чином, щоб мінімізувати вантажообіг перевезень (тобто отримання найкоротших відстаней доставки вантажу).
Таблиця 1.1 - Обсяг відправлення вантажів
Наявність вантажу у відправника вантажу, т | ||||
Товарний склад № 1 | Товарний склад № 2 | КЖБІ № 1 | КЖБІ № 2 | ТОВ «Будівництво» |
A1 | A2 | A3 | A4 | A5 |
960 | 870 | 720 | 890 | 380 |
Вантажоодержувач | Умовне позначення | Потреба у вантажі, т. |
Об'єкт № 1 | B1 | 530 |
Об'єкт № 2 | B2 | 230 |
Об'єкт № 3 | B3 | 190 |
Об'єкт № 4 | B4 | 300 |
Об'єкт № 5 | B5 | 100 |
Об'єкт № 6 | B6 | 200 |
Об'єкт № 7 | B7 | 140 |
Об'єкт № 8 | B8 | 60 |
Об'єкт № 9 | B9 | 150 |
Об'єкт № 10 | B10 | 1920 |
Вантажоодержувач | Вантажовідправник | ||||
A1 | A2 | A3 | A4 | A5 | |
B1 | 6 | 6 | 7 | 8 | 3 |
B2 | 18 | 21 | 20 | 20 | 5 |
B3 | 2 | 15 | 14 | 15 | 4 |
B4 | 10 | 8 | 8 | 10 | 6 |
B5 | 6 | 9 | 8 | 8 | 8 |
B6 | 5 | 8 | 7 | 7 | 10 |
B7 | 6 | 6 | 7 | 8 | 15 |
B8 | 2 | 5 | 4 | 4 | 19 |
B9 | 17 | 3 | 5 | 6 | 6 |
B10 | 14 | 9 | 10 | 17 | 12 |
Методика розрахунку
1) Розподіляємо вантаж по кожному стовпців клітці з найменшою відстанню. Після розподілу такі клітини називаються завантаженими (Таблиця 2.1).
2) Для перевірки оптимальності отриманого розподілу визначаємо спеціальні індекси (потенціали), які проставляємо в клітини допоміжної рядка і стовпця. Індекси визначають за наступним правилом: спочатку в клітці стовпця рядка В1 проставляємо нуль, а інші індекси розраховуємо виходячи з того, що їх сума повинна дорівнювати
відстані кожної завантаженої клітини. Потім визначаємо потенціали інших стовпців і рядків, виходячи з того, що u + v = c, при цьому визначаємо потенціали тільки рядків і стовпців, що містять завантажені клітини. У випадку, якщо кількість завантажених клітин виявиться меншою від кількості m + n-1 (де m-число рядків, n-число стовпців), то необхідно штучно завантажити відсутню кількість клітин, для цього в них проставляють нуль завантаження і після цього з такою клітиною оперують як із завантаженою. Доцільно нуль ставити в таку клітку, для якої один з індексів вже визначений, а також по можливості в клітку з найменшою відстанню.
3) Після цього знаходимо такі незавантажені клітини, в яких сума індексів більше, ніж зазначено у відповідних клітинах - такі клітини називаються потенційними. Цифру різниці між сумою індексів і відстанню називають потенціалом. Потенціал записуємо у відповідну незавантажених клітку в круглих дужках.
4) Знаходимо клітину з найбільшим потенціалом (ця умова є необов'язковим). Для вибраної потенційної клітини «будуємо» контур - замкнуту лінію, що складається з прямих горизонтальних і вертикальних ліній, всі вершини цієї лінії повинні знаходитися в завантажених клітинах, а також у вибраній потенційної. Контур будуємо за правилом - від обраної потенційної клітини веду пряму горизонтальну або вертикальну лінію до такої завантаженої клітини, якій під прямим кутом відповідає ще одна закачана клітка, і так до тих пір, поки лінія не замкнеться у вихідній потенційної клітці.
5) Після цього всім вершин контуру поперемінно присвоюємо знаки «-» і «+», починаючи з обраної потенційної.
6) З завантажень, позначених знаком «+», вибираємо найменшу.
7) Дану величину віднімаємо від завантажень зі знаком «+» і додаємо до Завантаженнями зі знаком «-».
Таблиця 2.1 - Первісне розподіл обсягу перевезень між відправниками та споживачами
Пот-ре- бі-тель | Ін-декс | Постачальник | Пот-реб-ність у вантажі | |||||||||
A1 | A2 | A3 | A4 | A5 | ||||||||
u v | ||||||||||||
B1 | ||||||||||||
B2 | ||||||||||||
B3 | ||||||||||||
B4 | ||||||||||||
B5 | ||||||||||||
B6 | ||||||||||||
B7 | ||||||||||||
B8 | ||||||||||||
B9 | ||||||||||||
B10 | ||||||||||||
Наявність вантажу | 960 | 870 | 720 | 890 | 380 | 3820 | ||||||
спеціальні індекси, будуємо контур і так до тих пір, поки не буде потенційних клітин.
Таблиця 2.2 - Друге розподіл обсягу перевезень між відправниками та споживачами
Пот-ре- бі-тель | Ін-декс | Постачальник | Пот-реб-ність у вантажі | |||||||||
A1 | A2 | A3 | A4 | A5 | ||||||||
u v | ||||||||||||
B1 | ||||||||||||
B2 | ||||||||||||
B3 | ||||||||||||
B4 | ||||||||||||
B5 | ||||||||||||
B6 | ||||||||||||
B7 | ||||||||||||
B8 | ||||||||||||
B9 | ||||||||||||
B10 | ||||||||||||
Наявність вантажу | 960 | 870 | 720 | 890 | 380 | 3820 | ||||||
Пот-ре- бі-тель | Ін-декс | Постачальник | Пот-реб-ність у вантажі | |||||||||
A1 | A2 | A3 | A4 | A5 | ||||||||
u v | ||||||||||||
B1 | ||||||||||||
B2 | ||||||||||||
B3 | ||||||||||||
B4 | ||||||||||||
B5 | ||||||||||||
B6 | ||||||||||||
B7 | ||||||||||||
B8 | ||||||||||||
B9 | ||||||||||||
B10 | ||||||||||||
Наявність вантажу | 960 | 870 | 720 | 890 | 380 | 3820 | ||||||
Пот-ре- бі-тель | Ін-декс | Постачальник | Пот-реб-ність у вантажі | |||||||||
A1 | A2 | A3 | A4 | A5 | ||||||||
u v | ||||||||||||
B1 | ||||||||||||
B2 | ||||||||||||
B3 | ||||||||||||
B4 | ||||||||||||
B5 | ||||||||||||
B6 | ||||||||||||
B7 | ||||||||||||
B8 | ||||||||||||
B9 | ||||||||||||
B10 | ||||||||||||
Наявність вантажу | 960 | 870 | 720 | 890 | 380 | 3820 | ||||||
Пот-ре- бі-тель | Ін-декс | Постачальник | Пот-реб-ність у вантажі | |||||||||
A1 | A2 | A3 | A4 | A5 | ||||||||
u v | ||||||||||||
B1 | ||||||||||||
B2 | ||||||||||||
B3 | ||||||||||||
B4 | ||||||||||||
B5 | ||||||||||||
B6 | ||||||||||||
B7 | ||||||||||||
B8 | ||||||||||||
B9 | ||||||||||||
B10 | ||||||||||||
Наявність вантажу | 960 | 870 | 720 | 890 | 380 | 3820 | ||||||
Пот-ре- бі-тель | Ін-декс | Постачальник | Пот-реб-ність у вантажі | |||||||||
A1 | A2 | A3 | A4 | A5 | ||||||||
u v | ||||||||||||
B1 | ||||||||||||
B2 | ||||||||||||
B3 | ||||||||||||
B4 | ||||||||||||
B5 | ||||||||||||
B6 | ||||||||||||
B7 | ||||||||||||
B8 | ||||||||||||
B9 | ||||||||||||
B10 | ||||||||||||
Наявність вантажу | 960 | 870 | 720 | 890 | 380 | 3820 | ||||||
Пот-ре- бі-тель | Ін-декс | Постачальник | Пот-реб-ність у вантажі | |||||||||
A1 | A2 | A3 | A4 | A5 | ||||||||
u v | ||||||||||||
B1 | ||||||||||||
B2 | ||||||||||||
B3 | ||||||||||||
B4 | ||||||||||||
B5 | ||||||||||||
B6 | ||||||||||||
B7 | ||||||||||||
B8 | ||||||||||||
B9 | ||||||||||||
B10 | ||||||||||||
Наявність вантажу | 960 | 870 | 720 | 890 | 380 | 3820 | ||||||
n
Р = ΣQ i l i, т-км
i = 1
де Q i - обсяг i-ої перевезення вантажу, т; l i - відстань i-ої перевезення вантажу, км;
Р = 380 * 8 +150 * 3 +230 * 5 +190 * 2 +300 * 10 +60 * 8 +40 * 6 +200 * 5 +140 * 6 +
60 * 2 +150 * 6 +330 * 14 +870 * 9 +720 * 10 = 31250 т-км
3. Рішення транспортної задачі з використанням MS Excel
Спочатку готуємо необхідні таблиці на робочому листі MS Excel.
Таблиця 3.1 - Змінні в процесі рішення осередку
Постачальник | A1 | A2 | A3 | A4 | A5 | |
Споживач | ||||||
B1 | 5 | 1 | 1 | 1 | 1 | 1 |
B2 | 5 | 1 | 1 | 1 | 1 | 1 |
B3 | 5 | 1 | 1 | 1 | 1 | 1 |
B4 | 5 | 1 | 1 | 1 | 1 | 1 |
B5 | 5 | 1 | 1 | 1 | 1 | 1 |
B6 | 5 | 1 | 1 | 1 | 1 | 1 |
B7 | 5 | 1 | 1 | 1 | 1 | 1 |
B8 | 5 | 1 | 1 | 1 | 1 | 1 |
B9 | 5 | 1 | 1 | 1 | 1 | 1 |
B10 | 5 | 1 | 1 | 1 | 1 | 1 |
Факт | 10 | 10 | 10 | 10 | 10 |
Таблиця 3.2 - Вихідні дані для розв'язання транспортної задачі
Після використання процедури Пошук рішення отримуємо такі результати:
Таблиця 3.3 - Результати пошуку рішення
Висновок: в підсумку результати першого і другого способів рішень повністю збігаються, отриманий оптимальний варіант вантажообігу перевезень.
Запити | ||||||
Постачальник | A1 | A2 | A3 | A4 | A5 | |
Споживач | 590 | 1040 | 1260 | 560 | 380 | |
B1 | 530 | 6 | 6 | 7 | 8 | 3 |
B2 | 230 | 18 | 21 | 20 | 20 | 5 |
B3 | 190 | 2 | 15 | 14 | 15 | 4 |
B4 | 300 | 10 | 8 | 8 | 10 | 6 |
B5 | 100 | 6 | 9 | 8 | 8 | 8 |
B6 | 200 | 5 | 8 | 7 | 7 | 10 |
B7 | 140 | 6 | 6 | 7 | 8 | 15 |
B8 | 60 | 2 | 5 | 4 | 4 | 19 |
B9 | 150 | 17 | 3 | 5 | 6 | 6 |
B10 | 1920 | 14 | 9 | 10 | 17 | 12 |
Всього | 457 | 86 | 90 | 90 | 103 | 88 |
Таблиця 3.3 - Результати пошуку рішення
Оптимізація транспортних потоків | ||||||
Постачальник | A1 | A2 | A3 | A4 | A5 | |
Споживач | ||||||
B1 | 530 | 200 | 0 | 0 | 180 | 150 |
B2 | 230 | 0 | 0 | 0 | 0 | 230 |
B3 | 190 | 190 | 0 | 0 | 0 | 0 |
B4 | 300 | 0 | 0 | 0 | 300 | 0 |
B5 | 100 | 100 | 0 | 0 | 0 | 0 |
B6 | 200 | 0 | 0 | 0 | 200 | 0 |
B7 | 140 | 140 | 0 | 0 | 0 | 0 |
B8 | 60 | 0 | 0 | 0 | 60 | 0 |
B9 | 150 | 0 | 0 | 0 | 150 | 0 |
B10 | 1920 | 330 | 870 | 720 | 0 | 0 |
Факт | 960 | 870 | 720 | 890 | 380 | |
Запити | ||||||
Постачальник | A1 | A2 | A3 | A4 | A5 | |
Споживач | 590 | 1040 | 1260 | 560 | 380 | |
B1 | 530 | 6 | 6 | 7 | 8 | 3 |
B2 | 230 | 18 | 21 | 20 | 20 | 5 |
B3 | 190 | 2 | 15 | 14 | 15 | 4 |
B4 | 300 | 10 | 8 | 8 | 10 | 6 |
B5 | 100 | 6 | 9 | 8 | 8 | 8 |
B6 | 200 | 5 | 8 | 7 | 7 | 10 |
B7 | 140 | 6 | 6 | 7 | 8 | 15 |
B8 | 60 | 2 | 5 | 4 | 4 | 19 |
B9 | 150 | 17 | 3 | 5 | 6 | 6 |
B10 | 1920 | 14 | 9 | 10 | 17 | 12 |
Всього | 31250 | 7640 | 7830 | 7200 | 6980 | 1600 |