طريقة بيج إم

في بحوث العمليات ، تُعدّ طريقة "بيغ إم" أسلوبًا لحلّ مسائل البرمجة الخطية باستخدام خوارزمية السمبلكس . وتُوسّع هذه الطريقة خوارزمية السمبلكس لتشمل المسائل التي تتضمن قيودًا من نوع "أكبر من". ويتم ذلك بربط هذه القيود بثوابت سالبة كبيرة لا تُشكّل جزءًا من أي حلّ أمثل، إن وُجد.

تُعدّ خوارزمية السمبلكس الطريقة الأصلية، ولا تزال من أكثر الطرق استخدامًا لحلّ مسائل التعظيم الخطي. من البديهي أن النقاط التي تحقق الهدف الأمثل تقع على رأس من رؤوس السمبلكس، وهو شكل المنطقة الممكنة في البرنامج الخطي. تُمثّل النقاط الواقعة على رؤوس السمبلكس أساسًا. لذا، لتطبيق خوارزمية السمبلكس التي تهدف إلى تحسين الأساس حتى الوصول إلى الحل الأمثل الشامل، يلزم أولًا إيجاد أساس ممكن.

لا تُعدّ القاعدة التافهة (جميع متغيرات المسألة تساوي صفرًا) جزءًا من المُعقّد دائمًا. وتكون قابلةً للتطبيق فقط إذا كانت جميع القيود (باستثناء قيد عدم السلبية) قيودًا من نوع "أصغر من" مع وجود ثابت موجب في الطرف الأيمن. تُدخل طريقة "العدد الكبير M" متغيرات زائدة ومتغيرات اصطناعية لتحويل جميع المتباينات إلى هذا الشكل، وبالتالي تُوسّع المُعقّد في أبعاد أعلى ليصبح صالحًا في القاعدة التافهة. وهو دائمًا رأسٌ نظرًا لقيد الإيجابية على متغيرات المسألة المتأصل في الصيغة القياسية للبرمجة الخطية. ويُشير "العدد الكبير M" إلى عدد كبير مرتبط بالمتغيرات الاصطناعية، ويُمثّل بالحرف  M.

الخطوات في الخوارزمية هي كالتالي:

1. اضرب قيود المتباينة لضمان أن يكون الجانب الأيمن موجباً.
2. إذا كانت المشكلة تتعلق بالتقليل، فقم بتحويلها إلى تعظيم عن طريق ضرب الهدف في -1.
3. بالنسبة لأي قيود أكبر من، أدخل الفائض s _i والمتغيرات الاصطناعية a _i (كما هو موضح أدناه).
4. اختر قيمة موجبة كبيرة M وأدخل حدًا في دالة الهدف على شكل −M مضروبًا في المتغيرات الاصطناعية.
5. بالنسبة للقيود الأقل من أو تساوي، أدخل متغيرات الركود s _i بحيث تكون جميع القيود عبارة عن معادلات.
6. حل المسألة باستخدام طريقة السمبلكس المعتادة.

على سبيل المثال، تصبح المعادلة x  + y ≤ 100 على الصورة x + y + s ₁ = 100، بينما تصبح المعادلة x + y ≥ 100 على الصورة x + y − s ₁ + a ₁ = 100. يجب إثبات أن المتغيرات الاصطناعية تساوي صفرًا. تُعاد كتابة الدالة المراد تعظيمها لتشمل مجموع جميع المتغيرات الاصطناعية. ثم تُطبق عمليات اختزال الصفوف للوصول إلى الحل النهائي.                   

يجب اختيار قيمة M كبيرة بما يكفي بحيث لا يكون المتغير الاصطناعي جزءًا من أي حل ممكن.

بالنسبة لقيمة M كبيرة بما فيه الكفاية، يحتوي الحل الأمثل على أي متغيرات اصطناعية في الأساس (أي القيم الموجبة) إذا وفقط إذا كانت المشكلة غير قابلة للحل.

مع ذلك، فإن اختيار قيمة مناسبة لـ M مسبقًا ليس بالأمر البسيط. وقد وُصفت إحدى طرق التغلب على الحاجة إلى تحديد قيمة M في المرجع ^{[ 1 ]} . وتتضمن الطرق الأخرى لإيجاد أساس أولي لخوارزمية السمبلكس حل برنامج خطي آخر في المرحلة الأولية.

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

في التحسين الخطي المختلط، قد يشير مصطلح "Big M" أيضًا إلى استخدام حد كبير في القيود نفسها. على سبيل المثال، القيد المنطقي${\displaystyle z=0\iff x=y}$حيث z متغير ثنائي (0 أو 1)، ويشير هذا إلى ضمان تساوي المتغيرات فقط عندما يأخذ متغير ثنائي معين قيمة واحدة، مع ترك المتغيرات "مفتوحة" إذا أخذ المتغير الثنائي قيمته المعاكسة. بالنسبة لقيمة M كبيرة بما فيه الكفاية ومتغير ثنائي z (0 أو 1)، فإن القيود

${\displaystyle xy\leq Mz}$

${\displaystyle xy\geq -Mz}$

تأكد من ذلك عندما${\displaystyle z=0}$ثم${\displaystyle x=y}$وإلا، فعندما${\displaystyle z=1}$، ثم${\displaystyle -M\leq xy\leq M}$مما يشير إلى أن المتغيرين x و y يمكن أن يأخذا أي قيم طالما أن القيمة المطلقة لفرقهما محدودة بـ${\displaystyle M}$(ومن هنا تأتي الحاجة إلى أن تكون M "كبيرة بما فيه الكفاية"). وبالتالي، من الممكن "ترميز" القيد المنطقي في مشكلة MILP.

• طريقة المرحلتين (البرمجة الخطية) هي نهج آخر لحل المشكلات ذات القيود الأكبر من أو تساوي
• شروط كاروش-كون-تاكر ، التي تنطبق على مسائل التحسين غير الخطي ذات القيود غير المتباينة.

فهرس

• غريفا، إيغور. ناش، ستيفان G.؛ صوفر ، أرييلا (26 مارس 2009). التحسين الخطي وغير الخطي (الطبعة الثانية  ). جمعية الرياضيات الصناعية. رقم ISBN 978-0-89871-661-0.

مناقشة

• طريقة سيمبلكس - بيج إم ، لين كيلين، جامعة مدينة دبلن .
• طريقة بيغ إم ، businessmanagementcourses.org
• طريقة بيغ إم ، مارك هاتشينسون
• طريقة Big-M مع M العددية اللانهائية ، وهي صيغة حديثة بدون معلمات
• طريقة سيمبلكس ثلاثية المراحل لحل مسائل البرمجة الخطية غير الممكنة وغير المحدودة ، طريقة Big M عندما M=1