[PDF] Programmation linéaire. Méthode du simplexe.

View - Download Programmation linéaire. Méthode du simplexe.

Previous PDF

Next PDF

Programmation lin´eaire.

M´ethode du simplexe.

S. EL BERNOUSSI

25 octobre 2010

Table des mati`eres

1Introduction. 2

2Notion de programme lin´eaire.2

2.1Exemple.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.2Forme g´en´erale d"un programme lin´eaire.. . . . . . . . . 3

2.3Formes matricielles classiques et convensions.. . . . . . . 3

2.4Interpr´etation ´economique.. . . . . . . . . . . . . . . . . . . 3

3R´esolution graphique.4

4Principes de la r´esolution alg´ebrique.4

4.1Bases , solutions de bases et solutions r´ealisables.. . . . 4

4.2Caract´erisation alg´ebrique des points extˆemes.. . . . . . 6

4.3 Propri´et´es fondamentales de la programmation lin´eaire. . . . . . 7

4.4 Op´eration de pivotage. . . . . . . . . . . . . . . . . . . . . . . . . 8

4.5 Algorithme du simplexe `a la main. . . . . . . . . . . . . . . . . . 8

5 Algorithme du simplexe . 8

5.1 Algorithme du simplexe. . . . . . . . . . . . . . . . . . . . . . . 9

5.1.1 Probl`emes soulev´es par la d´eg´en´er´escence. . . . . . . . . 10

5.2 Complexit´e de l"algorithme et ´efficacit´e pratique. . . . . . . . . . 10

6 Exercices 11

1

1Introduction.

programmation lin´eaire est le domaine qui a eu le plus de succ´e en opti- misation. Depuis sa formulation de 1930 `a 1940, et le d´eveloppement de la m´ethode de simplexe par Danzig en 1940, des chercheurs dans diff´erents do- maines : ´economie, finance, ing´enerie etc..., ont ´et´e amen´e `a formuler et `a

r´esoudre des probl`emes lin´eaires, et mˆeme quand le probl`eme ´etait non lin´eaire,

il ´etait mod´elis´e sous forme lin´eaire, car les mod`eles non lin´eaires n´ec´essitent

des algorithmes plus ´elabor´es et plus couteux. La publication en 1984 du papier de Karmarkar est probablement l"´ev´enement le plus significatif en programmation lin´eaire apr`es la d´ecouverte de la m´ethode du simplexe. L"int´errˆet du travail de Karmarkar vient de la complexit´e po- lynˆomiale de son algorithme, ce travail a donn´e naissance aux m´ethodes de points int´erieurs, qui restent jusqu"`a pr´esent un domaine de recherche tr`es actif.

2Notion de programme lin´eaire.

Un programme lin´eaire est la maximisation ou la minimisation d"une fonction lin´eaire sous des contraintes lin´eaires.

2.1 Exemple.

Voici un petit exemple traitable par la programmation lin´eaire. Une usine produit deux ciments, rapportant 500Dhet 700Dhpar tonne.

Une tonne du ciment N

◦1 nec´essite 40min de calcination dans un four `a chaux et 20min de broyage.

Une tonne du ciment N

◦2 nec´essite 30min de calcination dans un four `a chaux et 30min de broyage. Le four et l"atelier de broyage sont disponibles 6het 8hpar jour. Combien de ciment de chaque type peut-on produire par jour pour maximiser le b´en´efice?

Ce probl`eme se mod´elise comme suit :

??Max z= 500x1+ 700x2(1) x

1≥0, x2≥0 (4)

(1) : est le profit total qui est `a optimiser appel´e fonction objective. (2) et (3) sont des contraintes. (2) est la disponibilit´e du four et (3) est la disponibilit´e du broyeur. (4) est le domaine des variables. 2

2.2 Forme g´en´erale d"un programme lin´eaire.

????(1) max ou min n? j=1c jxj (2)?i= 1,...,m:n? j=1a (3)?j= 1,...,n xj≥0 (1) : fonction objective. (2) :mcontraintes lin´eaires. (3) : contraintes de positivit´e.

2.3 Formes matricielles classiques et convensions.

