دراسة تحليلية للبحث في شجرة التفريعات في طريقة التفريع والتحديد (B and B)‎: دراسة نظرية للمشاكل الخطية من نوع (2×m)‎

Abstract AR

تستخدم البرمجة الخطية في حل المشاكل التي تكون العلاقة بين متغيراتها (Decision Variables) علاقة خطية، وعادة ما تحتوي قيمها عند الحل على كسور (Non-int)، وفي العديد من الحالات يكون هذا الحل غير منطقي من الناحية الاقتصادية والفيزيائية، عندما تكون متغيرات المشكلة غير قابلة للتجزئة على أرض الواقع، فمثلا عندما تكون المشكلة إيجاد التوليفة المثلى لإنتاج نوعين من السفن، فإنه من غير المقبول أن يكون الحل لهذه المشكلة هو إنتاج (5.48) سفينة حجم صغيرة وإنتاج (3.67) سفينة حجم كبير.

الجدير بالذكر هنا هو أنه يوجد عدة طرق لإيجاد الحل الأمثل الصحيح (Int) وهو حل لا يحتوي على كسر، ومن أهم هذه الطرق طريقة التفريع والتحديد (Branch and Bound Method، تبدأ الية عملها من الحل الأمثل (Non-int)، وذلك بتفريع المشكلة إلى مشكلتين فرعيتين باستخدام قيود إضافية، وهو يعني فصل منطقة الحلول الممكنة لمنطقتين مشكلتين فرعيتين، ومن تم إيجاد الحل الأمثل لهاتين المشكلتين كلا على حدة، وبنفس الطريقة يتم تفريع المشاكل الفرعية وإيجاد حلولها أيضا.

ويتم التوقف عن سلسلة التفريعات في حالة عدم وجود حل للمشكلة الفرعية أو عندما تكون قيم حلها قيم صحيحة (Int Solution).

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