IUP MIAGE
IUP MIAGE
IUP3 Recherche Opérationnelle 1
TD4: le 12/11/2002
Le problème des pompiers est le suivant:
Dans une île, il y a cinq villes N, E, O, S et C.
Les villes de N, C et S possèdent, chacune une caserne de pompiers.
Il y a des routes entre N et C, N et O, S et C, S et O
et aussi C et E.
Dans le cas d'un incendie dans une ville donnée, les pompiers
peuvent y arriver
s'ils sont dans cette même ville ou dans une ville reliée par une route.
Il faut que 60 pompiers soient disponibles pour un incendie à N,
50 pour E, 100 pour O, 120 pour S et 70 pour C.
(On supppose que la possibilité de deux incendies simultanés
peut être négligée!)
Il faut aussi que le
nombre total de pompiers soit au maximum 200.
Le coût d'un pompier à C ou N est de 10.000 mais à S ce coût
s'élève à 15.000. On veut minimiser le coût total.
- Exprimer le problème en forme de programme linéaire dans les
3 variables x1, x2 et x3 les nombres de pompiers
affectés à N, C et S.
- (0,0,0) est-elle une solution réalisable; est-elle une
solution de base?
- (50,70,50) est-elle une solution réalisable; est-elle une
solution de base?
- Expliquez pourquoi une solution avec 2 variables nulles
ne peut jamais être réalisable.
-
[A faire en 4 groupes]
Trouvez les solutions de base, et pour chacune décidez quelles
sont les contraintes vérifiées avec égalité, sont-elles
réalisables et quelle est la valeur de la fonction objective:
- (Groupe 1): les solutions où x1=0, x2, x3 > 0
- (Groupe 2): les solutions où x2=0, x1, x3 > 0
- (Groupe 3): les solutions où x3=0, x1, x2 > 0
- (Groupe 4): les solutions où aucune variable n'est nulle.
- Quels sont les sommets, les arêtes et les faces du
polyèdre des solutions réalisables?
Dessiner un graphe orienté montrant tous les changements
de solution de base possibles pour l'algorithme du simplexe
(avec choix aléatoire d'un meilleur voisin)
File translated from
TEX
by
TTH,
version 3.05.
On 14 Nov 2002, 12:31.