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

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

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

مجموعة القيود هي عبارة عن مجموعة من متباينات خطية

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

البرمجة الخطية هي طريقة البحث عن الحل الأمثل وتتكون من:

1) اقتران الهدف يكون في صورة:

$P=a x+b y$

حيث P هو اسم الاقتران (مثل الربح)، وa و b عددان حقيقيان، و x و y متغيران.

2) القيود: نظام من المتباينات الخطية، تكتب بدلالة المتغيرين y, x، وتحدد منطقة الحلول الممكنة كما في الشكل المجاور.

مثال:

أجد أحداثي النقطة (x,y) التي تجعل الاقتران $P=2x+3y$ أقل ما يمكن وإحداثي النقطة التي تجعل الاقتران أكبر ما يمكن ضمن القيود الآتية:

$$\begin{gathered} x+y\le 2 \\ x-2y\le 4 \\ x\ge 0 , y\ge 0 \end{gathered}$$

أولا: نمثل القيود بيانيا.

ثانيا: نحدد رؤوس منطقة الحل الممكنة.

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

رؤوس منطقة الحلول الممكنة	$p=2x+3y$
A(0,0)	$P=2\left(0\right)+3\left(0\right)=0$
B(0,2)	$P=2\left(0\right)+3\left(2\right)=6$
C(2,0)	$P=2\left(2\right)+3\left(0\right)=4$

رابعا: نحدد القيمة الصغرى والعظمى.

نلاحظ أن أكبر قيمة للاقتران P هي 6 التي تقابل النقطة (0,2) وإن أقل قيمة للاقتران P هي 0 التي تقابل النقطة (0,0).

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

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

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

3) تحديد إحداثيات رؤوس منطقة الحلول الممكنة.

4) اختيار القيمة العظمى أو الصغرى وفقا لما هو مطلوب في المسألة.

مثال:

يبيع متجر نوعين من أجهزة الحاسوب المحمولة، تكلفة الجهاز الواحد من النوع الثاني 400 JD. ويحقق الجهاز الواحد من النوع الأول ربحا قدره 45 JD، في ما يحقق الجهاز الواحد من النوع الثاني ربحا قدره 50 JD. ويقدر المتجر أن إجمالي الطلب الشهري على الأجهزة لا يتجاوز 250 جهازا، وأنه لا يمكنه استثمار أكثر من 70000 JD في ذلك. كم جهازا يجب على المتجر توفيرها للزبائن من كل نوع؛ لتحقيق أكبر ربح ممكن؟

1) أفرض أن عدد أجهزة الحاسوب التي سيوفرها المتجر من النوع الأول هو x، وأن عدد الأجهزة التي سيوفرها من النوع الثاني هو y. إذا افترضنا أن المتجر سيبيع جميع الأجهزة المتوافرة لديه؛ فإن الربح المتوقع هو: $p=45x+50y$

المطلوب أن يكون الربح أكبر ما يمكن ضمن القيود الآتية:

$250x+400y\le 70000 , x+y\le 250 , x\ge 0 , y\ge 0$

2) أمثل نظام المتباينات، ثم أضلل منطقة الحلول الممكنة كما في الشكل المجاور.

3) أحدد إحداثي كل من النقاط A, B, C, D، ثم أجد قيمة الربح P عند كل منها كما في الجدول الآتي:

$P=45x+50y$	رؤوس منطقة الحلول الممكنة
$P=45\left(0\right)+50\left(175\right)=8750$	A(0,175)
$P=45\left(200\right)+50\left(50\right)=11500$	B(200,50)
$P=45\left(250\right)+50\left(0\right)=11250$	C(250,0)
$P=45\left(0\right)+50\left(0\right)=0$	D(0,0)

ألاحظ من الجدول أن أكبر ربح ممكن هو 11500 JD، ويتحقق عند بيع 200 جهاز من النوع الأول، و50 جهازا من النوع الثاني.

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

مثال:

حمية غذائية: يشترط نظام الحمية الغذائية الذي يتبعه معاذ أن يتوافر ما لا يقل عن 300 سعرة حرارية، و36 وحدة من فيتامين A، و90 وحدة من فيتامين C، ضمن الجزء السائل من وجبته الغذائية. يبين الجدول المجاور تكلفة العلبة الواحدة من نوعين مختلفين من المكملات الغذائية، وعدد السعرات الحرارية، ووحدات فيتامين A وفيتامين C التي تحويها العلبة الواحدة. كم علبة من كل نوع يمكن أن يستهلكها معاذ يوميا بأقل تكلفة ممكنة؟

النوع 2	النوع 1
0.4 JD	0.3 JD	سعر العلبة الواحدة
60	60	سعر السعرات الحرارية
6	12	عدد وحدات فيتامين A
30	10	عدد وحدات فيتامين C

1) أفرض أن عدد العلب التي سيستهلكها معاذ يوميا من النوع الأول هو x، وأن عدد العلب التي سيستهلكها من النوع الثاني هو y. إذا افترضت أن معاذا سيحصل على حاجته اليومية من السعرات الحرارية والفيتامينات من النوعين معا؛ فإن التكلفة المتوقعة هي:

$C=0.3x+0.4y$

المطلوب أن تكون التكلفة أقل ما يمكن ضمن القيود الآتية:

$60x+60y\ge 300, 12x+6y\ge 36, 10x+30y\ge 90, x\ge 0, y\ge 0$

ويمكن كتابة الشروط في أبسط صورة كما يأتي:

$x+y\ge 5, 2x+y\ge 6, x+3y\ge 9, x\ge 0, y\ge 0$

2) أمثل نظام المتباينات الخطية، ثم أظلل منطقة الحلول الممكنة كما في بالشكل المجاور.

3) أحدد رؤوس منطقة الحلول الممكنة، ثم أحدد القيمة العظمى أو القيمة الصغرى.

رؤوس منطقة الحلول الممكنة	$C=0.3x+0.4y$
A(0,6)	$C=0.3\left(0\right)+0.4\left(6\right)=2.4$
B(1,4)	$C=0.3\left(1\right)+0.4\left(4\right)=1.9$
C(3,2)	$C=0.3\left(3\right)+0.4\left(2\right)=1.7$
D(9,0)	$C=0.3\left(9\right)+0.4\left(0\right)=2.7$

ألاحظ من الجدول أن أقل تكلفة ممكنة تساوي 1.7 JD، وأن معاذا يستهلك حينئذ 3 علب من النوع الأول من المكمل الغذائي، وعلبتين من النوع الثاني من المكملات الغذائية، وهو الحد الأدنى الذي يحتاج إليه من السعرات الحرارية والفيتامينات ضمن الجزء السائل من وجبته الغذائية.