Оптимізація рішення транспортної задачі (оптимізація розподілу постачань).

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

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

При переміщенні по циклу k одиниць ресурсу зміна вартості складе Δ W=k ´ b_ij. При цьому значення ресурсу в клітках зі знаком «+» збільшиться на k, а в клітках зі знаком «-» - зменшиться на k.

Значення k вибирається серед кліток циклу, що мають знак «-». Крім того, воно має мінімальне значення серед цих кліток, отже k = min{2, 4} = 2, тобто це буде клітка B2. Для обнулення постачання в цій клітці по циклу слід передати 2 одиниці ресурсу. Постачання, передане по циклу, визначається як мінімум серед постачань у клітках циклу зі знаком «-». Після цього клітка В3 вважається заповненою, а клітка В2 - вільною. Одержали новий базисний розподіл постачань:

Зміна витрат на новому розподілі складе Δ W⁽¹⁾ = -7 ´ 2 = -14. Загальний обсяг витрат при новому базисному розподілі складе: W⁽¹⁾ = W⁽⁰⁾ + Δ W⁽¹⁾ = 107-14 = 93.

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

B1: b_B1 = 12-4+7-7+10-11 = 7 пo циклу B1à A1à A2à C2à C3à В3à В1.

Оскільки є вільні клітки з від’ємною оцінкою (b₃ = - 4), то оптимальне рішення ще не знайдене. Для одержання чергового базисного розподілу використовуємо цикл перерахунку по A3. При цьому k = min{2, 2} = 2; Δ W⁽²⁾ = b₃ x k⁽²⁾= - 4 x 2 = - 8; W⁽²⁾= W⁽¹⁾ + Δ W⁽²⁾ = 93 - 8 = 85.

Дослідження отриманого базисного розподілу на оптимальність покаже, що в ньому відсутні клітки з від’мною оцінкою. Таким чином, даний розподіл постачань буде оптимальним. У розглянутій задачі отримане оптимальне рішення збігається з первинним базисним рішенням, отриманим методом найменшого елемента.

Як видно, при виконанні кожного чергового циклу перерахунку вільна клітка стає заповненою, а одна з заповнених – вільною.

Загальний алгоритм рішення транспортної задачі може бути сформульований у такому вигляді:

1. Для даного базисного розподілу постачань підбираються потенціали рядків і стовпців таблиці постачань так, щоб коефіцієнти витрат заповнених кліток стали рівні 0. Складається матриця оцінок.

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

3. Для обраної вільної клітки будується зазначений цикл перерахунку. Постачання k, передане по циклу, визначається як мінімум серед постачань у клітках зі знаком «-». Знайдене постачання пересувається по циклу. При цьому постачання в клітках зі знаком «+» збільшується на k, а в клітках зі знаком «-» зменшується на k. Клітка, постачання в який при цьому стане рівним 0, буде вважатися вільною, інші клітки циклу – заповненими. Таким чином, отримано базисний розподіл постачань.

Даний алгоритм рішення відповідає закритій транспортній задачі - коли сумарний попит споживачів збігається із сумарною потужністю постачальників.

Відкрита транспортна задача припускає, що сумарна потужність постачальників менше сумарного попиту споживачів, і зводиться до рішення закритої транспортний шляхом уведення фіктивного постачальника.