Notons parx= (x1,x2,...,xn)Tle vecteur des variables.b= (b1,b2,...,bm)T le second membre des contraintes,c= (c1,c2,...,cn)Tle vecteur cˆout ou profit associ´e aux variables etAla matricem×ndesaij.???? ??Forme canonique : maxz=cx x≥0.,? ??Forme standard : maxz=cx Ax=b x≥0. graphique, et la forme standard avec des contraintes ´egalit´e s"utilise dans la r´esolution alg´ebrique. Remarque 1Ces formes ne servent qu"`a simplifier les repr´esentations th´eoriques. Dans la r´ealit´e un probl`eme lin´eaire peut comporter des contraintes ´egalit´ees ou in´egalit´ees. Ainsi n j=1a ijxj=bi??? ??n j=1a n? j=1a et n? j=1a j=1a ijxj+ei???? variable d"´ecart.=bi maxz=-min-z x?R, x=x+-x-avecx+et x-?R+.

2.4 Interpr´etation ´economique.

Un programme lin´eaire a une int´erpr´etation ´economique tr`es large : Un acteur´economique qui exercenactivit´es avec des intensit´esxj`a d´et´erminer. Ces activit´es utilisentmresources. La quantit´eaijde resourcesin´ecessaires 3 pour exerser l"activit´ejavec une intensit´e 1.On connait le profit (en maximisa- tion) et le cˆout (en minimisation).cjcorrespond `a une intensit´e 1 de l"activit´e j.

3R´esolution graphique.

On r´esoud graphiquement le probl`eme suivant : maxz=x1+ 2x2 x x x

1,x2≥0

matriciellement on am= 2, n= 2, c= (1,2), x= (x1,x2)T, b= (6,3)TetA=?1 1 0 1? (la r´esolution se fait en cours)

4Principes de la r´esolution alg´ebrique.

La r´esolution alg´ebrique utilise la forme standard, o`uAest une matricem×n de rangm. (P)? ?maxz=cx Ax=b x≥0

4.1 Bases , solutions de bases et solutions r´ealisables.

Les bases deAsont les matricesm×minversibles extraites deA. SoitBune base deA.On partitionneAsous la forme suivante :A= [B N] ( on suppose pour faciliter la pr´esentation que les colonnes de bases sont lesm premi`eres colonnes), on partitionne de mˆeme les vecteursxetc. x= (xB,xN)T etc= (cB,cN)T. Ax=b ??BxB+NxN=b ??xB=B-1b-B-1NxN. z=cx=cBxB+cNxN =cBB-1b+?cN-cBB-1N?xN. 4

On notec

N=cN-cBB-1N.

Le probl`eme (P) s"´ecrit alors sous la forme : (P?)? ?maxz=cBB-1b+c NxN x

B=B-1b-B-1NxN

x

B,xN≥0

C"est la forme canonique par rapport `a la baseB.

x ?est dite solution de basesi elle v´erifieAx?=betx?=?xB=B-1b x N= 0? Si en plusxB≥0 alorsx?est une solution de base r´ealisable. x ?est dite solution r´ealisablesi elle v´erifie les contraintes c"est `a direAx?= betx?≥0. 5 Exemple 2D´eterminer les bases et les bases r´ealisables du syst`eme suivant : x

1+x2+x3= 6

x

2+x4= 3

x

1,x2,x3,x4≥0

A= ?1 1 1 0

0 1 0 1?

1.B1=?A1A2?=?1 1

0 1? =?xB1=B-11b=?1-1 0 1?

×?6

3? =?3 3? ≥0. B

1est une base r´ealisable.

B

2=?A1A3?=?1 1

0 0? =?detB2= 0. B

2n"est pas une base.

B

3=?A1A4?=?1 0

0 1? =?xB3=B-13b=?6 3? ≥0. B

3est une base r´ealisable.

B

4=?A2A3?=?1 1

1 0? =?xB4=B-14b=?3 3? ≥0. B4est une base r´ealisable. B

5=?A2A4?=?1 0

1 1? =?xB5=B-15b=?6 -3? ?0. B

3n"est pas une base r´ealisable.

B

6=?A3A4?=?1 0

0 1? =?xB6=B-16b=?6 3? ≥0. B

6est une base r´ealisable.

4.2 Caract´erisation alg´ebrique des points extˆemes.

D´efinition 3Un ensembleXest convexe si :?x,y?Xet?α,β?[0,1] avecα+β= 1;on aαx+βy?X. D´efinition 4Une combinaison lin´eaire d"´el´ements deX(?n

1λixi) est dite

convexe si?n

1λi= 1etλi≥0.

