6. Analyse postoptimale. Analyse postoptimale Mesurer linfluence sur la solution optimale de...

6. Analyse postoptimale

Analyse postoptimale

• Mesurer l’influence sur la solution optimale de modifier certains coefficients du problème

• Indiquer à l’utilisateur où mettre son énergie pour estimer avec plus de précision les coefficients les plus critiques

• 6.1 Modification des coefficients de la fonction économique

• 6.2 Modification des termes de droite

• 6.3 Modification des contraintes

• 6.4 Introduction d’une nouvelle variable

• 6.5 Introduction d’une nouvelle contrainte

6.1 Modification des coefficients de la fonction économique

a) Le coût cj d’une variable hors base est modifié

Seul le coût relatif de la variable xj est influencé dans le tableau optimal du simplexe.

En effet B et cB n’étant pas modifiés, n’est pas modifié, et les coûts relatifs des autres variables restent donc identiques.

Le coût relatif de la variable xj devient

La solution demeure optimale si

ou

jjjj cccc ~devient

1 BcTB

T

jjjjT

jjT

jjj cccacaccc )()(~

0~ jjj ccc jj cc

6.1 Modification des coefficients de la fonction économique

b) Le coût de la variable de base dans la ligne r est modifié

Alors le coût relatif de toutes les variables est modifié comme suit.

Le vecteur des multiplicateurs est modifié:

