Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Optimisation Linéaire L’algorithme du Simplexe DESS QUASSI Ludovic Plaçais 2002

Optimisation Linéaire L’algorithme du Simplexe DESS QUASSI Ludovic Plaçais 2002/2003 PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 2 Plan ! Programmation Linéaire ! Exemple conducteur ! L’algorithme du Simplexe ! Conclusion Exemple conducteur Programmation Linéaire L’algorithme du Simplexe Conclusion PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 3 Partie 1 : !Programmation Linéaire Exemple conducteur Programmation Linéaire L’algorithme du Simplexe Conclusion PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 4 Présentation ! Une définition ! l'optimisation d'une fonction de variables soumises à des contraintes sous forme d'égalités ou d'inégalités non strictes. ! Ce qu’elle permet ! une modélisation assez générale des problèmes rencontrés en gestion et qui sont relativement complexes. ! Domaines d’application ! modélisation, optimisation, économie, productique, ordonnancement, planification, théorie des jeux, ... Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion Présentation Formalisation Vocabulaire PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 5 Formalisation !4 étapes ! compréhension du problème. ! identification des variables de décision (qui sont les inconnues du problème) ! fixation des objectifs à atteindre => la fonction objective ! précision des contraintes du problème, contraintes exprimées sous forme linéaire par rapport aux variables de décision. => les sous-contraintes Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion Présentation Formalisation Vocabulaire PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 6 Vocabulaire ! Solution admissible ! Les solutions admissibles sont celles qui satisfont toutes les contraintes du problème. ! Solution optimale ! Elles se distinguent des solutions optimales qui, parmi les solutions admissibles, optimisent la fonction dont on cherche le maximum ou le minimum. Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion Présentation Formalisation Vocabulaire PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 7 Partie 2 : !Exemple conducteur Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 8 Énoncé !Le restaurateur Un restaurateur a constaté que sa clientèle préfère les assortiments de coquillages et qu'il peut offrir indifféremment: - des assiettes à 8 euros, contenant 5 oursins, 2 bulots et une huître. - des assiettes à 6 euros, contenant 3 oursins, 3 bulots et 3 huîtres. Il dispose de 30 oursins, 24 bulots, 18 huîtres. Question : Comment doit-il disposer ces assiettes pour réaliser la recette maximale ? Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion Enoncé Formalisation Résumé PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 9 Formalisation de l’exemple (1) !1ère étape : Compréhension du problème. Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion Enoncé Formalisation Résumé PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 10 Formalisation de l’exemple (2) !1ère étape : Compréhension du problème. !2ème étape : Identification des variables de décision. x1 : la quantité d'assiettes à 8 euros x2 : la quantité d’assiettes à 6 euros Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion Enoncé Formalisation Résumé PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 11 Formalisation de l’exemple (3) !1ère étape : Compréhension du problème. !2ème étape : Identification des variables de décision. x1 : la quantité d'assiettes à 8 euros x2 : la quantité d’assiettes à 6 euros !3ème étape : Fixation des objectifs à atteindre. La recette que nous voulons rendre maximale, est donnée par la relation : Max(z) = 8 x1 + 6 x2 Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion Enoncé Formalisation Résumé PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 12 Formalisation de l’exemple (4) ! 4ème étape : Mise en équation des sous-contraintes Rappel : Les assiettes à 8 € contiennent 5 oursins ; celles à 6 € en contiennent 3 et le restaurateur dispose de 30 oursins. 5 x1 + 3 x2 ≤30 De même pour les autres coquillages, on obtient alors : 2 x1 + 3 x2 ≤24 x1 + 3 x2 ≤18 Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion Enoncé Formalisation Résumé PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 13 Formalisation de l’exemple (5) ! 4ème étape (suite) : Mise en équation des sous- contraintes On a également les sous-contraintes implicites suivantes : x1 " 0 x2 " 0 Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion Enoncé Formalisation Résumé PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 14 Résumé On a donc le problème suivant : La fonction objective : max(z) = 8 x1 + 6 x2 Les sous contraintes : 5 x1 + 3 x2 ≤30 2 x1 + 3 x2 ≤24 x1 + 3 x2 ≤18 x1, x2 " 0 Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion Enoncé Formalisation Résumé PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 15 Partie 3 : !L’algorithme du Simplexe Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 16 Présentation !Développé par G. B. Dantzig (1947) !Année 1940 – 50 : ! à des fins militaires !Après la guerre : ! dans le monde des affaires !Dès 1970 : ! optimiser une production, un bénéfice face à la concurrence ! maîtriser les phénomènes naturels ! s’opposer militairement efficacement à un adversaire ! améliorer les jeux Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion Présentation Principe Exemple PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 17 Principe !Trouver une solution de base admissible ! En général tous les xi = 0 !Chercher à améliorer cette solution ! En satisfaisant les conditions de la sous contrainte la plus forte ! Répéter cette opération jusqu’à obtention de la solution optimale !NB : ! Vérification à chaque tour que le problème est borné Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion Présentation Principe Exemple PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 18 Exemple (1) !Solution de base admissible : max(z) = 8 x1 + 6 x2 5 x1 + 3 x2 ≤30 2 x1 + 3 x2 ≤24 x1 + 3 x2 ≤18 x1, x2 " 0 En prenant x1 = x2 = 0 , on a une première solution admissible. On va maintenant chercher à améliorer cette solution. Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion Présentation Principe Exemple PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 19 Exemple (2) !Première amélioration de la solution : ! La contrainte qui fixe le plus de contraintes est : 5 x1 + 3 x2 ≤30 ! On va chercher à optimiser la fonction objective en satisfaisant cette sous-contrainte par rapport à la variable qui impose le plus de contraintes ; c’est à dire x1. => On a donc x1 = 6 Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion Présentation Principe Exemple PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 20 Exemple (3) !Première amélioration de la solution : ! On a x1 = 6 et x2 = 0. ! Le restaurateur vend donc 6 assiettes à 8 € et 0 à 6 € ! Il réalise donc une recette de 6 * 8 = 48 € ! Il lui reste donc 0 oursins, 12 bulots et 12 huitres. ! Cette solution n’est pas optimale. On va donc chercher à l’améliorer Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion Présentation Principe Exemple PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 21 Exemple (4) !Seconde amélioration de la solution : ! La seconde contrainte qui fixe le plus de contraintes est : x1 + 3 x2 ≤18 ! On va chercher à optimiser la fonction objective en satisfaisant cette sous-contrainte par rapport à la variable qui impose le plus de contraintes : c’est à dire x2 ; tout en tenant compte de la variable x1. => On obtient après déroulement de l’algorithme x1 = 3 et x2 = 5 Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion Présentation Principe Exemple PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 22 Exemple (5) !Seconde amélioration de la solution : ! Avec x1 = 3 et x2 = 5, le restaurateur gagne 3 * 8 + 5 * 6 = 54 € ! Cette solution est optimale ! ! Il reste au restaurateur 0 oursins, 3 bulots et 0 huitres. Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion Présentation Principe Exemple PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 23 Conclusion Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion PLAÇAIS Ludovic Mini-Projets - DESS QUASSI 2002/2003 24 Question : Programmation Linéaire Exemple conducteur L’algorithme du Simplexe Conclusion uploads/Ingenierie_Lourd/ optimisation-lineaire.pdf