الانتقال إلى المحتوى
العودة إلى نتائج البحث

الطريقة السيمبلكس

قدّمه
George Dantzig
السنة
1947
النوع
algorithm
العائلة
Optimization

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

الطريقة السيمبلكس، التي طورها جورج دانتزيغ عام 1947، هي خوارزمية أساسية لحل مسائل البرمجة الخطية. تستكشف بشكل منهجي رؤوس المنطقة الممكنة لإيجاد الحل الأمثل حيث يتم تعظيم أو تقليل دالة الهدف مع مراعاة القيود الخطية.

الفكرة الحدسية وراء الطريقة

تعمل الطريقة عن طريق البدء من نقطة ركنية (رأس) للمنطقة الممكنة المحددة بالقيود الخطية، ثم الانتقال إلى الرؤوس المجاورة التي تحسن قيمة دالة الهدف. تستمر حتى الوصول إلى رأس لا يوفر فيه أي رأس مجاور تحسنًا إضافيًا، مما يضمن الأمثلية. تستغل الخوارزمية الخاصية الهندسية المتمثلة في أن مسائل البرمجة الخطية لها حلولها المثلى عند رؤوس متعدد السطوح للقيود.

التاريخ

قدم جورج دانتزيغ الطريقة السيمبلكس في عام 1947، مما أحدث ثورة في بحوث العمليات وأصبحت الخوارزمية القياسية للبرمجة الخطية لعقود. أظهر كلي ومينتي (1972) التعقيد الأسي في أسوأ الحالات، ومع ذلك ظلت الطريقة سريعة تجريبيًا. شهدت الثمانينيات تطوير طرق النقطة الداخلية كبدائل، لكن الطريقة السيمبلكس ظلت مهيمنة للعديد من التطبيقات العملية نظرًا لقوتها ومتانة تطبيقاتها الحديثة المتطورة.

متى تُستخدم

تطبيق الطريقة السيمبلكس عند حل مسائل البرمجة الخطية ذات المناطق الممكنة المحدودة ودالة هدف خطية. إنها فعالة بشكل خاص للمسائل التي تحتوي على مئات أو آلاف المتغيرات والقيود. تجنب استخدامها إذا كانت المسألة غير خطية أو غير محدودة. قد تُفضل طرق النقطة الداخلية للمسائل واسعة النطاق جدًا.

الحدود والاعتبارات

  • تعقيد زمني أسي في أسوأ الحالات (على الرغم من ندرته عمليًا)
  • يمكن أن يكون أداؤها ضعيفًا على المسائل المنحلة بشدة
  • أقل تنافسية من طرق النقطة الداخلية على المسائل واسعة النطاق جدًا
  • تتطلب أن تكون المسائل في شكل قياسي مع معالجة صريحة للقيود

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

  • ضمان إيجاد الحل الأمثل في وقت محدود لمسائل البرمجة الخطية
  • فعالة عمليًا مع التنفيذ الدقيق ومعالجة الانحلال
  • منفذة على نطاق واسع ومدعومة بمكتبات تحسين ناضجة
  • أساس لفهم خوارزميات التحسين الأكثر تقدمًا

التطبيقات

  • تخطيط الإنتاج: تحسين كميات الإنتاج لتقليل التكاليف مع تلبية قيود الطلب
  • النقل واللوجستيات: تحديد مسارات وكميات الشحن المثلى بين المستودعات ومراكز التوزيع
  • تحسين المحفظة: تخصيص رأس المال عبر الأصول لتعظيم العوائد مع مراعاة قيود المخاطر والميزانية
  • تخصيص الموارد: توزيع الموارد المحدودة مثل العمالة والمواد لتعظيم الإنتاج التنظيمي
  • مسائل المزج: خلط المواد الخام بنسب مثلى لتلبية مواصفات الجودة وتقليل التكلفة
  • جدولة القوى العاملة: تعيين العمال للورديات لتقليل تكاليف العمالة مع تلبية الطلب

كيف يعمل

كيف يعمل

1

تحويل مسألة البرمجة الخطية إلى الشكل القياسي باستخدام متغيرات راكدة، وتحديد حل أساسي ممكن أولي (عادةً الأصل إذا كان ممكنًا).

2

إجراء عمليات المحورية على جدول السيمبلكس: اختيار متغير داخل له تكلفة مخفضة سالبة، وتحديد المتغير الخارج باستخدام اختبار النسبة الدنيا، وتحديث الأساس.

3

التحقق من شروط الأمثلية باستخدام التكاليف المخفضة؛ إذا كانت جميع التكاليف المخفضة غير سالبة للتعظيم، فإن الحل الحالي هو الأمثل؛ وإلا، عد إلى خطوة المحور.

الأخطاء الشائعة

  • الفشل في معالجة الدوران بشكل صحيح عند مواجهة قواعد منحلة (استخدم قاعدة بلاند أو طرق الاضطراب)
  • اختيار محوري غير صحيح أو أخطاء حسابية في تحديثات الجدول تؤدي إلى عدم استقرار عددي
  • عدم التحقق من عدم التحديد أو عدم الإمكانية قبل بدء الخوارزمية

الأسئلة الشائعة

لماذا تسمى الطريقة السيمبلكس بـ 'سيمبلكس'؟

يشير مصطلح 'سيمبلكس' إلى أبسط شكل متعدد السطوح في أي بعد معين. تعمل الخوارزمية عن طريق التحرك على طول حواف ورؤوس متعدد السطوح المحدد بالقيود.

ما الفرق بين الطريقة السيمبلكس وطريقة النقطة الداخلية؟

تبقى الطريقة السيمبلكس على حدود المنطقة الممكنة عند الرؤوس، بينما تعبر طرق النقطة الداخلية عبر الداخل. تتمتع طرق النقطة الداخلية بتعقيد أفضل في أسوأ الحالات، ولكن السيمبلكس غالبًا ما تكون أسرع عمليًا للمسائل متوسطة الحجم.

كيف تتعامل مع عدم الإمكانية أو عدم التحديد؟

استخدم طريقة السيمبلكس ذات المرحلتين: المرحلة الأولى تحل مسألة مساعدة لإيجاد حل أساسي ممكن أو تحديد عدم الإمكانية؛ المرحلة الثانية تطبق الطريقة السيمبلكس القياسية على المسألة الأصلية.

ما هو الانحلال ولماذا هو مهم؟

يحدث الانحلال عندما يكون للحل الأساسي الممكن أكثر من تمثيل أساسي واحد، مما قد يسبب الدوران. تعامل معه باستخدام قاعدة بلاند (اختر المتغيرات حسب ترتيب الفهرس) أو طرق الاضطراب.

طرق ذات صلة

المصادر

  1. Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.

    افتح مرجع DOI
    تم النسخ.
  2. Vanderbei, R. J. (2014). Linear Programming: Foundations and Extensions (4th ed.). Springer.

    افتح مرجع DOI
    تم النسخ.