1 Programmation linéaire

Exercices de Programmation Lin´eaire – Simplexe Primal – exercice 1 : R´esoudre le programme lin´eaire suivant par la m´ethode du simplexe Max z =5x1+6x2+9x3+8x4 s c x1+2x2+3x3+ x465 x1+ x2+2x3+3x463 x1, x2, x3, x4>0 – en faisant entrer en base la variable hors base dont le couˆt r´eduit est le plus grand

174 EXERCICES SUPPLÉMENTAIRES — PARTIE II

180 CHAPITRE 4 PROGRAMMATION LINÉAIRE Introduction La programmation linéaire constitue l’origine de l’optimisation mathématique moderne Son étude a été menée par George Bernard Dantzig à partir de 1947 L’algorithme du sim-plexe, que nous présentons dans ce chapitre, est considéré comme un des dix algorithmes les

Programmation linéaire

la programmation linéaire Nous étudierons 3 méthodes pour résoudre les diﬀérents types de problèmes de programmation linéaire; la première est basée sur une résolution graphique, elle est donc limitée à 2 ou 3 variables La deuxième méthode est plus algébrique et elle justiﬁera la troisième qui porte le nom de

1 Programmation linéaire

1 Programmation linéaire Corrigé ex 1 : Méthode du simplexe Programme 1 8 >> >> >> < >> >> >>: Max(x 1 + 2x 2) x 1 + 3 2 21 x 1 + 3x 2 18 x 1 2 5 x 1 et x 2 0 On introduit des variables d’écart, ce qui conduit aux équations suivantes pour les contraintes du problème : 8 >< >: x 1 + 3 2 + 3 = 21 x 1 + 3x 2 + x 4 = 18 x 1 x 2 + x 5 = 5

Programmation lin eaire et Optimisation

Programmation lin eaire et Optimisation Didier Smets Chapitre 1 Un probl eme d’optimisation lin eaire en dimension 2 On consid ere le cas d’un fabricant d

CORRIGE du TD N°1 : PROGRAMMATION LINÉAIRE

CORRIGE du TD N°1 : PROGRAMMATION LINÉAIRE EXERCICE 1 : corrigé 1- Modélisation sous forme de programme linéaire Désignons par et les nombres d’articles de chaque type (poterie, émaux sur cuivre) produits et par Z, le bénéfice généré par cette fabrication et sont les variables de décision du modèle

Programmation Lin aire Cours 1 : programmes lin aires, mod

