Premiers pas en RO: Énoncé et guide

Cours MAP 557, «Recherche Opérationnelle : aspects mathématiques et applications»

Séance 1, 22 Septembre 2017

Le traitement de la feuille de PC k s’étend parfoissur les séances k et k + 1. Pensez à ramener votrefeuille de PC à la séance suivante.1

Acquisition du cours

Signalons quelques résultats clés:

- le théorème de Minkowski-Weyl 2.21, établissantl’équivalence entre représention interne et représenta-tion externe des convexes polyédraux;

- le Corollaire 2.25: une fonction concave minorée sur unpolyèdre atteint son minimum en au moins un pointextrême de celui-ci;

- le Corollaire 2.34, donnant une condition suffisante denature algébrique (faisant intervenir la notion de totaleunimodularité) pour qu’un problème de programma-tion linéaire admette une solution entière.

- La Prop. 2.37 (Poincaré), donnant une condition suff-isante pour qu’une matrice soit totalement unimodu-laire.

Les preuves de ces résultats dépassant ce qu’on peutraisonnablement faire en amphi, nous ferons quelques exer-cices aidant à assimiler cette partie du cours. Les exercicessuivants nous permettrons d’appliquer ces résultats.

1.1 Problème de couverture

Un centre d’appel téléphonique a une courbe de charge:ct est le nombre de clients devant être servis à l’instant dis-cret t ∈ {1, . . . , T}. Des conseillers de clientèle répondentaux appels. On simplifie le problème en supposant que tousles appels sont de même type. On supposera qu’il y a k ho-raires de travail possibles, l’horaire i, pour i ∈ {1, . . . , k},étant caractérisé par un intervalle de présence du conseiller[αi, βi], avec 1 6 αi 6 βi 6 T , ce qui revient à faire ab-straction des pauses. On note Si le salaire à verser à unconseiller de clientèle travaillant de l’instant αi à l’instantβi. On souhaite minimiser le coût total des salaires versésaux conseillers, sachant que le nombre total de conseillersprésents à chaque instant t doit être supérieur ou égal à lacharge ct.

1. Modéliser ce problème par un programme linéaire ennombre entiers. Indications. On notera xi le nom-bre de conseillers convoqués dans l’horaire i, on ex-primera le coût total des salaires en fonction de x,et l’on écrira, pour chaque instant t, une contrainte

1Une copie des feuilles de PC peut être trouvée sur http://www.cmap.polytechnique.fr/~gaubert/RO, ainsi que sur le moodle ducours

linéaire avec inégalité exprimant la couverture de lademande à l’instant t.

2. Montrer que l’ensemble des solutions admissibles dece problème peut s’écrire comme l’ensemble des pointsentiers d’un polyèdre de la forme

Q = {x ∈ Rn | c 6 Dx 0 6 x} (1)

où la matrice D est une matrice d’intervalles, c’est-à-dire une matrice à coefficients 0, 1 telle que les 1apparaissent consécutivement sur une colonne.

3. Montrer qu’une matrice d’intervalles est totalementunimodulaire.

4. Conclure qu’il est équivalent de résoudre le problèmelinéaire en nombres entiers original et son relâché con-tinu (i.e. le programme linéaire obtenu en oubliant lacontrainte d’intégrité des variables). Quel est l’intérêtde ce dernier résultat?

D’ici quelques séances, vous pourrez retrouver ce résultatde manière intuitive, en modélisant le problème de couver-ture par un problème de flot à coût minimum.

1.2 Théorème de Birkhoff

On considère un graphe biparti complet avec 2n som-mets, que l’on peut voir comme un graphe avec deux sortesde sommets, les sommets féminins, notés {1, . . . , n}, etles sommets masculins, notés {1′, . . . , n′}, tel qu’une arête{i, j′} relie chaque sommet fille i à chaque sommet garçonj′. On munit cette arête d’un poids wij . On appelle cou-plage un ensemble d’arêtes C tel que chaque sommet appar-tienne au plus à une arête de C. Le poids d’un couplage estla somme des poids de ses arêtes. Le couplage est dit par-fait si chaque sommet appartient à exactement une arête.

1. Montrer que le poids maximum d’un couplage parfaitse modélise par le PLNE

w = maxx ∈ Nn×n

∀i,∑

j xij = 1,

∀j,∑

i xij = 1

∑16i6n, 16j6n

wijxij

2. Montrer que le problème relâché continu

maxx ∈ Rn×n

+

∀i,∑

j xij = 1,

∀j,∑

i xij = 1

∑16i6n, 16j6n

wijxij (2)

a même valeur que le PLNE.

1

Indication: on écrira les contraintes égalité sous laforme Dx = b, et l’on pourra appliquer le théorème dePoincaré pour montrer que D est totalement unimod-ulaire. (Nous retrouverons - sans effort - ce résultatune fois connu le cours sur les flots.)

3. On appelle matrice bistochastique une matrice admis-sible pour le problème (2). Montrer qu’une matricebistochastique est enveloppe convexe de matrices depermutations. (Théorème de Birkhoff).

4. Pour quelles valeurs de γ > 0 pouvez vous assurer quequels que soient les poids wij > 0, le maximum duproblème

maxx ∈ Rn×n

+

∀i,∑

j xij = 1,

∀j,∑

i xij = 1

∑16i6n, 16j6n

wijxγij

est atteint par une matrice de permutation x ?

5. A un bal, il y a n garçons et n filles, chaque garçonayant été présenté à r filles, et chaque fille ayant étéprésentée à r garçons. On suppose r > 1. Déduiredu théorème de Birkhoff qu’il est possible de formern couples de danseurs, de sorte que les danseurs d’unmême couple aient déjà été présentés l’un à l’autre.Indication. Considérer la matrice xij telle que xij = 1lorsque i a été présenté à j′ et 0 sinon.

1.3 “Vertex cover” est 2-approximable en tempspolynômial

Étant donné un graphe non-orienté, le problème de cou-verture par des sommets (“vertex cover”) consiste à trouverun ensemble de sommets de cardinalité minimum tel quechaque arête contienne au moins un sommet de cette en-semble.

1. Modéliser ce problème par un PNLE.

2. Donner un procédé très simple pour construire unecouverture à partir de la solution du relâché continu.

3. Montrer (plus astucieux) que le nombre de sommetsde la converture ainsi obtenue n’excède pas deux foisle nombre optimal de sommets d’une couverture.

1.4 Théorèmes de König-Egerváry et deKönig-Frobenius

Cet exercice prolonge l’exercice 1.2 sur le théorème deBirkhoff, dont il reprend les notations. Il s’appuie sur lathéorie de la dualité qui est exposée au Chapitre 2.

1. Montrer par un argument de dualité que

w = miny ∈ Rn, z ∈ Rn

∀i, j, yi + zj > wij

∑16i6n

yi +∑

16j6n

zj (3)

On s’intéresse maintenant au cas où wij ∈ {0, 1}. On noteG le graphe formé des arcs (i, j′) tels que wij = 1.

2. Montrer que le problème (2) revient alors à trouver uncouplage de cardinalité maximum dans G .

3. Peut-on conclure à partir du cours que l’optimum duproblème dual (3) est atteint en un point extrême?

4. Montrer que l’optimum du problème dual (3) nechange pas si l’on rajoute les conditions yi > 0 etzj > 0 pour tous 1 6 i, j 6 n. (Indication: montrerque l’on l’on peut toujours supposer qu’une solutionvérifie min16i6n yi = 0.)

5. En déduire que le problème dual (3) admet une solu-tion optimale (y, z) entière.

6. Montrer même (preuve un peu plus astucieuse) que ceproblème a une solution optimale y, z ∈ {0, 1}n.

7. On dit qu’un ensemble S de sommets couvre le grapheG si chaque arc de G contient au moins un sommet deS. En déduire très simplement que le cardinal max-imal d’un couplage dans G est égal au cardinal min-imal d’un ensemble de sommets couvrant G (c’est lethéorème de König-Egerváry).

8. Déduire le cas particulier suivant (Théorème de König-Frobenius): pour une matrice A de taille n× n, on a∏

16i6n

Aiσ(i) = 0, ∀σ ∈ Sn ,

