Введена Вами таблиця дає нам наступну інформацію:
Запаси однотипної продукції, яка знаходиться у постачальників A 1, A 2, A 3.
Потреба в однотипної продукції споживачів B 1, B 2, B 3, B 4.
Вартість доставки одиниці продукції від кожного постачальника до кожного споживача (тарифи маршрутів).
Потрібно скласти план перевезень, при якому загальна вартість перевезень мінімальна.
Рішення:
Знайдемо початкове рішення методом північно-західного кута.
Сумарні запаси продукції у постачальників повинні дорівнювати сумарній потреби споживачів.
Запаси постачальників:
+ 180 + 190=570 одиниць продукції.
Потреба споживачів:
+ 130 + 150 + 140=570 одиниць продукції.
Сумарні запаси продукції у постачальників рівні сумарної потреби споживачів.
) Згідно з умовою задачі складемо таблицю (тарифи маршрутів розташовуються в нижньому правому куті комірки).
Починаємо заповнювати таблицю від лівого верхнього кута і поступово рухаємося до правого нижнього.
Від північного заходу на південний схід.
Від постачальника A 1 до споживача B 1 будемо доставляти
={200, 150}=150 одиниць продукції.
2)
Від постачальника A 1 до споживача B 2 будемо доставляти
={50, 130}=50 одиниць продукції.
3)
Від постачальника A 2 до споживача B 2 будемо доставляти
={180, 80}=80 одиниць продукції.
4)
Від постачальника A 2 до споживача B 3 будемо доставляти
={100, 150}=100 одиниць продукції.
5)
Від постачальника A 3 до споживача B 3 будемо доставляти
={190, 50}=50 одиниць продукції.
6)
Від постачальника A 3 до споживача B 4 будемо доставляти 140 одиниць продукції.
7)
Ми витратили всі запаси постачальників і задовольнили всі потреби споживачів.
Ми знайшли початкове рішення.
Вартість доставки продукції, для початкового рішення, не складно порахувати.
S=150 * 7 + 50 * 8 + 80 * 5 + 100 * 9 + 50 * 3 + 140 * 6=3740 ден. од.
Отримане початкове рішення є оптимальним?
Для того, щоб мати можливість відповісти на це питання, кількість задіяних маршрутів повинно дорівнювати
+ 4 - 1=6,
де
- кількість рядків у таблиці.
- кількість стовпців в таблиці.
Кількість задіяних маршрутів не може вийти більше 6, менше - можливо.
Порахуйте. Кількість задіяних маршрутів одно 6, що й потрібно.
В іншому випадку, ми не зможемо знайти потенціали постачальників і споживачів.
Подальші наші дії будуть складатися з однотипних кроків, кожен з яких полягає в наступному:
Знаходимо потенціали постачальників і споживачів.
Знаючи потенціали, знаходимо оцінки незадіяних маршрутів.
Якщо оцінки всіх незадіяних маршрутів невід'ємні, то зменшити загальну вартість доставки можна. Завдання вирішена.
Якщо хоча б один незадіяний маршрут має негативну оцінку, тоді ми можемо знайти нове рішення, як мінімум, не гірше наявного.
Вводимо незадіяний маршрут, з негативною оцінкою, в схему доставки продукції. Один, раніше задіяний маршрут, виключаємо.
Обчислюємо загальну вартість доставки всієї продукції для нового рішення.
Крок 1
Кожному постачальнику A i ставимо у відповідність деяке число - ui, зване потенціалом постачальника.
Кожному споживачеві B j ставимо у відповідність деяке число - vj, зване потенціалом споживача.
Знайдемо потенціали постачальників і покупців. (повірте, це дуже просто)
Для задіяного маршруту, сума потенціалу постачальника і споживача дорівнює тарифом задіяног...
