تنظيم صفحاتك في مجموعات
يمكنك حفظ المحتوى وتصنيفه حسب إعداداتك المفضّلة.
تحسين عدد صحيح
تُعرف مسائل التحسين الخطي التي تتطلب أن تكون بعض المتغيّرات كأعداد صحيحة باسم برامج العدد الصحيح المختلطة (MIP).
يمكن أن تنشأ هذه المتغيرات بطريقتين:
متغيّرات الأعداد الصحيحة التي تمثّل أعداد العناصر، مثل السيارات أو أجهزة التلفزيون، وتكمن المشكلة في تحديد عدد العناصر المطلوب تصنيعها من كل عنصر بهدف زيادة الربح إلى أقصى حد.
يمكن عادةً إعداد مثل هذه المسائل كمشاكل تحسين خطية عادية،
مع الشرط الإضافي بأن تكون المتغيّرات أعدادً صحيحةً.
يعرض القسم التالي مثالاً لهذا
النوع من المسائل.
المتغيّرات المنطقية التي تمثّل القرارات ذات القيم 0-1
كمثال، يمكنك التفكير في مشكلة تتعلّق بإسناد المهام إلى العاملين (
راجِع المهام الدراسية). لإعداد هذا النوع من المسائل، يمكنك تحديد متغيّرات منطقية xi,j تساوي 1 في حال تعيين العامل i للمهمة j، و0 في الحالات الأخرى.
وللحصول على معلومات تمهيدية جيدة حول تحسين الأعداد الصحيحة، ننصحك بالاطّلاع على
دليل إعداد نماذج Mosek.
الأدوات
توفّر Google بضع طرق لحل مشاكل MIP:
MPSolver: برنامج تضمين للعديد من حلول MIP التابعة لجهات خارجية التي تستخدم أساليب معيارية تعتمد على تفريع الفرع (MIP) وترابطه.
أداة حلّ CP-SAT: هي أداة لبرمجة القيود تستخدم طُرق تقييم SAT (مدى الرضا).
ما مِن قاعدة ثابتة لتحديد ما إذا كان يجب استخدام أداة حلّ MIP أو أداة حلّ CP-SAT. كدليل تقريبي:
تعتبر أدوات حلّ MIP أكثر ملاءمةً للمسائل التي يمكن إعدادها كتنسيق LP عادي، ولكن مع متغيّرات عشوائية للأعداد الصحيحة، كما في المثال الأول أعلاه.
تعد أداة حل CP-SAT أكثر ملاءمة للمشكلات التي تكون فيها معظم المتغيرات
منطقية، مثل المثال الثاني أعلاه.
بالنسبة إلى MIP النموذجي الذي يحتوي على كل من متغيّري الأعداد الصحيحة والقيم المنطقية، لا يوجد غالبًا اختلاف واضح في السرعة بين أداتي الحلّ، لذلك قد يعود اختيارك إلى التفضيل الشخصي.
للحصول على أمثلة تستخدم كلاً من أدوات حلّ MIP وCP-SAT، يمكنك مراجعة
حل مسألة مهمة
وأقسام المهام الأخرى.
هناك طريقة أخرى لحل مشاكل برمجة الأعداد الصحيحة وهي استخدام أداة حلّ تدفق الشبكة.
راجع التعيين كمشكلة الحد الأدنى للتكلفة
للحصول على مثال.
بالنسبة إلى أي مشكلة يمكن إعدادها كتدفق شبكة، يمكن أن تكون أداة حلّ الحد الأدنى للتكلفة أسرع من أدوات حلّ MIP أو CP-SAT. ومع ذلك، لا يمكن إعداد جميع MIP
بهذه الطريقة.
تاريخ التعديل الأخير: 2024-08-09 (حسب التوقيت العالمي المتفَّق عليه)
[[["يسهُل فهم المحتوى.","easyToUnderstand","thumb-up"],["ساعَدني المحتوى في حلّ مشكلتي.","solvedMyProblem","thumb-up"],["غير ذلك","otherUp","thumb-up"]],[["لا يحتوي على المعلومات التي أحتاج إليها.","missingTheInformationINeed","thumb-down"],["الخطوات معقدة للغاية / كثيرة جدًا.","tooComplicatedTooManySteps","thumb-down"],["المحتوى قديم.","outOfDate","thumb-down"],["ثمة مشكلة في الترجمة.","translationIssue","thumb-down"],["مشكلة في العيّنات / التعليمات البرمجية","samplesCodeIssue","thumb-down"],["غير ذلك","otherDown","thumb-down"]],["تاريخ التعديل الأخير: 2024-08-09 (حسب التوقيت العالمي المتفَّق عليه)"],[[["Mixed Integer Programs (MIPs) are linear optimization problems where some variables must be integers, representing quantities or decisions."],["Google offers tools for solving MIPs: MPSolver uses standard techniques, while CP-SAT solver employs constraint programming, particularly suitable for problems with many Boolean variables."],["Choosing between MIP and CP-SAT solvers depends on the problem structure, with MIP solvers often preferred for problems with standard LP formulations and arbitrary integer variables, while CP-SAT excels in scenarios dominated by Boolean variables."],["Network flow solvers can offer faster solutions for specific MIPs that can be formulated as network flow problems."]]],["Mixed Integer Programs (MIPs) handle linear optimization problems requiring integer variables, which can represent item counts or Boolean decisions. Google offers MPSolver for MIPs, CP-SAT, and original CP solvers for constraint programming. MIP solvers suit problems with arbitrary integer variables, while CP-SAT excels with predominantly Boolean variables. Network flow solvers are faster for problems adaptable to this format, although not all MIPs fit this structure. The choice between MIP and CP-SAT often depends on problem structure and personal preference.\n"]]
