En la formulación del problema de asignación lineal

Question

Me estoy mirando a la definición estándar del problema de asignación como se define aquí

Mi pregunta tiene que ver con las dos restricciones (notación de látex sigue):

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

En concreto, ¿por qué la segunda restricción necesaria? No la primera ya cubren todos los pares de x_ {ij}?

Answer 1

Considere el x_ij matriz con la i que van sobre las filas, y j que van sobre las columnas.

La primera ecuación dice que para cada i (es decir, para cada fila!) La suma de los valores de esa fila es igual a 1.

Las ecuaciones de segundo dice, que para cada j (es decir, para cada columna!) La suma de los valores de esa columna es igual a 1.

Answer 2

No. Dado que todas las entradas de X son 0 o 1, una restricción dice 'hay exactamente un 1 en cada columna ' - el otro dice 'hay exactamente un 1 en cada fila '(siempre se me olvida en qué dirección subíndices de matriz redonda convencionalmente van). Estas declaraciones tienen valores de verdad independientes.

Answer 3

Esto no es ni remotamente un problema de programación. Pero voy a responder de todos modos.

La primera es una suma sobre j, para cada valor de i. La segunda es una suma sobre i, para cada valor de j.

Así que, esencialmente, uno de estos conjuntos de restricciones requiere que la suma a través de las filas de la matriz x_ {i, j} de la matriz debe ser la unidad. La otra limitación es el requisito de que la suma de las columnas que la matriz debe ser la unidad.

(editar) Parece que todavía no estamos siendo claro aquí. Considere la matriz

[0 1]
[0 1]

Uno debe aceptar que la suma a través de las filas de esta matriz es de 1 por cada fila. Sin embargo, cuando se forma la suma de los elementos de la primera columna, es cero, y la suma de los elementos de la segunda columna, encontramos 2.

Ahora, considere una matriz diferente.

[0 1]
[1 0]

Vea aquí que, la suma sobre las filas o de las columnas es siempre 1.