Controle d optimisation et programmation lineaire 1ere annee
Télécharger PDFContrôle d'Optimisation et Programmation Linéaire
Ce document présente une série d'exercices d'optimisation destinés aux étudiants en ingénierie. Il couvre la modélisation de problèmes réels sous forme de programmes linéaires, l'utilisation de la dualité, ainsi que les méthodes de résolution pour les variables entières et binaires.
Exercice 1 : Optimisation de la production d'acier
Une usine fabrique trois types d'acier (A, B et C) en utilisant du fer et de la houille. L'objectif est de maximiser le profit en respectant les contraintes de ressources disponibles.
Données du problème :
- Acier A : 4 tonnes de fer, 1 tonne de houille, prix de vente 8 k€.
- Acier B : 7 tonnes de fer, 1 tonne de houille, prix de vente 8 k€.
- Acier C : 4 tonnes de fer, 10 tonnes de houille, prix de vente 47 k€.
Les stocks disponibles sont limités à 20 tonnes de fer et 30 tonnes de houille.
Questions de réflexion :
- Formuler le problème sous la forme d'un programme linéaire (PL).
- Déterminer le dual (PL*) correspondant au programme primal.
- Analyser lequel du primal ou du dual est le plus simple à résoudre selon le nombre de contraintes et de variables.
- Interpréter les valeurs marginales (prix d'ombre) obtenues dans le tableau optimal du simplexe pour comprendre l'impact d'une unité supplémentaire de ressource sur le bénéfice total.
Exercice 2 : Programmation linéaire en nombres entiers
Il s'agit de résoudre un problème de maximisation où les variables de décision doivent impérativement être des nombres entiers (X1, X2 ∈ N).
Fonction objectif : Max Z = 3X1 + 2X2
Contraintes :
- -2X1 + 2X2 ≤ 7
- 2X1 + 3X2 ≤ 18
- -9X1 + 2X2 ≥ -36
La solution relaxée (sans contrainte d'intégrité) est x*(144/31, 90/31) pour z* = 612/31. La résolution doit s'effectuer par la méthode de séparation et évaluation (Branch and Bound), en priorisant la variable avec la partie décimale la plus forte pour la séparation.
Exercice 3 : Optimisation avec variables binaires
Cet exercice porte sur la résolution d'un programme linéaire dont les variables sont binaires (0 ou 1), ce qui est fréquent dans les problèmes de choix de type "tout ou rien".
Minimiser z = -3x1 + 4x2 + 3x3 + 3x4 + 5x5 + 2x6
Sous les contraintes de structure suivantes :
- 6x1 - 8x1 + 7x2 + 4x4 - 8x5 + 2x6 ≥ 1
- -x2 + x3 - 4x5 - 4x6 ≤ 1
- 5x1 - x2 + 2x3 + 2x4 + x5 - x6 ≤ 2
- 2x1 + 2x2 + x3 + 7x4 + 3x5 + 2x6 ≤ 6
- xi ∈ {0, 1}
Exercice 4 : Modélisation d'un portefeuille d'investissement
Une société souhaite investir un capital total de 1 400 000 € dans différents projets. Quatre opportunités sont identifiées avec leurs coûts et bénéfices respectifs :
- Investissement 1 : Coût 500 000 €, Bénéfice 1 600 000 €, Rendement 3.20
- Investissement 2 : Coût 700 000 €, Bénéfice 2 200 000 €, Rendement 3.14
- Investissement 3 : Coût 400 000 €, Bénéfice 1 200 000 €, Rendement 3.00
- Investissement 4 : Coût 300 000 €, Bénéfice 800 000 €, Rendement 2.67
Après résolution en nombres entiers, la solution optimale retenue est x1 = 0, x2 = 1, x3 = 1, x4 = 1. Cela signifie que l'entreprise doit investir dans les projets 2, 3 et 4 pour maximiser son gain tout en respectant son budget de 1,4 million d'euros.
FAQ : Questions fréquentes sur l'optimisation
Qu'est-ce qu'une valeur marginale en économie ?
En programmation linéaire, la valeur marginale (ou prix d'ombre) représente l'amélioration de la valeur de la fonction objectif pour chaque unité supplémentaire d'une ressource limitée. Elle permet de savoir s'il est rentable d'acquérir davantage de matières premières.
Pourquoi utiliser la méthode de séparation et évaluation ?
La méthode de séparation et évaluation (Branch and Bound) est essentielle lorsque les solutions doivent être des nombres entiers. Elle permet d'explorer systématiquement les solutions possibles en divisant le problème en sous-problèmes plus restreints jusqu'à trouver l'optimum entier.
Quelle est la différence entre le primal et le dual ?
Le primal est le problème original (souvent une maximisation de profit), tandis que le dual est une formulation alternative (souvent une minimisation de coûts de ressources). La résolution du dual peut parfois être plus rapide et offre des informations précieuses sur la valeur des contraintes.