Modélisation en recherche opérationnelle - MTH6406

Date :  Lundi, le 23 avril 2013        Professeure :  François Soumis

Heure: 14h00 à 17h00        Salle L-2712

TOUTE DOCUMENTATION AUTORISÉE

QUESTION # 1 (20 points)

Considérer un problème de collecte chez 20 clients.  Vous avez au dépôt 5 camions de 32 m3 ayant un coût de déplacement de 2,00$ / km et un coût fixe de 40,00$ / jour.  Vous avez aussi 3 camions de 16 m3 ayant un coût de déplacement de 1,50$ / km et un coût fixe de 30,00$ / jour.  Chaque camion peut faire une seule tournée par jour.  On veut résoudre ce problème avec GENCOL.

(10 pts)        a)        On a deux fenêtres de temps sur les heures d'arrivée chez chaque client, une A.M. et une P.M. On doit visiter chaque client une seule fois dans une ou l’autre des fenêtres. Comment doit-on modéliser le(s) sous problème(s) : ressources, croquis de réseau.

(10 pts)        b)        On a la contrainte qu'il y a seulement 6 chauffeurs et que l'on doit choisir 6 camions parmi les 8. Décrivez les lignes qu'il faut ajouter au problème pour modéliser les contraintes de nombre de véhicules et de nombre de chauffeurs.  Écrivez les commandes « rows » et « colums » qui sont nécessaires. Quels sont les arcs de votre réseau qui contribuent aux « rows » que vous définissez ?  Et de combien 

QUESTION # 2        (15 points)

Une centrale électrique est composée de 10 turbines à gaz indépendantes avec chacune un alternateur. Il faut produire assez pour répondre à la demande et le surplus est perdu. La demande est prévue avec une bonne précision par tranche de 5 minutes pour les prochaines 24 heures. Vous avez [pic 1]la demande en kW prévu pour les 288 tranches des temps.

Les 10 turbines-alternateurs sont identiques et ont les propriétés suivantes :

• Une turbine peut produire à une température entre 800 C° et 1200 C°.
• L’entreprise opère ces turbines aux températures qui sont des multiples de 10 C°.
• Le coût du gaz durant 5 minutes pour produire de l’électricité en maintenant la température [pic 2] est K1  x t.
• Le coût du gaz durant 5 minutes pour  produire de l’électricité en augmentant la température de [pic 3] à [pic 4] est K2  x t.
• Le coût du gaz durant 5 minutes pour  produire de l’électricité en diminuant la température de [pic 5] à [pic 6] est. K3  x t
• La production électrique en kw est [pic 7]à la température [pic 8] (on prend la moyenne si la température varie de 10 degrés durant 5 minutes).
• On ne peut pas varier la température de plus de 10 degrés en 5 minutes durant la production.
• Si on interrompt le chauffage à 800 C° la température décroit de 50 C° par 5 minutes jusqu’à 100 C°.
• On ne peut pas redémarrer si t ∈ (100,800).
• Quand on démarre à [pic 9]100 C° la température augmente de 100 C° par 5 minutes jusqu’à 800 C° sans production d’électricité. Le coût du gaz est [pic 10] par 5 minutes.

On veut un modèle de génération de colonne déterminant l’évolution de la température des 10 turbines de façon à satisfaire la demande à coût minimal.

1.  (5 points)

Formulez le problème maître : variables, objectif, contraintes

1. (10 points)

      Combien de sous problèmes?

Formulez le sous-problème de plus court chemin pour une turbine. Décrivez les nœuds, les différents types d’arcs et les coûts pour chaque type d’arcs

QUESTION # 3  (20 points)

On veut développer un modèle d’optimisation pour affecter deux types de wagons aux trains d’un réseau. Les wagons de type 1 ont 70 places et les wagons de type 2 ont 50 places. On ne considère pas les locomotives dans ce problème. Pour un certain arc [pic 11] les contraintes sur les wagons requis sont :

1)        [pic 12][pic 13]

2)        [pic 14][pic 15]       

[pic 16] sont les variables indiquant les nombres de wagons de chaque type. [pic 17] est le nombre de passagers à transporter. [pic 18] est le nombre maximum de wagons permis.

On sait que la contrainte 1) peut causer un grand saut d’intégrité lors de la résolution.

(5 pts)        a)        Comment peut-on modifier le coefficient [pic 19] dans pour avoir une contrainte plus serrée en nombre réel mais équivalente en nombre entier?

(15 pts)        b)        Donner les bornes inférieures et supérieures sur les variables [pic 20] et les coupes (contraintes linéaires avec les variables[pic 21] ) remplaçant la contrainte 1) et  permettant d’avoir un polyèdre équivalent en nombres réels et en nombres entiers pour les variables [pic 22] .