Cycle Ingénieur

TD N° 1
R.O : Programmation linéaire

Exercice 1

1. Résoudre les programmes linéaires suivants par la méthode du Simplexe :

[M ax]z
 = x1 + 2x2 [M ax]z
 = 3x1 + 3x2 + 4x3
x1 + 3x2 ≤ 21
x1 + x2 + 2x3 ≤ 4


 2x1 + 3x2 ≤ 5

 

2x1 + 3x3 ≤ 5

sc −x1 + 3x2 ≤ 18 sc
2x1 + x2 + 3x3 ≤ 7
x 1 − x2 ≤ 5

 

x1 , x2 , x3 ≥ 0.

 
x1 , x2 ≥ 0.


2. Montrer graphiquement que le programme linéaire suivant n’admet pas de solution optimale :
[M ax]z = 2x + 6y

 x − y ≤ 30
sc y − x ≤ 40
x, y ≥ 0.


3. Montrez que le programme linéaire suivant est non borné.

[M ax]z = 3x1 − 4x2 + 3x3


 −x1 + x2 + x3 ≤ −3
−2x1 − 3x2 + 4x3 ≤ −5

sc

 −3x1 + 2x2 − x3 ≤ −3
x1 , x2 , x3 ≥ 0.


Exercice 2 Une entreprise fabrique trois qualités différentes d’huile d’olive. Les quantités maximales pouvant être
vendues chaque mois ainsi que les prix de vente sont donnés dans la table suivante :
Produit Ventes maximales Prix de vente
(en litres) (en =UM/litre)
Huile A 3000 4
Huile B 3000 6
Huile C 2000 10
L’entreprise paie 1000 UM pour une tonne d’olives. Chaque tonne d’olives fournit soit 300 litres d’huile A soit 200
litres d’huile B (les coûts de ces transformations ne sont pas modélisés). Chaque litre d’huile A peut être raffiné
pour produire 6 dl d’huile B et 3 dl d’huile C. Le coût d’un tel raffinement est de 0.5 UM par litre.
De même, chaque litre d’huile B peut être raffiné pour obtenir 8 dl d’huile C. Le coût de ce raffinement et de 0.3
UM par litre.
Formuler un programme linéaire afin d’aider l’entreprise à déterminer un plan de production mensuel maximisant
son profit en précisant clairement les variables de décision, la fonction objectif et les contraintes.

1
Exercice 3 Une entreprise dispose d’un budget publicitaire de 4800 (unités monétaires) pour le lancement de
son nouveau produit. Sa campagne publicitaire utilisera à la fois des spots télévisés et des pages dans la presse
quotidienne. On pense que chaque minute de télévision va atteindre 100 000 nouveaux spectateurs et chaque page
dans un journal va être lue par 80 000 nouveaux lecteurs. Une minute de télévision coûte 800 UM et une page dans
un journal 600 UM. La direction de l’entreprise souhaite diffuser au moins trois minutes de spot et une page dans
un journal. Son objectif est de maximiser le nombre total de cibles (spectateurs et lecteurs).
1. Modéliser ce problème en programme linéaire.
2. Représenter l’espace des solutions réalisables.

3. Quelle est la combinaison optimale si le budget est augmenté de 4800 à 6000 ?

4. Quelle est la décision optimale s’il n’y a pas de contrainte de temps de télévision ?

Exercice 4 Une société se consacre à l’excavation et la distribution de matériaux de carrière. Elle doit assurer,
pour des travaux routiers, la fourniture de graviers en divers calibres. Un marché a été adjugé pour un prix global
de facturation, portant sur les quantités suivantes :
• 13500 tonnes de graviers de calibre 1

• 11200 tonnes de graviers de calibre 2

• 5000 tonnes de graviers de calibre 3.
La société exploite deux carrières P1 et P2 louées à une société civile qui perçoit une redevance par tonne extraite
comme suit : 19,40 UM par tonne pour P1 et 20 UM par tonne pour P2 .
Après extraction, le pierre est concassée et les graviers ainsi obtenus sont triés selon leur calibre. Chaque tonne
de pierre fournit les quantités suivantes (le complément représente du sable considéré comme déchet sans valeur
marchande) :

Carrière 1 Carrière 2
graviers calibre 1 0,36 t 0,45 t
graviers calibre 2 0,40 t 0,20 t
graviers calibre 3 0,16 t 0,10 t

1. Formuler le programme linéaire d’optimisation permettant de définir un programme d’extraction des carrières
P1 et P2 afin de minimiser le coût des redevances à la société civile.

2. Résoudre par la méthode du simplexe.

3. Donner une représentation graphique.

Exercice 5 La compagnie GOOD Oil possède 5.000 barils de pétrole de type 1 et 10.000 barils de pétrole type 2.
La société vend deux produits : l’essence et le fioul avec les spécifications suivantes :
• Les deux produits sont fabriqués en combinant le pétrole 1 et le pétrole 2.

• Les niveaux de qualité des pétroles 1 et 2 sont respectivement 10 et 5.

• L’essence doit avoir un niveau de qualité moyen d’au moins 8 et le fioul au moins 6.
• La demande pour chaque produit doit être créée par publicité.
• Chaque dollar dépensé en publicité pour l’essence crée une demande de 5 barils, et chaque dollar dépensé pour
le fioul de chauffage crée une demande de 10 barils.
• L’essence est vendue pour 25$ le baril, le mazout pour 20$.
Formuler un PL pour aider GOOD Oil à maximiser ses profits.
On admet qu’aucun pétrole de l’un ou l’autre type ne peut être acheté.

2
Exercice 6 Dans une entreprise qui fabrique des pièces détachées à la demande un client désire commander des
pièces A et B dans un délai d’un mois. Fournisseur et client se sont mis d’accord sur les prix suivants : 138 UM
par série de 100 pièces A et 136 UM par série de 100 pièces B. La réalisation des pièces A et B nécessite un passage
dans trois ateliers pour lesquels on dispose des renseignements suivants :
Nb d’unités d’oeuvre Nb d’unités d’oeuvre Coût variable d’une
pour 100 pièces A pour 100 pièces B unité d’oeuvre (UM)
Atelier T 2 1 10
Atelier F 1 4,5 12
Atelier M 4 3 14
Au moment de la commande, l’entreprise ne dispose que d’un nombre limité d’heures dans chaque atelier correspondant
respectivement à : 200 unités d’oeuvre pour l’atelier T, 540 unités d’oeuvre pour l’atelier F, 480 unités d’oeuvre
pour l’atelier M. Ces nombres d’unités d’oeuvre sont insuffisants pour satisfaire le client dans le délai demandé.
L’entreprise lui propose une livraison partielle.
Quelles quantités de pièces A et de pièces B l’entreprise a-t-elle intérêt à fabriquer au cours du mois si elle veut
obtenir une marge maximum compte-tenu des moyens de production disponibles. On utilisera la méthode du simplexe
dont on donnera par la suite une interprétation graphique.

Exercice 7 Un agriculteur possède 45 hectares de terre. Chaque hectare peut être planté avec du blé ou du haricot.
Chaque hectare de blé rapporte 2000 UM de profit ; et chaque hectare de haricot en rapporte 3000 UM. Travail et
les besoins en engrais par hectare pour planter du blé et du haricot sont les suivants :
haricot blé
Travail 3 travailleurs 2 travailleurs
Engrais 2t 4t
On suppose que 100 travailleurs et 120 tonnes d’engrais sont disponibles.
1. Proposer une formulation PL du problème de maximisation du profit de l’agriculteur.

2. Développer le problème dual et écrire une interprétation de celui-ci.

Exercice 8 Une usine produit, sur deux chaı̂nes, des appareils électroniques.
En raison de différences importantes dans les procédés de fabrication, les temps nécessaires aux machines outils
”fabrication” (FAB) et ”finition-réglage” (FIR) pour traiter un appareil diffèrent sensiblement sur chaque chaı̂ne,
avec des prix de revient eux aussi sensiblement différents.
L’élaboration d’un appareil sur la chaı̂ne 1 nécessite 3 heures de FAB et 1 heure de FIR, pour un prix de revient
unitaire de 20 KUM, tandis que la chaı̂ne 2 le produit pour 60 KUM avec 1 heure de FAB et 2 heures de FIR. La
machine FAB est disponible 60 heures par mois, et la machine FIR 70 heures.
1. La demande étant de 30 appareils par mois au moins, écrire le problème d’OL permettant de déterminer le
plan de production (charges x1 et x2 des chaı̂nes) de coût minimal.
2. Écrire et interpréter son dual.

3. Quel problème est plus adapté pour être résolu par l’algorithme du simplexe ? Trouver la solution optimale de
ce problème (primal ou dual, à vous de décider) et reconstruire la solution du problème complémentaire.