البرمجة الخطية العددية: مثال وأدوات جيدة؟

Question

ابحث عن المتجه X الذي يقلل C. X خاضع للقيود م. x> = b ، x integer.

إليك مجموعة إدخال عينة:

c : {1,2,3}
m : {{1,0,0},
     {0,1,0},
     {1,0,1}}
b : {1,1,1}

مع الإخراج:

x = {1,1,0}

ما هي الأدوات الجيدة لحل هذا النوع من المشكلة ، وأمثلة على كيفية استخدامها؟

Answer 1

الرياضيات

Mathematica لديه هذا مدمج في. (NB: Mathematica ليس برنامجًا مجانيًا.)

LinearProgramming[c, m, b, Automatic, Integers]

المخرجات:

{1, 1, 0}

Answer 2

GLPK

أنا أقدم إجابة باستخدام GLPK's GLPSOL, ، لكنني آمل أن تكون هناك طرق أفضل بكثير للقيام بذلك (يبدو أن GLPK قوي/عام للغاية لهذا النوع من الحالة الخاصة البسيطة لمشكلة البرمجة الخطية):

من أجل إنشاء ملف .mps الوارد أدناه ، يجب عليك تقسيم المصفوفات الخاصة بك إلى نظام من المعادلات ، وبالتالي يصبح وصف المشكلة:

minimize

cost = 1 x_1 + 2 x_2 + 3 x_3

s.t. constraints:

S1 = 1 x_1 + 0 x_2 + 0 x_3
S2 = 0 x_1 + 1 x_2 + 0 x_3
S3 = 1 x_1 + 0 x_2 + 1 x_3

S1 >= 1
S2 >= 1
S3 >= 1

0 <= x1 <= 1
0 <= x2 <= 1
0 <= x3 <= 1

وثائق GLPK لديه معلومات مفصلة عن تنسيق .mps ، لكنك تحدد الصفوف والأعمدة و RHS والحدود. في قسم الصفوف ، حدد "N" و "G" نوع القيد (الرقم ، وأكبر من على التوالي). في قسم الحدود ، يحدد "واجهة المستخدم" أن الحدود عدد صحيح علوي اكتب ، إجبار الحل على أن يكون صحيحًا.

لتشغيل المحاليل على مواصفات المشكلة:

> glpsol --freemps example.mps -o example.out

ملف example.mps:

NAME          VM
ROWS
 N cost
 G S1
 G S2
 G S3
COLUMNS
 x_1    cost    1.0
 x_1    S1      1.0
 x_1    S3      1.0
 x_2    cost    2.0
 x_2    S2      1.0
 x_3    cost    3.0
 x_3    S3      1.0
RHS 
 RHS1 cost   0.0
 RHS1 S1     1.0
 RHS1 S2     1.0
 RHS1 S3     1.0
BOUNDS
 UI BND1 x_1 1.0
 UI BND1 x_2 1.0
 UI BND1 x_3 1.0
ENDATA

المخرجات:

Problem:    VM
Rows:       4
Columns:    3 (3 integer, 3 binary)
Non-zeros:  7
Status:     INTEGER OPTIMAL
Objective:  cost = 3 (MINimum)

   No.   Row name        Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 cost                        3
     2 S1                          1             1
     3 S2                          1             1
     4 S3                          1             1

   No. Column name       Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 x_1          *              1             0             1
     2 x_2          *              1             0             1
     3 x_3          *              0             0             1

Integer feasibility conditions:

INT.PE: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

INT.PB: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

End of output

أيضًا ، لست واضحًا حول كيفية الحصول مباشرة على متجه X الذي يحل المشكلة ، على الرغم من ترميزه في الإخراج أعلاه في هذا القسم:

  No. Column name       Activity     
------ ------------    ------------- 
     1 x_1          *              1 
     2 x_2          *              1 
     3 x_3          *              0  

Answer 3

لقد حددت مشكلة برمجة عدد صحيح نقي. تتضمن معظم التطبيقات العملية عادة ما يسمى برمجة عدد صحيح مختلط حيث تكون بعض المتغيرات فقط عدد صحيح. يمكن العثور على برنامج تعليمي ومقال موجز حول هذا الموضوع:

http://mat.gsia.cmu.edu/orclass/integer/integer.html

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

حظا طيبا وفقك الله

Answer 4

بيثون: لب

Answer 5

يمكن أيضًا حل هذا النوع من المشكلات البسيطة باستخدام تقنية تسمى برمجة القيد. يمكنك العثور على مزيد من التفاصيل حول التقنية والمحللون المجانيين والتجاريين المتاحة لحل هذه المشكلات من مقابلة دخول ويكيبيديا. إذا كانت المشكلات التي تنطوي على متغيرات عدد صحيح أكثر تعقيدًا مما ذكرته ، فمن الأفضل أن تنظر في حلول البرمجة الخطية/البرمجة الصحيح للأغراض العامة (مثل GLPK). هناك مجموعة منهم ، بعض الأسماء هي: LPSOLVE (مجاني) ، IBM ILOG CPLEX (تجاري).

Answer 6

أنا أستخدم Python & Pyomo. هناك نظرة عامة جيدة على المزايا على موقع المشروع: http://www.pyomo.org

Answer 7

هنالك سؤال مماثل على scicomp.stackexchange.com وإجابة تسرد بعض المكتبات.