البرمجة الخطية (الحل بطريقة السمبلكس)

حل البرمجة الخطية بطريقة السمبلكس The Simplex Method

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

ومهما كان عدد المتغيرات (مئات، آلاف...) فالحل يمكن أن يتوفر في خلال ثواني، ومن أهم هذه البرامج LP ،LINDO.

تسير طريقة السمبلكس بخطوات منتظمة في إيجاد الحل الأمثل. 

ويتم الحصـول على الحل الأمثل بإتباع خطوات معدودة، علماً أن طريقة السمبلكس تشير إلـى نوعية الحلول فيما إذا كانت المسألة بدون حل أمثل أو أن لها حلولاً متعددة.

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

مع اختلاف بسيط وهـو أن المعادلات الخطية للمسألة موضوع الحل تكتب على شكل جدول.

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

لاحظنا عند حل البرنامج الخطي بيانياً أن الحل الأمثل يقع دائماً على أحد النقـاط القصوى Extreme Points والمحددة لمنطقة الحلول الممكنة.

وتعتمـد طريقـة السمبلكس على اختيار نقطة قصوى ممكنة Feasible Extreme Point عـادة تكون نقطة الأصل The Origin Point، وينتقل الحل في عمليات متتاليـة مـن نقطة إلى أخرى أفضل منها حتى يصل إلى النقطة التي تحقـق الحـل الأمثـل.