104
1-1 Cours 3: Programmation lin´ eaire Position du probl` eme Dualit´ e. eg´ en´ erescence et terminaison de l’algorithme Algorithme du simplexe g´ en´ erique Gilles Schaeffer INF-550-3: Programmation lin´ eaire

Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

Embed Size (px)

Citation preview

Page 1: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

1-1

Cours 3: Programmation lineaire

• Position du probleme

• Dualite.

• Degenerescence et terminaison de l’algorithme

• Algorithme du simplexe generique

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 2: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

2-1

Cours 3: Programmation lineaire

• Position du probleme

• Dualite.

• Degenerescence et terminaison de l’algorithme

• Algorithme du simplexe generique

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 3: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

3-1

Un probleme de programmation lineaireDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Probleme: Trouver un point x = (x1, . . . , xn) qui

• satisfait les m contraintes ai,1x1 + . . . + ai,nxn ≤ bi,

• et maximise le produit c · x = c1x1 + . . . + cnxn.

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 4: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

3-2

Un probleme de programmation lineaireDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Probleme: Trouver un point x = (x1, . . . , xn) qui

• satisfait les m contraintes ai,1x1 + . . . + ai,nxn ≤ bi,

• et maximise le produit c · x = c1x1 + . . . + cnxn.

Reformulation matricielle: on cherche max(c · x | Ax ≤ b).

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 5: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

3-3

Un probleme de programmation lineaireDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Probleme: Trouver un point x = (x1, . . . , xn) qui

• satisfait les m contraintes ai,1x1 + . . . + ai,nxn ≤ bi,

• et maximise le produit c · x = c1x1 + . . . + cnxn.

Reformulation matricielle: on cherche max(c · x | Ax ≤ b).

Gilles Schaeffer INF-550-3: Programmation lineaire

Remarque: Les ai,j , bi et ci peuvent etre negatifs, on peut doncmodeliser des contraintes ≥ ou = et chercher min au lieu de max.

Page 6: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

4-1

Un exemple bateau: le fleuristeDonnee. En stock: 50 lys, 80 roses, 80 jonquilles.

Composition des bouquets au catalogue:

• 10 lys, 10 roses, 20 jonquilles: 4 euros

• 10 lys, 20 roses, 10 jonquilles: 5 euros

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 7: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

4-2

Un exemple bateau: le fleuristeDonnee. En stock: 50 lys, 80 roses, 80 jonquilles.

Composition des bouquets au catalogue:

• 10 lys, 10 roses, 20 jonquilles: 4 euros

• 10 lys, 20 roses, 10 jonquilles: 5 euros

Probleme Quels bouquets preparer si on est assure de tout vendre ?

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 8: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

4-3

Un exemple bateau: le fleuristeDonnee. En stock: 50 lys, 80 roses, 80 jonquilles.

Composition des bouquets au catalogue:

• 10 lys, 10 roses, 20 jonquilles: 4 euros

• 10 lys, 20 roses, 10 jonquilles: 5 euros

Probleme Quels bouquets preparer si on est assure de tout vendre ?

x bouquets

y bouquets

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 9: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

4-4

Un exemple bateau: le fleuristeDonnee. En stock: 50 lys, 80 roses, 80 jonquilles.

Composition des bouquets au catalogue:

• 10 lys, 10 roses, 20 jonquilles: 4 euros

• 10 lys, 20 roses, 10 jonquilles: 5 euros

Probleme Quels bouquets preparer si on est assure de tout vendre ?

x bouquets

y bouquets

Contraintes: sur les lys: 10x + 10y ≤ 50

sur les roses: 10x + 20y ≤ 80

sur les jonquilles: 20x + 10y ≤ 80

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 10: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

4-5

Un exemple bateau: le fleuristeDonnee. En stock: 50 lys, 80 roses, 80 jonquilles.

Composition des bouquets au catalogue:

• 10 lys, 10 roses, 20 jonquilles: 4 euros

• 10 lys, 20 roses, 10 jonquilles: 5 euros

Probleme Quels bouquets preparer si on est assure de tout vendre ?

x bouquets

y bouquets

Contraintes: sur les lys: 10x + 10y ≤ 50

sur les roses: 10x + 20y ≤ 80

sur les jonquilles: 20x + 10y ≤ 80

x ≥ 0 y ≥ 0

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 11: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

4-6

Un exemple bateau: le fleuristeDonnee. En stock: 50 lys, 80 roses, 80 jonquilles.

Composition des bouquets au catalogue:

• 10 lys, 10 roses, 20 jonquilles: 4 euros

• 10 lys, 20 roses, 10 jonquilles: 5 euros

Probleme Quels bouquets preparer si on est assure de tout vendre ?

x bouquets

y bouquets

Contraintes: sur les lys: 10x + 10y ≤ 50

sur les roses: 10x + 20y ≤ 80

sur les jonquilles: 20x + 10y ≤ 80

Fonction economique a maximiser: max(4x + 5y).

x ≥ 0 y ≥ 0

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 12: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

4-7

Un exemple bateau: le fleuristeDonnee. En stock: 50 lys, 80 roses, 80 jonquilles.

Composition des bouquets au catalogue:

• 10 lys, 10 roses, 20 jonquilles: 4 euros

• 10 lys, 20 roses, 10 jonquilles: 5 euros

Probleme Quels bouquets preparer si on est assure de tout vendre ?

x bouquets

y bouquets

Contraintes: sur les lys: 10x + 10y ≤ 50

sur les roses: 10x + 20y ≤ 80

sur les jonquilles: 20x + 10y ≤ 80

Fonction economique a maximiser: max(4x + 5y).

x ≥ 0 y ≥ 0 x

y

0 11 2 3 40

1

2

3

4

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 13: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

4-8

Un exemple bateau: le fleuristeDonnee. En stock: 50 lys, 80 roses, 80 jonquilles.

Composition des bouquets au catalogue:

• 10 lys, 10 roses, 20 jonquilles: 4 euros

• 10 lys, 20 roses, 10 jonquilles: 5 euros

Probleme Quels bouquets preparer si on est assure de tout vendre ?

x bouquets

y bouquets

Contraintes: sur les lys: 10x + 10y ≤ 50

sur les roses: 10x + 20y ≤ 80

sur les jonquilles: 20x + 10y ≤ 80

Fonction economique a maximiser: max(4x + 5y).

x ≥ 0 y ≥ 0 x

y

0 11 2 3 40

1

2

3

4

16

22

23

20

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 14: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

4-9

Un exemple bateau: le fleuristeDonnee. En stock: 50 lys, 80 roses, 80 jonquilles.

Composition des bouquets au catalogue:

• 10 lys, 10 roses, 20 jonquilles: 4 euros

• 10 lys, 20 roses, 10 jonquilles: 5 euros

Probleme Quels bouquets preparer si on est assure de tout vendre ?

x bouquets

y bouquets

Contraintes: sur les lys: 10x + 10y ≤ 50

sur les roses: 10x + 20y ≤ 80

sur les jonquilles: 20x + 10y ≤ 80

Fonction economique a maximiser: max(4x + 5y).

x ≥ 0 y ≥ 0 x

y

0 11 2 3 40

1

2

3

4

16

22

23

20

c

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 15: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

4-10

Un exemple bateau: le fleuristeDonnee. En stock: 50 lys, 80 roses, 80 jonquilles.

Composition des bouquets au catalogue:

• 10 lys, 10 roses, 20 jonquilles: 4 euros

• 10 lys, 20 roses, 10 jonquilles: 5 euros

Probleme Quels bouquets preparer si on est assure de tout vendre ?

x bouquets

y bouquets

Contraintes: sur les lys: 10x + 10y ≤ 50

sur les roses: 10x + 20y ≤ 80

sur les jonquilles: 20x + 10y ≤ 80

Fonction economique a maximiser: max(4x + 5y).

x ≥ 0 y ≥ 0 x

y

0 11 2 3 40

1

2

3

4

16

22

23

20

c

Lorsqu’on a les contraintes xi ≥ 0 on peut toujours penser en termeseconomiques: produits finis, matieres premieres, benefice.

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 16: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

5-1

Interpretation geometriqueDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 17: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

5-2

Interpretation geometriqueDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Chaque equation ai,1x1 + . . . + ai,nxn ≤ bi coupe l’espace en 2,le long d’un l’hyperplan normal au vecteur Li = (ai,1, . . . , ai,n) .

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 18: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

5-3

Interpretation geometriqueDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Chaque equation ai,1x1 + . . . + ai,nxn ≤ bi coupe l’espace en 2,le long d’un l’hyperplan normal au vecteur Li = (ai,1, . . . , ai,n) .

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 19: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

5-4

Interpretation geometriqueDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Chaque equation ai,1x1 + . . . + ai,nxn ≤ bi coupe l’espace en 2,le long d’un l’hyperplan normal au vecteur Li = (ai,1, . . . , ai,n) .

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 20: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

5-5

Interpretation geometriqueDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Chaque equation ai,1x1 + . . . + ai,nxn ≤ bi coupe l’espace en 2,le long d’un l’hyperplan normal au vecteur Li = (ai,1, . . . , ai,n) .

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 21: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

5-6

Interpretation geometriqueDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Chaque equation ai,1x1 + . . . + ai,nxn ≤ bi coupe l’espace en 2,le long d’un l’hyperplan normal au vecteur Li = (ai,1, . . . , ai,n) .

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 22: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

5-7

Interpretation geometriqueDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Chaque equation ai,1x1 + . . . + ai,nxn ≤ bi coupe l’espace en 2,le long d’un l’hyperplan normal au vecteur Li = (ai,1, . . . , ai,n) .

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 23: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

5-8

Interpretation geometriqueDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Chaque equation ai,1x1 + . . . + ai,nxn ≤ bi coupe l’espace en 2,le long d’un l’hyperplan normal au vecteur Li = (ai,1, . . . , ai,n) .

L’ensemble des x satisfaisant Ax ≤ bforme un polyhedre convexe P

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 24: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

5-9

Interpretation geometriqueDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Chaque equation ai,1x1 + . . . + ai,nxn ≤ bi coupe l’espace en 2,le long d’un l’hyperplan normal au vecteur Li = (ai,1, . . . , ai,n) .

L’ensemble des x satisfaisant Ax ≤ bforme un polyhedre convexe P

eventuellement vide

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 25: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

5-10

Interpretation geometriqueDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Chaque equation ai,1x1 + . . . + ai,nxn ≤ bi coupe l’espace en 2,le long d’un l’hyperplan normal au vecteur Li = (ai,1, . . . , ai,n) .

L’ensemble des x satisfaisant Ax ≤ bforme un polyhedre convexe P

eventuellement vide

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 26: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

5-11

Interpretation geometriqueDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Chaque equation ai,1x1 + . . . + ai,nxn ≤ bi coupe l’espace en 2,le long d’un l’hyperplan normal au vecteur Li = (ai,1, . . . , ai,n) .

L’ensemble des x satisfaisant Ax ≤ bforme un polyhedre convexe P

eventuellement vide ou non borne

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 27: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

5-12

Interpretation geometriqueDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Chaque equation ai,1x1 + . . . + ai,nxn ≤ bi coupe l’espace en 2,le long d’un l’hyperplan normal au vecteur Li = (ai,1, . . . , ai,n) .

L’ensemble des x satisfaisant Ax ≤ bforme un polyhedre convexe P

Le vecteur c indique la direction danslaquelle on optimise: max(c · x | x ∈ P )

eventuellement vide ou non borne

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 28: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

5-13

Interpretation geometriqueDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Chaque equation ai,1x1 + . . . + ai,nxn ≤ bi coupe l’espace en 2,le long d’un l’hyperplan normal au vecteur Li = (ai,1, . . . , ai,n) .

L’ensemble des x satisfaisant Ax ≤ bforme un polyhedre convexe P

Le vecteur c indique la direction danslaquelle on optimise: max(c · x | x ∈ P )

eventuellement vide ou non borne

Gilles Schaeffer INF-550-3: Programmation lineaire

L’optimum peut etre a l’infini.

Page 29: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

5-14

Interpretation geometriqueDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Chaque equation ai,1x1 + . . . + ai,nxn ≤ bi coupe l’espace en 2,le long d’un l’hyperplan normal au vecteur Li = (ai,1, . . . , ai,n) .

L’ensemble des x satisfaisant Ax ≤ bforme un polyhedre convexe P

Le vecteur c indique la direction danslaquelle on optimise: max(c · x | x ∈ P )

eventuellement vide ou non borne

Gilles Schaeffer INF-550-3: Programmation lineaire

L’optimum peut etre a l’infini.

Page 30: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

5-15

Interpretation geometriqueDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Chaque equation ai,1x1 + . . . + ai,nxn ≤ bi coupe l’espace en 2,le long d’un l’hyperplan normal au vecteur Li = (ai,1, . . . , ai,n) .

L’ensemble des x satisfaisant Ax ≤ bforme un polyhedre convexe P

Le vecteur c indique la direction danslaquelle on optimise: max(c · x | x ∈ P )

eventuellement vide ou non borne

S’il est fini, il est atteint en un sommet.C’est toujours le cas si P est borne.

Gilles Schaeffer INF-550-3: Programmation lineaire

L’optimum peut etre a l’infini.

Page 31: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

5-16

Interpretation geometriqueDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Chaque equation ai,1x1 + . . . + ai,nxn ≤ bi coupe l’espace en 2,le long d’un l’hyperplan normal au vecteur Li = (ai,1, . . . , ai,n) .

L’ensemble des x satisfaisant Ax ≤ bforme un polyhedre convexe P

Le vecteur c indique la direction danslaquelle on optimise: max(c · x | x ∈ P )

eventuellement vide ou non borne

Gilles Schaeffer INF-550-3: Programmation lineaire

Par convexite, un sommet est optimum siet seulement si il est meilleur que ses voisins.

Page 32: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

5-17

Interpretation geometriqueDonnee: Une matrice reelle A = (ai,j) de taille m× n,

un vecteur b = (b1, . . . , bm) de taille m,un vecteur c = (c1, . . . , cn) de taille n.

Chaque equation ai,1x1 + . . . + ai,nxn ≤ bi coupe l’espace en 2,le long d’un l’hyperplan normal au vecteur Li = (ai,1, . . . , ai,n) .

L’ensemble des x satisfaisant Ax ≤ bforme un polyhedre convexe P

Le vecteur c indique la direction danslaquelle on optimise: max(c · x | x ∈ P )

eventuellement vide ou non borne

Gilles Schaeffer INF-550-3: Programmation lineaire

Par convexite, un sommet est optimum siet seulement si il est meilleur que ses voisins.

optimum local ⇒ optimum global

Page 33: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

6-1

Cours 3: Programmation lineaire

• Position du probleme

• Dualite.

• Degenerescence et terminaison de l’algorithme

• Algorithme du simplexe generique

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 34: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

7-1Gilles Schaeffer INF-550-3: Programmation lineaire

L’algorithme du simplexe (cas generique)

Algorithme du simplexe, premier essai

• Initialiser x avec un sommet quelconque de P

Page 35: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

7-2Gilles Schaeffer INF-550-3: Programmation lineaire

L’algorithme du simplexe (cas generique)

Algorithme du simplexe, premier essai

• Initialiser x avec un sommet quelconque de P

• Tant qu’on a pas trouve une direction infinie ou c·x croit,et qu’il existe x′ voisin de x avec c · x′ > c · x,faire x := x′.

Page 36: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

7-3Gilles Schaeffer INF-550-3: Programmation lineaire

L’algorithme du simplexe (cas generique)

Algorithme du simplexe, premier essai

• Initialiser x avec un sommet quelconque de P

• Tant qu’on a pas trouve une direction infinie ou c·x croit,et qu’il existe x′ voisin de x avec c · x′ > c · x,faire x := x′.

Remarques: Glouton...

Page 37: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

7-4Gilles Schaeffer INF-550-3: Programmation lineaire

L’algorithme du simplexe (cas generique)

Algorithme du simplexe, premier essai

• Initialiser x avec un sommet quelconque de P

• Tant qu’on a pas trouve une direction infinie ou c·x croit,et qu’il existe x′ voisin de x avec c · x′ > c · x,faire x := x′.

Remarques: Glouton...

Qu’est ce qu’un sommet, un voisin ?

Page 38: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

7-5Gilles Schaeffer INF-550-3: Programmation lineaire

L’algorithme du simplexe (cas generique)

Algorithme du simplexe, premier essai

• Initialiser x avec un sommet quelconque de P

• Tant qu’on a pas trouve une direction infinie ou c·x croit,et qu’il existe x′ voisin de x avec c · x′ > c · x,faire x := x′.

Remarques: Glouton...

Qu’est ce qu’un sommet, un voisin ?

donne par I = {indices des n equations}Sommet = intersection de n hyperplans,

Page 39: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

7-6Gilles Schaeffer INF-550-3: Programmation lineaire

L’algorithme du simplexe (cas generique)

Algorithme du simplexe, premier essai

• Initialiser x avec un sommet quelconque de P

• Tant qu’on a pas trouve une direction infinie ou c·x croit,et qu’il existe x′ voisin de x avec c · x′ > c · x,faire x := x′.

Remarques: Glouton...

Qu’est ce qu’un sommet, un voisin ?

donne par I = {indices des n equations}Sommet = intersection de n hyperplans,

Voisin = partage n− 1 equations

Page 40: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

7-7Gilles Schaeffer INF-550-3: Programmation lineaire

L’algorithme du simplexe (cas generique)

Algorithme du simplexe, premier essai

• Initialiser x avec un sommet quelconque de P

• Tant qu’on a pas trouve une direction infinie ou c·x croit,et qu’il existe x′ voisin de x avec c · x′ > c · x,faire x := x′.

Remarques: Glouton...

Qu’est ce qu’un sommet, un voisin ?

donne par I = {indices des n equations}Sommet = intersection de n hyperplans,

Voisin = partage n− 1 equations⇒ un sommet a n(m− n) voisins ?

n = 2m = 5

Page 41: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

7-8Gilles Schaeffer INF-550-3: Programmation lineaire

L’algorithme du simplexe (cas generique)

Algorithme du simplexe, premier essai

• Initialiser x avec un sommet quelconque de P

• Tant qu’on a pas trouve une direction infinie ou c·x croit,et qu’il existe x′ voisin de x avec c · x′ > c · x,faire x := x′.

Remarques: Glouton...

Qu’est ce qu’un sommet, un voisin ?

donne par I = {indices des n equations}Sommet = intersection de n hyperplans,

Voisin = partage n− 1 equations⇒ un sommet a n(m− n) voisins ?

n = 2m = 5

On veut un voisin qui soit un sommet de P .

Page 42: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

7-9Gilles Schaeffer INF-550-3: Programmation lineaire

L’algorithme du simplexe (cas generique)

Algorithme du simplexe, premier essai

• Initialiser x avec un sommet quelconque de P

• Tant qu’on a pas trouve une direction infinie ou c·x croit,et qu’il existe x′ voisin de x avec c · x′ > c · x,faire x := x′.

Remarques: Glouton...

Qu’est ce qu’un sommet, un voisin ?

donne par I = {indices des n equations}Sommet = intersection de n hyperplans,

Voisin = partage n− 1 equations⇒ un sommet a n(m− n) voisins ?

n = 2m = 5

On veut un voisin qui soit un sommet de P .Le long d’une arete (I \ {i}), seul le premiervoisin rencontre est dans P : comparer les distances.

Page 43: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

8-1Gilles Schaeffer INF-550-3: Programmation lineaire

Detecter les directions infinies ou c · x croıt.Si le polyhedre n’est pas borne, c · x peut croıtre indefiniment:

• c s’ecrit c =P

i yiLi avec les yi ≥ 0

Lemme: les 2 cas suivants s’excluent mutuellement:

• il existe u tq c · u > 0 et Au ≤ 0

Page 44: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

8-2Gilles Schaeffer INF-550-3: Programmation lineaire

Detecter les directions infinies ou c · x croıt.Si le polyhedre n’est pas borne, c · x peut croıtre indefiniment:

• c s’ecrit c =P

i yiLi avec les yi ≥ 0

Lemme: les 2 cas suivants s’excluent mutuellement:

• il existe u tq c · u > 0 et Au ≤ 0

• c s’ecrit c =P

i yiLi avec les yi ≥ 0

Page 45: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

8-3Gilles Schaeffer INF-550-3: Programmation lineaire

Detecter les directions infinies ou c · x croıt.Si le polyhedre n’est pas borne, c · x peut croıtre indefiniment:

• c s’ecrit c =P

i yiLi avec les yi ≥ 0

Lemme: les 2 cas suivants s’excluent mutuellement:

• il existe u tq c · u > 0 et Au ≤ 0

• c s’ecrit c =P

i yiLi avec les yi ≥ 0 ⇔ l’optimum est borne

Page 46: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

8-4Gilles Schaeffer INF-550-3: Programmation lineaire

Detecter les directions infinies ou c · x croıt.Si le polyhedre n’est pas borne, c · x peut croıtre indefiniment:

• c s’ecrit c =P

i yiLi avec les yi ≥ 0

Lemme: les 2 cas suivants s’excluent mutuellement:

• il existe u tq c · u > 0 et Au ≤ 0

⇔ l’optimum est borne

• il existe u tq c · u > 0 et Au ≤ 0

Page 47: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

8-5Gilles Schaeffer INF-550-3: Programmation lineaire

Detecter les directions infinies ou c · x croıt.Si le polyhedre n’est pas borne, c · x peut croıtre indefiniment:

• c s’ecrit c =P

i yiLi avec les yi ≥ 0

Lemme: les 2 cas suivants s’excluent mutuellement:

• il existe u tq c · u > 0 et Au ≤ 0

⇔ l’optimum est borne

• il existe u tq c · u > 0 et Au ≤ 0 ⇔ ∞

Page 48: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

8-6Gilles Schaeffer INF-550-3: Programmation lineaire

Detecter les directions infinies ou c · x croıt.Si le polyhedre n’est pas borne, c · x peut croıtre indefiniment:

• c s’ecrit c =P

i yiLi avec les yi ≥ 0

Lemme: les 2 cas suivants s’excluent mutuellement:

• il existe u tq c · u > 0 et Au ≤ 0

En effet: c = yA ⇒ cu = yAu

donc si y ≥ 0 et Au ≤ 0, on a cu ≤ 0.

⇔ l’optimum est borne

• il existe u tq c · u > 0 et Au ≤ 0 ⇔ ∞

Page 49: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

8-7Gilles Schaeffer INF-550-3: Programmation lineaire

Detecter les directions infinies ou c · x croıt.Si le polyhedre n’est pas borne, c · x peut croıtre indefiniment:

• c s’ecrit c =P

i yiLi avec les yi ≥ 0

Lemme: les 2 cas suivants s’excluent mutuellement:

• il existe u tq c · u > 0 et Au ≤ 0

En effet: c = yA ⇒ cu = yAu

donc si y ≥ 0 et Au ≤ 0, on a cu ≤ 0.

Application: si au cours de l’executionon rencontre une arete de direction u tqAu ≤ 0 et cu > 0, on a trouve une directionde croissance infinie et on peut s’arreter.

⇔ l’optimum est borne

• il existe u tq c · u > 0 et Au ≤ 0 ⇔ ∞

Page 50: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

8-8Gilles Schaeffer INF-550-3: Programmation lineaire

Detecter les directions infinies ou c · x croıt.Si le polyhedre n’est pas borne, c · x peut croıtre indefiniment:

• c s’ecrit c =P

i yiLi avec les yi ≥ 0

Lemme: les 2 cas suivants s’excluent mutuellement:

• il existe u tq c · u > 0 et Au ≤ 0

En effet: c = yA ⇒ cu = yAu

donc si y ≥ 0 et Au ≤ 0, on a cu ≤ 0.

Application: si au cours de l’executionon rencontre une arete de direction u tqAu ≤ 0 et cu > 0, on a trouve une directionde croissance infinie et on peut s’arreter.Si au point xI , on a c =

Pi∈I yiLi avec yi ≥ 0,

on a trouve l’optimum.

⇔ l’optimum est borne

• il existe u tq c · u > 0 et Au ≤ 0 ⇔ ∞

Page 51: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

9-1Gilles Schaeffer INF-550-3: Programmation lineaire

Algorithme du simplexe, version generiqueSoit xI le sommet courant, solutions des n equations (Lkx = bk)k∈I

Page 52: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

9-2Gilles Schaeffer INF-550-3: Programmation lineaire

Algorithme du simplexe, version generiqueSoit xI le sommet courant, solutions des n equations (Lkx = bk)k∈I

• Exprimer c dans la base {Lk}k∈I : c =P

k∈I ykLk.

Page 53: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

9-3Gilles Schaeffer INF-550-3: Programmation lineaire

Algorithme du simplexe, version generiqueSoit xI le sommet courant, solutions des n equations (Lkx = bk)k∈I

• Exprimer c dans la base {Lk}k∈I : c =P

k∈I ykLk.

Si yk ≥ 0 pour tout k ∈ I, on a trouve l’optimum.

Page 54: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

9-4Gilles Schaeffer INF-550-3: Programmation lineaire

Algorithme du simplexe, version generiqueSoit xI le sommet courant, solutions des n equations (Lkx = bk)k∈I

• Exprimer c dans la base {Lk}k∈I : c =P

k∈I ykLk.

Si yk ≥ 0 pour tout k ∈ I, on a trouve l’optimum.

• Sinon on choisit i ∈ I tq yi < 0 et on considere l’arete definiepar les equations de I ′ = I \ {i}. Soit u son vecteur directeurtq Liu = −1 (on s’eloigne): u est une colonne de (AI)−1.

Page 55: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

9-5Gilles Schaeffer INF-550-3: Programmation lineaire

Algorithme du simplexe, version generiqueSoit xI le sommet courant, solutions des n equations (Lkx = bk)k∈I

• Exprimer c dans la base {Lk}k∈I : c =P

k∈I ykLk.

Si yk ≥ 0 pour tout k ∈ I, on a trouve l’optimum.

• Sinon on choisit i ∈ I tq yi < 0 et on considere l’arete definiepar les equations de I ′ = I \ {i}. Soit u son vecteur directeurtq Liu = −1 (on s’eloigne): u est une colonne de (AI)−1.

• Calculer la vitesse vers Lj quand on suit u: vj = Lj · u.

Page 56: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

9-6Gilles Schaeffer INF-550-3: Programmation lineaire

Algorithme du simplexe, version generiqueSoit xI le sommet courant, solutions des n equations (Lkx = bk)k∈I

• Exprimer c dans la base {Lk}k∈I : c =P

k∈I ykLk.

Si yk ≥ 0 pour tout k ∈ I, on a trouve l’optimum.

• Sinon on choisit i ∈ I tq yi < 0 et on considere l’arete definiepar les equations de I ′ = I \ {i}. Soit u son vecteur directeurtq Liu = −1 (on s’eloigne): u est une colonne de (AI)−1.

• Calculer la vitesse vers Lj quand on suit u: vj = Lj · u.

si vj ≤ 0 on s’eloigne de l’hyperplan Lj : si ∀j, max =∞.

Page 57: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

9-7Gilles Schaeffer INF-550-3: Programmation lineaire

Algorithme du simplexe, version generiqueSoit xI le sommet courant, solutions des n equations (Lkx = bk)k∈I

• Exprimer c dans la base {Lk}k∈I : c =P

k∈I ykLk.

Si yk ≥ 0 pour tout k ∈ I, on a trouve l’optimum.

• Sinon on choisit i ∈ I tq yi < 0 et on considere l’arete definiepar les equations de I ′ = I \ {i}. Soit u son vecteur directeurtq Liu = −1 (on s’eloigne): u est une colonne de (AI)−1.

• Calculer la vitesse vers Lj quand on suit u: vj = Lj · u.

si vj ≤ 0 on s’eloigne de l’hyperplan Lj : si ∀j, max =∞.

• Parmi les voisins sur l’arete, prendre celui qui est dans P .C’est celui qui est le plus proche parmi ceux du bon cote:donne par un des j tels que vj > 0 qui minimisent

bj−LjxI

vj.

Page 58: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

9-8Gilles Schaeffer INF-550-3: Programmation lineaire

Algorithme du simplexe, version generiqueSoit xI le sommet courant, solutions des n equations (Lkx = bk)k∈I

• Exprimer c dans la base {Lk}k∈I : c =P

k∈I ykLk.

Si yk ≥ 0 pour tout k ∈ I, on a trouve l’optimum.

• Sinon on choisit i ∈ I tq yi < 0 et on considere l’arete definiepar les equations de I ′ = I \ {i}. Soit u son vecteur directeurtq Liu = −1 (on s’eloigne): u est une colonne de (AI)−1.

• Calculer la vitesse vers Lj quand on suit u: vj = Lj · u.

si vj ≤ 0 on s’eloigne de l’hyperplan Lj : si ∀j, max =∞.

• Parmi les voisins sur l’arete, prendre celui qui est dans P .C’est celui qui est le plus proche parmi ceux du bon cote:donne par un des j tels que vj > 0 qui minimisent

bj−LjxI

vj.

faire I = I \ {i} ∪ {j}, recalculer xI et reprendre.

Page 59: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

10-1

Algorithme du simplexe, analyse

Gilles Schaeffer INF-550-3: Programmation lineaire

Soit xI le sommet courant, solutions des n equations (Lkx = bk)k∈I

Si on avance vers le sommet xJ , J = I \ {i} ∪ {j}, alors:

• c =P

k∈I ykLk, avec yi < 0.

Page 60: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

10-2

Algorithme du simplexe, analyse

Gilles Schaeffer INF-550-3: Programmation lineaire

Soit xI le sommet courant, solutions des n equations (Lkx = bk)k∈I

Si on avance vers le sommet xJ , J = I \ {i} ∪ {j}, alors:

Comparons l’objectif c · xI avec c · xJ :

• c =P

k∈I ykLk, avec yi < 0.

Page 61: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

10-3

Algorithme du simplexe, analyse

Gilles Schaeffer INF-550-3: Programmation lineaire

Soit xI le sommet courant, solutions des n equations (Lkx = bk)k∈I

Si on avance vers le sommet xJ , J = I \ {i} ∪ {j}, alors:

Comparons l’objectif c · xI avec c · xJ :

• c · xJ = c · xI + c · bj−LjxI

vju = c · xI +

bj−LjxI

vjc · u

or c · u =P

k∈I ykLk · u = −yi > 0 puisque u est dans leshyperplans Lk, k 6= i et Li · u = −1.

• c =P

k∈I ykLk, avec yi < 0.

Page 62: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

10-4

Algorithme du simplexe, analyse

Gilles Schaeffer INF-550-3: Programmation lineaire

Soit xI le sommet courant, solutions des n equations (Lkx = bk)k∈I

Si on avance vers le sommet xJ , J = I \ {i} ∪ {j}, alors:

Comparons l’objectif c · xI avec c · xJ :

• c · xJ = c · xI + c · bj−LjxI

vju = c · xI +

bj−LjxI

vjc · u

or c · u =P

k∈I ykLk · u = −yi > 0 puisque u est dans leshyperplans Lk, k 6= i et Li · u = −1.

⇒ comme prevu xJ ameliore l’objectif...

• c =P

k∈I ykLk, avec yi < 0.

Page 63: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

10-5

Algorithme du simplexe, analyse

Gilles Schaeffer INF-550-3: Programmation lineaire

Soit xI le sommet courant, solutions des n equations (Lkx = bk)k∈I

Si on avance vers le sommet xJ , J = I \ {i} ∪ {j}, alors:

Comparons l’objectif c · xI avec c · xJ :

• c · xJ = c · xI + c · bj−LjxI

vju = c · xI +

bj−LjxI

vjc · u

or c · u =P

k∈I ykLk · u = −yi > 0 puisque u est dans leshyperplans Lk, k 6= i et Li · u = −1.

⇒ comme prevu xJ ameliore l’objectif... sauf si bj − Ljx = 0 !

• c =P

k∈I ykLk, avec yi < 0.

Page 64: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

10-6

Algorithme du simplexe, analyse

Gilles Schaeffer INF-550-3: Programmation lineaire

Soit xI le sommet courant, solutions des n equations (Lkx = bk)k∈I

Si on avance vers le sommet xJ , J = I \ {i} ∪ {j}, alors:

Comparons l’objectif c · xI avec c · xJ :

• c · xJ = c · xI + c · bj−LjxI

vju = c · xI +

bj−LjxI

vjc · u

or c · u =P

k∈I ykLk · u = −yi > 0 puisque u est dans leshyperplans Lk, k 6= i et Li · u = −1.

⇒ comme prevu xJ ameliore l’objectif... sauf si bj − Ljx = 0 !

Si plus de n hyperplans Lk passent par xI , certaines aretes degenerentet on peut avoir xJ = xI , l’algorithme risque de boucler.

• c =P

k∈I ykLk, avec yi < 0.

Page 65: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

10-7

Algorithme du simplexe, analyse

Gilles Schaeffer INF-550-3: Programmation lineaire

Soit xI le sommet courant, solutions des n equations (Lkx = bk)k∈I

Si on avance vers le sommet xJ , J = I \ {i} ∪ {j}, alors:

Comparons l’objectif c · xI avec c · xJ :

• c · xJ = c · xI + c · bj−LjxI

vju = c · xI +

bj−LjxI

vjc · u

or c · u =P

k∈I ykLk · u = −yi > 0 puisque u est dans leshyperplans Lk, k 6= i et Li · u = −1.

⇒ comme prevu xJ ameliore l’objectif... sauf si bj − Ljx = 0 !

Si plus de n hyperplans Lk passent par xI , certaines aretes degenerentet on peut avoir xJ = xI , l’algorithme risque de boucler.

Une solution: perturber les bi pour eliminer les degenerescences.

• c =P

k∈I ykLk, avec yi < 0.

Page 66: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

11-1

Algorithme du simplexe, initialisation

Gilles Schaeffer INF-550-3: Programmation lineaire

Pour demarrer l’algorithme il faut avoir un sommet de P .

Page 67: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

11-2

Algorithme du simplexe, initialisation

Gilles Schaeffer INF-550-3: Programmation lineaire

Pour demarrer l’algorithme il faut avoir un sommet de P .

On cherche: argmax(cx | Ax ≤ b)

Page 68: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

11-3

Algorithme du simplexe, initialisation

Gilles Schaeffer INF-550-3: Programmation lineaire

Pour demarrer l’algorithme il faut avoir un sommet de P .

On cherche: argmax(cx | Ax ≤ b)

On peut toujours poser xi = yi − zi (le nombre de variables double)et maximiser (c,−c) ·

`yz

