مسئله کمینه هزینه جریان (Minimum Cost Flow Problem)، در ریاضیات (Mathematics)

انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :

انواع روش های بهینه سازی (Optimization Methods)، در ریاضیات (Mathematics)

مسئله کمینه هزینه جریان (Minimum Cost Flow Problem) :

📌 معرفی

مسئله کمینه هزینه جریان (Minimum Cost Flow) یک مسئله عمومی تر است که در آن هر یال دارای هزینه هر واحد جریان و ظرفیت است، و هر گره دارای عرضه یا تقاضا می باشد. هدف ارسال جریان از گره های عرضه به گره های تقاضا با کمترین هزینه است.

📐 فرمول بندی ریاضی

\[ \min \sum_{(i,j) \in A} c_{ij} f_{ij} \] \[ \text{s.t.} \quad \sum_{j} f_{ij} - \sum_{j} f_{ji} = b_i \quad \forall i \] \[ \quad 0 \leq f_{ij} \leq u_{ij} \quad \forall (i,j) \]

که

\[ b_i \]

عرضه (مثبت) یا تقاضا (منفی) در گره

\[ i \]

است و

\[ \sum_i b_i = 0 \]

🔧 الگوریتم های حل

الگوریتم چرخه های منفی (Negative Cycle Canceling): یافتن و حذف چرخه های با هزینه منفی.

الگوریتم سیمپلکس شبکه (Network Simplex): کارآمدترین روش برای مسائل بزرگ.

الگوریتم های مبتنی بر پتانسیل (Successive Shortest Path): با استفاده از الگوریتم دیکسترا و پتانسیل ها.

دسته بندی روش های بهینه سازی (Optimization Methods) (الگوریتم های بهینه سازی)، در ریاضیات (Mathematics)

نویسنده علیرضا گلمکانی