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.
(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
(50,70,50) est-elle une solution réalisable; est-elle une
solution de base?
réalisable mais pas de base
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.
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.
Quels sont les sommets, les arêtes et les faces du
polyèdre des solutions réalisables?
Les sommets A,B,C,D,E,F,G,H
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)
Les faces
ABED (dans le plan (1))
ACGFD(2), FGH(4), DEHF(5), BCGHE(6), ABC(7)
Le graphe (quelques arcs manquent l'indicateur d'orientation):