´pour (A,−A)

`yz

´≤ b et

`yz

´≥ 0.

Page 69: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

11-4

Algorithme du simplexe, initialisation

Gilles Schaeffer INF-550-3: Programmation lineaire

Pour demarrer l’algorithme il faut avoir un sommet de P .

On cherche: argmax(cx | Ax ≤ b)

On peut toujours poser xi = yi − zi (le nombre de variables double)et maximiser (c,−c) ·

`yz

´pour (A,−A)

`yz

´≤ b et

`yz

´≥ 0.

On cherche donc: argmax(cx | Ax ≤ b, x ≥ 0)

Page 70: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

11-5

Algorithme du simplexe, initialisation

Gilles Schaeffer INF-550-3: Programmation lineaire

Pour demarrer l’algorithme il faut avoir un sommet de P .

On cherche: argmax(cx | Ax ≤ b)

On peut toujours poser xi = yi − zi (le nombre de variables double)et maximiser (c,−c) ·

`yz

´pour (A,−A)

`yz

´≤ b et

`yz

´≥ 0.

On cherche donc: argmax(cx | Ax ≤ b, x ≥ 0)

Si les bi sont positifs, (0, . . . , 0) est notre sommet initial.

Page 71: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

11-6

Algorithme du simplexe, initialisation

Gilles Schaeffer INF-550-3: Programmation lineaire

Pour demarrer l’algorithme il faut avoir un sommet de P .

On cherche: argmax(cx | Ax ≤ b)

On peut toujours poser xi = yi − zi (le nombre de variables double)et maximiser (c,−c) ·

`yz

´pour (A,−A)

`yz

´≤ b et

`yz

´≥ 0.

On cherche donc: argmax(cx | Ax ≤ b, x ≥ 0)

Si les bi sont positifs, (0, . . . , 0) est notre sommet initial.

Sinon on cherche un sommet de P = {x | Ax ≤ b, x ≥ 0}

Page 72: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

11-7

Algorithme du simplexe, initialisation

Gilles Schaeffer INF-550-3: Programmation lineaire

Pour demarrer l’algorithme il faut avoir un sommet de P .

On cherche: argmax(cx | Ax ≤ b)

On peut toujours poser xi = yi − zi (le nombre de variables double)et maximiser (c,−c) ·

`yz

´pour (A,−A)

`yz

´≤ b et

`yz

´≥ 0.

On cherche donc: argmax(cx | Ax ≤ b, x ≥ 0)

Si les bi sont positifs, (0, . . . , 0) est notre sommet initial.

Sinon on cherche un sommet de P = {x | Ax ≤ b, x ≥ 0}On fait cela en cherchant parmi les (x1, . . . , xn, t) tq

ai,1x1 + . . . + ai,nxn − t ≤ bi pour tout i,un point qui minimise t.

Page 73: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

11-8

Algorithme du simplexe, initialisation

Gilles Schaeffer INF-550-3: Programmation lineaire

Pour demarrer l’algorithme il faut avoir un sommet de P .

On cherche: argmax(cx | Ax ≤ b)

On peut toujours poser xi = yi − zi (le nombre de variables double)et maximiser (c,−c) ·

`yz

´pour (A,−A)

`yz

´≤ b et

`yz

´≥ 0.

On cherche donc: argmax(cx | Ax ≤ b, x ≥ 0)

Si les bi sont positifs, (0, . . . , 0) est notre sommet initial.

Sinon on cherche un sommet de P = {x | Ax ≤ b, x ≥ 0}On fait cela en cherchant parmi les (x1, . . . , xn, t) tq

ai,1x1 + . . . + ai,nxn − t ≤ bi pour tout i,un point qui minimise t.On connait un sommet initial (0, . . . , 0, T ) pour ce probleme lineaire.

Page 74: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

11-9

Algorithme du simplexe, initialisation

Gilles Schaeffer INF-550-3: Programmation lineaire

Pour demarrer l’algorithme il faut avoir un sommet de P .

On cherche: argmax(cx | Ax ≤ b)

On peut toujours poser xi = yi − zi (le nombre de variables double)et maximiser (c,−c) ·

`yz

