اختيار المتغير ذو الكسر الأكبر أو الأصغر كأساس للتفريع في طريقة التفريع والتحديد

Abstract

إن معظم مشاكل البرمجة الخطية الواقعية تحتوي قيم حلها (متغيراتها القرارية Decision Variables) على كسور (Non-integer)، وفي العديد من الحالات الاقتصادية والفيزيائية يكون هذا الأمر غير منطقي، فمثلاً غير مقبول أن يكون الحل هو إنتاج 5.67 طائرة، وتُعد طريقة التفريع والتحديد (Branch and Bound Method) من أهم الطرق المستخدمة في تحديد الحل الأمثل الصحيح (Integer). وتُعنى هذه الورقة بدراسة هذه الطريقة (B&B) وتحديداً دراسة الاختلاف القائم بين البُحاث والمؤلفين في عملية تفريع (تجزئة) المشكلة الرئيسية إلى مشاكل فرعية، وكيفية تحديد المتغير الذي تتم على أساسه عملية التفريع بهدف الوصول للحل الأمثل الصحيح (Integer)، فيرى بعض البحاث أن عملية التفريع تتم على أساس المتغير الذي يحتوي على الكسر الأكبر، والبعض الآخر منهم لا يرى فرقاً في استخدام أي من المتغيرات. والجدير بالذكر هنا هو أن كلا الفريقين لم يذكروا التحليلات المنطقية والأدلة التي تؤيد نظريتهم، وتهدف هذه الورقة لدراسة هذه المشكلة والغوص في آلية عمل هذه الطريقة (B&B) باتباع المنهج التحليلي في تجزئة المشكلة الرئيسية إلى مشاكل فرعية وتتبع مسارات التفريع باستخدام الطريقة البيانية. تبين بأنه يمكن الوصول للحل الأمثل الصحيح باختيار أي من المتغيرين، إلا أنه ليس بالضرورة الوصول للحل الأمثل بنفس عدد عمليات التفريع (المشاكل الفرعية)، فقد يختلف عدد عمليات التفريع باختلاف المتغير المستخدم في عملية التفريع، وتمكنا أيضاً من تقديم التحليلات المنطقية والأدلة التي تؤيد صحة هذه التحليلات.