البرمجة الخطية الصيغة العامة _بحوث العمليات

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

2 – 1 المقدمة Introduction
تعتبر البرمجة الخطية أحدى نماذج البرمجة الرياضية التي تعالج مسألة تخصيص أو توزيع الموارد أو الطاقات المحدودة لتحقيق هدف معين ويعبر عن هذا الهدف بدالة خطية مستخدمة لوصف العلاقة بين متغيرين أو أكثر وهذه العلاقة مباشرة وتتغير بنفس النسبة أي عند تغير ساعات الأنتاج بنسبة 10% فأن الأنتاج يتغير بنسبة 10% أيضاً.
تكمن أهمية البرمجة الخطية كونها أحدى الوسائل المستخدمة في دراسة سلوك عدد كبير من الأنظمة, كما وتستخدم في معالجة كثير من مشكلات البرمجة الصناعية والحكومية المعقدة. وتعتبر البرمجة الخطية من الأساليب الرياضية التي تهدف للوصول الى تحقيق الأمثلية والذي بموجبه يتم تخصيص الموارد المحدودة من أجل تحقيق الهدف المحدد. يستخدم نموذج البرمجة الخطية بشكل واسع لحل المشاكل التي تواجه منظمات الأعمال في مجالات كثيرة كالأنتاج والتوزيع والنقل وكثير من الأنشطة المختلفة لغرض تعظيم (Maximize) الأرباح أو العوائد وتقليل (Minimize) الخسائر والتكاليف.
مثال (2 - 1): تقوم أحدى الشركات بأنتاج نوعين من المعدات (A & B), وتحقق الشركة ربحاً قدره (10000) دينار في الوحدة الواحدة من المنتوج (A), و (15000) دينار في الوحدة الواحدة من المنتوج (B), علماً بأن الشركة تحتاج الى (20) ساعة لأنتاج وحدة واحدة من منتوج (A) و (30) ساعة لأنتاج وحدة واحدة من (B), وأن الوقت الأجمالي المسموح العمل به سنوياً (1200) ساعة كما أن الطلبات التي يمكن توقعها على المنتوجين يتوقف على قدرة الشركة على الأنتاج, وتوجد أمكانية أنتاج كمية من (B) لا تزيد عن (40) وحدة والكمية المنتجة من (A), لا تزيد عن (30) وحدة في السنة. ما هو العدد الأمثل من الوحدات المنتجة من كل نوع بحيث تعظم أرباح الشركة عن أنتاجها السنوي.
الحل:
لصياغة نموذج رياضي لهذا المثال نلاحظ ما يأتي:
نفترض أن عدد الوحدات المنتجة من المنتوج (B) هو:
x_1,? x?_1?0
نفترض أن عدد الوحدات المنتجة من المنتوج (A) هو:
x_2,? x?_2?0
دالة الهدف objective function
max??x_0 ?=10000x_1+15000x_2
القيود Constraints
20 x_1+30 x_2=1200 الأنتاج ساعات
x_1?40
x_2?30
x_1,x_2?0
مثال (2 - 1): نموذج رياضي
ينتج أحد المصانع ثلاثة نماذج (I,II,III) من منتج معين, بأستخدام نوعين من مواد الخام (A & B), والكمية المتاحة من كل نوع هي (2000) وحدة من المادة الخام (A) و (3000) وحدة من المادة الخام (B). والجدول التالي يبين الكميات المطلوبة من كل نوع من الخامات لأنتاج المنتجات الثلاث.
المتطلبات لكل وحدة من أنواع النماذج الثلاث المواد الخام
III II I
5 3 2 A
7 2 4 B

