مرجع
آخر الزيارات

مسألة التدفق الأقصى

3٬170 كلمة•0 مشاهدة•🗒️ منذ 18 يوماً
باختصار: في إطار نظرية التحسين، تُعنى مسائل التدفق الأقصى بإيجاد تدفق ممكن عبر شبكة تدفق يحقق أعلى معدل تدفق ممكن. تتناول المقالة 14 قسماً، منها «الامتدادات»، «تنص نظرية التدفق التكاملي على أن» و«مشكلة التدفق الأقصى متعدد المصادر ومتعدد الأحواض».
المحتويات
  1. الامتدادات
  2. تنص نظرية التدفق التكاملي على أن
  3. مشكلة التدفق الأقصى متعدد المصادر ومتعدد الأحواض
  4. مشكلة الإغلاق
  5. الخوارزميات
  6. تقسيم الصورة
  7. تاريخ
  8. مطابقة ثنائية الأجزاء لأقصى عدد أساسي
  9. إقصاء البيسبول
  10. الحد الأقصى للتدفق مع قدرات القمة
  11. تعريف
  12. مشكلة التداول والطلب
  13. لأن
  14. جدولة خطوط الطيران
مسألة التدفق الأقصى

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

في هذا الإطار، يمكن اعتبار مشكلة التدفق الأقصى حالة خاصة من مسائل تدفق الشبكات الأكثر شمولية، مثل مشكلة الدورة الدموية .. وتنص نظرية الحد الأقصى للتدفق والحد الأدنى للقطع على أن القيمة القصوى للتدفق من المصدرs إلى المصرف t (يُشار إليها بتدفق st) تعادل الحد الأدنى لسعة أي قطع يفصل s عن t (يُشار إليه بقطع st) في الشبكة..

.

الامتدادات

ومن ناحية أخرى، 2. يمكن تعقيد مشكلة التدفق الأقصى بإضافة قيود منفصلة. ينص القيد المنفصل السلبي على أنه لا يمكن لزوج معين من الحواف أن يحمل تدفقًا غير صفري في نفس الوقت. أما القيد المنفصل الإيجابي فيشترط أنه في زوج معين من الحواف، يجب أن يكون لدى واحدة على الأقل تدفق غير صفري. عند وجود قيود سلبية، تصبح المشكلة صعبة للغاية حتى في الشبكات البسيطة. أما مع القيود الإيجابية، فتكون المشكلة قابلة للحل في زمن متعدد الحدود إذا سُمح بقيم تدفق كسرية، ولكنها قد تصبح من المسائل NP-صعبة عندما يجب أن تكون قيم التدفق أعدادًا صحيحة.

ومن ناحية أخرى، 1. في مشكلة التدفق بأقل تكلفة ، تُضاف إلى كل حافة (u, v) معامل تكلفة uv إلى جانب سعتها. وإذا كان التدفق عبر هذه الحافة هو f uv، فإن التكلفة الإجمالية تُحسب بضرب uv f uv في f uv. المطلوب هو إيجاد تدفق بحجم معين d يحقق أقل تكلفة ممكنة. وفي أغلب صور هذه المسألة، يمكن أن تكون معاملات التكلفة إما موجبة أو سالبة. توجد الكثير من الخوارزميات التي تعمل في زمن متعدد الحدود لحل هذه المشكلة.

تنص نظرية التدفق التكاملي على أن

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

من جانب آخر، إذا كان لكل حافة في شبكة التدفق سعة متكاملة، فسيكون هناك تدفق أقصى متكامل.

طلب

مشكلة التدفق الأقصى متعدد المصادر ومتعدد الأحواض

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

مشكلة الإغلاق

وفي هذا الصدد، في الرسم البياني الموجه، الإغلاق هو مجموعة من الرؤوس C بحيث لا توجد أي حافة تبدأ من رأس في C وتنتهي في رأس خارج C. ومشكلة الإغلاق هي مهمة إيجاد إغلاق ذي أقصى وزن أو أدنى وزن في رسم بياني موجه تكون رؤوسه مُوزنة. يمكن حل هذه المشكلة في زمن متعدد الحدود عن طريق اختزالها إلى مشكلة التدفق الأقصى.

تطبيقات العالم الحقيقي

الخوارزميات

نظرية التدفق التكاملي