´pour (A,−A)

`yz

´≤ b et

`yz

´≥ 0.

On cherche donc: argmax(cx | Ax ≤ b, x ≥ 0)

Si les bi sont positifs, (0, . . . , 0) est notre sommet initial.

Sinon on cherche un sommet de P = {x | Ax ≤ b, x ≥ 0}On fait cela en cherchant parmi les (x1, . . . , xn, t) tq

ai,1x1 + . . . + ai,nxn − t ≤ bi pour tout i,un point qui minimise t.On connait un sommet initial (0, . . . , 0, T ) pour ce probleme lineaire.Il existe (et on obtient) un sommet de P ssi t = 0 dans sa solution.

Page 75: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

12-1

Cours 3: Programmation lineaire

• Position du probleme

• Dualite.

• Degenerescence et terminaison de l’algorithme

• Algorithme du simplexe generique

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 76: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

13-1

Primal/dual et theoreme de dualite

Gilles Schaeffer INF-550-3: Programmation lineaire

Theoreme (cas inegalites+positivite). Si l’un des 2 problemes suivant

(P) max(cx | Ax ≤ b, x ≥ 0)

(D) min(yb | yA ≥ c, y ≥ 0)

admet une solution finie, alors l’autre aussi et on a

min(yb | yA ≥ c, y ≥ 0) = max(cx | Ax ≤ b, x ≥ 0)

