[PDF] [PDF] 1 Programmation linéaire

[PDF] 174 EXERCICES SUPPLÉMENTAIRES — PARTIE II

lité de la programmation linéaire, l'algorithme du simplexe révisé, les notions de La dualité faible affirme que si les programmes primal et dual ont la même Exercice 4 10 5 [Deux phases] Proposez une méthode, utilisant deux phases, 

[PDF] TD 5 Programmation linéaire et optimisation Dualité Exercice 1 - grug

Corrigé: Exercice 2 Dans le cas d'un problème de programmation linéaire ( minimisation) possédant une solution optimale finie, l'algorithme primal du simplexe 

[PDF] Dualité en Programmation Linéaire Algorithmes primal et - ENSIIE

Ecrire le dual de ce problème A-t-il une solution réalisable ? Confirmer votre réponse en résolvant (P) par l'algorithme du simplexe Que se 

[PDF] 1 Programmation linéaire

Document 4 : Corrigé des exercices d'optimisation linéaire simplexe Programme 1 Le tableau de départ pour la méthode du simplexe est donc : x1 x2

[PDF] Exercices de Programmation Linéaire – Modélisation –

exercice 1 : On veut préparer 500 litres de punch `a partir de cinq boissons A, B, C, D et exercice 1 : Résoudre le programme linéaire suivant par la méthode du simplexe (a) Appliquez la phase I du simplexe au probl`eme (P) pour montrer qu'il admet Dualité – exercice 1 : Écrire le dual du programme linéaire suivant :

[PDF] - Exercices de TD - 1 Modélisation - LIRMM

Traduire par un programme linéaire en forme canonique Maximiser le gain de l'année par la méthode du simplexe 6 Dualité - Exercice 50 - Piles, suite et fin Suite de l'Exercice 1 a Ecrire le dual (D) du programme linéaire de l'exercice 

[PDF] Exercices corrigés PROGRAMMATION LINÉAIRE

où on reconnaît l'optimum : H“ ou HVP ne pouvant être augmentée Méthode des Tableaux Déf 4 G Tableau du Simplexe : on ajoute au système des contraintes 

[PDF] Programmation linéaire et recherche opérationnelle - LIM

maximiser le profit obtenu apr`es deux ans? 3/56 Introduction Méthode graphique Simplexe Dualité Des probl 

[PDF] Série 1: Programmation linéaire

Dans les exercices suivants, appliquer l'algorithme du simplexe pour résoudre le probl`eme de programmation linéaire Exercice 8 Une solution de base 

[PDF] SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual

PPL : Le problème de programmation linéaire sous forme canonique est de maximiser Excel dans son algorithme du simplexe utilise une construction du dual 

[PDF] exercices corrigés de recherche opérationnelle méthode du simplexe

[PDF] exercices corrigés de régulation industrielle

[PDF] exercices corrigés de rhéologie

[PDF] exercices corrigés de séchage pdf

[PDF] exercices corrigés de structure de la matière et des liaisons chimiques

[PDF] exercices corrigés de système d'information géographique

[PDF] exercices corrigés de toxicologie générale

[PDF] exercices corrigés dénombrement terminale s pdf

[PDF] exercices corrigés dérivées partielles secondes

[PDF] exercices corrigés dérivées terminale es

[PDF] exercices corrigés dessin technique pdf

[PDF] exercices corrigés diagonalisation trigonalisation matrices

[PDF] exercices corrigés différentiabilité

[PDF] exercices corrigés droit des sociétés pdf

[PDF] exercices corrigés dual simplexe

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 xquotesdbs_dbs3.pdfusesText_6