Modélisation en recherche opérationnelle - MTH6406

...

Un bon dessin des coupes donnera 6 points. De bonnes équations donneront 9 points supplémentaires.

QUESTION # 4 (35 points)

Les conduites principales d'un aqueduc municipal forment un réseau orienté.[pic 23][pic 24]

Le nœud 1 est une usine de filtration avec une capacité suffisante Les nœud 2 à 13 sont des points de consommation ou des points intermédiaires ayant une demande dit litres par heure constante pour chaque tranche de temps [t, t+1), t= 0, à 23. Chaque arc (i, j) correspond à une conduite orientée de capacité maximale Uij litres par heure avec des pompes le long de la conduite. Pour acheminer un flot de [pic 25] litres par heure dans l'arc [pic 26] il faut payer un coût de pompage de ci,j x fij2 dollars par heure. (les capacités sont suffisantes pour satisfaire la demande).

a) (10 points)

On veut déterminer les flots fijt à chaque heure qui répondent à la demande en minimisant les couts de pompage. Proposer un (ou plusieurs) modèle(s) permettant d’obtenir rapidement une solution optimale. Présenter les modèles en utilisant le langage de la programmation mathématique (variables, contraintes, fonction objectif). Donner le nom du (ou des) algorithme(s) permettant de résoudre rapidement.

- (7 points)

On ajoute un réservoir au nœud 6 de capacité V litres, on veut une solution périodique optimale que l'on pourra répéter à tous les jours. Décrivez un modèle d'optimisation de réseau permettant de résoudre ce problème.

c) (3 points)

Décrivez la modification à apporter au modèle d) si on veut planifier la capacité optimale du réservoir en plus de la politique d'opération. On considère C un coût d'amortissement journalier du réservoir de par litre de capacité.

ON NE CONSIDÈRE PLUS LE RÉSERVOIR

d) (5 points)

Si les conduites ne sont pas parfaitement étanches et qu’il y a un pourcentage de perte pij du début à la fin de chaque conduit (i,j). Indiquez les modifications à apporter à votre programme linéaire.

e) (10 points)

Si les pij sont inférieurs à 10%, proposez un modèle de réseau permettant d’obtenir rapidement une solution approchée avec une erreur de l’ordre de 1% sur la réalisabilité. Indiquez la taille du réseau en comparaison avec celui présenté en a). Indiquez le type de problème de réseau.