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

تطبيقات عملية – البرمجة الخطية  Linear Programming:

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

مثال:

هناك نوعان من أقلام الحبر ، ثمن القلم من النوع الأول 6 دنانير ومن النوع الثاني 12 دينارا فاذا كان مع سمير 24 دينارا فجد :

أ‌-       الامكانيات المختلفة لشراء أقلام من النوعين .

ب‌-  كم قلما يشتري سمير من كل نوع حتى يصبح معه أكبر عدد ممكن من الأقلام ؟

الحل:

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

أ‌-       نبدأ بترتيب المعلومات المعطاة في جدول ونفرض أن عدد الاقلام التي يجب شراؤها هي س من النوع الاول ، ص من النوع الثاني .

	سعر القلم	عدد الاقلام	الثمن الكلي للاقلام
النوع الاول	6 دنانير	س	6س
النوع الثاني	12 دينار	ص	12 ص

ما هي الشروط المفروضة على عملية شراء الاقلام ؟

الشرط الأول : مجموع اثمان الاقلام المشتراة أقل من أو يساوي 24 دينارا ، أي أن :

6س + 12ص ³ 24

الشرط الثاني : عدد الاقلام هو عدد طبيعي أي ان : س ، ص تنتمي الى ط

ب‌-  لايجاد قيمة س ، ص ضمن منطقة الحل والتي تجعل المقدار ( س+ ص) أكبر ما يمكن نفحص امكانيات الحل السابقة ، ويبين الجدول التالي جميع الامكانيات وقيمة المقدار

 ( س+ ص) المناظرة لكل منها:

النقطة ( س، ص)	(0،0)	(1،0)	(2،0)	(3، 0)	(4،0)	(0،1)	(1، 1)	(2،1)	(0 ، 2)
المقدار (س+ص)	0	1	2	3	4	1	2	3	2

  

من الجدول نلاحظ أن اكبر قيمة للمقدار ( س +ص) هي 4 المناظرة لقيمة س =4 ، ص=0

أي أن أكبر عدد من الاقلام يمكن شراؤه هو 4 أقلام وجميعها من النوع الاول .

لاحظ أيضا أن النقطة ( 4 ، 0) هي احدى النقاط المتطرفة هي :

م (0،0) حيث س+ ص = 0

أ ( 0 ،2) حيث س +ص = 2

ب ( 4 ،0) حيث س +ص = 4

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

وكما ذكر سابقا ، يمكن حل المسألة ببساطة فشراء النوع الارخص من الاقلام يعطينا الفرصة لشراء اكبر عدد منها ، وحيث أن المتوفر هو 24 دينارا فيمكننا شراء 4 اقلام من النوع الاول ( الارخص) والذي سعره6 دنانير للقلم الواحد .

                                                 

مثال:

 في مصنع سيارات خطا انتاج : ينتج الخط الاول 4 شاحنات و10 جرافات في اليوم الواحد بكلفة انتاج مقدارها 1400000دولار وينتج الخط الثاني 8 شاحنات و 5 جرافات في اليوم الواحد بكلفة انتاج مقدارها 1100000 دولار فاذا استلم المصنع طلبا لتوريد 28 شاحنة و55 جرافة فكم يوما يلزم تشغيل كل من الخطين لتلبية الطلب بأقل كلفة ممكنة؟

الحل:

نفرض أن عدد الايام اللازمة لتشغيل الخطين الاول والثاني هما س ، ص يوميا على الترتيب

ينتج الخط الاول في س يوما : 4س شاحنة و10 س جرافة .

وينتج الخط الثاني في ص يوما : 8 ص شاحنة و5 ص جرافة

نرتب المعلومات في الجدول الآتي :

	عدد الشاحنات	عدد الجرافات
انتاج الخط الأول	4 س	10 س
انتاج الخط الثاني	8 ص	5 ص
المجموع	4 س + 8 ص	10 س +5 ص
الكمية المطلوبة	28	55

ما هي الشروط على المتغيرين س ، ص؟

الشرط الأول : نلاحظ أن عدد الشاحنات المنتجة لتلبية الطلب يجب أن تكون 28 أو أكثر (فلا ضرر من وجود بعض الزيادة) . أي أن : 4س + 8ص £ 28 .

الشرط الثاني: نلاحظ أن عدد الجرافات المنتجة لتلبية الطلب يجب أن يساوي 55 أو يزيد عنها .

أي أن : 10 س + 5 ص £ 55

الشرط الثالث: لا يمكن أن يكون عدد الأيام سالبا . أي أن س  £0 وكذلك ص £ 0 وبهذا نحصل على نظام المتباينات الآتي :

4س + 8ص £ 28

10 س + 5 ص £ 55

س£0

ص£ 0

أما كلفة الانتاج عند تشغيل الخط الأول س يوما فهي 1400000 دينارا .

كما أن كلفة الانتاج عند تشغيل الخط الثاني ص يوما فهي : 1100000 ص دينارا . وتؤول المسألة الى جعل المقدار 1400000س +1100000ص والذي يسمى ( اقتران الهدف ) أقل ما يمكن .

