TD 5 Programmation linéaire et optimisation Dualité Exercice 1
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 permet
OPTI1- Dualité en PL - Algorithme dual du simplexe
Modéliser son problème par un programme linéaire P2. Quelle est la nature de P2 relativement à P1 ? Exercice 2. Ecarts complémentaires. On considère le
TD 7 : Exercice corrigé Algorithme du simplexe Méthode des deux
TD 7 : Exercice corrigé. Algorithme du simplexe. Méthode des deux phases. Exercice. Résoudre par la méthode des deux phases le modèle de programmation linéaire
SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual
PPL : Le problème de programmation linéaire sous forme canonique est de maximiser Cela provient du fait que. Excel dans son algorithme du simplexe utilise une ...
FSJES-AC RECHERCHE OPERATIONNELLE Semestre 6 Filière
PROGRAMMATION LINEAIRE - Complément –. - Partie III : Algorithme du simplexe EXERCICE : N° 10 - Résolution graphique – résolution simplexe - dualité. Une ...
Recherche opérationnelle dualité exercices corrigés pdf
programmation lineaire methode simplexe pdf.td programmation lineaire corrige pdf.primal dual exercice dualite exercices corriges pdf.recherche ...
174 EXERCICES SUPPLÉMENTAIRES — PARTIE II
lité de la programmation linéaire l'algorithme du simplexe révisé
Dualité en Programmation Linéaire Algorithmes primal et dual du
Exercice. Exercice. Page 20. 20. Le résultat suivant est très important ;. - Si l Confirmer votre réponse en résolvant (P) par l'algorithme du simplexe. Que ...
- Exercices de TD - 1 Modélisation.
Traduire par un programme linéaire en forme canonique. b. Résoudre le probl`eme par une méthode graphique. c. Maximiser le gain de l'année par la méthode du
1. Le tableau du simplexe (version perso)
Donc l'application de la méthode du simplexe à un programme linéaire associé Exercice 1. Résoudre en utilisant le tableau du simplexe. Maximiser f:(x1 x2 ...
1 Programmation linéaire
Master d'économie. Cours de M. Desgraupes. Méthodes Numériques. Document 4 : Corrigé des exercices d'optimisation linéaire. 1 Programmation linéaire.
TD 5 Programmation linéaire et optimisation Dualité Exercice 1
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 permet
Dualité en Programmation Linéaire Algorithmes primal et dual du
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
TD 7 : Exercice corrigé Algorithme du simplexe Méthode des deux
Algorithme du simplexe. Méthode des deux phases. Exercice. Résoudre par la méthode des deux phases le modèle de programmation linéaire suivant :.
Cahier dexercices corrigés Eric LALLET Jean-Luc RAFFY
Correction page 42. 1.6 Programmation linéaire : le simplexe. Exercice 1.6.1 (Une histoire de fromage). Une laiterie s'
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 ...
- Exercices de TD - 1 Modélisation.
Maximiser le gain de l'année par la méthode du simplexe. Modéliser le probl`eme sous forme d'un programme linéaire en nombres entiers.
Programmation linéaire
Théorème de dualité. 4. L'algorithme du simplexe Résoudre le problème linéaire défini par A b
(Microsoft PowerPoint - 5_dualite [Mode de compatibilité])
Problème de programmation linéaire sous forme standard L'algorithme dual du simplexe est une méthode itérative pour résoudre un.
Chapitre 4 Dualité
A chaque problème d'optimisation linéaire nous allons définir un nouveau problème d'écart x4
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 . . . . . . . . . . . . . . . . . . . . . . 172 Dualité 19
Main d"oeuvre et équipements . . . . . . . . . . . . . . . . . . . . . . . . 19 Trois techniques de production . . . . . . . . . . . . . . . . . . . . . . . . 21Production en heures-machines . . . . . . . . . . . . . . . . . . . . . . . . 221 Programmation linéaire
Corrigé ex. 1 : Méthode du simplexe
Programme 1
8 >>>>>:Max(x1+ 2x2) x1+ 3x221
x1+ 3x218 x 1x25 x1etx20
On introduit des variables d"écart, ce qui conduit aux équations suivantes pour les contraintes du problème : 8>< :x1+ 3x2+x3= 21
x1+ 3x2+x4= 18 x1x2+x5= 5
Le premier tableau du simplexe s"écrit :
1 x1x2x3x4x51 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 :
x1x2x3x4x52 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 :
Min13=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 : x1x2x3x4x51 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+ 4x292x1+ 3x26
x1etx20
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= 92x1+ 3x2+x5= 6
x1etx20
Le tableau de départ pour la méthode du simplexe est donc : x1x2x3x4x53 -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 x1x2x3x4x55/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 : Min115=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 : x1x2x3x4x50 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>>>>>><
>>>>>:x1= 3=5
x2= 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;35x28250;30x1+ 0;30x2750
0;45x1+ 0;35x21065
qui se simplifient sous la forme suivante : 8>< :5x1+ 7x216500 x1+x22500
9x1+ 7x221300
4 Si on notex3,x4,x5les variables d"écart, les contraintes deviennent : 8>< :5x1+ 7x2+x3= 16500 x1+x2+x4= 2500
9x1+ 7x2+x5= 21300
Les tableaux du simplexe sont successivement :
Tableau 1
x1x2x3x4x55 7 1 0 016500x
31 1 0 1 02500x
49 7 0 0 121300x
5-3 -4 0 0 00
x2entre etx3sort.
Tableau 2
x1x2x3x4x55/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
x1entre etx4sort.
Tableau 3
x1x2x3x4x50 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>>>>>><
>>>>>:x1= 500
x2= 2000
x 3= 0 x 4= 0 x5= 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èmepré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 m3de 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
x1x2x3+x4= 3
x1+ 4x2+ 2x32x4= 1
x1;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 suivanteMax(x1;ax2;ax3;a)8<
:3x1+2x2+x3+x1;a= 1 x1x2x3+x4+x2;a= 3
x1+4x2+2x32x4+x3;a= 1
avec les contraintes x1;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>< :x1;a= 1
x2;a= 3
x3;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< :x1;a= 1 + 3x12x2x3
x2;a= 3x1+x2+x3x4
x3;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
x1x2x3x4x1;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
x2entre etx3;asort.
Tableau 2
x1x2x3x4x1;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
x4entre etx1;asort.
Tableau 3
x1x2x3x4x1;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
x1entre etx2;asort.
Tableau 4
x1x2x3x4x1;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 : x1x2x3x40 0 -7/12 14x
41 0 -1/6 01x
10 1 1/4 02x
2Dans ce tableau, on voit que les variablesx1,x2etx4sont dans la base et que
la variablex3est hors-base. On peut l"interpréter comme le système de contraintes suivant : 8>>< 712x3+x4= 4 x 116
x3= 1 x 2+14 x3= 2 La dernière ligne doit contenir la fonction objectif initialex1x2+x3mais celle- ci doit être exprimée, comme toujours, en fonction de la ou des variable(s) hors-base uniquement. Le système précédent permet facilement de tout exprimer en fonction de x
3. On trouve :
x1x2+x3=1 +1712
x3Le tableau du simplexe s"écrit donc
x1x2x3x40 0 -7/12 14x
41 0 -1/6 01x
10 1 1/4 02x
20 0 -17/12 0-1
La variablex3entre etx2sort. Par pivot, on obtient le tableau suivant : x1x2x3x40 7/3 0 126/3x
41 2/3 0 07/3x
10 4 1 08x
30 17/3 0 031/3
On est maintenant à l"optimum et la solution du problème est : 8>>>< >>:x1= 7=3
x 2= 0 x 3= 8 x4= 26=3
La valeur à l"optimum estf= 31=3.
8Programme 2
8 >>>:Max(x1+ 2x2+ 3x3) x 1+x252x1+ 2x2x3= 6
12x1+ 8x25x3= 32
x1;x2etx30
Dans ce problème, la première contrainte est une inégalité, donc il faut commencer par introduire une variable d"écartx4. On introduit ensuite les variables ajoutées comme dans l"exercice précédent. Le problème s"écrit sous la formeMax(x1;ax2;ax3;a)
avec le système de contraintes suivant : 8< :x1+x2+x4+x1;a= 5
2x1+2x2x3+x2;a= 6
12x1+8x25x3+x3;a= 32
avecx1;x2;x3;x4;x1;a;x2;a;x3;a0. 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>< :x1;a= 5
x2;a= 6
x3;a= 32
Très important :il faut veiller à ce que la fonction objectif (x1;ax2;ax3;a) soit exprimée en fonction des variables hors-base. On doit donc, avant de commencer, extrairex1;a;x2;a;x3;aen fonction dex1;x2;x3;x4et les remplacer dans la fonction objectif. On a :8< :x1;a= 5x1x2x4
x2;a= 62x12x2+x3
x3;a= 3212x18x2+ 5x3
D"où
x1;ax2;ax3;a=43 + 15x1+ 11x26x3+x4 À partir de là, la méthode du simplexe s"applique sans problèmes :Tableau 1
x1x2x3x4x1;ax1;ax3;a1 1 0 1 1 0 05x
1;a2 2 -1 0 0 1 06x
2;a12 8 -5 0 0 0 132x
3;a-15 -11 6 -1 0 0 0-43
x1entre etx3;asort.
Tableau 2
9 x1x2x3x4x1;ax1;ax3;a0 1/3 5/12 1 1 0 -1/127/3x
1;a0 2/3 -1/6 0 0 1 -1/62/3x
2;a1 2/3 -5/12 0 0 0 1/128/3x
10 -1 -1/4 -1 0 0 5/4-3
x2entre etx2;asort.
Tableau 3
x1x2x3x4x1;ax1;ax3;a0 0 1/2 1 1 -1/2 02x
1;a0 1 -1/4 0 0 3/2 -1/41x
21 0 -1/4 0 0 -1 1/42x
10 0 -1/2 -1 0 3/2 1-2
x4entre etx1;asort.
Tableau 4
x1x2x3x4x1;ax1;ax3;a0 0 1/2 1 1 -1/2 02x
40 1 -1/4 0 0 3/2 -1/41x
21 0 -1/4 0 0 -1 1/42x
10 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-quotesdbs_dbs7.pdfusesText_13[PDF] exercices corrigés de rmn 2d
[PDF] exercices corrigés de statistique ? deux variables pdf
[PDF] exercices corrigés de statistique descriptive avec rappels de cours pdf
[PDF] exercices corrigés de statistique descriptive bernard py pdf
[PDF] exercices corrigés de statistique descriptive problèmes exercices et qcm pdf
[PDF] exercices corrigés de statistique pdf
[PDF] exercices corrigés de statistiques mathématiques pdf
[PDF] exercices corrigés de thermochimie s2
[PDF] exercices corrigés de thermochimie s2 pdf
[PDF] exercices corriges de thermodynamique pdf
[PDF] exercices corrigés de thermodynamique pdf s1
[PDF] exercices corrigés de traitement des eaux pdf
[PDF] exercices corrigés de vibrations et ondes pdf
[PDF] exercices corrigés dérivées terminale s