Exercices corrigés de recherche opérationnelle

Résumé du document

Une série d'exercices corrigés de recherche opérationnelle. Sont proposés dans ce document un ensemble d'exercices de la vie pratique, intéressants, bien élaborés et détaillés.

Extraits

[...] On doit imposer que deux des trois contraintes suivantes soient respectées : x1 + x2 + + x6 x7 + x8 + x9 x10 + x11 + x12 0 Dans le modèle, on y arrive en ajoutant 3 variables binaires et les contraintes suivantes : x1 + x2 + + x6 0 + 16 y1 x7 + x8 + x9 0 + 11 y2 x10 + x11 + x12 0 + 4 y3 y1 + y2 + y3 y1, y2, y3 binaires La solution est alors d'investir à Montréal : x1= x2= x3= 3 et Z = 9,78 millions Exercice 2 Question 1 : La représentation du réseau est : Question 2 : En résolvant le modèle avec Excel, on obtient la solution optimale suivante : profit maximal = 2417.50 variables : x14 = carottes dans purée 3 légumes x65 = purée de carottes x15 = carottes en vrac x24 = brocolis dans purée 3 légumes x25 = brocolis en vrac x34 = pois dans purée 3 légumes x75 = purée de petits pois x45 = grammes de purée 3 légumes produites Exercice 3 Problème d'itinéraires d'avions Le réseau est celui dessiné plus haut. Le flot dans ce réseau est constitué d'avions. Les nœuds représentent des activités (arrivées ou départs) aux différents aéroports. Il y a trois types d'arcs. Les arcs horizontaux (e.g. A1D A2D). Le flot sur ces arcs représente les avions en attente de la prochaine activité. Les arcs en diagonale, (e.g. A1D B2A). [...]

[...] En modifiant le membre de droite de la contrainte de budget, on trouve que la nouvelle solution optimale est x3= x6= x9= 1 et Z = 8,63 millions donc une perte dans les revenus de 1,4 millions. Ce montant correspond au revenu minimal à demander pour cet immeuble. Question 4 : On doit ajouter une série de contraintes x1 + x2 + + x6 1 x7 + x8 + x9 1 x10 + x11 + x12 1. La solution est alors: x3= x6= x9= x10= 1 et Z = 9,98 millions. [...]

[...] Exercice 3 Problème d'itinéraires d'avions Une compagnie aérienne opère 15 vols sur une base journalière entre les villes B et C qu'elle veut desservir avec le plus petit nombre d'avions possible. Pour ce faire, elle doit déterminer le moyen le plus efficace de combiner les vols pour former les itinéraires des avions. La figure suivante représente ces vols sur un réseau où un identificateur de sommet indique la ville B ou le numéro d'activité dans l'ordre croissant, ainsi que l'activé : départ ou A : arrivée). [...]

[...] Son prix de vente est de 1,25 millions. Quels devraient être ses revenus minimums pour qu'il soit intéressant de l'acheter? Modifier le modèle de la question 2 pour répondre à cette question. Question 4 : Les 6 premiers projets sont sur l'île de Montréal, les projets 7 à 9 sont sur la rive Nord et les 3 derniers sont sur la rive sud. Si MQG souhaite avoir au moins un immeuble dans chacune des 3 régions, quelle serait la façon optimale de placer son argent, en modifiant le modèle de la question 2 ? [...]

[...] Les arcs de retour, (e.g. A8A A1D). Le flot sur ces arcs représente les avions prêts pour débuter la journée du lendemain. Il y a une variable par arc : A1DA2D = nombre d'avions en attente à l'aéroport A entre le premier et le deuxième départ. A1DB2A = nombre d'avions sur ce vol. (On peut dire qu'il en faut au moins . C10AC1D = Nombre d'avions dans le hangar C pendant la nuit. Il y a une contrainte de conservation de flot par nœud : A8AA1D = A1DA2D + A1DB2A A1DA2D = A2DC4A + A2DA3A A2DA3A + B1DA3A = A3AA4D . [...]