مقالات

4.3: التصغير بطريقة Simplex - الرياضيات


أهداف التعلم

في هذا القسم ، ستتعلم كيفية حل مشاكل تقليل البرمجة الخطية باستخدام طريقة simplex.

  1. تحديد وإعداد برنامج خطي في شكل تصغير قياسي
  2. قم بصياغة مشكلة مزدوجة في شكل تعظيم قياسي
  3. استخدم طريقة simplex لحل مشكلة التكبير المزدوج
  4. حدد الحل الأمثل لمشكلة التصغير الأصلية من لوحة العرض البسيط المثلى.

في هذا القسم ، سنحل مشاكل تصغير البرمجة الخطية القياسية باستخدام طريقة simplex. مرة أخرى ، نذكر القارئ أنه في مشاكل التصغير القياسية ، تكون جميع القيود من الشكل (ax + by ≥ c ).

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

من الجدول البسيط الأخير ، نستخرج الحل لمشكلة التصغير الأصلية.

قبل أن نذهب إلى أبعد من ذلك ، نتعلم أولاً تحويل مشكلة تصغير إلى مشكلة تعظيم مقابلة تسمى مشكلة التصغير مزدوج.

مثال ( PageIndex {1} )

حول مسألة التصغير التالية إلى مشكلتها المزدوجة.

[ ابدأ {مجموعة} {كامل}
textbf {Minimize} & mathrm {Z} = 12 mathrm {x} _ {1} +16 mathrm {x} _ {2}
textbf {Subject to:} & mathrm {x} _ {1} +2 mathrm {x} _ {2} geq 40
& mathrm {x} _ {1} + mathrm {x} _2 geq 30
& mathrm {x} _ {1} geq 0؛ mathrm {x} _ {2} geq 0
نهاية {مجموعة} غير رقم ]

حل

لتحقيق هدفنا ، نعبر أولاً عن مشكلتنا على أنها المصفوفة التالية.

[ ابدأ {مجموعة} {cc | c}
1 & 2 & 40 \
1 & 1 & 30 \
hline 12 & 16 & 0
نهاية {مجموعة} غير رقم ]

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

[ ابدأ {مجموعة} {cc | c}
1 & 1 & 12 \
2 & 1 & 16 \
hline 40 & 30 & 0
نهاية {مجموعة} غير رقم ]

تسمى مشكلة التعظيم التالية المرتبطة بالمصفوفة أعلاه ثنائية.

[ ابدأ {مجموعة} {كامل}
textbf {Maximize} & mathrm {Z} = 40 mathrm {y} _ {1} +30 mathrm {y} _ {2}
textbf {Subject to:} & mathrm {y} _ {1} + mathrm {y} _ {2} leq 12
& 2 mathrm {y} _1 + mathrm {y} _2 leq 16
& mathrm {y} _ {1} geq 0؛ mathrm {y} _ {2} geq 0
نهاية {مجموعة} غير رقم ]

لاحظ أننا اخترنا المتغيرات مثل y بدلاً من x لتمييز المشكلتين.

مثال ( PageIndex {2} )

حل مشكلة التصغير ومشكلة التكبير المزدوج بيانياً.

حل

مشكلة التصغير لدينا هي على النحو التالي.

[ ابدأ {مجموعة} {كامل}
textbf {Minimize} & mathrm {Z} = 12 mathrm {x} _1 + 16 mathrm {x} _2
textbf {Subject to:} & mathrm {x} _ {1} +2 mathrm {x} _ {2} geq 40
& mathrm {x} _ {1} + mathrm {x} _ {2} geq 30
& mathrm {x} _ {1} geq 0؛ mathrm {x} _ {2} geq 0
نهاية {مجموعة} غير رقم ]

نحن الآن نرسم المتباينات:

لقد رسمنا الرسم البياني ، وقمنا بتظليل منطقة الجدوى ، وقمنا بتسمية نقاط الزاوية. تعطي نقطة الركن (20 ، 10) أقل قيمة للدالة الهدف وهذه القيمة هي 400.

الآن الثنائي هو:

[ ابدأ {مجموعة} {كامل}
textbf {Maximize} & mathrm {Z} = 40 mathrm {y} _1 + 30 mathrm {y} _ {2}
textbf {Subject to:} & mathrm {y} _ {1} + mathrm {y} _ {2} leq 12
& 2 mathrm {y} _1 + mathrm {y} 2 leq 16
& mathrm {y} _ {1} geq 0؛ mathrm {y} _ {2} geq 0
نهاية {مجموعة} غير رقم ]

نحن نرسم أوجه عدم المساواة:

مرة أخرى ، قمنا برسم الرسم البياني ، وظللنا منطقة الجدوى ، وسمينا نقاط الزاوية. تعطي نقطة الركن (4 ، 8) أعلى قيمة للدالة الهدف ، بقيمة 400.

قد يتعرف القارئ على أن المثال ( PageIndex {2} ) أعلاه هو نفسه المثال 3.1.1 ، في القسم 3.1. إنها أيضًا نفس مشكلة المثال 4.1.1 في القسم 4.1 ، حيث قمنا بحلها بطريقة simplex.

