в таблиці вони розташовуються в нижньому лівому кутку комірки).
Оцінка незадействованного маршруту=тариф маршруту - (потенціал постачальника + потенціал споживача).
A 1 B 2: 12=8 - (8 + 0)=0 1 B 3: 13=1 - (8 + 1)=- 8 2 B 3: 23=9 - (5 + 1)=3 2 B 4: 24=8 - (5 + (- 6))=9 3 B 1: 31=9 - (2 + (- 1))=8 3 B 4: 34=6 - ( 2 + (- 6))=10
1 незадіяний маршрут мають негативну оцінку.
Введення даного маршруту в схему доставки продукції, дозволить отримати нове рішення, як мінімум, не гірше наявного.
Будемо використовувати новий маршрут доставки продукції від постачальника A 1 до споживача B 3. (комірка A 1 B 3)
Побудуємо цикл для нового маршруту. ( lt; javascript: Comments (125) gt;)
Нехай осередок A 1 B 3, для якої ми будували цикл, має порядковий номер один.
Серед осередків циклу, номери яких парні, знайдемо осередок володіє найменшим значенням.
min={60, 90, 150}=60.
Від осередків циклу з парними номерами віднімає 60. До осередкам з непарними номерами додаємо 60.
Досить поглянути на таблицю і Ви побачите, що баланс не порушиться. Усі постачальники витратять всі свої запаси, а всі споживачі отримають необхідну їм кількість продукції. А ось загальні витрати на доставку всієї продукції зміняться на величину
1 * 60 - 7 * 60 + 4 * 60 - 5 * 60 + 2 * 60 - 3 * 60=(1 - 7 + 4 - 5 + 2 - 3) * 60=- 8 * 60=13 * 60.
Вираз стоїть у дужках одно оцінці нового маршруту !!
Тому нова вартість доставки обчислюється саме так:
S=2040 + 13 * 60=2040 - 8 * 60=1560 ден. од.
Один маршрут з побудованого циклу, за яким нічого не доставляється, ми повинні виключити.
Це маршрут від постачальника A 1 до споживача B 1 (див. таблицю вище). Тепер даний маршрут незадіяний.
Крок 5
Отримане рішення є оптимальним?
Кожному постачальнику A i ставимо у відповідність деяке число - ui, зване потенціалом постачальника.
Кожному споживачеві B j ставимо у відповідність деяке число - vj, зване потенціалом споживача.
Знайдемо потенціали постачальників і покупців. (повірте, це дуже просто)
Для задіяного маршруту, сума потенціалу постачальника і споживача дорівнює тарифом задіяного маршруту.
Приймемо v 3=0.
A 1 B 3: v 3 + u 1=1 u 1=1 - 0=1 1 B 4: v 4 + u 1=2, v 4=2 - 1=1 3 B 3: v 3 + u 3=3, u 3=3 - 0=3 3 B 2: v 2 + u 3=2, v 2=2 - 3=- 2 січня B 2: v 2 + u 2= 5, u 2=5 - (- 1)=6
A 2 B 1: v 1 + u 2=4, v 1=4 - 6=- 2
- Знайдемо оцінки незадіяних маршрутів (в таблиці вони розташовуються в нижньому лівому кутку комірки).
Оцінка незадействованного маршруту=тариф маршруту - (потенціал постачальника + потенціал споживача).
A 1 B 1: 11=7 - (1 + (- 2))=8 1 B 2: 12=8 - (1 + (- 1))=8 2 B 3: 23 =9 - (6 + 0)=3 2 B 4: 24=8 - (6 + 1)=1 3 B 1: 31=9 - (3 + (- 2))=8
A 3 B 4: 34=6 - (3 + 1)=2
Оцінки всіх незадіяних маршрутів невід'ємні. Отже, зменшити загальну вартість доставки ми не зможемо.
Відповідь:
X опт=0060140 15030000100900
S=1 560 ден. од.