•C Gu´eret, C Prins et M Sevaux - Programmation lin´eaire : 65 probl`emes d’optimisation mod´elis´es et r´esolus avec Visual Xpress, Eyrolles, 2000 •C Prins et M Sevaux - Programmation lin´eaire avec Excel : 55 probl`emes d’optimisation mod´elis´es pas `a pas et r´esolus avec Excel, Eyrolles, 2011

Chapitre : PROGRAMMATION LINÉAIRE 1ere ES

Chapitre : PROGRAMMATION LINÉAIRE 1ere ES Exercice4 Dans un centre de loisirs, il est possible de prendre une carte d’abonnement annuelle de 140 e, commune à la disco-thèque et au cinéma A la discothèque, l’entrée sans réduction est de 15 eet l’abonnement donne droit à une réduction de 40

Exercices 1 Programmes lin eaires - imag

Exercices 1 Programmes lin eaires Mod elisation et g eom etrie Exercice 1 Votre r egime alimentaire exige que tous les aliments que vous mangez proviennent de l’un des quatre \groupes d’aliments de base" (g^ateau au chocolat, cr eme glac ee, soda et chee-secake)

MHT 423: Mod elisation et optimisation - u-bordeauxfr

Programmation en nombres entiers mixtes et relaxations Le deuxi eme fait veut dire que, malheureusement, la programmation en nombres entiers est plus di cil (m^eme beaucoup plus di cil) que la programmation lin eaire Le premier veut dire qu’on peut n eanmoins d e nir des m ethodes de r esolution pour les programmes en nombres entiers qui

[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

[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

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 :

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

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

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

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

1x2x3x4x55 7 1 0 016500x

31 1 0 1 02500x

49 7 0 0 121300x

5-3 -4 0 0 00

2entre etx3sort.

Tableau 2

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

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

44 0 -1 0 14800x

5-1/7 0 4/7 0 066000/7

1entre etx4sort.

Tableau 3

1x2x3x4x50 1 1/2 -5/2 02000x

21 0 -1/2 7/2 0500x

10 0 1 -14 12800x

50 0 1/2 1/2 09500

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= 500

2= 2000

x 3= 0 x 4= 0 x

5= 2800

La valeur à l"optimum estf= 9500. La première et le deuxième contrainte sont saturées : les quotas imposés pour l"essence et le gasoil sont atteints. La troisième

présente un écart de 140 (le tableau indique 2800 mais cette contrainte avait été divisée

par 20 avant d"être insérée dans le tableau) : cela signifie que le quota de 1065 imposé sur le fuel n"est pas atteint et qu"on fabrique seulement1065140 = 925milliers de m

3de fuel.

5 Corrigé ex. 3 : Méthode des variables ajoutées Les deux programmes d"optimisation de cet exercice présentent une difficulté sup- plémentaire pour appliquer la méthode du simplexe : on ne peut pas démarrer le sim-

plexe à partir de l"origine (c"est-à-dire à partir du point de coordonnées nulles) car ce

point ne vérifie pas les contraintes. L"origine ne fait pas partie du domaine réalisable. Il faut donc trouver un point de départ dans le domaine réalisable, autrement dit trouver un pointà coordonnées positivesqui vérifie les équations des contraintes. On utilise pour cela la méthode des variables ajoutées. Elle consiste à introduire des va- riables supplémentairesx1;a;x2;a;:::dans les contraintes et à chercher à les annuler. Comme ce sont des variables positives, il suffit d"annuler leur somme et on en fait un problème d"optimisation en fixant comme objectif de minimiser cette somme : Min X jx j;a Il y a autant de variables ajoutées qu"il y a de contraintes.

Programme 1

8 >>>:Max(x1x2+x3)

3x1+ 2x2+x3= 1

1x2x3+x4= 3

1+ 4x2+ 2x32x4= 1

1;x2;x3etx40

On introduit 3 variables positivesx1;a;x2;a;x3;adans les contraintes et on cherche à minimiser la fonction objectifx1;a+x2;a+x3;a. On se ramène à un problème de maximisation en changeant le signe de cette fonction objectif. Le problème s"écrit donc sous la forme suivante

Max(x1;ax2;ax3;a)8<

:3x1+2x2+x3+x1;a= 1 x

1x2x3+x4+x2;a= 3

1+4x2+2x32x4+x3;a= 1

avec les contraintes x

1;x2;x3;x4;x1;a;x2;a;x3;a0

La fonction objectiveinitiale duproblème estpour lemoment ignorée. Leproblème avec les variables ajoutées peut se traiter au moyen de la méthode du simplexe ordi- naire. La configuration de départ consiste à annuler les variablesx1;x2;x3;x4qui sont ainsi des variables hors-base. Les variables de base sont donc au départ : 8>< :x

1;a= 1

2;a= 3

3;a= 1

Très important :il faut veiller à ce que la fonction objectif (x1;ax2;ax3;a) soit exprimée en fonction des variables hors-base. C"est une règle qui doit toujours être vérifiée : 6 À tous les stades de la méthode du simplexe, la fonction objectif et les variables de base doivent être exprimées en fonction des variables hors-base. et les remplacer dans la fonction objectif. On a : 8< :x

1;a= 1 + 3x12x2x3

2;a= 3x1+x2+x3x4

3;a= 1x14x22x3+ 2x4

D"où

x1;ax2;ax3;a=5x1+ 5x2+ 2x3x4 À partir de là, la méthode du simplexe s"applique sans problèmes.

Tableau 1

1x2x3x4x1;ax1;ax3;a-3 2 1 0 1 0 01x

1;a1 -1 -1 1 0 1 03x

2;a1 4 2 -2 0 0 11x

3;a1 -5 -2 1 0 0 0-5

2entre etx3;asort.

Tableau 2

1x2x3x4x1;ax1;ax3;a-7/2 0 0 1 1 0 -1/21/2x

1;a5/4 0 -1/2 1/2 0 1 1/413/4x

2;a1/4 1 1/2 -1/2 0 0 1/41/4x

29/4 0 1/2 -3/2 0 0 5/4-15/4

4entre etx1;asort.

Tableau 3

1x2x3x4x1;ax1;ax3;a-7/2 0 0 1 1 0 -1/21/2x

43 0 -1/2 0 -1/2 1 1/23x

2;a-3/2 1 1/2 0 1/2 0 01/2x

2-3 0 1/2 0 3/2 0 1/2-3

1entre etx2;asort.

Tableau 4

1x2x3x4x1;ax1;ax3;a0 0 -7/12 1 5/12 7/6 1/124x

41 0 -1/6 0 -1/6 1/3 1/61x

10 1 1/4 0 1/4 1/2 1/42x

20 0 0 0 1 1 10

Dans le dernier tableau, les trois variables ajoutées sont sorties de la base. Elles sont donc nulles, ce qui était l"objectif. Cela signifie que les variables qui sont main- tenant dans la base constituent une solution à coordonnées positives pour le système 7 des contraintes. On a donc trouvé un point de départ pour résoudre le problème de l"exercice. C"est le point de coordonnées (icix3est nulle car elle est hors-base ) : 8>>>< >>:x 1= 1 x 2= 2 x 3= 0 x 4= 4 On peut donc maintenant traiter le problème posé à partir du point trouvé. On com- mence par supprimer, dans le dernier tableau calculé, les colonnes des variables ajou- tées :quotesdbs_dbs22.pdfusesText_28

[PDF] 1 Programmation linéaire

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

2 Dualité 19

Corrigé ex. 1 : Méthode du simplexe

Programme 1

1+ 3x221

1etx20

1+ 3x2+x3= 21

1x2+x5= 5

Le premier tableau du simplexe s"écrit :

1x2x3x4x51 3 1 0 021x

3-1 3 0 1 018x

41 -1 0 0 15x

5-1 -2 0 0 00

On obtient le tableau suivant :

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 :

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 :

13=21=6;102=3

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

8>>>>>><

Programme 2

3x12x27

2x1+ 3x26

1etx20

Max(x1+ 3x2)

2x1+ 3x2+x5= 6

1etx20

1x2x3x4x53 -2 1 0 07x

3-1 4 0 1 09x

4-2 3 0 0 16x

51 -3 0 0 00

Cela conduit au tableau suivant :

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

115=3;15=3

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

8>>>>>><

1= 3=5

2= 12=5

Max (3x1+ 4x2)

0;30x1+ 0;30x2750

0;45x1+ 0;35x21065

1+x22500

9x1+ 7x221300

1+x2+x4= 2500

9x1+ 7x2+x5= 21300

Les tableaux du simplexe sont successivement :

Tableau 1

1x2x3x4x55 7 1 0 016500x

31 1 0 1 02500x

49 7 0 0 121300x

5-3 -4 0 0 00

2entre etx3sort.

Tableau 2

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

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

44 0 -1 0 14800x

5-1/7 0 4/7 0 066000/7

1entre etx4sort.

Tableau 3

1x2x3x4x50 1 1/2 -5/2 02000x