UTA A NNÉE ACADÉMIQUE 2023-2024
RO L 3 FBA
F ICHE DE T RAVAUX D IRIGÉS:
Exercice 1.
Vous êtes ingénieur conseiller du ministre du budget dans un pays où une catastrophe a détruit
toute infrastructure et quasiment toutes les ressources de production sauf celles situées dans la
ville de Diofo. Les coûts de reconstruction du réseau routier entre les principales villes ont été
chiffrés par le ministère de l’équipement. Le tableau ci dessous donne les coûts en milliards de
francs des seules villes entre lesquelles la route peut être reconstruite.
Diofo Bere Onene Paska Tchefari
Diofo 3 7 7
Bere 2 4
Onene 2 3
Paska 6
Tchefari
• Travail à faire : Proposer votre solution pour avoir un réseau minimal à moindre coût.
(On entend par réseau minimal, un réseau qui permet d’aller de n’importe quelle ville à
n’importe quelle autre.) Toute notion utile du cours pourra être citée.
Exercice 2.
1. Donner le nom d’un algorithme qui per-
E 5 F 4 G met de déterminer la plus courte chaîne
2
1
allant d’un point à un autre point quel-
1 2 1 conque d’un graphe.
1
1
H
A
1 4 2. Déterminer en utilisant cet algorithme,la
B 3 C 1 D longueur de la plus courte chaîne de A à
H.
Exercice 3.
Vous êtes chargé de la sécurité d’un diplomate dont le domicile et d’autres repères ainsi que les
voies entre ces repères sont donnés par le graphe ci-joint. Vous êtes préparé à son évacuation
depuis son domicile jusqu’à l’abri où votre responsabilité est dégagée. Les arcs sont pondérés
par les temps moyens mis entre les differents lieux.
1
1. Donner le nom d’un algorithme qui permettent de déterminer un plus court chemin allant
d’un point à un autre point quelconque d’un graphe.
2. En utilisant cet algorithme, déterminer un des chemins les plus rapide et sa durée moyenne
du domicile du diplomate à l’abri.
Exercice 4.
Tâches Antécédents Durée
A / 3
B A 1
C A 5
1. Ranger les sommets par niveau
D C, I 6
E B, D 4 2. Dresser le diagramme PERT de ce projet en ren-
F C, I 2 seignant les dates au plus tôt et les dates au plus
G E, F 9 tard.
H / 5 3. Quel est le chemin critique ?
I H 8
J H 2
K I 3
L K, J 7
Exercice 5.
Deux artisans A et B decident de s’associer en travaillant chacun un maximum de 42 heures
par semaine pour fabriquer des couteaux et des paires de ciseaux.
Un couteau rapporte un benefice de 200 francs. Une paire de ciseaux rapporte un benefice de
300 francs. La fabrication d’un couteau necessite 2 heures de travail de l’artisan A puis une
heure de travail de l’artisan B.
La fabrication d’une paire de ciseaux necessite 2 heures de travail de l’artisan A et 3 heures de
travail de l’artisan B.
1. Combien faut-il fabriquer de couteaux et de paires de ciseaux par sernaine pour réaliser
un bénéfice maximum ?
2. Quelle est la valeur de ce bénéfice hebdomadaire ?
2
Exercice 6.
Resoudre le programme linéaire : Maximiser Z = 3x1 + x2 + 3x3 sous les contraintes
2x1 + x2 + x3 ≤ 2
x1 + 2x2 + 3x3 ≤ 5
2x1 + 2x2 + x3 ≤ 6
x1 , x2 , x3 ≥ 0
Exercice 7.
A
4
10 3 D
5 7
1
B P
S 13
2
E
4
10 11
1. Donne le nom d’un algorithme pour calculer le flow maximum dans un réseau de trans-
port.
2. Donner la valeur initiale du flow.
3. Justifie que le chemin SCEP améliore ce flow de 10.
4. Donner un autre chemin améliorant et la valeur dont il améliore le flow.
5. Calculer le flow maximal dans ce réseau.
Exercice 8.
Une généreuse grand-mère décide de gâter 4 de ses petits-enfants (Alison, Brad, Charleen,
Dylan) en leur offrant à chacun un cadeau. Férue de technologie, elle est décidée à acheter 4
cadeaux différents :
– une console de jeu vidéo ;
– un téléphone portable ;
– un baladeur MP3
– un appareil photo numérique
Elle n’achètera qu’un seul appareil de chaque type. Chaque enfant aura donc l’un de ces ca-
deaux. Pour savoir comment répartir ces cadeaux, elle demande à ses petits-enfants d’indiquer
pour chacun de ces types d’objets le prix de l’appareil de ses rêves. Généreuse mais pas folle,
elle décide après avoir eu les réponses d’attribuer les cadeaux de façon à minimiser sa dépense
totale. Aidez-la donc à trouver une affectation des cadeaux qui écorne auminimumson budget,
sachant qu’elle a eu les réponses suivantes :
Alison Brad Charleen Dylan
Console 130 650 165 330
Téléphone 170 250 90 250
Baladeur 330 320 335 330
Photo 100 400 230 400
3
Exercice 9.
La société Alpha possédant quatre dépots A1 , A2 , A3 et A4 dans lesquels existent une quantité
de matière première, et trois usines D1 , D2 et D3 . Les couts de transport, Cij , sont donnés par
le tableau ci-dessous.
Comment organiser le transport au moindre coût total ?
D1 D2 D3 D4
A1 147 121 344 552
A2 241 153 102 312
A3 451 364 557 285
Exercice 10.
Soit un jeu de matrice
−2 1 −1 4
0 −1 3 0
−1 0 1 2
−3 1 0 4
1. Déterminer le comportement rationnel des joueurs
2. Existent ils des points selles ?
3. Si non, exprimer les gains moyens des joueurs en fonction des stratégies mixtes
4. Déterminer la stratégie mixte optimal ainsi que la valeur v du jeu.