من جهة ثانية، الجدول التالي يسرد الخوارزميات المستعملة لحل مشكلة التدفق الأقصى. في هذا الجدول، يمثل ∣V∣ عدد الرؤوس ويمثل ∣E∣ عدد الحواف في الشبكة. أما القيمة U فتشير إلى أكبر سعة حافة بعد تحويل جميع السعات إلى قيم صحيحة (إذا كانت الشبكة تتضمن سعات غير نسبية، فقد تكون قيمة U لانهائية).

لمزيد من الخوارزميات، راجع .

تقسيم الصورة

وفي هذا السياق، في كتابهما، يقدم كلاينبيرج وتاردوس خوارزمية لمعالجة مشكلة تقسيم الصور. تحديدًا، يقترحون خوارزمية لتحديد مناطق الخلفية والمقدمة في الصورة. وبشكل أكثر دقة، تستقبل الخوارزمية خريطة من البيانات الثنائية (بتات) كمدخل، ويتم تمثيل هذه البيانات على النحو التالي: aᵢ ≥ 0 يمثل احتمالية انتماء البكسل i إلى منطقة المقدمة، و bᵢ ≥ 0 يمثل احتمالية انتماء البكسل i إلى منطقة الخلفية، بينما تمثل pᵢⱼ قيمة العقوبة المترتبة على وضع بكسلين متجاورين i و j في منطقتين مختلفتين (أحدهما في المقدمة والآخر في الخلفية). الهدف من الخوارزمية هو إيجاد تقسيم (A, B) لمجموعة البكسلات يحقق أقصى قيمة للمقدار التالي:

ومن جهة أخرى، في الواقع، بالنسبة لكل بكسل في المنطقة A (التي نعتبرها المقدمة)، نحصل على قيمة aᵢ. وبالمثل، بالنسبة لجميع البكسلات في المنطقة B (التي نعتبرها الخلفية)، نحصل على قيمة bᵢ. أما على الحدود بين أي بكسلين متجاورين i و j، فإننا نخسر قيمة pᵢⱼ. وهذا يعادل تقليل الكمية التالية:

تاريخ

وفي هذا الصدد، 1955، ابتكر ليستر ر. فورد الابن وديلبرت ر. فولكرسون أول خوارزمية معروفة، وهي خوارزمية فورد-فولكرسون . في ورقتهم البحثية لعام 1955، كتب فورد وفولكرسون أن مشكلة هاريس وروس صيغت على النحو التالي تخيل شبكة سكك حديدية تصل بين مدينتين مرورًا بعدة مدن أخرى، حيث يمثل رقم محدد لسعة كل وصلة في هذه الشبكة. وبافتراض استقرار الظروف التشغيلية، المطلوب هو إيجاد أقصى قدر من التدفق (مثل عدد القطارات أو حجم البضائع) يمكن نقله من مدينة معينة إلى مدينة أخرى. في كتابهما الذي يحمل عنوان "التدفقات في الشبكات" والذي نُشر عام 1962، كتب فورد وفولكرسون ما يلي:عُرضت هذه الفكرة على المؤلفين في ربيع عام 1955 من قِبل تي إي هاريس، الذي قام، بالاشتراك مع الجنرال المتقاعد إف إس روس، بصياغة نموذج مبسط لتدفق حركة السكك الحديدية، وحدد هذه المشكلة تحديدًا باعتبارها القضية الأساسية التي يطرحها النموذج [11].حيث يشير [11] إلى التقرير السري لعام 1955 " تعتمد طريقة تقييم قدرات شبكات السكك الحديدية على قياس وتحليل أقصى إمكانية لاستيعاب حركة القطارات مع الحفاظ على مستوى خدمة مقبول، وذلك بفحص أنواع القدرة (نظرية، عملية، مستعملة، متبقية) والعوامل المؤثرة (البنية التحتية، التشغيل، الأداء)، وتطبيق أدوات تحليلية ومحاكاة لدعم التخطيط والتحسين واتخاذ القرارات الاستراتيجية. "بقلم هاريس وروس (انظر ص. 5).

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

وعلى صعيد آخر، على مدار السنوات، تم اكتشاف الكثير من الحلول المحسنة لمسألة التدفق الأقصى، وأهمها خوارزمية أقصر مسار متزايد التي توصل إليها كل من إدموندز وكارب ودينيتز بشكل مستقل، إلى جانب خوارزمية التدفق الحاجز التي ابتكرها دينيتز.

