[PDF] 1 Programmation linéaire

Série 1: Programmation linéaire

1 Programmation linéaire

[PDF] Programmation linéairebdesgraupes pagesperso orange UPX MNM corr doc pdf

Exercices de Programmation Linéaire #8211; Modélisation - ISIMA

[PDF] Exercices de Programmation Linéaire Modélisation ISIMA isima ~duhamel PROGLIN exercices pdf

174 EXERCICES SUPPLÉMENTAIRES #8212; PARTIE II

[PDF] EXERCICES SUPPLÉMENTAIRES PARTIE II dmi usherb ca ~dussault RennesOptim OPTChap pdf

Série 1: Programmation linéaire

[PDF] Série Programmation linéairemath univ lyon ~noble ISFA td pdf

Introduction ? la programmation linéaire/exercices/corrigé/p1

[PDF] Introduction ? la programmation linéaire exercices corrigé p ressources aunege nuxeo site Exercices CorExercices pdf

Corrigé

[PDF] Corrigé edu gov mb ca m frpub ped ma unitedcorrige pdf

Méthodes d Optimisation - LMPA

[PDF] Méthodes d 'Optimisation LMPA lmpa univ littoral ~smoch L optimisation chap pdf

Programmation linéaire Jean-Philippe Javet

[PDF] Programmation linéaire Jean Philippe Javet gymomath ch javmath polycopie prog lin pdf

Exercices de TD - 1 Modélisation - Lirmm

[PDF] Exercices de TD Modélisation Lirmm lirmm ~bessy PL ExosPL pdf

Recueil de 100 exercices de programmation linéaire

Faculté des Sciences Département de Mathématiques Recueil de exercices de programmation linéaire En annexe des indications sur les problèmes de

