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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

مسئله کم‌هزینه‌ترین جریان، پیدا کردن کم‌هزینه‌ترین راه فرستادن میزان مشخصی از جریان درون یک شبکه شاره است. حل این مسئله در زندگی روزمره کاربردهایی دارد از جمله شبکه‌های هزینه‌دار (مانند شبکه‌های مخابراتی) و هم‌چنین در مواردی که تناسب آن با مسئله خیلی مشهود نیست، مانند تعیین محل قرارگیری انبارها.

تعریف[ویرایش]

یک شبکه شاره داریم که آن را با گراف جهت‌دار G=(V,E) با مبدا s \in V و مقصد t \in V که در آن یال (u,v) \in E دارای ظرفیت c(u,v)> 0، جریان f(u,v) \ge 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) \le 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

ارتباط با مسئله‌های دیگر[ویرایش]

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

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

می‌توان از مسئله کم‌هزینه‌ترین گردش در حل این مسئله استفاده کرد. این کار با صفر قرار دادن کران پایین همه‌ی یال‌ها، اضافه کردن یک یال از مقصد t به مبدا s با ظرفیت c(t,s)=d و کران پایین l(t,s)=d و قرار دادن کل جریان برابر d انجام می‌شود.

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

راه‌حل‌ها[ویرایش]

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

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

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

کاربرد[ویرایش]

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

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

در گراف دو بخشی G=(A \cup B,E)، میخواهیم تطابق بیشینه با کمترین هزینه را بیابیم. w: ER را تابع وزن یال های گراف در نظر بگیرید. هدف از مسئله کم وزن ترین تطابق بیشینه دو بخشی یا مسئله تخصیص، پیدا کردن یک تطابق کامل ME است که مجموع وزن هایش کمینه باشد. میخواهیم این مسئله را به یک مسئله شبکه شاره کاهش دهیم.

G'=(V'=A \cup B,E'=E) را در نظر بگیرید. ظرفیت تمام یال های E' را 1 بگذارید. رأس مبدا s را اضافه کرده و به تمام رئوس A' متصل میکنیم و رأس مقصد t را اضافه کرده و تمام رئوس B' را به آن متصل میکنیم. ظرفیت تمام یال های جدید را یک و هزینه آنها را صفر در نظر میگیریم. ثابت میشود که یک کم وزن ترین تطابق دو بخشی در G موجود است اگر و فقط اگر یک کم هزینه ترین جریان در G' وجود داشته باشد.[۷]

جستارهای وابسته[ویرایش]

پانویس‌ها و منابع[ویرایش]

  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 E. Tarjan (1989). "Finding minimum-cost circulations by canceling negative cycles". Journal of the ACM 36 (4): 873–886. 
  4. ^ Jack Edmonds and ریچارد کارپ (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM 19 (2): 248–264. 
  5. ^ Andrew V. Goldberg and Robert E. 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. 

پیوندهای کمکی[ویرایش]