IUP MIAGE
Master 1 Recherche Opérationnelle 1
TD4: le 6/10/2004
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?
File translated from TEX by
TTH,
version 3.05.
On 6 Oct 2004, 13:15.