Chapitre 3 : Analyse post-optimale

Publié par

Graphes et Recherche Operationnelle – ESIAL 2A Chapitre 3 : Analyse post-optimale J.-F. Scheid 2011–2012 1

  • permutation pres des colonnes

  • methode des dictionnaires appliquee au probleme de production de l'introduction

  • analyse post-optimale de l'objectif

  • base optimale

  • optimum dans le tableau du simplexe


Publié le : mardi 19 juin 2012
Lecture(s) : 320
Tags :
Source : iecn.u-nancy.fr
Nombre de pages : 13
Voir plus Voir moins
GraphesetRechercheOp´erationnelle
Chapitre
3
:
Analyse
post-optimale
J.-F. Scheid
2011–2012
ESIAL
2A
1
Plan du chapitre
1
2
3
Introduction
Analyse post-optimale
Analyse post-optimale
de l’objectif
du second membre
des
contraintes
2
I. Introduction
Lanalyseoptimalepermetdede´terminer lasensibilite´ d’un PL par rapportauxdonn´ees : Unefaiblevariationdesdonn´eesentraine-t-elleunchangement important de la solution optimale ? Lanalyseoptimalepermetdede´terminer des intervalles de variationsdesdonne´es pour lesquels la base optimale B n’est pas modi´ee.
3
II. Analyse post-optimale de l’objectif
But :e´tudierlinuencedes coefficients de la fonction objectif sur l optimum.
PL sous forme standard qui admet une base optimale B (fin normale du simplexe). A une permutation pres des colonnes, `
A = ( A B | A H ) .
On note A H lamatricehors-baseobtenue`aloptimumdansletableaudu simplexe. La matrice A H estdonne´epar
A H = A B 1 A H
4
L.maAHdodee´htctioesdiresannaie´uqilpplborpuaeprdeme`eontiucodExlpmededeete´nimrioatelndatamceriL>)0,0(=>)3e,2(e=H>x2272,15atepere´ine`dareedelnairtionediclosaoituruofltinucodontildetrin1>)=,52x,1e,exB=(xnoptimal5
x 2 = 5 13 e 2 + 23 e 3 = x 1125 + 16 e 2 65 e 3 e 1 = 227 + 52 e 2 7 e 3 2 F = 65 13 e 2 73 e 3
La matrice A H vaut donc + A H = 613125 ++ 32756 . 2
ate´ti
Proposition(conditiondoptimalite´) Laconditiondoptimalit´e
L H > = c > H c B > A H 0
est une condition suffisante optimale.
pourquunesolutiondebasere´alisablesoit
n Preuve : Pour tout x R , on a
F ( x ) = F ( x ) + L H > x H >
ou` x estunesolutiondebasere´alisableassoci´ee`alabase B .
(1)
6
.Onutilept´rdoutioplimaitiddnolesinocaremrnie´et
Application l’influence d’un coefficient de la fonction objectif F : Onremplacececoecientparunparame`treetoncalculelacondition doptimalite´. Onobtientalorsuneconditionsurceparame`tre.Cetteconditionest uneconditionne´cessairepourquelasolutiondebaseoptimalesoit inchangee et une condition suffisante pour que la solution obtenue ´ soit optimale.
7
O.elpmexdnerpernEe`emedrpdocuitnolexempleduprobl8
Onveute´tudierlasensibilitedeloptimumparrapportauprixdevente ´ unitaire du produit P 1 (variable x 1 ) qui vaut 6. De combien peut-on faire varier ce prix, sans changer le plan de production ? Onatrouve´lasolutiondebaseoptimale x B = ( x 2 , x 1 , e 1 ) > = 5 , 125 , 227 > x H = ( e 2 , e 3 ) > = (0 , 0) > 3 3 A 152162756 H =  2
( x m 1 , a x x 2 ) [ F ( x 1 , x 2 ) = 6 x 1 + 4 x 2 ] . 3 x 1 + 9 x 2 81 4 x 1 + 5 x 2 55 2 x 1 + x 2 20 x 1 , x 2 0
On remplace le coefficient 6 dans F parunparam`etre c 1 :
c > = (4 , c 1 , 0) , c > H = (0 , 0) . B
Lescoˆutsre´duitsdeviennentalors L H > = c H c B > A H = c 6 1 43 , 38 56 c 1 . >
Laconditiondoptimalit´e L H > 0 donne alors
16 5 c 1 8 .
Interpre´tation .Sionchoisit156 c 1 8, la solution de base optimale est inchang´eecest-`a-direqueleplandeproductionnechangepas.Ona F =125 c 1 + 20. Avec c 1 = 8 (la valeur max. permise pour c 1 ), on obtient F = 80 soit u ´ t de Δ F = 15. n ecar
9
II. Analyse post-optimale du second membre des contraintes
But :´etudierlinuencedu second membre des contraintes sur la solution de base optimale.
PL sous forme standard qui admet une base optimale B (fin normale du simplexe).Aunepermutationpre`sdescolonnes,
A = ( A B | A H ) .
Proposition(conditiondefaisabilite´) Aloptimum,onan´ecessairementlaconditiondefaisabilit´e
x B = A B 1 b 0 .
(2)
01
x B = A B 1 d 0 .
¸lepram`etre On obtient de cette facon une condition sur a introduit. Cetteconditionestuneconditionn´ecessairepourquelabase optimale B soitinchang´ee.
1
Application l’influence d’un coefficient du second membre des contraintes sur la solution optimale. Onremplacececoecientparunparame`tre.Onobtientainsiun second membre d . Oncalculealorslaconditiondefaisabilite´surlasolutiondebase
Remarque . Les valeurs de la solution de base x B changent, mais x B est toujoursunesolutiondebaser´ealisableoptimalecaronmaintientlescouts ˆ re´duits L > H 0inchang´es.
1nuti.Oocalesildnoitidnbisaaiefouept´lidre´etmrnire
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.