أذا كان الوقت المطلوب لكل وحدة من النموذج الأول هو ضعف الوقت المطلوب للوحدة من النموذج الثاني وثلاثة أمثال الوقت المطلوب للوحدة من النموذج الثالث. أن الطاقة التشغيلية للمعمل تستطيع أن تنتج ما يكافئ (700) وحدة من النموذج الأول, وأشارت دراسة السوق الى أن الحد الأدنى المطلوب من كل نوع هو (150, 200, 200) وحدة على التوالي, بالرغم من ذلك أن نسبة الوحدات المصنعة يجب أن تكون بالترتيب (3: 2: 5) فإذا كان ربح الوحدة الواحدة من النوع الأول (300) دينار والثاني (200) والثالث (500). أكتب المسألة بصورة نموذج برمجة خطية لتحديد عدد الوحدات المصنعة من كل نموذج بحيث تحصل الشركة على أعظم ربح ممكن.
الحل: النموذج الرياضي
نفرض أن (x_1) عدد وحدات المنتج الأول(I).
نفرض أن (x_2) عدد وحدات المنتج الأول(II).
نفرض أن (x_3) عدد وحدات المنتج الأول(III).
دالة الهدف objective function
max??x_0 ?=300x_1+200x_2+500x_3
القيود Constraints
2x_1+3x_2+5x_3?2000 A النوع من الخام المواد

4x_1+2x_2+7x_3?3000 B النوع من الخام المواد
قيد الوقت
x_1+0.5x_2+1/3 x_3?700
قيد العمل
x_1/3=x_2/2=x_2/5
متطلبات السوق من المنتجات
x_1?200
x_2?200
x_3?150
مثال (2 - 2):
تقوم أحدى الشركات بوضع خطة لاستيراد ثلاثة أنواع من السلع لغرض تسويقها في السوق المحلي علماً بأن نفقات الشراء والنفقات الأخرى موضحة في الجدول التالي:
المبالغ المخصصة المبالغ بالآف الدنانير النفقات
السلعة الثالثة السلعة الثانية السلعة الأولى
=40000 1 2 2 نفقات التسويق
?30000 2 1 2 نفقات أدارية
?100000 2 2 4 نفقات متنوعة
6 4 5 سعر الشراء

المطلوب: تحديد الحجم الأمثل للأستيراد والذي يحقق أقل كلفة ممكنة.
الحل: نفرض أن:
x_1 : عدد الوحدات للسلعة الأولى.
x_2 : عدد الوحدات للسلعة الثانية.
x_3 : عدد الوحدات للسلعة الثالثة.
دالة الهدف objective function
Min??x_0 ?=5x_1+4x_2+5x_3
Subject to:
2x_1+2x_2+x_3=40000
2x_1+x_2+2x_3?30000
4x_1+2x_2+2x_3?100000
x_1,x_2,x_3?0
وسيتم لاحقاً توضيح كيفية حل هذه المسائل من البرامج الخطية.
2 – 2 فرضيات البرمجة الخطية Linear Programming Hypothesis
لغرض بناء نموذج رياضي دقيق ومعتمد, يجب توفر الشروط التالية:
1 - تعظيم (Maximize) الأرباح أو العوائد وتقليل (Minimize) الخسائر والتكاليف.
2 – وجود بدائل مختلفة للوصول إلى الهدف.
3 – أن تكون الموارد المستخدمة محدودة لأن طريقة البرمجة الخطية تتمثل في كونها طريقة علمية تهدف إلى استخدام الموارد المحدودة أفضل استخدام لتحقيق هدف معين, ونقصد هنا بالموارد, عدد ساعات التشغيل, المواد الخام, الأيدي العاملة, كمية المبالغ المستثمرة, وغيرها من الموارد.
4 – التأكد (certainty): يجب أن تكون هنالك علاقة بين المتغيرات أي توفر عنصر التأكد وغياب الاحتمالات, وأن تكون قيود النموذج معروفة وثابتة أثناء فترة معالجة المشكلة المدروسة.
5 – الخطية (linearity ): وهو التعبير عن دالة الهدف والقيود بمعادلات أو متباينات خطية.
6 – التناسبية (proportionality): أي أن تكون مساهمة العوامل في دالة الهدف والكميات المستخدمة من الموارد في القيود متناسبة مع قيمة كل متغير من المتغيرات القرارية.
7 – عدم وجود تداخل بين الأنشطة المختلفة.
8 – أن تكون قيم القرارات موجبة (x_j?0).