IUP MIAGE IUP MIAGE
IUP3 Recherche Opérationnelle 1
TD4

  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 (dans cet ordre).


    x1+x2
    ³
    60
    (1)
    x1+x3
    ³
    100
    (2)
    x1+x2+x3
    ³
    70
    (3)
    x2+x3
    ³
    120
    (4)
    x2
    ³
    50
    (5)
    x1+x2+x3
    £
    200
    (6)
    x1
    ³
    0
    (7)
    x2
    ³
    0
    (8)
    x3
    ³
    0
    (9)

    fonction objective z = 10000x1+10000x2+15000x3 à minimiser.

  2. (0,0,0) est-elle une solution réalisable; est-elle une solution de base?
    de base (contraintes 1,2,3 vérifiées) mais pas réalisable
  3. (50,70,50) est-elle une solution réalisable; est-elle une solution de base?
    réalisable mais pas de base
  4. Expliquez pourquoi une solution avec 2 variables nulles ne peut jamais être réalisable.
    Deux variables nulles équivaut à tous les pompiers dans une seule ville et il n'y a aucune ville reliée à toutes les autres.
  5. Trouvez les solutions de base
    0,60,100
    intersection  (1),(2),(7)
    A 2.1M
    0,60,140
    intersection  (1),(6),(7)
    B 2.7M
    0,100,100
    intersection  (2),(6),(7)
    C 2.5M
    10,50,90
    intersection  (1),(2),(5)
    D 1.95M
    10,50,140
    intersection  (1),(5),(6)
    E 2.7M
    30,50,70
    intersection  (2),(4),(5)
    F 1.85M
    80,100,20
    intersection  (2),(4),(6)
    G 2.1M
    80,50,70
    intersection  (4),(5),(6)
    H 2.35M
    et plusieurs non réalisables.
  6. Quels sont les sommets, les arêtes et les faces du polyèdre des solutions réalisables?

    1. Les sommets
      A,B,C,D,E,F,G,H
    2. Les arêtes
      AB (intersection des plans (1) et (7))
      AC(2,7), AD(1,2), BC(6,7), BE(1,6), CG(2,6), DE(1,5),
       DF(2,5), EH(5,6), FG(2,4), FH(4,5), GH(4,6)
    3. Les faces
      ABED (dans le plan (1))
      ACGFD(2), FGH(4), DEHF(5), BCGHE(6), ABC(7)
  7. Le graphe (quelques arcs manquent l'indicateur d'orientation):
                      C------->-------G
                     .|               |.
                    . |               | .
                   .  ^               ^  .
                  .   |               |   .
                 .    |               |    .
                A--<--B               H-->--F
                 .     .             .     .
                  .     .           .     .
                   .     .         .     .
                    .     .       .     .
                     .     .     .     .
                      .     .   .     .
                       .     . .     .
                        .     E     .
                         .    |    .
                          .   |   .
                           .  V  .
                            . | .
                             .|.
                              D
    
    



File translated from TEX by TTH, version 3.05.
On 14 Nov 2002, 14:21.