[PDF] Université Pierre et Marie Curie



Previous PDF Next PDF







Méthodes et outils doptimisation - Optimisation

Programmation linéaire Nombres entiers Programmation par Contraintes Meta-heuristiques Conclusion Biblio Méthodes d'optimisation Méthodes génériques : Programmation linéaire (modélisation sous forme d'équations linéaires) Programmation en nombres entiers (variables entières) Programmation quadratique Programmation dynamique



Cours de Programmation linéaire et Recherche Opérationnelle

2 Chapitre 1 Programmation linéaire ormFulation : Un programme linéaire écrit sous sa forme canonique, s'écrit sous la forme : (PL) 8 >> < >>: Max z= f:x S:c Ax b x 0: f: la fonction objective (fonction coût) A= (A ij) 1 i m 1 j n 2Rmn: matrice de contraintes b= (b i) 1 i m: second membre des contraintes x= (x j) 1 j n 2R n: ariablev



Programmation linéaire

Programmation linéaire en nombre entiers : toutes les ariablesv sont entières Résoudre un PLNE est un problème NP-complet Dé nition Etant donné un P L en nombre entiers, on appelle P L relaxé le P L privé de ses ontrcaintes d'intégrité, àdc les variables sont elérles Théorème Soit w





ETUDE DES METHODES DE POINT INTERIEUR APPLIQUEES A LA

François Glineur Etude des méthodes de point intérieur appliquées à la programmation linéaire et à la programmation semidéfinie A 1 Introduction - Présentation générale Page 2 A INTRODUCTION A 1 PRESENTATION GENERALE La programmation mathématique, branche de l’optimisation, s’occupe de la minimisation sous



Recherche opérationnelle Aide à la décision

2 Programmation linéaire : généralisation et théorie 2 1 Généralités Dé nition 2 1 1 La programmation linéaire est une méthode permettant d'optimiser (maximiser ou minimiser) une fonction linéaire sous certaines contraintes linéaires dé nies par des inégalités



La r f rence a ronautique - LAAS

Programmation linéaire en nombres entiers Dé nitions Programmation linéaire avec variables entières PL : trouver x = argmin f cT x jx 2 Z n;A x 0 g max x 1 +2 x 2 3 x 1 +4 x 2 4 3 x 1 +2 x 2 11 2 x 1 x 2 5 x 1;x 2 entiers x 1 x 2 3 x 1 + 4 x 2 = 4 3 x 1 + 2 x 2 = 11 2 x 1 x 2 = 5 Christian Artigues (LAAS-CNRS) Optimisation sous incertitudes



La budgétisation de la production est la représentation

programmation linéaire permettent d’y répondre Combien faut-il commander et stocker de manières premières pour satisfaire la demande prévue ? le calcul des besoins en composants donne la réponse Comment et combien faut-il charger les ateliers, les machines, les capacités humaines pour que la production correspondre aux



INTRODUCTION À LA RECHERCHE OPÉRATIONNELLE

CHAPITRE 1 GÉNÉRALITÉS Présentation La Recherche Opérationnelle (RO) est la discipline des mathématiques appliquées qui traite des questions d'utilisation optimale des ressources dans l'industrie et dans le secteur public

[PDF] programmation lineaire methode simplexe

[PDF] programmation linéaire recherche opérationnelle

[PDF] interprétation droite de henry

[PDF] principe droite de henry

[PDF] exercice corrigé droite de henry

[PDF] courbe de henry excel

[PDF] droite de henry pdf

[PDF] programmation linéaire exercices corrigés pdf

[PDF] programmation linéaire exercices corrigés

[PDF] programmation linéaire simplexe

[PDF] recherche opérationnelle programmation linéaire exercices corrigés pdf

[PDF] exercices recherche operationnelle

[PDF] recherche opérationnelle cours complet

[PDF] cours recherche opérationnelle methode de simplexe

[PDF] recherche opérationnelle simplexe exercices corrigés

