البرمجة الخطية وطريقة السمبلكس: التطور التاريخي والتطبيقات العملية

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

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

والسؤال كيف يتم الحصول على الحل الأمثل؟

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

• وجود هدف لهذه المسألة (أكبر ربح – أقل خسارة) ويتم التعبير عن الهدف من خلال تابع خطي يسمى تابع الهدف.
• متحولات القرار وهي مجموعة كبيرة من المتغيرات ويجب تحديد قيمتها.
• جميع المتحولات ترتبط بين بعضها من خلال علاقات ارتباط خطي تسمى قيود المسألة مع الأخذ بعين الاعتبار جميع المتغيرات موجبة (شرط عدم السلبية).

صياغة مسألة البرمجة الخطية

مسألة البرمجة الخطية هي مسألة ثنائية تمثل بجدول يتألف من أسطر وأعمدة وتتم الصياغة بالشكل التالي:

1. تحديد عدد المتغيرات (عدد الأسطر) والمتغيرات هي X1,X2,X3,…Xn.
2. تحديد نوع دالة الهدف (max أكبر ربح، أو min  أقل خسارة) ويتم تشكيل دالة الهدف من المتغيرات.
3. تحديد عدد القيود (عدد الأعمدة) وهي متراجحات خطية بالنسبة للمتغيرات، مع قيد عدم السلبية.

طريقة السمبلكس في البرمجة الخطية

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

خطوات طريقة السمبلكس في بحوث العمليات 

حتى تحل مسألة البرمجة الخطية بطريقة السمبلكس، اتبع الخطوات التالية:

• نحول المسألة إلى الصيغة القياسية وذلك بإضافة متغيرات صناعية جديدة لتحويل التراجح إلى مساوة.
• نصفر دالة الهدف (ننقل جميع الحدود إلى طرف واحد).
• نكون جدول أولي لدالة الهدف والقيود بحيث يتألف هذا الجدول من الأعمدة التالية:
  • • العمود الأول: عمود المتغيرات الأساسية (B.V (Basic Variable وهي المتغيرات الصناعية التي نبدأ بها الحل والتي نضيفها لقيود المسألة .(عدد المتغيرات الصناعية بعدد القيود ) وفي الجزء الأسفل من هذا العمود نضع دالة الهدف.
    • العمود الثاني: يضم في جزئه الأعلى جميع رموز متغيرات دالة الهدف بينما معاملات القيود توضع في الجزء الأوسط لهذا العمود ومعاملات متغيرات دالة الهدف توضع في الجزء الأسفل لهذا العمود.
    • العمود الثالث: عمود معاملات الجانب الأيمن (Right Hand Side) نضع فيه جميع قيود المسألة وقيمة دالة الهدف المصفرة.
    • العمود الرابع: هو عمود النسبة Ratio
• نستخرج المتغير الداخلي: هذا المتغير ضمن عمود نسميه العمود الرئيسي ويأخذ أكبر قيمة بالإشارة سالب عندما يكون تابع الهدف max وأكبر قيمة بالموجب لما يكون تابع الهدف min
• نستخرج المتغير الخارج: هذا المتغير موجود ضمن صف نسميه الصف الرئيسي ونحصل عليه بقسمة معاملات عمود الجانب الأيمن على معاملات العمود الرئيسي (عمود المتغير الداخل ) ثم نأخذ أصغر رقم  موجب غير معدوم  ناتج عن القسمة
• إيجاد العنصر المشترك:  هذا العدد الناتج عن تقاطع سطر المتغير الخارج مع عمود المتغير الداخل.

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

• استخراج الحل الأمثل: نحصل على الحل الأمثل من الجدول الأخير عندما يحقق
  • • لما يكون تابع الهدف من نوع max فإن جميع قيم z إما صفر أو موجبة
    • لما يكون تابع الهدف من نوع min فإن جميع قيم z  إما صفر أو سالبة

إذا لم يحقق الجدول الأخير الحل الأمثل نكرر الخطوات من (4) وحتى (7) حتى نحصل على الحل الأمثل.

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

الكاتب: أ. عبد الحميد الديبان مدرس مادة الرياضيات في مبادرة مسارات