Module D108 : Programmation mathématique et optimisation
Programmation Linéaire
Le programme dual d'un programme linéaire
La relation entre les solutions des deux programmes
L'algorithme du simplexe trouve les deux solutions !
Interprétation économique de la solution du dual
Exercices
Auteur(s) : Mike Robson - IUP Miage Bordeaux
Date de dernière modification : 30 Janvier 2006
A un programme linéaire exprimé dans la forme
on associe son programme dual qui est
ici est la transposée de la matrice . Par exemple le dual du programme: (des exercices de la
section 3)
serait:
On peut transformer le dual dans la forme familière d'une maximisation sous contraintes de la
forme par deux multiplications par :
Pour notre exemple cette transformation donne:
On voit clairement qu'effectuer cette transformation deux fois revient au programme de départ: la
relation de dualité est une relation réciproque.
La relation entre les solutions des deux programmes
On retrouve le programme dual en cherchant à démontrer algébriquement un majorant sur les
solutions réalisables du programme initial. Par exemple dans notre programme exemple nous pouvons
facilement démontrer le majorant grossier de sur la fonction objective en choisissant des
multiplicateurs pour les lignes, ce qui donne les nouvelles
inéquations:
et ensuite ajoutant ces inéquations: d'où on déduit
que puisque les ne peuvent pas être négatifs; c'est-à-dire que est un
majorant sur la fonction objective.
Si on pose la question pour quels multiplicateurs ce processus est valable, on voit qu'on doit
forcément avoir que:
; si on multiplie une inéquation par une valeur négative, elle ne reste pas vraie;
; par exemple dans notre exemple on a utilisé le fait
que .
C'est-à-dire que les constituent une solution réalisable du dual. Qui plus est, le majorant calculé
par ce processus est exactement , la fonction objective du dual (dans sa première forme avant
les multiplications par ). Donc les majorants qu'on peut démontrer de cette façon sont exactement
les valeurs de la fonction objective des solutions réalisables du dual et, en particulier, la solution
optimale du dual donne le meilleur majorant qu'on puisse obtenir de cette façon.
Reste la question: existe-t-il de meilleurs majorants qu'on ne peut pas démontrer de cette façon
simple? La réponse est que non mais, au lieu de la démontrer ici, nous allons la traiter dans la section
suivante.
Si on avait commencé avec un programme qui n'avait pas de solution optimale finie (donc,
programme non faisable ou sans majorant sur la fonction objective), le dual aurait aussi eu ce
caractère. Il n'est pas possible que les deux soient sans majorant mais les trois autres cas (infaisable-
infaisable, infaisable-sans majorant ou sans majorant-infaisable) sont possibles.
L'algorithme du simplexe trouve les deux solutions !
Dans notre programme exemple, le simplexe donne le tableau final:
1.00 0.00 0.37 0.00 -0.02 -0.11 -0.15 0.53
0.00 1.00 -0.80 0.00 -0.20 0.10 0.00 0.10
0.00 0.00 -0.39 1.00 -0.06 -0.09 0.05 0.35
0.00 0.00 35.10 0.00 -5.40 -1.05 -0.50
solution
variable 1= 0.53
variable 2= 0.10
variable 3= 0.00
variable 4= 0.35
pour un resultat de 14.45
ou pour le dual:
0.00 0.00 1.00 0.15 0.00 0.00 -0.05 0.50
1.00 0.00 0.00 0.02 0.20 0.00 0.06 5.40
0.00 0.00 0.00 -0.37 0.80 1.00 0.39 35.10
0.00 1.00 0.00 0.11 -0.10 0.00 0.09 1.05
0.00 0.00 0.00 -0.53 -0.10 0.00 -0.35
solution
variable 1= 5.40
variable 2= 1.05
variable 3= 0.50
pour un resultat de 14.45
On voit que sauf les multiplications par , la solution trouvée dans l'un cas se trouve dans le tableau
final de l'autre cas dans la ligne ``fonction économique'' dans les colonnes des variables d'écart.
L'explication de ce phénomène en général n'est pas trop compliquée.
à chaque itération chacune des lignes du tableau contient une combinaison linéaire des
valeurs initiales de ces lignes; donc la dernière ligne (celle de la fonction) contient sa valeur
initiale moins une combinaison linéaire des autres lignes; mettons pour le coefficient de la
ligne dans cette combinaison linéaire après la dernière itération, c'est-à-dire
.
donc, en regardant la colonne on obtient .
donc, parce que l'algorithme ne halte que quand chaque , on a que
chaque .
et, en regardant les autres colonnes,
alors, les constituent une solution réalisable du programme dual.
la valeur de trouvée pour le programme initial est de qui est exactement la valeur
de son de la solution réalisable du dual ( ); et parce que les solutions du dual donnent
des majorants sur les solutions du primal, cette valeur de est forcément la solution optimale
commune des deux programmes et les deux solutions trouvées sont chacune optimale pour son
programme.
Interprétation économique de la solution du dual
La solution du programme dual peut nous donner des informations utiles sur comment la solution du
programme initial va changer si les contraintes changent. Rappelons que si est une valeur de la
variable dans la solution optimale du dual, est le coefficient final dans de la variable d'écart
numéro dans le tableau du primal. Donc, si cette variable est incrémentée par , la valeur de sera
décrémentée par ; donc, si on pouvait décrémenter la variable d'écart, serait incrémentée
par . Cela veut dire que si la ème contrainte est relachée par (remplacant par ), la
valeur de peut être augmentée par . Si cette contrainte exprime une quantité limité d'une
ressource (matière de base, main d'oeuvre etc.) on peut déduire que est le prix maximum qu'on
puisse raisonnablement payer pour avoir plus de cette ressource. Cette conclusion n'est valable que
pour les suffisamment petits que déplacer la contrainte par ne change pas la topologie du
polytope. L'intervalle de ces peut être étroite ou même nulle!
Exercices
Questionnaire de compréhension immédiate
1 exercices