???? ????? ??????? ???conv(S)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???? ?????? ????? ??????? ??PM(G)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???? g i(x)0i= 1;:::;m x2S: g i(x)0i= 1;:::;m x2ZZn:

10x1+ 12x259

x

1??x20

x

1;x2???????:

4 3 2 1 0

123456x

2 x

1Optimum continu= (5:9;0)Optimum entier= (1;4)

10x1+ 12x2= 59

A

1x1+A2x2b

x

12IRn1

x

22ZZn2:

8x1;x22S;82[0;1]; f(x1+ (1)x2)f(x1) + (1)f(x2):

x2S: g i(x)0i= 1;:::;m x2S: i=1P n j=1qijxixj+Pn i=1lixi g(x)0 x 2ZZn: x

TAx=Pn

i=1P j=1Aijxixj>0?????xTAx0?? ???? ?? ??? ?? ?? ???????Q???? A iXci;i= 1;:::;m y2IRm q(x1;x2) =Cx1x28(x1;x2)2 f0;1g2 ~q(x1;x2) =12

C(x1+x2)212

C(x1+x2)8(x1;x2)2 f0;1g2

~q(x1;x2) =12

C(x21+x222x1x2)12

C(x1+x2) =q(x1;x2)

i=1v iyi??nX i=1y i= 1? i=12 iyi?? y i2 f0;1g????i= 1;:::;n? ?????? ???L??L??x???? ??????? ??? ??? ??????M? xLy??xMy: e=xy,8 >>>>:ex ey ex+y1 e0 e2IR x b??xc? a a

1xb1a1xb1+M1y1

a

2xb2a2xb2+M2y2

a nxbnanxbn+MnynPn i=1yi=nk y

2= 1y?

a1x b1+M(1y)????? a

2xb2+My?????

??? ?? ???fw(F)jF2 Fg: E ???W? ????N(W) =S e P??? ?? ????? ?? ??? ?????? ??uv??? ????? ??EnP????u;v2V(P)? ?????uv??? ??????? ?? ?????? ??????? ???v ???? ?? ?????ai? ?? ???? ?????? ??? ?????? ???? ?? ????? ??? ???? ???? ?? ??????? p i???? ?? ?? ????qi????? nX i=1c ixi n X i=1a ixib;????? p ixiqi;????i= 1;:::;n; x i2IN;????i= 1;:::;n: ??? ???????F fE1;:::;Emg??? ???? E a) b) c) 21
4 5 21
4 5 21
4 5E 1 E 2E 1E1E 4 E 3 mX i=1c jxj Ax1? x2 f0;1gm?????? mX i=1c jxj Ax1? ?????? ????mX i=1c jxj

Ax= 1?

x2 f0;1gm A=0 B

BBBB@1 1 0 0

1 0 0 0

0 1 1 1

0 1 1 1

0 1 0 11

C

CCCCA:

v2Sc(v)???? ? ?? ????? ?? ??????? ?? ?? ??? ??? ?????? ??? ??????? ??? ?? ??????fv1;v5g?v 1 v 5 v 3v2v 4 ???? ??? ??? ??????? ??V??? ???S(u) = 1??u2S?? ? ?????? ?? ??? ??????? X u2Vc(u)x(u) x(u) +x(v)1;???? ????uv2E;????? x(u)2 f0;1g;???? ????u2V: X u2Kx(u)1;???? ????? ??????K??G:????? X i;jc ijxij P j2Vxij= 1???? ????i2V;?????P i2Vxij= 1???? ????j2V;????? x ij0???? ????(i;j)2VV; x ij2IN???? ????(i;j)2VV: u

1= 1;?????

2uin???? ????i6= 1;?????