si et seulement si il existe un ensemble de lignes I decardinal p, et un ensemble de colonnes J de cardinalq, tel que p+ q = n+ 1 et Aij = 0, ∀i ∈ I, ∀j ∈ J . Cerésultat généralise (de manière optimale) le fait qu’unematrice qui a une ligne nulle ou une colonne nulle àun déterminant nul!

9. Comment traiter le cas où le nombre de filles et degarçons diffèrent.

1.5 Théorème de Gale et Shapley sur lesmariages stables

Une autre approche du problème des mariages consisteà remplacer la fonction d’utilité de la société par despréférences individuelles: on suppose que chaque fille aun ordre de préférence (total) entre les différents garçonsqu’elle connait, et qu’il en est de même pour les garçons.Un ensemble de mariages est dit stable si lorsqu’une fille,disons Alice, et un garçon, disons Bob, ne sont pas mariésentre eux, soit Alice est mariée à un garçon qu’elle préfèreà Bob, soit Bob est marié à une fille qu’il préfère à Alice.On propose l’algorithme suivant.Chaque matin, chaque garçon invite à dîner la fille qu’il

préfère parmi celles qui ne lui ont pas déjà refusé une in-vitation. Chaque fille qui a été invitée dîne le soir avec legarçon qu’elle préfère parmi ceux qui l’ont invitée ce jourlà. L’algorithme se poursuit tant qu’au moins une invita-tion change. Les couples qui ont dîné entre eux le derniersoir sont mariés.

1. Montrer que cet algorithme termine.

2. Montre que toute fille qui est invitée un soir à dînerest sûre de dîner le lendemain avec un garçon qui luiplaise au moins autant.

3. Montrer que cet algorithme fournit un mariage stable.

2

MAP557, Recherche Opérationnelle:Aspects mathématiques et applications

Guide pour la résolution des exercicesSéance 1 (22 Septembre)

Corrigé: Problème de couverture

1. Le problème peut s’écrire comme suit:

Minx ∈ Nk

∑16i6k

xiSi ;

sous les contraintes

ct 6∑

1 6 i 6 kαi 6 t 6 βi

xi pour t ∈ {1, . . . , T}

Le coût total est en effet donné par la fonction x 7→∑16i6k xiSi (somme des salaires versés aux différents

conseillers). La contrainte

ct 6∑

1 6 i 6 kαi 6 t 6 βi

xi (4)

traduit la couverture de la charge à l’instant t.

2. Pour parvenir a la forme voulue, il suffit de poser:

Dti =

