مشكلة في الدورة الدموية

الموسوعة الحرة

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

تعريف

شبكة التدفق المعطاةجي(V،هـ){\displaystyle G(V,E)}مع:

ل(v،w){\displaystyle l(v,w)}الحد الأدنى للتدفق من العقدةv{\displaystyle v}إلى العقدةw{\displaystyle w}،
u(v،w){\displaystyle u(v,w)}الحد الأعلى للتدفق من العقدةv{\displaystyle v}إلى العقدةw{\displaystyle w}،
ج(v،w){\displaystyle c(v,w)}تكلفة وحدة التدفق على(v،w){\displaystyle (v,w)}

والقيود:

ل(v،w)≤و(v،w)≤u(v،w){\displaystyle l(v,w)\leq f(v,w)\leq u(v,w)}،
∑w∈Vو(u،w)=0{\displaystyle \sum _{w\in V}f(u,w)=0}(لا يمكن أن يظهر التدفق أو يختفي في العقد).

إن إيجاد تخصيص تدفق يفي بالقيود يعطي حلاً لمشكلة الدوران المعطاة.

في صيغة الحد الأدنى للتكلفة للمسألة، قم بتقليل

∑(v،w)∈هـج(v،w)⋅و(v،w).{\displaystyle \sum _{(v,w)\in E}c(v,w)\cdot f(v,w).}

تداول السلع المتعددة

في مشكلة تداول السلع المتعددة، تحتاج أيضًا إلى تتبع تدفق السلع الفردية:

وأنا(v،w){\displaystyle \,f_{i}(v,w)}تدفق السلعأنا{\displaystyle i}منv{\displaystyle v}لw{\displaystyle w}.
و(v،w)=∑أناوأنا(v،w){\displaystyle \,f(v,w)=\sum _{i}f_{i}(v,w)}التدفق الكلي.

يوجد أيضًا حد أدنى لكل تدفق من السلع.

لأنا(v،w)≤وأنا(v،w){\displaystyle \,l_{i}(v,w)\leq f_{i}(v,w)}

يجب الالتزام بقيد الحفظ بشكل فردي لكل سلعة:

 ∑w∈Vوأنا(u،w)=0.{\displaystyle \ \sum _{w\in V}f_{i}(u,w)=0.}

حل

بالنسبة لمسألة الدوران، تم تطوير العديد من الخوارزميات متعددة الحدود (مثل خوارزمية إدموندز-كارب ، 1972؛ تارجان 1987-1988). وقد اكتشف تاردوس أول خوارزمية متعددة الحدود قوية . [ 1 ]

في حالة السلع المتعددة، تكون المسألة من فئة NP-complete بالنسبة للتدفقات الصحيحة. [ 2 ] أما بالنسبة للتدفقات الكسرية، فيمكن حلها في وقت متعدد الحدود ، حيث يمكن صياغة المسألة كبرنامج خطي .

فيما يلي بعض المشاكل، وكيفية حلها باستخدام نظام الدوران العام المذكور أعلاه.

  • مشكلة تداول السلع المتعددة بأقل تكلفة - باستخدام جميع القيود المذكورة أعلاه.
  • مشكلة التداول بأقل تكلفة - استخدام سلعة واحدة
  • تداول السلع المتعددة - حل المشكلة دون تحسين التكلفة.
  • التداول البسيط - استخدام سلعة واحدة فقط، وبدون تكلفة.
  • تدفق السلع المتعددة - إذاكأنا(sأنا،تأنا،دأنا){\displaystyle K_{i}(s_{i},t_{i},d_{i})}يشير إلى طلب مندأنا{\displaystyle d_{i}}للسلعأنا{\displaystyle i}منsأنا{\displaystyle s_{i}}لتأنا{\displaystyle t_{i}}، إنشاء حافة(تأنا،sأنا){\displaystyle (t_{i},s_{i})}معلأنا(تأنا،sأنا)=u(تأنا،sأنا)=دأنا{\displaystyle l_{i}(t_{i},s_{i})=u(t_{i},s_{i})=d_{i}}لجميع السلعأنا{\displaystyle i}. يتركلأنا(u،v)=0{\displaystyle l_{i}(u,v)=0}بالنسبة لجميع الحواف الأخرى.
  • مشكلة تدفق السلع المتعددة بأقل تكلفة - كما هو مذكور أعلاه، ولكن مع تقليل التكلفة.
  • مشكلة تدفق التكلفة الدنيا - كما هو مذكور أعلاه، مع سلعة واحدة.
  • مشكلة التدفق الأقصى - اجعل جميع التكاليف تساوي صفرًا، وأضف حافة من نقطة التجميع.ت{\displaystyle t}إلى المصدرs{\displaystyle s}معل(ت،s)=0{\displaystyle l(t,s)=0}،u(ت،s)={\displaystyle u(t,s)=}∞ وج(ت،s)=-1{\displaystyle c(t,s)=-1}.
  • مسألة الحد الأدنى للتكلفة والحد الأقصى للتدفق - أولاً، إيجاد الحد الأقصى لمقدار التدفقم{\displaystyle m}ثم قم بالحل باستخدامل(ت،s)=u(ت،s)=م{\displaystyle l(t,s)=u(t,s)=m}وج(ت،s)=0{\displaystyle c(t,s)=0}.
  • أقصر مسار من مصدر واحد - ليكنل(u،v)=0{\displaystyle l(u,v)=0}وج(u،v)=1{\displaystyle c(u,v)=1}لكل حافة في الرسم البياني، أضف حافة(ت،s){\displaystyle (t,s)}معل(ت،s)=u(ت،s)=1{\displaystyle l(t,s)=u(t,s)=1}وج(ت،s)=0{\displaystyle c(t,s)=0}.
  • أقصر مسار بين جميع الأزواج - لنفترض أن جميع السعات غير محدودة، ونجد تدفقًا مقداره 1 لـv(v-1)/2{\displaystyle v(v-1)/2}السلع، سلعة واحدة لكل زوج من العقد.

مراجع

  1. ↑ إيفا تاردوس (1985). "خوارزمية تداول ذات تكلفة دنيا متعددة الحدود بقوة". كومبيناتوريكا . 5 (3): 247-255 . doi : 10.1007/BF02579369 .
  2. ↑ إس. إيفن، أ. إيتاي، وأ. شامير (1976). "حول تعقيد مسائل الجداول الزمنية وتدفق السلع المتعددة" . مجلة SIAM للحوسبة . 5 (4). SIAM: 691-703 . doi : 10.1137/0205048 .{{cite journal}}: CS1 maint: deprecated archiveal service ( link )