u iuj+ 1n(1xij)???? ????i6= 1;j6= 1:????? ? ???? ???? ???? ???(i;j)??xij= 1? ????? ???????ujui+ 1? u X i2S;j2Sx ij jSj 1;???? ????SV;jSj>1;S6=V????? X e2+(W)x(e)1;???? ????W(V etW6=;;?????? X e2(W)x(e)1;???? ????W(V etW6=;; Min X e2Ec(e)x(e) X e2(v)x(e) = 2;???? ????u2V;?????? X e2(W)x(e)2;???? ????W(V??W6=;;?????? x(e)2 f0;1g;???? ????e2E: KX l=1w l K X l=1x lu= 1;???? ????u2V;?????? x lu+xlvwl;???? ????e=uv2E??1lK;?????? x lu2 f0;1g;???? ????u2V??1lK: X S2St S X

S2S ju2St

S= 1;???? ????u2V;??????

t

S2 f0;1g;???? ????S2 S:??????

X a2+(u)x(a)X a2(u)x(a) = 08u2vn fs;tg: ???? ?? ??? ??? ??? ?? ??????P a2(s)x(a)? ???vX a2+(u)x(a)X a2+(u)x(a) = 08u2Vn fs;tg?????? X a2+(s)x(a)v= 0;?????? X a2(t)x(a) +v= 0;?????? x(a)c(a)8a2A;?????? v0;?????? x(a)08a2A:?????? ???? ?? ?????? ??????? ???????G= (V1[V2;E)??????? ? ?? ?????c2INm??????? ??? ??????? ??? ??? ?? ??????? ?????c??? ??????? X e2Ec(e)x(e) X e2(u)x(e)18u2V1?????? X e2(u)x(e)18u2V2?????? x(e)08e2E:?????? i=1E(ri)xi? ?? ????? ?? ?????? ???????Pn i=1V(ri)x2i? (D)8 >>>:Max a0+Pn i=1aixib 0+Pn i=1bixi Tx x i2 f0;1g 8i2 f1;:::;ng: ?ai0????i= 0;1;:::;n ?bi0????i= 1;:::;n??b0>0 s i= 1;:::;n??j= 1;:::;m? i= 1;:::;n??j= 1;:::;m? mX j=1c jyj+nX i=1m X j=1c ijxij m X j=1x ij=di;???? ????i2 f1;:::;ng;????? n X i=1x ijMjyj;???? ????j2 f1;:::;mg;????? y j2 f0;1g;???? ????j2 f1;:::;mg; x ij0;???? ????i2 f1;:::;ng??j2 f1;:::;mg: ???????Pm s ??????? ?Mj???? ???????j? e2E0w(e)???? H ij=J(d)SiSj

H(S) =X

ij2LJijSiSj ij2Ewij ??????E0??? ????? ??G? ??????? ??? ???? ???? ?????C??G?? ???? ????FC ????jFj???????E0\C6=F?

0??????

x(F)x(CnF) jFj 1???? ???? ?????C;FC;jFj???????(1) (P)8 X e2Ec(e)x(e) x(F)x(CnF) jFj 1;???? ???? ?????C; FC;jFj???????(1)

0x(e)1;???? ????? ?????e2E;(2)

x(e)??????;???? ????? ?????e2E:(3) ??2;4:1018 ????10

301??????

????? ???zoptzapproxzopt? gap=zbsgzbestsolz bestsol: ???? ??? ?? ??????? ??????? ?v 0v 1v 2v 3v 4v

0?????

v

1?????

v

2?????

v

3?????

v

4?????

??????v

3v4v4v3v2v2v3v4v4v1v

1v2v3v4

v

2v3v4v3v4v1v2v4v1v2v3v1

v

1v3v4v1v1v3v2v1v1v2v3v2v2v4(1) =

(2) =v 0 ((4))(3) = v v 23

2123 2312 18

19 2210

18 14 16

19 2516v

1v2v3v4

v

2v3v4v3v4v1v2v3v1

v

1v3v1v3v

0 v 3v1v4 ?x1+x2<= 5?x1+x2>5?? ? ?????? L??? ???? ????? ????? ? ?????? Pi????L? ???4x1+ 5x2 x

1+ 4x25

3x1+ 2x27

x

10;x20

x

1;x22IN:

2 5 43
8 91
6 7

101123,1

19,7

18,7 19,6 19,4 18,6

18,0 18,7 19,5 18,2 18,1

y ???c1x1+c2x2+c3x3+:::+cnxn a

1x1+a2x2+a3x3+:::+anxnb

x i2 f0;1g 8i2 f1;:::;ng: b >0?ci;ai>0????i= 1;:::;n?Pn i=1ai> b ??c1a 1c2a 2c3a

3:::cna

n: i=1aib??Pk+1 i=1ai> b? x i= 1????i= 1;:::;k x k=bPk i=1aia k+1xi= 0????i=k+ 2;:::;n? ???16x1+ 22x2+ 8x3+ 12x4

5x1+ 7x2+ 3x3+ 4x414

x i2 f0;1gi= 1;:::;4: ???f(x) g i(x)0i2I x2SIRn:

L(x;) =f(x) +X

i2I igi(x)

L(x;)L(x;)80

L(x;)L(x;)8x2S:

??L(x;) =Minx2SfL(x;)g ???gi(x)0?8i2I? igi(x) = 0?8i2I? X i2I igi(x)X i2I igi(x)80:() i0??gi(x)0???? ????i2I? ?? ??????? ???? ????? ??? ???? ???? ????0?L(x;) =f(x)+P i2Iigi(x)f(x)? ?? ????? ??? ????? ????? igi(x) = 0?8i2I? ?? ??????? ???L(x;) =f(x)?

0? ?????x??? ?? ??????? ?????? ???? ?? ????

f(x) +X i2I igi(x)f(x) +X i2I igi(x) f(x)f(x) +X i2I igi(x) x2S?2 w() = infx2SfL(x;)g 80: w() = minx2SfL(x;)g 80: ???w()( =???f???x2SL(x;)g) IRm+: ???? ????0?w()w()f(x)? i2Iigi(x)? ???? ????x2S? ?????g(x)0???? ????x2S?w()f(x)? w() =f(x) +X i2I igi(x): w(1)f(x) +X i2I

1igi(x)??w(2)f(x) +X

i2I

2igi(x)

tw(1) + (1t)w(2)f(x) +X i2I t1i+ (1t)2igi(x) tw(1) + (1t)w(2)f(x) +X i2I igi(x) =w(): 2 ??????? ??? ??????? ?? ???? ??????? ??S=f0;1g3 ???f(x) = 103x12x2x3

2x1+ 3x2+ 4x34

x= (x1;x2;x3)2 f0;1g3: y

5= (0;0;1)?y6= (1;0;1)?y7= (0;1;1)??y8= (1;1;1)? ????? ?????? ?? ?????? ???

?????yi??S????? ????? L(yi;) =f(yi) +g(yi) = 103yi12yi2yi3+ (2yi1+ 3yi2+ 4yi34)82IR+;

L(y1;) = 10482IR+; L(y5;) = 982IR+?

L(y2;) = 7282IR+; L(y6;) = 6 + 282IR+?

L(y3;) = 882IR+; L(y7;) = 7 + 382IR+?

L(y4;) = 5 +82IR+; L(y8;) = 4 + 582IR+:

??w() =173 ;0)??? ?????f(xR) =173 ???f(x) g i(x)0i2I x2SIRn: (P)???cTx Axb xd x2INn: (PR)???cTx Axb Cxd x2IRn?? (DL)MaxMinx2SfL(x;)g ????S=fx2INnjCxdg: (P0)???cTx Axb x2conv(S): w() =MinKk=1cTxk+T(Axkb): (PL)???z zcTxk+T(Axkb)8k2 f1;:::;Kg 2IRm+ z2IR: (DPL)??? PK i=1(cTxk)ukPK i=1(Axk)ukbPk i=1uk= 1 u k2IR+8k2 f1;:::;Kg: zmX i=1 i(Aixkbi)cTxk KX k=1(Aixkbi)uk0 i:e: KX k=1Aquotesdbs_dbs16.pdfusesText_22