Leçon 3 sur 5
Programmation linéaire et méthode du simplexe
Je sais mettre un programme linéaire sous forme standard, relier solutions de base et sommets, dérouler la méthode du simplexe en tableaux, reconnaître les cas particuliers et lire dans le tableau final la solution et les prix duaux.
- 1 h 30
- 6 exercices corrigés
- QCM de 7 questions
À la fin de la leçon, vous saurez :
- Mettre un programme linéaire sous forme standard avec variables d'écart
- Relier solutions de base réalisables et sommets du polyèdre admissible
- Dérouler l'algorithme du simplexe en tableaux (variable entrante, test du rapport, pivot)
- Reconnaître un problème non borné, une solution multiple, une base dégénérée et savoir démarrer en deux phases
- Lire la solution optimale et les prix duaux dans le tableau final
Avant de commencer : Leçon 2 (dualité lagrangienne, dual d'un programme linéaire) ; algèbre linéaire (systèmes, rang, pivot de Gauss).
1Je découvre
Mme Bangoura a compris, à la leçon 2, que la production optimale de Kindia Jus est x = (3, 1). Mais elle l'a trouvée en dessinant le polygone des contraintes et en calculant la marge à chaque sommet. Avec deux produits, c'est facile. Avec les quinze références que l'usine prévoit pour l'an prochain (jus, sirops, confitures, fruits séchés) et une trentaine de contraintes (machines, sucre, bouteilles, camions vers Conakry et Mamou), il n'y a plus de dessin possible, et le nombre de sommets se compte en millions.
En 1947, George Dantzig a proposé une idée simple : partir d'un sommet et passer, à chaque étape, à un sommet voisin meilleur, jusqu'à ce qu'aucun voisin ne soit meilleur. C'est la méthode du simplexe, encore au cœur des logiciels de planification utilisés dans l'industrie, les mines et la logistique.
Comment passer méthodiquement d'un sommet à un meilleur, comment savoir qu'on a atteint l'optimum, et que lit-on dans le dernier tableau ?
La suite se lit avec votre compte Kharandi Université
La première leçon de chaque cours est libre. Kharandi Université est une inscription à part de l’école : avec votre compte étudiant, vous lisez toutes les leçons en entier, avec les exercices corrigés et les QCM, et les 7 premiers jours sont offerts.