Приклад вирішення транспортної задачі за допомогою MS Excel
Транспортна задача є класичною задачею дослідження операцій. Безліч завдань розподілу ресурсів зводиться саме до цього завдання.
У господарстві є п'ять складів мінеральних добрив і чотири пункти, куди їх необхідно доставити. Потреба кожного пункту в мінеральних добривах різна, і запаси на кожному складі обмежені. Потрібно визначити, з якого складу, в який пункт поставляти, скільки мінеральних добрив для мінімізації вантажообігу перевезень.
Є такі вихідні дані.
Наявність мінеральних добрив на складах.
На перетині шпальти конкретного пункту доставки з рядком складу знаходиться інформація про відстані між цими пунктом доставки і складом. Наприклад, відстань між 3 пунктом і складом №3 дорівнює 10 кілометрам.
Для вирішення завдання підготуємо необхідні таблиці. (Рис. 1)
Рис.1 Змінні комірки.
Значення осередків по стовпчику В з четвертої по восьму рядок визначаються підсумовуванням даних осередків відповідних рядків починаючи з стовпця С до стовпчика F.
Наприклад, значення комірки B4 = СУММ (C4: F4)
Значення осередків по 9 рядку по стовпчиках від С до F визначаються підсумовуванням даних осередків відповідних стовпців з 4 по 8 рядка.
Наприклад, значення комірки С9 = СУММ (C4: C8)
Кожне значення в осередках на перетині шпальти конкретного пункту доставки та рядки складу означає кількість тонн, що поставляються з цього складу в даний пункт споживання. У нижньому рядку (рядок 9) підсумовується загальна кількість мінеральних добрив, що поставляються в певний пункт доставки, а в другому стовпці (стовпець В) підсумовується кількість доставленого з конкретного складу мінеральних добрив.
Тепер, використовуючи вихідні дані, введемо на цьому ж аркуші необхідні обсяги поставок і відстані між складами і пунктами доставки.
Рис.2 Вихідна інформація.
У рядку 16 за стовпцями C-F визначимо вантажообіг по кожному пункту доставки. Наприклад для 1 пункту (осередок С16) це розраховується за допомогою формули
С16 = С4 * С1 1 + С5 * С1 2 + С6 * С1 3 + С7 * С14 + С8 * С15
або можна використовувати функцію СУММПРОИЗВ
В осередку С4 знаходиться кількість мінеральних добрив, що перевозяться зі складу №1 в 1 пункт доставки, а в осередку С11 - відстань від складу №1 до 1 пункту доставки. Відповідно перший доданок у формулі означає повний вантажообіг по даному маршруту. Вся ж формула обчислює повний вантажообіг перевезень мінеральних добрив в 1 пункт доставки.
В осередку В16 за формулою = СУММ (С16: F 16) буде обчислюватися загальний обсяг вантажообігу мінеральних добрив.
Таким чином, інформація на робочому аркуші прийме такий вигляд (рис. 3)
Мал. 3. Робочий лист, підготовлений для вирішення транспортної задачі
Для вирішення транспортної задачі скористаємося процедурою Пошук рішення, яка знаходиться в меню Сервіс.
Після вибору даної команди з'явиться діалогове вікно (рис. 4).
Мал. 4. Діалогове вікно Пошук рішення
Оскільки в якості критерію оптимізації нами обрана мінімізація вантажообігу, в поле Встановити цільову осередок введіть посилання на клітинку, яка містить формулу розрахунку про бщего обсягу вантажообігу мінеральних добрив. У нашому випадку це осередок $ B $ 1 6. Щоб мінімізувати значення кінцевої комірки шляхом зміни значень впливають осередків (впливають, в даному випадку це і змінювані осередки, є осередки, які призначені для зберігання значень шуканих невідомих), перемикач встановіть в положення мінімального значення;
В поле Змінюючи осередки введіть посилання на змінювані осередки, розділяючи їх комами; або, якщо осередки знаходяться поруч, вказуючи першу і останню клітинку, розділяючи їх двокрапкою ($ З $ 4: $ F $ 8). Це означає, що для досягнення мінімального вантажообігу перевезень будуть змінюватися значення в осередках з С4 по F8. тобто будуть змінюватися кількість вантажу, перевезеного по конкретному маршруту.
Якщо зараз запустити процес підбору параметрів, то буде знайдено варіант, де всі змінні дорівнюють нулю. І це правильно - якщо не перевозити нічого, то це найдешевший варіант. Але нам необхідно перевезти мінеральні добрива, тому треба накласти деякі обмеження для пошуку рішення.
У групі полів Обмеження натисніть кнопку Додати. З'явиться діалог Додавання обмеження (рис. 5)
Мал. 5. Діалогове вікно Додавання обмеження
Слід ввести ліву частину обмеження в ліве поле, вибрати знак умови, що накладається на значення і ввести праву частину обмеження. Як і в інших випадках, можна не вводити посилання на комірки, а виділити мишею ці осередки. Після введення одного обмеження слід натиснути кнопку Додати і ввести наступне. Після закінчення введення всіх обмежень натисніть на кнопку ОК. У діалозі з'являться рядки введених обмежень (рис. 6)
Мал. 6. Діалогове вікно Пошук рішення з заповненими полями
Для зміни і видалення обмежень в меню Обмеження діалогового вікна Пошук рішення вкажіть обмеження, яке потрібно змінити або видалити. Виберіть команду Змінити і внесіть зміни або натисніть кнопку Видалити.
Розглянемо більш докладно умови, які слід накласти на значення в деяких осередках для правильного вирішення завдання.
Перша умова $ B $ 4: $ B $ 8 <=$B$11:$B$12. Оно означает, что значение в ячейке В4 должно быть меньше или равно значению в В11. в В5 меньше или равно, чем в В12. и так далее до В8 и В15.
В осередках з В4 по В8 на аркуші знаходяться обсяги поставок з конкретних складів. В осередках з В11 по В15 - запаси на цих же складах. Так як неможливо вивести зі складу більше, ніж на ньому є, перше значення повинно бути не більше другого.
Друга умова $ З $ 4: $ F $ 8> = 0. Воно означає, що обсяг перевезень не може бути негативним, тобто, якщо на складі не вистачає мінеральних добрив, їх не везуть з пункту доставки, на який ці мінеральні добрива були завезені раніше. Вантажопотік має тільки один напрямок - від складів до пунктів доставки добрив.
І. нарешті, третє, і остання умова $ З $ 9: $ F $ 9> = $ C $ 10: $ F $ 10. Воно означає, що значення в осередках дев'ятого рядка повинні бути більше або дорівнюють значенням в осередках десятої рядка. тобто запити пунктів доставки мінеральних добрив повинні бути виконані повністю. Перевиконання обсягу поставок допустимо, а недовиконання - немає.
Введені умови повинні дозволити знайти найбільш оптимальний варіант вирішення завдання. Натисніть кнопку Виконати для підбору рішення.
Після знаходження рішення з'являється діалог Результати пошуку рішення (рис. 7)
Мал. 7. Діалогове вікно Результати пошуку рішення
Натиснувши кнопку ОК, ви занесете варіант рішення на робочий лист (рис. 7).
Мал. 7. Вирішена транспортна задача
Мінімальний вантажообіг перевезень при дотриманні всіх умов дорівнює 3540 т.-км.