Back

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




                                     

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

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

                                     

1. Дефиниција

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

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

∑ u, v ∈ E a u, v ⋅ f u, v {\displaystyle \sum _{u,v\in E}au,v\cdot fu,v}

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

                                     

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

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

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

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

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

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

3. Решења

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

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

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

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