وفي هذا الصدد، ، تم اكتشاف الكثير من الحلول المحسنة لمسألة التدفق الأقصى، وأهمها خوارزمية أقصر مسار متزايد التي توصل إليها كل من إدموندز وكارب ودينيتز بشكل مستقل، فضلًا عن خوارزمية التدفق الحاجز التي ابتكرها دينيتز.؛ وخوارزمية الدفع وإعادة التسمية لجولدبيرج وتارجان ؛ وخوارزمية التدفق الحاجز الثنائي لجولدبيرج وراو. تجد خوارزميات شيرمان وكيلنر ولي وأوريكيا وسيدفورد، على التوالي، تدفقًا أقصى مثاليًا على وجه التقريب ولكنها تعمل فقط في الرسوم البيانية غير الموجهة.

وفي السياق ذاته، في سنة 2013، نشر جيمس ب. أورلين ورقة بحثية تصف خوارزمية تعمل في زمن قدره .

وفي هذا السياق، طُرحت مشكلة التدفق الأقصى للمرة الأولى في عام 1954 على يد TE Harris و FS Ross، وذلك كنموذج مبسط لتدفق حركة المرور على شبكة السكك الحديدية السوفيتية .

مطابقة ثنائية الأجزاء لأقصى عدد أساسي

إضافةً إلى ذلك، ونتيجة لذلك، لا يوجد أي رأس في C لديه حافتان واردتان أو حافتان صادرتان، مما يعني أن جميع المسارات المكونة للغطاء C منفصلة عن بعضها البعض من حيث الرؤوس.

الحد الأدنى لتغطية المسار في الرسم البياني اللادوري الموجه

وفي هذا الصدد، كل رأس في يمكن أن تكون غير متطابقة في ، وفي هذه الحالة لا توجد حواف متبقية في ؛ أو يمكن مطابقتها ، وفي هذه الحالة يكون هناك حافة واحدة فقط متبقية في . في كلتا الحالتين، لا يترك أكثر من حافة واحدة أي رأس في .

  • يحتوي على الحواف في موجه من ل .
  • لكل واحد و لكل واحد .
  • لكل واحد (انظر الشكل 4.3.1).

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

كذلك، وبالمثل لكل رأس في - إذا تم التطابق، هناك حافة واردة واحدة في في ؛ خلاف ذلك ليس له حواف واردة في .

وفي السياق ذاته، لنفترض أننا توصلنا إلى تطابق M في G'، ونقوم بإنشاء الغطاء C بناءً عليه. من البديهي أنه إذا كان الرأسان و متطابقين في M، فإن الحافة (u, v) ستكون موجودة في C. من الواضح أن عدد الحواف في C سيكون m. لتوضيح أن C منفصل من حيث الرؤوس، تأمل ما يلي:

في هذا الإطار، وبالتالي، يمكننا أن نوضح أن الرسم البياني G' يمتلك مطابقة M بحجم m إذا وفقط إذا كان الرسم البياني G يحتوي على غطاء مسار منفصل من حيث الرؤوس C يتكون من m حافة و مسارًا، حيث n هو عدد الرؤوس في G. ونتيجة لذلك، يمكن حل المشكلة عن طريق إيجاد الحد الأقصى لحجم المطابقة في G' بدلاً من G.

وعلى صعيد آخر، بالنظر إلى الرسم البياني غير الدوري الموجه ، فإن الهدف هو إيجاد الحد الأدنى لعدد المسارات المنفصلة عن الرؤوس التي تغطي جميع الرؤوس في V. يمكننا إنشاء رسم بياني ثنائي الأجزاء , من G، حيث:

في هذا الإطار، لإثبات أن الغطاء C له حجم ، نبدأ بغطاء فارغ ونقوم ببنائه تدريجيًا. لإضافة رأس u إلى الغطاء، لدينا خياران: إما إضافته إلى مسار موجود، أو إنشاء مسار جديد بطول صفر يبدأ من هذا الرأس. ينطبق الخيار الأول عندما توجد حافة ويبدأ أحد المسارات في الغطاء عند v، أو عندما توجد حافة وينتهي أحد المسارات عند v. أما الخيار الثاني (إنشاء مسار جديد) فهو ممكن دائمًا. في الحالة الأولى (إضافة إلى مسار موجود)، يزداد العدد الكلي للحواف في الغطاء بمقدار 1 بينما يظل عدد المسارات ثابتًا؛ وفي الحالة الثانية (إنشاء مسار جديد)، يزداد عدد المسارات بمقدار 1 بينما يظل عدد الحواف ثابتًا. من الواضح الآن أنه بعد تغطية جميع n رؤوس الرسم البياني G، سيكون مجموع عدد المسارات والحواف في الغطاء مساويًا لـ n. لذلك، إذا كان عدد الحواف في الغطاء هو m، فإن عدد المسارات سيكون .

