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

Правила знаходження початкового опорного плану транспортної задачі методом найменшої вартості відрізняються від правил знаходження такого плану діагональним методом тільки послідовністю вибору клітинки, яку потрібно заповнювати. Згідно з методом найменшої вартості першою вибирається клітинка з найменшою вартістю перевезення одиниці вантажу від постачальника до споживача. Якщо таких клітинок декілька, то вибираємо ту, для якої кількість вантажу, що можна перевезти, найбільша.

Після побудови початкового опорного плану кожним з методів у таблиці ма’ бути заповнено (т+п-1) клітинок, тому що ранг матриці системи обмежень транспортної задачі рівний r=m+n-l, де т- кількість постачальників, п - кількість споживачів. Заповнені клітинки називаються базисними, а незаповнені - вільними. Якщо кількість базисних клітинок рівна (т+п-1), то такий план називається невиродженим. Якщо кількість заповнених клітинок менша (т+п-1), то план називається виродженим. Тоді необхідно заповнити відповідну кількість порожніх (небазисних) клітинок, записуючи в них «нульове перевезення», і ці клітинки вважати базисними. Коли ж кількість заповнених клітинок перевищує (т+п-1), то початковий опорний план побудовано неправильно і він не є опорним.