البرمجة الخطية – مقدمة…….Linear Programming

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

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

ربحية المؤسسة = عدد القطع المباعة x  ربحية القطعة

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

البرمجة الخطية

هناك نوعية من القرارات تهدف إما إلى تعظيم maximize متغير ما مثل الربحية أو تصغير minimize متغير ما مثل التكلفة أو الوقت، وهذا أمر يسير ما لم تكن هناك أمور تحد من قدرتنا على التعظيم او التصغير وهذه الامور تسمى بالقيود constraints مثل وقت محدود للتصنيع أو توفر الخامات بكمية محددة. إذا أمكن التعبير عن هذه الأمور كلها بمعادلات خطية فإن هذه المسألة يمكن حلها عن طريق حل مجموعة معادلات وهو ما يعرف بالبرمجة الخطية Linear Programming.

ما معنى معادلة خطية؟ المعادلة الخطية هي معادلة لا تحتوى على متغير مضروبا في نفسه أو في متغير آخر. فالمعادلات الآتية تعتبر معادلات خطية:

س + ص =500

س <  1000

3س +  2 ص + 5 ع    > 300

جميع هذه المعادلات عندما نرسمها تعبر عن خط مستقيم وهذا هو معنى “خطية” Lineare

أما المعادلات الآتية فهي غير خطية:

س ص +1 = 100

س ² <100

3 س ² + س ²  = 950

هذه المعادلات تعبر عن خطوط منحنية ولذلك تسمى “غير خطية” Non Linear

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

مثال: شركة تنتج منتجين أ و ب، وربحية كل منتج هي 100 و 120 على التوالي، وكلا من المنتجين يتم تصنيعه باستخدام ماكينتين والوقت المتاح على كل منهما هو 1500 ساعة سنويا، ويستغرق تصنيع منتج أ وب على الماكينة الاولى  ساعتين، 4 ساعات على التوالي، ويستغرق تصنيع منتج أ وب على الماكينة الثانية ساعتين ونصف، 3 ساعات على التوالي. المطلوب تحديد كمية إنتاج كل منتج بما يُحقق أعلى ربحية. يُلاحظ اننا نفترض ضمنيا وجود طلب كبير على كل منتج.

يمكننا صياغة المشكلة كالتالي:

الربحية =  100 س + 120 ص

القيود:

تشغيل الماكينة الاولى:       2 س + 4 ص <= 1500

تشغيل الماكينة الثانية:       2.5 س + 3 ص <= 1500

تسمى معدلة الربحية دالة الهدف Objective Function وهي تهدف هنا لتعظيم الربحية، أما المعادلات الأخرى فهي معادلات أو دوال (جمع دالّة)  الفيود Constraints، كما يسمى س و ص بمتغيرات القرار Decision variables وهي المتغيرات التي يريد متخذ القرار تحديد قيمتها. هذه هي مسألة برمجة خطية، ولهذه لمسألة أشباه كثيرة.

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

يمكنك وضع المشكلة في إكسل بأي شكل يريحك، وسوف أعرض الشكل الذي أراه بسيطا لأنه يُشبه شكل المعادلات.

لقد سجلت كل معادلة في سطر، ففي السطر رقم 44 سجلت ربحية كل منتج، وفي السطر رقم 7 و 8 سجلت معادلة ساعات تشغيل كل ماكينة. ولكن أين س و ص التي هي متغيرات القرار؟ سوف نعتبر أن س هي الخلية B5 وأن ص هي الخلية  C5. علينا الآن أن نستكمل المعادلات باستخدام دالة من إكسل تسمى sumproduct وهي تقوم جمع حاصل ضرب عدة خلايا في بعضها. ففي العمود F نسجل حاصل ضرب س و ص في معاملاتها في كل المعادلات. ففي F5 نسجل حاصل جمع 100 س + 120 ص، وفي F7 نسجل حاصل جمع 2 س +4 ص، وفي F8 نسجل حاصل جمع 2.5 س + 3 ص. لاحظ ان B5:C5 تمثل س و ص واما B4:C4 فتمثل ربحية كل منتج وهي 100 و 120. كان من المكن أن نستخدم =B5*B4+C5*C4 وهكذا، ولكن استخدام sumproduct أسهل خاصة عند كثرة المتغيرات فهي تجعلنا نضرب مجموعة خلايا فيما يناظرها دون ان نكتب أسماء كل الخلايا بل نكتب أول وآخر خلية فقط.

علينا الآن أن نجعل هذه الأرقام تتحول لمشكلة برمجة خطية في إكسل، ولذلك علينا استخدام ما يسمى بوسيلة الحل Solver الذي قد يكون غير مضاف على إكسل ويمكنك إضافته كالتالي:

1- ميكروسوفت 2007 و 2010:  File…..Options……Add-ins   ثم اختر Go أسفل الصفحة المجاور لـ Manage Excel Add-ins

بعدئذ اختر Solver Add-in وأنصحك باختيار Analysis Toolpak لأنك ستحتاجها في بعض الأساليب الإحصائية.

2- ميكروسوفت ما قبل 2007: من قائمة Tools اختر Add-ins ثم اختر Solver Add-in.

هذه العملية تقوم بها مرة واحدة ولا تحتاج لتكرارها حيث يظل solver متاحا على جهازك.

نعود للمسألة فنختار قائمة data فنجد solver على االيمين.

نختار solver فيظهر لنا نافذة نقوم بإدخال المعادلات بها:

ثم نقوم بإدخال الخلية التي تحتوي على دالة الهدف وهي هنا F5، ثم نحدد الخلايا لاتي سيقوم إكسل بتغييرها لتعظيم دالة الهف وهي هنا B5  و C5 أي س و ص،

ثم نُدخل معادلات القيود بالضغط على Add على اليمين فيظهر لنا نافذة نملؤها كما يلي:

ثم نختار Simplex في Select Solving Method. ثم نضغط Solve فيظهر لنا الحل هكذا:

نضغط OK فتظهر لنا البيانات كلها كالتالي:

هذا يعني أنه يمكننا تحقيق أعلى ربحية إذا أنتجنا من منتج أ 375 قطعة ومن منتج ب 187 قطعة.

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

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

موضوعات ذات صلة:

شجرة القرار

مصفوفة القرار

البرمجة الخطية -2

حجم الطلبية الاقتصادي EOQ

مخططات لدراسة العمليات -5

نظرية الطوابير -1

الإعلان