§1. Постановка Транспортної завдання (ТЗ) для n змінних
§2. Приклад рішення Транспортної завдання
§3. Транспортні завдання за різними критеріями
§4. Рішення транспортної задачі в Excel
Під назвою "транспортна задача" об'єднується широке коло завдань з єдиною математичною моделлю. Класична транспортна задача - завдання про найбільш економному плані перевезень однорідного продукту або взаємозамінних продуктів з пунктів виробництва в пункти споживання, зустрічається найчастіше в практичних додатках лінійного програмування. Лінійне програмування є одним з розділів математичного програмування - області математики, що розробляє теорію і чисельні методи рішення багатовимірних екстремальних задач з обмеженнями.
Величезна кількість можливих варіантів перевезень ускладнює отримання досить економного плану емпіричним або експертним шляхом. Застосування математичних методів і обчислювальних в плануванні перевезень дає великий економічний ефект. Транспортні задачі можуть бути вирішені симплексним методом однак матриця системи обмежень транспортної задачі настільки своєрідна, що для її рішення розроблені спеціальні методи. Ці методи, як і симплексний метод, дозволяють знайти початкове опорне рішення, а потім, поліпшуючи його отримати оптимальне рішення.
Залежно від способу представлення умов транспортної задачі вона може бути представлена в мережевий (схематичною) або матричної (табличній) формі. Транспортна задача може також вирішуватися з обмеженнями і без обмежень.
§1. Постановка Транспортної завдання (ТЗ) дляnпеременних
Нехай є кілька постачальників однорідної продукції (кожен з певним запасом) і кілька споживачів цієї продукції (з відомими потребами у кожного). Задана також мережу комунікацій (доріг, річок, повітряних ліній і т.д.) зв'язує кожного постачальника з кожним споживачем. На кожній комунікації задана ціна перевезення - вартість перевезення одиниці продукції. Якщо будь - яка комунікація відсутня, то вважаємо, що вона є, але ціну перевезення на ній встановлюємо рівною нескінченності (+ ∞). Ця угода зробить невигідним перевезення по ній і автоматично виключить цю комунікацію з плану перевезень.
Таким чином, потрібно скласти план перевезень продукції від постачальників до споживачів так, щоб потреби споживачів були б задоволені за рахунок вивезення запасу від постачальників. Мета - мінімізація сумарної вартості всіх перевезень.
Транспортні задачі бувають:
1) відкриті m ≠ n (сумарний запас продукції, що є у постачальників, не збігається з сумарною потребою в продукції у споживачів.)
2) закриті m = n (сумарний запас продукції, що є у постачальників, збігається з сумарною потребою в продукції у споживачів.)
Метод потенціалів «працює» тільки для закритих ТЗ, причому, закрита ТЗ завжди можна вирішити.
Відкриту ТЗ зводять до закритої ТЗ шляхом додавання до сумарного запасу продукції або сумарної потреби продукції відсутніх одиниць до рівності сумарного запасу продукції і сумарною потреби продукції.
Закрита транспортна задача формулюється як Завдання Лінійного Програмування (ЗЛП) наступного вигляду:
1. Оптимальність порушена в клітці (3,3). Призначимо в неї перевезення # 952;> 0 (+ # 952; означає, збільшення на # 952;).
2.Нарушается баланс вивезення від постачальника 3 (вивозить 50+ # 952 ;, а це більше його запасу!). зменшуємо на # 952; перевезення в заповненій клітині рядка 3 (поза заповненої зменшувати не можна, так як це призведе до негативної перевезення).
Розглянемо ті клітини циклу в яких зменшуємо на # 952; перевезення і беремо мінімум з вичетаемих, у нас це min = 10.
І дане число треба підставити в цикл
§3. Транспортні завдання за різними критеріями
Транспортна задача за критерієм часу
Іноді виникає ситуація, коли в умовах (ТЗ) необхідно мінімізувати не вартість перевезень, а час їх виконання (Термінові вантажі, перевезення швидкопсувних продуктів, робота «швидкої допомоги» і т.д.)
Є m постачальників
однорідного вантажу і n споживачів
вантажу. Для кожної пари (
,
, за яке вантаж перевозиться від
. Потрібно скласти такий план перевезень, при якому всі запаси постачальників будуть вивезені, а всі запити споживачів будуть повністю задоволені і найбільший час доставки всіх вантажів буде мінімізований.
Задача про призначення (Угорський метод)
Є n видів робіт і n робочих. Кожен робітник може виконати будь-яку з nработ за деякий час (ціна робочого). Потрібно розподілити всі роботи між усіма робочими так, щоб час виконання робіт було мінімальним, а кожну роботу виконував тільки один робочий.
§4. Рішення транспортної задачі вExcel
Як приклад я розглянув транспортну задачу для 2 складів і 5 магазинів.
· В осередку C4: C5 записав обсяги продукції, що є на 2 складах.
· В осередку E5: I5 - заявки на продукцію, що надійшли від магазинів.
· В осередку B8: F9 - матрицю транспортних витрат, що задає витрати на перевезення з I-го складу в J-й магазин одиниці продукції.
· В осередку B13: F14 - план перевезень - матрицю, що задає кількість товару, перевезеного з I-го складу в J-й магазин. Початковий розподіл плану задано за принципом "кожній сестрі по сережці", рівномірно розподіливши всю наявну на складі продукцію по магазинах. Ці осередки є регульованими і Вирішувач повинен знайти більш підходяще рішення, змінивши значення в цих осередках.
· У осередок D15 - записав цільову функцію:
· В осередку D17: H17 записав обмеження, які визначають вимога про точне виконання заявки кожного магазину. Як завжди, я записав відповідну формулу в першу з цих осередків:
Потім скопіював її. При копіюванні формула автоматично змінюється, задаючи потрібне обмеження. Правда, потрібно стежити при цьому за правильною орієнтацією даних. Наприклад, в даному випадку формулу потрібно копіювати в рядок, а не в стовпець.
· Потім поставив наступну групу обмежень. Ці обмеження відповідають тому природному умові, що зі складу не можна відвести більше продукції, ніж там є. Формула, вміщена в клітинку D18, має вигляд:
Ця формула скопійована вже по стовпчику в клітинку D19. Підготовчий етап завершено - можна викликати Вирішувач.
При виклику розв'язувача і завданні параметрів в його діалоговому вікні виконувалася стандартна робота за вказівкою осередку з цільовою функцією, діапазоном регульованих осередків і завданням обмежень. Зауважте, крім двох груп обмежень я задав і обмеження целочисленности змінних. Передбачається, що продукція може перевозитися тільки цілими одиницями - бочками, мішками, ящиками. Такі обмеження в вирішувачі створюються зовсім просто, - досить серед операторів, що зв'язують ліву і праву частини обмеження, вибрати оператор int. Погляньте, як виглядають результати моєї роботи:
Мал. 2.21. Вікно розв'язувача при вирішенні транспортної задачі
Перш ніж дати команду на вирішення завдання, я провів настройку параметрів у вікні Options. Зокрема я включив прапорці, що вказують на лінійність моделі і позитивність змінних. Крім того, я збільшив точність рішення целочисленной завдання, задавши у вікні Tolerance значення в 1% замість 5%, прийнятих за замовчуванням.
Мал. 2.22. Налаштування у вікні параметрів розв'язувача при вирішенні транспортної задачі
Залишилося натиснути кнопку "Solve" і отримати оптимальний план перевезень. Ви можете проаналізувати, наскільки оптимальний план відрізняється від рівномірного розподілу, запропонованого в якості початкового варіанту, і як зменшилися транспортні витрати:
Мал. 2.23. Рішення транспортної задачі
Параметри, що керують роботою розв'язувача
Розглянемо можливості управління роботою розв'язувача, що задаються у вікні Параметри (Options):
· Максимальний час (MaxTime) - обмежує час, відведений на процес пошуку рішення. За замовчуванням задано 100 секунд, що зазвичай достатньо для задач невеликої розмірності, що мають близько 10 обмежень. Для задач великої розмірності доведеться це значення збільшувати.
· Граничне число ітерацій (Iterations) - ще один спосіб обмеження часу пошуку шляхом завдання максимального числа ітерацій. За замовчуванням задано 100, але це число можна збільшувати до 32767. Найчастіше, якщо рішення не отримано за 100 ітерацій, надій отримати його при збільшенні цього значення мало. Краще спробувати змінити початкове наближення і запустити процес пошуку заново.
· Відносна похибка (Precision) - задає точність виконання обмежень. Іноді простіше змінити обмеження, відсунувши кордон, ніж намагатися виконати обмеження з високою точністю.
· Відповідність (Convergence) - задається десятковим дробом, меншою одиниці, дозволяючи зупинити процес пошуку при збіжності рішення до нерухому точку, коли відносні зміни протягом останніх 5 ітерацій не перевищують задану дріб.
· Лінійна модель (Assume Linear Model) - цей прапорець слід включати, коли цільова функція і обмеження - лінійні функції. Ця додаткова інформація дозволяє вирішувачі спростити процес пошуку рішення.
· Позитивне значення (Assume Non-Negative) - цим прапорцем можна задати обмеження на змінні, що дозволить шукати рішення в позитивній області значень, не ставлячи спеціальних обмежень на їх нижню межу.
· Показувати результати ітерацій (Show Iteration Results) - прапорець, який дозволяє включити покроковий процес пошуку, показуючи на екрані результати кожної ітерації. У складних ситуаціях, коли Вирішувач не знаходить вирішення автоматично, рекомендується включати цей прапорець, так як іноді можна знайти точку, від якої процес пошуку ухилився в бік.
· Автоматичне масштабування (Use Automating Scaling) - прапорець автоматичної зміни масштабу слід включати, коли масштаб значень вхідних змінних і цільової функції і обмежень відрізняється, можливо, на порядки. Наприклад, змінні задаються в штуках, а цільова функція, що задає сумарну вартість, вимірюється в мільйонах карбованців.
· Відносна похибка (Tolerance) - задається у відсотках. Вказане значення має сенс тільки для задач з цілочисельними обмеженнями. Вирішувач в таких завданнях спочатку знаходить оптимальне НЕ целочисленное рішення, а потім намагається знайти найближчу целочисленную точку, рішення в якій відрізнялося б від оптимального не більше ніж на вказане даними параметром кількість відсотків. Якщо така точка знайдена, Вирішувач повідомляє про успіх. При великому допуск (за замовчуванням 5%) може бути втрачено краще целочисленное рішення, правда, що відрізняється від знайденого вирішувачі в межах допуску. Для цілочисельних задач допуск має сенс зменшити, що я і зробив при вирішенні транспортної задачі. Хочу ще раз звернути увагу на цю особливість вирішення завдань цілочисельного програмування. Якщо значення параметра Tolerance задати великим, то Вирішувач може зупинитися завчасно, не знайшовши кращого цілочисельного рішення. Якщо ж його взяти малим, то найкраще целочисленное рішення буде відрізнятися від оптимального нецілочисельне рішення на величину більшу, ніж ту, яка задається параметром Tolerance. В цьому випадку формально рішення закінчується неуспіхом, оскільки знайдене рішення не задовольняє всім вимогам. Звичайно, параметр Tolerance грає службову роль, і "розумний" Вирішувач, знайшовши найкраще целочисленное рішення, мав би повідомляти, що рішення знайдено, але обмеження по Tolerance не виконано. Цього, однак, не відбувається. Ми ще зіткнемося з цією ситуацією при розгляді наступного завдання.
· Зберегти модель (Save Model) - командна кнопка; дозволяє відкрити діалогове вікно, де можна вказати ім'я що зберігається моделі. Має сенс використовувати цю можливість, коли на робочому аркуші кілька моделей, так як єдина модель запам'ятовується автоматично.
· Завантажити модель (Load Model) - дозволяє завантажити одну зі збережених моделей.
· Є ще кілька більш спеціальних параметрів, якими можна управляти, варіюючи процедурами, застосовуваними в процесі пошуку. До них слід вдаватися в важких ситуаціях, коли рішення знайти не вдається.