Транспортна задача.

Перевезення вантажів – це обов’язкова компонента нашого повсякденного життя. Тому задача про вартість такого перевезення та її оптимізацію є класичною. В процесі перевезення є дві сторони – постачальники транспортних послуг та одержувачі вантажів (покупці). Класична постановка транспортної задачі є закритою, це означає, що передбачається баланс між обсягами відправленого вантажу від постачальників та одержаного вантажу покупцями за критерієм мінімуму суми транспортних витрат. Якщо ж задача відкрита, то її приводять до закритого типу шляхом введення фіктивного постачальника або покупця.

У задачі відомі можливості кожного постачальника (потужність постачальника) і можливості кожного покупця (потужність покупця), тарифи на перевезення одиниці вантажу від кожного постачальника до кожного покупця.

У якості обмежень виступають умови по обов’язковому задовільненою потреб покупців та використанню всіх ресурсів постачальників.

Таблиця 5.4 Узагальнені дані транспортної задачі для чотирьох постачальників і чотирьох покупців

Математична модель задачі.

Змінні – кількість одиниць вантажу, який перевозиться від і-го постачальника до j-го покупця – х_ij.

Цільова функція: ,

де n – кількість постачальників,

m – кількість покупців,

Cij – тарифи на перевезення одиниці вантажу від і-го постачальника до j -го покупця,

Обмеження:

для постачальників ,

для покупців .

Приклад 5.2. Вантаж перевозиться від чотирьох постачальників чотирьом покупцям. Всі вхідні дані зведені у таб. 5.5. На перехресті рядків і стовпців вказані тарифи на перевезення. Необхідно скласти оптимальний план перевезень за критерієм мінімуму витрат.

Таблиця 5.5 Дані для приклада 5.2

Виконання.

1. Перевірка задачі на закритість – підрахувати суми потужностей покупців та постачальників (Разом по стовпцю і Разом по рядку). Обсяг вантажу у постачальників менше, ніж потрібно покупцям. З таб. 5.5 випливає, що сумарний обсяг вантажу у постачальників на 20 од. Менше, ніж потрібно покупцям.

Розв’язання такого типу задачі можна виконати двома способами:

Варіант 1. Привести задачу до класичного варіанту шляхом введення в таблицю Фіктивного постачальника з обсягом вантажу в 20 од. і з нульовими транспортними тарифами. Тоді будуть збалансовані обсяги і задача буде розв’язана класичним методом.

Варіант 2. Не вводити фіктивного постачальника, але тоді в системі обмежень змінити умови постачання покупцю: знак строгої рівності замінити на нестрогу рівність <=.

Розглянемо рішення задачі послідовно в двох варіантах.

2. Додамо в таблицю 5.5 рядок з фіктивним постачальником з обсягом постачання 20 од. та нульовими транспортними витратами (таб. 5.6).

3. Для застосування метода Поиск решения Excel необхідно підготувати чарунки так, як на рис. 5.6. Для скорочення запису цільової функції задачі варто використати математичну функцію СУММПРОИЗВ: =СУММПРОИЗВ(C16:F20;C4:F8).

Таблиця 5.6 Модифіковані дані для приклада 3.16

Рисунок 5.6 - Підготовка даних до використання методу Поиск решения

4. Викликати вікно метода Поиск решения та заповнити його (рис. 5.7).

Рисунок 5.7 – Заповнення полів вікна Поиск решения при розв’язанні транспортної задачі

В результаті рішення був одержаний наступний розподіл вантажних потоків (таб. 5.7):

Таблиця 5.7 - Результати розрахунків транспортної задачі

З таб. 5.7 випливає, що Покупець 1 недоотримав вантаж в обсязі 20 од., тому, що введення фіктивного постачальника необхідно було для балансування обсягів поставки з обсягами споживання.

Тепер розглянемо другий варіант розв’язання відкритої транспортної задачі.

З вхідної таблиці 5.5 бачимо, що потужність постачальників на 20 од. менше потужності споживачів, тому у діалоговому вікні Поиск решения обмеження по покупцям не можуть йти зі знаком «=», їх потрібно вказувати зі знаком «<=»:

Тоді в результаті оптимізації одержимо рішення у таб 5.8.

Порівняння результатів розв’язання задачі 1 і 2 способами показують їх ідентичність. Суми транспортних витрат співпадають. Різниця тільки в тому, що при введені фіктивного постачальника будуть збалансовані загальні обсяги поставок і потреби покупців на реальну величину недопостачання вантажу - 20 одиниць.

Таблиця 5.8 Результати розв’язання транспортної задачі за варіантом 2

У разі наявності у постачальників вантажу більше, ніж потребують покупці розв’язання задачі можна також виконувати будь-яким з приведених варіантів.

У разі використання покупцем послуг транспортних фірм мінімізація витрат покупця не буде задовольняти потреби постачальника послуг, якому потрібен максимум загальної вартості постачання. У цьому випадку має сенс використання консенсусного значення у діалоговому вікні Поиск решения для цільової чарунки (перемикач Значение).