من جانب آخر، عندئذٍ، تكون قيمة التدفق الأقصى في الشبكة N مساوية لحجم المطابقة القصوى في الرسم البياني G. ويمكن تحديد المطابقة ذات أكبر عدد من الحواف عن طريق اختيار تلك الحواف التي يحمل تدفقها قيمة 1 في التدفق الأقصى الذي تكون قيمه عددًا صحيحًا.

.

إقصاء البيسبول

في هذا الإطار، في هذه الطريقة، يُدعى أن الطاقم k لا يُستبعد من الجدول الزمني إذا وفقط إذا وُجدت قيمة تدفق بحجم r(S - {k}) في الشبكة G. وقد تم إثبات أن قيمة هذا التدفق، كما ورد في المقالة المذكورة، هي قيمة التدفق الأقصى من المصدر s إلى المصب t.

.

من جهة ثانية، لنفترض أن G = (V, E) هي شبكة، حيث يمثل s المصدر و t المصب. نضيف عقدة "لعبة ij" لكل مباراة بين الفريقين i و j (حيث i < j) إلى V، ونربط s بكل عقدة لعبة {i, j} بحافة ذات سعة rᵢⱼ تمثل عدد مرات اللعب بينهما. نضيف كذلك عقدة "فريق" لكل فريق مشارك، ونربط كل عقدة لعبة {i, j} بعقدتي الفريق i و j لضمان فوز أحدهما في كل مباراة. لا يلزم تقييد قيمة التدفق على هذه الحواف الرابطة بين عقد اللعبة وعقد الفريق. أخيرًا، ننشئ حوافًا من عقدة الفريق i إلى عقدة المصب t ونضبط سعتها على لمنع الفريق i من الفوز بأكثر من مرة. ليكن S مجموعة جميع الفرق المشاركة في الدوري، وليكن...

وفي السياق ذاته، في سياق مشكلة الإقصاء في دوري لعبة البيسبول، يتنافس n فريقًا. في مرحلة معينة من الموسم، يمثل wᵢ عدد مرات فوز الفريق i، و rᵢ عدد المباريات المتبقية للفريق i، بينما يمثل rᵢⱼ عدد المباريات المتبقية بين الفريقين i و j. يُعتبر الفريق مُقصًى إذا لم يعد لديه أي فرصة رياضية لإنهاء الموسم في الصدارة. وتتمثل مهمة مشكلة إقصاء البيسبول في تحديد الفرق التي تم إقصاؤها عند أي نقطة خلال الموسم. اقترح شوارتز طريقة لتبسيط هذه المشكلة وتحويلها إلى مشكلة تدفق أقصى في شبكة. تتضمن هذه الطريقة إنشاء شبكة خاصة لتحديد ما إذا كان سيتم استبعاد فريق معين k.

الحد الأقصى للتدفق مع قدرات القمة

في هذا الإطار، بالنظر إلى رسم بياني موجه ورأسين محددين s و t، فإن الهدف هو إيجاد الحد الأقصى لعدد المسارات المنفصلة من s إلى t. لهذه المسألة عدة صور:

كذلك، 1. أولاً، يجب أن تكون المسارات منفصلة من حيث الحواف. يمكن تحويل هذه المشكلة إلى مشكلة تدفق أقصى عن طريق إنشاء شبكة من الرسم البياني G، مع اعتبار s و t هما المصدر والمصب في N على التوالي، وتعيين سعة قدرها 1 لكل حافة. في هذه الشبكة، يكون الحد الأقصى للتدفق هو k إذا كان هناك k مسارًا منفصلاً من حيث الحواف.

وفي هذا الصدد، 2. ثانيًا، يجب أن تكون المسارات مستقلة، أي لا تشترك في أي رؤوس فيما بينها (باستثناء الرأسين s و t). يمكننا بناء شبكة من الرسم البياني G مع إضافة سعات للرؤوس، حيث تكون سعة كل رأس وكل حافة مساوية لـ 1. في هذه الحالة، تكون قيمة التدفق الأقصى مساوية لأكبر عدد من المسارات المستقلة من s إلى t.

الحد الأقصى لعدد المسارات من s إلى t

من جانب آخر، 3. فضلًا عن اشتراط فصل المسارات من حيث الحواف و/أو الرؤوس، قد يكون للمسارات كذلك قيد على طولها: حيث نحسب فقط المسارات التي يكون طولها k بالضبط، أو على الأكثر k. أغلب المتغيرات لهذه المشكلة تصنف ضمن المسائل NP-كاملة، باستثناء الحالات التي تكون فيها قيمة k صغيرة.

كذلك، أولا، كل يتم استبداله بـ و ، أين متصل بواسطة حواف متوجهة إلى و متصل بالحواف الخارجة من ،

ثانيا بتعيين السعة إلى الحافة المتصلة و (انظر الشكل 4.4.1).

من جانب آخر، لنفترض أن لدينا شبكة . فضلًا عن سعة كل حافة، نفترض كذلك وجود سعة لكل عقدة، أي دالة تعيين ، بحيث يجب أن يفي التدفق ليس فقط بقيد السعة التقليدي وقانون حفظ التدفق، بل كذلك بقيد سعة الرأس (أو العقدة).

كذلك، في هذا التمثيل الموسع للشبكة، يُلغى القيد المفروض على سعة الرأس، مما يتيح لنا حل المشكلة باستخدام تقنيات التدفق الأقصى التقليدية.

من جانب آخر، بعبارة أخرى، يجب ألا تتجاوز كمية التدفق العابر لأي رأس في الشبكة سعته المحددة. ولإيجاد الحد الأقصى للتدفق عبر الشبكة N، يمكننا تحويل هذه المسألة إلى مشكلة تدفق أقصى بالمعنى التقليدي من خلال توسيع الشبكة N.

تعريف

من جانب آخر، قيد القدرة . لا يمكن لتدفق الحافة أن يتجاوز سعتها، بمعنى آخر: للجميع

من جانب آخر، تعريف: تُعنى مشكلة التدفق الأقصى بإيجاد طريقة لتوجيه أكبر قدر ممكن من التدفق من نقطة المصدر إلى نقطة المصب في الشبكة. بعبارة أخرى، الهدف هو تحديد التدفق الأمثل الذي يحقق أعلى قيمة ممكنة.

ملاحظة . التدفقات متماثلة بشكل غير متساوٍ: للجميع

تعريف. التدفق عبارة عن خريطة الذي يلبي الشروط التالية:

ومن ناحية أخرى، تعريف: قيمة التدفق هي إجمالي كمية التدفق الصافي التي تنتقل من المصدر إلى المصب. وبالنسبة لتدفق معين ، تُعطى قيمته بالعلاقة التالية:

علاوةً على ذلك، تعريف: سعة الحافة هي الحد الأعلى لكمية التدفق التي يمكن أن تعبر من خلال تلك الحافة. ويُعبر عنها رياضيًا بدالة c تربط كل حافة E بقيمة حقيقية موجبة أو صفرية من المجموعة R

  • أولاً نقوم بإنشاء بعض التدوينات:
  • يترك كن شبكة مع كونها المصدر والمصرف على التوالى.
  • لو هي دالة على حواف ثم قيمتها على يتم الإشارة إليه بواسطة أو

في هذا الإطار، تجدر الإشارة إلى أنه قد توجد حلول متعددة لمشكلة التدفق الأقصى. وعندما يُسمح لقيم التدفق بأن تكون أعدادًا حقيقية أو حتى نسبية اختيارية (بدلاً من اقتصارها على الأعداد الصحيحة)، فإننا إما أن نجد حلاً أقصى واحدًا بالضبط، أو عددًا لا نهائيًا من الحلول. ويرجع ذلك إلى وجود عدد لا نهائي من التركيبات الخطية للتدفقات القصوى الأساسية. بمعنى آخر، إذا كان التدفق الأقصى الأول يرسل x وحدة تدفق عبر الحافة u، وكان تدفق أقصى آخر يرسل y وحدة تدفق عبر نفس الحافة u (حيث y > x)، فإنه لكل قيمة Δ تقع في النطاق ، يمكننا إرسال x + Δ وحدة عبر الحافة u وتعديل التدفق على الحواف الأخرى بحسب ذلك، لنحصل على تدفق أقصى آخر. إذا كانت قيم التدفق يمكن أن تأخذ أي قيمة حقيقية أو نسبية، فسيكون هناك عدد لا نهائي من قيم Δ الممكنة لكل زوج من القيم x و y.