[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

[PDF] livre recherche opérationnelle pdf

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

[PDF] recherche opérationnelle cours maroc

[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

UNIVERSITÉ PARIS OUEST NANTERRE LA DÉFENSE

U.F.R. SEGMI Année universitaire 2012 - 2013

Master d"économie Cours de M. Desgraupes

Méthodes Numériques

Document 4 : Corrigé des exercices d"optimisation linéaire1 Programmation linéaire 1 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Raffinerie de pétrole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Méthode des variables ajoutées . . . . . . . . . . . . . . . . . . . . . . . . 6 Indices d"octane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Fabrique de pièces détachées . . . . . . . . . . . . . . . . . . . . . . . . . 13 Plan de production de moteurs . . . . . . . . . . . . . . . . . . . . . . . . 15 Excavation et matériaux de carrière . . . . . . . . . . . . . . . . . . . . . . 17

2 Dualité 19

Main d"oeuvre et équipements . . . . . . . . . . . . . . . . . . . . . . . . 19 Trois techniques de production . . . . . . . . . . . . . . . . . . . . . . . . 21

Production en heures-machines . . . . . . . . . . . . . . . . . . . . . . . . 221 Programmation linéaire

Corrigé ex. 1 : Méthode du simplexe

Programme 1

8 >>>>>:Max(x1+ 2x2) x

1+ 3x221

x1+ 3x218 x 1x25 x

1etx20

On introduit des variables d"écart, ce qui conduit aux équations suivantes pour les contraintes du problème : 8>< :x

1+ 3x2+x3= 21

x1+ 3x2+x4= 18 x

1x2+x5= 5

Le premier tableau du simplexe s"écrit :

1 x

1x2x3x4x51 3 1 0 021x

3-1 3 0 1 018x

41 -1 0 0 15x

5-1 -2 0 0 00

La variable entrante estx2qui correspond à l"élément le plus négatif de la dernière ligne. La variable sortante se calcule en trouvant le plus petit rapport positif entre la colonne de droite et la colonne dex2(colonne entrante) : Min 213
;183 =183 = 6 Doncx4est la variable sortante. La ligne dex4sert de ligne pivot et on exécute une transformation du pivot autour de la valeur 3 (à l"intersection de la ligne dex4et de la colonne dex2).

On obtient le tableau suivant :

x

1x2x3x4x52 0 1 -1 03x

3-1/3 1 0 1/3 06x

22/3 0 0 1/3 111x

5-5/3 0 0 2/3 012

Maintenant c"estx1qui entre etx3qui sort car :

Min 32
;112=3 =32 Un nouveau pivot autour du nombre 2 (à l"intersection de la ligne dex3et de la colonne dex1) conduit au tableau suivant : x

1x2x3x4x51 0 1/2 -1/2 03/2x

10 1 1/6 1/6 013/2x

20 0 -1/3 2/3 110x

50 0 5/6 -1/6 029/2

Maintenant c"estx4qui entre etx5qui sort car :

Min

13=21=6;102=3

=102=3= 15 Un nouveau pivot autour du nombre 2/3 (à l"intersection de la ligne dex5et de la colonne dex4) conduit au tableau suivant : x

1x2x3x4x51 0 1/4 0 3/49x

10 1 1/4 0 -1/44x

20 0 -1/2 1 3/215x

40 0 3/4 0 1/417

2 Ce tableau correspond à l"optimum car il n"y a plus de termes négatifs dans la dernière ligne. On obtient donc comme solution :

8>>>>>><

>>>>>:x 1= 9 x 2= 4 x 3= 0 x 4= 15 x 5= 0 La première et la troisième contrainte sont saturées.

Programme 2

8 >>>>>:Min(x13x2)

3x12x27

x1+ 4x29

2x1+ 3x26

x

1etx20

On transforme le problème en une maximisation en changeant le signe de la fonc- tion objectif :

Max(x1+ 3x2)

On introduit ensuite les variables d"écart comme ceci : 8>>>< >>:3x12x2+x3= 7 x1+ 4x2+x4= 9

2x1+ 3x2+x5= 6

x

1etx20

Le tableau de départ pour la méthode du simplexe est donc : x

1x2x3x4x53 -2 1 0 07x

3-1 4 0 1 09x

4-2 3 0 0 16x

51 -3 0 0 00

La variable entrante estx2qui correspond à l"élément le plus négatif de la dernière ligne. La variable sortante se calcule en trouvant le plus petit rapport positif entre la colonne de droite et la colonne dex2(colonne entrante) : Min 94
;63 =63 = 2 Doncx5est la variable sortante. La ligne dex5sert de ligne pivot / on exécute une transformation du pivot autour de la valeur 3 (à l"intersection de la ligne dex5et de la colonne dex2).

Cela conduit au tableau suivant :

3 x

1x2x3x4x55/3 0 1 0 2/311x

35/3 0 0 1 -4/31x

4-2/3 1 0 0 1/32x

2-1 0 0 0 16

Cette fois la variablex1entre dans la base et la variablex4sort car : Min

115=3;15=3

=35 Le pivot se fait autour de la valeur 5/3 (à l"intersection de la ligne dex4et de la colonne dex1). On obtient alors le tableau suivant : x

1x2x3x4x50 0 1 -1 210x

31 0 0 3/5 -4/53/5x

10 1 0 2/5 -1/512/5x

20 0 0 3/5 1/533/5

Il n"y a plus de terme négatif dans la dernière ligne et on est donc à l"optimum. La solution est :

8>>>>>><

>>>>>:x

1= 3=5

x

2= 12=5

x 3= 10 x 4= 0 x 5= 0 La deuxième et la troisième contrainte sont saturées. Il ne faut pas oublier de re- changer le signe de la fonction objectif : la valeur à l"optimum est -33/5 (alors que la case inférieure droite du tableau indique 33/5 car ce tableau correspond à la maximisa- tion def).Corrigé ex. 2 : Raffinerie de pétrole On désigne parx1etx2les quantités de brut 1 et 2 qu"il faut traiter. La fonction objectif est la marge totale, qu"il faut maximiser :

Max (3x1+ 4x2)

Les contraintes de production s"expriment sous la forme suivante : 8>< :0;25x1+ 0;35x2825

0;30x1+ 0;30x2750

0;45x1+ 0;35x21065

qui se simplifient sous la forme suivante : 8>< :5x1+ 7x216500 x

1+x22500

9x1+ 7x221300

4 Si on notex3,x4,x5les variables d"écart, les contraintes deviennent : 8>< :5x1+ 7x2+x3= 16500 x

1+x2+x4= 2500

9x1+ 7x2+x5= 21300

Les tableaux du simplexe sont successivement :

Tableau 1

x

1x2x3x4x55 7 1 0 016500x

31 1 0 1 02500x

49 7 0 0 121300x

5-3 -4 0 0 00

x

2entre etx3sort.

Tableau 2

x

1x2x3x4x55/7 1 1/7 0 016500/7x

22/7 0 -1/7 1 01000/7x

quotesdbs_dbs28.pdfusesText_34