Дължината на най-краткия път е .... Преминаването от началния връх до края на избраните краищата се получи най-краткия път.
3. Задачата на определяне на максималния поток
Ние считаме, че една мрежа с един вход възел (източник) и един изход възел (изтичане). Определяне на максималната стойност на потока (броя на машините, съобщения, течност и т.н.), което може да влезе в електроенергийната система и извън нея в даден период от време. Предполага се, че отпадъчните води от възела равна на потока, протичащ през възела.
Скорост (или мощност) на дъгата - горната граница на потока в дъгата. Например, магистрали ограничават броя на превозните средства в транспортната система на тръбопроводи стойност ограничава размера на петрол в своята дистрибуторска система.
Мощност на потока може да зависи от нейната посока.
Този символ показва, че потока мощност от възел 1 до възел 2 е равно на 6 и потока мощност от възел 2 към възел 1 е 0, т.е. Тази "еднопосочна улица".
Това означава, че потокът на енергия във всяка посока е равно на 2.
Предполагаме желаната стойност на максималния поток равен на нула.
Етап 1. Виж някакъв начин от източника на канала, която е оформена от дъги, всяка от които има нула без посока мощност поток. Ако такава пътека не е налице, след оптималното решение е намерена.
Стъпка 2. Намерете най-малкото мощност стойност Pf дъгата в избрано стъпка път 1. За да се увеличи потокът чрез мрежата от стойността Pf.
Стъпка 3: По пътя от етап 1 за намаляване на потока мощност на всички дъги Pf в посоката на потока и повишаване на мощността Pf потоци на всички дъги в обратна посока. Преминете към стъпка 1.
Пример. Системата на пътища "Север-Юг", минаваща през регион Псков може да осигури ленти, показани на схема (хил. Коли на час).
Определя максималния поток през системата (хил. Коли на час).
Желаният стойността на максималния поток се определя като равна на нула.
Повторение 1. Изберете пътя
Pf = мин = .... Следователно силата потоци на ......... път в посока на потока (а именно, ... и ...) намали количеството Pf = ... и силата потоци в обратна посока по пътя .......... (... и ...) се увеличават с Pf = .... Общият ще тече
Повторение 2. Изберете пътя
Pf = мин = .... Всички потоци в пътя в ......... обща посока на потока (... и ...) за намаляване на PF = ..., и всички потоци по този начин в обратна посока (... и ...) се увеличава с Pf = .... Общият поток се увеличава с Pf = ... (............).
Повторение 3. Изберете начин
Pf = мин = .... Всички потоци по пътя .......... в общата посока на потока (.............) за намаляване на PF = ..., и всички потоци по този начин в обратна посока (............) се увеличава от Pf = .... Общият поток се увеличава с Pf = ... (................).
Повторение 4. Изберете начина, по който
Pf = мин = .... Всички теми, в начина, по ................ в общата посока на потока (............... ..) за намаляване Pf = ..., и всички потоци по този начин в обратна посока (............... ..) за увеличаване Pf = .... Общо увеличава потока от Pf = ... (............ ..).
Повторение 5. Изберете начина, по който
Pf = мин = .... Всички теми, в начина, по ................... в общата посока на потока (.................. ..) за намаляване Pf = ..., и всички потоци по този начин в обратна посока (.................. ..), за да се увеличи Pf = .... Общият поток се увеличава с Pf = ... (.............).
Дълго съществува пътеки от възел 1 до 6 възел с капацитет над нула целия път. Вследствие на това .... хил. - е максималният поток през мрежата.
Определя размера и посоката на потока на всяка дъга. Посоката на потока съответства на избраните пътеки. Потокът минава през дъга със стойност, равна на разликата в мощността между началните и крайните потоци:
дъга 1-2: първоначална сила е ... (в оригиналната графиката), окончателен - ... (последната колона), така че посока от възел 1 до възел 2 има капацитет на потока
Като резултат, ние получаваме графика, която показва посоката и силата поток на всяка дъга:
Свързани статии