Проблем минималне цене

Из Википедије, слободне енциклопедије

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

Дефиниција[уреди]

Са задатом Трансортном мрежом која је оријентисани граф Г=(В, Е) са извором с∈В и завпшним чвором т∈В, где грана(у, в)∈Е има пропустност ц(у, в)>0, проток ф(у, в)>0 и цене а(у, в)(већина алгоритама минималне цене протока подржавају гране са негативним ценама). Цена сланја оваквог протока је ф(у, в)·а(у, в). Потребно је послати д протока од с до в. Дефиниција проблема је минимизирати укупну цену протока.

Σ(у, в)∈Ва(у, в)·ф(у, в)

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

   Ограничење пропусности ф(у, в)≤ц(у, в)
   Коса циметрија ф(у, в)= -ф(в, у)
   Чување тока Σх∈Вф(у, х)=0 за све у≠с, т
   Потребан проток Σх∈Вф(с, х)=д и Σх∈Вф(х, т)=д

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

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

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

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

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

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

Решења[уреди]

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

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

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

  • Избациванје циклуса, генерално основни метод.[2]
  • Избациванје минималноих циклуса, једноставан строго полиномијални алгоритам.[3]
  • Узастопни најкраћи путеви, пропорционисанје пропустности: дуалне методе , које се могу посматрати као генерализације форд-фулкерсон алгоритма.[4]
  • Пропорционисање цена:Основна дуални приступ који може бити посматран као генерализаија алгоритма гурања-ознаке.[5]
  • Симплекс мреже: Специјализована верзија линеарног програмиранја симплекс методе, која се извршава у полиномијалном времену.[6]

Такође видети[уреди]

Референце[уреди]

  1. ^ Равиндра К. Ахуја,Томас Л. Магнанти, и Џејмс Б. Орлин(1993). Транспортне мреже:Теорија, Алгоритми и употребе.
  2. ^ Мортон Клеин (1967) основни алгоритам за минимлну цену протока са употребама за проблеме задатака и проблеме транспортације.
  3. ^ Андерс В. Голдбург и Роберт Е. Тарјан (1989). Налажење циклуса минималне цене поништавањем негативних циклуса
  4. ^ Џек Емондс и Ричард М. Карп (1972)Теоритичка побољшања у ефикасности алгоритама за транспортне мреже.
  5. ^ Андерс В. Голдбург и Роберт Е. Тарјан (1990) Налажење циклуса минималне цене постепеном апроксимацијом
  6. ^ Џејмс Б. Орлин (1997). Симплекс алгоритам полиномијалног времена извршавања основне мреже за протоке минималне цене