مشكلة التدفق بأقل تكلفة

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
📷 يحتوي على 31 صور
الموسوعة الحرة

تُعدّ مسألة التدفق بأقل تكلفة ( MCFP ) مسألة تحسين واتخاذ قرار تهدف إلى إيجاد أرخص طريقة ممكنة لنقل كمية معينة من التدفق عبر شبكة تدفق . ومن التطبيقات الشائعة لهذه المسألة إيجاد أفضل مسار توصيل من مصنع إلى مستودع، حيث تتمتع شبكة الطرق بسعة وتكلفة محددتين. وتُعتبر مسألة التدفق بأقل تكلفة من أهم مسائل التدفق والتداول، إذ يمكن صياغة معظم المسائل الأخرى المشابهة على أنها مسألة تدفق بأقل تكلفة، كما يمكن حلها بكفاءة باستخدام خوارزمية الشبكة البسيطة .

تعريف

شبكة التدفق هي رسم بياني موجهجي=(V،هـ){\displaystyle G=(V,E)}مع رأس مصدرs∈V{\displaystyle s\in V}ورأس حوضت∈V{\displaystyle t\in V}، حيث كل حافة(u،v)∈هـ{\displaystyle (u,v)\in E}لديها القدرةج(u،v)>0{\displaystyle c(u,v)>0}، تدفقو(u،v){\displaystyle f(u,v)}والتكلفةأ(u،v){\displaystyle a(u,v)}تدعم معظم خوارزميات تدفق التكلفة الدنيا الحواف ذات التكاليف السالبة. تكلفة إرسال هذا التدفق على طول حافة(u،v){\displaystyle (u,v)}يكونو(u،v)⋅أ(u،v){\displaystyle f(u,v)\cdot a(u,v)}تتطلب المشكلة قدراً من التدفقد{\displaystyle d}سيتم إرسالها من المصدرs{\displaystyle s}للغرقت{\displaystyle t}.

تعريف المشكلة هو تقليل التكلفة الإجمالية للتدفق عبر جميع الحواف:

∑(u،v)∈هـأ(u،v)⋅و(u،v){\displaystyle \sum _{(u,v)\in E}a(u,v)\cdot f(u,v)}

مع مراعاة القيود

قيود الطاقة الاستيعابية :و(u،v)≤ج(u،v){\displaystyle \,f(u,v)\leq c(u,v)}
التناظر المائل :و(u،v)=-و(v،u){\displaystyle \,f(u,v)=-f(v,u)}
حفظ التدفق :∑w∈Vو(u،w)=0 للجميع u≠s،ت{\displaystyle \,\sum _{w\in V}f(u,w)=0{\text{ لجميع }}u\neq s,t}
التدفق المطلوب :∑w∈Vو(s،w)=د و ∑w∈Vو(w،ت)=د{\displaystyle \,\sum _{w\in V}f(s,w)=d{\text{ و }}\sum _{w\in V}f(w,t)=d}

العلاقة بالمشاكل الأخرى

يتمثل أحد أشكال هذه المسألة في إيجاد تدفق أقصى بأقل تكلفة بين حلول التدفق الأقصى. ويمكن تسمية هذه المسألة بمسألة التدفق الأقصى بأقل تكلفة، وهي مفيدة لإيجاد أفضل تطابق بأقل تكلفة .

في بعض الحلول، يكون إيجاد الحد الأدنى للتكلفة والحد الأقصى للتدفق أمرًا مباشرًا. وإذا لم يكن الأمر كذلك، فيمكن إيجاد الحد الأقصى للتدفق عن طريق إجراء بحث ثنائي علىد{\displaystyle d}.

تُعدّ مسألة تدوير التكلفة الدنيا مشكلةً ذات صلة ، ويمكن استخدامها لحلّ مسألة تدفق التكلفة الدنيا. لا تحتوي مسألة تدوير التكلفة الدنيا على مصدر أو مصب؛ بل تحتوي على تكاليف وحدود دنيا وعليا على كل حافة، وتسعى إلى إيجاد كميات تدفق ضمن الحدود المُعطاة تُوازن التدفق عند كل رأس وتُقلّل مجموع حاصل ضرب التكلفة في التدفق على جميع الحواف. يُمكن تحويل أيّ حالة تدفق بتكلفة دنيا إلى حالة تدوير بتكلفة دنيا عن طريق ضبط الحد الأدنى على جميع الحواف إلى الصفر، ثم إنشاء حافة إضافية من المصب.ت{\displaystyle t}إلى المصدرs{\displaystyle s}بسعةج(ت،s)=د{\displaystyle c(t,s)=d}والحد الأدنىل(ت،s)=د{\displaystyle l(t,s)=d}مما يجبر التدفق الكلي منs{\displaystyle s}لت{\displaystyle t}أن يكون أيضًاد{\displaystyle d}.

