الرئيسية
تقدمت وسائل التحليل الرياضي للمشاكل الإدارية والاقتصادية تقدما كبيرا وتعتبر البرمجة الخطية إحدى هذه الوسائل وقد استخدمة كلمة Programming كأداه تهدف إلى استغلال الموارد المتاحة للمنشاة من قوة عاملة ومواد أولية الخ لتحقيق اكبر عائد ممكن.
وتهدف البرمجة الخطية إلى الإجابة باسلوب التحليل الرياضي على بعض الأسئلة وحل المشاكل بما يحقق اكبر ربح ممكن أو اقل تكلفة ممكنة في ظل القيود والمحددات القائمة.
وعموماُ فان أداء أي عمل بأفضل الوسائل يعني في حد ذاته البحث عن الحدود الدنيا أو القصوى. فعندما تتعلق المشكلة بالتكاليف فان الهدف عادة يكون الوصول إلى الحد الأدنى وإذا تعلق الأمر بالأرباح فان الهدف يكون هو الوصول إلى الحد الأقصى.
صياغة المشكلة:
المشكلات الامثلية غالبا ما تاتي في صورة كلامية. وتحدد طريقة الحل في تصوير المشكلة في شكل نموذج رياضي يعبر عن المشكلة، ومن ثم يحل هذا النموذج بالاساليب المختلفة. ويمكن اتباع الخطواط التالية في بناء النموذج الرياضي.
1) حدد الكميات التي تحتاج الى قيم مثلى. وعرفها كمتغيرات لتاخذ الرموز x1, x2, …, xn
2) عرف هدف المشكلة وغبر عنه رياضياً باستخدام المتغيرات .
3) حدد ومثل القيود في صورة متباينات وذلك باستخدام المتغيرات.
4) اضف الى النموذج الرياضي شرط عدم السالبية( ان جميع المتغيرات يجب ان تكون اكبر من او تساوي الصفر).
مثال1:
يقوم جزار بعمل شطائر اللحم بتكوين من لحم بقري ولحم ماعز. يحتوي لحم البقر على %80 لحم و %20 دهون ويكلف 24 جنيه لكل كيلو في حين ان لحم الماعز على %68 لحم و %32 دهون ويكلف 18 جنيه لكل كيلو. ماهي كمية اللحم من كل نوع يجب ان يستخدمها المحل في كل كيلو من شطائر اللحم اذا علمت انه يجب تخفيض التكاليف والمحافظة علي نسبة الدهون. بحيث لايذيد عن %25؟
الحل:
المتغيرات:
نفرض ان وزن لحم البقر المستخدم في الكيلو = X
نفرض ان وزن لحم الماعز المستخدم في الكيلو = Y
دالة الهدف:
تصغير Min Z = 24X + 18Y
القيود:
القيد الاول: يحتوي كل كيلو علي 0.20 X من الدهون من لحم البقر و 0.32Y من الدهون من لحم الماعز ويجب الا تزيد الدهون في الشطيرة عن 0.25 .
0.20 X + 0.32 Y ≤ 0.25
القيد الثاني: ويجب ان يكون وزن لحم البقر و لحم الماعز مجتمعين في كل كيلو من الشطائر هو كيلو واحد.
X + Y = 1
القيد الثالث: قيد عدم السالبية
X ≥ و 0 Y ≥ 0
النموذج الرياضي:
تصغير Min Z = 24X + 18Y
علماَ بان: 0.20 X + 0.32 Y ≤ 0.25
X + Y = 1
X ≥ و 0 Y ≥ 0
الحل البياني للمثال رقم 1
للحصول علي السم الباني الممثل للمشكلة يتم اتباع الخطوات التالية:
1. رسم محوري العمودي X والراسيY كا هو موضح بالرسم التالي >
2. رسم القيود كما يلي:
القيد الاول :
بفرض ان X= 0 نجد ان Y = 0.78 نحصل على النقطة ((0, 0.78
بفرض ان Y = 0 نجد ان X = 1.25 نحصل على النقطة ((1.25, 0
نوقع النقتطين ((0, 0.78 و ((1.25, 0 علي الرسم.
القيد الثاني :
بفرض ان X= 0 نجد ان Y = 1 نحصل على النقطة ((0, 1
بفرض ان Y = 0 نجد ان X = 1 نحصل على النقطة ((1, 0
نوقع النقتطين ((0, 1 و ((1, 0 علي الرسم.
بحل المعادلتين:
0.20 X + 0.32 Y ≤ 0.25 و X + Y = 1
نحصل على:
X* = 7/12 , Y* = 5/12
بالتعويض في Z نجد ان Z = 24 (7/12) + 18( 5/12)= 21
مما بعني ان المحال يجب ان يستخدم 7/12من لحم البقر والباقي 5/12 من لحم الماعز وذلك يحقق اقل تكلفة والتي تساوي 21 جنيه للكيلو.
مثال 2
حل البرمجة الخطية التالية باستخدام طريقة الرسم البياني
Min z = 5X + 2Y صغر
s.t. 2X + 5Y > 10
4X - Y > 12
X + Y > 4
X, Y > 0
رسم القيود:
القيد الأول: 4X - Y > 12 بفرض ان Y = 0, نجد ان X = 5 وعندما نفرض ان X = 0 نجد ان Y = 2 اذا وصل النقتطين (0,5 ) و (2,0)
القيد الثاني: X + Y > 4
بفرض ان Y = 0, نجد ان X = 3 وعندما نفرض ان X = 0 نجد ان Y = -12 والتي ليست على الرسم لذلك لذلك نفرض ان X = 5 نجد ان Y = 8
اذا وصل النقتطين (3,0 ) و (5,8)القيد الثالث: X + Y > 4
بفرض ان Y = 0, نجد ان X = 4 وعندما نفرض ان X = 0 نجد ان Y = 4
إذا وصل النقتطين (0,4 ) و (4,0)
رسم دالة الهدف:
افرض ان دالة الهدف تساوي أي رقم اختياري وليكن 20
اذا 5X + 2Y = 20, عندما X = 0, اذاُ Y = 10وعندما Y= 0, اذاً X = 4. وصل النقتطين (4,0) و (0,10).حرك دالة الهدف في اتجاة تصغير القيمة حتى تصل إلى أخر نقطة في منطقة الحلول المحددة بأخر قيدين.
حل نقط التقاطع للقيود الحاكمة التي يقع عليها الحل
, 4X - Y = 12 X+ Y = 4
بحل المعادلتين السابقتين نجد ان:
5X = 16 or X = 16/5.
بالتعويض في X + Y = 4 نجد ان Y = 4/5
بالتعويض في دالة الهدف كما يلي:
z = 5X + 2Y = 5(16/5) + 2(4/5) = 88/5.
نجد ان الحل الامثل هو:
X = 16/5; Y = 4/5; z = 88/5
كما هو موضح بالرسم التالي
البرمجة الخطية
باستخدام طريقة السمبلكس
Linear Porogramming Using Simplex Method
نظرا لان طريقة الحل بالرسم البياني لا تصلح لأكثر من اثنين او ثلاث متغيرات وكذلك لو نظرنا الي المشكلات الواقعية نجد ان معظم المشكلات في الواقع العملي تحتوي على العديد من المتغيرات مما يصعب استخدام الطرق البيانية في الحل. ومن ثم استلزم وجود طرق اخري للتعامل مع مثل هذة المشكلات. ومن بين هذه الطرق والتي تصلح للتعامل مع مشكلات البرمجة الخطية طريقة السمبلكس Simplex Method. بالاضافة لصلاحية هذة الطريقة للتعامل مع المشكلات ذات المتغيرات كثيرة العدد فانه يوجد الكثير من برامج الحاسب الالي التي تعمل وفق هذه الطلريقة والتي يمكن ان تستخدم لحل مشاكل البرمجة الخطية ذات الابعاد الكبيرة ( عدد كبير من المتغيرات وعدد كبير من القيود) والتى تعطي حلول في اوقات صغيرة جدا وتجيب علي كثير من التسائلات ومن اشهر تلك التسائلات ما يعرف ب ماذا لو what if qustions. وفيما يلي سوف نعرض الخطوات الرئيسية لطريقة السمبلكس.
طريقة السمبلكس
وفيما يلي يمكن اتباع الخطوات التالية للوصول الى الحل الامثل من خلال استخدام طريقة السمبلكس.
1. حدد اعلى قيمة سالبة في الصف السفلي من جدول السمبلكس باستثناء العمود الاخير, ويطلق على العمود الذي تظهر فيه هذة القيمة عمود العمل. في حالة تساوي اكثر من قيمة اختار احداهما.
2. كون نسبا من خلال قسمة القيم الموجبة في عمود العمل علي القيم المناظرة لها في اخر عمود وذلك باستثناء اخر صف. وان لم يوجد قيم موجبة في عمود العمل فان المشكلة ليس لها حل.
3. اختار العنصر الذي ينتمي الي عمود العمل والذي له اقل نسبة (يسمى العنصلر المحوري)
4. استخدم العمليات الاولية لتحويل العنصر المحوري الى واحد صحيح وبقي العمود اصفار.
5. استبدل المتغير x في صف المحور والعمود الاول بالمتغير x في الصف الاول وعمود المحور (عمود المتغيرات الاساسية).
6. كرر الخطوات من 1-5 حتى تحصل على جدول ليس به اعداد سالبة في الصف الاخير باستثناء العمود الاخير.
7. نحصل على الحل الامثل من خلال تخصيص كل في العمود الاخير والمتغير المناظر له في العمود الاول . وباقي المتغيرات تاخذ قيمة صفر. والقيمة المثلي للهدف z* هي العدد الموجود في الصف الاخير والعمود الاخير وذلك في حالة التعظييم. والقيمة السالبة لهذا العدد في حالة التصغيير.
مثال3
تعظيم Max Z = x1 + 9x2 + x3
علماَ بان: x1 + 2x2 + 3 x3 ≤ 9
3 x1 + 2x2 + 2 x3 ≤ 15
x1 , x2 , x3 ≥ 0
الحل:
تحويل المتباينات الي الصيغة القياسية كما يالي:
Max Z = x1 + 9x2 + x3+ x4 + x5
علماَ بان: 9 = x1 + 2x2 + 3 x3 + x4
3 x1 + 2x2 + 2 x3 + x5 = 15
x1 , x2 , x3, x4 , x5 ≥ 0
تكوين جدول السمبلكس من الصيغة القياسية كما يالي:
وتهدف البرمجة الخطية إلى الإجابة باسلوب التحليل الرياضي على بعض الأسئلة وحل المشاكل بما يحقق اكبر ربح ممكن أو اقل تكلفة ممكنة في ظل القيود والمحددات القائمة.
وعموماُ فان أداء أي عمل بأفضل الوسائل يعني في حد ذاته البحث عن الحدود الدنيا أو القصوى. فعندما تتعلق المشكلة بالتكاليف فان الهدف عادة يكون الوصول إلى الحد الأدنى وإذا تعلق الأمر بالأرباح فان الهدف يكون هو الوصول إلى الحد الأقصى.
صياغة المشكلة:
المشكلات الامثلية غالبا ما تاتي في صورة كلامية. وتحدد طريقة الحل في تصوير المشكلة في شكل نموذج رياضي يعبر عن المشكلة، ومن ثم يحل هذا النموذج بالاساليب المختلفة. ويمكن اتباع الخطواط التالية في بناء النموذج الرياضي.
1) حدد الكميات التي تحتاج الى قيم مثلى. وعرفها كمتغيرات لتاخذ الرموز x1, x2, …, xn
2) عرف هدف المشكلة وغبر عنه رياضياً باستخدام المتغيرات .
3) حدد ومثل القيود في صورة متباينات وذلك باستخدام المتغيرات.
4) اضف الى النموذج الرياضي شرط عدم السالبية( ان جميع المتغيرات يجب ان تكون اكبر من او تساوي الصفر).
مثال1:
يقوم جزار بعمل شطائر اللحم بتكوين من لحم بقري ولحم ماعز. يحتوي لحم البقر على %80 لحم و %20 دهون ويكلف 24 جنيه لكل كيلو في حين ان لحم الماعز على %68 لحم و %32 دهون ويكلف 18 جنيه لكل كيلو. ماهي كمية اللحم من كل نوع يجب ان يستخدمها المحل في كل كيلو من شطائر اللحم اذا علمت انه يجب تخفيض التكاليف والمحافظة علي نسبة الدهون. بحيث لايذيد عن %25؟
الحل:
المتغيرات:
نفرض ان وزن لحم البقر المستخدم في الكيلو = X
نفرض ان وزن لحم الماعز المستخدم في الكيلو = Y
دالة الهدف:
تصغير Min Z = 24X + 18Y
القيود:
القيد الاول: يحتوي كل كيلو علي 0.20 X من الدهون من لحم البقر و 0.32Y من الدهون من لحم الماعز ويجب الا تزيد الدهون في الشطيرة عن 0.25 .
0.20 X + 0.32 Y ≤ 0.25
القيد الثاني: ويجب ان يكون وزن لحم البقر و لحم الماعز مجتمعين في كل كيلو من الشطائر هو كيلو واحد.
X + Y = 1
القيد الثالث: قيد عدم السالبية
X ≥ و 0 Y ≥ 0
النموذج الرياضي:
تصغير Min Z = 24X + 18Y
علماَ بان: 0.20 X + 0.32 Y ≤ 0.25
X + Y = 1
X ≥ و 0 Y ≥ 0
الحل البياني للمثال رقم 1
للحصول علي السم الباني الممثل للمشكلة يتم اتباع الخطوات التالية:
1. رسم محوري العمودي X والراسيY كا هو موضح بالرسم التالي >
2. رسم القيود كما يلي:
القيد الاول :
بفرض ان X= 0 نجد ان Y = 0.78 نحصل على النقطة ((0, 0.78
بفرض ان Y = 0 نجد ان X = 1.25 نحصل على النقطة ((1.25, 0
نوقع النقتطين ((0, 0.78 و ((1.25, 0 علي الرسم.
القيد الثاني :
بفرض ان X= 0 نجد ان Y = 1 نحصل على النقطة ((0, 1
بفرض ان Y = 0 نجد ان X = 1 نحصل على النقطة ((1, 0
نوقع النقتطين ((0, 1 و ((1, 0 علي الرسم.
بحل المعادلتين:
0.20 X + 0.32 Y ≤ 0.25 و X + Y = 1
نحصل على:
X* = 7/12 , Y* = 5/12
بالتعويض في Z نجد ان Z = 24 (7/12) + 18( 5/12)= 21
مما بعني ان المحال يجب ان يستخدم 7/12من لحم البقر والباقي 5/12 من لحم الماعز وذلك يحقق اقل تكلفة والتي تساوي 21 جنيه للكيلو.
مثال 2
حل البرمجة الخطية التالية باستخدام طريقة الرسم البياني
Min z = 5X + 2Y صغر
s.t. 2X + 5Y > 10
4X - Y > 12
X + Y > 4
X, Y > 0
رسم القيود:
القيد الأول: 4X - Y > 12 بفرض ان Y = 0, نجد ان X = 5 وعندما نفرض ان X = 0 نجد ان Y = 2 اذا وصل النقتطين (0,5 ) و (2,0)
القيد الثاني: X + Y > 4
بفرض ان Y = 0, نجد ان X = 3 وعندما نفرض ان X = 0 نجد ان Y = -12 والتي ليست على الرسم لذلك لذلك نفرض ان X = 5 نجد ان Y = 8
اذا وصل النقتطين (3,0 ) و (5,8)القيد الثالث: X + Y > 4
بفرض ان Y = 0, نجد ان X = 4 وعندما نفرض ان X = 0 نجد ان Y = 4
إذا وصل النقتطين (0,4 ) و (4,0)
رسم دالة الهدف:
افرض ان دالة الهدف تساوي أي رقم اختياري وليكن 20
اذا 5X + 2Y = 20, عندما X = 0, اذاُ Y = 10وعندما Y= 0, اذاً X = 4. وصل النقتطين (4,0) و (0,10).حرك دالة الهدف في اتجاة تصغير القيمة حتى تصل إلى أخر نقطة في منطقة الحلول المحددة بأخر قيدين.
حل نقط التقاطع للقيود الحاكمة التي يقع عليها الحل
, 4X - Y = 12 X+ Y = 4
بحل المعادلتين السابقتين نجد ان:
5X = 16 or X = 16/5.
بالتعويض في X + Y = 4 نجد ان Y = 4/5
بالتعويض في دالة الهدف كما يلي:
z = 5X + 2Y = 5(16/5) + 2(4/5) = 88/5.
نجد ان الحل الامثل هو:
X = 16/5; Y = 4/5; z = 88/5
كما هو موضح بالرسم التالي
البرمجة الخطية
باستخدام طريقة السمبلكس
Linear Porogramming Using Simplex Method
نظرا لان طريقة الحل بالرسم البياني لا تصلح لأكثر من اثنين او ثلاث متغيرات وكذلك لو نظرنا الي المشكلات الواقعية نجد ان معظم المشكلات في الواقع العملي تحتوي على العديد من المتغيرات مما يصعب استخدام الطرق البيانية في الحل. ومن ثم استلزم وجود طرق اخري للتعامل مع مثل هذة المشكلات. ومن بين هذه الطرق والتي تصلح للتعامل مع مشكلات البرمجة الخطية طريقة السمبلكس Simplex Method. بالاضافة لصلاحية هذة الطريقة للتعامل مع المشكلات ذات المتغيرات كثيرة العدد فانه يوجد الكثير من برامج الحاسب الالي التي تعمل وفق هذه الطلريقة والتي يمكن ان تستخدم لحل مشاكل البرمجة الخطية ذات الابعاد الكبيرة ( عدد كبير من المتغيرات وعدد كبير من القيود) والتى تعطي حلول في اوقات صغيرة جدا وتجيب علي كثير من التسائلات ومن اشهر تلك التسائلات ما يعرف ب ماذا لو what if qustions. وفيما يلي سوف نعرض الخطوات الرئيسية لطريقة السمبلكس.
طريقة السمبلكس
وفيما يلي يمكن اتباع الخطوات التالية للوصول الى الحل الامثل من خلال استخدام طريقة السمبلكس.
1. حدد اعلى قيمة سالبة في الصف السفلي من جدول السمبلكس باستثناء العمود الاخير, ويطلق على العمود الذي تظهر فيه هذة القيمة عمود العمل. في حالة تساوي اكثر من قيمة اختار احداهما.
2. كون نسبا من خلال قسمة القيم الموجبة في عمود العمل علي القيم المناظرة لها في اخر عمود وذلك باستثناء اخر صف. وان لم يوجد قيم موجبة في عمود العمل فان المشكلة ليس لها حل.
3. اختار العنصر الذي ينتمي الي عمود العمل والذي له اقل نسبة (يسمى العنصلر المحوري)
4. استخدم العمليات الاولية لتحويل العنصر المحوري الى واحد صحيح وبقي العمود اصفار.
5. استبدل المتغير x في صف المحور والعمود الاول بالمتغير x في الصف الاول وعمود المحور (عمود المتغيرات الاساسية).
6. كرر الخطوات من 1-5 حتى تحصل على جدول ليس به اعداد سالبة في الصف الاخير باستثناء العمود الاخير.
7. نحصل على الحل الامثل من خلال تخصيص كل في العمود الاخير والمتغير المناظر له في العمود الاول . وباقي المتغيرات تاخذ قيمة صفر. والقيمة المثلي للهدف z* هي العدد الموجود في الصف الاخير والعمود الاخير وذلك في حالة التعظييم. والقيمة السالبة لهذا العدد في حالة التصغيير.
مثال3
تعظيم Max Z = x1 + 9x2 + x3
علماَ بان: x1 + 2x2 + 3 x3 ≤ 9
3 x1 + 2x2 + 2 x3 ≤ 15
x1 , x2 , x3 ≥ 0
الحل:
تحويل المتباينات الي الصيغة القياسية كما يالي:
Max Z = x1 + 9x2 + x3+ x4 + x5
علماَ بان: 9 = x1 + 2x2 + 3 x3 + x4
3 x1 + 2x2 + 2 x3 + x5 = 15
x1 , x2 , x3, x4 , x5 ≥ 0
تكوين جدول السمبلكس من الصيغة القياسية كما يالي:
