Метод мінімального елемента

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

Складемо розв'язок наступної задачі з допомогою цього методу. Приклад: На три бази  поступив товар в кількості 160; 140 і 170 одиниць відповідно. Цей груз потрібно перевезти в чотири пункти призначення , потреби яких становлять 120; 50; 190; 110. Тарифи перевезення записані в таблиці:

Найменшу вартість має перевезення, яке здійснюються з  в , ціна перевезення одиниці продукції якого становить 1-ну умовну одиницю. Заповнимо дану клітинку. Оскільки відправник  має в запасі 160 одиниць продукції, а пункт призначення  потребує — 190, то від першого відправника третьому споживачеві можна перевезти лише 160 одиниць продукції. І таким чином запаси першого пункту відправлення повністю вичерпані (перший рядок викреслюємо з розгляду).

З клітинок, що залишилися вибираємо ту, в якій знаходиться маршрут з мінімальною вартістю перевезення. Таких клітинок у нас дві:  і . Виходячи з того, що клітинка  знаходиться в першому рядку, а його ми на попередньому кроці викреслили з розгляду, то будемо заповнювати клітинку . Обсяг запасів пункту відправлення рівні , а потреби , тому, за рахунок запасів третього відправника, потреби другого споживача задовільняються в повному обсязі (стовбець під номером два викреслюється з розгяду) і в клітинку  записуємо число 50. В результаті отримуємо наступну таблицю:

Знову вибираємо клітинку (серед тих що залишилися незаповненими) з найменшою вартістю перевезень. Такою клітинкою буде . Виходячи з того, що запаси третього пункту відправлення становлять , а потреби третього пункту призначення рівні , то ставимо в клітинку  значення 30. І таким чином потреби 3-го пункту призначення задоволені, а стовбець в якому знаходиться даний пункт викреслюємо з розгляду.

Продовжуючи даний процес до тих пір, поки усі запаси не будуть вичерпані, а потреби — задоволеними, ми отримаємо таблицю, у заповнених клітинках якої містяться числа, які означають можливий план перевезення продукції із загальною вартістю F = 120 * 4 + 50 * 2 + 160 * 1 + 3 * 30 + 20 * 8 + 90 * 6 = 1530