Université Cadi Ayyad Année universitaire 2019/20

Faculté des Sciences et Techniques - Marrakech Mod. : Rech. operationnelle

Fiche de TD

Exercice 1
On désire déterminer la composition, à coût minimum, d’un aliment pour le bétail composé de maı̈s, de
soja et d’herbe. L’aliment ainsi conditionné devra comporter au plus 0.5% de calcium, au maximum 5% de
fibres et au moins 30% de protéines, pour se conformer au désir de la clientèle. On a indiqué ci-dessous les
pourcentages de calcium, de fibres et de protéines contenus, respectivement, dans le maı̈s et le soja, ainsi
que le coût par tonne de chacun de ces ingrédients (on suppose que le prix de l’herbe est nul et que sa teneur
en calcium, fibres et protéines est négligeable).

Ingrédients Calcium (en %) Fibres (en %) Protéines (en %) Prix (par tonne)
Maı̈s 0.1 2 9 200 euros
Soja 0.2 6 60 600 euros
requis ≤ 0.5 ≤5 ≥ 30
1. Formuler le problème sous la forme d’un programme linéaire PL.
2. Résoudre graphiquement le problème PL. En déduire la composition optimale du mélange et son
coût.

Exercice 2
Un atelier de confection fabrique en série deux modèles de chemises. Une chemise du premier modèle
nécessite 1 mètre de tissu, 4 heures de travail et rapporte 24 euros. Une chemise du deuxième modèle exige
2 mètres de tissu, 2 heures de travail et rapporte 16 euros. Sachant que l’atelier dispose quotidiennement de
150 mètres de tissu et de 400 heures de travail, et qu’il peut vendre toute sa fabrication, combien de lots de
10 chemises de chaque modèle faut-il fabriquer pour obtenir un bénéfice maximal ?

Exercice 3
Résoudre graphiquement les programmes linéaires suivants :

  max 2x1 + x2 ,
min −x1 − 2x2 ,
 

 
 x1 + 2x2 ≤ 6,

 


 −x + x ≤ −2, 
1 2
(P1 ) : (P2 ) : x1 + x2 ≤ 4,
 x1 + x2 ≤ 4,
 



 x1 ≥ 0, x2 ≥ 0.




 x1 ≤ 3,

x1 ≥ 0, x2 ≥ 0.


1/2
Exercice 4
On considère le programme linéaire suivant :


 min −x1 − 2x2 ,


−3x1 + 2x2 ≤ 2,




(L) : −x1 + 2x2 ≤ 4,





 x1 + x2 ≤ 5,

x1 ≥ 0, x2 ≥ 0.


1. Ecrire le programme (L) sous forme standard.

Exercice 5
Résoudre les problèmes de programmation linéaires suivants :

 min −10x1 − 12x2 − 12x3 , 
min −2x1 − x2 ,

 
 
 x1 + 2x2 + 2x3 + x4 = 20,

 

 
 x − x ≤ 2,
1 2
(P1 ) : 2x1 + x2 + 2x3 + x5 = 20, (P2 ) :

  x1 + x2 ≤ 6,




 2x1 + 2x2 + x3 + x6 = 20, 

 xi ≥ 0, i = 1, 2.


xi ≥ 0, i = 1, ..., 6.


On mettra le problème (P2 ) d’abord sous forme canonique en introduisant les variables d’écarts.

Exercice 6
On considère le programme linéaire :


 min 2x1 − x2 + x3 ,


 x1 + x2 − x3 ≥ −2,



(P0 ) : −x1 + x2 + 2x3 ≤ 1,





 x1 + x3 = 1,

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.


1. Ecrire le programme (P0 ) sous forme standard, on note le nouveau programme (P).
2. Montrer que x̄ = ( 31 , 0, 32 , 35 , 0)T est une solution réalisable de base de (P).
3. Résoudre par la méthode du simplexe le programme linéaire (P).
4. Transformer le programme (P0 ) en un programme linéaire à deux variables.
5. Résoudre graphiquement le programme linéaire à deux variables. Comparer la solution obtenue par
la méthode graphique et la solution obtenue par la méthode du simplexe.

2/2