EN SI
2013/2014
Classe I.I.1: Recherche Opérationnelle. Série Programmation Linéaire
Exercice 1 (modélisation) Une personne a la possibilité de vendre: - 500 cartes postales,
- 20 guides touristiques.
Elle constitue deux lots publicitaires:
- Lot n(cid:14)1 = un guide et 10 cartes postales, - Lot n(cid:14)2 = un guide et 50 cartes postales.
Son béné…ce unitaire est fonction du lot vendu, il est de 6 dinars par lot n(cid:14)1 et de 10 dinars par lot n(cid:14)2: 1) Formuler un modèle donnant un plan qui maximise le béné…ce total. 2) Mettre le modèle obtenu sous forme standard. Exercice 2 (modélisation) On désire déterminer la composition, à coût minimal, d’un aliment pour bé- tail qui est obtenu en mélangeant au plus trois produits bruts: orge, arachide et sésame. L’aliment ainsi conditionné devra comporter au moins 22% de pro- téines et 3; 6% de graisses, pour se conformer aux exigences de la clientele. Dans le tableau ci-dessous, on indique les pourcentages de protéines et de graisses contenus, respectivement, dans l’orge, les arachides et le sésame, ainsi que le coût par tonne de chacun des produits bruts:
produit brut pourcentage de protéines pourcentage de graisses coût par tonne
orge arachides 12% 2% 25
52% 2% 41
sésame 42% 10% 39
A…n de déterminer la composition, à coût minimal, d’un tonne d’aliment conforme aux exigences de la clientèle, donner une formulation du problème posé sous forme d’un programme linéaire. Exercice 3 (solution non bornée) On considère le programme linéaire suivant:
(cid:0)
M in z = x2 Sous (cid:0) 2x1 x2 (cid:0) x1 x2 (cid:0) x1 + x2 xj
x1 Contraintes : 2 (cid:21) (cid:0) 2 (cid:20) 5 (cid:20) 0; j = 1; :::; 2
(cid:21)
1
(P L)
8
>>>>>>< >>>>>>:
a- Représenter l’ensemble des solutions admissibles. b- Localiser toutes les solutions de base réalisables. c-Calculer la valeur de la fonction coût Z en chacun de ces points et donner la solution optimale. d- Déterminer graphiquement l’ensemble des solutions optimales. Exercice 4 (manipulation des bases) On considère le programme linéaire suivant:
M ax z = 5x1 + x2 + 6x3 + 24x4 Sous-Contraintes: 4x1 + 4x2 + 4x3 + x4 8x1 + 6x2 + 4x3 + 3x4 0; j = 1; :::; 4 xj
24 36
(cid:20) (cid:20)
(cid:21)
(P L) 8 >>>>< >>>>:
a- Ecrire (P L) sous forme standard, les variables d’écart seront nomées x5 et x6: b- soit B = (A3; A4): Cette base est-elle réalisable? est-elle optimale? Exercice 5 (solution initiale) On considère les programmes linéaires suivants:
(P L)
(cid:20)
(cid:20)
M ax z = 2x1 + x2 + x3 Sous-Contraintes: 2x1 + x2 + x3 2 x1 + x2 10 2x1 + 4x2 + x3 8 (cid:20) 0; j = 1; :::; 3 xj max z = 3x1 + 4x2 + x3 Sous-Contraintes : 8 x1 + 2x2 + 2x3 3 7 x1 + 2x2 + 3x3 3 xj
(cid:20) (cid:21) 0; j = 1; 2; 3
(cid:21)
(cid:21)
(P L)
8
>>>>>>< >>>>>>: >>>>< >>>>:
Publicité
8
a- Ecrire (P L) sous forme standard. b- Ce problème admet-il une solution initiale évidente? justi…er votre réponse. Exercice 6 (solution intermédiaire) On considère le programme linéaire suivant:
2
max z = 3x1 + 2x2 + 5x3 Sous Contraintes: x1 + 2x2 + x3 + x4 = 430 3x1 + 2x3 + x5 = 460 x1 + 4x2 + x6 = 420 xj > 0; j = 1; ::::; 6
(P:L)
8
>>>>>>< >>>>>>:
1) Montrer que la solution : X = (0; 0; 230; 200; 0; 420) est une solution de base réalisable du programme linéaire (P:L). 2) Donner le tableau du simplexe correspondant à cette solution de base. 3) Le tableau obtenu est-il optimal? Justi…er votre réponse. Exercice 7 (méthode des deux phases ou méthode M) : On considère le programme linéaire suivant:
1) Résoudre ce programme linéaire à l’aide de la méthode des deux phases. 2) Donner une résolution graphique de (LP ) dans le plan (x1; x2). Décrire, dans ce plan, le cheminement qui correspond à l’application de la méthode du simplexe.
Exercice 8 (programmation paramétrée)
On considère le programme linéaire suivant:
8
>>>>>>< >>>>>>:
8
>>>>>>< >>>>>>:
(P L)
x2
(cid:0)
2x1
max z = (cid:0) Sous-Contraintes : 3x1 + x2 = 3 4x1 + 3x2 x1 + 2x2 xj
6 (cid:21) 3 (cid:20) 0; j = 1; 2
(cid:21)
(P L)
max Z = 6x1 + 5x2 contraintes sous
(cid:0)
x1 + x2 (cid:20) 2x1 + 3x2 x1
x2
8
(cid:20) 2
(cid:0) (cid:20) 0; i = 1; 2
6
(cid:0)
xi
(cid:21)
3
1- Donner une résolution graphique de ce programme linéaire. 2- Soit un modèle de programmation linéaire qui doit être appliqué régulière- ment mais dont certains coe¢ cients varient d’une application à l’autre. Prenons
le cas où les coe¢ cients de la fonction coût Z varient en fonction d’un facteur extérieur (prix d’une matière première, taux d’intérêt, indice des prix,...etc). Ce phénomène peut être modélisé par un paramètre intervenant dans ces coe¢ cients. En introduisant un paramètre (cid:21) dans la fonction coût Z, le programme linéaire (P L) s’écrit:
max Z = (6 sous
Publicité
2(cid:21))x1 + (5 + (cid:21))x2 contraintes
(cid:0) (cid:0)
x1 + x2 (cid:20) 2x1 + 3x2 x1
x2
8
(cid:20) 2
(cid:0) (cid:20) 0; i = 1; 2
6
(cid:0)
xi
(cid:21)
(P L)
8
>>>>>>< >>>>>>:
a- Résoudre ce programme linéaire suivant les valeurs de (cid:21): b- Parmi les solutions réalisables trouvées dans la première question, quelles sont celles qui ne sont jamais solutions optimales. c- Pour quelles valeurs de (cid:21); le programme linéaire (P L) admet une in…nité de solutions optimales?
Exercice 9 (programme dual)
Donner le programme dual de chaque programme linéaire.
Max z = 15x1 + 40x2 + 12x3 Sous-Contraintes: 6x1 + 10x2 + 2x3 + x4 = 60 2x1 + 10x2 + 6x3 + x5 = 140 xj
0; j = 1; :::; 5
(cid:21)
Max z = 4x1 + 5x2 + 9x3 Sous-Contraintes: x1 + x2 + 2x3 = 16 7x1 + 5x2 + 3x3 xj
(cid:20) 0; j = 1; :::; 3
25
(cid:21)
Exercice 10: (solution primal à partir du dual et inversement)
On considère le programme linéaire suivant:
P2
(cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)
8
>>>>< >>>>:
P1
8
>>>>< >>>>:
(P:L)
8
>>>>>>< >>>>>>:
M in z = 2x1 + 3x2 Sous
Contraintes :
Publicité
(cid:0) 4x1 + x2 x1 + 4x2 7x1 + 10x2 xj
8 8 47 0; j = 1; 2;
(cid:21) (cid:21) (cid:21)
(cid:21)
4
1- Donner le programme dual de P.L. 3- Résoudre le programme dual à l’aide de la méthode du tableau de simplex. 4- Donner le tableau optimal du programme primal à l’aide du tableau opti- mal dual.
Exercice 11 (théorème des écarts complémentaires)
On considère le programme linéaire suivant:
max Z = 3x1 + 4x2 contraintes sous
(cid:0)
2x1 + x2 x1 + 2x2 3x1 + 9x2 xi
2 6 1 0; i = 1; 2
(cid:20) (cid:20) (cid:20)
(cid:21)
(P L)
8
>>>>>>< >>>>>>:
1- Donner une résolution graphique de ce programme linéaire. 2- Ecrire le dual de ce problème et utiliser le théorème des écarts complé- mentaires pour déterminer la solution optimale du dual.
Exercice 12 (DS 2012-2013) Soit le programme linéaire:
max Z = 3x1 + 3x2 + x3 contraintes sous (cid:0) 2x1 + x2 + x3 x1 x3 x1 + x2 + 2x3 x1; x2; x3 0
(cid:20)
(cid:20)
(cid:0)
(cid:21)
2
4
4
(cid:21)
(P )
8
>>>>>>< >>>>>>:
1. Résoudre ce programme à l’aide de la méthode des deux phases. 2.On se place dans le plan x3 = 0.
a- Résolver graphiquement le problème b- Donner le tableau de simplexe correspondant à chacun des points
extrèmes du domaine réalisable. Conclure.
5