البرمجة الخطية ، تقنية النمذجة الرياضية التي يتم من خلالها تكبير أو تصغير الوظيفة الخطية عند تعرضها لقيود مختلفة. كانت هذه التقنية مفيدة لتوجيه القرارات الكمية في تخطيط الأعمال ، والهندسة الصناعية ، وبدرجة أقل في العلوم الاجتماعية والفيزيائية.
التحسين: البرمجة الخطية
على الرغم من استخدامها على نطاق واسع الآن لحل مشاكل القرار اليومية ، إلا أن البرمجة الخطية كانت غير معروفة نسبيًا قبل عام 1947. لا يوجد أي عمل ذي أهمية
يقلل حل مشكلة البرمجة الخطية من العثور على القيمة المثلى (الأكبر أو الأصغر ، حسب المشكلة) للتعبير الخطي (تسمى الوظيفة الهدف)
تخضع لمجموعة من القيود المعبر عنها بعدم المساواة:
إن a و b و c هي ثوابت تحددها القدرات والاحتياجات والتكاليف والأرباح والمتطلبات والقيود الأخرى للمشكلة. الافتراض الأساسي في تطبيق هذه الطريقة هو أن العلاقات المختلفة بين الطلب والتوافر خطية. أي ، لا يتم رفع أي من x i إلى قوة أخرى غير 1. من أجل الحصول على حل لهذه المشكلة ، من الضروري إيجاد حل لنظام التفاوتات الخطية (أي ، مجموعة قيم n من المتغيرات x i التي ترضي جميع المتباينات في آن واحد). ثم يتم تقييم الدالة الهدف باستبدال قيم x i في المعادلة التي تحدد f.
تمت محاولة تطبيق طريقة البرمجة الخطية لأول مرة بشكل جدي في أواخر الثلاثينيات من قبل عالم الرياضيات السوفياتي ليونيد كانتوروفيتش والاقتصادي الأمريكي فاسيلي ليونتييف في مجالات جداول التصنيع والاقتصاد ، على التوالي ، ولكن تم تجاهل عملهم لعقود. خلال الحرب العالمية الثانية ، تم استخدام البرمجة الخطية على نطاق واسع للتعامل مع النقل والجدولة وتخصيص الموارد الخاضعة لقيود معينة مثل التكاليف والتوافر. فعلت هذه التطبيقات الكثير لإثبات مقبولية هذه الطريقة ، والتي اكتسبت زخمًا إضافيًا في عام 1947 مع إدخال طريقة الرياضيات البسيط الأمريكية جورج دانتزيغ ، والتي بسطت إلى حد كبير حل مشاكل البرمجة الخطية.
ومع ذلك ، مع محاولة المزيد من المشاكل المعقدة التي تنطوي على متغيرات أكثر ، زاد عدد العمليات الضرورية بشكل كبير وتجاوز القدرة الحسابية حتى أقوى أجهزة الكمبيوتر. ثم ، في عام 1979 ، اكتشف عالم الرياضيات الروسي ليونيد خاتشيان خوارزمية متعددة الحدود الزمنية - ينمو فيها عدد الخطوات الحسابية كقوة لعدد المتغيرات بدلاً من الأس - مما يسمح بحل المشاكل التي لا يمكن الوصول إليها حتى الآن. ومع ذلك ، كانت خوارزمية خاتشيان (تسمى طريقة القطع الناقص) أبطأ من طريقة البسيط عند تطبيقها عمليا. في عام 1984 اكتشف عالم الرياضيات الهندي ناريندرا كارماركار خوارزمية أخرى متعددة الحدود الزمنية ، طريقة النقاط الداخلية ، التي أثبتت قدرتها التنافسية مع طريقة البسيط.
