RechercheOpérationnelle:TD1

Exercice 1.
Une usine fabrique 2 produits P1 et P2 en utilisant un certain nombre de ressources : équipement,
main d’œuvre, matières premières. Ces besoins sont indiqués dans le tableau ci-dessous. Par ailleurs,
chaque ressource est disponible en quantité limitée (cf. tableau).

P1 P2 disponibilité
Équipement 3 9 81
Main d’œuvre 4 5 55
Matière première 2 1 20

Les deux produits P1 et P2 rapportent à la vente respectivement des bénéfices de 6$ et 4$ par unité.
1. Formuler algébriquement le PL ainsi posé.

– Choix des variables : x1 et x2 sont respectivement les quantités des produits P1 et P2

fabriqués.
– Choix de la fonction objectif : Pour x1 quantité de P1, on aura un profit de 6x1 et pour x2
quantité de P2, on aura 4x2 .
Le bénéfice total est alors Z=6x 1 +4x 2
– Les contraintes :
L’équipement : on utilise 3x1 pour x1 de P1 et 9x2 pour x2 de P2 et au total on utilise
3x1 +9x 2 de l’équipement et qui ne doit pas dépasser 81.
Main d’œuvre : on utilise 4x1 pour x1 de P1 et 5x2 pour x2 de P2 et au total on utilise
4x1 +5x 2 de main d’œuvre qui ne doit pas dépasser 55.
Matières premières : On utilise 2x1 pour x1 de P1 et 1x2 pour x2 de P2 et au total on
utilise 2x1 +1x 2 de Matières premières qui ne doit pas dépasser 20.
Plus la positivités des variables : x1 , x2 ≥ 0.
En résumé, le problème de production se modélise sous la forme

max
 z=6x 1 +4x 2

 3x1 + 9x 2 ≤ 81
4x1 + 5x 2 ≤ 55

s.c

 2x1 + x2 ≤ 20
x1 , x2 ≥ 0


2. Déterminez graphiquement l’ensemble des solutions admissibles.

Dans le cas d’un PL à deux variables, on peut résoudre le problème par la méthode graphique.
Les contraintes avec des inégalités corrsepondent géométriquement à des demi-plans.
L’intersection de ces demi-plans forme l’ensemble des solutions admissibles (réalisables) (la
partie coloriée)

1
 Pour déterminer la solution optimale, on fait glisser la droite (z = 6x1 + 4x2 )(translation
parallèle à la direction de la droite) du bas (z = 6x1 + 4x2 = 0) vers le haut jusqu’à rencontrer
le point optimal.
3. Quelles quantités de produits P1 et P2 doit produire l’usine afin de maximiser le bénéfice total
venant de la vente des 2 produits ?
Graphiquement, on trouve les coordonnées de la solution optimale(voir la question précédente)
x = (x1 , x2 ) = (15/2, 5)
4. Donnez le profit maximal.
Le profit maximal est donc Zmax = 6 ∗ 15/2 + 4 ∗ 5 = 65

Exercice 2.
On se propose de réaliser une alimentation économique pour des bestiaux, qui contient obligatoi-
rement 4 sortes de composants nutritifs, A, B, C et D. L’industrie alimentaire produit précisément
deux aliments M et N qui contiennent ces composants :
1 Kg d’aliment M contient 100 g de A, 100 g de C, 200 g de D ;
1 Kg d’aliment N contient 100 g de B, 200 g de C, 100 g de D.
Un animal doit consommer par jour au moins 0.4 Kg de A, 0.6 Kg de B, 2 Kg de C et 1.7 Kg de D.
L’aliment M coûte 10$ le Kg et N coûte 4$ le Kg.
1. Formuler algébriquement le PL ainsi posé.
On peut résumer toutes les données du problème dans le tableau suivant
M N Quantités prescrites
A 0.1 0 0.4
B 0 0.1 0.6
C 0.1 0.2 2
D 0.2 0.1 1.7
Coût 10 4
Les variables de décision sont
- x1 : la quantité d’aliments M
- x2 : la quantité d’aliments N
Les contraintes de positivité sont x1 , x2 ≥ 0.
On utilise la composante nutritif A dans l’aliment M (0.1x1 ) et dans l’aliment N(0x2 ), au total

2
 0.1x1 + 0x2 ≥ 0.4 ← consommation minimale de A par l’animal
On utilise la composante nutritif B dans l’aliment M (0x1 ) et dans l’aliment N(0.1x2 ), au total
0x1 + 0.1x2 ≥ 0.6 ← consommation minimale de B par l’animal
On utilise la composante nutritif C dans l’aliment M (0.1x1 ) et dans l’aliment N(0.2x2 ), au
total 0.1x1 + 0.2x2 ≥ 2 ← consommation minimale de C par l’animal
On utilise la composante nutritif D dans l’aliment M (0.2x1 ) et dans l’aliment N(0.1x2 ), au
total 0.2x1 + 0.1x2 ≥ 1.7 ← consommation minimale de C par l’animal
La fonction objectif est une fonction coût : z = 10x1 + 4x2 .
Le programme linéaire est un programme de minimisation :
min
 z = 10x1 + 4x2

 x1 + 0x2 ≥ 4
0x 1 + 1x2 ≥ 6



s.c 1x1 + 2x2 ≥ 20
2x1 + 1x2 ≥ 17




x1 , x2 ≥ 0


2. Déterminez graphiquement les quantités d’aliments M et N doit-on utiliser par jour et par
animal pour réaliser l’alimentation la moins coûteuse ?

