بيئة تجربة البرمجة بالأعداد الصحيحة
حل برنامجًا خطيًا صغيرًا بأعداد صحيحة بخوارزمية التفرّع والتحديد الدقيقة، واعرض كل عقدة في البحث. ولا يوصف أفضل حل بأنه أمثل مثبت إلا بعد استكشاف الشجرة كاملة.
تقتصر البرامج على 4,000 حرف و40 سطرًا و8 متغيرات و8 قيود تشمل متغيرين أو أكثر؛ ويكون حد العقد من 1 إلى 5,000، كما يتوقف البحث بعد 3,000,000 خطوة حسابية دقيقة. تُجرى الحسابات على جهازك في عامل خلفي بمهلة 15 ثانية. التنزيلات تقرير JSON وملف CSV للعقد. في السطر الأول اكتب maximize أو minimize ودالة الهدف. ثم اكتب قيدًا واحدًا في كل سطر. حتى 4,000 حرف. راجع الإعدادات قبل التشغيل.
نتيجتك
بيئة تجربة البرمجة بالأعداد الصحيحة
- اكتب دالة الهدف في السطر الأول، مثل maximize 5x + 4y.
- أضف قيدًا واحدًا في كل سطر، وحدودًا مثل x, y >= 0، ويمكنك إضافة أسطر مثل integer x أو binary z.
- حدّد حد العقد ثم شغّل البحث.
- اقرأ الحالة وأفضل حل حالي وأفضل حد والفجوة، ثم نزّل تقرير JSON أو ملف CSV للعقد.
ما تحتاج إلى معرفته
تقتصر البرامج على 4,000 حرف و40 سطرًا و8 متغيرات و8 قيود تشمل متغيرين أو أكثر؛ ويكون حد العقد من 1 إلى 5,000، كما يتوقف البحث بعد 3,000,000 خطوة حسابية دقيقة. تُجرى الحسابات على جهازك في عامل خلفي بمهلة 15 ثانية. التنزيلات تقرير JSON وملف CSV للعقد.
التفرّع والتحديد
يحل كل عقدة الإرخاء الخطي بدقة بطريقة السمبلكس. ويُقسّم المتغير الصحيح ذي القيمة الكسرية إلى فرعين: x <= floor وx >= ceiling. تُحذف العقد إذا كان استرخاؤها غير ممكن أو لم يكن بوسعها الوصول إلى حل أفضل من أفضل نقطة صحيحة عُثر عليها. الطريقة: Wolsey، Integer Programming، الطبعة 2، الفصل 7 (2020).
ما معنى الإثبات
عندما تُحل كل عقدة أو تُحذف بحد دقيق، يثبت أن أفضل حل حالي أمثل أو يثبت أن المسألة غير ممكنة. وإذا أوقف حد العقد أو ميزانية الخطوات البحث مبكرًا، فلا يكون أفضل حل حالي إلا أفضل نقطة عُثر عليها حتى الآن، ويعرض التقرير أفضل حد والفجوة بينهما.
قواعد الإدخال
تكون المتغيرات صحيحة ما لم تحدد بعضها بعبارة integer x, y، وعندها تكون البقية مستمرة. وتصبح القيود ذات المتغير الواحد حدودًا. ويوقف الإرخاء غير المحدود البحث، لأن البرنامج الصحيح قد يكون عندئذ غير محدود أو غير ممكن.