Université saad dahlab blida 15 juin 2010 -Programmation lin
Télécharger PDFExercices de Programmation Linéaire : Méthodes et Applications
Ces exercices sont conçus pour explorer les concepts fondamentaux et les méthodes de résolution en programmation linéaire, un domaine essentiel de l'optimisation. Ils couvrent la recherche de solutions de base réalisables, la modélisation de problèmes concrets, et l'application d'algorithmes clés tels que le simplexe et la méthode des deux phases, ainsi que la dualité.
Exercice 1 : Détermination des Solutions de Base Réalisables
À partir de la solution X = (2, 4, 2), déterminez deux solutions de base réalisables du système suivant, en considérant les variables x1, x2, x3 ainsi que les variables d'écart x4 et x5 :
x1 + x2 + x3 + x4 = 16
2x1 + x2 + x3 + x5 = 12
avec toutes les variables xi ≥ 0.
Exercice 2 : Optimisation de Production par la Méthode du Simplexe
Une limonaderie traditionnelle fabrique deux types de boissons gazeuses, type A et type B. Le bénéfice net est de 2 DA pour une bouteille de type A et de 1,50 DA pour le second type. Le temps de fabrication pour le type A est deux fois le temps de fabrication pour le type B. Si toutes les bouteilles sont de type B, l'entreprise peut fabriquer 1000 bouteilles par jour.
L'approvisionnement en sucre est suffisant pour 800 bouteilles par jour (tous types confondus). De plus, l'entreprise dispose de 400 bouchons de type A et de 700 bouchons de type B quotidiennement.
Quels sont les nombres respectifs de bouteilles des deux types (A et B) à fabriquer chaque jour afin de maximiser le bénéfice total de cette entreprise ? Écrivez la formulation mathématique de ce problème de programme linéaire et résolvez-le par la méthode du simplexe.
Exercice 3 : Résolution d'un Programme Linéaire par la Méthode des Deux Phases
Par la méthode des deux phases, résolvez le programme linéaire suivant :
Min Z = 6x1 + 9x2 + 3x3
Sous les contraintes :
-x1 + 2x2 + x3 ≥ 2
3x1 + x2 - x3 ≥ 1
avec x1 ≥ 0 ; x2 ≥ 0; x3 ≥ 0.
Exercice 4 : Formulation et Résolution du Dual d'un Programme Linéaire
Écrivez et résolvez le dual du programme linéaire suivant :
Min Z = x1 + 2x2 + 3x3 + ... + nxn
Sous les contraintes (pour i = 1, ..., n) :
x1 + x2 + ... + xi ≥ i
avec xj ≥ 0, pour j = 1, ..., n.
Foire Aux Questions (FAQ)
Qu'est-ce qu'une solution de base réalisable en programmation linéaire ?
Une solution de base réalisable (SBR) est un sommet du polyèdre des solutions admissibles d'un programme linéaire. C'est une solution obtenue en fixant un nombre de variables (non-basiques) à zéro égal à la différence entre le nombre total de variables et le nombre de contraintes d'égalité, et en résolvant le système d'équations résultant. Pour qu'elle soit "réalisable", toutes les variables doivent être non-négatives.
Quand utilise-t-on la méthode des deux phases ?
La méthode des deux phases est utilisée pour résoudre des programmes linéaires lorsque le problème ne possède pas une solution de base réalisable initiale évidente, c'est-à-dire quand la forme canonique standard (avec toutes les variables de base initiales étant des variables d'écart positives) n'est pas directement applicable. Cela se produit souvent en présence de contraintes de type "supérieur ou égal" (≥) ou d'égalités (=), nécessitant l'introduction de variables artificielles.
Quel est l'intérêt de formuler le dual d'un programme linéaire ?
La formulation du dual d'un programme linéaire présente plusieurs avantages. Elle offre une perspective économique complémentaire au problème primal, facilite parfois la résolution (si le dual est plus simple à résoudre), et fournit des bornes sur la valeur optimale du problème primal. De plus, la théorie de la dualité est fondamentale pour comprendre les conditions d'optimalité et la sensibilité des solutions.