Page 77: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

13-2

Primal/dual et theoreme de dualite

Gilles Schaeffer INF-550-3: Programmation lineaire

Theoreme (cas inegalites+positivite). Si l’un des 2 problemes suivant

(P) max(cx | Ax ≤ b, x ≥ 0)

(D) min(yb | yA ≥ c, y ≥ 0)

admet une solution finie, alors l’autre aussi et on a

min(yb | yA ≥ c, y ≥ 0) = max(cx | Ax ≤ b, x ≥ 0)

Interpretation. Retour au fleuriste.Primal

max(4x + 5x′)10x + 10x′ ≤ 5010x + 20x′ ≤ 8020x + 10x′ ≤ 80x ≥ 0, x′ ≥ 0

Page 78: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

13-3

Primal/dual et theoreme de dualite

Gilles Schaeffer INF-550-3: Programmation lineaire

Theoreme (cas inegalites+positivite). Si l’un des 2 problemes suivant

(P) max(cx | Ax ≤ b, x ≥ 0)

(D) min(yb | yA ≥ c, y ≥ 0)

admet une solution finie, alors l’autre aussi et on a

min(yb | yA ≥ c, y ≥ 0) = max(cx | Ax ≤ b, x ≥ 0)

Interpretation. Retour au fleuriste.Primal

max(4x + 5x′)10x + 10x′ ≤ 5010x + 20x′ ≤ 8020x + 10x′ ≤ 80x ≥ 0, x′ ≥ 0

×y1

y2

y3

Page 79: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

13-4

Primal/dual et theoreme de dualite

Gilles Schaeffer INF-550-3: Programmation lineaire

Theoreme (cas inegalites+positivite). Si l’un des 2 problemes suivant

(P) max(cx | Ax ≤ b, x ≥ 0)

(D) min(yb | yA ≥ c, y ≥ 0)

admet une solution finie, alors l’autre aussi et on a

min(yb | yA ≥ c, y ≥ 0) = max(cx | Ax ≤ b, x ≥ 0)

Interpretation. Retour au fleuriste.Primal

max(4x + 5x′)10x + 10x′ ≤ 5010x + 20x′ ≤ 8020x + 10x′ ≤ 80x ≥ 0, x′ ≥ 0

⇒ (10y1 + 10y2 + 20y3)x + (10y1 + 20y2 + 10y3)x′ ≤ 50y1 + 80y2 + 80y3

×y1

y2

y3 y1 ≥ 0, y2 ≥ 0, y3 ≥ 0.

Page 80: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

13-5

Primal/dual et theoreme de dualite

Gilles Schaeffer INF-550-3: Programmation lineaire

Theoreme (cas inegalites+positivite). Si l’un des 2 problemes suivant

(P) max(cx | Ax ≤ b, x ≥ 0)

(D) min(yb | yA ≥ c, y ≥ 0)

admet une solution finie, alors l’autre aussi et on a

min(yb | yA ≥ c, y ≥ 0) = max(cx | Ax ≤ b, x ≥ 0)

Interpretation. Retour au fleuriste.Primal

max(4x + 5x′)10x + 10x′ ≤ 5010x + 20x′ ≤ 8020x + 10x′ ≤ 80x ≥ 0, x′ ≥ 0

⇒ (10y1 + 10y2 + 20y3)x + (10y1 + 20y2 + 10y3)x′ ≤ 50y1 + 80y2 + 80y3

×y1

y2

y3

4x + 5x′ ≤

10y1 + 10y2 + 20y3 ≥ 410y1 + 20y2 + 10y3 ≥ 5y1 ≥ 0, y2 ≥ 0, y3 ≥ 0.

Page 81: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

13-6

Primal/dual et theoreme de dualite

Gilles Schaeffer INF-550-3: Programmation lineaire

Theoreme (cas inegalites+positivite). Si l’un des 2 problemes suivant

(P) max(cx | Ax ≤ b, x ≥ 0)

(D) min(yb | yA ≥ c, y ≥ 0)

admet une solution finie, alors l’autre aussi et on a

min(yb | yA ≥ c, y ≥ 0) = max(cx | Ax ≤ b, x ≥ 0)

Interpretation. Retour au fleuriste.Primal

max(4x + 5x′)10x + 10x′ ≤ 5010x + 20x′ ≤ 8020x + 10x′ ≤ 80x ≥ 0, x′ ≥ 0

⇒ (10y1 + 10y2 + 20y3)x + (10y1 + 20y2 + 10y3)x′ ≤ 50y1 + 80y2 + 80y3

×y1

y2

y3

4x + 5x′ ≤

min(50y1 +80y2 +80y3)10y1 + 10y2 + 20y3 ≥ 410y1 + 20y2 + 10y3 ≥ 5y1 ≥ 0, y2 ≥ 0, y3 ≥ 0.

Page 82: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

13-7

Primal/dual et theoreme de dualite

Gilles Schaeffer INF-550-3: Programmation lineaire

Theoreme (cas inegalites+positivite). Si l’un des 2 problemes suivant

(P) max(cx | Ax ≤ b, x ≥ 0)

(D) min(yb | yA ≥ c, y ≥ 0)

admet une solution finie, alors l’autre aussi et on a

min(yb | yA ≥ c, y ≥ 0) = max(cx | Ax ≤ b, x ≥ 0)

Interpretation. Retour au fleuriste.Primal

max(4x + 5x′)10x + 10x′ ≤ 5010x + 20x′ ≤ 8020x + 10x′ ≤ 80x ≥ 0, x′ ≥ 0