نلاحظ أن الحد الأدنى لقيمة مشكلة التصغير هو نفس القيمة القصوى لمشكلة التصغير ؛ في المثال ( PageIndex {2} ) الحد الأدنى والحد الأقصى كلاهما 400. هذا ليس مصادفة. نعلن مبدأ الازدواجية.

مبدأ الازدواجية

مبدأ الازدواجية

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

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

مثال ( PageIndex {3} )

أوجد حل مشكلة التصغير في المثال ( PageIndex {1} ) عن طريق حل المشكلة الثنائية باستخدام طريقة simplex. نعيد كتابة مشكلتنا.

[ ابدأ {مجموعة} {كامل}
textbf {Minimize} & mathrm {Z} = 12 mathrm {x} _ {1} +16 mathrm {x} _ {2}
textbf {Subject to:} & mathrm {x} _ {1} +2 mathrm {x} _ {2} geq 40
& mathrm {x} _ {1} + mathrm {x} _ {2} geq 30
& mathrm {x} _ {1} geq 0؛ mathrm {x} _ {2} geq 0
نهاية {مجموعة} غير رقم ]

حل

[ ابدأ {مجموعة} {كامل}
textbf {Maximize} & mathrm {Z} = 40 mathrm {y} _ {1} +30 mathrm {y} _ {2}
textbf {Subject to:} & mathrm {y} _ {1} + mathrm {y} _ {2} leq 12
& 2 mathrm {y} _ {1} + mathrm {y} _ {2} leq 16
& mathrm {y} _ {1} geq 0؛ mathrm {y} _ {2} geq 0
نهاية {مجموعة} غير رقم ]

تذكر أننا حللنا المشكلة أعلاه بالطريقة البسيطة في المثال 4.1.1 ، القسم 4.1. لذلك ، نعرض فقط الجدول البسيط الأولي والنهائي.

اللوحة الأولية البسيطة هي

[ ابدأ {مجموعة} {ccccc | c}
mathrm {y} _1 & mathrm {y} _2 & mathrm {x} _ {1} & mathrm {x} _ {2} & mathrm {Z} & mathrm {C}
1 & 1 & 1 & 0 & 0 & 12 \
2 & 1 & 0 & 1 & 0 & 16 \
hline-40 & -30 & 0 & 0 & 1 & 0
نهاية {مجموعة} غير رقم ]

لاحظ تغييرًا مهمًا. هنا المتغيرات الرئيسية لدينا هي ( mathrm {y} _1 ) و ( mathrm {y} _2 ) ومتغيرات الركود هي ( mathrm {x} _1 و mathrm {x} _2 ).

تقرأ اللوحة البسيطة النهائية على النحو التالي:

[ ابدأ {مجموعة} {ccccc | c}
mathrm {y} _1 & mathrm {y} _2 & mathrm {x} _ {1} & mathrm {x} _ {2} & mathrm {Z} &
0 & 1 & 2 & -1 & 0 & 8 \
1 & 0 & -1 & 1 & 0 & 4 \
hline 0 & 0 & 20 & 10 & 1 & 400
نهاية {مجموعة} غير رقم ]

تكشف نظرة فاحصة على هذا الجدول أنه يمكن الحصول على قيم ( mathrm {x} _1 ) و ( mathrm {x} _2 ) بالإضافة إلى الحد الأدنى لقيمة مشكلة التصغير من الصف الأخير من الصف الأخير تابلوه. لقد أبرزنا هذه القيم بواسطة الأسهم.

[ ابدأ {مجموعة} {ccccc | c}
mathrm {y} _1 & mathrm {y} _2 & mathrm {x} _ {1} & mathrm {x} _ {2} & mathrm {Z} &
0 & 1 & 2 & -1 & 0 & 8 \
1 & 0 & -1 & 1 & 0 & 4 \
hline 0 & 0 & 20 & 10 & 1 & 400
& & uparrow & uparrow & & & uparrow
نهاية {مجموعة} غير رقم ]

نعيد صياغة الحل على النحو التالي:

مشكلة التصغير لها قيمة لا تقل عن 400 عند نقطة الزاوية (20 ، 10)

نلخص الآن مناقشتنا.

التصغير بطريقة Simplex

  1. قم بإعداد المشكلة.
  2. اكتب مصفوفة تمثل صفوفها كل قيد مع وظيفة الهدف كصفها السفلي.
  3. اكتب مدور هذه المصفوفة عن طريق تبديل الصفوف والأعمدة.
  4. اكتب الآن المشكلة المزدوجة المرتبطة بالمبدل.
  5. قم بحل المشكلة المزدوجة بطريقة simplex التي تم تعلمها في القسم 4.1.
  6. تم العثور على الحل الأمثل في الصف السفلي من المصفوفة النهائية في الأعمدة المقابلة لمتغيرات الركود ، والحد الأدنى لقيمة دالة الهدف هو نفس القيمة القصوى للثنائي.


شاهد الفيديو: Simplex part 3 Big M Simplex Method شرح (شهر اكتوبر 2021).