Метод найменшої вартості

Кількість ітерацій при рішенні ТЗ можна скоротити, якщо первісний опорний план будувати по більше розробленому методу - методу найменшої вартості.

Суть методу — на І етапі здійснюється максимально можлива поставка в клітку з найменшим тарифом, а остача, якщо вона є, розподіляється по рядку або стовпцю в порожню клітку з найменшим тарифом.

Особливість — метод враховує значення тарифів, а це означає, що побудований опорний план буде більш близький до оптимального, чим план, сформований по методу північно-західного кута.

Приклад:

Побудувати первісний опорний план для ТЗ по методу північно-західного кута й методом найменшої вартості.

	В1	В2	В3	В4	Зап.
А1	^3	^5	^7	^11	100
А2	^1	^4	^6	^3
А3	^5	^8	^12	^7
Потр.

Побудуємо первинний опорний план методом найменшої вартості:

	В1	В2	В3	В4	Зап.
А1	^3	^5	^7	^11	100
А2	^1	^4	^6	^3
А3	^5	^8	^12	^7
Потр.

Вирішити методом потенціалів, визначаючи при цьому первісний оптимальний план методом північно-західного кута

	V1=3	V2=6	V3=10	V4=5	Зап.
U1=0	^3	^5	^+7	^11	100
U2=2	^1	^4	^6	^3	Далее проверяют на потенциальность клеток небазисного набора 130
U3= –2	^5	^8	^-12	^7
Потр.

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

	V1=3	V2=6	V3=7	V4=5	Зап.
U1=0	^3	^5	^7	^11	100
U2=2	^1	^4	^6	^3
U3= –2	^5	^8	^12	^7
Потр.

	V1=3	V2=5	V3=7	V4=4	Зап.
U1=0	^3	^+5	^7	^11	100
U2=2	^1	^4	^6	^3
U3= –3	^5	^8	^12	^7
Потр.

	V1=2	V2=5	V3=7	V4=4	Зап.
U1=0	^3	^5	^7	^11	100
U2=2	^1	^4	^6	^3
U3= –3	^5	^8	^12	^7
Потр.

Отриманий план потенційний і оптимальний, тому що в ньому відсутні непотенційні клітки.

Дата добавления: 2014-12-07