⇒ (10y1 + 10y2 + 20y3)x + (10y1 + 20y2 + 10y3)x′ ≤ 50y1 + 80y2 + 80y3

×y1

y2

y3

Dual

4x + 5x′ ≤

min(50y1 +80y2 +80y3)10y1 + 10y2 + 20y3 ≥ 410y1 + 20y2 + 10y3 ≥ 5y1 ≥ 0, y2 ≥ 0, y3 ≥ 0.

Page 83: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

13-8

Primal/dual et theoreme de dualite

Gilles Schaeffer INF-550-3: Programmation lineaire

Theoreme (cas inegalites+positivite). Si l’un des 2 problemes suivant

(P) max(cx | Ax ≤ b, x ≥ 0)

(D) min(yb | yA ≥ c, y ≥ 0)

admet une solution finie, alors l’autre aussi et on a

min(yb | yA ≥ c, y ≥ 0) = max(cx | Ax ≤ b, x ≥ 0)

Interpretation. Retour au fleuriste.Primal

max(4x + 5x′)10x + 10x′ ≤ 5010x + 20x′ ≤ 8020x + 10x′ ≤ 80x ≥ 0, x′ ≥ 0

⇒ (10y1 + 10y2 + 20y3)x + (10y1 + 20y2 + 10y3)x′ ≤ 50y1 + 80y2 + 80y3

×y1

y2

y3

Dual

4x + 5x′ ≤

Le theoreme ditqu’on peut obtenirune borne optimalepar multiplicateur.

min(50y1 +80y2 +80y3)10y1 + 10y2 + 20y3 ≥ 410y1 + 20y2 + 10y3 ≥ 5y1 ≥ 0, y2 ≥ 0, y3 ≥ 0.

Page 84: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

13-9

Primal/dual et theoreme de dualite

Gilles Schaeffer INF-550-3: Programmation lineaire

Theoreme (cas inegalites+positivite). Si l’un des 2 problemes suivant

(P) max(cx | Ax ≤ b, x ≥ 0)

(D) min(yb | yA ≥ c, y ≥ 0)

admet une solution finie, alors l’autre aussi et on a

min(yb | yA ≥ c, y ≥ 0) = max(cx | Ax ≤ b, x ≥ 0)

Interpretation. Retour au fleuriste.Primal

max(4x + 5x′)10x + 10x′ ≤ 5010x + 20x′ ≤ 8020x + 10x′ ≤ 80x ≥ 0, x′ ≥ 0

⇒ (10y1 + 10y2 + 20y3)x + (10y1 + 20y2 + 10y3)x′ ≤ 50y1 + 80y2 + 80y3

×y1

y2

y3

Dual

4x + 5x′ ≤

Le theoreme ditqu’on peut obtenirune borne optimalepar multiplicateur.

Si on augmente ladenree i de ∆i, le gainaugmente de ∆iyi.

min(50y1 +80y2 +80y3)10y1 + 10y2 + 20y3 ≥ 410y1 + 20y2 + 10y3 ≥ 5y1 ≥ 0, y2 ≥ 0, y3 ≥ 0.

Page 85: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

14-1

Primal/dual et theoreme de dualite

Primal / Dual, cas general. Le theoreme s’applique aux paires:

Primalmax(c1x1 + . . . + cnxn)

ai1x1 + . . . ainxn ≤ bi pour i ∈ Iai1x1 + . . . ainxn = bi pour i ∈ E

xj ≥ 0 pour j ∈ P .

Dualmin(b1y1 + . . . + bmym)

a1jy1 + . . . amjym ≥ cj pour j ∈ Pa1jy1 + . . . amjym = cj pour j ∈ N

yi ≥ 0 pour i ∈ I.

ou m = |I|+ |E| et n = |P |+ |N |

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 86: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

14-2

Primal/dual et theoreme de dualite

Primal / Dual, cas general. Le theoreme s’applique aux paires:

Primalmax(c1x1 + . . . + cnxn)

ai1x1 + . . . ainxn ≤ bi pour i ∈ Iai1x1 + . . . ainxn = bi pour i ∈ E

xj ≥ 0 pour j ∈ P .

Dualmin(b1y1 + . . . + bmym)

a1jy1 + . . . amjym ≥ cj pour j ∈ Pa1jy1 + . . . amjym = cj pour j ∈ N

yi ≥ 0 pour i ∈ I.

ou m = |I|+ |E| et n = |P |+ |N |

Les inegalite donnent dans le dual des variables contraintes a etre positives,les egalites des variables quelconques (penser a l’interpretation des variablesduales comme multiplicateurs).

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 87: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

14-3

Primal/dual et theoreme de dualite

Primal / Dual, cas general. Le theoreme s’applique aux paires:

Primalmax(c1x1 + . . . + cnxn)

ai1x1 + . . . ainxn ≤ bi pour i ∈ Iai1x1 + . . . ainxn = bi pour i ∈ E

xj ≥ 0 pour j ∈ P .

Dualmin(b1y1 + . . . + bmym)

a1jy1 + . . . amjym ≥ cj pour j ∈ Pa1jy1 + . . . amjym = cj pour j ∈ N

yi ≥ 0 pour i ∈ I.

ou m = |I|+ |E| et n = |P |+ |N |

Les inegalite donnent dans le dual des variables contraintes a etre positives,les egalites des variables quelconques (penser a l’interpretation des variablesduales comme multiplicateurs).

En TD: le theoreme de dualite ⇒ maxflow = mincut

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 88: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

15-1

Cours 3: Programmation lineaire

• Position du probleme

• Dualite.

• Degenerescence et terminaison de l’algorithme

• Algorithme du simplexe generique

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 89: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

16-1

Degenerescence et risque de bouclage

Degenerescence: un sommet appartient a plus de n hyperplans.

Il n’est pas forcement acceptable de perturber.

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 90: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

16-2

Degenerescence et risque de bouclage

Degenerescence: un sommet appartient a plus de n hyperplans.

Il n’est pas forcement acceptable de perturber.

Parmi les voisins de x{2,3} il y ax{1,3}, x{1,4}, x{1,2}, x{2,4}.

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 91: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

16-3

Degenerescence et risque de bouclage

Degenerescence: un sommet appartient a plus de n hyperplans.

Il n’est pas forcement acceptable de perturber.

Parmi les voisins de x{2,3} il y ax{1,3}, x{1,4}, x{1,2}, x{2,4}.

Ce sont meme ses plus proches voisins...

1

2

3

4

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 92: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

16-4

Degenerescence et risque de bouclage

Degenerescence: un sommet appartient a plus de n hyperplans.

Il n’est pas forcement acceptable de perturber.

Parmi les voisins de x{2,3} il y ax{1,3}, x{1,4}, x{1,2}, x{2,4}.

Ce sont meme ses plus proches voisins...

1

2

3

4

En dimension superieure il peut etre necessairede changer plusieurs lignes pour trouver un vrai voisin dans P .

Il peut y avoir un nombre exponentiel de faux voisins.

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 93: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

16-5

Degenerescence et risque de bouclage

Degenerescence: un sommet appartient a plus de n hyperplans.

Il n’est pas forcement acceptable de perturber.

Parmi les voisins de x{2,3} il y ax{1,3}, x{1,4}, x{1,2}, x{2,4}.

Ce sont meme ses plus proches voisins...

1

2

3

4

En dimension superieure il peut etre necessairede changer plusieurs lignes pour trouver un vrai voisin dans P .

Il peut y avoir un nombre exponentiel de faux voisins.

