ся. Усі постачальники витратять всі свої запаси, а всі споживачі отримають необхідну їм кількість продукції. А ось загальні витрати на доставку всієї продукції зміняться на величину
4 * 50 - 9 * 50 + 3 * 50 - 6 * 50 + 2 * 50 - 7 * 50=(4 - 9 + 3 - 6 + 2 - 7) * 50=- 13 * 50=21 * 50.
Вираз стоїть у дужках одно оцінці нового маршруту !!
Тому нова вартість доставки обчислюється саме так:
S=3090 + 21 * 50=3090 - 13 * 50=2440 ден. од.
Один маршрут з побудованого циклу, за яким нічого не доставляється, ми повинні виключити.
Це маршрут від постачальника A 2 до споживача B 3 (див. таблицю вище). Тепер даний маршрут незадіяний.
Крок 3
Отримане рішення є оптимальним?
Кожному постачальнику A i ставимо у відповідність деяке число - ui, зване потенціалом постачальника.
Кожному споживачеві B j ставимо у відповідність деяке число - vj, зване потенціалом споживача.
Знайдемо потенціали постачальників і покупців. (повірте, це дуже просто)
Для задіяного маршруту, сума потенціалу постачальника і споживача дорівнює тарифом задіяного маршруту.
Приймемо v 4=0.
A 1 B 4: v 4 + u 1=2, u 1=2 - 0=2 3 B 4: v 4 + u 3=6, u 3=6 - 0=6 1 B 1: v 1 + u 1=7, v 1=7 - 2=5 2 B 1: v 1 + u 2=4, u 2=4 - 5=- 1 2 B 2: v 2 + u 2= 5, v 2=5 - (- 1)=6
A 3 B 3: v 3 + u 3=3, v 3=3 - 6=- 3
- Знайдемо оцінки незадіяних маршрутів (в таблиці вони розташовуються в нижньому лівому кутку комірки).
Оцінка незадействованного маршруту=тариф маршруту - (потенціал постачальника + потенціал споживача).
A 1 B 2: 12=8 - (2 + 6)=0 1 B 3: 13=1 - (2 + (- 3))=2 2 B 3: 23=9 -(- 1 + (- 3))=13 2 B 4: 24=8 - (- 1 + 0)=9 3 B 1: 31=9 - (6 + 5)=- 2 3 B 2: 32=2- (6 + 6)=- 10
2 незадіяних маршрутів мають негативну оцінку.
Введення будь-якого з них в схему доставки продукції дозволить отримати нове рішення, як мінімум, не гірше наявного.
Будемо використовувати новий маршрут доставки продукції від постачальника A 3 до споживача B 2. (комірка A 3 B 2)
Побудуємо цикл для нового маршруту.
Нехай осередок A 3 B 2, для якої ми будували цикл, має порядковий номер один.
Серед осередків циклу, номери яких парні, знайдемо осередок володіє найменшим значенням.
min={40, 100, 130}=40.
Від осередків циклу з парними номерами віднімає 40. До осередкам з непарними номерами додаємо 40.
Досить поглянути на таблицю і Ви побачите, що баланс не порушиться. Усі постачальники витратять всі свої запаси, а всі споживачі отримають необхідну їм кількість продукції. А ось загальні витрати на доставку всієї продукції зміняться на величину
2 * 40 - 6 * 40 + 2 * 40 - 7 * 40 + 4 * 40 - 5 * 40=(2 - 6 + 2 - 7 + 4 - 5) * 40=- 10 * 40=32 * 40.
Вираз стоїть у дужках одно оцінці нового маршруту !!
Тому нова вартість доставки обчислюється саме так:
S=2440 + 32 * 40=2440 - 10 * 40=2 040 ден. од.
Один маршрут з побудованого циклу, за яким нічого не доставляється, ми повинні виключити.
Це маршрут від постачальника A 3 до споживача B 4 (див. таблицю вище). Тепер даний маршрут незадіяний.
Крок 4
Отримане рішення є оптимальним?
Кожному постачальнику A i ставимо у відповідність деяке число - ui, зване потенціалом постачальника.
Кожному споживачеві B j ставимо у відповідність деяке число - vj, зване потенціалом споживача.
Знайдемо потенціали постачальників і покупців (повірте, це дуже просто)
Для задіяного маршруту, сума потенціалу постачальника і споживача дорівнює тарифом задіяного маршруту.
Приймемо v 2=0.
A 2 B 2: v 2 + u 2=5, u 2=5 - 0=5 3 B 2: v 2 + u 3=2, u 3=2 - 0=2 3 B 3: v 3 + u 3=3, v 3=3 - 2=1 2 B 1: v 1 + u 2=4, v 1=4 - 5=- 1 1 B 1: v 1 + u 1= 7, u 1=7 - (- 1)=8
A 1 B 4: v 4 + u 1=2, v 4=2 - 8=- 6
- Знайдемо оцінки незадіяних маршрутів (...
