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.

  1. 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.
  2. (0,0,0) est-elle une solution réalisable; est-elle une solution de base?
  3. (50,70,50) est-elle une solution réalisable; est-elle une solution de base?
  4. Expliquez pourquoi une solution avec 2 variables nulles ne peut jamais être réalisable.
  5.    [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:
  6. 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.