Nella formulazione del problema assegnazione lineare

Question

sto guardando la definizione standard del problema incarico come definito qui

La mia domanda è a che fare con i due vincoli (notazione lattice 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

In particolare, il motivo per cui il secondo vincolo richiesto? Non il primo già coprono tutte le coppie di x_ {ij}?

Answer 1

Si consideri la x_ij matrice con la i vanno sulle righe, e j spaziando colonne.

La prima equazione dice che per ogni i (che è, per ogni riga!) La somma dei valori in quella fila è uguale a 1.

Il secondo equazioni dice thta per ogni j (cioè, per ogni colonna!) La somma dei valori in tale colonna è uguale a 1.

Answer 2

No. Dato che tutte le voci in X sono 0 o 1, un vincolo dice 'c'è esattamente un 1 in ogni Colonna ' - l'altro dice 'c'è esattamente un 1 in ogni riga '(mi dimentico sempre che modo gli indici di matrice rotonda convenzionalmente vanno). Queste dichiarazioni hanno valori di verità indipendenti.

Answer 3

Questa non è neanche lontanamente un problema di programmazione. Ma io ti risponderò lo stesso.

La prima è una somma su j, per ogni valore di i. Il secondo è una somma sulle i, per ogni valore di j.

Quindi, in sostanza, uno di questi insiemi di vincolo impone che la somma tra le righe della matrice di x_ {i, j} matrice deve essere l'unità. L'altro vincolo è un requisito che la somma le colonne di detta matrice deve essere l'unità.

(edit) Sembra che stiamo ancora non essere chiari qui. Si consideri la matrice

[0 1]
[0 1]

Uno deve accettare che la somma di tutti i righe di questa matrice è 1 per ogni riga. Tuttavia, quando si forma la somma degli elementi della prima colonna, è pari a zero, e la somma degli elementi nella seconda colonna, troviamo 2.

Ora, si consideri una matrice diversa.

[0 1]
[1 0]

vedi che qui, la somma sopra le righe o le colonne è sempre 1.