La solution optimale est x = (4, 9).

3. Donnez le coût minimal.
Le coût minimal est Zmin = 10 ∗ 4 + 4 ∗ 9 = 76

Exercice 3.
Soit le programme linéaire suivant :

max z = x1 + 3x2



 x1 + x2 ≤ 14


 −2x + 3x

≤ 12
1 2
s.c
 2x1 − x2

 ≤ 12


≥0

 x1 , x2

3
Déterminez, en utilisant l’interprétation géométrique :
1. L’ensemble des solutions réalisables du PL : Polyèdre (OABCD), voir la figure suivante

2. Les sommets de l’ensemble des solutions admissibles et la solution optimale

Les sommets sont O, A, B, C, D. La solution optimale est x = (6, 8)
3. Dans la fonction objectif on change le coefficient (c2 = 3) par c (z = x1 + cx2 ). Pour quelles
valeurs de c le problème PL possède
– une infinité de solutions
– une solution autre que celle trouvée en 2.
La solution optimale ne change pas si :
pente(x1 + x2 = 4) < pente(x1 + cx2 ) < pente(−2x1 + 3x2 = 12) c’est-à-dire
−1 < − 1c < 2/3 =⇒ c > 1 et c > −3/2 ce qui implique c > 1.
Donc si c > 1, la solution optimale ne change pas .
Si c = 1 alors z = x1 + x2 . Cette droite devienne parallèle avec la droite x1 + x2 = 14 ce qui
donne une infinité de solution,
Si 0 < c < 1, on aura une solution autre que celle trouvée en 2.

Exercice 4.
Soit le programme linéaire suivant :

max z = 3x1 + 2x2




 2x1 + x2 ≤ 4


 −2x + x ≤ 2

1 2
s.c


 x1 − x2 ≤ 1


x1 , x2 ≥ 0



1. Résoudre le problème par la méthode graphique. Quelle est la solution optimale et la valeur
maximale de la fonction économique ?

4
 La solution optimale est x = (0.5, 3) et la profit maximal est Zmax = 0.5 ∗ 3 + 2 ∗ 3 = 7.5
2. Donner les coordonnées des sommets de l’ensemble des solutions admissible
Les sommets avec les coordonnées :
O(0,0), A(1,0), B(5/3,2/3), C(0.5,3), D(0,2). Pour le B, on résout le système suivant :

2x1 + x2 = 4
x1 − x2 = 1

Par élimination (la somme des equations 1 et 2) on a x1 = 5/3 et si on remplace x1 on obtient

x2 = 2/3.
3. Quelles sont les valeurs du second membre b1 (dans la première contrainte), pour lesquelles la
solution optimale initiale ne change pas ?
La solution optimale se strouve à l’intersection entre le droite 2x1 + x2 = b1 = 4 et la droite
−2x1 + x2 = 2 c’est-à-dire ces deux contraintes sont saturées et tout changement du second
membre de ces équations entraine nécessairement un changement de solution optimale. La seule
valeur de b1 qui laisse la solution optimale initiale inchangée est la valeur initiale de b1 = 4.
4. Pour quelles valeurs du second membre b2 (dans la deuxième contrainte), l’ensemble des solu-
tions réalisables est
– vide
Si la droite −2x1 + x2 = b2 dépasse le point B vers le bas
(c-à-d b2 < −2 ∗ 5/3 + 2/3 = −8/3) alors l’ensemble admissible est vide.
– contient une seule solution
Si la droite −2x1 + x2 = b2 dépasse le point B(5/3,2/3) vers le haut
(c-à-d b2 > −2 ∗ 5/3 + 2/3 = −8/3) au aura toujours une seule solution optimale.

5. Pour quelles valeurs du coefficient c1 de la fonction objectif, le PL admet plus qu’une solution ?
La solution optimale ne change pas si :
pente(2x1 + x2 = 4) < pente(cx1 + 2x2 ) < pente(−2x1 + x2 = 2) c’est-à-dire

5
−2< − 2c <2= ⇒ 0<c<4 .
Donc si 0<c<4 , la solution optimale ne change pas .
Si c=4 alors on aura une infinité de solutions,
Si 4<c , on aura une solution autre que celle trouvée auparavant.

6
Exercice 6.
Un conseiller financier doit choisir pour un club d’investissement un certain nombre d’actions
dans lesquelles investir. Le club souhaite investir 100 000$ dans six actions différentes. Le conseiller
lui indique le retour d’investissement (taux de retour) qu’il peut espérer pour une période de six
mois. Le tableau suivant donne pour chaque action son nom, sa catégorie (T : technologique, N :
non technologique) et le taux de retour espéré. Le club impose certaines contraintes au conseiller.
Il veut investir au moins 5 000 $ et au plus 40 000$ dans chaque action. Le club d’investissement
désire investir la moitié de son capital dans les actions françaises et au plus 30% dans des valeurs
technologiques.
No Nom catégorie Retour
1 Dash Associates (UK) T 5.3%
2 Ilog France (F) T 6.2%
3 France Telecom(F) T 5.1%
4 General Motor (USA) N 4.9%
5 Elf (F) N 6.5%
6 BNP(F) N 3.4%
Comment doit se répartir le capitale entre chaque action pour espérer le meilleur retour sur in-
vestissement ? (formuler le problème par un programme linéaire puis le résoudre avec le solveur
d’Excel)
Voir le fichier Excel TD1EXE6.xlsx