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, dun aliment pour b -
tail qui est obtenu en m langeant au plus trois produits bruts: orge, arachide
et s same. Laliment 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 lorge, 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, dun tonne daliment
conforme aux exigences de la client le, donner une formulation du probl me
pos sous forme dun 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 lensemble 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.
Publicité
d- D terminer graphiquement lensemble 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
>>>>>><
>>>>>>:
>>>><
>>>>:
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
>>>>>><
>>>>>>:
Publicité
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 laide 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 lapplication 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 dune application lautre. Prenons
le cas o les coe cients de la fonction co t Z varient en fonction dun facteur
ext rieur (prix dune mati re premi re, taux dint 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
2(cid:21))x1 + (5 + (cid:21))x2
contraintes
(cid:0)
(cid:0)
x1 + x2
Publicité
(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 :
(cid:0)
4x1 + x2
x1 + 4x2
7x1 + 10x2
Publicité
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 laide de la m thode du tableau de simplex.
4- Donner le tableau optimal du programme primal laide 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:0)
(cid:21)
(cid:20)
(cid:20)
4
2
4
(cid:21)
(P )
8
>>>>>><
>>>>>>:
1. R soudre ce programme laide 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