2014/2015

U niversité de M’hamad Bougara de Boumerdès

Faculté des Sciences Département de Mathématiques
Deuxième Année Licence Responsable du Module:
Recherche Opérationnelle Mr. M. BEZOUI

Semestre 04
Série de T D N ◦01 d’Optimisation Linéaire

0.1 Exercices
Exercice 1 (Voir la solution 1). Un artisan menuisier fabrique des tables et des chaises à base du bois et
d’un métal pour le compte d’un revendeur, il emploie deux jeunes stagiaires. Son stock pour la semaine
à venir en bois est 60 m2 et 30 mettre du métal. La fabrication d’une table nécessite 3h du travail et 5
m2 du bois et 2m du métal, et pour fabriquer une chaise il faut 1.5 h du travail et 2 m2 du bois et 1m du
métal. Le menuiser et ses stagiaires travaillent 40 h par semaine, une chaise génère le profit de 2000 DA
et une chaise dégage un profit de 1200 DA. Toute sa production sera vendue le lendemain.

• Modéliser ce problème sous forme d’un programme linéaire afin de maximiser le bénéfice hebdo-
madaire?

Exercice 2 (Voir La solution 2). Une entreprise produit deux types de ceintures A et B. Le type A est
de meilleure qualité que B. le bénéfice est de 200 Da pour le type A et de 150 Da pour le second type. Le
temps de fabrication pour le type A est le double du temps pour la fabrication du type B et si toutes les
ceintures étaient du type B l’entreprise pourrait en fabriquer 1000 par jour. L’approvisionnement en cuir
est suffisant pour 1400 ceintures par jour (Type A et B), 800 boucles de type A et 900 pour le type B sont
disponibles par jour.

• Modéliser ce Problème afin de maximiser le bénéfice total.

Exercice 3 (Voir La solution 3). On doit organiser un pont aérien pour transporter 1600 personnes et 90
tonnes de bagages. Les avions disponibles sont de deux types: 12 du type A et 9 du type B. Le type A
peut transporter, à pleine charge, 200 personnes et 6 tonnes de bagages. Le type B, 100 personnes et 6
tonnes de bagages. La location d’un avion du type A coûte 800.000 F; la location d’un avion du type B
coûte 200.000 F.

✈ Trouver une formulation au problème sus-définit, pour trouver le nombre optimal d’avions de type
A et du type B pour minimiser le coût de location.

Exercice 4 (Voir la solution 4). Un chocolatier−confiseur confectionne des assortiments de chocolats.

Dans ceux-ci il a convenu d’y placer 3 sortes de chocolats dénotés chocolat 1, 2 et 3, dont chaque kg lui
coûte respectivement 400DA, 140, 5DA et 240DA. Chaque assortiment doit peser un kg et se vendra
800DA.
Le chocolat 1 doit représenter entre 10% et 20% du poids d’un assortiment. Le chocolat 1 et 2 présent
dans l’assortiment ne doivent pas peser plus de 800g. Au moins la moitié du poids d’un assortiment doit
parvenir des chocolats 1 et 3.

☞ Quelle proportion de chaque type de chocolats, le chocolatier doit−il utiliser pour maximiser les
revenus nets qu’il tirera de la vente de ses assortiments?

Exercice 5 (Voir la solution 5). Une entreprise disposant de 10 000 m2 de carton en réserve, fabrique et
commercialise 2 types de boîtes en carton. La fabrication d’une boîte en carton de type 1 ou 2 requiert,
respectivement, 1 et 2 m2 de carton ainsi que 2 et 3 minutes de temps d’assemblage. Seules 200 heures
de travail sont disponibles pendant la semaine à venir. Les boîtes sont agrafées et il faut quatre fois plus
d’agrafes pour une boîte du second type que pour une du premier. Le stock d’agrafes disponible permet
d’assembler au maximum 15 000 boîtes du premier type. Les boîtes sont vendues, respectivement, 3$ et
5$.

1. Formuler le problème de la recherche d’un plan de production maximisant le chiffre d’affaires de

