анспортних потоків складається з двох етапів. На першому етапі ми вибираємо деякий необов'язковий оптимальний план перевезень. На другому етапі ми послідовно крок за кроком покращуємо цей план, для досягнення мінімум витрат. p align="justify"> Крок 1:
Для того щоб система запрацювала, заповнені клітини плану повинні утворити В«драбинку з не розпадаються сходинкамиВ».
Таблиця 2.1.1
j 12345 i 3623263420 1 32 13 321521117V2 17 22 421 1335 3813V3 19 1021 1028 92428V4 31 251922 1729 1417V5 40 18173341 2025 20VVVVVV
Направляємо в першу клітку максимальний потік вантажів (, закриваємо рядок 1. У клітку (направляємо 4 і тим самим закриваємо стовпець. Аналогічно проводимо такі ж операції з іншими стоками і стовпцями і закриваємо їх. Таким чином, сума витрат дорівнює: В
Відповідь: при використанні діагонального (північно-західного кута) методу, сума витрат склала 3339 ткм.
Таблиця 2.1.2
j 12345 i 2842432720 1 41 13 2815 1321 117V2 29 2221 2935 0 3813V3 33 102128 332428V4 27 251922 1029 1717V5 30 18173341 1025 20VVVVVV
Аналогічно проводимо ті ж операції, що і в першому прикладі. В« 0В» - дефективна (порожній) перевезення.
Таким чином, сума витрат дорівнює:
В
Відповідь: при використанні діагонального (північно-західного кута) методу, сума витрат склала ткм.
2.2 Метод мінімуму елемента по рядку
При використанні даного методу явище вираженості не спостерігається. Зміст даного методу полягає в напрямку максимального потоку в мінімальний елемент рядка. p> Вибираємо в першому рядку мінімальний елемент (і направляємо максимальний потік 20, закриваємо стовпець 5. Так як рядок ще не закрита, то в клітку з мінімальним елементом 11, направляємо максимальний потік (. Закриваємо першу сходинку і переходимо до другої рядку. Ан...
