Correction examen recherche operationnelle 3eme emfb session

Télécharger PDF

Correction de l'Examen de Recherche Opérationnelle (3ème EMFB) – Session Principale (Mai 2016)

Exercice 1 : Problème de Minimisation

Le premier exercice aborde un problème de minimisation sous contraintes (MIN S/C). Les détails spécifiques de la fonction objectif et des contraintes ne sont pas fournis dans cet extrait, ce qui limite la présentation d'une solution complète. Il s'agirait typiquement de trouver les valeurs de variables qui minimisent une fonction donnée tout en respectant un ensemble de conditions.

Exercice 2 : Résolution d'un Problème de Transport

Cet exercice se concentre sur la résolution d'un problème de transport, avec l'objectif de minimiser les coûts. Deux méthodes principales sont appliquées pour trouver une solution initiale.

Application de la méthode du coin nord-ouest

La méthode du coin nord-ouest est une technique simple pour déterminer une solution initiale réalisable à un problème de transport. Elle commence par attribuer le maximum de ressources à la cellule la plus en haut à gauche (le "coin nord-ouest") du tableau des coûts, puis progresse. Voici la solution d'allocation obtenue :

Usine/Entrepôt	Entrepôt 1	Entrepôt 2	Entrepôt 3	Entrepôt 4	Capacité de l'usine
Usine 1	40				40
Usine 2	15	5			20
Usine 3		20	45	5	70
Demande de l'entrepôt	55	25	45	5	130 (Total)

Les variables de base (quantités transportées) sont : x₁₁, x₂₁, x₂₂, x₃₂, x₃₃ et x₃₄. Le Coût Total (CT) calculé avec cette méthode est de 420.

Application de la méthode de Vogel

La méthode de Vogel, également connue sous le nom de méthode des pénalités, vise à trouver une solution initiale plus proche de l'optimum en se basant sur les différences de coûts minimales de chaque ligne et colonne. Voici la progression des allocations :

Étape 1 : Tableau initial avec les coûts unitaires, les capacités des usines (a_i), les demandes des entrepôts (b_j) et les pénalités (différences).

Usine/Entrepôt	E1	E2	E3	E4	Capacité (a_i)	Diff. Usines
Usine 1	2	4	9	6	40	2
Usine 2	3	3	2	5	20	1
Usine 3	1	3	4	8	70	2
Demande (b_j)	55	25	45	5	130
Diff. Entrepôts	1	0	2	1

Allocation initiale : X₃₁ = 55 (L'entrepôt 1 est saturé, la capacité de l'usine 3 est réduite à 15).

Allocation suivante : X₂₃ = 20 (La capacité de l'usine 2 est entièrement utilisée, la demande de l'entrepôt 3 est réduite à 25).

Allocations restantes : X₃₃ = 15, X₁₂ = 25, X₁₃ = 10 et X₁₄ = 5.

Le Coût Total (CT) obtenu avec la méthode de Vogel est de 375.

Conclusion : En comparaison avec la méthode du coin nord-ouest (CT = 420), la méthode de Vogel fournit une solution initiale moins coûteuse (CT = 375).

Exercice 3

Le contenu détaillé de l'Exercice 3 n'est pas fourni dans cet extrait.

Questions Fréquemment Posées (FAQ)

Qu'est-ce que la Recherche Opérationnelle ?
La Recherche Opérationnelle est une discipline qui utilise des méthodes scientifiques et mathématiques (modélisation, optimisation, simulation) pour aider à la prise de décision, notamment dans la planification et l'optimisation des systèmes complexes.

Quelle est la différence entre la méthode du coin nord-ouest et la méthode de Vogel ?
La méthode du coin nord-ouest est une méthode simple et rapide pour trouver une solution initiale à un problème de transport, sans prendre en compte les coûts unitaires de transport. La méthode de Vogel, en revanche, est plus sophistiquée : elle minimise les "pénalités" (différences de coûts) et fournit généralement une solution initiale de meilleure qualité, plus proche de l'optimum, bien que plus longue à calculer.

Pourquoi chercher une solution initiale dans un problème de transport ?
Une solution initiale est nécessaire comme point de départ pour des méthodes d'optimisation plus avancées, telles que la méthode du pas solitaire ou l'algorithme de Modi (Méthode de Distribution Modifiée). Ces méthodes itératives visent à améliorer la solution initiale étape par étape jusqu'à atteindre la solution optimale, c'est-à-dire le coût de transport le plus bas possible.