23
La notion de dualit´ e Dual d’un PL sous forme standard Un programme lin´ eaire est caract´ eris´ e par le tableau simplexe " A b c # . Par d´ efinition, le probl` eme dual est obtenu en transposant ce tableau. " A T c T b T # . Soit v ∈< n le vecteur-colonne des variables du probl` eme dual ou u ∈< n le vecteur-ligne des variables du probl` eme dual. 38 Outils d'aide à la décision Master SIS 2009-2010

La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

  • Upload
    builien

  • View
    213

  • Download
    0

Embed Size (px)

Citation preview

Page 1: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 2: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 3: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 4: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 5: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 6: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 7: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 8: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 9: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 10: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 11: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 12: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 13: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 14: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

• 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

Page 15: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 16: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 17: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 18: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 19: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 20: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 21: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 22: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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

Page 23: La notion de dualit¶e Dual d’un PL sous forme standard de cours_114.pdf · tableau simplexe " A b c #: ... construire une solution avec ... de recherche d’une solution initiale

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