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.
Cas dégénérés possibles
On a vu que si l'un des deux programmes a une solution optimale, c'est
vrai aussi pour l'autre.
Il reste trois cas possibles ou ni l'un ni l'autre n'a pas de solution
optimale:
- les deux programmes sont infaisables
- le primal est infaisable et le dual a des solutions sans borne
- le primal a des solutions sans borne et le dual est infaisable
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 ...)
Un autre algorithme
Celui de Khachiyan (1979) a l'avantage d'être certain de terminer dans
un temps
polynomial (dans la taille des entrées ... ) dans tous les cas.
- Il suffit de pouvoir décider si un programme est faisable ou non
(recherche dichotomique peut ensuite donner le résultat exact dans un nombre
polynomial d'itérations)
- Toutes les solutions de base (et donc une solution réalisable
s'il y en a, même si l'espace de solutions est infini) sont à l'intérieur
d'une (hyper-)sphère de taille calculable (et pas trop grande)
- Considérer le point au centre de cette sphère
- S'il est une solution réalisable, le programme est faisable.
- Sinon, toute solution réalisable de base est à l'intérieur d'une
hémisphère bornée par la moitié de la sphère et un plan parallel à la contrainte
violée
- Trouver la plus petite ellisoïde qui contient cette hémisphère;
- Et appliquer une transformation linéaire qui transforme cette ellisoïde
en une sphère !
Algorithme plutôt d'intérêt théorique mais qui a produit beaucoup
de recherches pour d'autres nouvelles méthodes dont quelques unes
qui conservent l'avantage théorique de celle de Khachiyan
mais sont compétitifs avec le simplexe (méthodes des points
intérieurs).
File translated from
TEX
by
TTH,
version 3.05.
On 30 Oct 2006, 15:42.