l’entreprise sous forme d’un programme linéaire.

2. Déterminer un plan de production optimal en résolvant graphiquement le programme linéaire trouvé

en (1).

Exercice 6 (Voir la solution 6). Un professionnel de tourisme installé au sud a la possibilité de vendre 500
cartes postales et 20 guides touristiques, il possède deux lots publicitaires, lot N1 constitué d’un seul guide
touristique et 10 cartes postales et un lot N2 constitué d’un seul guide touristique et 50 cartes postales,
Son bénéfice unitaire par lot est 60 DA par lot N1 et 100 DA par lot N2 .

• Modéliser ce problème sous forme d’un programme linéaire et combien faut-il constituer de lot de
chaque type pour maximiser le bénéfice total?

Exercice 7 (Voir la solution 7). Pour nourrir sa vache, un paysan dispose de deux poudres alimentaires P1
et P2 composées d’ingrédients A, B et C. Un sac de poudre P1 pèse 900 g et contient 100 g d’ingrédients A,
200 g de B et 600 g de C. Un sac de poudre P2 pèse 600 g et contient 200 g de chacun des trois ingrédients.
Chaque jour, la vache doit consommer au moins 300 g de A, 500 g de B et 700 g de C. Les prix respectifs
par kg de P1 et P2 sont respectivement 300 DA, et 200 DA.

• Quelle dépense journalière minimale le paysan doit-il envisager, de sorte que sa vache reçoive une
nourriture suffisante?

Exercice 8 (Voir la solution 8). Un oléiculteur désire exporter deux types de l’huile d’olive, huile d’olive
ordinaire et huile d’olive de haute qualité. Compte tenu des réglementations en vigueur des exportations,
il n’a la possibilité de vendre qu’au maximum 5000 litres de l’huile ordinaire et 1000 litres de l’huile de
qualité par année. Il propose à ses clients trois types de packs (fardeaux).

a Pack 1 est composé de deux bouteilles (1litre) d’huile simple et de quatre bouteilles d’huile de qualité.
La marge brute par pack 1 est de 4 dollar.

b Pack 2 est composé de six bouteilles d’huile de qualité. La marge brute par pack 2 est de 10 dollar.

c Pack 3 est composé de six bouteilles d’huile ordinaire. La marge brute par pack 3 est de 3 dollar.

• Aider cet oléiculteur à savoir combien de pack de chaque type doit-il constituer afin de maximiser
son bénéfice annuel?

Exercice 9 (Voir la solution 9). Une entreprise d’investissement souhaite investir exactement 100000
dollars dans 3 projets différents, elle souhaite investir 60000 dollars dans l’achat d’un bien immobilier qui
génère un bénéfice de 2900 dollars et dans l’achat d’actions boursières qui coûtent 2000 dollars/action
et dégage un profit de 800 dollars/action et dans l’achat de lot de terrain qui coûtent 300 dollars/m2 et
génère un profit de 100 dollars.

• Modéliser ce problème afin de trouver le profit maximum de cet investissement?

Exercice 10 (Voir la solution 10). Une usine dispose de trois machines A, B et C. La machine A permet
de faire de la gelée d’abricots, la machine B de la confiture de fraises et de la gelée de fraises et la machine
C traite les déchets produits par A et B.
La machine A est alimentée par un mélange composé à 60% d’abricots et à 40% de sucre et peut traiter
au plus 15 tonnes de mélange par jour ; pour une tonne de mélange, elle produit 800kg de gelée et 200kg
de déchets. La machine B est alimentée par un mélange composé à 80% de fraises et à 20% de sucre et
peut traiter au plus 10 tonnes de mélange par jour ; pour une tonne de mélange, elle produit 600kg de
confiture, 300kg de gelée et 100kg de déchets.
 Tous ces déchets doivent être éliminés à l’aide de la machine C qui peut en traiter au plus 2 tonnes
par jour.
L’usine achète des abricots, des fraises et du sucre aux prix respectifs de 3000$, 3500$ et 1200$ la
tonne. Elle vend la tonne de gelée d’abricots à 4500$, celle de gelée de fraises à 5000$ et celle de confiture
de fraises à 4000$.
On recherche un plan de production journalier maximisant le bénéfice de l’usine.

1. Formuler ce problème sous la forme d’un programme linéaire (PL).

2. Déterminer un plan de production journalier optimal en résolvant graphiquement le PL.

Corrections
Solution 1.
Variables de décision

1. x1 le nombre de tables à fabriquer par semaine.

2. x2 le nombre de chaises à fabriquer par semaine.

Les contraintes

• 5x1 + 2x2 ≤ 60 pour le bois

• 2x1 + 1x2 ≤ 30 pour le métal

• 3x1 + 1.5x2 ≤ 45 pour le temps du travail

• les variables sont non-négatives x1 , x2 ≥ 0

La fonction objectif
La fonction objectif est Z(x1 , x2 ) = 2000x
 1 + 1200x2 à maximiser.

 Z(max) = 2000x1 + 1200x2
 5x1 + 2x2 ≤ 60


Enfin, le PL peut s’écrire comme suit: 2x1 + 1x2 ≤ 30
3x1 + 1.5x2 ≤ 45




x 1 , x2 ≥0


Solution 2.
Variables de décision

1. x1 le nombre de ceintures de type A à fabriquer par jour.

2. x2 le nombre de ceintures de type B à fabriquer par jour.

Les contraintes

• 2x1 + x2 ≤ 1000 pour le temps

• x1 + x2 ≤ 1400 pour le cuir

• x1 ≤ 800 pour les boucles de type A.

• x2 ≤ 900 pour les boucles de type B.

• les variables sont non-négatives x1 , x2 ≥ 0

La fonction objectif
La fonction objectif est Z(x1 , x2 ) = 200x
1 + 150x2 à maximiser.

 Z(max) = 200x1 + 150x2
2x1 + x2 ≤ 1000




x1 + x2 ≤ 1400

Enfin, le PL peut s’écrire comme suit:

 x 1 ≤ 800
x2 ≤ 900




x 1 , x2 ≥0


Solution 3.
Variables de décision

1. x1 Le nombre d’avions loués du type A.

2. x2 le nombre d’avion loués de type B.

Les contraintes

• x1 ≤ 12 Nombre d’avions disponibles du type A.

• x1 ≤ 9 Nombre d’avions disponibles du type B.

• 200x1 + 100x2 ≥ 1600 Toutes les personnes doivent être transportées.

• 6x1 + 6x2 ≥ 90 Tous les bagages doivent être transportés.

• les variables sont non-négatives x1 , x2 ≥ 0

La fonction objectif
La fonction objectif est Z(x1 , x2 ) = 800000x
 1 + 200.000x2 à minimiser.

 Z(max) = 800.000x1 + 200.000x2
x1 ≤ 12




x2 ≤9

Enfin, le PL peut s’écrire comme suit:

 200x1 + 100x2 ≥ 1600
6x + 6x2 ≥ 90


 1


x 1 , x2 ≥0
Solution 4.
Variables de décision

1. x1 La quantité de chocolat 1 dans l’assortiment (en Kg).

2. x2 La quantité de chocolat 2 dans l’assortiment (en Kg).

3. x3 La quantité de chocolat 3 dans l’assortiment (en Kg).

Pour se faire, on note "A", l’assortiment réalisé, A = x1 + x2 + x3 . Les contraintes

• 0.10 ∗ A ≤ x1 ≤ 0.20 ∗ A quantité du chocolat 1 dans l’assortiment.

• x1 + x2 ≤ 0.800 La quantité du chocolat 1 et 2 dans un kg de l’assortiment.

1
• x1 + x2 ≥ 2
∗ A Quantité du chocolat 1 et 3.

• les variables sont non-négatives x1 , x2 , x3 ≥ 0

