next up previous
Next: About this document ...

Recherche Opérationnelle

IUP-MIAGe 3

Jeudi 20 janvier 2000

Tous documents autorisés

1.
Pour le programme linéaire:


x5 + x6 $\textstyle \leq$ 10 (1)
x4-x5 $\textstyle \leq$ 10 (2)
x3-x5-x6 $\textstyle \leq$ 10 (3)
x2-x4+x5-x6 $\textstyle \leq$ 10 (4)
x1-x2+x4-2x5+x6 $\textstyle \leq$ 10 (5)
-x2+x4-x5+x6 $\textstyle \leq$ 0 (6)
-x1+x2-x4+2x5-x6 $\textstyle \leq$ 0 (7)
x1,x2,x3,x4,x5,x6 $\textstyle \geq$ 0 (8)
zmin = -6x1+5x2-5x4+13x5-3x6 (9)

(a)
Démontrez que ${\bf x}=(10,0,20,10,10,0)$, ${\bf x}=(0,10,10,0,0,10)$ et ${\bf y}=(2,0,0,0,0,1,6)$ sont des solutions faisables de base du programme et de son dual,
(b)
Quelles sont les valeurs des fonctions objectives pour ces trois solutions?
(c)
Que peut-on déduire de la réponse précédente (et pourquoi)?
(d)
Donner une solution faisable du programme initial qui n'est pas une solution de base et qui donne la valeur optimale de la fonction objective,
(e)
Expliquer pourquoi, dans la recherche de la valeur optimale d'un programme linéaire possédant une solution optimale, il suffit de considérer les solutions de base,
(f)
Combien de solutions de base possède le programme initial (y compris celles qui ne sont pas faisables)?

2.
(a)
Expliquez, pour une chaîne de Markov avec une seule classe finale qui n'est pas périodique, comment vous pouvez trouver la limite de la probabilité d'être dans un état donné.
(b)
Pourquoi votre méthode ne donne-t-elle pas forcément le bon résultat dans le cas de plusieurs classes finales et dans le cas d'une classe finale périodique?
(c)
Supposez que dans une chaîne l'état i est périodique avec période $\lambda$ et que l'état initial est l'état 1. Comment calcule-t-on la limite de la probabilité d'être dans l'état i après un nombre de transitions qui est un multiple de $\lambda$?




next up previous
Next: About this document ...
Mike ROBSON
2000-11-27