Deux problèmes avec la méthode du simplexe
- Comment commencer?
Il faut commencer à une solution de base réalisable;
(ou trouver qu'il n'y en a pas)
mais la réussite de la méthode dépend du fait qu'on peut
éviter de regarder toutes les solutions de bases potentielles.
- Terminaison prématurée ou boucle infinie
Dans un cas la méthode ``supprimer une équation et en ajouter
une nouvelle'' ne trouve aucune solution meilleur quand on n'est
pas à la solution optimale.
Trouver une solution de base pour commencer
- Modifier le problème de sorte que le nouveau problème aie une solution
de base triviale et une solution optimale du nouveau
problème soit forcément une solution
réalisable (de base) de l'ancien;
- Résoudre ce nouveau problème par
l'algorithme du simplexe!
- Enfin commencer a résoudre le vrai problème
- Pour construire le nouveau problème:
- Ajouter une nouvelle variable, disons y (avec y ³ 0)
- Remplacer toute contrainte lin £ const par lin-y £ const
(et transformer dans la forme canonique)
- Il existe une solution réalisable de base avec n+1
équations vérifiées
- Minimiser y (maximiser -y); si le résultat est nul, on a trouvé une solution
réalisable de base
de l'ancien problème; sinon il n'y en a pas.
Un petit exemple
Les contraintes: x1+x2 £ 10,x1-3x2 £ -5, -5x1+x2 £ -3
deviennent
x1+x2 £ 10+y, x1-3x2 £ -5+y,-5x1+x2 £ -3+y
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
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).
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,
- choisir les équations à supprimer et à rajouter comme normale avec
un choix aléatoire quand plus d'un candidat
peut marcher de façon acceptable quand il existe une meilleur
solution mais risque de ne peut pas trouver qu'il n'y en a pas.
- ajouter (virtuellement) une petite quantité ei
à la constante bi de la contrainte i;
Agir comme si 1 >> e1 >> e2 >> e3¼;
Impossibilité d'avoir plus de n équations vérifiées!!
Et on résout un programme indistinguable de l'initial!
Pourquoi ne pas jeter les contraintes inutiles?
Trop difficile de les trouver!
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;
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 ...)
Les méthodes plus récentes
Depuis une vingtaine d'années de nouveaux algorithmes existent
avec des différences importantes par rapport à celui du simplexe:
- parcourir un chemin de solutions strictement à l'intérieur
du polytope
de solutions réalisables
- garantie de converger sur la solution optimale en temps
raisonnable
(borné par un poynôme)
- un peu moins vite en moyenne en pratique
- choisir une bonne direction (améliorer la fonction
objective sans s'approcher trop des contraintes) et avancer
tout en restant strictement à l'intérieur
Novembre 2002
Un prof aux E.U. annonce un algorithme
fortement polynomial (nombre d'opérations arithmétiques
borné par un polynôme indépendant du nombre de chiffres
dans les coefficients).
Est-il vrai? L'algorithme reste secret pour le moment.
File translated from
TEX
by
TTH,
version 3.05.
On 13 Nov 2002, 16:23.