next up previous
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 $\textstyle \geq$ 0 (1)
x2 $\textstyle \geq$ 0 (2)
x3 $\textstyle \geq$ 0 (3)
x1+x2 $\textstyle \geq$ 60 (4)
x1+x3 $\textstyle \geq$ 100 (5)
x1+x2+x3 $\textstyle \geq$ 70 (6)
x2+x3 $\textstyle \geq$ 120 (7)
x2+x3 $\textstyle \geq$ 20 (8)
x1+x2+x3 $\textstyle \leq$ 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

\begin{eqnarray*}
0,60,100 & intersection (1),(4),(5)&A~1.6M\\
0,60,140 & inter...
...5),(7) & G~1.5M\\
80,100,20 & intersection (5),(7),(9) & H~2.4M
\end{eqnarray*}


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 up previous
Next: About this document ...
Mike ROBSON
2000-10-04