11 Exercices Corrigés Modélisation
11 Exercices Corrigés Modélisation
11 Exercices Corrigés Modélisation
Exercice 1. La cafétéria
Pour faire fonctionner une cafétéria, le gérant doit assurer des permanences sur la base des
statistiques sur le personnel requis résumé dans la table ci-dessous :
Solution :
Xi donne le nombre d’employé commençant a travailler le jour i.
Min \sum(xi)
s.c. xi + x(i-1) + x(i-2) + x(i-3) + x(i-4) >= Ni;
xi >= 0;
solution : f.obj.=22
Le procédé de production d’acier est tel qu’une adition directe de Mn est envisageable. Ce
Manganèse est disponible au prix de 8 millions d’euros (ME) la tonne. Quant aux minerais, ils
coûtent respectivement 21 ME les milles tonnes pour le type A, 25 ME pour B et 15 ME pour
C. Si la fonderie envisage de vendre l’acier produit de 0,45ME la tonne, comment doit-elle
fabriquer les 1000 tonnes demandées de manière à maximiser son profit, sachant que le
coût de fonte d’une tonne de minerais est de 0,005 ME ?
Solution :
Variables de décisions : A, B, C, M (en milliers de tonnes);
Maximiser le profit est équivalent à minimiser le coût.
Coût = 21A + 25B + 15C + 8*1000 M + (A+B+C)*1000*0.005
Contraintes :
1) A 0.45 + B0.5 + C0,4 + M*100 >= 0,45 ;
2) A4 + B1 + C0.6 >= 3.25
3) A4 + B1 + C0.6 <= 5
4) A+B+C + M =1 ;
5) A, B, C, M >= 0;
Exercice 3. Modélisation
Une entreprise suisse fabrique trois modèles de TV A, B et C qui lui rapportent des profits de
160, 300 et 400 francs. Les niveaux minima de production pour une semaine sont 100 pour
A, 150 pour B et 75 pour C. Chaque douzaine de TV de type i requiert un temps Fi pour la
Fabrication, un temps Ai pour l’Assemblage et un temps Ei pour l’Emballage.
A B C
Fi 3 3,5 5
Ai 4 5 8
Ei 1 2,3 3
Pendant la semaine à venir, l’entreprise aura 150 heures disponibles pour la fabrication, 200
pour l’assemblage et 60 pour l’emballage. Formuler un modèle (PL ou PLNE ?) donnant un
plan de production qui maximise le profit de la compagnie.
Solution :
Variables de décisions : A, B, C.
Max 160A + 300B + 400C
s.c.
1) 3A + 3.5B + 5C <= 150*12
2) 4A + 5B + 8C <= 200*12
3) A + 2.3b + 3C <= 60*12
4) + contraintes de bornes
Solution : f;obj.=25560
Méthode de résolution :
C’est un problème de couverture des sommets (NP-complet): il s’agit de trouver le plus petit
ensemble des nœuds couvrant l’ensemble des arcs du réseau. G=(V,E), trouver V’ de
cardinalité min tel que pour tout arc ij, i ou j est dans V’.
Solution :
Le premier problème est un problème de p-centre et le deuxième un problème de
couverture totale.
Exercice 7. Un problème de transport.
Trois raffineries ravitaillent en essence 4 dépôts à l’aide de camions. Le tableau donne les
coûts de transport en Euros/m3, les stocks des raffineries, et les besoins des dépôts (en
milliers de m3). Les coût nul sont dus à deux pipe-line permettant le transport à coût
négligeable. On souhaite ravitailler les dépôts en minimisant le coût de transport.
Solution :
Minimiser 10x1,1 + 20x1,3 +11x1,4 + 12x2 ,1 +7x2,2 + 9x2,3 +20x2,4 + 14x3 ,2 + 16x3,3 +18x3,4
Sous les contraintes :
x1,1 + x2 ,1 + x3,1 ≥ 5;
x1,2 + x2 ,2 + x3,2 ≥ 15;
x1,3 + x2 ,3 + x3,3 ≥ 15;
x1,4 + x2 ,4 + x3,4 ≥ 10;
x1,1 + x1,2 + x1,3 + x1,4 ≤ 15;
x2,1 + x2,2 + x2,3 + x2,4 ≤ 25;
x3,1 + x3,2 + x3,3 + x3,4 ≤ 5;
xi,j ≥ 0;
Méthode de résolution :
Minimiser 3x1,1 + 5x1,2 +3x1,3 + 2x2 ,1 +7x2,2 + x2,3
Sous les contraintes :
x1,1 + x2 ,1 = 8;
x1,2 + x2 ,2 = 7;
x1,3 + x2 ,3 = 5;
x1,1 + x1,2 + x1,3 = 12;
x2,1 + x2,2 + x2,3 = 8;
xi,j ≥ 0;
N wagons de SNCF de charge utile limitée à un poids P sont réservés pour transporter m
caisses. Les caisses, 1,2, .., m et leur poids p1, p2, .., pm sont connus. Il est admis que le poids
total des caisses ne dépasse pas la capacité totale N*P.
1) Comment affecter les caisses aux wagons de façon à respecter les charges utiles
maximales et à minimiser la charge du wagon le plus chargé. Modéliser le problème
comme un programme linéaire.
2) Etudier le cas de deux wagons. Faire le rapprochement avec le problème de sac à dos
(voir ci-dessous). Donner ensuite une formulation en programmation linéaire plus
simple que celle donnée en 1).
Solution :
1)
Min pmin
s.c. :
(a) Pi <= P ; pour tout wagon ; (Pi donne le poids chargé du wagon i).
(b) Pi <= pmin ;
2) Il suffit de :
Max P1
S.c. :
2*P1 <= Somme des poids des caisses ;
Besoins en
containeurs
Genoa 20
Venice 14
Ancona 26
Naples 32
Bari 22
Le transport des containeurs par des péniches. Chaque péniche ne peut contenir que deux
containeurs et le coût du transport (par péniche) est proportionnel à la distance parcourue
(30Euros/km). Les distances sont données dans le tableau suivant :
Genoa Venice Ancona Naples Bari
Verona 290 115 355 715 810
Perugia 380 340 165 380 610
Rome 505 530 285 220 450
Pescara 655 450 155 240 315
Taranto 1010 840 550 305 95
Lamezia 1072 1097 747 372 333
Une autre façon de faire, encore plus simple, est de décomposer en deux types de variables
de décision :
xij = nombre de péniches pleines et yij = nombre de péniches avec un seul containeur ;