مشكلة تدفق السلع المتعددة

مشكلة تدفق السلع المتعددة هي مشكلة تدفق شبكي تتضمن سلعًا متعددة (طلبات تدفق) بين عقد المصدر والمصب المختلفة.

بالنظر إلى شبكة التدفق${\displaystyle \,G(V,E)}$، حيث الحافة${\displaystyle (u,v)\in E}$لديها القدرة${\displaystyle \,c(u,v)}$هناك${\displaystyle \,k}$سلعة${\displaystyle K_{1},K_{2},\dots ,K_{k}}$، كما هو محدد بواسطة${\displaystyle \,K_{i}=(s_{i},t_{i},d_{i})}$، أين${\displaystyle \,s_{i}}$و${\displaystyle \,t_{i}}$هو مصدر ومصب السلعة​${\displaystyle \,i}$، و${\displaystyle \,d_{i}}$هو الطلب عليه. المتغير${\displaystyle \,f_{i}(u,v)}$يحدد نسبة التدفق${\displaystyle \,i}$على طول الحافة${\displaystyle \,(u,v)}$، أين${\displaystyle \,f_{i}(u,v)\in [0,1]}$في حال إمكانية تقسيم التدفق بين مسارات متعددة، و${\displaystyle \,f_{i}(u,v)\in \{0,1\}}$وإلا (أي "التوجيه أحادي المسار"). أوجد تعيينًا لجميع متغيرات التدفق التي تحقق القيود الأربعة التالية:

(1) سعة الرابط: مجموع جميع التدفقات الموجهة عبر رابط لا يتجاوز سعته.

${\displaystyle \forall (u,v)\in E:\,\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\leq c(u,v)}$

(2) حفظ التدفق في عقد العبور: مقدار التدفق الداخل إلى عقدة وسيطة${\displaystyle u}$هو نفسه الذي يخرج من العقدة.

${\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(u,w)-\sum _{(w,u)\in E}f_{i}(w,u)=0\quad \mathrm {when} \quad u\neq s_{i},t_{i}}$

(3) الحفاظ على التدفق عند المصدر: يجب أن يخرج التدفق من عقدة المصدر الخاصة به بالكامل.

${\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(s_{i},w)\in E}f_{i}(s_{i},w)-\sum _{(w,s_{i})\in E}f_{i}(w,s_{i})=1}$

(4) الحفاظ على التدفق عند الوجهة: يجب أن يدخل التدفق عقدة المصب بالكامل.

${\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(w,t_{i})\in E}f_{i}(w,t_{i})-\sum _{(t_{i},w)\in E}f_{i}(t_{i},w)=1}$

موازنة الأحمال هي محاولة لتوجيه التدفقات بحيث يكون الاستخدام${\displaystyle U(u,v)}$من بين جميع الروابط${\displaystyle (u,v)\in E}$زوجي، حيث

${\displaystyle U(u,v)={\frac {\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}}{c(u,v)}}}$

يمكن حل المشكلة، على سبيل المثال، عن طريق تقليل${\displaystyle \sum _{u,v\in V}(U(u,v))^{2}}$تتمثل إحدى طرق التبسيط الشائعة لهذه المشكلة في تقليل الحد الأقصى للاستخدام${\displaystyle U_{max}}$، أين

${\displaystyle \forall (u,v)\in E:\,U_{max}\geq U(u,v)}$

في مسألة تدفق السلع المتعددة ذات التكلفة الدنيا ، توجد تكلفة${\displaystyle a(u,v)\cdot f(u,v)}$لإرسال تدفق على${\displaystyle \,(u,v)}$ثم عليك تقليل

${\displaystyle \sum _{(u,v)\in E}\left(a(u,v)\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\right)}$

في مسألة التدفق الأقصى للسلع المتعددة ، لا يكون الطلب على كل سلعة ثابتًا، ويتم تعظيم إجمالي الإنتاجية عن طريق تعظيم مجموع جميع الطلبات.${\displaystyle \sum _{i=1}^{k}d_{i}}$

يُعدّ متغير الحد الأدنى للتكلفة لمسألة تدفق السلع المتعددة تعميمًا لمسألة تدفق الحد الأدنى للتكلفة (التي يوجد فيها مصدر واحد فقط).${\displaystyle s}$وحوض واحد${\displaystyle t}$تُعدّ متغيرات مسألة الدوران تعميمات لجميع مسائل التدفق. أي أنه يمكن اعتبار أي مسألة تدفق مسألة دوران خاصة. ^{[ 1 ]}

سيتم التعامل مع التوجيه وتخصيص الطول الموجي (RWA) في تبديل النبضات الضوئية للشبكة الضوئية من خلال صيغ تدفق السلع المتعددة، إذا كانت الشبكة مجهزة بتحويل الطول الموجي في كل عقدة.

يمكن نمذجة تخصيص السجلات كمسألة تدفق سلع متعددة بأقل تكلفة عددية صحيحة: القيم التي تنتجها التعليمات هي عقد المصدر، والقيم التي تستهلكها التعليمات هي عقد المصب، والسجلات بالإضافة إلى خانات المكدس هي الحواف. ^{[ 2 ]}

في نسخة القرار من المشاكل، فإن مشكلة إنتاج تدفق صحيح يلبي جميع الطلبات هي NP-كاملة ، ^{[ 3 ]} حتى بالنسبة لسلعتين فقط وقدرات وحدة (مما يجعل المشكلة NP-كاملة بقوة في هذه الحالة).

إذا سُمح بالتدفقات الكسرية، فيمكن حل المشكلة في وقت متعدد الحدود من خلال البرمجة الخطية ، ^{[ 4 ]} أو من خلال مخططات تقريبية متعددة الحدود بالكامل (عادةً ما تكون أسرع بكثير) . ^{[ 5 ]}

يتم تطبيق تدفق السلع المتعددة في توجيه التراكب في توصيل المحتوى. ^{[ 6 ]}

• أوراق بحثية لكليفورد شتاين حول هذه المشكلة: http://www.columbia.edu/~cs2035/papers/#mcf
• برنامج لحل المشكلة: https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/

إضافة: جان باتريس نيتير، شبكات تعزيز التدفق: نوع أولي من النهج لتحقيق أقصى تدفق صحيح في شبكة متعددة السلع، أطروحة دكتوراه، جامعة جونز هوبكنز، 1971