مسئله کم‌هزینه‌ترین جریان

یک شبکه شاره داریم که آن را با گراف جهت‌دار ${\displaystyle G=(V,E)}$

تعریف مسئله کمینه کردن هزینه کل جریان است:

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

با شرط‌های زیر:

محدودیت ظرفیت:	${\displaystyle f(u,v)\le c(u,v)}$
تقارن یک‌سویه:	${\displaystyle f(u,v)=-f(v,u)}$
بقای جریان:	${\displaystyle \sum _{w\in V}f(u,w)=0\text{ for all }u\ne s,t}$
جریان خواسته‌شده:	${\displaystyle \sum _{w\in V}f(s,w)=d\text{ and }\sum _{w\in V}f(w,t)=d}$

حالت دیگری از این مسئله پیدا کردن جریان بیشینه‌ای است که بین جریان‌های بیشینه کم‌ترین هزینه را دارد که می‌توان آن را مسئله کم‌هزینه‌ترین بیشینه جریان نامید. این حالت در پیدا کردن کم‌هزینه‌ترین تطابق بیشینه کاربرد دارد.

در بعضی راه‌حل‌ها پیدا کردن کم‌هزینه‌ترین بیشینه جریان ساده است. در غیر این صورت، می‌توان از جستجوی دودویی روی ${\displaystyle d}$

می‌توان از مسئله کم‌هزینه‌ترین گردش در حل این مسئله استفاده کرد. این کار با صفر قرار دادن کران پایین همه‌ی یال‌ها، اضافه کردن یک یال از مقصد ${\displaystyle t}$

دو مسئله زیر حالات خاص این مسئله به شمار می آیند:

• اگر محدودیت ظرفیت برداشته شود، به مسئله یافتن کوتاه‌ترین مسیر تبدیل می‌شود.
• اگر همه هزینه‌ها صفر باشند، به مسئله بیشینه جریان تبدیل می‌شود.

از آنجایی که ما تابعی خطی را بهینه میکنیم و تمام شروط خطی اند، این مسئله با استفاده از برنامه‌ریزی خطی قابل حل است.

علاوه بر آن الگوریتم‌های ترکیبیاتی مختلفی نیز وجود دارند، برای بررسی جامع تر، را ببینید. تعدادی از آن‌ها تعمیم الگوریتم بیشینه جریان هستند، بقیه روش‌های کاملاً متفاوتی استفاده میکنند.

الگوریتم‌های اساسی شناخته شده (حالت‌های زیادی دارند):

• Cycle canceling یک روش کلی اولیه
• Minimum mean cycle canceling یک الگوریتم ساده قویا چندجمله‌ای
• Successive shortest path and capacity scaling روش‌های دوگانه که می‌توان آن‌ها را به عنوان تعمیم‌های الگوریتم فورد–فالکرسون در نظر گرفت.
• Cost scaling یک روش اولیه-دوگانه، که حالت کلی الگوریتم ارسال-برچسب است.
• Network simplex حالت خاص برنامه‌ریزی خطی غیر مرکب است که در زمان چندجمله‌ای اجرا می‌شود.
• الگوریتم Out-of-kilter توسط D.R.Fulkerson

کم وزن ترین تطابق بیشینه دو بخشی

در گراف دو بخشی ${\displaystyle G=(A\cup B,E)}$

${\displaystyle G^{\prime }=(V^{\prime }=A\cup B,E^{\prime }=E)}$

• LEMON (C++ library)

1. ^ Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin (1993). Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc. ISBN 0-13-617549-X.
2. ^ Morton Klein (1967). "A primal method for minimal cost flows with applications to the assignment and transportation problems". Management Science. 14: 205–220.
3. ^ Andrew V. Goldberg and Robert Tarjan (1989). "Finding minimum-cost circulations by canceling negative cycles". Journal of the ACM. 36 (4): 873–886.
4. ^ Jack Edmonds and Richard M. Karp (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM. 19 (2): 248–264.
5. ^ Andrew V. Goldberg and Robert Tarjan (1990). "Finding minimum-cost circulations by successive approximation". Math. Oper. Res. 15 (3): 430–466.
6. ^ James B. Orlin (1997). "A polynomial time primal network simplex algorithm for minimum cost flows". Mathematical Programming. 78: 109–129.

• LEMON C++ library with several maximum flow and minimum cost circulation algorithms