Upload
builien
View
213
Download
0
Embed Size (px)
Citation preview
La notion de dualite
Dual d’un PL sous forme standard
Un programme lineaire est caracterise par le
tableau simplexe[
A bc
].
Par definition, le probleme dual est obtenu
en transposant ce tableau.[
AT cT
bT
].
Soit v ∈ <n le vecteur-colonne des variables
du probleme dual ou u ∈ <n le vecteur-ligne
des variables du probleme dual.
38
Outils d'aide à la décision
Master SIS 2009-2010
Le probleme primal s’ecrit:
(P )
Min xz = cxsous Ax = b
et x ≥ 0
Le probleme dual s’ecrit:
(D)
Max v w = bTv
sous ATv ≤ cT
et v ≥ 0 ou < 0
ou encore, avec u = vT ,
(D)
Max u w = ubsous uA ≤ c
et u ≥ 0 ou < 0
39
Outils d'aide à la décision
Master SIS 2009-2010
Dual d’un PL sous forme generale
Primal DualMinimiser cx Second membre cT
Second membre b Maximiser bTvA matrice des contraintes AT matrice des contraintes
Contrainte j ≥ Variable vj ≥ 0Variable xi ≥ 0 Contrainte i ≤contrainte j = Variable vj ≥ 0 ou ≤ 0
Variable xi ≥ 0 ou ≤ 0 Contrainte i =
40
Outils d'aide à la décision
Master SIS 2009-2010
Theoremes de la dualite
1. Le dual du dual est le primal.
En effet, la transposee d’une matrice est
la matrice elle-meme.
2. Si x et u sont respectivement des solu-
tions du primal et du dual, alors:
z = cx ≥ w = ub .
Demonstration :Dans (P), multiplions les 2 termes de la con-trainte Ax = b a gauche par u
uAx = ub
Dans (D), multiplions les 2 termes de l’inegaliteuA ≤ c a droite par x: (x ≥ 0):uAx ≤ cx. D’ou ub ≤ cx.Interpretation :Une solution primale admissible sous-optimale estmeilleure qu’optimale, mais non admissible pourle probleme dual.Une solution duale admissible sous-optimale estmeilleure qu’optimale, mais non admissible pourle probleme primal.
41
Outils d'aide à la décision
Master SIS 2009-2010
3. Si (P) et (D) ont des solutions, alors chacund’entre eux a une solution optimale et:
z∗ = min cx = w∗ = max ub
Reciproquement, si x est admissible pour (P) etu est admissible pour (D) et que cx = ub, alors xest optimal pour (P) et u est optimal pour (D).Si l’un d’eux a un optimum non borne, l’autre n’apas de solution.
4. Complementarite:Une CNS pour que (x∗, u∗) soit optimal est:(u∗Aj − cj)x∗j = 0 ∀j = 1, .., n,Aj representant la jeme colonne de A.
Elements de demonstration :
uAx = ub
donc
uAx− cx = ub− cx
L’egalite est obtenue si et seulement si (x∗, u∗)est optimal.
Interpretation Les variables xj ≥ 0 sont as-sociees aux contraintes inegalite uAj ≤ cj:Une variable duale associee a une contrainte inegalitenon saturee (uAj < cj) est necessairement nulle.Une variable duale associee a une contrainte saturee(uAj = cj) est necessairement positive.
Outils d'aide à la décision
Master SIS 2009-2010
Interpretation economique de la dualite:
La variable duale associee a une contrainte
correspond au cout de cette contrainte dans
la solution courante. Si cette contrainte est
saturee, ce cout est positif. Il est nul si cette
contrainte n’est pas saturee.
Utilisation algorithmique de la dualite
Resolution du dual
La premiere utilisation, evidente, du probleme
dual, est de le resoudre s’il est plus simple que
le probleme primal. Ce sera le cas, en par-
ticulier, lorsque le probleme primal n’a pas
de solution admissible evidente mais qu’il est
facile d’en construire une pour le probleme
primal.
42
Outils d'aide à la décision
Master SIS 2009-2010
Proprietes du dual
On remarque que la condition d’admissibilite
d’une solution de base pour le probleme dual
est c ≥ 0, qui est la condition d’optimalite du
probleme primal. De facon analogue (duale),
la condition d’admissibilite d’une solution de
base pour le probleme primal est b ≥ 0, qui
est la condition d’optimalite du probleme dual.
On resoudra donc plutot le probleme dual
au lieu du probleme primal s’il est plus sim-
ple ou (et) si l’on parvient plus facilement a
construire une solution avec c ≥ 0 qu’avec
b ≥ 0
43
Outils d'aide à la décision
Master SIS 2009-2010
Exemple
Min x1,x2 z = 4x1 + 6x2 + 18x3sous x1 + 3x3 ≥ 3sous x2 + 2x3 ≥ 5et x1, x2, x3 ≥ 0
L’introduction de variables d’ecart x4 et x5
conduit au tableau simplexe suivant:
x4 x5 x1 x2 x3 z(1) 1 0 -1 0 -3 0 -3(2) 0 1 0 -1 -2 0 -5(c) 0 0 4 6 18 -1 0
La solution de base construite avec comme
variables de base les variables d’ecart n’est
pas admissible car les termes de b sont negatifs.
Mais on peut remarquer que tous les couts
reduits associes aux variables d’ecart sont posi-
tifs. La valeur ”de base” du critere est donc
un minorant de la valeur optimale du critere.
44
Outils d'aide à la décision
Master SIS 2009-2010
Probleme dual
Cette propriete sur les couts reduits indique
que la solution de base associee est admissi-
ble pour le probleme dual.
Le probleme dual s’ecrit:
Max u1,u2 w = 3u1 + 5u2sous u1 ≤ 4
u2 ≤ 63u1 + 2u2 ≤ 18et u1, u2 ≥ 0
45
Outils d'aide à la décision
Master SIS 2009-2010
Appliquons la methode du simplexe auprobleme dual.
• Etape 1:
u3 u4 u5 u1 u2 w(1) 1 0 0 1 0 0 4(2) 0 1 0 0 1 0 6(3) 0 0 1 3 2 0 18(c) 0 0 0 3 5 -1 0
• Etape 2: variable entrante u2, variablesortante u4, puis variable entrante u1, vari-able sortante u5, ce qui donne
u3 u2 u1 u5 u4 w(1) 1 0 0 -1/3 2/3 0 2(2) 0 1 0 0 1 0 6(3) 0 0 1 1/3 -2/3 0 2(c) 0 0 0 -1 -3 -1 -36
La solution duale optimale est donc: w∗ =36, u∗1 = 2, u∗2 = 6, u∗3 = 2, u∗4 = u∗5 = 0.
46
Outils d'aide à la décision
Master SIS 2009-2010
L’algorithme dual du simplexe
1. Base initiale en representation primale,
non-realisable pour le primal mais cor-
respondant a une solution realisable du
probleme dual : B0, k = 0.
Pour etre duale-realisable, on doit avoir,
pour une minimisation, cN ≥ 0, et pour
une maximisation, cN ≤ 0
2. Pour k, calculer b = B−1b, π = cBB−1,
cN = cN − πN , A = B−1A,
3. Si b ≥ 0, STOP, optimum realisable at-
teint
Sinon, choisir s tel que bs ≤ 0. En pra-
tique, on choisit la variable de base dont
la valeur est la plus negative. Cette vari-
able sort de la base. Elle sera donc nulle
dans la base de l’iteration k+1.
47
Outils d'aide à la décision
Master SIS 2009-2010
4. Pivot. Soit As la ligne s de A.
On fait entrer dans la base une variable
de base a coefficient negatif dans As. On
choisit comme variable entrante i celle
pour laquelle le rapport ci−Ais
est non-negatif
et minimal, de facon a faire croıtre le
critere le moins possible.
Construire la nouvelle base, B et aller en
2-
Outils d'aide à la décision
Master SIS 2009-2010
Exemple
x4 x5 x1 x2 x3 z(1) 1 0 -1 0 -3 0 -3(2) 0 1 0 -1 -2 0 -5(c) 0 0 4 6 18 -1 0
On constate que la solution est duale-realisablecar les coefficients ci sont non-negatifs.
• Etape 1On choisit x5 comme variable de basesortante. La variable entrante est x2, quel’on elimine dans l’equation (c), ce quidonne, apres permutation des colonnesde x5 et x2 :
x4 x2 x1 x5 x3 z(1) 1 0 -1 0 -3 0 -3(2) 0 1 0 -1 2 0 5(c) 0 0 4 6 6 -1 -30
On constate que la solution est resteeduale-realisable car les coefficients ci sontnon-negatifs.
48
Outils d'aide à la décision
Master SIS 2009-2010
• Etape 2
La nouvelle variable sortante est x4 et la
nouvelle variable entrant en base est x3,
ce qui donne:
x3 x2 x1 x5 x4 z(1) 1 0 1/3 0 -1/3 0 1(2) 0 1 -2/3 -1 2/3 0 3(c) 0 0 2 6 2 -1 -36
La solution est devenue primale-realisable
tout en restant duale-realisable. Elle est
donc optimale. La solution primale opti-
male est donc : z∗ = 36, x∗1 = 0, x∗2 = 3,
x∗3 = 1.
Outils d'aide à la décision
Master SIS 2009-2010
Utilisation de la complementarite
La solution duale et la solution primale opti-
males ont ete obtenues par deux techniques
differentes.
On verifie que z∗ = w∗ = 36, mais ce resultat
etait connu theoriquement.
De meme, la theorie permet directement de
trouver les valeurs optimales des variables duales.
On a donc en pratique un seul probleme a
resoudre,
Theoreme
La valeur optimale de la variable duale as-
sociee a une contrainte inegalite est egale
(au signe pres) au cout reduit de la variable
d’ecart associee dans le tableau simplexe de
la solution primale optimale.
Exemple: Ici, a partir de la solution primale,
on deduit: u∗1 = 2, u∗2 = 6. En reportant ces
valeurs dans l’expression du dual, on obtient
les variables d’ecart du dual: u∗3 = 2, u∗4 =
0 u∗5 = 0.
49
Outils d'aide à la décision
Master SIS 2009-2010
Algorithme primal-dual
Dans le cas ou il est difficile de trouver une
solution primale-realisable mais aussi une so-
lution duale-realisable, on peut partir d’une
initialisation quelconque des variables et proceder
alternativement par optimisation duale et pri-
male. L’introduction de variables artificielle
est un autre moyen de resoudre le probleme
de recherche d’une solution initiale admissi-
ble. Il s’agit alors de la methode dite revisee
du simplexe.
50
Outils d'aide à la décision
Master SIS 2009-2010
Application Numerique
Voici des valeurs numeriques relatives au problemede transport:
1
2
1
2
3
MARSEILLE
LE HAVRE
PARIS
TOULOUSE
BORDEAUX
53
6
53
4
QUANTITES DISPONIBLES
QUANTITES DEMANDEES
550
350
400
300
200
Application Numerique
Minimiserz = 5x11 +6x12 +3x13 +3x21 +5x22 +4x23
sous les contraintes:x11 + x12 + x13 ≤ 550x21 + x22 + x23 ≤ 350−x11 − x21 ≤ −400−x12 − x22 ≤ −300−x13 − x23 ≤ −200
xij ≥ 0 pour i = 1,2, pour j = 1, ..,3.
51
Outils d'aide à la décision
Master SIS 2009-2010
Interpretation du probleme dual
Le probleme primal exprime le point de vue
du constructeur qui cherche a minimiser ses
couts de production.
Le probleme dual s’ecrit ainsi :
Maximiser
z = −550u1−350u2+400v1+300v2+200v3
sous les contraintes:
v1 − u1 ≤ 5
v2 − u1 ≤ 6
v3 − u1 ≤ 3
v1 − u2 ≤ 3
v2 − u2 ≤ 5
v3 − u2 ≤ 5
ui ≥ 0 pour i = 1,2, vj ≥ 0 pour j = 1, ..,3.
52
Outils d'aide à la décision
Master SIS 2009-2010
Interpretation du probleme dual
Le probleme dual exprime le point de vue du
transporteur qui veut maximiser son profit.
Ses variables sont les prix d’achat a Mar-
seille (u1) et au Havre (u2) et ses prix de
vente a Paris (v1), Toulouse (v2) et Bordeaux
(v3). Les quantites qu’il doit acheter et ven-
dre sont fixees. Les contraintes du probleme
dual expriment que les prix sont competitifs,
c’est a dire acceptables pour le constructeur.
53
Outils d'aide à la décision
Master SIS 2009-2010
Resolution
La valeur optimale du critere est 3700 $. Elle
correspond au graphe d’approvisionnement suiv-
ant.
1
2
1
2
3
MARSEILLE
LE HAVRE
PARIS
TOULOUSE
BORDEAUX
50
350
300
200
QUANTITES DISPONIBLES
QUANTITES DEMANDEES
550
350
400
300
200
Solution optimale
54
Outils d'aide à la décision
Master SIS 2009-2010
Approche Lagrangienne en
Programmation Lineaire
Le lagrangien d’un probleme permet de com-
biner la formulation duale et la formulation
primale.
Soit x le vecteur de variables de (P), appelees
variables primales.
Soit u le vecteur de variables de (D), appelees
variables duales.
Les variables duales sont associees aux con-
traintes Ax = b du probleme primal.
Elles sont encore appelees multiplicateurs de
Lagrange, car elles sont associees multiplica-
tivement aux contraintes a travers les rela-
tions de complementarite a l’optimum :
u∗j(bj −Ajx∗) = 0.
55
Outils d'aide à la décision
Master SIS 2009-2010
Approche Lagrangienne en
Programmation Lineaire
Le lagrangien du probleme est la fonction:
L(x, u) = cx + u(b−Ax)
Resoudre le probleme (P) est equivalent a
resoudre son probleme dual (D). Ces problemes
sont equivalents au probleme suivant :
Maxu Minx≥0L(x, u) = cx + u(b−Ax)
Le probleme d’optimisation sous contraintes
revient a la recherche du point selle du la-
grangien sans contraintes.
56
Outils d'aide à la décision
Master SIS 2009-2010
Lemme de Farkas-Minkowski
C’est un lemme tres utile dans de nombreuses
demonstration, et a la base des proprietes de
dualite.
Lemme
Un et un seul des systames lineaires suivants
a une solution :
{Ax ≤ bx ≥ 0
et
uA ≥ 0u ≥ 0ub < 0
Il y a de nombreuses variantes de ce Lemme.
Corollaire du Lemme de Farkas
∃x ≥ 0; Ax = b si et seulement si
uA ≥ 0 =⇒ ub ≥ 0 (b, u ∈ <m).
Corollaire
∃x; Ax ≤ b si et seulement si
u ≥ 0 et uA = 0 =⇒ ub ≥ 0 (b, u ∈ <m).
Corollaire
∃x ≥ 0; Ax ≤ b si et seulement si
u ≥ 0 et uA ≥ 0 =⇒ ub ≥ 0 (b, u ∈ <m).
57
Outils d'aide à la décision
Master SIS 2009-2010