rjc

]...,,...,,,[~devient21 mrr jjjjj

TB

TB ccccccc

11 ]0,...,....,,0,0[ BcBcrj

TB

1]0,...,....,,0,0[ Bcrj

T

1~~Alors Bc TB

T

rrrr jjjj cccc ~devient

6.1 Modification des coefficients de la fonction économique

1]0,...,....,,0,0[~ Bcrj

TT

jT

jj

r

acc

jj

~~,pourAinsi

jjjT

j aBcacr

1]0,...,....,,0,0[

jjj accr

]0,...,....,,0,0[

rrrrrr jjjT

jjj

r

aBcaccc

j

1]0,...,....,,0,0[)(~Pour

rrrrr jjjjT

j aBccac

1]0,...,....,,0,0[)(

0)( rrr jjj ccc

rjjj accr

6.1 Modification des coefficients de la fonction économique

rrjjjj jjnjacccr

;,...,2,10~sioptimaledemeureactuellesolutionla,conséquentPar

rj

jj

rjjjrjjjj

rjr

a

cc

accaccc

ajj

r

rr

0~0quetelMais

rj

j

rj

jj

jrjjrjjjj

rjr

a

c

a

cc

cacaccc

ajj

r

rr

0~0quetel,similairefaçonDe

.0:min0:max

sioptimaledemeuresolutionlasomme,En

,...,2,1,...,2,1

rj

rj

j

jjnj

jrjrj

j

jjnj

aa

cca

a

c

r

r

r

6.1 Modification des coefficients de la fonction économique

.0:min0:max

sioptimaledemeuresolutionlasomme,En

,...,2,1,...,2,1

rj

rj

j

jjnj

jrjrj

j

jjnj

aa

cca

a

c

r

r

r

rjjTB

TB

TB

bczbcbcbc

bcz

rr

*]0,...,....,,0,0[~devientmodifiéproblèmeduoptimalevaleurlaalors

original,problèmeduoptimalevaleurladénote*Si

6.1 Modification des coefficients de la fonction économique

simplexe.dualgorithmel'avecmodifiéproblèmedu

résolutionlaspoursuivonnousalorsvérifiée,pasestn'

0:min0:max

conditionlaSi

,...,2,1,...,2,1

rj

rj

j

jjnj

jrjrj

j

jjnj

aa

cca

a

c

r

r

r

6.2 Modifications des termes de droite

rrr bbb devenirpourmodifiéestdroitedetermeleSi

121

2

1

2

1

11

2

1

1

decolonnelaest,...,,...,,où

0

0

0

0

0

0

deviennentoptimaltableaududroitedetermesLes

Br

b

b

b

b

b

bBbB

b

b

b

b

b

B

Tmrrrrr

r

rm

rr

r

r

m

rrr

m

r

121

2

1

2

1

11

2

1

1

decolonnelaest,...,,...,,où

0

0

0

0

0

0

deviennentoptimaltableaududroitedetermesLes

Br

b

b

b

b

b

bBbB

b

b

b

b

b

B

Tmrrrrr

r

rm

rr

r

r

m

rrr

m

r

.0:min0:max

direàestc'

,...,2,10

siréalisabledemeureactuellebasedesolutionlaAinsi

,...,2,1,...,2,1

ir

ir

i

mirir

ir

i

mi

riri

bb

b

mibb

6.2 Modifications des termes de droite

Si la solution n’est plus réalisable sous l’effet du changement, nous déterminons une nouvelle solution réalisable pour le problème modifié avec l’algorithme dual du simplexe.

.0:min0:max

direàestc'

,...,2,10

siréalisabledemeureactuellebasedesolutionlaAinsi

,...,2,1,...,2,1

ir

ir

i

mirir

ir

i

mi

riri

bb

b

mibb

6.3 Modification des contraintes

• Nous limitons notre étude au cas où les coefficients des variables hors base peuvent être modifiés

,devenirpour

modifiéestbasehorsvariableuned'tcoefficienleSi

ijij

ij

aa

a

.~direàestc'

0

0

0

0

~

devientbasehorsvariableladerelatifcoûtlealors

ijijj

ijT

jT

jijjT

jj

j

acc

aacaacc

x

6.3 Modification des contraintes

Si la solution n’est plus optimale, nous poursuivons la résolution du problème modifié avec l’algorithme du simplexe.

.0lorsque

0lorsque

0lorsque

sidireàestc'

0~sioptimaledemeuresolutionLa

iij

ii

jij

ii

jij

ijijj

quelconquea

ca

ca

acc

6.4 Introduction d’une nouvelle variable

Considérons le cas où nous voulons introduire une nouvelle variable xn+1

dont le coût unitaire est cn+1 et dont la colonne des coefficients est . 1na

.

derelatifcoûtlesDéterminon

111

1

nT

nn

n

acc

x

modifié.problèmelepouroptimaleest0avecactuellesolutionla

,0Si

1

111

n

nT

nn

x

acc

6.4 Introduction d’une nouvelle variable

Considérons le cas où nous voulons introduire une nouvelle variable xn+1

dont le coût unitaire est cn+1 et dont la colonne des coefficients est . 1na

.

derelatifcoûtlesDéterminon

111

1

nT

nn

n

acc

x

.

calculerdevonsnoussortie,decritèrele

exécuterpouretentrée,d'variabledevientvariableLa

simplexe.dualgorithmel'

avecmodifiéproblèmedurésolutionlaspoursuivonnousalors

,0Si

11

1

1

111

nn

n

nT

nn

aBa

x

acc

6.5 Introduction d’une nouvelle contrainte

a)

.

standardcontraintelarendrepourécartd'variableunensIntroduiso

.

typeducontrainteuned'ajoutl'sConsidéron

1111

1

111

n

jmnjjm

n

n

jmjjm

bxxa

x

bxa

6.5 Introduction d’une nouvelle contrainte

Le tableau associé à la solution optimale avant l’ajout de la nouvelle contraint

est modifié en introduisant la nouvelle contrainte dans la ligne (m+1) du tableau.

.tableaudu1ligneladansbasedevariableladevientvariableLa 1 mxn

r

r

jm

j

a

r

x

1parmultipliée

lignelasoustrairedesuffitiltableau,auajoutonsnous

queligneladans0àégaledetcoefficienlerendrePour

rjma 1

rjma 1

m

r

rjmmm

m

r

rjjmjmjm

j

babb

aaaa

x

r

r

1111

1111

.

devientdroitedetermeleet

devientdetcoefficienle

