على صياغة مشكلة المهمة الخطية

Question

أنا أبحث في التعريف القياسي لمشكلة المهمة على النحو المحدد هنا

سؤالي هو القيام بالقيود (يتبع تدوين اللاتكس):

\sum_{j=1}^n(x_{ij}) = 1 for all i = 1, ... , n
\sum_{i=1}^n(x_{ij}) = 1 for all j = 1, ... , n

على وجه التحديد ، لماذا القيد الثاني المطلوب؟ ألا يغطي الأول بالفعل جميع أزواج x_ {ij}؟

Answer 1

النظر في المصفوفة x_ij مع ال i بدءا من الصفوف ، و j بدءا من الأعمدة.

المعادلة الأولى تقول ذلك لكل منها i (وهذا هو ، لكل صف!) مجموع القيم في هذا الصف يساوي 1.

المعادلات الثانية تقول thta لكل منها j (أي لكل عمود!) مجموع القيم في هذا العمود يساوي 1.

Answer 2

لا. بالنظر إلى أن جميع الإدخالات في X نكون 0 أو 1, ، يقول أحد القيود "هناك واحد بالضبط 1 في كل عمودي" - يقول الآخر" هناك واحد بالضبط 1 في كل صف'(أنا دائما أنسى أي طريقة Round Matrix Screprics التقليدية يذهب). هذه العبارات لها قيم الحقيقة المستقلة.

Answer 3

هذه ليست حتى مشكلة البرمجة عن بعد. لكنني سأجيب عليه على أي حال.

الأول هو مبلغ أكثر من j ، لكل قيمة i. والثاني هو مبلغ أكثر من أنا ، لكل قيمة j.

لذلك ، تتطلب إحدى مجموعات القيود هذه أن يكون المبلغ عبر صفوف مصفوفة المصفوفة X_ {i ، j} وحدة. القيد الآخر هو شرط أن يكون مجموع أعمدة تلك المصفوفة هو الوحدة.

(تحرير) يبدو أننا ما زلنا غير واضحين هنا. النظر في المصفوفة

[0 1]
[0 1]

يجب على المرء أن يوافق على أن المبلغ عبر صفوف هذه المصفوفة هو 1 لكل صف. ومع ذلك ، عندما تشكل مجموع عناصر العمود الأول ، يكون صفرًا ، ومجموع العناصر في العمود الثاني ، نجد 2.

الآن ، فكر في مصفوفة مختلفة.

[0 1]
[1 0]

تعرف على ذلك هنا ، المبلغ فوق الصفوف أو أسفل الأعمدة هو دائمًا 1.