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:
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
- (colonne de la j-ième
variable d'écart) -mj;
donc
on a mj > = 0 par la
condition d'arrêt de l'algorithme,
- (colonne de la j-ième
variable du programme de départ)
cj-∑ai,jmj; donc ∑ai,jmj
> = cj (par la même
condition)
- (colonne des constantes) ∑-cjmj;
donc la solution trouvée
pour le programme de départ était ∑cjmj.
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