La fonction objectif
La fonction objectif est Z(x1 , x2 , x3 ) = 800(x1 + x2 + x3 ) − 400x1 − 140, 5x2 − 240x3 à maximiser.
Enfin, le PL peut s’écrire comme suit:


 Z(max) = 800(x1 + x2 + x3 ) − 400x1 − 140.5x2 − 240x3
0.10 ∗ (x + x + x ) ≤ x ≤ 0.20 ∗ (x1 + x2 + x3 )

1 2 3 1


x1 + x2 ≤ 0.800
x1 + x2 ≥ 12 ∗ (x1 + x2 + x3 )




x 1 , x2 , x3 ≥0


Solution 5. 1. Formuler le problème de la recherche d’un plan de production maximisant

le chiffre d’affaires de l’entreprise sous forme d’un programme linéaire.

(a) Soient les variables de décision suivantes:

x1 : le nombre de boîtes de type 1 fabriquées;
x2 : le nombre de boîtes de type 2 fabriquées.
(b) On a les contraintes suivantes:
sur les m2 de carton: x1 + 2x2 ≤ 10000
sur le temps d’assemblage en minutes : 2x1 + 3x2 ≤ 200 × 60
sur le nombre d’agrafes: x1 + 4x2 ≤ 15000
(c) La fonction objectif à maximiser correspond au chiffre d’affaires obtenu lors de la vente des
cartons: z = 3x1 + 5x2

On a donc le programme linéaire suivant :

Z(max) = 3x1 + 5x2

s.c x1 + 2x2 ≤ 10000
2x1 + 3x2 ≤ 12000
x1 + 4x2 ≤ 15000
x 1 , x2 ≥ 0

2. Déterminer un plan de production optimal en résolvant graphiquement le programme

linéaire trouvé en (1).
Il suffit de représenter le domaine admissible D du programme linéaire trouvé en (1) et de trouver
sur le bord de D le point qui maximise 3x1 + 5x2 , c’est-à-dire de faire glisser la droite d’équation
3x1 +5x2 = α jusqu’à ce que α soit maximal en prenant garde que cette droite intersecte le domaine
 D, 
3
ou bien de prendre le dernier point toucher par les droites perpendiculaires au gradient ∇Z = .
5
Ceci est fait sur la figure ci-dessous, et l’on voit que le plan optimal consiste donc à produire 600
boîtes de type 1 (x∗1 = 600) et 3 600 boîtes de type 2 (x∗2 = 3600), pour un chiffre d’affaires d’une
valeur de 19800$ (z ∗ = 19800).

Solution 6.
Variables de décision

1. x1 le nombre de lots de type Nj à constituer, j=1,2.

Les contraintes

• x1 + x2 ≤ 20 pour les guides

• 10x1 + 50x2 ≤ 500 pour les cartes postales

 Figure 1: Résolution graphique du problème (P)

• les variables sont non-négatives x1 , x2 ≥ 0

La fonction objectif
La fonction objectif est Z(x1 , x2 ) = 60x1 + 100x2 à maximiser.
Enfin,
 le PL peut s’écrire comme suit:

 Z(max) = 60x1 + 100x2
x1 + x2 ≤ 20


 10x 1 + 50x 2 ≤ 500
x 1 , x2 ≥0


Solution 7.
Variables de décision

1. xj nombre de sac de poudre Pj à acheter, j=1,2.

Les contraintes

• 100x1 + 200x2 ≥ 300 pour l’ingrédient A.

• 200x1 + 200x2 ≥ 500 pour l’ingrédient B.

• 600x1 + 200x2 ≥ 700 pour l’ingrédient C.

• Les variables sont non-négatives x1 , x2 ≥ 0

La fonction objectif
La fonction objectif est Z(x1 , x2 ) = 300 ∗ 0.9 ∗ x1 + 200 ∗ 0.6 ∗ x2 à maximiser.
Il suffit d’appliquer la règle de trois pour trouver les prix en Kg.
Enfin,
 le PL peut s’écrire comme suit:

 Z(max) = 60x1 + 100x2
100x + 200x ≥ 300

1 2


