Network model (operations research) — النماذج الشبكية
النماذج الشبكية (في بحوث العمليات؛ بالإنجليزية: Network models) هي فئة من النماذج الرياضية التي تمثل مسألة ما في شكل رسم بياني (شبكة)، حيث تمثل الرؤوس (العُقد) الكيانات أو الحالات، وتمثل الأضلاع (الأقواس) الروابط أو العمليات بينها[1]. في سياق الأمثَلة (Optimization)، غالبًا ما يُقصد بالشبكة رسم بياني موجّه، والذي يُطلق عليه مباشرةً في التحليل العملياتي اسم "شبكة"؛ وتُسمى رؤوس هذه الشبكة بالعُقد، وأضلاعها بالأقواس[2].
تُعد النماذج الشبكية أداة قوية لتحليل وأمثَلة النظم المعقدة في مجالات مثل الخدمات اللوجستية، والاتصالات، وإدارة المشاريع، والتمويل. تكمن قوتها في المستوى العالي من التجريد: يمكن للعقدة أن تمثل مدينة، أو موجّه حاسوبي (router)، أو مرحلة في مشروع، بينما يمكن للقوس أن يمثل طريقًا، أو قناة اتصال، أو عملية تقنية.
التعريف والمصطلحات
تستند النماذج الشبكية إلى نظرية المخططات (Graph theory). المفاهيم الرئيسية هي:
- شبكة التدفق (بالإنجليزية: flow network): هي رسم بياني موجّه لكل ضلع فيه سعة (capacity) وتدفق (flow). يتم تحديد رأسين خاصين في الرسم البياني: المصدر (source) الذي يخرج منه التدفق، والمصب (sink) الذي يدخل إليه[1].
- قانون حفظ التدفق: لأي رأس ليس مصدرًا أو مصبًا، يجب أن يكون إجمالي التدفق الداخل مساويًا لإجمالي التدفق الخارج. هذا الشرط هو نظير متقطع لقوانين الحفظ الفيزيائية[3].
- التخطيط الشبكي: نموذج يمثل المشروع كمجموعة من العمليات المترابطة (الأقواس) والأحداث (العقد). تكون هذه الشبكات عبارة عن رسوم بيانية موجّهة غير دورية (acyclic)، مما يعكس ترتيب تنفيذ الأعمال[4].
الخصائص والنظريات الرئيسية
تمتلك النماذج الشبكية عددًا من الخصائص الخاصة التي تسمح بتطبيق خوارزميات عالية الكفاءة لحلها.
- سلامة الحلول (Integer solutions): العديد من مسائل الأمثَلة الشبكية (مثل مسائل التدفق الأقصى أو المسار الأقصر) تتمتع بخاصية الوحدوية الكلية (total unimodularity) لمصفوفة القيود. بفضل هذا، إذا كانت معلمات المسألة (السعات، الأطوال) أعدادًا صحيحة، فإن الحل الأمثل الذي يتم العثور عليه باستخدام طرق البرمجة الخطية سيكون أيضًا عددًا صحيحًا دون الحاجة إلى فرض قيود إضافية[5][6].
- نظرية التدفق الأقصى والقطع الأدنى: نتيجة محورية في نظرية التدفقات. تنص على أن القيمة القصوى للتدفق من المصدر إلى المصب تساوي السعة الدنيا بين جميع القواطع (cuts) التي تفصل المصدر عن المصب. تضع هذه النظرية معيارًا لأمثلية التدفق وتشكل أساسًا للعديد من الخوارزميات[6][7].
- مبدأ الأمثلية للمسارات الأقصر: إذا كان المسار من النقطة أ إلى النقطة ج هو الأقصر، فإن أي جزء منه (على سبيل المثال، من نقطة وسيطة ب إلى ج) هو أيضًا المسار الأقصر بين الرؤوس المقابلة. هذه الخاصية، التي تكمن في أساس البرمجة الديناميكية، تضمن صحة خوارزميات مثل خوارزمية ديكسترا[8].
- خصائص الشجرة الممتدة الدنيا (MST):
- خاصية القطع: لأي قطع في الرسم البياني، فإن الضلع ذا الوزن الأدنى الذي يعبر القطع ينتمي إلى شجرة ممتدة دنيا واحدة على الأقل.
- خاصية الدورة: في أي دورة في الرسم البياني، فإن الضلع ذا الوزن الأقصى لا ينتمي إلى أي شجرة ممتدة دنيا.
تستند صحة الخوارزميات "الجشعة" (greedy) مثل خوارزمية بريم وخوارزمية كروسكال إلى هذه الخصائص[9].
مسائل الأمثَلة الشبكية الرئيسية
- مسألة المسار الأقصر: إيجاد المسار ذي الطول (الوزن) الإجمالي الأدنى بين عقدتين محددتين. تُحل باستخدام خوارزمية ديكسترا (للأوزان غير السالبة) أو خوارزمية بلمان-فورد (للأوزان الاعتباطية)[8].
- مسألة التدفق الأقصى: تحديد أقصى تدفق ممكن من المصدر إلى المصب في ظل سعات الأقواس المحددة. الطريقة الكلاسيكية للحل هي خوارزمية فورد-فولكرسون[6].
- مسألة الشجرة الممتدة الدنيا: إيجاد رسم بياني جزئي يربط جميع رؤوس الشبكة وله أدنى تكلفة إجمالية للأضلاع.
- طريقة المسار الحرج (CPM): في نماذج التخطيط الشبكي، يتم تحديد أطول تسلسل من الأعمال، والذي يحدد أقل وقت ممكن لإنجاز المشروع بأكمله. الأعمال الواقعة على هذا المسار ليس لها أي هامش زمني (float or slack)[10].
أمثلة
- المسار الأقصر: البحث عن المسار الأمثل بواسطة نظام ملاحة بين نقطتين على خريطة مدينة، حيث تمثل المدن العقد، والطرق هي الأقواس ذات الأوزان التي تساوي الطول أو وقت السفر.
- التدفق الأقصى: تحديد السعة القصوى لشبكة أنابيب، حيث تكون محطات الضخ هي العقد، والأنابيب هي الأقواس ذات السعات المحدودة.
- الشجرة الممتدة الدنيا: تصميم شبكة اتصالات (على سبيل المثال، تمديد كابل ألياف بصرية) لربط عدة مدن بأقل طول إجمالي للكابل.
- المسار الحرج: في مشروع بناء منزل، حيث يكون للأعمال (وضع الأساس، بناء الجدران، تركيب السقف) مدد زمنية محددة وتبعيات تقنية، يحدد المسار الحرج الحد الأدنى من الوقت اللازم لإتمام البناء. أي تأخير في عمل على هذا المسار سيؤدي إلى تأخير المشروع بأكمله[10].
انظر أيضًا
- بحوث العمليات
- نظرية المخططات
- مسألة النقل
- طريقة المسار الحرج
- PERT
المراجع
- ↑ 1.0 1.1 "Flow network". Wikipedia. [١]
- ↑ "Тема 10: Сетевые модели". Учебное пособие. Гомель: БелГУТ. [٢]
- ↑ "Transport network". Wikipedia. [٣]
- ↑ "Network planning". Wikipedia. [٤]
- ↑ Bradley S. P., Hax A. C., Magnanti T. L. (1977). Applied Mathematical Programming. Addison-Wesley. Ch.8: Network Models. [٥]
- ↑ 6.0 6.1 6.2 "Maximum flow problem". Wikipedia. [٦]
- ↑ Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: Paths, Flows, and VLSI-Layout. Springer. [٧]
- ↑ 8.0 8.1 "Shortest path problem". Wikipedia. [٨]
- ↑ "Minimum spanning tree". Wikipedia. [٩]
- ↑ 10.0 10.1 "Critical path method". Wikipedia. [١٠]