[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.

quotesdbs_dbs33.pdfusesText_39

[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] 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