Graphes et Recherche Operationnelle ESIAL 2A

Publié par

Graphes et Recherche Operationnelle – ESIAL 2A Chapitre 4 : Dualite en programmation lineaire J.-F. Scheid 2011–2012 1

  • programme lineaire

  • x2 ≤

  • entreprise

  • programme lineaire dual

  • theoremes de dualite

  • dualite en programmation lineaire

  • prix unitaire

  • entreprise en question

  • conditions d'optimalite primal


Publié le : mardi 19 juin 2012
Lecture(s) : 69
Source : iecn.u-nancy.fr
Nombre de pages : 20
Voir plus Voir moins
Chapitre
4
:
GraphesetRechercheOp´erationnelle – ESIAL
Dualite´enprogrammation
J.-F. Scheid
2011–2012
lin´eaire
2A
1
Plan du chapitre
1
2
3
Introductionetd´enitions
Propriet´esetTh´eor`emesdedualite´ ´
Conditions d’optimalit´ primal-dual e
(COPD)
2
I.Introductionetde´nitions
Probl`emeduproduction .
Deux produits P 1 et P 2 fabrique´senquantit´e x 1 et x 2 ,n´ecessitanttrois ressourcesdisponiblesenquantite´sdonne´es.Lentreprisecherche`a maximiserleb´ene´cetotalprovenantdelaventedes2produits.
max F ( x 1 , x 2 ) [ ( x 1 , x 2 ) = 6 x 1 + 4 x 2 ] . 3 x + 24 xx 11 + x 9 2 x 2 2081 1 + 5 x 2 55 x 1 , x 2 0
3
tpoutienleobsieltinuoruduqpecrahoiumeantvedeixpruqtorpualage´snrepriseaes.Lentedulvineccpeetaresssssreetdrteoueuqitnemcruonusesirenimie´epesds.nsesellfereiaetvnnedantsesproduits.oseDoˆcn,e´tcaltehechurcherame`riae´nilemmargorPe.4
Quels prix unitaires y 1 , y 2 , y 3 lacheteurdoit-ilproposer`alentrepriseen question pour qu’elle accepte de vendre toutes ses ressources ?
( y 1 , m y 2 i , n ) [ G ( y 1 , y 2 , y 3 ) = 81 y 1 + 55 y 2 + 20 y 3 ] y 3 3 y 1 + 4 y 2 ++21 yy 33 64 9 y 1 + 5 y 2 y 1 , y 2 , y 3 0
e´estnuquanhcteSupposons`aprlprose.Ieprientredlcrsessuoseerslteourtteheacuropetnese´rpesrueressourcacunedes3yopruhcse1yy,,2nixuirtaleserisprtneirpeesopla`
Matrice A de taille m × n Vecteurs c R n et b R m .
D´enition(probl`emedual) Auprogrammeline´aireprimal
( PL )
x R n h F ( x ) = c > i max x x b x A 0
onassocieleprogrammelin´eairedual
( PLD )
y mi R n m h G ( y ) = b > y i A > y y 0 c
5
Programmeline´aireprimal x m a R n x h F ( x ) = c > x i A ( PL ) xx 0 b
Comparaison primal/dual .
Primal
max( F ) coefficient c de F second membre b m contraintesin´egalit´es( ) n contraintesdepositivit´e
Programmeline´airedual in ( PLD ) y m R y A m > h y G ( y ) c = b > y i 0
Dual
min( G ) second membre c coefficient b de G m contraintesdepositivit´e n contraintesine´galit´es( )
6
D´enitiong´ene´raledeladualit´equandleproble`meprimalestsous forme canonique mixte
Primal x m a R n x h F ( x ) = c > x i n i I 1 , X a ij x j b i j =1 n i I 2 , X a ij x j = b i j =1 j J 1 , x j 0
j J 2 , x j de signe quelconque
Dual y R m h G ( y ) b > y i min = i I 1 , y i 0
i I 2 , y i de signe quelconque m j J 1 , X a ij y i c j i =1 m j J 2 , X a ij y i = c j i =1
7
II.Propri´ete´s-Theore`mesdedualit´e ´
Proposition Le dual du dual est le primal.
Preuve . Dual d’un (PL) sous forme canonique pure : ( PL ) m y in h G ( y ) = b > y i m y ax h G ( y ) = ( b ) > y i D y A > y 0 c ⇐⇒ A > y ≤ − c y 0
On prend le dual du dual : m x in h ( c ) > x i ( ( x A > ) > x ( b ) > 0
⇐⇒
max h c > x i x x A x 0 b
( PL )
8
Th´eor`emesdedualit´e
Th´eor`eme1. Th´eoremefaiblededualite ` ´ Soit x unesolutionre´alisabledun(PL)sousformecanoniquemixteet y unesolutionr´ealisableduprobl`emedual(PLD).Alors: 1 F ( x ) G ( y ) 2 Si F ( x ) = G ( y ) alors x et y sont des solutions optimales de (PL) et (PLD) respectivement.
Preuve . (PL) sous forme canonique pure 1 On a A x b , x 0 et A > y c , y 0.
F ( x ) = c > x ( A > y ) > x > A x G ( y ) = y |{z} y > b = b
2 Soient x et y dessolutionsre´alisablesde(PL)et(PLD)tellesque F ( x ) = G ( y ).Dapr`es1.,pour x solutionre´alisablede( PL ), on a F ( x ) G ( y ) = F ( x ) donc x estunesolutionr´ealisableoptimale. Idem pour y .
9
Th´eor`eme2. Theore`mefortdedualite´ ´ Sileproble`meprimal(PL)admetunesolutionr´ealisableoptimale x alors leprobl`emedual(PLD)admetluiaussiunesolutionr´ealisableoptimale y et on a
F ( x ) = G ( y ) .
Preuve . On suppose (PL) mis sous forme standard. Silexisteunesolutionre´alisableoptimale,alorsilexisteune solution de base r´ealisableoptimale x B = A B 1 b . On choisit alors
y = ( A B 1 ) > c B .
On montre que y estunesolutionr´ealisableoptimalepourledual(PLD).
01
Avec y = ( A 1 ) > c B , on a B A H > y = A > H ( A B 1 ) > c B = A B 1 A H > c B = c H L H .
` Or, a l’optimum L H 0 donc A H > y c H . Puisque A > B y = c B , on a
A > y c y de signe quelconque. i.e. y estunesolutionre´alisabledudual(PLD)(pasdecontraintede positivit´esurlesvariables y du dual).
F ( x ) = c > x = c B > A B 1 b = ( A B 1 ) > c B > b = G ( y ) | {z } y Th´eor`emefaiblededualit´e y est optimal pour (PLD).
11
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.