طريقة التفرع والتحديد (Branch and Bound):

طريقة التفرع والتحديد (Branch and Bound):
طريقة التفرع والتحديد هي أكثر الطرائق واسعة الاستخدام لحل كل من مسائل برمجة الاعداد الصحيحة التامة ومسائل برمجة الاعداد الصحيحة المختلطة في الواقع العملي تتضمن خوارزمية التفرع والتحديد اجراءات تكرارية عددية كفوءة لاختيار الحلول العددية المتاحة كلها, مبتدء باهمال القيود العددية لمسألة برمجة الاعداد الصحيحة الخطية ومن ثم حل المسئلة برمجة خطية اذا كان الحل الأمثل للمسئلة الخطية صحيحا عدديا فالحل امثل من الناحية العدية عدا ذلك طريقة التفرع والتحديد يتم اعتمادها بتطبيق عمليتين أساسيتين.
(1)- التفرع (Branching):
يقصد بالتفرع تقسيم فضاء الحل المستمر الى فضاءات فرعية مسائل فرعية مستمرة الهدف امن عملية التقسيم هو حذف أجزاء من الفضاء المستمر والذي يكون غير مقبول (infeasible) المسألة برمجة الأعداد الصحيحة, وهذا يتم عن طريق القيود العددية الضرورية للحصول على الحلول العددية المثلى, ولكن في طريقة أخرى لا يمكن حذف نقاط عددية غير متاحة بمعنى اخر المجموعة الناتجة من المسائل الفرعية تعرف بشكل متكامل جميع نقاط الحل العددي المتاح اللمسألة الأصلية بسبب أعطي اسم التفرع (Branching).
(2)- التحديد (Bounding):
قيمة دالة الهدف المثلى لكل مسئلة فرعية للمسئلة الأصلية من نوع التعظيم او التصغير يحصل عليها من عملية التقسيم اذ يتم ادراجها كحد اعلى اواصغر لقيمة دالة الهدف المرتبطة مع القيم العددية المتاحة المتغيرات القرار. هذا الحد(Bound) اساسي لعملية ترتيب الحلول المثلى للمجموعات الفرعية, هذه العملية يطلق عليها اسم التحديد (Bounding).
ويمكن تمثيل خوارزمية التقرع والتحديد بالخطوات الرئيسية الاتية:
وو
1- نقوم بايجاد الحل الأمثل لنموذج البرمجة الخطية باحدى الطرق المتاحة لحل نموذج
البرمجة الخطية.
2- نقوم بتجزئة الحل الامثل لنموذج البرمجة الخطية من خلال التفرع لاحدى متغيرات
القرار الذي يفترض أن يكون ذو قيمة عددية صحيحة والذي هو في الأصل ذو قيمة کسرية في الحل الأمثل للبرمجة الخطية. وبما أن هناك متغيرات قرار اكثر من متغير تكون القيمة الكسرية بالحل الأمثل للبرمجة الخطية والتي ايضا يجب ان تكون ذو قيمة عددية صحيحة لذلك يجب أن نحدد اي متغير من المتغيرات القرار ليرشح ان يكون متغير التفرع والاعتبارات المقترحة لمتغير المتفرع المناسب هي:
a- اختيار المتغير العددي ذو اكبر قيمة كسرية في حل البرمجة الخطية.
b- تخصيص الأولوية للمتغيرات العددية من حيث الأهمية حسب المعايير.