теоретичні відомості
Мета роботи: Придбання навичок побудови математичних моделей на прикладі транспортної задачі лінійного програмування та її рішення в Microsoft Excel.
Якщо в будь-якій системі (економічної, організаційної, військової і т.д.) наявних ресурсів не вистачає для ефективного виконання кожної з намічених робіт, то виникають так звані розподільні завдання. Мета рішення розподільної задачі - відшукання оптимального розподілу ресурсів по роботах. Під оптимальністю розподілу може розумітися, наприклад, мінімізація загальних витрат, пов'язаних з виконанням робіт, або максимізація отримуваного в результаті загального доходу.
Для вирішення таких завдань використовуються методи математичного програмування. Математичне програмування - це розділ математики, що займається розробкою методів відшукання екстремальних значень функції, на аргументи якої накладені обмеження. Слово "програмування" запозичене з зарубіжної літератури, де воно використовується в сенсі "планування". Найбільш простими і найкраще вивченими серед завдань математичного програмування є задачі лінійного програмування.
Характерні риси задач ЛП такі:
показник ефективності являє собою лінійну функцію, задану на елементах рішення;
обмежувальні умови, що накладаються на можливі рішення, мають вигляд лінійних рівностей або нерівностей.
У загальній формі записи модель задачі ЛП має вигляд:
Допустиме рішення - це сукупність чисел, що задовольняють обмеженням завдання
Оптимальне рішення - це план, при якому цільова функція приймає своє максимальне (мінімальне) значення.
Для побудови математичної моделі необхідно відповісти на наступні три питання.
Що є шуканими величинами, тобто змінними цього завдання?
У чому полягає мета, для досягнення якої з усіх допустимих значень змінних потрібно вибрати ті, які будуть відповідати найкращому, тобто оптимальному, рішенням?
Які обмеження повинні бути накладені на змінні, щоб виконувалися умови, описані в задачі?
Завдання про розміщення (транспортна задача) - це розподільна завдання, в якій роботи і ресурси вимірюються в одних і тих же одиницях. У таких завданнях ресурси можуть бути розділені між роботами, і окремі роботи можуть бути виконані за допомогою різних комбінацій ресурсів. Прикладом типової транспортної задачі є розподіл (транспортування) продукції, що знаходиться на складах, по підприємствам-споживачам.
Стандартна транспортна задача визначається як завдання розробки найбільш економічного плану перевезення продукції одного виду з декількох пунктів відправлення в пункти призначення. При цьому величина транспортних витрат прямо пропорційна обсягу перевезеної продукції і задається за допомогою тарифів на перевезення одиниці продукції.
Вихідні параметри моделі транспортної задачі:
-кількість пунктів відправлення, - кількість пунктів призначення.
-запас продукції в пункті відправлення [од. тов.].
-попит на продукцію в пункті призначення [од. тов.].
-тарифи (вартість) перевезення одиниці продукції з пункту відправлення в пункт призначення [руб. / од. тов.].
Шукані параметри моделі ТЗ:
-кількість продукції, що перевозиться з пункту відправлення в пункт призначення [од. тов.].
-Транспортні витрати на перевезення всієї продукції [руб.].
Етапи побудови моделі:
З моделі випливає, що сума запасів продукції в усіх пунктах відправлення повинна дорівнювати сумарній потреби у всіх пунктах споживання, тобто
Якщо це рівність виконується, то транспортна задача називається збалансованою. в іншому випадку - незбалансованою. Оскільки обмеження моделі можуть бути виконані тільки при збалансованій транспортної задачі, то при побудові транспортної моделі необхідно перевіряти умова балансу.
У разі, коли сумарні запаси перевищують сумарні потреби. необхідний додатковий фіктивний пункт споживання, який буде формально споживати існуючий надлишок запасів, тобто
Якщо сумарні потреби перевищують сумарні запаси. то необхідний додатковий фіктивний пункт відправлення, формально який заповнює існуючий недолік продукції в пунктах відправлення:
Введення фіктивного споживача або відправника спричинить необхідність формального завдання фіктивних тарифів (реально не існуючих) для фіктивних перевезень. Оскільки нас цікавить визначення найбільш вигоднихреальних перевезень, то необхідно передбачити, щоб при вирішенні задачі (при знаходженні опорних планів) фіктивні перевезення не розглядалися до тих пір, поки не будуть визначені всі реальні перевезення. Для цього треба фіктивні перевезення зробити невигідними, тобто дорогими, щоб при пошуку рішення задачі їх розглядали в найостаннішу чергу. Таким чином, величина фіктивних тарифів повинна перевищувати максимальний з реальних тарифів, використовуваних в моделі, тобто
.
На практиці можливі ситуації, коли в певних напрямках перевезення продукції неможливі, наприклад, через ремонт транспортних магістралей. Такі ситуації моделюються за допомогою введення так званих заборонних тарифів. Заборонні тарифи повинні унеможливити, тобто абсолютно невигідними, перевезення у відповідних напрямках. Для цього величина забороняють тарифів повинна перевищувати максимальний з реальних тарифів, використовуваних в моделі:
.