بحوث العمليات-الجزء الثاني

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

II – 1 مقدمة
رأينا في الفصل الأول من هذا الكتاب أنه يمكن اتخاذ أي قرار على مرحلتين رئيستين الأولى هي صياغة المسألة وفق علاقات رياضية يطلق عليها اسم النموذج الرياضي، و الثانية هي حل النموذج الرياضي و البحث عن أفضل الحلول و تطبيقها على المشكلة الحقيقية. و هذا يكون ممكناً باستخدام طرق البرمجة الرياضية. فماذا نعني بالبرمجة الرياضية؟
- II 2 البرمجة الرياضية Mathematical Programming
إن مسألة البرمجة الرياضية تعني – بشكل عام – البحث عن القيمة المثلى (صغرى أو عظمى ) لتابع جبري يضم عدة متغيرات . تخضع هذه المتغيرات لمجموعة من القيود تأخذ صيغة مساويات أو متراجحات .
• حيث X شعاع مركباته وهذه المركبات هي مجاهيل المسألة .
• التابع هو التابع الذي نرغب بإيجاد قيمته المثلى (عظمى أو صغرى) ويدعى تابع الهدف .
• مجموعة المتراجحات ، ومجموعة المساويات هي توابع معرفة في الفضاء وتدعى قيود المسألة .
• نسمي مجموعة الأشعة والتي تحقق جميع قيود المسألة بالحلول الممكنة . ونسمي المنطقة التي تحوي مجموعة الحلول الممكنة بمنطقة الإمكانيات.
• نسمي الشعاع الذي يحقق جميع قيود المسألة ويبلغ التابع فيه قيمته المثلى بالحل الأمثل .
إن حل مسألة البرمجة الرياضية يتطلب إذاً إيجاد الشعاع الذي يحقق جميع القيود ويُبْلِغ تابع الهدف قيمته المثلى .
ملاحظة “ 1 “ :
إن كلمة برمجة لم يكن لها علاقة بالحاسبات الإلكترونية في بادئ الأمر وإنما كانت تعني التخطيط . وهذا البرنامج الرياضي هو نموذج رياضي لمسألة ما .
II – 3 البرمجة الخطية Linear Programming
في مسألة البرمجة الرياضية ، إذا كان تابع الهدف ومجموعة القيود جميعها من الدرجة الأولى للمتحولات فإن البرنامج الرياضي يدعى برنامجاً خطياً . وتعد البرمجة الخطية من أوائل مواضيع بحوث العمليات. وقد بدأ بعرض مواضيعها العالم G-Stiegler بُعيد الحرب العالمية الثانية ، عندما حاول مقارنة الحد الأدنى لتكاليف المعيشة في ألمانيا قبل الحرب وبعدها ، فحصل على مسألة برمجة خطية .
إن تعبير البرمجة يعني وضع خطوات لحل مسألة ما لبلوغ هدف معين. أما تعبير خطية فيعني افتراض تغير الظاهرة التي نقوم بدراستها بصورة خطية (على شكل خط مستقيم) و كثيراً ما يستخدم هذا الافتراض لتقريب الواقع إلى صيغة رياضية سهلة.
تعد البرمجة الخطية احدى الوسائل المهمة في حل كثير من المشاكل الإدارية والاقتصادية و العسكرية، و قد ازداد تطبيقها في الآونة الأخيرة نظراً للتقدم التقني الذي ساعد على تطوير الحاسبات الالكترونية المستخدمة في حل مشاكل البرمجة.
II – 4 البرمجة غير الخطية Non-Linear Programming
إذا كان تابع الهدف أو أحد قيود مسألة برمجة رياضية من الدرجة الثانية فما فوق بالنسبة للمتحولات فإننا ندعوها مسألة برمجة غير خطية .
لقد عولجت مسائل البرمجة غير الخطية باستخدام طرق تقليدية قدمها رياضيو القرن السابع عشر والثامن عشر ( لاغرانج و نيوتن ، ... ) .
أما القفزة العظمى في هذا المجال ، فكانت عام 1951 عندما توصل كين– تيوكر ( Khun-Tuker ) إلى إضافة شروط جديدة على أسلوب مضاريب لاغرانج ، مما أدى إلى السيطرة على معظم مشاكل البرمجة غير الخطية .
II – 5 صياغة النماذج الرياضية
إن أهم مرحلة في البرمجة الخطية هي مرحلة إنشاء نموذج البرمجة الخطية، و نعني التعبير عن علاقات واقعية بعلاقات رياضية مفترضة و مبنية على دراسة الواقع وتحليله. من أجل صياغة نموذج البرمجة الخطية يجب توافر ثلاث مجموعات من العناصر الأساسية وهي:
• تحديد الهدف بصورة كمية. و يعبر عنه بتابع الهدف و هو عبارة عن التابع المطلوب إيجاد القيمة العظمى (أو الصغرى) له. يجب أن يكون بالإمكان التعبير عن الهدف كمياً كأن يكون الهدف تحقيق أكبر ما يمكن من الربح أو تأمين أصغر ما يمكن من الكلفة أو توفير أعظم ما يمكن من الوقت و الجهد.
• تحديد القيود. يحب أن تكون الموارد المتاحة محددة، كما يجب أن تكون تلك الموارد قابلة للقياس. و يتم التعبير عنها بصيغة رياضية على شكل متراجحات أو مساويات.
• تحديد البدائل المختلفة. و يشير هذا العنصر إلى أن يكون للمشكلة أكثر من حل واحد حتى يمكن تطبيق البرمجة الخطية. إذ لو كان للمشكلة حل واحد لما كانت هناك ضرورة لاستخدام البرمجة الخطية، إذ إن فائدتها تتركز في المساعدة على اختيار أفضل حل من بين الحلول المختلفة و المتعددة.
II – 6 أمثـلـة Examples
سنذكر فيما يأتي بعض الأمثلة البسيطة من مسائل اقتصادية تؤدي نمذجتها إلى برامج خطية .
مثـال “ 1 “ :
يقوم مصنع للألبسة بإنتاج أربعة أصناف من الملبوسات ( S4 , S3 , S2 , S1 ) ويستخدم من أجل ذلك المواد الأولية الآتية ( M3 , M2 , M1 ) . ترغب إدارة المصنع في دراسة التنظيم الأمثل للإنتاج خلال فترة زمنية ( شهر مثلاً ) وتحديد الإنتاج الشهري لكل منتوج من أجل تحقيق ربح أعظمي ، علماً بأن الربح يتناسب طرداً و عدد الوحدات المباعة من المنتوجات . نرتب المعلومات التي حصلنا عليها وفق الجدول الآتي :
المواد الأولية نـوع المنـتـج الكميات المتوافرة
S1 S2 S3 S4
M1 1.5 1 2.4 1 2000
M2 1 5 1 3.5 8000
M3 1.5 3 3.5 1 5000
ربح واحدة المنتج 5.24 7.3 8.34 4.18
نلاحظ أن هذا الجدول يوضح ما يأتي :1. الكميات المتوافرة من كل مادة أولية خلال الفترة الإنتاجية (شهر في مثالنا).
2. مقدار ما يلزم من كل مادة أولية في إنتاج واحدة منتج ( دستة مثلاً ) من كل من المنتوجات الأربعة.
3. الربح الناتج عن بيع واحدة المنتج من كل من المنتوجات الأربعة .
لنفرض أن x1 هو عدد الوحدات المنتجة من الصنف الأول S1 خلال الفترة الإنتاجية ( شهر في مثالنا ) . لنفرض أن x2 هو عدد الوحدات المنتجة من الصنف الثاني S2 خلال الفترة الإنتاجية ( شهر في مثالنا ). لنفرض أن x3 هو عدد الوحدات المنتجة من الصنف الثالث S3 خلال الفترة الإنتاجية ( شهر في مثالنا ). لنفرض أن x4 هو عدد الوحدات المنتجة من الصنف الرابع S4 خلال الفترة الإنتاجية ( شهر في مثالنا ).
إن الكميات المتوافرة من المواد الأولية هي مقادير محدودة ، و من ثم فإننا لا نستطيع زيادة الإنتاج بشكل عشوائي لأي منتج ، وإنما يجب توزيع الإنتاج بين الأصناف الأربعة بحيث يكون الربح أعظمياً و من غير تجاوز الكميات المتوفرة من كل مادة أولية من المواد الثلاث . كما أنه لا يمكن قصر الإنتاج على صنف واحد أو صنفين من الإنتاج فقط ، وذلك لضرورات السوق أو لتحقيق توازن في استهلاك المواد الأولية .
نلاحظ أنه يتم استهلاك كمية من المادة الأولية M1 في إنتاج الأصناف الأربعة من الملابس
اي انه يلزم كمية قدرها 1.5 من أجل إنتاج واحدة منتج من الصنف الأول ، علماً بأنه يتم إنتاج كمية قدرها x1 من الصنف الأول S1 . كما يلزم كمية قدرها 1 من أجل إنتاج واحدة منتج من الصنف الثاني ، علماً أنه يتم إنتاج كمية قدرها x2 من الصنف الثاني S2 . وهكذا بالنسبة لبقية الأصناف . ولكن مجموع ما يلزم من المادة الأولية M1 في إنتاج الأصناف الأربعة لا يمكن أن يتجاوز 2000 ( المقدار المتوافر من هذه المادة )
بالإضافة إلى ذلك ، فإنه لا يمكن إنتاج كميات سالبة ، فإما أن ننتج كمية موجبة من أي صنف أو ألا ننتج أي كمية على الإطلاق . وهو ما يسمى بشروط عدم السلبية .
بهذا نكون قد حددنا جميع القيود المفروضة على متحولات المسألة .
واضح أنه إذا تم إنتاج واحدات قدرها x4 , x3 , x2 , x1 من الأصنافS4 , S3 , S2 , S1 على الترتيب ، فإن الربح خلال الفترة الإنتاجية سوف يمثل تابع الهدف .
نرغب الآن في إيجاد قيم المنتوجات x4 , x3 , x2 , x1 التي تحقق القيود وتجعل الربح أعظم ما يمكن .