[PDF] [PDF] Programmation linéaire

[PDF] Programmation Linéaire Cours 1 : programmes linéaires

Programme linéaire Résolution graphique Points extrêmes Forme standard, bases Bilan Motivation et objectif du cours Introduction `a la programmation 

[PDF] Chapitre 4 Formes générale, canonique et standard dun probl`eme

Dans ce chapitre, nous définissons la forme générale d'un probl`eme d' optimisation linéaire, ainsi que la forme canonique et la forme standard Nous montrons 

[PDF] Programmation linéaire et Optimisation

La forme standard associée au primal (apr`es introduction des variables d'écart) aura m = 1000 contraintes pour n = p + q = 1100 inconnues L'algo- rithme du 

[PDF] Fondements de la programmation linéaire

≤ 2 En résolvant le problème de cet exemple sous sa forme standard, on obtiendrait comme solution de base réalisable optimale (2,1,0) 

[PDF] Support de cours : Introduction à la programmation linéaire - IA - LIP6

On peut toujours transformer la forme canonique en forme standard en ajoutant des variables d'écart UPEC - Master ScTIC 4 Page 6 Forme canonique maxcx

[PDF] Programmation linéaire - LaBRI

13 Programmation linéaire Interprétation géométrique Bases et points extrêmes L'algorithme du simplexe Programmation linéaire Forme standard d'un PL

[PDF] Programmation linéaire - LACIM - UQAM

Forme standard minimiser cTx sous les contraintes Ax = b A Blondin Massé ( UQAM) Chapitre 5: Programmation linéaire MAT7560 Hiver 2019 17 / 54 

[PDF] Programmation linéaire

Un problème d'optimisation linéaire sous forme standard est un problème de la forme (P LS) min Ax=b x≥0 c · x Proposition 2 3 Tout problème d'optimisation 

[PDF] Programmation linéaire

Peut-on mettre le problème suivant sous forme standard ? Minimiser : cx Sous les contraintes : Ax = b et l ≤ x ≤ u Exercice Donner une solution optimale pour  

[PDF] Chapitre I : Programmation linéaire

La méthode du simplexe nécessite la mise sous forme standard du programme linéaire à résoudre en ajoutant autant de variables d'écart qu'il y a de 

[PDF] programmation linéaire définition

[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

OPTIMISATION

LICENCEMATHÉMATIQUE ETGESTION2013-2014

Table des matières

2 Programmation linéaire 1

2.1 Optimisation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

2.2 Polytopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.3 Recherche d"un optimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.4 Algorithme du simplexe à une phase . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.5 Algorithme du simplexe à deux phases . . . . . . . . . . . . . . . . . . . . . . . .

9

2.6 Tableau du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.7 Programmation linéaire avec R . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

2.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2 Programmation linéaire

2.1 Optimisation linéaire

Définitions 2.1.-Une fonction af fine(sur Rn) est une fonction de la formex7!ax+b, aveca2Rnetb2R Un problème d"opti misationlinéaire est un problème de la forme minoumaxf(x);sous contraintesgj(x)0;hl(x)0;km(x) = 0;j= 1;:::;j1;l=

1;:::;l1;k= 1;:::;k1

Ici, toutes les fonctions qui apparaissent sont affines

Si x2Rn, la notationx0symbolisexj0,j= 1;:::;n

De mêmexyest une notation pourxjyj,j= 1;:::;n

On utilise aussix >0pourxj>0,j= 1;:::;n, etc.

Problème sous forme standard

1

Définition 2.2.Un problème d"optimisation linéaire sous forme standard est un problème de la

forme(PLS) minAx=b x0cx éventuellement au prix d"un ajout de nouvelles variables Démonstration.Pour transformer un problème en(PLS): -max min: on transformemax(cx+b)enbmin(c)x -cx+b cx: on transformemin(cx+b)enb+ mincx -xjquelconque xj0: on peut écrire un scalaire sans contrainte de signe,y2R, sous la formey=z1z2, avecz1;z20 -vx vx=: on avx()vxz=pour un scalairez0 -vx vx=: on avx()vx+z=pour un scalairez0 Dans les deux de rnierscas : z=variable d"écartExemple

Le problèmemax(x1x2+ 3)sousx1+x21,x10,

équivaut àmin(z1+z2z3)sousz1;z2;z3;z40,z1+z2z3z4= 1

Élimination des contraintes redondantes

Définitions 2.4.SoitA2Mm;n(R). La matriceAest pleine si son rang estm

Si le rang deAest< m, alorsAest déficiente

Proposition 2.5.Hypothèse :

le systèmeAx=best compatible

Conclusion :

il existe une matrice pleine~Aet un~btels que fx2Rn;Ax=bg=fx2Rn;~Ax=~bg Démonstration.-P arrécurrence s urm, le nombre de lignes deA

Le cas m= 1:

si le rang deAest1, on prend~A=Aet~b=b si le rang deAest nul, on prend~A= 0et~b= 0

P assagede m1àm:

siAest pleine, on prend~A=Aet~b=b 2 siAest déficiente, alors il existej2 f1;:::;mgtel quelj(A) =X k6=j klk(A), d"oùbj= X k6=j kbk(par compatibilité du système)

La matrice

~Aobtenue en privantAde lajeligne et le vecteur~bobtenu en privantbdebj satisfont~Ax=~b, alors que~Aa(m1)lignes. On peut donc remplacer~A(doncA) par une matrice pleineProblème linéaire encore plus standard De ce qui précède, on peut toujours supposer Apleine, c"est-à-dire rangA=m, ce qui impliquemn Si m=n, alors la solution deAx=best unique et le problème d"optimisation trivial

On supposera donc touj oursdans la suite :

-Apleine -m < n

2.2 Polytopes

Définitions 2.6.-Un polytope con vexeest un ensemble Pde points deRndéfini par un nombre fini de contraintes affines satisfaites au sens large Un polytope con vexeen forme standard est un ensemble de la forme P=fx2Rn;Ax= b;x0g, avecApleine de rangm < n -xest un sommet dePsi et seulement si :x2 Pet il n"existe pasy;z2 Pavecy6=zet x2(y;z) Une base de A(avecApleine de rangm < n) est une partieB=fj1;:::;jmg f1;:::;ng telle que les colonnes d"indicesj1;:::;jmdeAsoient libres, ce qui équivaut à : la matrice carréeBformée avec les lignes deAet les colonnes d"indicesj1;:::;jmdeAest inversible

Exemple

Le polytope ci-dessus est donné par les contraintes x

1+x21; x1x21; x1x2 1

xest un sommet,yetzne le sont pas 3 1 x=(1,0) z yExemple

Pour la matriceA=1 2 2 3

1 2 3 4

, les bases sontf1;3g,f1;4g,f2;3g,f2;4g,f3;4g SoientAune matrice pleine,Bune base deAetBla sous-matrice deAassociée àB Après permutation de colonnes, on peut identifierA(BjN) Après permutation des indices, un pointxdeRns"identifie àx(xB;xN), avecxB2Rmet x

N2Rnm, de sorte queAx=BxB+NxN

Les coordonnées dexBsont les coordonnées en base, les coordonnées dexNsont les coordonnées

hors base Sij2 B, alorsjest une variable en base; sij62 B, alorsjest une variable hors base

Exemple

SoientA=1 2 2 3 3

1 2 3 4 4

etB=f1;3g

AlorsB=1 2

1 3 ,N=2 3 3 2 4 4 ,xB= (x1;x3),xN= (x2;x4;x5) Les coordonnéesx1;x3sont en base, les coordonnéesx2;x4;x5sont hors base Les variables1et3sont en base, les variables2;4et5sont hors base Définitions 2.7.SoientAune matrice pleine,Bune base deAetA(BjN)la décomposition deAassociée àB La solution de base assoc iéeà Bet au systèmeAx=bestx(xB;0), avecxBla seule solution deBxB=b. On désigne aussi cetxparxB Ou encore : c"est l"unique solution deAx=btelle quexN= 0 La solution de bas exest admissible si et seulement sixB0, ce qui équivaut àx2 P La base Best admissible si et seulement sixBest admissible Théorème 2.8.SoitP=fx2Rn;Ax=b;x0gun polytope convexe en forme standard (doncAest pleine) Alorsxsommet deP ()xsolution de base admissible pour une certaine baseBdeA 4 Solution de base implique sommet.Siy;z2 Pett2]0;1[sont tels quex= (1t)y+tz, alors (1)xB= (1t)yB+tzBet (2)xN= (1t)yN+tzN

De (2) etyN;zN0, on ayN=zN= 0

DeAx=Ay=Az=b, on aBxB=ByB=BzB=b, d"oùxB=yB=zB, ce qui implique x=y=zSommet implique solution de base.Après permutation,A(CjM), avecxC>0etxM= 0 Soitwsolution deCw= 0. Pour" >0petit, on axC"w >0etx= 1=2y+ 1=2z, avec y(xC"w;0),z(xC+"w;0). Commey;z2 P, on doit avoiry=z, d"oùw= 0

Il s"ensuit queCest injective, c"est-à-dire les colonnes deCsont libres. On peut compléterCà

une matrice carréeB, extraite deAet de même rang que celui deA.Bcorrespond alors à une base BdeA

AvecA(BjN), on axN= 0, d"oùxest la solution de base associée àBAu passage, nous avons établi le résultat suivant

Corollaire 2.9.Soitx2 P. SoitCla sous matrice deAcorrespondant aux coordonnée strictement positives deA, c"est-à-dire :A(CjM)etx(xC;xM), avecxC>0etxM= 0

Hypothèse :

Cest injective, ou encore l"équationCw= 0n"a que la solutionw= 0, ou encore les colonnes de

Csont libres

Conclusion :

xest un sommet

Par ailleurs, la réciproque est vraie

2.3 Recherche d"un optimum

Théorème 2.10.On considère le(PLS) minAx=b x0cx

Hypothèse :

il existe une solutionxdu(PLS)

Conclusion :

il existe une solutionydu(PLS)qui soit, de plus, un sommet deP Démonstration.On considère, parmi toutes les solutionsz2 Pdu(PLS), une,y, qui a le moins de coordonnées strictement positives. SoitA(CjM),y(yC;yM), avecyC>0etyM= 0 Soitwsolution deCw= 0. D"abord, on acCw= 0(1). En effet, siz(yC"w;0), alorsz est admissible pour"petit. Commeyest optimal, on trouve"cCw0, d"oùcCw= 0 On montre ensuite quew= 0(d"oùysommet). Preuve par l"absurde : siw6= 0, on peut supposer, par exemple,w1>0. Soit":= minwj>0xj=wj>0 Soitz"(w;0)et soitx:=yz. Alors :x0,xM= 0etxC6>0. Par ailleurs,Ax= Cx C+MxM=AyCz=Ay=b. Doncxest une solution du(PLS)ayant moins de 5

coordonnées strictement positives quey. Par ailleurs, on a aussicx=cy(grâce à (1)), d"oùx

optimal. Contradiction!Recherche naïve d"un optimum

Algorithme

Hypothèse :

il existe une solution du(PLS)

Pour en trouver une :

On initialis ez=1

On considère tout esles parties de mélémentsB f1;:::;ng On vérifie si la matrice Bassociée àBest inversible Sinon, on passe au Bsuivant. Si oui, on calculexB:=B1b Si xB60, on passe auBsuivant. Sinon, on remplacezparminfz;cBxBg, oùc(cB;cN)

À la fin, zest le minimum du(PLS)

Inconvénients

Nombre prohibitif de calculs : CmnpartiesBà regarder, résolution deBxB=bpour chaque base On peut obtenir un zfini même si l"infimum du(PLS)vaut1

Exemples

Pour le problème (PLS) minx

1=1 x

1;x20(x1x2), on az= 1alors que l"infimum est1

Pour un problème a vec100inconnues et 10 contraintes, il faut regarderC10100familles de vecteurs deR10. Le nombre de familles est à douze chiffres

2.4 Algorithme du simplexe à une phase

Calcul de base

Soient Bune base admissible,Bla matrice associée,A(BjN), etx(xB;xN)un point deP

Alors xB=B1(bNxN)(carAx=b)

On a donc

cx=cTx=cTBB1b+ (cTNcTBB1N)xN

Définition 2.11.Le vecteurc

N:= (cTNcTBB1N)T=cNNT(B1)TcBest le vecteur des coûts réduits (associé à la baseB)

Étape#0

On part d"une base admissibleB

6

Étape#1

Sic N0, STOP :x(B1b;0)est solution optimale etz=cTBB1best le minimum du(PLS)

Démonstration.Six2 P, alorscx=cTx=cBB1b+c

NxNcBB1b, carxN0etc

N0

Le minimum est atteint quandxN= 0, ce qui donnex(B1b;0)Numérotation des coordonnées : un exemple

Sin= 5,m= 2etB=f1;3g, alors les coordonnées dec

Nont comme indices2;4et5

Nsontappeléesdeuxième,

quatrième et cinquième coordonnée

Étape#2

Sic

N60, soitcila première coordonnée<0dec

Net soitison rang

Soit aussivilaiecolonne deB1A(par abus de langage,viest appelée laiecolonne deB1N)

Étape#3

Sivi0, STOP : l"inf du(PLS)est1et n"est pas atteint Démonstration.Pour simplifier les notations, on supposeB=f1;:::;mg,i=m+ 1 Soitf= (1;0;:::;0)2Rnm. Soitt0. On posexN=tf0etxB=B1bB1N tf= B

1bB1N tf=B1btvi0. Soitx(xB;xN)2 P

On acx=cTBB1b+t(cTNB1N)f=cTBB1b+tci! 1quandt! 1Numérotation des coordonnées : un exemple Le colonnes deB1AouB1Nontmcoordonnées. On numérote ces coordonnées selon les indices qui donnentB Exemple : siB=f1;3;4get une colonne deB1Nestd= (2;4;3)T, alors2est la coordonnée de rang 1,4de rang3et3de rang4. Doncd= (d1;d3;d4)T Même numérotation pour les coordonnées deB1b

Étape#4

Sivi60, soitJ:=fk2 B;vik>0g 6=;

On posetk=(B1b)kv

ik,8k2 J

On choisit le plus petitjtel quetj= mink2Jtk

On remplaceBpar~B:=B n fjg [ fig

Rappel

Lemme 2.12(de substitution).SoitF= (ek)k2Iune famille libre dans un espace vectorielV. Soit f2V,f=X k kfk. Sii6= 0, alorsF n ffig [ ffgest encore une famille libre Proposition 2.13(L"étape#4diminue le coût).~Best une base admissible etcx~BcxB 7

Best une base.On désigne parAkles colonnes deA

Il faut montrer que la famillefAk;k2 Bg n fAjg [ fAigest libre

AvecT:= (k)k2B, on a

A i=X k2B kAk()Ai=B()=B1Ai=vi Commevij>0, la conclusion suit du lemme de substitution~ Best une base admissible.On peut supposerB=f1;:::;mgeti=m+ 1 Avec des notations déjà utilisées, soientxN=tjf,xB=B1bB1NxN, de sorte quex (xB;xN)vérifieAx=b,xm+10etxk= 0sikm+ 2 Pour conclure, il suffit de montrer quexk0,k= 1;:::;metxj= 0

Pourk= 1;:::;m, on axk= (B1b)ktjvik0. Par choix dej, on axj= 0Corollaire 2.14.Dans la baseB, on ax~B(B1btjvi;tjf)

Le coût diminue en passant deBà~B.Dans la baseBon ax~B(B1btjvi;tjf), de sorte que cx~B=cTBB1b+tj(cTNfcTB(B1N)i)

SiB1b >0, alorstj>0pour toutj2 J

Définition 2.15.Une baseBest non dégénérée siB1b >0 Théorème 2.16(non dégénérescence=)convergence).Hypothèse : Les bases admissibles sont non dégénérées

Conclusion :

L"algorithme du simplexe donne en un nombre fini d"itérations la solution du(PLS)

Démonstration.Si on passe par l"étape#4, on trouvecx~B< cxB=)le coût décroît strictement

=)on ne passe pas deux fois par la même base=)le nombre d"étapes est fini=)on s"arrête à

une étape type#1ou#2 =)on trouve la solution du(PLS)Théorème2.17(Bland1977;admis).L"algorithmedusimplexedonne,enunnombrefinid"étapes,

la solution optimale du(PLS)

Voir une preuve à l"adresse

http ://www.cmi.univ-mrs.fr/lugiez/Enseignement/Master1/RO/Cours/cours3.pdf pages6et7 L"argument essentiel est : si on passe plusieurs fois par une étape du type#4, alors les basesB correspondantes sont différentes (l"algorithme ne cycle pas)

Algorithme du simplexe à une phase

Entrées :

8 -un (PLS) une base admiss ible

Sorties :

le coût optimal zdu(PLS) si z >1, une solution optimalexB

Corollaire 2.18.Si le coût optimal d"un problème de programmation linéaire n"est pas1, alors

il existe une solution optimale

Inconvénient du simplexe à une phase : suppose connue une base admissible, qui peut être difficile

à trouver dans la pratique

Un cas particulier où il y a une base admissible "toute faite" est le(PL) minAxb x0cx, avec -A2Mm;n(R) -b2Rm,b0

Comment obtenir une base admissible pour(PL):

on introduitlesvariablesd"écartxj,j=n+1;:::;n+m,desortequeAx+(xn+1;:::;xn+m)T= b alors fn+ 1;:::;n+mgest une base admissible

2.5 Algorithme du simplexe à deux phases

Phase#0

Entrée :

Un(PLS)

Sortie :

si P=;, l"informationP=; si P 6=;, une base admissibleB

Phase#1: celle du simplexe à une phase

Entrées :

un (PLS) une base admiss ible

Sorties :

le coût optima lzdu(PLS) si z >1, une solution optimalexB

Simplexe à deux phases : phase#0

Étape#1

On transformeA ~A,b ~bde sorte que~b0

9 Pour ce faire, sibj0, alors on ne modifie nibj, nilj(A). Sibj<0, alors on remplacebjparbj etlj(A)parlj(A)

Cette étape ne change pas le rang deA

Ainsi, il suffit de traiter la phase#0sous les hypothèses : -Apleine, rangA < n -b0

Étape#2

On résout, avec l"algorithme du simplexe à une phase, le problème auxiliaire (en forme standard)

(PA) minAx+y=b x0;y0(y1+:::+ym); problème : de v ariableX= (x1;:::;xn;y1;:::;ym)(X1;:::;Xm+n) de matrice (AjIm), qui est pleine de base admissible B=fn+ 1;:::;n+mg, qui donne la solution de base admissible X(0;b)(c"est ici que la première étape sert) Pour le problème(PA), le coût est toujours0. Il s"ensuit qu"il existe toujours une solution optimale de base, associée à une baseB, et donnant le coût optimalz0de(PA)

Étape#3

Siz0>0, STOP : on aP=;. Les contraintes du(PLS)sont incompatibles Démonstration.Par l"absurde. Six2 P, alorsX(x;0)est admissible pour(PA)et le coût associé àX(x;0)est nul. Contradiction avecz0>0Étape#4

Siz0= 0, alorsP 6=;

Démonstration.SoitX(x;y)une solution optimale. On a alors : -y= 0 -Ax=b -x0Étape#5 On écrit(AjIm)(C DjE F), avec les sous-matrices choisies de sorte que la solution optimale de base de(PA)s"écriveX(xC;xD;yE;yF), avecxC>0, etyEen base, alors quexDetyF sont hors base

Alors les colonnes deCsont libres

On complèteCà une sous-matriceB(CjG)deA, carrée et de rangm. Les indices des colonnes deBforment une base admissibleBdeA, car siA(CjGjN), alorsxB(xC;0;0) 10 Comment compléterC: nous le verrons dans la section "tableau du simplexe" On est à la fin de la phase#0: on dispose d"une base admissibleBpour le(PLS)

2.6 Tableau du simplexe

Pour le calculer, il faut :

un (PLS) une base admiss ibleB, de matrice associéeB

Le tableau du simplexe estB

1AB 1bc

TcTBB1Aw

avecw=cTBxB(doncwest l"opposé du coût estimé en la solution admissible de base corres- pondant àB) C"est un tableau à(m+ 1)-lignes et(n+ 1)-colonnes Après permutation éventuelle des colonnes, on aA(BjN),c(cB;cN), et le tableau devientI mB1NB

1b0cTNcTBB1Nw

Proposition 2.19(Pivotage du tableau).Quand on passe de la baseBà une nouvelle base~B= B n fijg [ fig(avecij2 Beti62 B), le tableau du simplexe change de la façon suivante : on fait un pivot de Gauss par dans la i ecolonne, en prenant comme pivot(B1A)ij

Plus spécifiquement, si(tlk)l=1;:::;n+1

k=1;:::;m+1sont les éléments du tableau correspondant à la baseBet si l k,k= 1;:::;m+1sont les lignes de ce même tableau, alors on obtient les nouvelles lignes~lkde la manière suivante : -~lj=lj=tij pour k6=j,~lk=lktikt ijlj

Pratique du simplexe à une phase

Étape#1

On regarde le vecteur lignecTNcTBB1N(c"est la partie hors base de la dernière ligne du tableau) 11 -Si toutes ses coordonnées sont 0, STOP : la baseBest optimale, la solution optimale est x

B(B1b;0), le coût optimal estw

Sinon, on passe à l "étape#2

Étape#2

On trouve le premieritel que laiecoordonnée decTNcTBB1Nsoit<0

On passe à l"étape#3

Étape#3

Soitvilaiecolonne deB1A

quotesdbs_dbs6.pdfusesText_11