200x1 + 200x2 ≥ 500
600x1 + 200x2 ≥ 700




x 1 , x2 ≥0

Remarque 1. On peut aussi prendre comme variable de décision, les quantité à acheté en Kg, mais, il
faut faire attention à exprimer toute les contraintes en Kg.

Solution 8.
Variables de décision

1. xj nombre de packs (Fardeaux) de type Fj à exporter, j = 1, 3.

Les contraintes

• 2x1 + 6x2 ≤ 5000 pour l’huile simple.

• 4x1 + 6x3 ≤ 1000 pour l’huile de qualité.

• Les variables sont non-négatives x1 , x2 , x3 ≥ 0

La fonction objectif
La fonction objectif est Z(x1 , x2 ) = 4x1 + 10x2 + 3x3 à maximiser.
Enfin,
 le PL peut s’écrire comme suit:

 Z(max) = 4x1 + 10x2 + 3x3
2x1 + 6x2 ≤ 5000


 4x1 + 6x3 ≤ 1000
x 1 , x2 , x3 ≥0


Solution 9.
Variables de décision


1, Si le bien immobilier est acheté
1. x1 = x2 nombre d’actions achetées,
0, Sinon

2. x3 nombre de m2 de terre achetées,

3.

Les contraintes

• 60000x1 + 2000x2 + 300x3 = 10000 Il ne faut pas dépasser le budget alloué.

• Les variables sont non-négatives et d’intégrité x1 , x2 , x3 ≥ 0, x1 ∈ {0, 1}, x2 ∈ N

La fonction objectif
La fonction objectif est Z(x1 , x2 ) = 2900x1 + 800x2 + 100x3 à maximiser.
Enfin,
 le PL peut s’écrire comme suit:
 Z(max) = 2900x1 + 800x2 + 100x3
60000x1 + 2000x2 + 300x3 = 100000
x 1 , x2 , x 3 ≥ 0 x1 ∈ {0, 1}, x2 ∈ N


Remarque 2. Si vous mettez aussi xi ∈ N , est acceptable comme réponses.

Solution 10.
Soit les variables de décision:

• x1 = tonnes de mélange traitées par la machine A,

• x2 = tonnes de mélange traitées par la machine B,

On en déduit :

• la quantité d’abricots à acheter : 0.6x1

 • la quantité de fraises à acheter : 0.8x2
• la quantité de sucre à acheter : 0.4x1 + 0.2x2
• la quantité de gelée d’abricots produite : 0.8x1
• la quantité de confiture de fraises produite : 0.6x2
• la quantité de gelée de fraises produite :0.3x2
• la quantité de déchets produits : 0.2x1 + 0.1x2
Toutes ces quantités sont exprimées en tonnes.
On a donc la fonction objectif suivante, correspondant au bénéfice journalier en $:
Z = 4500.0, 8x1 + 5000.0, 3x2 + 4000.0, 6x2 − 3000.0, 6x1 ..3500.0, 8x2 − 1200(0, 4x1 + 0, 2x2 )
= 1320x1 + 860x2
Les contraintes sur les machines A, B et C:
x1 ≤ 15
x2 ≤ 10
0, 2x1 + 0, 1x2 ≤ 2
Le programme linéaire à résoudre est donc:

max Z = 1320x1 + 860x2

s.c. x1 ≤ 15
x2 ≤ 10
0, 2x1 + 0, 1x2 ≤ 2
x 1 , x2 ≥ 0

Figure 2: Représentation graphique du problème

La solution optimale est donnée par :

z ∗ = 15200, x∗1 = 5, et x∗2 = 10.
ce qui correspond à fournir 5 tonnes de mélange à la machine A et 10 tonnes de mélange à la machine
B pour un bénéfice journalier de 15200$.
On peut aussi formuler le problème avec comme variables de décisions: x1 , x2 qui représen-
tent le nombre de tonnes d’abricots et de fraises achetés chaque jour par l’usine. Ou, la
quantité de gelée d’abricots et de fraises produite en tonnes