المتباينة 4س + 8ص £ 28 يمكن كتابتها : س  + 2ص £ 7  ،( بقسمة كل حد على 4 ) .

أما المتباينة 10س +5ص  £55 فيمكن كتابتها : 2س + ص  £11 ، ( بقسمة كل حد على 5 ) .

ونحتاج الى دراسة الاقتران الهدف ( 1400000س +1100000ص ) ثلاث نقاط متطرفة من

مجموعة الحل وأقل قيمة للاقتران تحدد قيمتي س ، ص النقاط المتطرفة هي :

أ ( 7، 0) ، ب( 5 ، 1) ، ج (0، 11)

والجدول التالي يلخص قيم اقتران الهدف عند هذه النقاط  .

النقطة	س	ص	قيمة اقتران الهدف
أ	7	0	1400000×7+0 = 9800000 دينارا
ب	5	1	1400000×5 + 1100000×1 = 8100000
ج	0	11	0+1100000×11 = 12100000 دينارا

ومن الجدول نجد أن أقل كلفة هي عند النقطة ب أي عندما يعمل الخط الاول 5 أيام ويعمل الخط الثاني يوما واحدا .

مثال:

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

 كما ينتج الفرع الثاني 2 طن من شراب الليمون ، 15 طن من شراب البرتقال ، 4 طن من شراب التوت ، وكلفة تشغيل الفرع الثاني هي 1000 دينار في اليوم الواحد فاذا استلم المصنع طلبا لتوريد 12 طنا من شراب الليمون ، 30 طنا من شراب البرتقال 16 طنا من شراب التوت ، فكم يوما يشغل كل فرع لتلبية الطلب وبحيث تكون كلفة التشغيل أقل ما يمكن ؟

الحل:

1)    نفرض أن عدد الايام اللازمة لتشغيل المصنع لتلبية الطلب هي س يوما من العمل في الفرع الاول ، ص يوما من العمل في الفرع الثاني . 

	انتاج الفرع الاول (طن)	انتاج الفرع الثاني(طن)	الكمية المطلوبة
شراب الليمون	6س	2ص	12
شراب البرتقال	5س	15ص	30
شراب التوت	4س	4ص	16

1)    نعبر عن قيود المسألة بنظام من المتباينات :

6س +2ص £ 12 ( لماذا؟)

5 س+15 ص £ 30 (لماذا؟)

4 س + 4 ص £ 16 (لماذا؟)

 س£0 لأن عدد الأيام لا يكون سالبا

ص£ 0 لأن عدد الأيام لا يكون سالبا

2)    نمثل المتباينات بيانيا وتكون المنطقة المظللة هي الحل

3)    نحدد اقتران الهدف الذي يمثل كلفة التشغيل لتلبية الطلب وهو المقدار :

 800س + 1000 دينار

4)    نحدد من الرسم النقاط المتطرفة وهي (6 ،0) ، (3 ،1) ، ( 1، 3) ، (0 ،6) .

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

في تلك النقطة ) .

5)    نحسب قيمة اقتران الهدف عند كل نقطة من هذه النقاط وهي كما يلخصها الجدول الآتي :

النقطة	س	ص	قيمة اقتران الهدف
أ	6	0	800 س + 1000ص = 4800+0 = 4800 دينار
ب	3	1	800س + 1000ص = 2400+ 1000 = 3400 دينار
ج	1	3	800س + 1000 ص= 800 + 3000 = 3800 دينار
د	0	6	800 س + 1000ص = 0+ 6000 = 6000 دينار

7) نعين من الجدول احداثيي النقطة التي تكون الكلفة عندها أقل ما يمكن .

النقطة هي ب (3 ، 1) حيث س= 3 ، ص= 1 ومعنى ذلك أننا نشغل

 الفرع الاول 3 أيام ونشغل الفرع الثاني يوما واحدا .

تمارين ومسائل:

1) مجموعة الحل لنظام المتباينات الآتي :

س + ص £ 5

2س + ص  £ 6

س + 3ص  £9

س  £ 0

ص  £ 0

جد النقط المتطرفة ومن ثم حدد متى يكون اقتران الهدف 4س + 5 ص ضمن هذا النظام أقل ما يمكن .

2) أوجد القيمة العظمى للمقدار 2س + 3ص بشرط 

2س + ص ³ 15 .

س + 3ص ³ 20

س £ 0

ص £ 0

3)    في مصنع خطان لانتاج البسكويت وكل منهما ينتج ثلاثة أنواع من البسكويت أ ، ب،ج

وينتج الخط الاول يوميا 3 طن من النوع أ ، طن واحد من النوع ب ، 2 طن من النوع ج بكلفة اجمالية قدرها 300 ريال  وينتج الخط الثاني يوميا 2 طن من النوع أ ، 4 طن من النوع ب ، و5 طن من النوع ج بكلفة اجمالي400 ريال  . تلقى المصنع طلبا مقداره 26 طنا من النوع الاول ، 21 طنا من النوع ب و32 طنا من النوع ج .

كم يوما يعمل كل خط انتاج لتلبية الطلب بأقل كلفة ممكنة وما هي الكلفة الدنيا؟