Recherche opérationnelle
2.2.5 Utilisation de la méthode du simplexe dans un probl`eme de minimisation . . . . . . . 61. 2.2.6 Exercices récapitulatifs .
Cahier dexercices corrigés Eric LALLET Jean-Luc RAFFY
Cahier d'exercices corrigés 1.6 Programmation linéaire : le simplexe . ... D'ailleurs pour toutes ces recherches et tout l'aspect logistique
1 Programmation linéaire
Document 4 : Corrigé des exercices d'optimisation linéaire. 1 Programmation linéaire Le tableau de départ pour la méthode du simplexe est donc :.
Introduction à loptimisation et la recherche opérationnelle (2017
Algorithme du simplexe – corrigé (20 octobre 2017) exercice il n'est pas possible d'utiliser la solution de départ usuelle qui.
Exercice 1.2.1. Résoudre par le simplexe Max x1 + 2x2 sous ?3x1
2) Tableau du simplexe (forme canonique !) x1 x2 x3 x4 x5. z b. -1 -2 0. 0. 0 -1 0. -3
Examen de recherche opérationnelle – Corrigé
Examen de recherche opérationnelle – Corrigé. Marc Roelens. Décembre 2006. 1 Ordonnancement de tâches. 1.1. On dresse le tableau des contraintes de
TD 7 : Exercice corrigé Algorithme du simplexe Méthode des deux
Pour cela nous allons appliquer la phase I de la méthode des deux phases en espérant une solution de base réalisable optimale qui serait la S.B.R. de.
RECHERCHE OPERATIONNELLE
Résoudre par la méthode du simplexe. 4. Expliquer les résultats (variables principales fonction économique
FSJES-AC RECHERCHE OPERATIONNELLE Semestre 6 Filière
La méthode du simplexe est un algorithme qui permet la recherche de la solution optimale d'un programme linéaire donné. Dans la partie précédente ( Partie
- Exercices de TD - 1 Modélisation.
Maximiser le gain de l'année par la méthode du simplexe. Le but de cet exercice est la recherche d'une stratégie mixte optimale pour le jeu de Morra.
C D - EPFL
la recherche opérationnelle (2017–2018) Professeur : Michel Bierlaire Assistants responsables : Virginie Lurkin et Nikola Obrenovic Algorithme du simplexe – corrigé (20 octobre 2017) la ligne en gris comme étant la ligne de pivot et il va falloir éliminer les autres valeurs dans la colonne en gris Pour éliminer la valeur au
La Méthode de Simplexe - Cours de La Recherche Opérationnelle
A une certaine itération du simplexe nous disposons d’une solution de base x B lié à un choixB devariablesdebase Ensuiteils’agitdepivoterversunesolutiondebaseadjacente quidoitêtreadmissible Lecritèreduquotientassurequelanouvellesolutiondebasesera admissible Ene?etnotonsparj lacolonnedepivotdel’étape1etpari
Searches related to recherche opérationnelle simplexe exercices corrigés PDF
TD 7 20: Exercice corrigé Algorithme du simplexe Méthode des deux phases Exercice 12 Résoudre par la méthode des deux phases le modèle de programmation linéaire suivant : 12 12 12 12 60 0 80 0 x x x xx xx ° t °° t ® ° d ° °¯ tt a) Standardisation de (P) par ajout des variables d’écart : 1 2 3 4 5 1 2 3 1 2 4 1 2 5 1 2 3 4 5
Qu'est-ce que la méthode de simplexe ?
Cette solution correspond à un point extrême de l’ensemble des solutions réalisables qui est l’origine O. Pour la méthode de simplexe une solution réalisable de base initiale est demandée. Une telle solution peut être retrouvée en annulant toutes les variables de décision. Ce qui correspond dans notre exemple au point d’origine O.
Quel est le principe de résolution de la méthode de Simplexe?
La méthode de simplexe commence par l'identification d'une solution réalisable de base et ensuite, elle essaye de trouver d'autres solutions réalisables de base jusqu’à atteindre à la solution optimale. Ainsi, on doit, tout d’abord, retrouver cette solution réalisable de base.
Comment trouver une solution optimale pour un programme linéaire ?
Ainsi une autre solution optimale peut être trouvée pour notre programme linéaire. Ceci confirme le résultat de la méthode graphique qui indique que ce problème admet un ensemble de solution optimale décrit par le segment [BC]. La solution optimale donnée par le dernier tableau de simplexe correspond au point C.
Introduction à l"optimisation et
la recherche opérationnelle (2017-2018) Professeur : Michel Bierlaire, Assistants responsables : Virginie Lurkin et Nikola Obrenovic Algorithme du simplexe - corrigé (20 octobre 2017)Solution de la question 1:
1. Le domaine admissible est représenté en gris sur la Figure1. La solution
optimale correspond au sommet D (9,0). La fonction objective vaut alors -27. x1 x2012345678910
0 1 2 3 4 5 6 7 AB C D cTx=-12 cTx=-18 cTx=-27Figure1 - Domaine admissible
2. Pour résoudre le problème en utilisant la méthode du simplexe, on
commence par mettre le problème en forme standard. Pour cela, on introduit les variables d"écarte1ete2: min-3x1+ 4x2 sous contraintes x1+x2-e1= 4
2x1+ 3x2+e2= 18
x1,x2,e1,e2≥0
1Introduction à l"optimisation et
la recherche opérationnelle (2017-2018) Professeur : Michel Bierlaire, Assistants responsables : Virginie Lurkin et Nikola Obrenovic Algorithme du simplexe - corrigé (20 octobre 2017) On peut alors identifier la matriceA, le vecteurbet le vecteurc:A=?1 1-1 0
2 3 0 1?
,b=?4 18? etc=((((-3 4 0 0)))) Avant de commencer à résoudre cette optimisation en utilisant l"algo- rithme du simplexe, il nous faut trouver une solution de départ. Dans certains cas, il peut être difficile de trouver une solution debase ad- missible pour démarrer l"algorithme du simplexe. Dans le cas de cet exercice, il n"est pas possible d"utiliser la solution de départ usuelle qui consiste à mettre les variables d"écart en base (x1=x2= 0n"est pas une solution de base admissible). Il nous faut donc résoudrele problème auxiliaire.Étape I : problème auxiliaire
Afin de résoudre la première phase du simplexe et de trouver ainsi un premier tableau (une première solution admissible), nous introduisons dans le problème des variables auxiliaires,a1eta2. Le problème auxi- liaire a pour objectif d"éliminer ces variables auxiliaires et est défini comme suit : mina1+a2 sous contraintes x1+x2-e1+a1= 4
2x1+ 3x2+e2+a2= 18
x1,x2,e1,e2≥0
Itération #1
Nous pouvons maintenant facilement créer un tableau initial pour la phase I en choisissant comme variables en base les variablesauxiliaires a1eta2. Le tableau initial est donc constitué de 7 colonnes, correspon-
dant aux 4 variables du problème original, plus les deux variables auxi- liaires que nous avons ajoutées, plus une dernière colonne qui contiendra 2Introduction à l"optimisation et
la recherche opérationnelle (2017-2018) Professeur : Michel Bierlaire, Assistants responsables : Virginie Lurkin et Nikola Obrenovic Algorithme du simplexe - corrigé (20 octobre 2017) la partie droite du tableau. On construit le tableau initialde la manière suivante. Nous recopions d"abord la matriceApour les colonnes cor- respondant aux variables du problème original et la partie supérieure du tableau. Nous écrivons la matrice identité dans la partiecorrespon- dant aux variables auxiliaires. Effectivement ces variables auxiliaires sont en base, donc les colonnes associées sont les colonnes de la matrice identité. Pour ces colonnes, les valeurs dans la dernière ligne sont 0, puisqu"il s"agit des variables en base. Nous recopions le vecteurbdans la partie droite du tableau. Enfin, le calcul de la dernière ligne du ta- bleau pour les colonnes correspondant aux variables hors base, exploite la structure spécifique de cette première phase du tableau dusimplexe. Pour la calculer nous faisons la somme des différentes lignes(c-à-d les différentes éléments de la colonne) du tableau et nous changons le résul- tat de signe. Finalement, notons que la valeur sur la dernière ligne et la dernière colonne, qui correspond à l"opposé de la somme des éléments du vecteurb, contient l"opposé de la valeur de la fonction objectif. x1x2e1e2a1a2
a1A I2ba 2 jAi,j0 0-? jbjOn peut maintenant remplir le tableau :
x1x2e1e2a1a2
a11 1 -1 0 1 0 4 a22 3 0 1 0 1 18
-3 -4 1 -1 0 0 -22 Les six premières valeurs sur la dernière ligne correspondent aux coûts réduits. Vous pouvez, bien entendu, vérifier cela en calculant les coûts réduits avec la méthode algébrique. Vous pouvez aussi vérifier que l"op- posé de la somme des éléments du vecteurbcorrespond à l"opposé de la valeur de la fonction objectif. 3Introduction à l"optimisation et
la recherche opérationnelle (2017-2018) Professeur : Michel Bierlaire, Assistants responsables : Virginie Lurkin et Nikola Obrenovic Algorithme du simplexe - corrigé (20 octobre 2017) La prochaine étape consite à choisir quelle variable va rentrer dans la base. Pour cela, on sélectionne les variables auxquelles uncoût réduit négatif est associé. Nous avons, ici, le choix entrex1,x2ete2. Larègle de Blandstipule quesi on a le choix entre plusieurs variables qui peuvent rentrer dans la base, on choisit celle avec le plus petit indice (c-à-d le plus à gauche dans le tableau). On choisit doncx1pour rentrer dans la base. x1x2e1e2a1a2
a11 1 -1 0 1 0 4 a22 3 0 1 0 1 18
-3 -4 1 -1 0 0 -22 On peut maintenant calculer les distances correspondants aux variables en base. On a donc que a1=4 1= 4 a2=18 2= 9 Le pas maximum est le minimum des deux distances. Il vaut donc4. De plus, on sait maintenant quex1va rentrer dans la base eta1va en sortir. On peut aussi calculer la diminution de la fonction objectif qui vautθa1¯cx1=-12. x1x2e1e2a1a2
a11 1 -1 0 1 0 4 a22 3 0 1 0 1 18
-3 -4 1 -1 0 0 -22 Il faut bien s"assurer que le pivot (entouré en noir) vaut 1. Si ce n"est pas le cas, il est possible de diviser la ligne par la valeur dupivot afin de se ramener à un pivot de 1. Dans ce cas, il n"y a pas de souci. On peut donc calculer le tableau pour la seconde itération. Pour cela, on utilise 4Introduction à l"optimisation et
la recherche opérationnelle (2017-2018) Professeur : Michel Bierlaire, Assistants responsables : Virginie Lurkin et Nikola Obrenovic Algorithme du simplexe - corrigé (20 octobre 2017) la ligne en gris comme étant la ligne de pivot et il va falloir éliminer les autres valeurs dans la colonne en gris. Pour éliminer la valeur au milieu de la colonne, c"est-à-dire2, il faut prendre cette ligne du milieu et soustraire 2 fois la première ligne. Pour éliminer la valeur du bas de la colonne en gris, il faut ajouter 3 fois la première ligne. x1x2e1e2a1a2
a11 1 -1 0 1 0 4 a22 3 0 1 0 1 18
-3 -4 1 -1 0 0 -22 -2×+3×Itération #2
Le tableau pour la deuxième itération est le suivant : x1x2e1e2a1a2
x11 1 -1 0 1 0 4 a20 1 2 1 -2 1 10
0 -1 -2 -1 3 0 -10
On voit que la valeur de la fonction objectif est égale à-10ce qui équivaut à-(22-12). La réduction de la fonction objectif calculée était donc correcte. Nous devons maintenant continuer l"algorithme en choissisant la prochaine variable qui va rentrer dans la base. On a le choix entrex2,e1ete2. Par la règle de Bland, on choisitx2. x1x2e1e2a1a2
x11 1 -1 0 1 0 4 a20 1 2 1 -2 1 10
0 -1 -2 -1 3 0 -10
On peut calculer maintenant les pas afin de savoir quelle variable va sortir de la base. x1=4 1= 4 a2=10 1= 10 5Introduction à l"optimisation et
la recherche opérationnelle (2017-2018) Professeur : Michel Bierlaire, Assistants responsables : Virginie Lurkin et Nikola Obrenovic Algorithme du simplexe - corrigé (20 octobre 2017) Le pas maximum est donc de 4. C"est donc la variablex1qui va sortir de la base pour laisser sa place àx2. On peut aussi calculer la diminution de la fonction objectif qui vautθx1¯cx2=-4. x1x2e1e2a1a2
x11 1 -1 0 1 0 4 a20 1 2 1 -2 1 10
0 -1 -2 -1 3 0 -10
-1×+1×Itération #3
Le tableau pour la troisième itération est le suivant : x1x2e1e2a1a2
x21 1 -1 0 1 0 4 a2-1 0 3 1 -3 1 6
1 0 -3 -1 4 0 -6
Nous devons maintenant continuer l"algorithme en choissisant la pro- chaine variable qui va rentrer dans la base. On a le choix entree1ete2.Par la règle de Bland, on choisite1.
x1x2e1e2a1a2
x21 1 -1 0 1 0 4 a2-1 0 3 1 -3 1 6
1 0 -3 -1 4 0 -6
On peut calculer maintenant les pas afin de savoir quelle variable va sortir de la base. x2=4 -1=-4 a2=6 3= 2 Le pas ne pouvant pas être négatif, le pas maximum vaut 2. C"est donc la variablea2qui va sortir de la base pour laisser sa place àe1. On peut aussi calculer la diminution de la fonction objectif qui vautθa2¯ce1=-6. 6Introduction à l"optimisation et
la recherche opérationnelle (2017-2018) Professeur : Michel Bierlaire, Assistants responsables : Virginie Lurkin et Nikola Obrenovic Algorithme du simplexe - corrigé (20 octobre 2017) x1x2e1e2a1a2 x21 1 -1 0 1 0 4 a2-1 0 3 1 -3 1 6
1 0 -3 -1 4 0 -6
Le pivot vaut cette fois-ci 3. Il faut donc diviser la deuxième ligne par3 afin d"avoir un pivot valant 1.
x1x2e1e2a1a2
x21 1 -1 0 1 0 4 a2-1/3 0 1 1/3 -1 1/3 2
1 0 -3 -1 4 0 -6
+1× +3×Itération #4
Le tableau pour la quatrième itération est le suivant : x1x2e1e2a1a2
x22/3 1 0 1/3 0 1/3 6 e1-1/3 0 1 1/3 -1 1/3 2
0 0 0 0 1 1 0
Puisque tous les coûts réduits sont non-négatifs, la solution optimale du problème auxiliaire a été trouvée. La première phase est donc ter- minée. La solution est la suivante :x1,e2,a1eta2sont hors-base et valent, donc,0. Les variables en base valentx2= 6ete1= 2. Vous pouvez vérifier que ces deux variables satisfont bien les contraintes du problème sous forme standard. Nous pouvons maintenant passer à la résolution du problème d"optimisation en utilisant la méthode du sim- plexe et ce point en tant que point initial.Étape II : problème initial
La construction du tableau lors de la première utilisation est simple puisqu"il suffit de réutiliser le tableau qui a été trouvé lorsde l"étape 7Introduction à l"optimisation et
la recherche opérationnelle (2017-2018) Professeur : Michel Bierlaire, Assistants responsables : Virginie Lurkin et Nikola Obrenovic Algorithme du simplexe - corrigé (20 octobre 2017) finale du problème auxiliaire. Il faut, bien entendu, enlever les variables auxiliaires pour ce problème.Itération #1
Le tableau de la première itération est, donc, donné par : x1x2e1e2
x22/3 1 0 1/3 6 e1-1/3 0 1 1/3 2
¯cx10 0¯ce2-cTx
On connait déjà les coûts réduits des variables en base. Maisil faut calculer les coûts réduits des variables hors-base. On voitque la matriceBest l"idendité. On a donc queB-1=I2:
¯cx1=c1-cTBB-1A1=-3-?4 0??1 00 1??
2/3 -1/3? =-17 3¯ce2=c4-cTBB-1A4= 0-?4 0??1 00 1??
1/3 1/3? =-4 3 Notez bien que nous avons utilisé la matriceAprésente dans le tableau ci-dessus. On peut aussi calculer la valeur de la fonction objectif : -cTx=-?-3 4 0 0?((((0620)))) =-24Le tableau complet est donc donné par :
x1x2e1e2
x22/3 1 0 1/3 6 e1-1/3 0 1 1/3 2
-17/3 0 0 -4/3 -24 8Introduction à l"optimisation et
la recherche opérationnelle (2017-2018) Professeur : Michel Bierlaire, Assistants responsables : Virginie Lurkin et Nikola Obrenovic Algorithme du simplexe - corrigé (20 octobre 2017) Toujours en utilisant la règle de Bland, on choisit de faire rentrerx1 dans la base. x1x2e1e2
x22/3 1 0 1/3 6 e1-1/3 0 1 1/3 2
-17/3 0 0 -4/3 -24 On peut calculer maintenant les pas afin de savoir quelle variable va sortir de la base. x2=62/3= 9
e1=2 -1/3=-6 Le pas maximum est 9. On va donc faire rentrer la variablex1dans la base et faire sortir la variablex2. On peut aussi calculer la diminution de la fonction objectif qui vautθx2¯cx1=-51. x1x2e1e2
x22/3 1 0 1/3 6 e1-1/3 0 1 1/3 2
-17/3 0 0 -4/3 -24 Comme le pivot n"est pas égal à 1, il faut multiplier la première ligne par 3/2. x1x2e1e2
x21 3/2 0 1/2 9 e1-1/3 0 1 1/3 2
-17/3 0 0 -4/3 -24 +1/3×+17/3×Itération #2
9Introduction à l"optimisation et
la recherche opérationnelle (2017-2018) Professeur : Michel Bierlaire, Assistants responsables : Virginie Lurkin et Nikola Obrenovic Algorithme du simplexe - corrigé (20 octobre 2017) La tableau de la deuxième itération est, donc, donné par : x1x2e1e2
x11 3/2 0 1/2 9 e10 1/2 1 1/2 5
0 17/2 0 3/2 27
Puisque tous les coûts réduits sont non-négatifs, la solution optimale du problème initial a été trouvée. La solution est la suivante : x=((((x 1 x 2 e 1 e 2)))) =((((9050)))) aveccTx=-27 La solution optimale correspond, donc, bien au point D sur lafigure 1.Solution de la question 2:
1. Posonsx1le nombre de paquets de biscuits sucrés etx2le nombre de
paquets de biscuits salés. Le problème d"optimisation linéaire maximisant les revenus de la vente des biscuits est donné par : max3x1+ 4x2 sous contraintes x x x x1,x2≥0
En forme standard, on obtient :
min-3x1-4x2 10Introduction à l"optimisation et
la recherche opérationnelle (2017-2018) Professeur : Michel Bierlaire, Assistants responsables : Virginie Lurkin et Nikola Obrenovic Algorithme du simplexe - corrigé (20 octobre 2017) sous contraintes x1+ 2x2+e1= 50
x1+e2= 20
x2+e3= 30
x1,x2,e1,e2,e3≥0
2. Pour la résolution avec le simplexe, on a deux choix. Soit,on résoud
d"abord le problème auxiliaire afin de trouver un point de départ. Soit, on essaye de trouver soi-même une solution de base admissible. Dans le cas de ce problème, on peut facilement trouver une solution de base admissible. On pose quex1etx2sont hors-base. Nous avons, donc, que e1,e2ete3sont en base et valent respectivement 50, 20 et 30. Cette
solution vérifie les conditions pour être une solution de base et est bien une solution admissible puisque toutes les valeurs du vecteurxsont non-négatives.3. On résoud le problème en utilisant le point initial trouvéau point 2.
On commence donc directement par le problème initial.Itération #1
Le tableau initial est donc donné par :
x1x2e1e2e3
e11 2 1 0 0 50 equotesdbs_dbs16.pdfusesText_22[PDF] cours et exercices corrigés de recherche opérationnelle+pdf
[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
[PDF] adjectif pour acrostiche
[PDF] recherche qualitative définition
[PDF] méthode qualitative et quantitative
[PDF] méthode qualitative mémoire
[PDF] méthode quantitative
[PDF] méthodologie de recherche qualitative pdf
[PDF] méthode qualitative entretien