6 NotonsX={x|Ax=b,x≥0},l"ensemble des solutions r´ealisables de (P).

Cet ensemble est convexe.

D´efinition 5* L"ensembleXest appel´e un polytope convexe.

* Un polytope born´e est un poly`edre convexe.* Un point extrˆemed"un polytope ou d"un poly`edre convexeX,est un point

qui ne peut ˆetre exprim´e comme combinaison convexe d"autres points deX. * On app`ele support dex, l"enseble des indices des composantes non nulles.

On le notesupp(x).

Th´eor`eme 6L"ensemble des points extrˆemes du polytopeX, correspond `a l"en- semble des solutions de base r´ealisables.

Th´eor`eme 7Sic

est solution optimale du programme lin´eaire(P). ( Voir la d´emonstration en cours) Exemple 8d´eterminer les bases optimales du probl`eme suivant : maxz=x1+ 2x2 x

1+x2+x3= 6

x

2+x4= 3

x

1,x2,x3,x4≥0

nous avons d´eja v´erifi´e queB1,B3,B4,B6etaient r´ealisables pour v´erifier l"optimalit´e nous allons calculer lec

Nassoci´e.

B 1:c

N=cN-cBB-1N

= (0 0)-(1 2)?1-1 0 1?? 1 0 0 1? =-(1 1)<0. .B1est optimale,z?=cBB-1b= 9. B 3:c

N= (1-1).B3est non optimale, etz?= 6.

B 4:c

N= (1-2).B4est non optimale, etz?= 6.

B 6:c

N= (1 2).B6est non optimale, etz?= 0.

D"o`u la seule base optimale estB1, la solution optimale correspondante est x ((3 3 0 0)

4.3 Propri´et´es fondamentales de la programmation lin´eaire.

Proposition 9Si une fonction lin´eaire atteint son maximum (ou minimum) sur le polytopeXalors cet optimum a lieu en un sommet deX(point extˆeme de X). 7 Proposition 10SiX?=∅,il existe au moins un sommet (point extˆeme). Remarque 11- Pour100contraintes de400variables choisir100colonnes parmis400est de l"ordre de100100sommets. - L"algorithme du simplexe empreinte un chemin astusieu de fa¸con `a maxi- miser le profit.

4.4 Op´eration de pivotage.

tels queAsr?= 0.La matriceDd´efinie par : D j i=( (((1sij=i,j?=r 1A srsij=i=r As iA srsij=r,i?=r

0sinon

est appel´ee matrice de pivotage sur l"´el´ementAsrdeA. Th´eor`eme 13Si on applique l"op´eration de pivotage `a la matrice(A,b)du syst`emeAx=b,on obtient la matrice(DA,Db).Le syst`emeDAx=Dbest

´equivalent `aAx=b.

4.5 Algorithme du simplexe `a la main.

??max z =x1+ 2x2 x

1+x2+x3= 6

x

2+x4= 3

x

1,x2,x3,x4≥0

l"algorithme consiste `a construire une suite de bases r´ealisables, de profit croissant jusqu"`a ce qu"il n"y ait plus de gain possible. (voir cours pour l"exemple)

5 Algorithme du simplexe .

Th´eor`eme 14Etant donn´e un programme lin´eaire (PP)? Ax=b x≥0 o`uAest une matricem×nde rangm.(PP)est ´ecri sous forme canonique par rapport `a une baseB. 8 optimale de(PP).

2. S"il existesune colonne deA:As/?B,aveccs>0etI={i:Asi>0}=

∅alors(PP)n"a pas de solution optimale.

3. S"il existesune colonne deA:As/?B,aveccs>0etI={i:Asi>0} ?=

∅.Soitrtel quebrA sr= mini?I? b iA si? et soitxtla variable correspondant `a la r i`emeligne de base c`ad queAt=eralors on v´erifie apr`es pivotage de la matrice des co´efficients de(PP)surAsr,que la baseB?=B+{As}\{At} est r´ealisable et que le nouveau programme est ´ecrit sous forme canonique par rapport `a la nouvelle baseB?.

5.1 Algorithme du simplexe.

On dispose d"une base r´ealisableB0.

1.B0base r´ealisable du d´epart. It´erationk= 0.

2.k ? k+ 1.

3. `a l"it´erationk. SoitBla base courantex= (xB,xN) la solution de base

correspondante : calculer b=B-1b

π=cBB-1(les multiplicateurs du simplexe)c

