كيف تحصل بسرعة على حل عملي لبرنامج خطي في Python؟

2

الهدف: حساب تقاطع اثنين من محدبات متعددة محدبة.

انا استخدم scipy.spatial.HalfspaceIntersection لفعل هذا. توضح الصورة التالية التقاطع الناتج: Imagen 124

مشكلتي: تحديد نقطة مجدية أولية.

ترى الحالي Python بداية شئ scipy.spatial.HalfspaceIntersection يتطلب interior_point ليتم تمريرها كحجة.

interior_point : ndarray of floats, shape (ndim,)
Point clearly inside the region defined by halfspaces. Also called a feasible point, it can be obtained by linear programming.

الآن ، في الوقت الحالي ، أقوم بتزويد النقطة المجدية يدويًا لأنني كنت فقط أقوم بصياغة نموذج أولي للتجربة HalfspaceIntersection . ولكن الآن وصلت إلى نقطة لا أريد تحديدها يدويًا.

SciPy 's وحدة التحسين scipy.optimize.linprog تطبق اثنين من مذيبات البرمجة الخطية العامة (LP) : البسيط ، والنقطة الداخلية . ومع ذلك ، يبدو أنها تتطلب دالة تكلفة. [ 1 ]

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

الأسئلة:

  1. يكون scipy.optimize.linprog الطريقة الصحيحة للذهاب لحساب هذه النقطة الداخلية الممكنة؟

  2. إذا كانت الإجابة بنعم ، فكيف يمكنني استخدام نقطة بسيطة أو داخلية بدون دالة تكلفة؟

  3. لماذا scipy.spatial.HalfspaceIntersection تتطلب interior point ليتم تمريرها كحجة في المقام الأول؟ على حد علمي ، فإن تقاطع نصف المسافات هو إزالة التفاوتات الزائدة لمجموعة معينة من التفاوتات. لماذا مطلوب نقطة مجدية لذلك؟

1 إجابة

1
افضل جواب

يمكنك تحديد دالة تكلفة ثابتة ، على سبيل المثال 0.

هنا مثال:

%pylab
from scipy.optimize import linprog
A = array([[1] + 9 * [0], 9 * [0] + [1]])
b = array([1, 1])

يكشف قياس أداء هذا النهج أنه فعال للغاية:

%time
res = linprog(c=zeros(A.shape[1]), A_eq=A, b_eq=b)

انتاج:

CPU times: user 5 µs, sys: 1 µs, total: 6 µs
Wall time: 11 µs

علاوة على ذلك ، وفقا ل res.nit ، لقد انتهينا بعد تكرارين فقط.

النتائج res.x صحيح:

array([ 1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.])

لاحظ أن خوارزمية البسيط مصممة للعثور على رؤوس متعدد الوجوه المحدد بواسطة القيود الخطية. حسب فهمي ، فإن الأساليب الداخلية القائمة على النقاط ليس لديها مثل هذا التفضيل ، على الرغم من أنني لست على دراية بالتنفيذ وراء Scipy linprog . وبالتالي ، نظرًا لأن الشرط هو أن تكون النقطة "بوضوح داخل المنطقة المحددة بنصف مسافات" ، أقترح أيًا مما يلي:

  • إما أن تمر method='interior-point' إلى linprog .
  • أو احسب الرؤوس المختلفة واستغل أن متعدد الوجوه محدب:
    1. أضف بعض الضوضاء إلى وظيفة الهدف الثابتة (على سبيل المثال ، عبر np.random.randn )
    2. حل حالات متعددة من LP المعزز بالضوضاء عن طريق تغيير بذرة الضوضاء ( np.random.seed ).
    3. أخيرًا ، استخدم متوسط الحل الخاص بك كنقطة داخلية نهائية "بوضوح داخل المنطقة" .

نظرًا لأنه ليس من الواضح ، ما هو حجم الهامش المطلوب للنقطة الداخلية الخاصة بك ، أتوقع أن النهج الثاني (LP المعزز بالضوضاء) أكثر قوة.

:مؤلف

أسئلة ذات صلة

فوق
قائمة طعام