كيف تحل نظام عدم المساواة؟

Question

لقد خفضت مشكلتي (خوارزمية تخطيط الجدول) إلى المشكلة التالية:

تخيل أن لدي متغيرات x₁, ، x₂, ، ... ، x_ن. لدي أيضًا عدد (غير محدد) من عدم المساواة ، مثل:

x₁ >= 2
x₂ + x₃ >= 13
إلخ.

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

كيف تحل هذا النظام بهذه الطريقة ، أن قيم المتغيرات صغيرة قدر الإمكان؟

إضافة: اقرأ مقالة ويكيبيديا وأدركت أنني نسيت أن أذكر أن المتغيرات يجب أن تكون أعداد صحيحة. أعتقد أن هذا يجعله np-hard ، هاه؟

Answer 1

التقليل من X1 + X2 + ... حيث تسمى XI قيود الخطية البرمجة الخطية. إنه مغطى بشيء من التفصيل في ويكيبيديا

Answer 2

ما لديك هناك هو أساسي جدا البرمجة الخطية مشكلة. تريد زيادة المعادلة إلى أقصى حد X_1 + ... + X_n تخضع الى

X_1 >= 2
X_2 + X_3 >= 13
etc.

هناك العديد من الخوارزميات لحل هذا النوع من المشاكل. الأكثر شهرة هو Simplex خوارزمية والتي ستحل المعادلة الخاصة بك (مع بعض التحذيرات) بكفاءة تامة في الحالة المتوسطة ، على الرغم من وجود مشاكل LP التي تتطلب خوارزمية Simplex من أجلها العديد من الخطوات التي يجب حلها (في حجم المشكلة) بشكل كبير.

توجد تطبيقات مختلفة لحل LP. فمثلا lp_solve يجب أن تلبي معظم متطلباتك

Answer 3

يمكنك أيضًا نشر طرازك الخطي مباشرة إلى منصة NEOS (http://neos.mcs.anl.gov/neos/solvers/index.html). ما عليك القيام به ببساطة هو كتابة النموذج الخاص بك بلغة جبرية مثل AMPL. ثم سيقوم NEOS بحل النموذج وإرجاع النتائج عن طريق البريد الإلكتروني.

Answer 4

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