طريقة Simplex للبرمجة الخطية
طريقة Simplex للبرمجة الخطية!
يمكن حل أي مشكلة برمجة خطية تتضمن متغيرين بسهولة باستخدام طريقة رسومية لأنه من الأسهل التعامل مع الرسم البياني ثنائي الأبعاد. تقع جميع الحلول الممكنة في طريقة رسومية ضمن المنطقة المجدية على الرسم البياني ، وقد استخدمنا اختبار نقاط الزاوية للمنطقة المجدية للحل الأمثل ، أي أن إحدى نقاط الزاوية للمنطقة المجدية المستخدمة هي الحل الأمثل. استخدمنا لاختبار جميع نقاط الزاوية من خلال وضع هذه القيمة في وظيفة موضوعية.
ولكن إذا زاد عدد المتغيرات من اثنين ، يصبح من الصعب للغاية حل المشكلة عن طريق رسم الرسم البياني الخاص بها عندما تصبح المشكلة معقدة للغاية. تم تطوير طريقة Simplex بواسطة GB Dantzig ، وهو عالم رياضيات أمريكي.
هذه الطريقة هي المعالجة الرياضية للطريقة الرسومية. هنا يتم اختبار نقاط الزاوية المختلفة للمنطقة المجدية من أجل التحسين. ولكن من غير الممكن اختبار جميع نقاط الزاوية لأن عدد نقاط الزوايا يزيد من الفتحات مع زيادة عدد المعادلات والمتغيرات. الحد الأقصى لعدد هذه النقاط التي يمكن اختبارها يمكن أن يكون
م + ن م = م + 1! / م! ن!
حيث m عدد و n عدد المتغيرات.
في طريقة simplex ، يتم تقليل عدد نقاط الزاوية التي سيتم اختبارها بشكل كبير باستخدام خوارزمية فعالة للغاية والتي تقودنا إلى نقطة الحل الأمثل في عدد قليل من التكرار فقط. دعونا نأخذ مثالا واحدا ونمضي خطوة خطوة.
تتمثل الوظيفة الموضوعية في زيادة Z = 12x 1 + 15x 2 + 14x 3
تخضع لشروط
الخطوة 1:
(أ) يجب أن يكون الجانب الأيمن من جميع القيود إما صفر أو + ve. إذا كان الأمر كذلك ، فيجب أن يتم إجراؤها + ve بضرب كل من الطرفين (-1) وأن يتم عكس علامة عدم المساواة. في هذا المثال ، RHS بالفعل + ve أو صفر.
(ب) يتم تحويل جميع أوجه عدم المساواة إلى مساواة عن طريق إضافة أو طرح متغيرات الركود أو الفائض. يتم إدخال هذه المتغيرات السهلة أو الفائضة لأنه من الأسهل التعامل مع المساواة من عدم المساواة في المعاملة الرياضية.
إذا كان القيد هو النوع ≤ ، تضاف متغيرات الركود إذا كان القيد هو النوع then ثم يتم طرح الفائض المتغير. وهنا تضاف متغيرات الركود s ،، s 2 و s 3 في ثلاثة في المساواة (i) و (ii) و (iii) ، نحصل عليها.
وتصبح الوظيفة الموضوعية
Maximize Z = 12x 1 + 15x 2 + 14x 3 + os 1 + os 2 + os 3
الخطوة 2:
البحث عن الحل الأساسي الأساسي الأولي:
نبدأ بحل عملي ثم ننتقل إلى الحل الأمثل في التكرارات التالية. يفضل أن يتم اختيار المحلول القابل للتنفيذ المبدئي ليكون المصدر ، أي عندما تكون المتغيرات العادية على سبيل المثال في هذه الحالة x vx 2 ، x 3 تحمل قيم صفرية. أي × 1 × 2 ، × 3 = 0
ونحصل على s 1 = 0 و s 2 = 0 و s 3 = 100 من اللامساواة (i) و (ii) و (iii)
المتغيرات الأساسية هي المتغيرات الموجودة في الحل على سبيل المثال ، S v S 2 و S 3 هي المتغيرات الأساسية في الحل الأولي.
المتغيرات غير الأساسية هي المتغيرات التي تم تعيينها مساوية لصفر وهي ليست في الحل الحالي مثل x 1 و x 2 و x 3 هي المتغيرات غير الأساسية في الحل الأولي.
يمكن التعبير عن المعلومات الواردة أعلاه في الجدول 1
في الجدول ، يمثل الصف الأول معاملات دالة الهدف ، ويمثل الصف الثاني متغيرات مختلفة (المتغيرات العادية الأولى ثم المتغيرات الركود / الفائض). الصف الثالث والخامس يمثل معاملات المتغيرات في جميع القيود.
العمود الأول يمثل معاملات المتغيرات الأساسية (متغيرات الحل الحالية) في الهدف (e i ) يمثل العمود الثاني المتغيرات الأساسية (متغيرات الحل الحالية) ويمثل العمود الأخير ، الجانب الأيمن من القيود في الشكل القياسي. أي بعد تكديس جميع أوجه عدم المساواة في المساواة ، في أي جدول ، يتم إعطاء القيم الحالية لمتغيرات الحل الحالية (المتغيرات الأساسية) بواسطة RHS
في الجدول 1 ، الحل الحالي هو:
S 1 = 0، S 2 = 0، S 3 = 100
وبالطبع فإن المتغيرات غير الأساسية X v X 2 و X 3 ستكون صفرا
الانحلال كلما تفترض أي متغير أساسي على قيم صفرية ، يقال أن المحلول الحالي يتدهور كما هو الحال في المشكلة الحالية S 1 = 0 و S 2 = 0 يمكن حل المشكلة أكثر باستبدال S 1 = t و S 2 = t حيث t رقم صغير جدا + ve.
الخطوه 3:
اختبار الاداء.
يمكن إجراء اختبار التحسين لمعرفة ما إذا كان الحل الحالي هو الأمثل أم لا. لهذا أولا أكتب الصف الأخير في شكل (E ي ) حيث
Ej = Σ ei. أيج.
حيث يمثل ij معاملات في مصفوفة هوية الجسم لعمود ith row & jth ، أي يمثل العمود الأول من الجدول. في الصف الأخير ، اكتب قيمة (Cj - Ej) حيث c ؛ يمثل قيم الصف الأول ويمثل E j قيم الصف الأخير. (Cj - Ej) تمثل ميزة إحضار أي متغير غير أساسي إلى الحل الحالي أي عن طريق جعله أساسيًا.
في الجدول 2 ، تكون قيم Cj - Ej هي 12 و 15 و 14 لـ X v X 2 و X 3 . إذا كانت أي من قيم Cj - Ej هي + ve فهذا يعني أن معظم القيم الإيجابية تمثل المتغير الذي يتم إدخاله في المحلول الحالي سيزيد من الوظيفة الهدف إلى أقصى حد. في الحالة الراهنة X 2 هو متغير محتمل ليأتي إلى الحل للتكرار التالي. إذا كانت جميع القيم في صف (Cj - Ej) سلبية ، فهذا يعني أنه تم التوصل إلى الحل الأمثل.
الخطوة الرابعة:
تكرارا نحو الحل الأمثل:
الحد الأقصى لقيمة Cj - Ej يعطي Key coloumn كما هو موضح في الجدول
لذلك ، X X هو متغير الإدخال ، أي أنه يصبح أساسيًا وسيُدخل الحل. للخروج من المتغير الأساسي غير الموجود ، وعلى المرء أن يخرج ويصبح غير أساسي. للعثور على المتغير الذي سيتم إخراجه ، أقسم المعاملات في عمود RHS بواسطة المعاملات المقابلة في عمود المفتاح للحصول على "نسبة العمود". الآن ابحث عن أقل قيمة موجبة في عمود نسبة وسيعطي صف المفتاح. في المشكلة الحالية لدينا ثلاث قيم أي t و µ و 100 و من هذه ، t هي الأقل + ve. لذلك فإن الصف المقابل لـ t في عمود نسبة سيكون صف المفتاح. و S. ، سيكون متغير المغادرة. العنصر في تقاطع الصف الرئيسي والمفتاح coloumn هو العنصر الرئيسي.
الآن كل العناصر الموجودة في المفتاح الرئيسي باستثناء العنصر الأساسي هي أن تكون صفراً وأن العنصر الأساسي هو جعل الوحدة. يتم ذلك بمساعدة عمليات الصف كما فعلت هي المصفوفات. هنا العنصر الرئيسي هو بالفعل الوحدة ويتم إجراء عنصر آخر في coloumn الرئيسية صفر بإضافة -1 الصف الأول من الصف في الصف الثالث والحصول على الجدول التالي.
لذلك يصبح الحل المجدي الثاني
X 1 = 0، X 2 = t and X 3 = 0 there by z = 15t
في الجدول الجديد 1 ، استعيض عن X 2 في المتغيرات الأساسية ، وكذلك تم تغيير eum coloumn.
الخطوة 5:
عند النظر إلى قيم Cj -Ej في الجدول 3 ، نجد أن x 1 يحتوي على قيم + ve أكثر من 27 مما يشير إلى إمكانية تحسين المحلول عن طريق إحضار x 1 إلى المحلول أي جعله أساسيًا. ولذلك ، فإن x 1 coloumn هو عمود رئيسي ، كما سيجد صفًا أساسيًا كما تم توضيحه سابقًا وكامل الجدول 5.
العنصر الرئيسي في الجدول 5 يأتي ليكون 2 ويتم جعل الوحدة وجميع العناصر الأخرى في المفتاح coloumn تصبح صفر مع مساعدة من عمليات الصف وأخيرا نحصل على الجدول 6. يتكون العنصر الأساسي الأول من خلال تقسيم هذا الصف بواسطة 2. ثم بإضافة مضاعفات مناسبة لذلك الصف في صفوف أخرى نحصل على الجدول 6.
يمكن أن نرى من الجدول 6 أن الحل الثابت ليس هو الأمثل حيث أن Cj-Ej لا يزال يمثل قيم + ve 1/2 يعطي هذا اللون coloumn ويتم العثور على الصف الرئيسي المقابل ، يتم إجراء العنصر الرئيسي كما هو مبين في الجدول 7
الآن عن طريق عمليات صف مناسبة نجعل عناصر أخرى في coloumn الرئيسية هي صفر كما هو موضح في الجدول 8.
يمكن ملاحظة أنه بما أن جميع القيم في صف Cj-Ej هي إما -ve أو صفر- فقد تم التوصل إلى الحل الأمثل.
الحل النهائي هو × 1 = 40 طن
× 2 = 40 طنًا
× 3 = 20 طنًا
بما أن t صغير جدًا ، فهو مهمَل.
مثال 1:
حل المشكلة التالية بطريقة simplex
تكبير Z = 5x 1 + 4x 2
تخضع لـ 6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
-x 1 + x 2 ≤ 1
× 2 ≤ 2
و x 1 x 2 ≥0
حل:
أضف متغيرات الركود S 1 و S 2 و S 3 و S 4 في القيود الأربعة لإزالة التفاوتات.
نحصل على 6x 1 + 4x 2 + s 1 = 24
x 1 + 2x 2 + s 2 = 6
-x 1 + x 2 + s 3 = 1
x 2 + s 4 = 2
تخضع لـ x 1 و x 2 و s 1 و s 2 و s 3 & s 4 > 0
تصبح الوظيفة الموضوعية
تكبير Z = 5x 1 + 4x 2 0s 1 + 0s 2 + 0s 3 + 0s 4
الجدول 1 الذي تم تشكيله يرد أدناه. يمكن ملاحظة أن X 1 هو المتغير الداخل و S ، هو المتغير المانع. يتم جعل العنصر الرئيسي في الجدول 1 الوحدة ويتم جعل كل عنصر آخر في ذلك coloumn صفر.
يمكن أن يكون من الجدول 2 أن X 2 هو المتغير الداخل ، وأن S 2 هو متغير المغادرة.
ويمكن ملاحظة من الجدول 5 أن جميع قيم صف Cj-Ej هي إما -ve أو صفر. لذلك تم الحصول على الحل الأمثل.
الحل هو x 1 = 3، x 2 = 3/2
Z max = 5x 3 + 4x = 3/2
= 15 + 6 = 21
كبير M- الطريقة
دعونا نأخذ المشكلة التالية لتوضيح Big M- الطريقة.
تصغير Z = 2y 1 + 3y 2
تخضع لقيود ذ 1 + ذ 2 ≥ 5
y 1 + 2y 2 ≥ 6
ذ 1 ، ص 2 ≥ 0
التحويل إلى نموذج قياسي:
تكبير Z = -2y 1 - 3y 2 + Os ، + 0s 2
يتم تحويل أي مشكلة تقليل إلى الحد الأقصى مشكلة عن طريق ضرب RHS من دالة الهدف بواسطة -1.
القيود y 1 + y 2 - s 1 = 6 ... (i)
y، + y 2 - s 2 = 6 ... (ii)
y 1 y 2 ، s 1 s 2 ≥ 0
هنا المتغيرات الفائضة s1 و s2 وطرحها من القيود (i) و (ii) على التوالي.
الآن y 1 ، y 2 يمكن أن تؤخذ كمتغيرات غير أساسية وتساوي صفر لتحصل على s s s كمتغيرات أساسية حيث s 1 = -5، s 2 = -6.
هذا هو الحل غير قابل للتطبيق لأن المتغيرات الفائضة s 1 و s 2 لها قيم -ve. للتغلب على هذه المشكلة ، نضيف المتغيرات الصناعية A 1 و A 2 في eqn. (ط) و (الثاني) على التوالي للحصول عليها
y 1 + y 2 –s 1 + A 1 = 5… (iii)
y 1 + 2y 2 - s 2 + A 2 = 6 ... (iv)
حيث y 1 y 2 ، s 1 ، s 2 ، A 1 ، A 2 ≥ 0
وتصبح الوظيفة الموضوعية
Maximize Z 1 = -2y 1 - 3y 2 + 0s 1 + 0s 2 - MA 1 - MA 2
يمكن ملاحظة أننا قمنا بتعمد فرض عقوبات شديدة جداً على المتغيرات الصناعية في دالة الهدف في شكل -MA1 و MA 2 حيث M عبارة عن رقم + ve كبير جداً. الغرض من ذلك هو أن المتغيرات الصناعية تظهر في البداية في الحل الأساسي.
ولأن المتغيرات الصناعية تقلل من الوظيفة الموضوعية إلى درجة كبيرة جدا ، فإن حالة الخوارزمية البسيطة تدفع المتغيرات الصناعية إلى الخروج من الحل في التكرارات الأولية ، وبالتالي فإن المتغيرات الصناعية التي قدمناها لحل المشكلة لا تظهر في النهاية. حل. المتغيرات الصناعية ليست سوى جهاز حاسوبي. يحافظون على معادلات البدء في التوازن ويوفرون خدعة رياضية للحصول على حل البداية.
يصبح الجدول الأولي
نظرًا لأن Cj-Ej هو + ve تحت بعض الأعمدة ، فإن الحل المقدم في الجدول 1 ليس مثاليًا. يمكن ملاحظة أنه من -2 + 2M و -3 + 3M ، يكون -3 + 3M أكثر + ve حيث أن M عبارة عن رقم + ve كبير جدًا. تم العثور على العنصر الرئيسي كما هو موضح في الجدول 1 ويتم جعل الوحدة وجميع العناصر الأخرى في هذا العمود تكون صفرًا. نحصل على الجدول 2.
من الجدول 2 ، يمكن ملاحظة أنه لم يتم التوصل إلى الحل الأمثل وأن هناك حل أفضل. Y 1 هو المتغير الوارد و A 1 هو المتغير الصادر. نحصل على الجدول 3.
ويمكن ملاحظة ذلك من الجدول 3 الذي بلغ الحل الأمثل والحل هو
Y 1 = 4 ، Y 2 = 1
الحد الأدنى لقيمة Z = 2x 4 + 3x 1 = 11 units Ans.
حل غير محدود:
ويقال إن مشكلة البرمجة الخطية لديها حل غير محدود عندما في العمود نسبة ، نحصل على جميع الإدخالات إما -ve أو صفر وليس هناك دخول + ve. يشير هذا إلى أن قيمة المتغير الوارد المحدد من مفتاح coloomn يمكن أن تكون كبيرة كما نرغب دون انتهاك الحالة الممكنة ، ويقال إن المشكلة لها حل غير محدود.
عدد لا حصر له من الحلول:
ويقال إن مشكلة البرمجة الخطية لديها عدد لا حصر له من الحلول إذا كان خلال أي تكرار ، في صف CJ-EJ ، لدينا جميع القيم إما صفر أو - ح. هذا يدل على أن القيمة المثلى قد وصلت. ولكن نظرًا لأن أحد المتغيرات العادية له قيمة صفرية في صف Cj-Ej ، فيمكن استنتاج أنه يوجد حل بديل بديل.
مثال على هذا النوع من الجدول يرد أدناه.
يمكن ملاحظة أنه تم الوصول إلى الحل الأمثل لأن جميع القيم في صف Cj-Ej صفرية أو -ve ولكن X 1 هو متغير غير أساسي وله قيمة صفرية في صف Cj-Ej ، وهو يشير إلى أن X ، يمكن إحضارها إلى الحل ، ومع ذلك فإنه لن يزيد من قيمة وظيفة الهدف ويوجد بديل بديل.
حالة رقم الحل عمليا:
في بعض LPP يمكن ملاحظة أنه أثناء حل المشكلة مع المتغيرات الصناعية ، يظهر صف Cj-Ej أنه يتم التوصل إلى الحل الأمثل بينما لا يزال لدينا متغير مصطنع في المحلول الحالي يحتوي على بعض + vp value. في مثل هذه الحالات ، يمكن استنتاج أن المشكلة ليس لها أي حل عملي على الإطلاق.
المثال 2:
حل:
من أجل حل المشكلة ، يجب إضافة المتغيرات الصناعية في نظام LHS للحصول على الحل الأساسي الأساسي. دعونا ندخل المتغيرات الصناعية أ 1 ، أ 2 ، أ 3 ، يمكن كتابة القيود أعلاه.
الآن ، إذا ظهرت هذه المتغيرات الصناعية في الحل النهائي عن طريق الحصول على بعض قيم + ve ، عندئذ يتم إزعاج مساواة المعادلة (i) ، (ii) أو (iii). لذلك نريد أن لا تظهر المتغيرات الصناعية في الحل النهائي ، وبالتالي نطبق عقوبة كبيرة في الوظيفة الموضوعية ، والتي يمكن كتابتها كـ.
Maximize Z = Y، + 2Y 2 + 3Y 3 - Y 4 - MA، - MA 2 - MA 3
الآن إذا أخذنا y 1 Y 2 و y 3 و y 4 كمتغيرات غير أساسية ووضعنا Y 1 = Y 2 = y 4 = 0 فإننا نحصل على حل أولي كـ A 1 = 15، A 2 = 20 & A 3 = 10 و A 1 و A 2 و A 3 و A 4 هي متغيرات أساسية (متغيرات في الحل الحالي) لتبدأ بها. يمكن وضع المعلومات الواردة أعلاه في الجدول 1.
AS Cj- Ej إيجابي ، الحل الحالي ليس الأمثل ، وبالتالي يوجد حل أفضل.
تكرارا نحو الحل الأمثل
أداء التكرارات للحصول على الحل الأمثل كما هو موضح في الجدول أدناه
بما أن Cj-Ej إما صفر أو سالبة تحت كل الأعمدة ، فقد تم الحصول على الحل الأمثل الأساسي المثالي. القيم المثلى هي
Y 1 = 5/2، Y 2 = 5/2، Y 3 = 5/2، Y4 = 0
أيضًا A 1 = A 2 = 0 و Z max = 15 Ans.
