3.2.2 Метод мінімальної питомої вартості

 

Алгоритм методу мінімальної питомої вартості:

1. У транспортній матриці вибирається клітинка з мінімальним значенням с_іj. Якщо є кілька таких  клітинок, то вибирається будь-яка з них.

2. В обрану клітинку в якості базисної змінної заноситься найменша із двох величин A_і або B_j, тобто  При цьому виконується баланс потужності по рядку і або стовпцю j, у які входить змінна x_іj.

3. В інші клітинки рядка і або стовпця j, для яких виконаний баланс потужності, заносяться нулі, що відповідають вільним змінним. Більша із двох величин A_і й B_j умовно заміняється різницею цих двох величин.

4. З незаповнених клітинок транспортної матриці, що залишилися, знову вибирається клітинка з мінімальним значенням с_іj.

Далі пункти 2 і 3 повторюються до повного заповнення всіх клітинок транспортної матриці.

Варто нагадати, що загальна кількість змінних становить nхm. Кількість відмінних від нуля базисних змінних становить (n+m-1). Кількість рівних нулю вільних змінних становить (nm-(n+ m-1)).