Deux Problèmes avec l'algorithme du simplexe:
(1) Amélioration nulle

Comment? Si le nombre d'équations des contraintes vérifiées à une solution est supérieure à n.
Une itération jette une contrainte et en ajoute une autre; ça peut donner la même solution.
Et l'algorithme pourrait boucler (même point; ensembles différents d'équations).

Pourquoi ne pas jeter les contraintes inutiles?
Trop difficile de les trouver!

Un programme robuste doit être capable de traiter ce cas.

Et une règle simple suffit: à chaque choix (colonne ou ligne du pivot), choisir la première variable possible pour sortir ou entrer.

(2) Nombre d'itérations très grand

Le nombre d'itérations peut être exponentiel (par rapport au nombre de variables et contraintes) dans certains cas qui sont très rares en pratique;

Une conséquence inéluctable de la méthode de parcours des arêtes du polytope;

Pendant plusieurs années il était inconnu s'il existait un algorithme en temps polynomial dans tous les cas;

Un premier algorithme polynomial (Khachyan: la méthode des ellipsoides) a été découvert en 1979;

Début d'un nombre de méthodes de ``points intérieurs'' qui à chaque itération avance un peu dans la bonne direction en évitant de s'approcher trop des contraintes;

Comment une méthode qui n'arrive jamais à une contrainte peut-elle nous donner une solution exacte??

Maintenant les meilleures de ces nouvelles méthodes concurrencent le simplexe, même en temps moyen.

Le dual d'un programme linéaire
Motivation

Une solution réalisable d'un programme (de maximisation) donne un z possible, donc un minorant du z optimal.

Je peux aussi déduire des majorants de z par manipulation directe des inéquations:

10
10
20
50
0
40
25
  x  < =  
100
50
60
40
0
0
0
15

100
30
50
40
5
5
20
10

100
0
0
0
0
50
30
0

100

Si je calcule 2/5× (1) + 2/3× (2), j'obtiens
37.33x1+44x2+34.67x3+20x4+16x6+20x7
< = 106.67
Donc z=30x1+40x2+30x3+10x4+15x6+20x7 < = 106.67

Quel est le meilleur majorant que je peux trouver de cette façon?

Le problème de base: maximiser j=1n cjxj
avec m contraintes j=1n ai,jxj < = bi
et xj > = 0

En essayant de trouver un majorant de la solution, j'ai cherché des multiplicateurs yi pour les contraintes avec les propriétés:
yi > = 0
i=1m ai,jyi > = cj
Et je veux trouver un ensemble de tels multiplicateurs qui me donne la valeur la plus petite possible de i=1m bi yi.

Un nouveau programme linéaire!
appelé le dual.

Propriété évidente: chaque solution réalisable du dual est supérieure ou égale à chaque solution réalisable du problème de base.

Le dual du dual

Le dual, à savoir minimiser i=1m bi yi avec les contraintes i=1m ai,jyi > = cj équivaut à maximiser i=1m -bi yi avec les contraintes i=1m -ai,jyi < = -cj.
(pour l'exprimer en forme canonique)

On a multiplié les deux vecteurs b et c et la matrice a par -1, échangé les 2 vecteurs et transposé la matrice.

Donc, si on le fait une deuxième fois pour obtenir le dual du dual, on trouve le problème de base.

Les deux problèmes ont la même solution!
(c'est-à-dire la même valeur optimale de la fonction objective)

Le théorème le plus important de la programmation linéaire.

Démonstration compliquée.

Mais, il n'est pas difficile de voir que l'algorithme du simplexe calcule (dans le cas d'un programme faisable et borné) une valeur qui est une solution réalisable des deux problèmes;
En effet, à la fin de l'exécution de l'algorithme, la dernière ligne contient sa valeur initiale (la fonction objective) moins une somme de multiples des autres lignes; mettons mj pour le multiple de la ligne j.
En regardant les valeurs finales dans cette dernière ligne, on trouve

C'est-á-dire que les mj constituent une solution réalisable du programme dual et avec la même valeur de sa fonction objective que la solution trouvée du programme de départ.
donc, forcément la solution optimale des deux.

L'interprétation économique de la solution du dual

La solution du problème dual (c'est-à-dire les yi) nous dit par combien la solution optimale ( z) va changer si la contrainte (numéro i) est modifiée.
(parce que la valeur trouvée pour z est i biyi)

Si z est mon profit, yi est le maximum que je devrait payer (par unité) pour lâcher la contrainte (acheter plus d'une matière de base ...)




File translated from TEX by TTH, version 3.05.
On 21 Nov 2005, 14:51.

symboles bricolés pour netscape par sed