base,devariablechaquepouropérationmêmelaRépétant

Le tableau ainsi modifié devient

modifié.problemeduoptimalesolutionuneest

avecactuellesolutionlaalors

0Si

11

1111

mm

m

r

rjmmm

bx

babbr

Le tableau ainsi modifié devient

simplexe.dudualalgorithmel'avecmodifié

problèmedurésolutionlaspoursuivonNousnégative.est

actuellesolutionladansbasedevariablelaalors

,0Si

1

1111

m

m

r

rjmmm

x

babbr

6.5 Introduction d’une nouvelle contrainte

b)

.

standardcontraintelarendrepourécartd'variableunensIntroduiso

.

typeducontrainteuned'ajoutl'sConsidéron

1111

1

111

n

jmnjjm

n

n

jmjjm

bxxa

x

bxa

6.5 Introduction d’une nouvelle contrainte

Le tableau associé à la solution optimale avant l’ajout de la nouvelle contraint

est modifié en introduisant la nouvelle contrainte dans la ligne (m+1) du tableau.

r

r

jm

j

a

r

x

1parmultipliée

lignelasoustrairedesuffitiltableau,auajoutonsnous

queligneladans0àégaledetcoefficienlerendrePour

rjma 1

rjma 1

m

r

rjmmm

m

r

rjjmjmjm

j

babb

aaaa

x

r

r

1111

1111

.

devientdroitedetermeleet

devientdetcoefficienle

base,devariablechaquepouropérationmêmelaRépétant

Multiplions la dernière ligne du tableau par –1 pour que xn+1 devienne variable de base dans cette ligne

modifié.problemeduoptimalesolutionuneest

avecactuellesolutionlaalors

0Si

11

1111

mm

m

r

rjmmm

bx

babbr

Multiplions la dernière ligne du tableau par –1 pour que xn+1 devienne variable de base dans cette ligne

simplexe.dudualalgorithmel'avecmodifié

problèmedurésolutionlaspoursuivonNousnégative.est

actuellesolutionladansbasedevariablelaalors

,0Si

1

1111

m

m

r

rjmmm

x

babbr

6.5 Introduction d’une nouvelle contrainte

c)

.

typeducontrainteuned'ajoutl'sConsidéron

111

n

jmjjm bxa

6.5 Introduction d’une nouvelle contrainte

Le tableau associé à la solution optimale avant l’ajout de la nouvelle contraint

est modifié en introduisant la nouvelle contrainte dans la ligne (m+1) du tableau.

r

r

jm

j

a

r

x

1parmultipliée

lignelasoustrairedesuffitiltableau,auajoutonsnous

queligneladans0àégaledetcoefficienlerendrePour

rjma 1

rjma 1

m

r

rjmmm

m

r

rjjmjmjm

j

babb

aaaa

x

r

r

1111

1111

.

devientdroitedetermeleet

devientdetcoefficienle

base,devariablechaquepouropérationmêmelaRépétant

Le tableau ainsi modifié devient

pivot.uncomplétonsnouslequelsur

lignedernièreladansnégatifélémentunschoisisson

modifié,problèmedubasedesolutionuneidentifierPour

.0que Supposons 1 mb

Le tableau ainsi modifié devient

0:max

:simplexedudualalgorithmel'danscommepivotde

élémentl'schoisissonnousrelatifs,coûtsdesnégativiténon lapréserverPour

1111

1

jmjm

j

njsm

s

sm

aa

c

a

c

a

Le tableau ainsi modifié devient

.négatifdroitedetermeunretrouverpour1par)1(lignela

multipliéavoiraprèsfaçonmêmeladeonsnousprocéd,0S

1

1

m

m

bm

bi

Le tableau résultant est comme suit

1~

,...,2,1~

estmodifiéproblèmeduoptimalesolutionunealors

,1,...,2,10~

Si

ms

rj

i

bx

mrbx

mib

r

simplexe.dudualalgorithmel'avecmodifié

problèmedurésolutionlaspoursuivonnousAutrement