Notre algorithme du simplexe prend un voisin le plus proche: il faut bien lechoisir pour ne pas risquer de boucler indefiniment en changeant I sanschanger xI : x{2,3} → x{1,3} → x{1,2} → x{2,3}.

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 94: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

17-1Gilles Schaeffer INF-550-3: Programmation lineaire

Algorithme du simplexe, version finaleSoit xI le sommet courant, solutions des n equations (Lkx = bk)k∈I

• Exprimer c dans la base {Lk}k∈I : c =P

k∈I ykLk.

Si yk ≥ 0 pour tout k ∈ I, on a trouve l’optimum.

• Sinon on choisit le plus petit i ∈ I tq yi < 0 et on considerel’arete definie par les equations de I ′ = I \ {i}. Soit u sonvecteur directeur tq Liu = −1 (c’est une colonne de (AI)−1).

• Calculer la vitesse vers Lj quand on suit u: vj = Lj · u.

si vj ≤ 0 on s’eloigne de l’hyperplan Lj : si ∀j, max =∞.

• Parmi les voisins sur l’arete, prendre celui qui est dans P ,c’est celui qui est le plus proche parmi ceux du bon cote:le plus petit parmi les j tels que vj > 0 qui minimisent

bj−LjxI

vj.

faire I = I \ {i} ∪ {j}, recalculer xI et reprendre.

Page 95: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

18-1

Algorithme du simplexe, preuve de terminaisonSi l’algo boucle c’est qu’on est revenu au meme I, sans changer c · xI

(c · xI croıt). On observe l’evolution des indices presents dans I.

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 96: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

18-2

Algorithme du simplexe, preuve de terminaisonSi l’algo boucle c’est qu’on est revenu au meme I, sans changer c · xI

(c · xI croıt). On observe l’evolution des indices presents dans I.

I I

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 97: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

18-3

Algorithme du simplexe, preuve de terminaisonSi l’algo boucle c’est qu’on est revenu au meme I, sans changer c · xI

(c · xI croıt). On observe l’evolution des indices presents dans I.

I I′ I′′ I

Soit r le plus grand indice qui sort ou entre durant la boucle, et soientI′ et I′′ les ensembles d’indices a des temps de sortie et d’entree de r.

inchange

r

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 98: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

18-4

Algorithme du simplexe, preuve de terminaisonSi l’algo boucle c’est qu’on est revenu au meme I, sans changer c · xI

(c · xI croıt). On observe l’evolution des indices presents dans I.

I I′ I′′ I

Soit r le plus grand indice qui sort ou entre durant la boucle, et soientI′ et I′′ les ensembles d’indices a des temps de sortie et d’entree de r.

inchange

r

Gilles Schaeffer INF-550-3: Programmation lineaire

Comme r sort de I′: c =P

i∈I′ yiLi, avec yi ≥ 0 pour i < r, et yr < 0.

Page 99: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

18-5

Algorithme du simplexe, preuve de terminaisonSi l’algo boucle c’est qu’on est revenu au meme I, sans changer c · xI

(c · xI croıt). On observe l’evolution des indices presents dans I.

I I′ I′′ I

Soit r le plus grand indice qui sort ou entre durant la boucle, et soientI′ et I′′ les ensembles d’indices a des temps de sortie et d’entree de r.

inchange

r

Gilles Schaeffer INF-550-3: Programmation lineaire

Comme r sort de I′: c =P

i∈I′ yiLi, avec yi ≥ 0 pour i < r, et yr < 0.

alors Liu = 0 pour i ∈ I′′ \ {r} et, comme r entre dans I′′, on a Lju ≤ 0pour tout j < r avec bj − Lju = 0. C’est le cas pour tout j ∈ I′ \ I′′.

Soit u la direction de l’arete selectionnee lors du traitement de I′′:

Page 100: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

18-6

Algorithme du simplexe, preuve de terminaisonSi l’algo boucle c’est qu’on est revenu au meme I, sans changer c · xI

(c · xI croıt). On observe l’evolution des indices presents dans I.

I I′ I′′ I

Soit r le plus grand indice qui sort ou entre durant la boucle, et soientI′ et I′′ les ensembles d’indices a des temps de sortie et d’entree de r.

inchange

r

Gilles Schaeffer INF-550-3: Programmation lineaire

Comme r sort de I′: c =P

i∈I′ yiLi, avec yi ≥ 0 pour i < r, et yr < 0.

alors Liu = 0 pour i ∈ I′′ \ {r} et, comme r entre dans I′′, on a Lju ≤ 0pour tout j < r avec bj − Lju = 0. C’est le cas pour tout j ∈ I′ \ I′′.

D’ou cu =P

i∈I′ yiLiu =P

i<r, i∈I′ yiLiu + yrLru < 0.

Soit u la direction de l’arete selectionnee lors du traitement de I′′:

Page 101: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

18-7

Algorithme du simplexe, preuve de terminaisonSi l’algo boucle c’est qu’on est revenu au meme I, sans changer c · xI

(c · xI croıt). On observe l’evolution des indices presents dans I.

I I′ I′′ I

Soit r le plus grand indice qui sort ou entre durant la boucle, et soientI′ et I′′ les ensembles d’indices a des temps de sortie et d’entree de r.

inchange

r

Gilles Schaeffer INF-550-3: Programmation lineaire

Comme r sort de I′: c =P

i∈I′ yiLi, avec yi ≥ 0 pour i < r, et yr < 0.

alors Liu = 0 pour i ∈ I′′ \ {r} et, comme r entre dans I′′, on a Lju ≤ 0pour tout j < r avec bj − Lju = 0. C’est le cas pour tout j ∈ I′ \ I′′.

D’ou cu =P

i∈I′ yiLiu =P

i<r, i∈I′ yiLiu + yrLru < 0.

Ceci contredit le choix de u pour ameliorer l’objectif: (cu > 0).

Soit u la direction de l’arete selectionnee lors du traitement de I′′:

Page 102: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

19-1

Algorithme du simplexe, complexite

Gilles Schaeffer INF-550-3: Programmation lineaire

Puisque le nombre de voisins d’un sommet est n(m − 1) au plus,chaque etape a un cout polynomial.

Le nombre de sommets peut etre exponentiel (jusqu’a`

mn

´) en m et n,

et il existe des exemples pour lesquels le simplexe visite effectivementun nombre exponentiel de sommets... (Worst case analysis).

On constate que cela ne se produit quasiment jamais en pratique...

On peut montrer qu’en moyenne sur des problemes aleatoiresl’algorithme est polynomial (Average case analysis).

Mieux on peut montrer que si on perturbe aleatoirement des donneesarbitraires, l’algorithme reste polynomial (Smooth analysis).

Page 103: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

20-1

Programmation lineaire, algorithmes polynomiaux.

Le simplexe n’est pas polynomial mais presque...

De fait il existe des algorithmes polynomiaux pour la programmationlineaire: notamment les methodes de l’ellipsoide et du point interieur.

Attention toutefois: il y a des algorithmes polynomiaux si on chercheles optimaux a coordonnees dans R.

On verra que, contrairement a ce qui se passe pour les problemes deflots, le probleme devient dur si on veut des solutions entieres.

Gilles Schaeffer INF-550-3: Programmation lineaire

Page 104: Cours 3: Programmation lin eaire · 1-1 Cours 3: Programmation lin eaire Position du probl eme Dualit e. D eg en erescence et terminaison de l’algorithme Algorithme du simplexe

21-1

Cours 3: Programmation lineaire

• Position du probleme

• Dualite.

• Degenerescence et terminaison de l’algorithme

• Algorithme du simplexe generique

Gilles Schaeffer INF-550-3: Programmation lineaire

Retenir: - Il existe d’excellentes boites noires pour resoudre les LP.

- Modelisation par LP (en PC). Thm Primal-Dual.