المشاكل التالية هي حالات خاصة من مشكلة تدفق التكلفة الدنيا (نقدم رسومات موجزة لكل تخفيض قابل للتطبيق، بدوره): [ 1 ]

  • مسألة أقصر مسار (مصدر واحد). تتطلب هذه المسألة أن يُرسل الحل الأمثل لمسألة تدفق التكلفة الدنيا وحدة تدفق واحدة من مصدر محدد.s{\displaystyle s}إلى حوض مخصصت{\displaystyle t}أعطِ جميع الحواف سعة غير محدودة.
  • مسألة التدفق الأقصى . اختر طلبًا كبيرًاد{\displaystyle d}(كبيرة بما يكفي لتجاوز الحد الأقصى للتدفق؛ على سبيل المثال، مجموع السعات الخارجة من رأس المصدر) اجعل تكاليف جميع الحواف في حالة التدفق الأقصى تساوي صفرًا، وأضف حافة جديدة من المصدر إلى المصب بتكلفة وسعة وحدة واحدةد{\displaystyle d}.
  • مسألة التخصيص . لنفترض أن كل مجموعة جزئية في التقسيم الثنائي تحتوي علىن{\displaystyle n}الرؤوس، ونرمز إلى التقسيم الثنائي بـ(X،Y){\displaystyle (X,Y)}أعطِ كل واحدx∈X{\displaystyle x\in X}إمداد1/ن{\displaystyle 1/n}وأعطِ كل واحدy∈Y{\displaystyle y\in Y}يطلب1/ن{\displaystyle 1/n}يجب أن يكون لكل حافة سعة وحدة واحدة.

الحلول

يمكن حل مشكلة تدفق التكلفة الدنيا عن طريق البرمجة الخطية ، حيث أننا نقوم بتحسين دالة خطية، وجميع القيود خطية.

إلى جانب ذلك، توجد العديد من الخوارزميات التوافقية. [ 1 ] بعضها تعميمات لخوارزميات التدفق الأقصى ، والبعض الآخر يستخدم مناهج مختلفة تمامًا.

الخوارزميات الأساسية المعروفة (ولها العديد من الاختلافات):

خوارزميات إلغاء الدورة

هذه الخوارزميات تكرارية، ومثل خوارزمية فورد-فولكرسون، فإنها تحدد رسمًا بيانيًا متبقيًا. إذا كان هناك تدفقو(u،v){\displaystyle f(u,v)}على قوسهـ=(u،v){\displaystyle e=(u,v)}ثم تُعرَّف سعتها المتبقية بأنهاج(هـ)-و(هـ){\displaystyle c(e)-f(e)}وتكلفتها المتبقية هيأ(هـ){\displaystyle a(e)}القوس العكسي (الذي له قيمة تدفق سالبة) له تكلفة سالبة-أ(هـ){\displaystyle -a(e)}تبدأ الخوارزميات بتدفق ممكن عشوائي، ثم تُحسّن تكلفة الحل بشكل متكرر عن طريق توجيه التدفق حول الدورات ذات التكلفة السالبة. في خوارزمية إلغاء الدورة ذات المتوسط ​​الأدنى ، تختار الخوارزمية دورة ذات متوسط ​​تكلفة أدنى (نسبة التكلفة الإجمالية للدورة إلى عدد الأقواس). يمكن إيجاد هذه الدورة في وقت متعدد الحدود (باستخدام البحث الثنائي وخوارزمية بيلمان-فورد )، وقد ثبت أن العدد الإجمالي للتكرارات متعدد الحدود [ 5 ] .

خوارزمية زمنية شبه خطية

من المعروف أن خوارزمية حتمية ذات زمن شبه خطي تحل مشكلة التدفق بأقل تكلفة على الرسوم البيانية الموجهة. [ 9 ] أي على رسم بياني معم{\displaystyle m}مع وجود حواف وطلبات وتكاليف وقدرات محدودة متعددة الحدود، تعمل الخوارزمية في وقتم1+o(1){\displaystyle m^{1+o(1)}}.

طلب

مطابقة ثنائية الحد الأدنى للوزن

تقليل مطابقة الأجزاء الثنائية ذات الوزن الأدنى إلى مشكلة التدفق الأقصى بأقل تكلفة

