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

طريقة السمبلكس هي خوارزمية البرمجة الخطية التي طورها جورج دانتزيغ عام 1947 وهي أساس بحوث العمليات. الفكرة الجوهرية: منطقة إمكان LP في الصورة القياسية max c^T x s.t. Ax = b, x ≥ 0 متعدد سطوح محدب، وتبلغ الدالة الخطية أمثلها عند رأس؛ يقابل كل رأس حل أساس ممكن (BFS) تكون فيه m من المتغيرات الأساسية موجبة و n-m من المتغيرات غير الأساسية صفراً. تسير الخوارزمية كالآتي: (1) إيجاد BFS ابتدائية (بطريقة big-M أو الطريقة ثنائية الطور)؛ (2) حساب التكاليف المخفضة c_j - c_B^T B^(-1) A_j؛ إذا كانت ≥ 0 لكل متغير غير أساسي فإن BFS الحالية مثلى؛ (3) اختيار متغير داخل بتكلفة مخفضة سالبة (قاعدة دانتزيغ: الأكثر سلبية)، تحديد المتغير الخارج باختبار النسبة الأدنى، إجراء التمحور والعودة إلى الخطوة (2). هندسياً، تنتقل الطريقة من رأس متعدد السطوح إلى رأس مجاور. التعقيد: أظهر Klee و Minty (1972) عبر مكعب Klee-Minty أن أسوأ الحالات قد يتطلب 2^n تكراراً (أُسي)؛ غير أن تحليل الحالة المتوسطة والتحليل المنعَّم (Spielman و Teng 2004) يثبتان أن السمبلكس متعدد الحدود في المتوسط، مما يفسر سرعته العملية الباهرة. المتغيرات: (أ) السمبلكس المعدل بتحليل المصفوفة المتفرقة للمسائل الكبيرة؛ (ب) السمبلكس المزدوج (Lemke 1954) يتقدم عبر الإمكانية المزدوجة؛ (ج) سمبلكس الشبكة يحل النقل والإسناد على هياكل شجرية في ثوانٍ. تُمنع الدورة — الحلقة اللانهائية عند رأس مُتدهور — بقاعدة Bland (1977) أو التمحور المعجمي. في حلول LP الحديثة، يقدم السمبلكس جنباً إلى جنب مع طرق النقطة الداخلية ويسود في سياقات البدء الدافئ، خصوصاً ضمن branch-and-cut للـ MILP.