البرمجة الخطية متعددة الأهداف (MOLP)
- قدّمه
- Steuer, R. E.; Charnes, A.; Cooper, W. W.
- السنة
- 1955–1986
- النوع
- Mathematical optimization / vector optimization
- العائلة
- Simulation / optimization
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
تمتد البرمجة الخطية متعددة الأهداف (MOLP) من البرمجة الخطية الكلاسيكية للتعامل مع عدة دوال هدف خطية متعارضة في وقت واحد ضمن منطقة ممكنة محددة بقيود خطية. بدلاً من حل أمثل واحد، تنتج البرمجة الخطية متعددة الأهداف واجهة باريتو الفعالة التي يختار منها صانع القرار مقايضة مفضلة. وهي أساسية لأبحاث العمليات وعلوم الإدارة في مشاكل تخصيص الموارد والتخطيط والتصميم ذات الأهداف المتنافسة.
الفكرة الحدسية وراء الطريقة
في البرمجة الخطية العادية، تقوم بتقليل تكلفة واحدة أو زيادة ربح واحد، لكن القرارات الحقيقية تتضمن دائمًا تقريبًا عدة أهداف متنافسة - تقليل التكلفة مع زيادة مستوى الخدمة مع تقليل الانبعاثات. تعترف البرمجة الخطية متعددة الأهداف بأنه لا يوجد حل واحد هو الأفضل في جميع الأهداف دفعة واحدة. إنها ترسم كامل واجهة الحلول غير المهيمنة (فعالة باريتو) حيث يؤدي تحسين هدف واحد بالضرورة إلى تفاقم هدف آخر. ثم يستخدم صانع القرار معلومات التفضيل - الأوزان، مستويات التطلع، أو الاستعلامات التفاعلية - لاختيار حل نهائي من تلك الواجهة، مما يجعل المقايضات صريحة بدلاً من إخفائها داخل درجة مركبة.
التاريخ
تعود الأسس النظرية للبرمجة الخطية متعددة الأهداف إلى أعمال تشارنز وكوبر في الخمسينيات حول البرمجة الهدفية وكوبمانز حول الإنتاج الفعال. وحد كتاب ستوير عام 1986 هذا المجال، ونظم طرق المجموع الموزون، وإبسيلون-القيود، والطرق التفاعلية التي لا تزال معيارية حتى اليوم. أصبحت البرمجة الخطية متعددة الأهداف الآن موضوعًا أساسيًا في مناهج أبحاث العمليات في جميع أنحاء العالم.
متى تُستخدم
استخدم البرمجة الخطية متعددة الأهداف عندما تكون للمشكلة أهداف خطية متنافسة متعددة وقيود خطية، والبيانات مستمرة ومعروفة بدقة (أو يمكن اعتبارها حتمية)، ويحتاج صانع القرار إلى فهم المقايضات بشكل صريح بدلاً من قبول درجة مجمعة مسبقًا. تشمل الإعدادات النموذجية تخطيط الإنتاج، تخصيص المحافظ، توجيه النقل، وميزانيات الموارد العامة. لا تستخدم عندما تكون الأهداف أو القيود غير خطية (استخدم البرمجة غير الخطية متعددة الأهداف أو الخوارزميات فوق التطورية بدلاً من ذلك)، عندما تكون البيانات منفصلة أو ثنائية (استخدم البرمجة الصحيحة متعددة الأهداف)، عندما يتجاوز عدد الأهداف خمسة أو ستة (تصبح واجهة باريتو الفعالة صعبة حسابيًا)، أو عندما يكون صانع القرار غير راغب في المشاركة في استخلاص التفضيلات التفاعلية.
الحدود والاعتبارات
- مقتصرة على دوال الهدف الخطية والقيود الخطية؛ غالبًا ما تكون مشاكل العالم الحقيقي غير خطية.
- يمكن أن تحتوي الواجهة الفعالة على عدد أسي من النقاط الطرفية في الأبعاد الأعلى، مما يجعل التعداد الشامل غير عملي.
- تتطلب بيانات رقمية دقيقة؛ لا يتم التعامل مع عدم اليقين أو الضبابية في المعاملات بشكل طبيعي.
- تعتمد الأساليب التفاعلية بشكل كبير على توافر صانع القرار وقدرته على التعبير عن التفضيلات باستمرار.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- تنتج واجهة باريتو الفعالة بالكامل، مما يمنح صانعي القرار صورة كاملة للمقايضات.
- قابلة للحساب بشكل معقول لأحجام المشاكل المعتدلة عبر أدوات الحل المستندة إلى السيمبلكس.
- تضمن الأمثلية الرياضية لكل نقطة على الواجهة الفعالة.
- مدعومة جيدًا ببرامج ناضجة (CPLEX، Gurobi، بدائل مفتوحة المصدر).
- تصبح المقايضات صريحة بدلاً من دمجها في مؤشر مركب غير شفاف.
التطبيقات
- تخطيط الإنتاج الذي يوازن بين التكلفة والإنتاجية واستخدام الموارد.
- تحسين المحفظة الذي يوازن بين العائد والمخاطر والسيولة.
- تصميم شبكات النقل والخدمات اللوجستية بأهداف متنافسة للتكلفة والخدمة.
- تخطيط أنظمة الطاقة الذي يقلل التكلفة مع تلبية أهداف الانبعاثات والموثوقية.
- تخصيص موارد الرعاية الصحية الذي يوازن بين العدالة والكفاءة وقيود الميزانية.
- الإدارة البيئية التي تحسن الأداء الاقتصادي والبيئي في وقت واحد.
كيف يعمل
كيف يعمل
صياغة k دوال هدف خطية f1(x) إلى fk(x) ومنطقة ممكنة X محددة بقيود عدم المساواة والمساواة الخطية (Ax <= b، x >= 0). تحديد الأهداف التي سيتم تقليلها وتلك التي سيتم زيادتها. التأكد من أن جميع دوال الهدف والقيود خطية في متغيرات القرار.
الصيغة
\min_{x \in X} \mathbf{f}(x) = (f_1(x), f_2(x), \ldots, f_k(x))^T \text{ s.t. } Ax \leq b,\; x \geq 0توليد مجموعة الحلول الفعالة لباريتو (غير المهيمنة). تشمل الأساليب الشائعة طريقة المجموع الموزون (تغيير الأوزان عبر السيمبلكس)، طريقة إبسيلون-القيود (تحسين هدف واحد مع تحديد حدود للأهداف الأخرى)، وطريقة تشيبيشيف. كل طريقة تتتبع جزءًا أو كل الواجهة الفعالة.
تطبيق تقنية قياسية لتحويل مشكلة المتجه إلى سلسلة من مشكلات البرمجة الخطية ذات الهدف الواحد. في نهج المجموع الموزون، قم بحل min sum(wi * fi(x)) لأوزان متغيرة بشكل منهجي. سجل كل نقطة طرفية فعالة في فضاء الهدف.
الصيغة
\min_{x \in X} \sum_{i=1}^{k} w_i f_i(x), \quad w_i \geq 0, \; \sum w_i = 1جمع النقاط الطرفية الفعالة والحواف التي تربطها لتوصيف واجهة باريتو. تحليل نطاق كل هدف عبر الواجهة لفهم حجم المقايضات. تقديم الواجهة لصانع القرار عبر جداول أو رسوم بيانية ثنائية الهدف.
إشراك صانع القرار لاختيار حل مفضل من المجموعة الفعالة. تتناوب الأساليب التفاعلية (STEM، NIMBUS) بين تقديم الحلول وطلب التعبير عن التفضيل من صانع القرار، والتقارب نحو اختيار نهائي يعكس أولوياته بشكل أفضل.
الأخطاء الشائعة
- استخدام أوزان ثابتة في القياس الموزون والإبلاغ عن حل واحد فقط يحجب الواجهة ويهزم الغرض من البرمجة الخطية متعددة الأهداف.
- خلط مفاهيم الكفاءة لباريتو مع الأمثلية: كل نقطة على الواجهة فعالة، ولكن لا توجد نقطة هي 'الأفضل' عالميًا بدون معلومات التفضيل.
- إهمال التحقق مما إذا كانت المنطقة الممكنة محدودة؛ مشكلة غير محدودة لا تنتج مجموعة فعالة محدودة.
- معاملة البرمجة الخطية متعددة الأهداف كصندوق أسود دون إشراك صانع القرار في الاختيار يؤدي إلى اختيارات نهائية اعتباطية.
- تطبيق البرمجة الخطية متعددة الأهداف على مشاكل صحيحة بطبيعتها دون التحول إلى البرمجة الصحيحة متعددة الأهداف، مما ينتج حلولًا تنتهك خاصية الأعداد الصحيحة.
الأسئلة الشائعة
كيف تختلف البرمجة الخطية متعددة الأهداف عن البرمجة الهدفية؟
البرمجة الهدفية هي حالة خاصة أو متغير منها: فهي تحول كل هدف إلى مستوى تطلع وتقلل بعد ذلك الانحرافات عن تلك الأهداف، مما ينتج عنه حل واحد. تسعى البرمجة الخطية متعددة الأهداف في شكلها العام إلى توصيف واجهة باريتو الفعالة بالكامل دون تحديد مستويات مستهدفة مسبقًا، مما يمنح صانع القرار مزيدًا من المرونة.
هل يمكن للبرمجة الخطية متعددة الأهداف التعامل مع أكثر من هدفين؟
نعم، ولكن يصبح تصور واجهة باريتو أصعب بما يتجاوز هدفين أو ثلاثة أهداف ويمكن أن ينمو عدد النقاط الطرفية الفعالة بشكل أسي. يوصى بالأساليب التفاعلية وتقنيات المجموعات التمثيلية لأربعة أهداف أو أكثر.
ماذا لو كانت بياناتي غير مؤكدة؟
تفترض البرمجة الخطية متعددة الأهداف القياسية معاملات حتمية. يمكن معالجة عدم اليقين عن طريق التوسع إلى البرمجة الخطية العشوائية متعددة الأهداف (قيود الفرصة، الأساليب القائمة على السيناريوهات) أو التحسين القوي متعدد الأهداف، وهي أساليب منفصلة.
هل البرمجة الخطية متعددة الأهداف هي نفسها التحسين متعدد الأهداف؟
البرمجة الخطية متعددة الأهداف هي حالة خاصة من التحسين متعدد الأهداف حيث تكون جميع الأهداف والقيود خطية. التحسين متعدد الأهداف هو المجال الأوسع الذي يشمل أيضًا المتغيرات غير الخطية والصحيحة والتركيبية.
أي طريقة قياسية يجب أن أستخدم؟
طريقة المجموع الموزون بسيطة ولكنها تفوت الأجزاء غير المحدبة من الواجهة. يمكن لطريقة إبسيلون-القيود استعادة الواجهة الكاملة حتى للمناطق غير المحدبة وهي مفضلة بشكل عام للتحليل الشامل. الأساليب التفاعلية هي الأفضل عندما يكون إشراك صانع القرار ممكنًا.
طرق ذات صلة
المصادر
Steuer, R. E. (1986). Multiple Criteria Optimization: Theory, Computation, and Application. John Wiley & Sons, New York.
ردمك: 9780471888468تم النسخ.Chankong, V., Haimes, Y. Y. (1983). Multiobjective Decision Making: Theory and Methodology. North-Holland, New York.
افتح مرجع المنشورتم النسخ.