البرمجة الهدفية العشوائية — تحسين الأهداف المتعددة في ظل عدم اليقين
- قدّمه
- Contini, B. (building on Charnes & Cooper's chance-constrained programming)
- السنة
- 1968
- النوع
- Stochastic multi-goal optimization
- العائلة
- Simulation / optimization
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
تمتد البرمجة الهدفية العشوائية (SGP) من البرمجة الهدفية الكلاسيكية للتعامل مع عدم اليقين في أهداف الغايات، أو معاملات القيود، أو معلمات الطرف الأيمن. من خلال دمج القيود الاحتمالية ومكونات الهدف العشوائي، فإنها تجد حلولًا تلبي الأهداف المتعددة عند مستويات احتمالية مقبولة، مما يجعلها مناسبة لمشاكل اتخاذ القرار حيث تكون البيانات غير مؤكدة أو متغيرة بطبيعتها.
الفكرة الحدسية وراء الطريقة
تسأل البرمجة الهدفية الكلاسيكية: هل يمكننا الاقتراب من كل هدف في وقت واحد؟ تسأل البرمجة الهدفية العشوائية نفس السؤال ولكنها تقر بأن العالم غير مؤكد — قد تتغير الأهداف، وقد تختلف الموارد، وقد تكون البيانات مشوشة. بدلاً من التحسين لسيناريو ثابت واحد، تسعى SGP إلى إيجاد حلول تعمل بشكل جيد في المتوسط أو تلبي كل هدف بمستوى احتمالية محدد. فكر في الأمر على أنه وضع أفضل خطة ممكنة مع الاعتراف الصادق بما لا تعرفه.
التاريخ
تم تقديم البرمجة الهدفية بواسطة Charnes و Cooper في أواخر الخمسينيات. قام Contini (1968) بتوسيعها رسميًا إلى إعدادات عشوائية باستخدام أفكار البرمجة المقيدة بالفرص. شهدت العقود اللاحقة تطبيقات متزايدة في التمويل والزراعة والسياسة العامة. اكتسبت الطريقة أساسًا نظريًا إضافيًا من خلال الارتباطات بالتحسين القوي الذي تم تطويره في التسعينيات والعقد الأول من القرن الحادي والعشرين.
متى تُستخدم
استخدم البرمجة الهدفية العشوائية عندما تكون مشكلة القرار لها أهداف متعددة ومتعارضة، وعندما تكون بعض المعلمات على الأقل (الطلبات، التكاليف، الإنتاجيات) غير مؤكدة ويمكن وصفها بتوزيعات احتمالية، وعندما يحتاج صانعو القرار إلى ضمانات معبر عنها كمستويات ثقة بدلاً من حدود أسوأ الحالات. إنها مناسبة لتخطيط سلسلة التوريد، وتخصيص موارد الرعاية الصحية، وإدارة المحافظ المالية بأهداف متعددة، والتخطيط الزراعي في ظل عدم اليقين بشأن الطقس. لا تستخدمها عندما تكون الأهداف غير قابلة للمقارنة حقًا ولا يمكن ترجيحها، وعندما لا تتوفر معلومات توزيعية (استخدم التحسين القوي بدلاً من ذلك)، وعندما يكون للمشكلة هدف واحد فقط (استخدم البرمجة العشوائية)، أو عندما يكون عدد السيناريوهات كبيرًا جدًا بحيث تصبح إعادة الصياغة المكافئة الحتمية غير قابلة للحل.
الحدود والاعتبارات
- تتطلب معرفة معلمات التوزيع (المتوسطات، التباينات) التي قد يكون من الصعب تقديرها بدقة.
- قد تجعل التوزيعات غير الطبيعية أو قيود الفرص المشتركة إعادة الصياغة الحتمية غير قابلة للحل، مما يتطلب أساليب قائمة على السيناريوهات أو المحاكاة.
- اختيار مستويات الثقة alpha_i وأوزان الهدف w_i هو أمر ذاتي بطبيعته ويمكن أن يؤثر بشكل كبير على النتائج.
- أكثر تطلبًا من الناحية الحسابية من البرمجة الهدفية الحتمية، خاصة للمشاكل الكبيرة أو غير الخطية.
- قد يكون تفسير المقايضات بين الأهداف الاحتمالية صعبًا على أصحاب المصلحة غير التقنيين.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- تتعامل مع أهداف متعددة ومتعارضة في وقت واحد ضمن إطار تحسين واحد.
- تسمح بالتحديد الصريح لمستويات المخاطر المقبولة (الثقة) لكل هدف أو قيد.
- في ظل افتراضات الطبيعية، تختزل قيود الفرص إلى قيود مخروطية من الدرجة الثانية قابلة للحل باستخدام المحللات القياسية.
- توفر لصانعي القرار احتمالية تحقيق الهدف، مما يقدم معلومات أغنى من حل سيناريو واحد.
- تشمل البرمجة الهدفية الحتمية كحالة خاصة (مستوى الثقة = 1 مع معلمات ثابتة).
- متجذرة نظريًا بشكل جيد، وترتبط بأدبيات البرمجة المقيدة بالفرص والتحسين القوي.
التطبيقات
- التخطيط الزراعي: تخصيص الأراضي والموارد عبر المحاصيل في ظل ظروف هطول الأمطار والأسعار غير المؤكدة.
- تخصيص موارد الرعاية الصحية: جدولة الموظفين والأسرة مع تلبية أهداف مستوى الخدمة في ظل الطلب غير المؤكد للمرضى.
- إدارة سلسلة التوريد: تخطيط الإنتاج والمخزون مع عدم اليقين في الإنتاجيات، وأوقات التسليم، والطلب.
- تحسين المحافظ المالية بأهداف متعددة (العائد، المخاطر، السيولة) في ظل عدم اليقين في السوق.
- تخطيط أنظمة الطاقة: موازنة أهداف التكلفة والموثوقية والانبعاثات في ظل عدم اليقين في التوليد المتجدد.
- الميزنة البلدية: تخصيص الأموال العامة عبر الإدارات في ظل إيرادات ونفقات غير مؤكدة.
كيف يعمل
كيف يعمل
تحديد متغيرات القرار، والأهداف الطموحة المتعددة (الأهداف المرجوة)، وأي قيود صارمة. يتم التعبير عن كل هدف i على النحو التالي: f_i(x) + d_i^- - d_i^+ = g_i، حيث d_i^- و d_i^+ هما متغيرات الانحراف السالب والموجب عن الهدف المرجو g_i. تعيين أوزان الأولوية التي تعكس الأهمية النسبية لتحقيق كل هدف.
تحديد المعلمات غير المؤكدة: قد يتم نمذجة الأهداف المرجوة g_i، أو معاملات القيود، أو معاملات دالة الهدف كمتغيرات عشوائية ذات توزيعات معروفة أو مقدرة (مثل، التوزيع الطبيعي، المنتظم، التجريبي). تحديد الافتراضات التوزيعية بناءً على البيانات التاريخية أو حكم الخبراء.
تحويل القيود غير المؤكدة إلى قيود احتمالية (فرص). بالنسبة لقيد عشوائي يتضمن المعلمة العشوائية b_i ذات التوزيع F، يتطلب P(g_i(x) <= b_i) >= alpha_i، حيث alpha_i هو مستوى ثقة محدد من قبل المستخدم (مثل، 0.90 أو 0.95). في ظل افتراضات الطبيعية، يمكن إعادة صياغة هذه القيود كقيود مخروطية من الدرجة الثانية حتمية.
الصيغة
P(g_i(x) \leq b_i) \geq \alpha_i
حل مشكلة التحسين الناتجة (المعاد صياغتها ربما): تقليل مجموع الأوزان للانحرافات min sum_i (w_i^+ d_i^+ + w_i^- d_i^-) مع مراعاة المكافئات الحتمية لقيود الفرص وأي قيود صارمة متبقية. استخدام محللات البرمجة الخطية (LP)، أو البرمجة الخطية الصحيحة المختلطة (MILP)، أو المحللات غير الخطية اعتمادًا على هيكل المشكلة.
الصيغة
\min \sum_{i} (w_i^+ d_i^+ + w_i^- d_i^-)تقييم الحل عن طريق التحقق من مستويات تحقيق الهدف، واحتمالية استيفاء القيود، والحساسية للافتراضات التوزيعية. إجراء تحقق لاحق باستخدام محاكاة مونت كارلو عن طريق أخذ عينات من تحقق المعلمات والتحقق من أن الحل يلبي الأهداف عند مستويات الثقة المذكورة في السيناريوهات المحاكاة.
الأخطاء الشائعة
- افتراض طبيعية المعلمات غير المؤكدة دون تحقق تجريبي يمكن أن ينتج ضمانات ثقة مضللة.
- وضع مستويات ثقة عالية جدًا (مثل، 0.999) يؤدي فعليًا إلى انهيار النموذج إلى صياغة حتمية محافظة، مما يبطل الغرض من النمذجة العشوائية.
- الخلط بين البرمجة الهدفية المقيدة بالفرص والبرمجة الهدفية القوية — كلاهما يتعامل مع عدم اليقين بشكل مختلف وليس قابلًا للتبديل.
- الفشل في التحقق من صحة الحل العشوائي عبر محاكاة مونت كارلو يترك المخاطر الفعلية لانتهاكات الأهداف غير معروفة.
- تجاهل الارتباط بين المعلمات غير المؤكدة يمكن أن ينتج حلولًا غير قابلة للتنفيذ أو متفائلة بشكل مفرط.
الأسئلة الشائعة
كيف تختلف البرمجة الهدفية العشوائية عن البرمجة الهدفية الكلاسيكية؟
تفترض البرمجة الهدفية الكلاسيكية أن جميع المعلمات (الأهداف، القيود، التكاليف) معروفة بيقين. تسمح البرمجة الهدفية العشوائية لبعض المعلمات بأن تكون متغيرات عشوائية، وتدمج قيودًا احتمالية تتطلب تحقيق الأهداف بمستوى ثقة محدد بدلاً من تحقيقها بالضبط.
ما هو افتراض التوزيع الأكثر شيوعًا؟
التوزيع الطبيعي هو الافتراض الأكثر شيوعًا لأنه يسمح بإعادة صياغة قيود الفرص بالضبط كقيود مخروطية من الدرجة الثانية حتمية. عندما تشير البيانات إلى توزيعات غير طبيعية، يتم استخدام أساليب قائمة على السيناريوهات أو المحاكاة بدلاً من ذلك.
كيف أختار مستويات الثقة alpha_i لكل قيد فرصة؟
تعكس مستويات الثقة تحمل صانع القرار للمخاطر لكل هدف. القيم من 0.90 إلى 0.95 شائعة في الممارسة العملية. القيم الأعلى تجعل المشكلة أكثر تحفظًا وقد تتطلب تخفيف الأهداف الأخرى؛ القيم الأقل تسمح بمزيد من المخاطر ولكن قد تؤدي إلى نتائج غير مقبولة.
هل يمكن للبرمجة الهدفية العشوائية التعامل مع متغيرات القرار الصحيحة؟
نعم. عند دمجها مع المتغيرات الصحيحة، تصبح المشكلة برمجة هدفية صحيحة عشوائية، وهي أصعب في الحل ولكنها لا تزال قابلة للحل للحالات ذات الحجم المعتدل باستخدام أساليب الفرع والحد مع إعادة صياغة قيود الفرص.
هل يجب أن أستخدم البرمجة الهدفية العشوائية أم التحسين القوي عندما تكون لدي معلمات غير مؤكدة؟
إذا كانت لديك معلومات توزيعية موثوقة وتريد ضمانات احتمالية، فإن SGP مناسب. إذا كنت تعرف فقط مجموعات عدم اليقين (الحدود) وتريد ضمانات أسوأ الحالات دون افتراضات توزيعية، فإن التحسين القوي أفضل. عندما يكون كلاهما ممكنًا، فإن مقارنة الحلول من كلا النهجين هي ممارسة جيدة.
طرق ذات صلة
المصادر
Contini, B. (1968). A stochastic approach to goal programming. Operations Research, 16(3), 576–586.
افتح مرجع DOIتم النسخ.Charnes, A., Cooper, W. W. (1959). Chance-constrained programming. Management Science, 6(1), 73–79.
افتح مرجع DOIتم النسخ.