{1 si αi 6 t 6 βi

0 sinon,

de sorte que la contrainte de couverture de la charges’écrit c 6 Dx.La matrice D est à coefficients 0, 1, et a la propriétéremarquable que tous les 1 d’une même colonne appa-raissent consécutivement (car la colonne i de D n’estautre que le vecteur indicateur de l’intervalle [αi, βi]).

3. Notons M l’ensemble des matrices ayant cette pro-priété, et montrons que toute matrice de M est to-talement unimodulaire. Comme la propriété définis-sant M est préservée si l’on raye supprime une ligneou une colonne, il nous suffit de montrer que le déter-minant de toute matrice n×n A deM vaut 1,−1, ou0. Quitte à permuter les colonnes de A, on peut écrire

A =

1 . . . . . . 1 0 . . ....

... ∗1 . . . . . . 1 ∗0 1 . . . 1 ∗... ∗ ∗ ∗

en supposant (sinon detA = 0) que A n’aie pasdeux colonnes identiques. En soustrayant la premièrecolonnes à chacune des colonnes suivantes dont la pre-mière ligne est non nulle, on exprime le déterminantde A comme le déterminant d’une nouvelle matrice deM de taille (n−1)×(n−1), ce qui montre la propriétépar récurrence.

4. Comme la fonction linéaire x 7→ x · S est positive, etdonc minorée, sur le polyèdre des points admissiblesQ, il résulte du Corollaire 2.25 que le minimum estatteint en un point extrême du polyèdre Q. Comme Dest totalement unimodulaire, le Corollaire 2.34 montreque ce point extrême est entier.

Le problème en variables entières original est doncéquivalent au problème en variables réelles:

infx∈Q

∑16i6k

xiSi . (5)

Ce dernier peut être résolu par les algorithmes de pro-grammation linéaire vus dans la suite du cours (sim-plexe, points intérieurs), le simplexe retournant tou-jours un point extrême. (En fait, le plus efficace estd’utiliser un programme de flots à coût minimum. . . cequi pourra être fait une fois vue la modélisation parles flots.)

Corrigé: Théorème de Birkhoff

1. Étant sous-ensemble C ⊂ {1, . . . , n} × {1′, . . . , n′},posons xij = 1 si {i, j′} ∈ C et 0 sinon. On vérifieaussitôt que x est un point réalisable du PLNE ssi Cest un couplage parfait. En outre

∑ij wijxij donne le

poids du couplage.

2. Considérons

P = {x ∈ Rn×n+ | ∀i,∑j

xij = 1,∀j,∑i

xij = 1}. (6)

Soit X le vecteur de dimension n2 de coordonnéesx11, x12, . . . , xnn. On peut écrire les contraintes inégal-ités sous la forme 0 6 X,DX = e, où e = (1, . . . , 1)T .Chaque variable xkl apparaît seulement deux fois dansles contraintes∑

j

xij = 1,∑i

xij = 1

(prendre (i, j) = (k, l) dans les deux cas), et à chaquefois, le coefficient de xij est un. Le colonne de la ma-trice D correspondant aux indices (i, j) représente lescoefficients de xij , on en déduit que chaque colonne deD a tous ses coefficients nuls, sauf deux qui sont égauxà 1. Ceci suggère d’appliquer le lemme de Poincaré,qui affirme qu’une matrice formée de coefficients 0,±1est totalement unimodulaire si chacune de ses colonnesà au plus un 1 et un −1. On se ramène à cette situa-tion en multipliant chaque égalité de type

∑i xij = 1

par −1. La matrice D est donc bien totalement uni-modulaire. (Le lecteur qui trouve cette preuve sortiedu chapeau pourra se reporter au chapitre sur les flots,ou nous retrouverons ce résultat comme corollaire duthéorème d’optimalité des flots entiers.) D’après unrésultat du cours, la forme linéaire

x 7→ w · x =∑ij

wijcij

i

atteint son maximum en un point extrême de P , quiest entier en vertu de la totale unimodularité de D.Chaque point entier x de P est de la forme

xij =

{1 si j = σ(i)

0 sinon

avec σ permutation de {1, . . . , n}. Les permutationscorrespondent aux couplages parfaits. La valeur duproblème (2) est donc exactement le poids maximumd’un couplage parfait de cardinal n.

3. Les éléments de P sont exactement les matrices bis-tochastiques. D’après le théorème de Minkowski, P(qui est un polytope) est enveloppe convexe de sespoints extrêmes. Comme la matrice des contraintesdéfinissant P est totalement unimodulaire, les pointsextrêmes de P sont entiers. Or, les points entiers deP sont précisément les matrices de permutation. Onconclut que toute matrice bistochastique est enveloppeconvexe de matrices de permutations.

4. Pour γ > 1, le critère est convexe, en vertu d’unthéorème du cours, il atteint son maximum en unpoint extrême du polytope constituant l’ensemble ad-missible, c’est-à-dire, en vertu de ce qui précède, desmatrices de permutations. (Pour γ < 1, le critèreest strictement concave, et on trouve facilement descontre-exemples à la propriété demandée).

5. Soit B la matrice telle que Bij = 1 si la fille i a étéprésentée au garçon j. La condition que chaque garçonait été présenté à r filles, et que chaque fille ait étéprésentée à r garçons, exprime que la matrice r−1Best bistochastique. D’après la question précédente,r−1B est enveloppe convexe de matrices de permuta-tion. En particulier, il existe une permutation σ telleque r−1Biσ(i) > 0, pour tout i. La permutation σ four-nit une manière de former des couples de danseurs.

Corrigé: “Vertex cover” est 2-approximable entemps polynômial

1. Soit {1, . . . , n} l’ensemble des sommets, et El’ensemble des arêtes. Représentons un sous-ensembleC de {1, . . . , n} par un vecteur x ∈ {0, 1}n tel quexi = 1 si i ∈ C et 0 sinon. On vérifie que C couvre lesarêtes si et seulement si

xi + xj > 1, ∀{i, j} ∈ E .

Le problème revient donc à résoudre le PLNE

min∑i

xi, x ∈ {0, 1}n, xi + xj > 1∀{i, j} ∈ E .

Le relâché continu est donné par

min∑i

xi, x ∈ [0, 1]n, xi + xj > 1∀{i, j} ∈ E

2. Soit x∗ un point réalisable du relâché continu. PosonsC∗ = {i | xi > 1/2}. Comme xi+xj > 1 implique quexi > 1/2 ou xj > 1/2, C∗ est bien une couverture.

3. Prenons en particulier pour x∗ une solution optimaledu relâché continu, et soit x une solution optimale duPNLE et C la couverture associée. On par construc-tion du relâché continu∑

16i6n

x∗i 6∑

16i6n

xi = |C| .

Alors

|C∗| =∑i∈C∗

1 6∑i∈C∗

2x∗i

6 2(∑

16i6n

x∗i )

6 2(∑

16i6n

xi) = 2|C| ,

ce qui montre le résultat.

La couverture approchée à un facteur 2 près, C∗, est ainsiobtenue par programmation linéaire, et donc en tempspolynômial.Signalons une erreur intéressante faite par certains

élèves, qui ont écrit que pour tout nœud i, la somme des xjsur l’ensemble des voisins de i est > 1 (au lieu de xi+xj > 1pour tout arc). Cette contrainte est plus faible que la con-trainte de couverture. Par exemple, dans une triangle, lacouverture minimale est de cardinal 2, mais la contrainteen question donnerait une solution de cardinal 1.Signalons enfin que trouver une couverture optimale est

NP-dur. Par contre, le théorème de König-Egerváry (cf.exercice “théorème de Birkhoff” supra) montre que dans lecas des graphes bipartis, calculer une couverture est équiv-alent à un problème de flots (donc polynômial).

Corrigé: Théorèmes de König-Egerváry et deKönig-Frobenius

1. Formons le Lagrangien

L(x; y, z, λ) =∑ij

wijxij +∑i

yi(1−∑j

xij)

+∑j

zj(1−∑i

xij) +∑ij

xijλij

de sorte que la valeur du problème primal s’écrit

supx∈Rn×n

infy ∈ Rn, z ∈ Rm,

λ ∈ Rn×n+

L(x; y, z, λ) .

Le problème dual s’obtient en commutant le sup etl’inf:

infy ∈ Rn, z ∈ Rm,

λ ∈ Rn×n+

supx∈Rn×m

L(x; y, z, λ)

soit

infy ∈ Rn, z ∈ Rm,

λ ∈ Rn×n+

supx∈Rn×m

∑ij

xij(wij − yi − zj + λij)

+∑i

yi +∑j

zj

ii

soit

infy ∈ Rn, z ∈ Rn

∀i, j, yi + zj > wij

∑16i6n

yi +∑

16j6n

zj . (7)

Le problème primal (2) admet un point admissible(par exemple n’importe quelle matrice de permuta-tion). D’après le théorème de dualité forte 2.44, leproblème primal et le problème dual ont même valeur.CQFD. (On peut argumenter de manière alternativeque le problème dual à trivialement un point admissi-ble (il suffit de prendre y et z assez grand), et donc,toujours par le théorème de dualité forte, la valeur dubidual, c’est-à-dire du primal, coïncide avec celle dudual.)

2. Si C est un couplage parfait du graphe biparti complet,sa restriction aux arêtes de G est un couplage de G quià même poids car les arêtes qui ne sont pas danas G ontun poids nul. Réciproquement, un couplage optimalC dans G peut se compléter en un couplage parfaitdans le graphe biparti complet (il suffit de marier demanière arbitraire les filles et les garçons qui ne sontpas déjà mariés dans C) sans changer le poids puisqueles nouveaux couples ont un poids nul. L’équivalencedemandée en résulte.

3. Le polyédre des solutions admissibles est invariant partoute transformation qui associe à un vecteur (y, z) levecteur (y− te, z+ te), pour tout t ∈ R, où e désigne levecteur unitaire de Rn. Ce polyédre contient donc unedroite affine (de direction (−e, e)), et n’admet aucunpoint extrême!

4. D’après la question précédente, si (y, z) est une solu-tion optimale, alors pour tout t ∈ R, (y(t), z(t)) :=(y − te, z + te) est encore une solution admissible,et comme elle a même coût, elle est également op-timale. En choisissant t = min16i6n yi, on obtientmin16i6n yi(t) = 0. On peut donc sans perte degénéralité supposer que min16i6n yi = 0. En parti-culier, il existe un indice i∗ tel que yi∗ = 0. Par con-séquent, pour tout 1 6 j 6 n, zj > wi∗j > 0.

5. Le problème primal, qui est un problème de flot degain maximum, peut s’écrire

maxx>0,Mx=b

w · x ,

oùM est la matrice d’incidence nœuds-arcs du graphedécrit dans l’Exemple 3.5, et b un vecteur de taille n+n(dont les coordonnées valent +1 pour les nœuds detype i (fille) et −1 pour les nœuds de type j′ (garçon).D’après la Proposition 3.12, une matrice d’incidencenœuds arcs est totalement unimodulaire, donc M esttotalement unimodulaire. Le problème dual s’écrit demanière synthétique (voir l’Example 2.38, en prenantgarde que le primal est un problème de maximisationet non un problème de minimisation):

infM>u>w

b · u

avec

u =

(y−z

),

les vecteurs y et z étant précisément les vecteurs ap-paraissant dans la formulation du problème dual de lasection précédente, de sorte que b · u =

∑i yi +

∑j zj .

Comme M est totalement unimodulaire, la matriceM> est évidemment totalement unimodulaire. Ra-joutons les contraintes de borne yi > 0 et zj > 0 cequi d’après la question précédente, ne change pas lavaleur du dernier problème, de sorte que l’ensembledes solutions admissibles me contient pas de droiteaffine. Comme w est supposé entier, et que la fonc-tion objectif

∑i yi+

∑zj est minorée (par 0), on peut

maintenant appliquer le théorème d’optimalité des so-lutions entières (Corollaire 2.34) qui démontre que leproblème dual (2) admet nécessairement une solutionentière.

6. Rédaction 1. Soit (y, z) une solution optimale entière.L’argument de l’avant-dernière question montre que(y(t), z(t)) avec t = min16i6b yi est encore une so-lution optimale entière. On peut donc supposer quemin16i6n yi = 0. Comme le critère est strictementcroissant en z, y étant fixé, on a intérêt à prendre z leplus petit possible, ce qui montre qu’un (y, z) solutionoptimale du dual vérifie nécessairement

zj = maxi

(wij − yi) ,

et pour une raison symmétrique

yi = maxj

(wij − zj) .

En prenant i∗ tel que yi∗ = 0, on déduit que zj >wi∗j > 0, pour tout j. Comme y > 0, on déduit aussique zj 6 maxi wij 6 1. On a donc 0 6 z 6 1, etsachant que z est entier, ceci montre que z ∈ {0, 1}n.Comme z > 0 et w 6 1, on déduit de yi = maxj(wij −zj) que y 6 1. Comme par hypothèse, mini yi = 0,on a en particulier y > 0, et donc y ∈ {0, 1}n. Uncouple de vecteurs y, z ∈ {0, 1}n tels que yi + zj >wij correspond exactement à un ensemble de sommets{i | yi = 1} ∪ {j′ | zj = 1} couvrant G . Le théorèmede dualité forte montre donc que le cardinal maximald’un couplage du graphe G (valeur du primal) coïncideavec le cardinal minimal d’un ensemble de sommetscouvrants G (valeur du dual).

Rédaction 2: variante plus rapide. D’après la questionprécédente, l’optimum du dual est atteint pour y, zà coordonnées entières positives ou nulles. Commeyi + zj > wij et wij ∈ {0, 1}, yi := min(yi, 0) et zj :=min(zj , 0) vérifient encore yi+ zj > wij , et l’on conclutcomme dans la fin de la question précédente.

7. Immédiat à partir de la question précédente: on ob-tient l’ensemble des sommets couvrant en prenant lesi tels que yi = 1 et les j′ tels que zj = 1.

Voici une illustration du théorème de König-Egerváry.

iii

Soit la matrice

w =

1 1 11 0 01 0 0

Le premier garçon (colonne 1) peut être marié auxtrois filles, la première fille (ligne 1) peut être mariéeaux trois garçons, et c’est tout. On peut former deuxcouples (le garçon 1 avec la fille 2, le garçon 2 avecla fille 1 par exemple). Les coefficients non-nuls de lamatrice sont concentrés sur la ligne 1 et la colonne 1,ce qui signifie qu’il y a une couverture de cardinal 2du graphe, formé des sommets “garçon 1” et “fille 1”.L’existence de cette couverture de cardinal 2 montreque l’on ne peut pas former plus de 2 couples.

8. Soit A une matrice de taille n× n. Dire que∏16i6n

Aiσ(i) = 0, ∀σ ∈ Sn , (8)

c’est dire que le cardinal maximal d’un couplage dansle graphe formé des arcs {i, j′} tels que Aij 6= 0 eststrictement inférieur à n, et donc inférieur où égal àn − 1. D’après la question précédente, il existe unvecteur y ∈ {0, 1}n et un vecteur z ∈ {0, 1}n formantun point admissible pour le dual, c’est-à-dire tels que

Aij 6= 0 =⇒ yi = 1 ou zj = 1 ,

et ayant pour valeur∑i yi +

∑j zj 6 n − 1. En

notant p′ le nombre de coefficients 1 de y, et q′ lenombre de coefficients 1 de z, cela revient à dire quep′ + q′ 6 n − 1, et que les coefficients non-nuls deA appartiennent à l’union de p′ lignes et q′ colonnes.Posons p = n − p′, q = n − q′. Il en résulte que lerectangle complémentaire, formé de l’intersection desp lignes et q colonnes restantes de A, est identiquementnul, avec p+q = (n−p′)+(n−q′) > 2n−(n−1) = n+1.La réciproque s’obtient en remontant l’argument quel’on vient de faire.

9. Si par exemple il y a m filles et n garçons, avec m < n,pour se ramener à ce qui précède, il suffit de rajoutern−m filles imaginaires, le gain wij étant nul quand iest imaginaire.

Corrigé: Théorème de Gale et Shapley sur lesmariages stables

1. Une invitation qui a été refusée ne sera jamais répétée.À chaque étape précédant la fin de l’algorithme, aumoins une invitation est refusée. Le nombre d’étapesavant que la liste des invitations ne se stabilise est doncborné par le nombre d’invitations possibles, i.e. par lenombre de filles fois le nombre de garçons.

2. Si une fille, disons Alice, est invitée à dîner par ungarçon, disons Bob, c’est que Bob préfère Alice àtoutes celles qui ne l’ont pas déja refusé. Alice est doncsûre d’être réinvitée le lendemain par Bob, mais ellesera peut être aussi invitée par de nouveaux garçons

qui viennent d’essuyer des refus et pour qui elle est dé-sormais le meilleur choix restant. Peut être que Char-lie, l’un de ces nouveaux garçons, lui plait plus queBob, dans ce cas elle dînera avec Charlie, en congédi-ant Bob. Dans tous les cas, Alice dîne le lendemainavec un garçon au moins aussi plaisant.

3. Considérons le mariage obtenu à l’isse de l’algorithme,et imaginons qu’une fille, disons Alice, rencontre ungarçon avec lequel elle n’est pas mariée, disons Bob.Imaginons qu’Alice préfère Bob a son mari. Alors, Bobne l’a jamais invitée, car si cela avait été le cas, envertu de la question précédente, Alice serait mariée àun garçon au moins aussi plaisant que Bob, contredis-ant notre hypothèse. Si Bob préfé Alice à son épouseCorinne, alors, le soir où il a invité Corinne à dînerpour la première fois, il n’a pas respecté l’algorithme,car Corinne n’était pas sa préférée parmi celles nel’ayant pas éconduit (il aurait dû inviter Alice à saplace, ou peut être Delphine qui lui plaisait encoreplus qu’Alice). C’est donc que Bob préfère Corinne àAlice, le mariage est stable et la morale est sauve.

iv