Цикл перерахунку.

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

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

Цикл перерахунку.

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

Для цього спочатку потрібно виразити цільову функцію W (3.1) задачі через неосновні (вільні) змінні. Мінімум цільової функції, тобто рішення транспортної задачі, отримується тоді, коли всі коефіцієнти при вільних (неосновних) змінних у виразі для цільової функції W (3.1) через вільні перемінні невід’ємні.

У транспортній задачі змінна х_ij ототожнюється з вмістом відповідної клітки (i, j) таблиці постачань. Позначимо b_ij коефіцієнт біля вільної змінної х_ij у виразі для лінійної функції цілі W (3.1) через вільні змінні; b_ij називається оцінкою вільної клітки (i, j).

При даному базисному розподілі постачань клітка (i, j) - вільна (змінна х_ij - вільна), b_ij - оцінка клітки (i, j) чи коефіцієнт у виразі лінійної функції W (3.1) через вільні змінні:

де трикрапкою позначені доданки, що відповідають вільним змінним, відмінним від х_ij, W₀ – сумарні витрати на даний розподіл постачань.

Тоді з (3.4) випливає, що оцінка b_ij вільної (i, j) клітки дорівнює зміні сумарних витрат Δ W на постачання при переведенні в клітку (i, j) одиничного постачання (збільшення змінної х_ij від 0 до 1), тобто: b_ij = Δ W = W_п – W_н, де W_н - первинні витрати на постачання;
W_п - витрати на постачання після перерозподілу. Передбачається, що у всіх вільних клітках відмінних від клітки (i, j), постачання залишиться нульовим. Очевидно, що Δ W > 0 якщо
b_ij > 0; Δ W < 0 якщо b_ij < 0. Останнє непряме визначення оцінки вільної клітки називають економічним змістом оцінки вільної клітки.

Знайдемо оцінку вільної клітки А3. Для цього дамо в клітку А3 одиничне постачання. При цьому буде потрібно змінити постачання в заповнених клітках так, щоб зберігся баланс по рядках і стовпцям (передбачається, що у всіх вільних клітках відмінних від клітки А3, постачання залишиться нульовим). Так, щоб 3-й район як і раніше одержав 5 тис. номерів, постачання в клітці В3 варто зменшити на 1тис. Для того, щоб АТС В як і раніше поставила 3тис. номерів, постачання в клітці В2 збільшуємо на 1тис. 2-му району необхідно тільки 4тис. номерів, тому постачання в клітці А2 варто зменшити на 1тис. З'єднавши один по одному зазначені клітки A3 à B3 à B2 à A2 à A3 одержимо замкнутий контур (цикл).

Циклом перерахунку базисної транспортної таблиці називається група кліток цієї таблиці, з'єднаних замкнутою ламаною лінією, що проходить через клітки зі змінюваним постачанням і в кожній клітці робить поворот на + 90⁰. Одна з вершин лежить у вільній клітці, інші - у заповнених. Кожен цикл має парне число вершин.

Позначимо знаком «+» ті вершини, у яких постачання (перевезення) збільшуються, а знаком «-» ті, у яких вони зменшуються.

Позначеним циклом перерахунку називається цикл, у вершинах якого розставлені знаки «+» і «-», так, що у вільній клітці стоїть знак «+», а сусідні вершини мають протилежні знаки.

При переміщенні ресурсу по циклу перерахунку знаки у вершинах чергуються тому, що не повинна порушуватися умова балансу постачань і по рядках і по стовпцях.

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

Так, якщо після перерозподілу маємо b_ij=Δ W з від’ємною оцінкою, то вихідний базовий розподіл – не оптимальний і його можна поліпшити.

Якщо ціна циклу додатня величина, то поліпшити рішення за рахунок цього циклу перерахунку не вдасться. З іншого боку вартість перевезень зросте, якщо інакше перерозподілити ресурси по цьому циклу.

Якщо ціна дорівнює 0, то вартість постачань по цьому циклу не змінюється при переміщенні.

В отриманій базовій транспортній таблиці необхідно побудувати зазначені цикли перерахунку для усіх вільних кліток. У вихідній вільній клітці розміщаємо одну з вершин і приписуємо «+». Всі інші вершини перерахунку повинні спиратися на зайняті клітки.

Для поліпшення рішення в розглянутій задачі можна виконати єдиний цикл перерахунку з від’ємною ціною b_С2: