INTRODUCTION À LA PROGRAMMATION LINÉAIRE 11

3. Introduction à la programmation linéaire

La programmation linéaire est une branche de l'optimisation permettant de résoudre de nombreux problèmes
économiques et industriels.

3.1. L'artisan chocolatier

À l'approche des fêtes de Pâques, un artisan chocolatier décide de confectionner des
Remarque œufs en chocolat. En allant inspecter ses réserves, il constate qu'il lui reste 18 kg de
Le chocolat est composé de cacao, 8 kg de noisettes et 14 kg de lait.
beaucoup plus d'ingrédients Il a deux spécialités : l'œuf Extra et l'œuf Sublime. Un œuf Extra nécessite 1 kg de
(notamment du sucre), mais, cacao, 1 kg de noisettes et 2 kg de lait. Un œuf Sublime nécessite 3 kg de cacao, 1 kg de
pour la clarté de l'exemple, on noisettes et 1 kg de lait.
s'est ici limité à trois. Il fera un profit de 20 fr. en vendant un œuf Extra, et de 30 fr. en vendant un œuf
Sublime.
Combien d'œufs Extra et Sublime doit-il fabriquer pour faire le plus grand bénéfice
possible ?
Formulation du problème
Notons x1 le nombre d'œufs Extra et x2 le nombre d'œufs Sublime à produire. Le
chocolatier cherche à maximiser la fonction objectif :
C'est l'expression du bénéfice.
max z = 20x1 + 30 x2
Étant données les réserves du chocolatier, les contraintes suivantes devront être
L'artisan ne peut pas utiliser
satisfaites :
plus de :

{
18 kg de cacao x1  3 x2 ≤ 18
8 kg de noisettes x1  x2 ≤ 8
14 kg de lait. 2 x1  x2 ≤ 14
Il ne peut pas produire un
nombre négatif d'œufs !
Évidemment, on a encore les deux contraintes : x1 ≥ 0 et x2 ≥ 0.
Une inéquation définit un demi-plan où la condition est satisfaite (voir chapitre 4).

Démarche Résolution graphique

1. On dessine les demi-plans des
contraintes. On trace la droite
frontière et on indique par un petit
triangle le demi-plan défini par
l'inéquation (la droite frontière est
obtenue en remplaçant ≤ par =).
2. On détermine le domaine D
définissant l'ensemble des points
satisfaisant toutes les contraintes. Le
domaine D est l'intersection de tous
les demi-plans.
3. On trace la droite représentant la
fonction objectif et passant par
l'origine.
4. On translate la droite de la fonction
objectif selon son vecteur normal,
ici (20, 30).
5. Le point optimal est le dernier point
du domaine D que la droite de la
fonction objectif touchera lors de
son déplacement.

Didier Müller - LCP - 2013 Cahier Algèbre linéaire

12 CHAPITRE 3

Truc pour repérer rapidement Réponse au problème

le bon demi-plan défini par Le point optimal est (3 ; 5), ce qui signifie que x1=3 et x2=5.
une inéquation : S'il veut maximiser son bénéfice, le chocolatier doit donc confectionner 3 œufs Extra et
regarder si le point (0 ; 0) est 5 œufs Sublime.
du bon côté de la droite Son bénéfice sera de 20·3 + 30·5 = 210 fr.
frontière. Il utilisera 18 kg de cacao, 8 kg de noisettes et 11 kg de lait.

1. Dans cet exemple introductif, le résultat est en nombres entiers, ce n'est de loin pas
Remarques toujours le cas.
générales
2. On constate que le chocolatier va utiliser complètement deux de ces trois
ingrédients.
Une autre méthode (plus sûre
mais plus longue) pour trouver 3. Seuls les couples (x1 ; x2) ∈ D satisfont toutes les contraintes. Mais en fait, la solution
le point optimal consisterait à optimale sera toujours l'un des sommets du polygone délimitant le domaine D.
tester tous les sommets et garder 4. Faites un dessin suffisamment grand pour être précis. Ne le placez pas tout en bas de
le meilleur. votre feuille, car vous serez embêté pour dessiner la droite de la fonction objectif.
5. Le vecteur normal de la droite définissant la fonction objectif indique le sens dans
lequel on doit la translater pour trouver le point optimal.
Il se trouve facilement : la droite ax1 + bx2 + c a pour vecteur normal
a
b
.
6. Si le vecteur normal indique un déplacement vers le haut, la fonction objectif doit
couper l'axe Ox2 le plus haut possible dans le cas d'une maximisation, et le plus bas
possible dans le cas d'une minimisation, tout en touchant le domaine D.

7. Si le vecteur normal indique un déplacement vers le bas, la fonction objectif doit

couper l'axe Ox2 le plus bas possible dans le cas d'une maximisation, et le plus haut
Voir l'exercice 3.8
possible dans le cas d'une minimisation, tout en touchant le domaine D.

8. Si le vecteur normal est un vecteur horizontal (cas rare mais possible), la fonction
objectif ne coupera pas l'axe Ox2. Le point optimal sera, selon les cas, le plus éloigné
ou le plus proche de l'axe Ox2.

Cahier Algèbre linéaire Didier Müller - LCP - 2013

 INTRODUCTION À LA PROGRAMMATION LINÉAIRE 13

3.2. Exercices
Pour chacun des exercices, donnez la fonction objectif à maximiser ou à minimiser, énumérez toutes les contraintes,
déterminez graphiquement la solution et calculez-la algébriquement.

Une entreprise suisse fabrique deux produits qu'elle désire vendre aux USA.
Exercice 3.1 Le produit A rapporte 400 fr./kg et le produit B rapporte 600 fr./kg.
Ayant des moyens financiers limités, la société ne peut affréter qu'un seul avion. Celui-
ci ne peut transporter que 50'000 kg et a un volume de 2000 m3.
Le produit A a un volume de 0.032 m3 par kg ; le produit B a un volume de 0.1 m3 par
kg.
Combien de kg de chaque produit l'entreprise doit-elle mettre dans l'avion afin de
maximiser ses gains ?

Pour produire des pièces de fonte, une entreprise dispose d'une fonderie et d'un atelier
Exercice 3.2 de mécanique. On donne le tableau des consommations suivant :

Fonderie Atelier Énergie Recette par tonne

Une tonne de pièces de type 1 10 h 5h 14 kWh 2000 fr.
Une tonne de pièces de type 2 12 h 4h 30 kWh 3000 fr.
Quantités disponibles 100 h 45 h 210 kWh –

Combien de tonnes de pièces de chaque type faut-il fabriquer pour maximiser la

recette ?

Une menuiserie s'est spécialisée dans la fabrication de boîtes en bois. En prévision d'une
Exercice 3.3 grosse commande, elle décide de remplir ses stocks.
Un ouvrier produit de grandes boîtes rouges et un autre de petites boîtes jaunes.
Chaque boîte rouge a un volume de 20 dm3, chaque boîte jaune a un volume de 10 dm3.
L'armoire prévue pour stocker les boîtes a un volume de 4000 dm3.
Pour des raisons techniques, le premier ouvrier ne peut produire au maximum que 150
boîtes rouges et le deuxième que 200 boîtes jaunes.
Sachant que les boîtes rouges rapportent 80 fr. et les boîtes jaunes 30 fr., combien la
menuiserie doit-elle fabriquer de boîtes rouges et de boîtes jaunes pour maximiser son
profit ?

Un fabricant de raquettes de tennis fait un bénéfice de 8 fr. sur chaque raquette ordinaire
Exercice 3.4 et de 15 fr. sur chaque grande raquette. Pour satisfaire à la demande des vendeurs, la
production journalière de raquettes ordinaires devrait se situer entre 30 et 80, et la
production journalière de grandes raquettes entre 10 et 30. Pour maintenir une bonne
qualité, le nombre total de raquettes produites ne devrait pas dépasser 80 par jour.
Combien de raquettes de chaque type faudrait-il fabriquer quotidiennement pour réaliser
un bénéfice maximum ?

Pour nourrir sa vache, un paysan dispose de deux poudres alimentaires P1 et P2

Exercice 3.5 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 3 fr. et 2 fr.
Quelle dépense journalière minimale le paysan doit-il envisager, de sorte que sa vache
reçoive une nourriture suffisante ?

Didier Müller - LCP - 2013 Cahier Algèbre linéaire

14 CHAPITRE 3

Un teinturier dispose de deux différents produits sous forme de poudre pour colorer du
Exercice 3.6
tissu brut en couleur indigo. Ces deux produits, IND1 et IND2, contiennent trois
substances différentes :
La substance A est contenue à raison de 500 g par kg de poudre dans IND1 et à raison
de 400 g par kg de poudre dans IND2.
La substance B est contenue à raison de 150 g par kg de poudre dans IND1 et à raison
de 50 g par kg de poudre dans IND2.
La substance C n'est contenue que dans le produit IND1 et ceci à raison de 20 g par kg.
Dans un bain qui permet de teinter 10 kg de tissu, il faut au moins 500 g de la substance
A, 100 g de B et 5 g de C. De plus, la quantité de substance C ne doit pas dépasser 15 g
par bain.
Sachant que le produit IND1 coûte 20.- par kg et que le produit IND2 coûte 40.- par kg,
quel est le prix minimal que le teinturier devra payer pour pouvoir colorer 10 kg de
tissu ?

Un distributeur de lecteurs de DVD a deux entrepôts E1 et E2. Il y a 80 unités

Exercice 3.7 entreposées à E1 et 70 unités à E2. Deux clients, A et B, commandent respectivement
35 et 60 unités. Les coûts de transport à partir de chaque entrepôt jusque chez A et B
sont déterminés en fonction du tableau ci-dessous :

Entrepôt Client Coût de transport par unité

E1 A 8 fr.
E1 B 12 fr.
E2 A 10 fr.
E2 B 13 fr.

Comment répartir la commande pour que le coût de transport soit minimum ?

Trois substances X, Y et Z contiennent chacune quatre ingrédients A, B, C et D. Le

Exercice 3.8 pourcentage de chaque ingrédient et le coût, en centimes par gramme, de chaque
substance sont indiqués dans le tableau ci-dessous :

Ingrédients Coût par

Substance A B C D gramme
X 20% 10% 25% 45% 25 ct.
Y 20% 40% 15% 25% 35 ct.
Z 10% 20% 25% 45% 50 ct.

a. Si le coût doit être minimal, combien de grammes de chaque substance faudrait-il

amalgamer pour obtenir un mélange de 20 grammes contenant au moins 14% de A,
16% de B et 20% de C?
b. Quel serait le mélange le plus coûteux ?

Peut-il y avoir plusieurs solutions optimales à un problème de programmation linéaire ?

Exercice 3.9
Si oui, quand cela arrive-t-il ?
Si non, pourquoi cela ne peut-il pas arriver ?

3.3. Ce qu'il faut absolument savoir

Poser et résoudre graphiquement un problème d'optimisation linéaire ❏ ok

Cahier Algèbre linéaire Didier Müller - LCP - 2013