علاوةً على ذلك، حفظ التدفقات. يجب أن يساوي مجموع التدفقات الداخلة إلى عقدة ما مجموع التدفقات الخارجة من تلك العقدة، باستثناء المصدر والمصرف. أو:

مشكلة التداول والطلب

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

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

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

.

ومن جهة أخرى، أضف عقدة الحوض وأضف الحواف من جميع القرى إلى بسعة حيث هو معدل الطلب للقرية .

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

وفي هذا الصدد، ليكن G = (V, E) هذه الشبكة المُنشأة حديثًا. عندئذٍ، يكون هناك تداول يلبي الطلب إذا وفقط إذا تحققت الشروط التالية:

لأن

ومن ناحية أخرى، الآن، نشرع في إنشاء شبكة تكون عقدها هي البكسلات، فضلًا عن عقدتي المصدر والمصب، كما هو موضح في الشكل على اليمين. ننشئ حافة موجهة من المصدر إلى البكسل i بوزن قدره aᵢ. وبالمثل، ننشئ حافة موجهة من البكسل i إلى المصب بوزن قدره bᵢ. كما ننشئ حافة غير موجهة بين أي بكسلين متجاورين i و j بوزن قدره pᵢⱼ. الآن، يبقى علينا حساب الحد الأدنى للقطع في هذه الشبكة (أو ما يكافئه من تدفق أقصى). ويوضح الشكل الأخير الحد الأدنى لهذا القطع.

جدولة خطوط الطيران

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

ومن ناحية أخرى، في الطريقة المذكورة سابقًا، تم إثبات والتأكيد على أن إيجاد قيمة تدفق k في الشبكة G بين المصدر s والمصب t يعادل إيجاد جدول زمني قابل للتطبيق لمجموعة الرحلات الجوية F باستخدام k طاقم كحد أقصى. .

ومن ناحية أخرى، حافة بسعة [0، 1] بين كل d i و s j ، إذا كان من الممكن الوصول إلى المصدر s j في فترة زمنية معقولة وتكلفة من وجهة الرحلة i .

حافة بسعة [0، ∞ ] بين s و t .

علاوةً على ذلك، لنفترض أن G = (V, E) هي شبكة، حيث يمثل s و t عقدتي المصدر والمصب الرئيسيتين في V. لكل رحلة i، ذات مصدر ووجهة محددتين، نضيف عقدتين جديدتين إلى V: العقدة sᵢ لتمثيل مصدر الرحلة i، والعقدة dᵢ لتمثيل وجهة الرحلة i. علاوةً على ذلك، نضيف الحواف التالية إلى E:

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

  • حافة بسعة [0، 1] بين s وكل s i .
  • حافة بسعة [0، 1] بين كل d i و t .
  • حافة بسعة [1، 1] بين كل زوج من s i و d i .

وعلى صعيد آخر، توجد صيغة أخرى لمشكلة جدولة الخطوط الجوية تتمثل في إيجاد الحد الأدنى لعدد أفراد الطاقم اللازمين لتنفيذ جميع الرحلات الجوية المقررة. لحل هذه المشكلة، يُنشأ رسم بياني ثنائي الأجزاء G' = (A ∪ B, E)، حيث تُمثل كل رحلة جوية بنسخة في المجموعة A ونسخة أخرى في المجموعة B. إذا كان من الممكن لنفس الطاقم القيام بالرحلة j بعد الرحلة i، فإنه يتم إنشاء وصلة بين i∈A و j∈B. يؤدي إيجاد تطابق في G' إلى إنشاء جدول زمني لمجموعة من الرحلات F. ومن الواضح أن إيجاد التطابق الثنائي الأقصى (من حيث عدد الحواف) في هذا الرسم البياني ينتج عنه جدول زمني لشركة الطيران بأقل عدد ممكن من أفراد الطاقم. وكما ذُكر في قسم التطبيقات من هذه المقالة، فإن إيجاد التطابق الثنائي ذي العدد الأساسي الأقصى هو تطبيق مباشر لمشكلة التدفق الأقصى.

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.