Проблем протока са минималном ценом

Проблем протока са минималном ценом је оптимизациони проблем и проблем одлучивања како би се нашло најефтинији могући начин слања протока кроз транспортну мрежу. Решавање овог проблема је корисно за животне ситуације које садрже мреже са ценама (нпр. телекомуникационе мреже), као и за друге ситуације где аналогија није толико очигледна, на пример, где наћи стовариште.

Дефиниција

Транспортна мрежа је оријентисани граф $G=(V,E)$ са изворном тачком $s\in V$ и завршно тачком $t\in V$, где свака ивица $(u,v)\in E$ има попусност $c(u,v)>0$, проток $f(u,v)\geq 0$ и цену $a(u,v)$ (већина алгоритама минималне цене протока подржавају гране са негативним ценама). Цена слања оваквог протока је $f(u,v)\cdot a(u,v)$. Потребно је послати $d$ протока од $s$ до $t$.

Дефиниција проблема је минимизирати укупну цену протока:

$\sum _{(u,v)\in E}a(u,v)\cdot f(u,v)$

са овим ограничењима

Ограничење попусности:	$\,f(u,v)\leq c(u,v)$
Коса симетрија:	$\,f(u,v)=-f(v,u)$
Чување тока:	$\,\sum _{w\in V}f(u,w)=0{\text{ for all }}u\neq s,t$
Потребан проток:	$\,\sum _{w\in V}f(s,w)=d{\text{ and }}\sum _{w\in V}f(w,t)=d$

Релације са дргим проблемима

Једна варијација овог проблема је да се нађе проток који је максималан, али има најмању цену међу максималним. Овај проблем би се могао назвати поблем максималног потока минималне цене. Ово је корисно за налажење минималне цене максималног упаривања.

Са неким решењима, налажење минималне цене максималног протока је дирекно. Ако није, може се урадити бинарна претрага по д.

Повезан проблем је проблем минимална цене циркулације, који може да се користи за решавање минималне цене протока. Ово се ради тако што се доња граница на свим гранама стави на нулу, а онда се додаје нова грана од чвора $t$ до чвора $s$, са пропушношћу $c(t,s)=d$, Присиљавајући укупан проток од $s$ до $t$ да такође буде $d$.

Проблем може бити специјализован у друга два проблема:

• Ако је ограничење пропустности избачено, проблем се своди на проблем најкраће путање.
• Ако се све цене поставе на нуле, проблем се своди на проблем максималног протока.

Решења

Проблем минималне цене протока може бити решен коришћењем линеарног програмирања, пошто можемо да оптимизујемо линеарну функцију и сва ограничења су линеарна.

Осим тога постоји много комбинаторних алгоритама за опширнији. Неки од њих су генерализације алгоритама максималног протока, други користе у потпуности другачије приступе решавању проблема.

Добро познати фундементални алгоритми (имају много варијација):

• Избацивање циклуса, генерално основни метод.
• Избацивање минималних циклуса, једноставан строго полиномијални алгоритам.
• Узастопни најкраћи путеви, пропорционисање пропустности: дуалне методе, које се могу посматрати као генерализације Форд-фулкерсоновог алгоритма.
• Пропорционисање цена, Основни дуални приступ који може бити посматран као генерализаија алгоритма push-relabel.
• Симплекс мреже: Специјализована верзија линеарног програмирања симплекс методе, која се извршава у полиномијалном времену.