Deux problèmes avec la méthode du simplexe
Trouver une solution de base pour commencer
Un petit exemple
et le problème avec ces contraintes et la fonction objective z = -y a la solution réalisable de base x1=x2=0, x1-3x2 = -5+y
Une solution optimale est x1=1, x2=2,y=0, x1-3x2 = -5+y, -5x1+x2 = -3+y
Donc x1=1, x2=2,, x1-3x2 = -5,
5x1+x2 = -3 est une solution réalisable de base
du vrai problème.
Et les équations vérifiées à cette solution du vrai problème se trouve en supprimant le y = 0 dans les équations de la solution optimale du problème auxiliaire!
Amélioration nulle
Mais il existe au moins un bon ensemble d'équations qui permet à l'algorithme de continuer (vraie amélioration de z s'il y en a). Donc deux possibilités,
Pourquoi ne pas jeter les contraintes inutiles?
Trop difficile de les trouver!
Le dual d'un programme linéaire
Motivation
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
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)
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;
donc, forcément la solution optimale des deux.
L'interprétation économique de la solution du dual
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 ...)
Les méthodes plus récentes