بالنظر إلى رسم بياني ثنائي الأجزاء G = ( A ∪ B , E ) ، فإن الهدف هو إيجاد التطابق ذي العدد الأقصى من العناصر في G بأقل تكلفة. ولتكن w : E → R دالة وزن على حواف E. تتمثل مسألة المطابقة الثنائية ذات الوزن الأدنى، أو مسألة التخصيص، في إيجاد تطابق مثالي M ⊆ E يكون وزنه الإجمالي في أدنى حد. الفكرة هي اختزال هذه المسألة إلى مسألة تدفق شبكي.

ليكن G ′ = ( V ′ = A ∪ B , E ′ = E ) . نُعيّن سعة جميع الحواف في E ′ إلى 1. نضيف رأس مصدر s ونوصله بجميع رؤوس A ′، ونضيف رأس مصب t ونوصل جميع رؤوس المجموعة B ′ بهذا الرأس. سعة جميع الحواف الجديدة هي 1 وتكاليفها 0. ثبت أنه يوجد تطابق ثنائي مثالي ذو وزن أدنى في G إذا وفقط إذا كان هناك تدفق ذو تكلفة دنيا في G ′ . [ 1 ]

انظر أيضاً

مراجع

  1. 1 2 3 رافيندرا ك. أهوجا ؛ توماس ل. ماجنانتي وجيمس ب. أورلين (1993). تدفقات الشبكة: النظرية والخوارزميات والتطبيقات . برنتيس هول، إنك. ISBN 978-0-13-617549-0.
  2. ↑ مورتون كلاين (1967). "طريقة أولية لتدفقات التكلفة الدنيا مع تطبيقات على مشاكل التخصيص والنقل". مجلة علوم الإدارة . 14 (3): 205-220 . Bibcode : 1967ManSc..14..205K . CiteSeerX 10.1.1.228.7696 . doi : 10.1287/mnsc.14.3.205 . 
  3. ↑ رفائيل حسين (1983). "مسألة التدفق بأقل تكلفة: منهج موحد للخوارزميات الحالية وخوارزمية بحث شجرية جديدة". البرمجة الرياضية . 25 : 228-239 . doi : 10.1007/bf02591772 .
  4. ↑ توماس ر. إرفولينا وس. توماس ماكورميك (1993). "خوارزميتان قويتان لإلغاء القطع متعدد الحدود لتدفق الشبكة بأقل تكلفة" . الرياضيات التطبيقية المنفصلة . 4 (2): 133-165 . doi : 10.1016/0166-218x(93)90025-j .
  5. 1 2 أندرو ف. غولدبيرغ وروبرت إي. تارجان (1989). "إيجاد دورات بأقل تكلفة عن طريق إلغاء الدورات السلبية". مجلة ACM . 36 (4): 873-886 . doi : 10.1145/76359.76368 . hdl : 1721.1/149134 .
  6. ↑ جاك إدموندز وريتشارد إم. كارب (1972). "تحسينات نظرية في كفاءة الخوارزميات لمشاكل تدفق الشبكة" . مجلة ACM . 19 (2): 248-264 . doi : 10.1145/321694.321699 .
  7. ↑ غولدبيرغ، أندرو ف. وتارجان ، روبرت إي. (1990). "إيجاد دورات التكلفة الدنيا بالتقريب المتتالي". رياضيات بحوث العمليات . 15 (3): 430-466 . doi : 10.1287/moor.15.3.430 . hdl : 1721.1/149133 .
  8. ↑ جيمس ب. أورلين (1997). "خوارزمية شبكة سيمبلكس أولية ذات زمن متعدد الحدود لتدفقات التكلفة الدنيا". البرمجة الرياضية . 78 (2): 109-129 . doi : 10.1007/bf02614365 . hdl : 1721.1/2584 .
  9. ↑ براند، جان فان دين؛ تشين، لي؛ كينغ، راسموس؛ ليو، يانغ ب.؛ بينغ، ريتشارد؛ غوتنبرغ، ماكسيميليان بروبست؛ ساشديفا، سوشانت؛ سيدفورد، آرون (نوفمبر 2023). "خوارزمية حتمية شبه خطية لتدفق الحد الأدنى من التكلفة". المؤتمر السنوي الرابع والستون لمؤسسة مهندسي الكهرباء والإلكترونيات (IEEE) حول أسس علوم الحاسوب (FOCS) لعام 2023 : 503-514 . Bibcode : 2023focs.conf...38B . doi : 10.1109/FOCS57990.2023.00037 . ISBN 979-8-3503-1894-4.