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

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

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

min3

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

min6

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

min11

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

min15

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

min16

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар