مفاهيم أساسية

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

I-1 تعريف نموذج البرمجة الخطية :

يرجع استخدام نموذج البرمجة الخطية إلى جورج دانتزنج (G.Dantzing) عندما أستخدم أسلوب السمبلكس لحل مشاكل البرمجة الخطية سنة 1947م,و تعرف البرمجة الخطية بأنها :

-       طريقة رياضية فعالة  لاختيار الخطة المثلى , فهي إجراء للبحث عن الحل الأفضل لمشاكل الأعمال التي تتضمن تفاعل متغيرات متعددة, و التي تشمل اختيار أفضل مزيج للموارد التي تؤدي إلى أقصى الأرباح أو أقل التكاليف و يمكن تعريفها أيضا :

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

و تجدر الإشارة هنا إلى أن كلمة برمجة (Programming) ليست لها علاقة ببرمجة الحاسوب, و لكنها تعنيي وضع المشكلة بصيغة رياضية أو نموذج رياضي وحلها و التخطيط لها.

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

من التعريفات السابقة نستخلص أن النماذج الخطية هي :

-       تقنية وطريقة رياضية .

-       مشكلات البرمجة الخطية تهدف إما إلى تدنية أو تعظيم بعض الكميات, و التي عادة ما تكون في صورة تكاليف أو أرباح.

-       تستخدم في حل مشاكل الإدارة التي تتمثل في توزيع الموارد المحدودة على عدد  من الاستخدامات المتباينة

-       تحقق أحسن توزيع للموارد , و يكون بإعطاء الإدارة بالمعلومات التي تمكنها من اتخاذ قرارات أكثر فعالية فيما يتعلق بالموارد التي تحت تصرفها .

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

I-2 فرضيات البرمجة الخطية[1] :

-       وجود هدف نهائي :لبناء مسألة برمجة خطية يجب معرفة هدف المؤسسة و هو تحقيق أكبر ربح أو أقل تكاليف ....

-       وجود قيود معينة على المتغيرات التي يحتويها البرنامج و تؤثر كلها أو جزء منها على الأقل في تحقيق الهدف النهائي.

-       فرضية التأكد التام (Certainty):

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

-       التناسبProportionatity )):

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

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

-        الإضافة (Additivity):

ويعني هذا الافتراض أنه لا يوجد تداخل بين الفعاليات أو الأنشطة المختلفة , وبناء على ذلك فإن هذا الافتراض يتضمن ما معناه أنه لو أخذنا مستويات أو جوانب النشاط (X₁,X₂,……..X_n) , فإن الاستعمال الكلي و لكل مصدر و كذلك معيار الإنجاز الكلي الناتج عن هذه الأنشطة , يساوي مجموع الكميات المتولدة أو الناجمة عن كل النشاطات الفردية, و بشكل مستقل , فإذا كنا ننتج أربعة منتجات و كان الربح الناجم عن بيع وحدة واحدة من كل من هذه المنتجات هو : 6,12,10,8  وحدات نقدية  على التوالي , فإن إجمالي الربح الناجم عن إنتاج و بيع ثلاث وحدات من كل منتج هو (6+12+10+8)3  = 108 وحدات نقدية.

-            قابلية القسمة أو الكسر DivisibilityorFractionality)(

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

-       اللاسلبية (Non-negativity) :

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

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

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

-       تحديد المشكلة و صياغتها .

-       بناء النموذج الرياضي الذي يعبر عن نظام موضوع الدراسة .

-       إيجاد الحل للنموذج أو الحلول الممكنة و اختيار أفضلها .

-       تطبيق الحل المختار إن أمكن.

عناصر نموذج البرنامج الخطي :

-       دالة الهدف : أقصى ربح أو أدنى تكلفة .

-       مجموعة من القيود .

-       شرط عدم السلبية .

I-3 شروط استخدام البرمجة الخطية :

هناك مجموعة من الشروط التي ينبغي توفرها وهي :

-       وجود هدف واضح و محدد و هو مايمثل دالة الهدف و الذي يعبر عن أقصى عائد أو أدنى تكلفة

-       محدودية الموارد.

-       وجود علاقة بين المتغيرات و درجة تحقق الأهداف .

-       إمكانية التعبير عن متغيرات المشكلة بصورة كمية مثلا الكفاءة لا يمكن التعبير عنها بصورة كمية.

-       تعدد البدائل.

I-4 بعض نماذج البرمجة الخطية : Somelinearprogrammingmodel[2]

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

مثال :

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

ثمإنالمبلغالمتوفرهو 18,000,000 دجوساعاتالعمل المتاحة 4500ساعةومساحةالأرضالكليةتبلغ 42,000 مترامربعاً.

إنالصياغةالرياضيةلهذهالمسألةهيكما يلي:

MAX          30X+12Y

S/C 

     شرط عدم السلبية            

وعندحلهذهالمسألةيتبينأنالحلالأمثليتحققعندماX= 15و Y=45

و يتبقى 300 متر مربع دون أن يبنى.

The DietProblemالنموذج الأول : نموذج التغذية

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

لنرمز بـ

a_ij لكمية الفيتامين من النوع i في وحدة الطعام j , و لنرمز ب  b_i لكمية الفيتامين من النوع i التي يجب أن تحتويها الوجبة , و لنرمز بcj لتكلفة الوحدة من الطعام j . و المطلوب هو تحديد الكميةx_j من نوع الطعام j بحيث تكون حلا للبرنامج التالي :

Sous contraintes

مثال :إذا كانت المعطيات كما هي مبينة في الجدول التالي :

إنّالبرنامج الخاص بهذه المسألة هو:

Min         2x₁+3x₂+x₃

_S .C

 10X₁+15X₂+10X₃≥ 20

100X₁+10X₂+10X₃ ≥ 50

                10X₁+100X₂+10X₃≥ 10

X₁ ,X₂ ,X₃ ≥ 0

حيث : X₁تمثل عدد اللترات من الحليب و X₂تمثل كمية اللحم بالكيلوغرام و X₃ تمثل عدد البيض.

النموذج الثاني :مسألة الإنتاج ( The production problem)

مصنع ينتج n صنفا و يحتاج من أجل ذلك إل m من المواد الخام .كل صنف يحتاج إلى كمية معينة من كل مادة خام . لنرمز بـ a_ijإلى كمية المادة الخام i التي تحتاجها الوحدة من الصنف j . و لتكنb_i هي الكمية المتوفرة من المـــادة i

و لنفترض أن c_jهو ربح الوحدة من الصنف j   و المطلوب هو تعيين الكمية x_j من الصنف المنتج jبحيث يتحقق ما يلي:

                                                   S.C

i=1 …..m

j=1…...n

X_j≥ 0

فعلى سبيل المثال لنأخذ المعطيات المبينة في الجدول الآتي :

إن البرنامج الخطي الخاص بهذه المسألة هو :

Max    160 x₁+ 210 x₂+ 100 x₃

s/c

3x₁+4 x₂+ 2x₃ ≤57

2x₁+x₂+ 2 x₃≤ 27

4x₁+5x₂+4x₃≤ 73

X₁,x₂,x₃ ≥ 0

حيث:

x₁: تمثل عدد الكراسي.

X₂تمثل عدد الطاولات.

X₃ تمثل عدد الخزانات.

النموذج الثالث : مسألة النقل The transportation problem

في إحدى الدول يوجد m  فرع لمصنع السكر . الفرع i ينتج a_iطنا من السكر هذه على nمنطقة . المنطقة j تحتاج إلىb_j طنا من السكر في الشهر الواحد . و لنفترض أن كميات السكر المنتجة تستهلك جميعها أي أنّ:

لتكنc_ij هي تكلفة نقل طن واحد من الفرع i  إلى المنطقة j . و المطلوب هو تحديد كمية السكر x_ijالتي ينبغي نقلها من المصنع i إلى المنطقة j بحيث تكون تكلفة النقل الكلية اقل ما يمكن .

بمعنى انه علينا أن نحقق البرنامج الأتي :

s.c

x_{i  j}≥ 0      i=1…….m

j=1………n

النموذج الرابع : مسألة التوظيف ( The assignnment problem) مسألة التخصيص أو التعيين

هذا النموذج يشبه نموذج النقل إلا أن قيم a_i=1 و b_j=1

فعلى سبيل المثال هناك ثلاث أساتذة يدرسون ثلاث مقررات كل واحد من هؤلاء الأساتذة يصحح أوراق اختبار هذه المقررات و لنفرض أن cij هو الزمن اللازم للأستاذi كي يصحح أوراق المقرر j  وفقا للجدول التالي :

و السؤال المطروح هو كيف يجب أن تنظم عملية التصحيح هذه حتى يكون زمن التصحيح الكلي أقل ما يمكن :

فإن الصياغة الرياضية لهذه المسألة تأخذ الشكل التالي :

Min 6X₁₁+4X₁₂+8X₁₃+9X₂₁+3X₂₂+6X₂₃+5X₃₁+2X₃₂+7X₃₃

S .C

X₁₁+X₁₂+X₁₃=1

X₂₁+X₂₂+X₂₃=1

X₃₁+X₃₂+X₃₃=1

X₁₁+X₂₁+X₃₁=1

X₁₂+X₂₂+X₃₂=1

X₁₃+X₂₃+X₃₃=1

X₁₁ ,X₁₂ ,X₁₃,X₂₁,X₂₂,X₂₃ ;X₃₁,_X32,X₃₃≥ 0

أمثلة عن صياغة النماذج الرياضية :

التمرين الأوّل :

مصنع ينتج سلعتين يستدعي ورود كل منهما 03 أقسام انتاجية على التوالي لغرض تصنيعها , الوقت المتاح في كل قسم انتاجي و الربح موضح في الجدول التالي :

المطلوب :

شكل البرنامج الخطي للمسألة؟

الحل :

الترميز :

السلعة 1 : x₁

السلعة 2: x₂

النموذج الرياضي :

دالة الهدف :    max z = 80 x₁+75x₂

القيود:

شرط عدم السلبية :x_j≥0                              j=1 ,2                               

التمرين الثاني :

تنتج الشركة منتجين أحدهما ذو مواصفات نوعية ممتازة Aو الآخر ذو مواصفات نوعية عادية Bفإذا كانت تكلفة الوحدة الواحدة من المنتج A02 دينار و من المنتج B 01 دينار  . واجهت  الشركة طلبا محدودا يجب أن لا يتجاوز 300 وحدة من كلا المنتجين و لأسباب مالية لا يجب أن تزيد تكاليف الإنتاج عن 500 دينار  و أن لا يزيد عدد الوحدات المنتجة العادية عن الوحدات المنتجة الممتازة بأكثر من 100 وحدة , اوجد قيمة الربح التي يمكن للشركة ان تحققها اذا كان الربح في الوحدة الواحدة من Aيساوي 03 دينار و من المنتج B يساوي 02 دينار.

المطلوب :

شكل نموذج البرمجة الخطية لهذه المشكة؟

الحل :

الترميز :

النوع الممتاز: X₁

النوع العادي :X₂

النموذج الرياضي :

دالة الهدف :  Max z= 3x₁+2x₂

القيود:

شرط عدم السلبية :X₁ ,X₂≥0

التمرين الثالث :

تقوم شركة بإنتاج نوعين من السلع الاستهلاكية و لإنتاج وحدة واحدة من كل نوع تحتاج هذه الشركة الى ما يلي :

اذا كانت المواد المتاحة للشركة اسبوعيا هي 120 كغ من المواد الخام و 360 منتجا وسيطا و 168 ساعات عمل تغليف ( 3 فرق عمل ). و كان ربح الشركة من النوع الاول 03 دينار و من بيع الوحدة الثانية هو 05 دينار .

المطلوب :

حدد هدف الشركة ؟

حدد القيود المفروضة مع شكل النموذج الرياضي المعبر عن مشكلة الشركة ؟

الحل :

الترميز :

النوع الاول : X₁

النوع الثاني :X₂

النموذج الرياضي :

دالة الهدف :   Max z= 3X₁+5X₂

القيود :

شرط عدم السلبية :X₁,X₂ ≥0                                                                   

التمرين الرابع :

تقوم مؤسسة ( pharmacier-point) بإنتاج ستة انواع من المواد A,B,C,D,E,F الكيمياوية المستقلة من حيث الانتاج , حيث يكلف انتاج اللتر الواحد من A , C, F  هو 5 دينار و اللتر الواحد من B , D  هو 7 دينار و اللتر الواحد من E هو 15 دينار .

يتطلب من المؤسسة إنتاج على الأقل 3 لتر من A ;B ;Cو على الأكثر 2 لتر من D يوميا, اما بالنسبة للمواد E ,F فيجب على المؤسسة إنتاج 7 لتر في اليوم نظرا للنقص في احد المواد الأولية الضرورية لإنتاج هذين النوعية لان المؤسسة لديها فقط 100 غرام من هذه المادة مع العلم ان كل لتر من A,B يحتاج إلى 3 غرامات من هذه المادة و كل لتر من C,D,E,F  يحتاج إلى 5 غرامات من هذه المادة.

العمل المطلوب : صياغة نموذج البرمجة الخطية اللازمة ؟

الحل:

الترميز :المواد A=X₁,B=X₂,C=X₃,D=X₄,E=X₅,F=X₆

النموذج الرياضي :

دالة الهدف :Min z=5x₁+7x₂+5x₃+7x₄+15x₅+5x₆

القيود:

X₁,X₂,X₃,X₄,X₅,X₆≥0              شرط عدم السلبية :