دراسة تحليلية للبحث في شجرة التفريعات في طريقة التفريع والتحديد (B&B)

دراسة نظرية للمشاكل الخطية من نوع (2m×)

الملخص

تستخدم البرمجة الخطية في حل المشاكل التي تكون العلاقة بين متغيراتها (Decision Variables) علاقة خطية، وعـادةً ما تحـتوي قيـمها عند الحــل على كسـور (Non-int)، وفي العديد من الحالات يكون هذا الحل غير منطقي من الناحية الاقتصادية والفيزيائية، عندما تكون متغيرات المشكلة غير قابلة للتجزئة على أرض الواقع، فمثلاً عندما تكون المشكلة إيجاد التوليفة المثلى لإنتاج نوعين من السفن، فإنه من غير المقبول أن يكون الحل لهذه المشكلة هو إنتاج (5.48) سفينة حجم صغيرة وإنتاج (3.67) سفينة حجم كبير. الجدير بالذكر هنا هو أنه يوجد عدة طرق لإيجاد الحل الأمثل الصحيح (Int) وهو حل لا يحتوي على كسر، ومن أهم هذه الطرق طـريقة التفـريع والتحـديد (Branch and Bound Method)، تبـدأ آلية عملها من الحــل الأمثـــل (Non-int)، وذلك بتفريع المشكلة إلى مشكلتين فرعيتين باستخدام قيود إضافية، وهو يعني فصل منطقة الحلول الممكنة لمنطقتين (مشكلتين فرعيتين)، ومن تم إيجاد الحل الأمثل لهاتين المشكلتين كلاً على حدة، وبنفس الطريقة يتم تفريع المشاكل الفرعية وإيجاد حلولها أيضاً. ويتم التوقف عن سلسلة التفريعات في حالة عـدم وجـود حــل للمشكلة الفرعيـــة أو عندما تكون قيم حلها قيم صحيحة (Int Solution). إن عدد المشاكل الفرعية الناتجة من عملية التفريع تزداد بشكل كبير بزيادة عدد متغيراتها وعدد قيودها، عمدت هذه الورقـــة لدراسة سلسلة التفريعات والعوامل المؤثرة في نواتج الحل للمشاكل الفرعية مع تقديم التحليلات المطلوبة وتتبعها بيانياَ، للوصول لمعايير (Criterions) يمكن من خلالها تحديد المشكلة الفرعية الواجب تفريعها (المشكلة المرشحة لاحتواء الحل الأمثل Int)) ، والتوقف عن تفريع الأخرى (التي لا تحتوي على هذا الحل)، بهدف توفير الوقت والجهد اللازم لحل المشكلة الرئيسية (تقليص عملية البحث في شجرة التفريعات).