1
(STG-MCV-ECOMO-CF)
Par : Pr Donatien EZE EZE
Exercice1.
Trois tailles T1, t2 et t3 sont respectivement susceptibles de fournir une extraction maximale journalière
de e1 = 200, e2 = 500 et e3 = 300 tonnes.
La production journalière est d’abord stockée dans un local abrité d’une contenance maximale de
1800m3 et on indique les volumes spécifiques respectifs des trois catégories de produit : 1,8 ;2 et 2,2
m3 /t
Le lendemain, les minerais sont lavés : La laverie débite respectivement80, 90 et 100 tonnes à l’heure
pour les produits extraits des tailles t1, t2 et t3 ; en outre, son horaire journalier est limité à 10 heures de
travail.
Enfin les profits unitaires réalisés sont respectivement : p1 = 4, p2 = 5 et p3 = 6 unités monétaires.
Ecrire le programme linéaire permettant de déterminer la meilleure répartition des quantités à
extraire.
Exercice2
Trois dépôts A, B, C disposent respectivement de 30, 20, 45 tonnes de marchandises. Quatre
(04) destinations D, E, F et G en demandent des quantités respectives de 10, 25, 20 et 40 tonnes.
La matrice des coûts unitaires est la suivante :
D E F G
A 12 27 61 49
B 23 39 78 28
C 67 56 90 24
TAF : Formuler un programme linéaire pouvant aider l'entreprise à déterminer le plan de transport
qui assure au moindre coût la satisfaction de la demande.
Exercice 3
Une verrerie produit des verres à vin, des verres à eau et des flûtes à champagne. Les prix de vente, les
quantités requises de verre ainsi que les temps de façonnage et d'emballage sont différents pour chacun
des produits et sont résumés dans la table suivante :
Verre à vin Verre à eau Flûtes à champagne
Temps de façonnage [min] 4 2 12
Temps d'emballage [min] 2 1 4
Quantités de verre [kg] 0.1 0.15 0.1
Prix de vente [Frs] 8 6 15.
Pour la semaine à venir, l'entreprise dispose de 3000 minutes pour le façonnage, de 1200 minutes pour
l'emballage et de 100 kilogrammes de verre.
2
Formuler un programme linéaire aidant l'entreprise à déterminer une production maximisant son
chiffre d'affaires.
Résoudre le PL suivant :
Min z = 5x1 − 2 x2 + 3x3
2 x1 + 2 x2 − x3 2
3x1 − 4 x2 3
x2 + 3x3 5
x1 0 , x2 0 , x3 0
Exercice4
Une usine sidérurgique doit produire 1000 pièces identiques nécessitant chacune 1, 0.6, et 0,3 kilogrammes de
métaux M1 M2 M3. Ces métaux sont présents dans différents alliages que l’usine achète sur le marché. Le prix et
la composition en pourcentage de ces alliages sont précisés dans le tableau suivant :
Alliage1 Alliage2 Alliage3
M1 10% 40% 10%
M2 30% 60% 60%
M3 60% - 30%
Prix en FCFA 3 1 4
1- Ecrire le programme linéaire permettant à l’usine de produire les 1000 pièces demandées au moindre
cout.
2- Quelle quantité d’alliage de chaque type faut-il pour réaliser la production ? Déterminer le cout minimal
d’achat
3- Donner les quantités inutilisées de métaux a la fin du processus de production
Exercice 5
Pour réaliser la production de quatre types de boissons gazeuses en quantités respectives x1 , x 2 ,
x3 et x 4 , les ETS « boit tout sauf eau » disposent de trois ressources : le sucre(3 tonnes), le malt(10
litres) et des colorants (8 litres) .L’entreprise veut maximiser son profit. Les profits unitaires sont
respectivement de 4,5 ; 2,5 ; 1 et 3 unités monétaire pour chacun des quatre produits. L’analyse du
processus de production par Aminou , étudiant à la FSEG a permis d’aboutir au programme linéaire
suivant :
MaximiserZ = 4,5x1 + 2,5x2 + x3 + 3x4
s/c
2 x1 + x2 + x4 3
x1 − 2 x2 + 2 x3 10
3x1 + 2 x2 + x3 + 2 x4 8
x1 0 , x 2 0 x3 0 x 4 0
La solution optimale du programme est : x1 = 0 , x2 = 0 , x3 = 2 et x4 = 3 .
1/ Toutes les ressources dont dispose l’entreprise seront-elles épuisées au terme du processus de
production ? Justifier votre réponse.
2/ Ecrire le dual et donner sa solution par application du théorème de la dualité. On précisera alors
en même temps la valeur des variables d’écart du Dual.
3
3/ Si le prix de vente du malt sur le marché est de 5 unités monétaires, l’entreprise aurait elle intérêt
à vendre les quantités dont elle dispose ? Justifier votre réponse.
4/ On donne ci-dessous quelques éléments du tableau optimal du simplexe de ce programme
Base X1 X2 X3 X4 X5 X6 X7 B
2 1 0 1 1 0 0
3 -2 0 0 4 1 -2
-1 0 1 0 -2 0 1
a/ Compléter le tableau
b/ Supposons que la quantité disponible de sucre diminue, à quelle condition la solution optimale
reste t elle inchangée ?
c/ Supposons maintenant que le profit unitaire du premier type de boisson passe 4,5 à 14,5. La
solution optimale va-t-elle changer ? Si oui, quelle sera la nouvelle solution ?
d/ Supposons maintenant que c’est plutôt le profit unitaire du second type de boisson qui varie. A
quelle condition la solution restera t elle inchangée ? Si cette condition n’est pas remplie, quelle sera
la nouvelle solution optimale
Exercice6
Dans une entreprise, il y a 5 ouvriers (01,02,03,04,05) et 5 postes (P1,P2,P3, P4, P5) à pourvoir. On donne
ci-dessous la matrice des coûts d’affectation.
PostesOuvriers P1 P2 P3 P4 P5
O1 12 10 8 15 6
O2 7 20 16 12 10
O3 13 8 12 11 9
O4 9 8 15 6 14
O5 13 12 14 10 8
Quelle est la solution optimale permettant à chaque ouvrier d’avoir un poste si l’affectation est faite
au coût minimal ?
Exercice 7 .
Trois dépôts A, B,C disposent respectivement de 30, 20, 45 tonnes de marchandises. Quatre (04)
destinations D, E, F et G en demandent des quantités respectives de 10, 25, 20 et 40 tonnes.
La matrice des coûts unitaires est la suivante :
D E F G
A 12 27 61 49
B 23 39 78 28
C 67 56 90 24
Question : Etablir le meilleur plan de transport, celui qui assure au moindre coût le transport des
quantités demandées en utilisant la méthode de Stepping Stone..
Exercice8
On veut organiser la production de lots de pièces A et B qui doivent tous deux être usinés sur
la machine M1 , puis sur la machine M2. Les taches d’usinage sont notées U1A, U2A,U1B,U2B et ont pour
durées respectives 2, 3, 2, 1. Avant d’usiner les lots de pièces A et B , il faut procéder au réglage de
chaque machine. D’où les taches de réglage notées R1A, R2A,R1B,R2B qui doivent précéder les taches
d’usinage correspondantes et qui ont pour durées respectives 1, 1, 2, 6.
4
Il y a un ouvrier par machine, si bien que les deux machines peuvent être utilisées ou réglées
parallèlement. D’autre part, on choisit d’abord d’usiner le lot A puis le lot B.
1) Sachant qu’on veut minimiser le temps total d’exécution des pièces, tracer le graphe
correspondant à la méthode des potentiels. Déterminer les dates de début au plus
tôt et au plus tard des différentes tâches, ainsi que le chemin critique.
2) Reprendre la question en utilisant la méthode PERT.
Exercice 9
Un projet a été divisé en 7 tâches, notées A, B, C, D, E, F et G dont les durées en jours sont données
dans la table qui suit.
Tache A B C D E F G
Durée (en jours) 4 3 2 6 5 4 5
Les contraintes suivantes doivent être respectées lors de la réalisation du projet :
- les tâches D et E ne peuvent commencer avant que A ne soit finie ;
- la tâche B peut débuter au plus tôt 3 jours après le début de D et doit être terminée avant que
F et G ne débutent
- l'exécution de la tâche C doit précéder celle de F ; de plus une pause d'au moins 4 jours est
nécessaire entre le début de C et la fin de E.
Après avoir représenté le graphe, déterminer la durée minimale de réalisation du projet ainsi que les
tâches critiques. Préciser la démarche utilisée et les étapes intermédiaires de la résolution.
EXERCICE 10
Dans un phénomène d’attente, les arrivées sont poissoniennes et le service exponentiel. Un seul
employé dessert un guichet ouvert de 7heures à 13 heures sans interruption. Le nombre moyen de
clients est de 54 par jour. La durée moyenne du service 5 minutes.
1/ Déterminer le nombre moyen de clients dans le système, le nombre moyen de clients dans la file,
le temps moyen d’attente.
2/ Quelle est la probabilité d’attendre plus d’une demi-heure ?