Sur la formulation du problème d'affectation linéaire

Question

Je regarde la définition standard du problème d'affectation tel que défini ici

Ma question concerne les deux contraintes (la notation latex suit) :

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

Plus précisément, pourquoi la deuxième contrainte est-elle requise ?Le premier ne couvre-t-il pas déjà toutes les paires de x_{ij} ?

Answer 1

Considérons la matrice x_ij avec le i allant sur les lignes, et j allant sur les colonnes.

La première équation indique que, pour chaque i (qui est, pour chaque rangée!) La somme des valeurs de cette ligne est égal à 1.

Les deuxièmes équations dit CGU pour chaque j (qui est, pour chaque colonne!) La somme des valeurs de cette colonne est égal à 1.

Answer 2

Non. Étant donné que toutes les entrées X sont 0 ou 1, une contrainte dit «il y a exactement un 1 dans chaque colonne - l'autre dit « il y a exactement un 1 dans chaque ligne (J'oublie toujours de quelle manière la matrice ronde indices vont de façon classique). Ces déclarations ont des valeurs de vérité indépendantes.

Answer 3

Ce n’est même pas un problème de programmation.Mais je vais quand même y répondre.

Le premier est une somme sur j, pour CHAQUE valeur de i.La seconde est une somme sur i, pour CHAQUE valeur de j.

Donc, essentiellement, l'un de ces ensembles de contraintes exige que la somme sur les lignes de la matrice x_{i,j} soit égale à l'unité.L'autre contrainte est que la somme des colonnes de cette matrice doit être égale à l'unité.

(modifier) ​​Il semble que nous ne soyons toujours pas clairs ici.Considérons la matrice

[0 1]
[0 1]

Il faut convenir que la somme des lignes de cette matrice est de 1 pour chaque ligne.Or, lorsque l’on forme la somme des éléments de la première colonne, elle est nulle, et la somme des éléments de la deuxième colonne, on trouve 2.

Considérons maintenant une matrice différente.

[0 1]
[1 0]

Voyez qu'ici, la somme sur les lignes ou dans les colonnes est toujours 1.