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

Linear Programming

البرمجة الرياضية:

تنقسم البرمجة الرياضية إلى عده أقسام وهى:

1- البرمجة الخطية Linear Programming (LP)

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

2- برمجة الأهداف  (Goal Programming) (GP)

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

3- البرمجة الصحيحة Integer Programming (IP)

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

أ) البرمجة الصحيحة العامة :General Integer Programming

    وهى التى تكون جميع متغيرات القرار فيها فى صورة صحيحة.

ب) البرمجة الصحيحة الثنائية: Binary Integer Programming

     وهى التى يمكن أن تكون فيها متغيرات القرار إما صفر أو واحد.

جـ) البرمجة الصحيحة المختلطة Mixed Integer:

       وهى التى تحتوى على خليط من المتغيرات ذات الطبيعة الصحيحة        والكسرية.

4- البرمجة غير الخطية Non-Linear Programming (NLP) يعتبر البرنامج غير خطى إذا تم صياغة علاقة أو أكثر من العلاقات فى صورة غير خطية ويمكن حله باستخدام حساب التفاضل للحصول على قيم متغيرات القرار التى تعظم أو تخفض دالة الهدف .

5- البرمجة التربيعية Quadratic Programming (QP)

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

6- البرمجة العشوائية أو الاحتمالية Stochastic Programming (SP)

وفى البرمجة العشوائية يتم وصف مؤشر أو أكثر من مؤشرات النموذج باستخدام متغيرات عشوائية –احتمالية-، ومن الطريق المعروفة للحل طريقة Chance Continues Programming حيث تقدر البرمجة العشوائية المقيدة القيم المتوقعة لدالة الهدف ومعاملات متغيرات القرار من القيود الهيكلية أو الطرف الأيمن لها أو كليهما كمتغيرات عشوائية ذات توزيعات احتمالية معينة.

7- البرمجة الديناميكيةDynamic Programming (DP) 

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

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

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

-    تعظيم الربح: حيث يعتبر الربح متغيراً تابعاً يتعمد فى تغيره على مجموعة من المتغيرات المستقلة المحددة بمجموعة من القيود.

-    تخفيض التكلفة: حيث تعتبر التكلفة متغيراً تابعاً يتعمد فى تغيره على مجموعة من المتغيرات المستقلة المحددة بمجموعة من القيود.

ويفترض أن العلاقة التى تربط بين المتغير التابع ومجموعة المتغيرات المستقلة هى علاقة خطية حيث يتم التعبير عنه من خلال المعادلة التالية والتى يطلق عليها دالة الهدف Objective Function

ص= أ­­₁ س­₁ + أ₂ س₂ + ...................+ أ_نس_ن

حيث:

      أ­­₁  ،   أ_{2   ،} ........، أ_{ن هى معاملات للمتغيرات المستقلة تكون ذات قيم ثابتة}

_{كما يلاحظ :}

_{1-        أن المعادلة خطية لأن المتغيرات المستقلة جمعيها مرفوعة للقوة (1).}

_{2-        أن المتغيرات المستقلة المحددة للمتغير التابع محددة بقيود وهذه القيود تأخذ شكل المتباينات ( عدم التساوى).}

أ­­₁ س­₁ + أ₂ س₂ + ...................+ أ_نس_{ن  ≥}   ب

أ­­₁ س­₁ + أ₂ س₂ + ...................+ أ_نس_{ن  ≥} ب

_{حيث  ب: القيد المفروض على المتغيرات المستقلة والذى بدوره يمثل قيداً على المتغير التابع ص.}

مجالات تطبيق البرمجة الخطية:

1-     الصناعة :

 لوضع جدول إنتاج وسياسة مخزون لمقابلة الطلب مستقبلاً ، حيث تكون الأمثلية أن يقابل كل من الجدول والسياسة الطلب ، وفى الوقت نفسه تخفض تكاليف الإنتاج والمخزون إلى أدنى حد ممكن .

2-     التحليل المالى:

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

3-    التسويق:

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

4-     توزيع ونقل البضائع:

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

متطلبات استخدام أسلوب البرمجة الخطية:

1-       وجود مشكلة تهدف إلى تعظيم أو تدنية بعض القيم أو الكميات، مثل تعظيم الربح أو تدنية التكاليف.

2-                 وجود مجموعة من القيود المفروضة على الهدف.

3-                 توافر عدة بدائل لحل المشكلة من أجل الاختيار بينها.

4-                  التعبير عن دالة الهدف والقيود فى شكل متباينات خطية.

الافتراضات الأساسية لنموذج البرمجة الخطية:

1-       وجود حالة من التأكد التام فيما يتعلق بقيم دالة الهدف أو القيود ، بمعنى عدم وجود قيم احتمالية.

2-                 ثبات معاملات المتغيرات المستقلة فى كل من دالة الهدف والقيود.

مثال ذلك: إذا كانت وحدة المنتج س تحتاج 3 ساعات لإنتاجها ، فإن إنتاج 10 وحدات يحتاج 30 ساعة ، وأن إنتاج 20 وحدة يحتاج 60 ساعة وهكذا.

3-       وجود خاصية الجمع ، مثال ذلك: أن الربح الكلى هو مجموع أرباح المنتجات المباعة ، فإذا كان ربح الوحدة من المنتج (س₁) 10 جنيهات وربح الوحدة من المنتج (س₂) 15 جنيهاً ، فإن بيع وحدة واحدة من كل من المنتجين يعنى تحقيق ربحاً قدره 25 جنيهاً .

4-       امكانية التقسيم  أو التجزئة ، بمعنى أن الحلول الممكنة لا يجب بالضرورة أن تكون قيماً صحيحة، حيث يمكن تواجد قيم كسرية بينها.

5-       وجود شرط عدم السالبية فى الحلول النهائية للمشكلة ، حيث لاتوجد قيم سالبة للأشياء المادية مثل عدد الوحدات أو عدد المنتجات....).