о маршруту.
Приймемо v 3=0.
A 2 B 3: v 3 + u 2=9, u 2=9 - 0=9 3 B 3: v 3 + u 3=3, u 3=3 - 0=3 3 B 4: v 4 + u 3=6, v 4=6 - 3=3 2 B 2: v 2 + u 2=5, v 2=5 - 9=- 4 1 B 2: v 2 + u 1= 8, u 1=8 - (- 4)=12 1 B 1: v 1 + u 1=7, v 1=7 - 12=- 5
- Знайдемо оцінки незадіяних маршрутів (в таблиці вони розташовуються в нижньому лівому кутку комірки).
Оцінка незадействованного маршруту=тариф маршруту - (потенціал постачальника + потенціал споживача).
A 1 B 3: 13=1 - (12 + 0)=- 11 січня B 4: 14=2 - (12 + 3)=- 13 2 B 1: 21=4 - ( 9 + (- 5))=0 2 B 4: 24=8 - (9 + 3)=- 4 3 B 1: 31=9 - (3 + (- 5))=11 3 B 2: 32=2- (3 + (- 4))=3
незадіяних маршрути мають негативну оцінку.
Введення будь-якого з них в схему доставки продукції дозволить отримати нове рішення, як мінімум, не гірше наявного.
Будемо використовувати новий маршрут доставки продукції від постачальника A 1 до споживача B 4. (комірка A 1 B 4)
Побудуємо цикл для нового маршруту.
Нехай осередок A 1 B 4, для якої ми будували цикл, має порядковий номер один.
Серед осередків циклу, номери яких парні, знайдемо осередок володіє найменшим значенням.
min={50, 100, 140}=50.
Від осередків циклу з парними номерами віднімає 50. До осередкам з непарними номерами додаємо 50.
Досить поглянути на таблицю і Ви побачите, що баланс не порушиться. Усі постачальники витратять всі свої запаси, а всі споживачі отримають необхідну їм кількість продукції. А ось загальні витрати на доставку всієї продукції зміняться на величину
2 * 50 - 8 * 50 + 5 * 50 - 9 * 50 + 3 * 50 - 6 * 50=(2 - 8 + 5 - 9 + 3 - 6) * 50=- 13 * 50=14 * 50.
Вираз стоїть у дужках одно оцінці нового маршруту !!
Тому нова вартість доставки обчислюється саме так:
S=3740 + 14 * 50=3740 - 13 * 50=3 090 ден. од.
Один маршрут з побудованого циклу, за яким нічого не доставляється, ми повинні виключити.
Це маршрут від постачальника A 1 до споживача B 2 (див. таблицю вище). Тепер даний маршрут незадіяний.
Крок 2
Отримане рішення є оптимальним?
Кожному постачальнику 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 3 B 3: v 3 + u 3=3, v 3=3 - 6=- 3 2 B 3: v 3 + u 2= 9, u 2=9 - (- 3)=12
A 2 B 2: v 2 + u 2=5, v 2=5 - 12=- 7
- Знайдемо оцінки незадіяних маршрутів (в таблиці вони розташовуються в нижньому лівому кутку комірки).
Оцінка незадействованного маршруту=тариф маршруту - (потенціал постачальника + потенціал споживача).
A 1 B 2: 12=8 - (2 + (- 7))=13 1 B 3: 13=1 - (2 + (- 3))=2 2 B 1: 21 =4 - (12 + 5)=- 13 2 B 4: 24=8 - (12 + 0)=- 4 3 B 1: 31=9 - (6 + 5)=- 2 3 B 2: 32=2- (6 + (- 7))=3
незадіяних маршрути мають негативну оцінку.
Введення будь-якого з них в схему доставки продукції дозволить отримати нове рішення, як мінімум, не гірше наявного.
Будемо використовувати новий маршрут доставки продукції від постачальника A2 до споживача B1. (комірка A2B1) ( lt; javascript: Comments (12343) gt;)
Побудуємо цикл для нового маршруту. ( lt; javascript: Comments (123) gt;)
Нехай осередок A 2 B 1, для якої ми будували цикл, має порядковий номер один.
Серед осередків циклу, номери яких парні, знайдемо осередок володіє найменшим значенням.
min={50, 90, 150}=50.
Від осередків циклу з парними номерами віднімає 50. До осередкам з непарними номерами додаємо 50.
Досить поглянути на таблицю і Ви побачите, що баланс не порушить...
