300 أمثلة

مشكلة التدفق القصوى

Maximum Flow Problem

صياغة النموذج | المحاولة و الخطأ | حل النموذج



استخدم الحل في اكسل لتجد ال أقصى تدفق من العقدة S إلى العقدة T في شبكة موجهة. تسمى النقاط في الشبكة العقد (S و A و B و C و D و E و T). تسمى الخطوط في الشبكة الأقواس (SA ، SB ، SC ، AC ، إلخ).

صياغة النموذج

النموذج الذي سنقوم بحله يبدو كما يلي في Excel.





مشكلة التدفق القصوى في Excel

1. لصياغة هذا مشكلة التدفق الأقصى ، أجب على الأسئلة الثلاثة التالية.



أ. ما هي القرارات التي يجب اتخاذها؟ بالنسبة لهذه المشكلة ، نحتاج إلى Excel للعثور على التدفق على كل قوس. على سبيل المثال ، إذا كان التدفق على SB هو 2 ، فإن الخلية D5 تساوي 2.

ب. ما هي القيود على هذه القرارات؟ يجب أن يكون صافي التدفق (التدفق الخارج - التدفق للداخل) للعقدة A و B و C و D و E مساوياً لـ 0. بمعنى آخر ، التدفق الخارج = التدفق للداخل. أيضا ، كل قوس له سعة ثابتة. يجب أن يكون التدفق على كل قوس أقل من هذه السعة.

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

2. لتسهيل فهم النموذج ، قم بإنشاء ما يلي النطاقات المسماة .

اسم النطاق الخلايا
من عند B4: B15
إلى C4: C15
تدفق D4: D15
الاهلية F4: F15
العرض والطلب K5:K9
أقصى تدفق D17

3. أدخل الوظائف التالية.

إدراج الوظائف

شرح: ملف سوميف وظائف حساب صافي التدفق لكل عقدة. بالنسبة للعقدة A ، تجمع دالة SUMIF الأولى القيم الموجودة في عمود التدفق بالحرف 'A' في العمود 'من' (التدفق الخارج). تجمع دالة SUMIF الثانية القيم الموجودة في عمود التدفق بالحرف 'A' في العمود 'إلى' (التدفق للداخل). يساوي الحد الأقصى للتدفق القيمة الموجودة في الخلية I4 ، وهي التدفق الخارج من العقدة S. نظرًا لأن صافي التدفق للعقدة A و B و C و D و E يساوي 0 ، فإن التدفق خارج العقدة S سيساوي التدفق الداخل للعقدة T.

المحاولة و الخطأ

باستخدام هذه الصيغة ، يصبح من السهل تحليل أي حل تجريبي.

1. على سبيل المثال ، مسار SADT بتدفق 2. مسار SCT بتدفق 4. مسار SBET بتدفق 2. هذه المسارات تعطي تدفقًا إجماليًا قدره 8.

حل تجريبي

التفوق في كيفية إنشاء القائمة المنسدلة

ليس من الضروري استخدام التجربة والخطأ. سوف نصف بعد ذلك كيف برنامج Excel Solver يمكن استخدامها لإيجاد الحل الأمثل بسرعة.

حل النموذج

للعثور على الحل الأمثل ، قم بتنفيذ الخطوات التالية.

1. في علامة التبويب بيانات ، في المجموعة تحليل ، انقر فوق Solver.

انقر فوق Solver

ملاحظة: ألا يمكنك العثور على زر Solver؟ انقر هنا لتحميل ملف الوظيفة الإضافية Solver .

أدخل معلمات الحل (اقرأ). يجب أن تكون النتيجة متسقة مع الصورة أدناه.

معلمات Solver

لديك خيار كتابة أسماء النطاقات أو النقر فوق الخلايا في جدول البيانات.

2. أدخل MaximumFlow للهدف.

3. انقر فوق Max.

4. أدخل التدفق للخلايا المتغيرة المتغيرة.

5. انقر فوق إضافة لإدخال القيد التالي.

قيود صافي التدفق

6. انقر فوق إضافة لإدخال القيد التالي.

قيود القدرات

7. حدد 'جعل المتغيرات غير المقيدة غير سلبية' وحدد 'Simplex LP'.

8. أخيرًا ، انقر فوق حل.

نتيجة:

نتائج Solver

الحل الأمثل:

نتيجة مشكلة التدفق القصوى

الخلاصة: مسار SADT بتدفق 2. المسار SCT بتدفق 4. مسار SBET بتدفق 2. المسار SCET بتدفق 2. المسار SACET بتدفق 1. المسار SACDT بتدفق 1. تعطي هذه المسارات أقصى تدفق يبلغ 12.

اكتمل 5/7! تعرف على المزيد حول الحل>
انتقل إلى الفصل التالي: حزمة أدوات التحليل



^