Sobre a formulação do problema de atribuição linear

Question

Estou olhando para a definição padrão do problema de atribuição, conforme definido aqui

Minha pergunta é fazer com as duas restrições (a notação do látex segue):

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

Especificamente, por que a segunda restrição necessária? O primeiro já cobre todos os pares de x_ {ij}?

Answer 1

Considere a matriz x_ij com o i variando sobre as fileiras e j variando sobre as colunas.

A primeira equação diz que para cada i (Ou seja, para cada linha!) A soma dos valores nessa linha é igual a 1.

As segundas equações dizem Thta para cada j (Ou seja, para cada coluna!) A soma dos valores nessa coluna é igual a 1.

Answer 2

Não. Dado que todas as entradas em X são 0 ou 1, uma restrição diz 'existe exatamente um 1 em cada coluna' - o outro diz' existe exatamente um 1 em cada fileira'(Eu sempre esqueço de que maneira os subscritos da matriz redonda vão convencionalmente). Essas declarações têm valores de verdade independentes.

Answer 3

Isso nem é remotamente um problema de programação. Mas eu vou responder de qualquer maneira.

O primeiro é uma soma sobre J, para cada valor de i. O segundo é uma soma sobre i, para cada valor de j.

Portanto, essencialmente, um desses conjuntos de restrições exige que a soma entre as linhas da matriz da matriz x_ {i, j} deve ser a unidade. A outra restrição é um requisito de que a soma nas colunas dessa matriz deva ser unidade.

(Editar) Parece que ainda não estamos sendo claros aqui. Considere a matriz

[0 1]
[0 1]

É preciso concordar que a soma nas linhas desta matriz é 1 para cada linha. No entanto, quando você forma a soma dos elementos da primeira coluna, ela é zero e a soma dos elementos na segunda coluna, encontramos 2.

Agora, considere uma matriz diferente.

[0 1]
[1 0]

Veja que aqui, a soma sobre as linhas ou as colunas é sempre 1.