شرح كامل عن البرمجة الخطية 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 قطعة.

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

نتعرف على فوائد أكثر للبرمجة الخطية، كما نتعرف على استخداماتها في التجارة.

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

1- ثمن شراء كل سلعة على التوالي: 10، 12، 9

2- المخزون الحالي من كل سلعة على التوالي: 30، 20، 70

3- حدَّدَ المالك المخزون الأقصى لكل سلعة طبقا لطلب السوق كالتالي: 200، 220، 270

4- هناك علاقة بين مبيعات أ و ب ولذلك فإن مجموعهما ينبغي ألا يزيد عن 350

5- يريد المالك ألا يقل مخزون أي سلعة بعد الشراء عن 70 قطعة لكي يظل منافسا في المنتجات الثلاث

6- السيولة المتوفرة للشراء هي: 5500 جنيه

7- ثمن بيع كل سلعة على التوالي: 14، 15، 12

نبدأ في صياغة المسألة كالتالي:



س: عدد القطع الني سيشتريها من المنتج أ

ص: عدد القطع الني سيشتريها من المنتج ب

ع: عدد القطع الني سيشتريها من المنتج ج

دالة الهدف هي تعظيم الربحية كالتالي:

الربح = ربحية كل قطعة x عد دالقطع = 4 س + 3 ص + 3 ع

لاحظ أن الربحية = ثمن البيع – ثمن الشراء ……. (مع إهمال المصاريف للتبسيط)

القيود:

الحد الأدنى لشراء أ = 70 -30 = 40

الحد الأقصى لشراء أ = 200 – 30 =170

40 => س =< 170

الحد الأدنى لشراء ب = 70 -20 = 50

الحد الأقصى لشراء ب = 220 – 20 =200

50 => ص =< 200

الحد الأدنى لشراء ج = 70 -70 = 0

الحد الأقصى لشراء ج = 270 – 70 = 200

0 => ع =< 200

ينبغي ألا يزيد مجموع المنتجين أ و ب عن 350. أي (س+ مخزون أ + ص + مخزون ب) ينبغي ألا يزيد عن 350

س + 30 + ص + 20 =< 350

أي

س + ص =< 300

ينبغي ألا يتجاوز ثمن شراء كل لمنتجات 5500 جنيه

10 س + 12 ص + 9 ع =< 5500

نبدأ في وضع المسألة في إكسل كالتالي:

لاحظ أن الخلايا B5، C5، D5 هي س، ص، ع. الحد الادنى والأقصى لشراء كل سلعة تم وضعه على خطوتين للتوضيح ولكي لا تختلط المعادلات. العمود G يبين المعادلات المستخدمة وذلك باستخدام خاصية إظهار المعادلات وإنما ستكون قيمتهم في البداية صفرا.

نبدأ في الحل باستخدام Solver، وإن لم يكن ظاهرا في الشاشة عند اختيار قائمة Data فعليك بإضافته كما في المقالة السابقة.

لاحظ أن القيود تم وضعها بشكل مجمع حيث من الممكن أن نجمع عدة قيود إذا كانوا متتاليين في الترتيب وكلهم يحتوى نفس المقارنة مثل > أو <. ويمكن وضع كل واحد على حدة حسبما تريد.

نحصل على الحل كالتالي:

الحل الأمثل هو شراء 170 من أ و 130 من ب و200 من ج. لاحظ ان كل القيود تحققت. بهذا نكون قد حصلنا على الحل الأمثل.

نفترض أنه كان لدينا قيدا آخر وهو السعة التخزينية التي لا تتجاوز 600 متر مكعب، علما بأن حجم كل السلع على التوالي هي: 1، 1.2، 1.1 متر مكعب.

يمكننا أن نضيف هذا القيد كالتالي: (س + 30) + 1.2 (ص+ 20) + 1.1 ( ع + 70 ) <= 650

أي:

س + 1.2 ص + 1.1 ع <= 519

وبهذا تصبح المسألة والحل كالتالي:

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

ما هي القيود الحاكمة لهذا الحل؟ أي ما الذي إذا تغير فإن الحل يتغير؟ هل كل القيود أم بعضها؟ يمكننا معرفة ذلك بأن نختار تقرير الحل Answer كما يلي:

فيظهر لنا التقرير في صفحة مستقلة تسمى Answer Report 1 كما يلي:

إن المعادلات في الصفوف: 7، 9، 15 هي حاكمة Binding وهي معادلات: الحد الأقصى لـ س و ع والمساحة التخزينية. هل هذا صحيح؟ نعم فنحن سنشتري الحد الأقصى لكل من س وع، ونحن نستغل كل المساحة التخزينية. معنى هذا أن أي تغير في هذه الشروط ولو بمقدار الواحد الصحيح يعني تغيرا مباشرا في الحل.

ماذا عن باقي الشروط؟ إنها ليست حاكمة أي أنها لو تغيرت فلن يتأثر الحل ولكن في حدود ما، فلو زاد التغير فستصبح مؤثرة في الحل. ما معنى هذا؟ انظر غلى العمود في أقصى اليمين، إنه يسمة Slack أي غير جاد أو أنه مهمل، والقيمة التي أمام كل شرط تعني أن هذا الشرط غير مؤثر حتى يتغير بهذه القيمة. فمثلا شرط الحد الأدنى لـ ص في الصف 11 هو غير مؤثر مالم يزيد بمقدار يزيد عن 57.5، ولو حاولت تغييره بأقل من ذلك فلن يتأثر الحل، ولكن جرب أن تزيده بـ 59 مثلا فستجد قيمة ص أصبحت 109 وستتغير ع إلى 198. وكذلك السيولة فإنها لا تؤثر ما لم تقل بما يزيد عن 710 جنيه. هذه خاصية أخرى من خواص البرمجة الخطية.