البرمجة الخطية (LP)

البرمجة الخطية هي صنف المسائل max c^T x s.t. Ax ≤ b, x ≥ 0 في الصورة القياسية، حيث c ∈ R^n متجه التكاليف، A ∈ R^(m×n) مصفوفة القيود، b ∈ R^m متجه الطرف الأيمن، و x ∈ R^n متغيرات القرار الحقيقية المتصلة. منطقة الإمكان X = {x : Ax ≤ b, x ≥ 0} متعدد سطوح محدب، وتبلغ الدالة الخطية أمثلها في رأس (حل أساس ممكن). أسس هذا الفرع جورج دانتزيغ بخوارزمية السمبلكس عام 1947، انطلاقاً من مسائل تخطيط القوات الجوية الأمريكية (ومن هنا جاء مصطلح 'البرمجة' السابق لاستخدامه الحاسوبي). تربط نظرية الازدواجية (von Neumann 1947) كل LP أولي بـ LP مزدوج؛ وتنص نظرية الازدواجية القوية على أنه إذا كان كلاهما ممكناً ومحدوداً فإن قيمتيهما المثلتين متساويتان، وتُقرأ أسعار الظل من متغيرات الازدواج. التعقيد: أثبت Klee و Minty (1972) أن السمبلكس أُسي في أسوأ الحالات؛ قدم Khachiyan (1979) أول خوارزمية متعددة الحدود لـ LP عبر طريقة القطع الناقص (نظرية)؛ أدخل Karmarkar (1984) طريقة النقطة الداخلية التي تجمع بين الزمن متعدد الحدود والكفاءة العملية. تجمع الحلول الحديثة بين السمبلكس المعدل والنقطة الداخلية، مع المعالجة المسبقة وتحليل LU المتفرق والبدء السريع، وتحل مسائل بملايين المتغيرات في ثوانٍ. التطبيقات: تخطيط الإنتاج، مسائل الخلط، النقل، إدارة التدفق النقدي، ومسألة الحمية الغذائية.