تم إضافة تقرير جديد 2024
ارسل ملاحظاتك

ارسل ملاحظاتك لنا









الرئيسية > دراسة نظرية لتصميم معيار يسهم...>الوصف

دراسة نظرية لتصميم معيار يسهم في تقليص عدد تفريعات طريقة التفريع والتحديد "B&B" للمشاكل الخطية من نوع "m×2"

العنوان بلغة أخرى: A Theoretical Study on Designing a Criterion for Reducing the Number of Branches in the Branch and Bound "B&B" Method for "2×M" Linear Problems
المصدر: مجلة الدراسات الاقتصادية
الناشر: جامعة سرت - كلية الاقتصاد
المؤلف الرئيسي: الشيخ، عبدالله محمد (مؤلف)
المؤلف الرئيسي (الإنجليزية): Elshaikh, Abdalla Mohamed
مؤلفين آخرين: الرمالي، عمر محمد (م. مشارك)
المجلد/العدد: مج7, ع2
محكمة: نعم
الدولة: ليبيا
التاريخ الميلادي: 2024
الشهر: أكتوبر
الصفحات: 68 - 84
رقم MD: 1523632
نوع المحتوى: بحوث ومقالات
اللغة: العربية
قواعد المعلومات: EcoLink
مواضيع:
البرمجة الخطية | طريقة التفريع والتحديد | المشاكل الخطية | النماذج الرياضية
كلمات المؤلف المفتاحية:
التفريع والتحديد | المشاكل الفرعية | Branch and Bound Ethod | Subproblems | Non-int
رابط المحتوى:
PDF (صورة)     
صورة الغلاف QR قانون

عدد مرات التحميل

1

حفظ في:
المستخلص: تعتبر طـريقة التفـريع والتحـديد (Branch and Bound Method) أهم الطرق المستخدمة في حل مشاكل برمجة العدد الصحيح، وتستخدم عندما يكون حل المشكلة غير منطقي من الناحية الفيزيائية، بمعنى عندما تكون متغيرات المشكلة غير قابلة للتجزئة، وتبـدأ آلية عمل هذه الطريقة انطلاقا من الحل الأمثل (Non-int)، وذلك بتفريع المشكلة إلى مشكلتين فرعيتين، وهذا يعني تجزئة منطقة الحلول الممكنة لمنطقتين، ومن تم إيجاد الحل الأمثل لهاتين المشكلتين كلا على حدة، ويتم الاستمرار في تفريع المشاكل الفرعية وإيجاد حلولها. ويتم التوقف عن سلسلة التفريعات في حالة عدم وجـود حل للمشكلة الفرعية أو عندما تكون قيم حلها قيم صحيحة (Integer). إن عدد المشاكل الفرعية الناتجة من عملية التفريع تزداد بشكل كبير بزيادة عدد متغيراتها وعدد قيودها، وقد توصل الشيخ وآخرون (يوليو 2022) لتحديد المعايير (Criterions) التي يتم استخدامها في بعض الحالات في تحديد المشكلة الفرعية الواجب تفريعها (المشكلة المرشحة لاحتواء الحل الأمثل Int)، والتوقف عن تفريع الأخرى (التي لا تحتوي على هذا الحل)، وفي هذه الورقة تم تصميم معيار أخر لتقليص عدد التفريعات التي عجزت عليها المعايير المستخدمة في الورقة المذكورة، بهدف توفير الوقت والجهد اللازم لحل المشكلة (تقليص شجرة التفريعات)، حيث يمكن عن طريق استخدام هذا المعيار تقليص ما يقارب على 25% من عدد التفريعات.

The Branch and Bound Method is considered the most important approach for solving integer programming problems. It is particularly useful when the problem's solution is physically infeasible, meaning the problem's variables are indivisible. The method begins by finding the non-integer optimal solution (Non-int) and then branching the problem into two subproblems, effectively dividing the feasible solution space into two regions. The optimal solutions for these subproblems are found individually, and the process of branching and solving continues. The branching sequence stops when a subproblem has no feasible solution or when its solution yields integer values. The number of subproblems generated through branching increases significantly with the number of variables and constraints. Sheikh et al. (July 2022) identified criteria for selecting the subproblem most likely to contain the optimal integer solution and stopping the branching for others that do not. In this paper, we propose an additional criterion aimed at reducing the number of branches, where previous criteria have been insufficient. This new criterion can reduce the number of branches by approximately 25%, thereby saving time and effort in solving the problem (pruning the branch tree).

عناصر مشابهة


© 2025 المنظومة. جميع الحقوق محفوظة.