Next: About this document ...
IUP MIAGE
IUP3 Recherche Opérationnelle 1
TD1
- 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 |
 |
0 |
(1) |
x2 |
 |
0 |
(2) |
x3 |
 |
0 |
(3) |
x1+x2 |
 |
60 |
(4) |
x1+x3 |
 |
100 |
(5) |
x1+x2+x3 |
 |
70 |
(6) |
x2+x3 |
 |
120 |
(7) |
x2+x3 |
 |
20 |
(8) |
x1+x2+x3 |
 |
200 |
(9) |
fonction objective
z = 15000x1+10000x2+10000x3 à 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.
- (60,20,120) 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
et plusieurs non réalisables.
- 6.
- Quels sont les sommets, les arêtes et les faces du
polyèdre des solutions réalisables?
- (a)
- Les sommets
A,B,C,D,E,F,G,H
- (b)
- Les arêtes
AB (intersection des plans (1) et (4))
AC(1,5), AG(4,5), BC(1,9), BE(4,9), CH(5,9), DE(2,4),
DF(2,7), DG(4,7), EF(2,9), FH(7,9), GH(5,7)
- (c)
- Les faces
ABC (dans le plan (1))
DEF(2), ABEDG(4), ACHG(5), DFHG(7), BCHFE(9)
Next: About this document ...
Mike ROBSON
2000-10-04