Programmation Lineaire, FLIN609 Annee 2008-2009
- Examen du 20 mai 2009. -
- Duree 2h. Seul document autorise : Une feuille
manuscrite recto/verso. Pas de calculatrices. -
- Une large part de la notation prendra en compte la clarte de la
redaction et la rigueur des justications. -
- Exercice 1 - Extrait de Fiche TD1 Licence Info Paris 6
Une personne soucieuse de sa forme physique souhaite absorber chaque jour
36 unites de Vitamine A, 28 unites de Vitamine C et 32 unites de Vitamine D.
Deux marques sont susceptibles de fournir ces apports. La marque 1 co ute 3
euros et procure 2 unites de Vitamine A, 2 unites de Vitamine C et 8 unites de
Vitamine D. La marque 2 co ute 4 euros et procure 3 unites de Vitamine A, 2
unites de Vitamine C et 2 unites de Vitamine D.
Il sagit de trouver la combinaison respectant les exigences dabsorption quo-
tidienne au moindre co ut.
a. Enoncer ce probl`eme sous forme dun programme lineaire (P).
b. Ecrire le dual (D) de (P).
c. Resoudre (D) par la methode du simplexe.
d. Deduire une solution de (P) `a partir du dictionnaire nal de (D).
e. Certier loptimalite de la solution de (P) `a laide de combinaisons de contraintes.
f. Resoudre (P) graphiquement.
- Exercice 2 - Resoudre le programme lineaire suivant avec lalgorithme
du simplexe en deux phases. Certier loptimalite de la solution trouvee.
Maximiser 3x
1
+x
2
Sous x
1
x
2
1
x
1
x
2
3
2x
1
+x
2
4
x
1
, x
2
0
1
Programmation Lineaire, FLIN609 Annee 2008-2009
- Exercice 3 -
Montrer que le programme lineaire suivant admet comme solution optimale
x
1
=
1
5
, x
2
= 0, x
3
= 0, x
4
=
7
5
.
Maximiser x
1
+x
2
+x
3
+x
4
Sous 3x
1
+6x
2
+3x
3
+x
4
2
2x
1
+3x
2
+3x
3
+x
4
4
x
1
+2x
2
+5x
3
+2x
4
3
4x
1
+3x
2
+4x
3
+x
4
5
x
1
, x
2
, x
3
, x
4
0
- Exercice 4 -
On consid`ere deux centrales electriques, chacune de capacite de production
800 megawatt. Ces centrales desservent trois villes dont les besoins en electricite
sont respectivement de 700, 400 et 500 megawatt. Chaque centrale peut fournir
tout ou partie de sa production `a chacune des villes.
Les co uts dacheminement (par megawatt) dans le reseau electrique sont
donnes par le tableau suivant :
Centrale 1 Centrale 2
Ville 1 20 25
Ville 2 15 10
Ville 3 10 15
Le probl`eme est de subvenir aux besoins des villes `a moindre co ut.
a. Modeliser sous forme dun programme lineaire.
b. Proposer une solution de ce probl`eme `a la main.
c. (Hors bareme) Montrer loptimalite de votre solution en proposant un certi-
cat dual.
2
