Реферат Побудова оптимального плану перевезень вантажу з мінімальною вартістю

му куті клітин записана вартість перевезення.

Заповнювати таблицю первісного опорного плану починаємо з клітки а 1 b 1 - це північно-західний кут.

Закриваємо потреби b 1 поставкою з а 1 і цей стовпець виключаємо з подальшого розгляду. Залишок вантажу з а 1 відправляємо споживачеві b 2 < span align = "justify"> і рядок а 1 виключаємо з подальшого розгляду. Потім весь вантаж з а 2 відправляємо в b 2 , виключаючи рядок а 2 і частиною вантажу з а 3 закриваємо потребу b 2 , виключаючи стовпець b 2 . Далі закриваємо потребу b 3 поставкою з а 3 < span align = "justify">, а залишок вантажу з а 3 відправляємо споживачеві b 4 . Вантаж з а 4 відправляємо споживачеві b 4 . Опорний план складений.

Вартість перевезень за цим планом:

Z 1 = 95.17 + 10? 12 + 70? 11 + 80? 19 + 135? 22 + 25? 27 + 85? 7 = 8265 Д.Є.

Число заповнених клітин має бути m + n -1 = 4 + 4 - 1 = 7, що так і є, тобто план не виродилися.

Перевіряємо оптимальність плану методом потенціалів, присвоївши першому рядку нульовий потенціал U 1 = 0. Потенціали інших рядків і стовпців визначаємо за формулами:

U i = C ij < span align = "justify"> - V j ; V j = C ij - U i ;

Назад | сторінка 2 з 21 | Наступна сторінка