Постановка транспортної задачі та її математична модель

💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

Транспортна задача полягає у пошуку найбільш вигідного плану перевезення однорідного продукту з пунктів виробництва (чи зберігання) до пунктів споживання, тобто від постачальників до споживачів, ефективність якого будемо оцінювати за критерієм найменшої вартості перевезення. Транспортна задача - це специфічна задача лінійного програмування.

Сформулюємо визначення транспортної задачі. Деяку однорідну продукцію, яка знаходиться в т постачальників А₁_, А₂,..., А_т кількістю a₁, а₂,..., а_т одиниць відповідно, потрібно перевезти п споживачам В₁, В₂,..., В_п в кількостях b₁, b₂,..., b_n одиниць. Відома матриця вартостей перевезення одиниці продукції від i -го постачальника до j -го споживача:

Необхідно скласти такий план перевезення, щоб вивезти всю продукцію від постачальників, задовольнити потреби всіх споживачів і сумарна вартість перевезення при цьому має бути мінімальною.

Окреслена постановка задачі вимагає виконання рівності загальної суми запасу вантажу загальній сумі потреб в ньому, тобто

Якщо в транспортній задачі умова (5.1) виконується, то таку транспортну задачу називають закритою (з правильним балансом). Якщо ж рівність (5.1) не виконується, то транспортну задачу називають відкритою (з неправильним балансом). Побудуємо математичну модель транспортної задачі. Оскільки наперед невідомо, скільки вантажу потрібно перевезти від певного постачальника до споживача, щоб план перевезень був оптимальним, то позначимо його через

. Вартість перевезення всього вантажу від постачальників до споживачів позначимо Z. Умову транспортної задачі можна записати у вигляді таблиці:

Для складання обмежень транспортної задачі скористаємося такими міркуваннями:

1) кількість вантажу, який потрібно перевезти до пункту В_j з усіх пунктів постачання, рівна

aспоживачеві В_j потрібно b_j -одиниць вантажу, тому, враховуючи те, що всі потреби повинні бути задоволеними, можемо записати обмеження стосовно потреб:

2) кількість вантажу, який треба вивезти з пункту постачання А_i до всіх споживачів, дорівнює

а постачальник має одиниць вантажу і всі вантажі мають бути вивезені, тому обмеження стосовно запасів матимуть вигляд:

В загальному випадку систему обмежень запишемо таким чином:

Ми отримали математичну модель транспортної задачі (5.2)-(5.3), де

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

- вартість перевезення одиниці продукції від i -го постачальника до j-го споживача;

- запаси продукції i -го постачальника; b_j - попит на продукцію j -го споживача.

Тепер, виходячи з економічної постановки транспортної задачі, можемо сформулювати її математичну задачу: серед всіх невід’ємних розв’язків системи рівнянь (5.3) знайти такий, при якому оптимізуюча форма (5.2) набуде найменшого значення.

Транспортна задача є задачею лінійного програмування, яку можна розв’язати симплекс-методом, але при розв’язуванні транспортної задачі симплексним методом ми б отримали симплекс-таблиці великих розмірів, оскільки число невідомих дорівнює

. Специфічна структура цієї задачі дозволяє використати для її розв’язання ефективніший метод - метод потенціалів, який розглянуто в п. 5.3.

Методи побудови початкового опорного плану

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