N=cN-πN

4. sic

si?stel quec s>0 alors

5. soitAsla colonnesdeA: calculerA

s=B-1As - sinon calculer?xs=¯brA sr= min?¯biA si:A si>0?

6. soitxtla variable correspondant `a lari`emeligne de la base, c`ad telle que

B -1At=er(m-vecteur `a composantes toutes nulles sauf la composante r´egale `a 1); alors la variablesprend la valeur?xs>0 (entre en base); la variablets"annule (?xt= 0)( sort de la base) la nouvelle base r´ealisable?B= B+{As} - {At},calculer l"inverse de la nouvelle base?B-1et retourner `a (2). Remarque 15- Dans(6)on a suppos´e que?xs>0c`ad que¯br>0.Si¯br= 0 alors la nouvelle solution obtenue est la mˆeme que la pr´ec´edente, et ce sommet

est repr´esent´e par plusieurs bases r´ealisables c"est un cas de d´eg´en´er´escence. Si

(P)est ´ecrit sous forme canonique par rapport `a une base optimaleˆBalors : - Sic

˜N<0la solution de(P)est unique.

9 - Si?c s= 0, s?ˆNalors la solution n"est pas unique en g´en´erale.

On peut choisirˆxs= min?bbic

Asi:?Asi>0?

,on d´etermine ainsi un ensemble de

Th´eor`eme 16Convergence finie.

Sous l"hypoth`ese de non-d´eg´en´er´escence, l"algorithme du simplexe converge en un nombre fini d"it´erations. D´emonstration.Il suffit d"observer que le nombre de sommets est fini, et

que la croissance stricte dezinterdit de passer deux fois par le mˆeme sommet.5.1.1 Probl`emes soulev´es par la d´eg´en´er´escence.

Dans le cas de d´eg´en´er´escence o`u

¯br= 0, on a?xs=¯brA

sr= 0.Alors la valeur de la fonctionzne varie pas apr`es le changement de base (en effet z(?x) =zB+c s?xs=zB). Il est possible apr`es un certain nombre de changements de bases de retrouver une base d´eja rencontr´ee et de cycler ind´efiniment. On peut r´egler le probl`eme de plusieurs fa¸cons.

1. Par p´erturbation des donn´ees du probl`eme.

2. Par des r`egles de s´election du pivot(R.G. Bland 1977).

A chaque it´eration de l"algorithme du simplexe - parmis toutes les variables susceplibles d"entrer en base (c`ad telles quec s>0) choisir celle du plus petit indice. - parmis toutes les variables susceptibles de quitter la base (c`ad toute les variablesxrtelles queb rA sr= min{b iA si:A si>0}choisir celle du plus petit indice. Bland a montr´e que mˆeme en cas de d´eg´en´er´escence cette r`egle assure la convergence finie de la m´ethode du simplexe.

5.2 Complexit´e de l"algorithme et ´efficacit´e pratique.

L"´evaluation de la complexit´e d"un algorithme est l"´etude du nombre maximal d"op´erations ´el´ementaires qu"il n´ecessite dans le pire des cas. Kelle et Minty (1972) ont construit des probl`emes n´ec´essitant l"´examen d"un nombre de sommets croissant exponentiellement en fonction de la taille du probl`eme (contraintes et variables) la complexit´e de la m´ethode du simplexe est donc exponentielle. 10

6 Exercices

S´erie N°1

Programmation lin´eaire

Exercise 17Montrer que le probl`eme d"optimisation : (P)? ????minr.x+s.y

B.x+D.y≥f

P.x+Q.y=h

x≥0 est un programme lin´eaire. Exercise 18Consid´erons le programme lin´eaire suivant : (P)? ????minx1+ 2x2+ 3x3 xquotesdbs_dbs33.pdfusesText_39

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

[PDF] exercices recherche operationnelle

[PDF] theme astral chinois complet gratuit interpretation

[PDF] cours recherche opérationnelle methode de simplexe

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

[PDF] livre recherche opérationnelle pdf

[PDF] cours et exercices corrigés de recherche opérationnelle+pdf

[PDF] inpes

[PDF] methode boscher pdf download

[PDF] méthode boscher cahier de lecture pdf

[PDF] methode boscher en ligne

[PDF] méthode boscher gratuit

[PDF] méthode boscher cahier des sons pdf

[PDF] adjectif pour acrostiche

[PDF] recherche qualitative définition