Examen recherche operationnelle emfb mai 2016 -Programmation
Télécharger PDFExercice 1 : Problème de Transport
Description du Problème
Considérons le problème de transport suivant où des usines doivent acheminer des produits vers des entrepôts. Les coûts unitaires de transport et les capacités/demandes sont indiqués dans le tableau ci-dessous.
| Usine | Entrepôt 1 | Entrepôt 2 | Entrepôt 3 | Entrepôt 4 | Capacité (Unités) |
|---|---|---|---|---|---|
| Usine 1 | 7 | 3 | 3 | 2 | 30 |
| Usine 2 | 3 | 4 | 7 | 7 | 35 |
| Usine 3 | 5 | 3 | 1 | 9 | 30 |
| Usine 4 | 6 | 4 | 8 | 5 | 55 |
| Demande (Unités) | 20 | 45 | 45 | 40 | Total: 150 |
Questions
Écrire le programme linéaire de ce problème de transport.
Un programme linéaire (PL) pour un problème de transport vise à minimiser le coût total de transport. Il est formulé avec des variables de décision xij représentant la quantité transportée de l'usine i vers l'entrepôt j. La fonction objectif minimise la somme des produits des coûts unitaires cij par les quantités xij. Les contraintes incluent les capacités d'offre de chaque usine et les demandes de chaque entrepôt.
Trouver les variables de base de ce problème de transport selon la méthode du coin nord-ouest.
La méthode du coin nord-ouest est un algorithme simple pour trouver une solution de base initiale réalisable à un problème de transport. Elle commence par allouer la quantité maximale possible à la cellule du coin supérieur gauche du tableau des coûts (le "coin nord-ouest"), puis ajuste les capacités d'offre et les demandes avant de passer à la cellule suivante.
Exercice 2 : Résolution de Problèmes de Transport Avancée
Description du Problème
Le tableau suivant détaille les coûts unitaires de transport entre différentes usines et entrepôts, ainsi que les capacités de production de chaque usine et les demandes de chaque entrepôt.
| Usine | Entrepôt 1 | Entrepôt 2 | Entrepôt 3 | Entrepôt 4 | Capacité (Unités) |
|---|---|---|---|---|---|
| Usine 1 | 2 | 4 | 9 | 6 | 40 |
| Usine 2 | 3 | 3 | 2 | 5 | 20 |
| Usine 3 | 1 | 3 | 4 | 8 | 70 |
| Demande (Unités) | 55 | 25 | 45 | 5 | Total: 130 |
Questions
Modéliser ce problème de transport sous la forme d’un programme linéaire.
La modélisation consiste à formuler mathématiquement le problème en définissant les variables de décision (quantités transportées), la fonction objectif à minimiser (coût total) et l'ensemble des contraintes (capacités des usines, demandes des entrepôts et non-négativité des variables).
Trouver une solution de base initiale ainsi que le coût total à l’aide des deux méthodes suivantes :
La méthode du coin nord-ouest.
La méthode de Vogel.
La méthode d'approximation de Vogel (VAM) est une heuristique qui cherche à trouver une meilleure solution de base initiale que la méthode du coin nord-ouest en se basant sur les "pénalités" (différences entre les deux coûts les plus bas) de chaque ligne et colonne du tableau des coûts. Elle tend à produire des solutions initiales plus proches de l'optimum.
Laquelle est la moins coûteuse ?
Exercice 3 : Résolution Graphique de Programme Linéaire
Description du Modèle
Soit (P), le modèle linéaire suivant :
Maximiser z = c1x1 + c2x2
Sous les contraintes :
- 2x1 + 5x2 ≥ 10 (1)
- 2x1 + 2x2 ≤ 10 (2)
- -2x1 + 3x2 ≤ 0 (3)
- x1 ≤ 5 (4)
- x1, x2 ≥ 0 (5)
Questions
Déterminer graphiquement l’ensemble des solutions admissibles de (P). Énumérer les sommets de cette région admissible.
L'ensemble des solutions admissibles, aussi appelé région réalisable, représente l'ensemble de tous les points (x1, x2) du plan qui satisfont simultanément toutes les contraintes du programme linéaire. Graphiquement, il s'agit d'un polygone convexe dont les sommets sont des points d'intersection de certaines contraintes.
Résoudre graphiquement le modèle (P) dans le cas où c1 = 3 et c2 = 4 : donner une solution optimale et la valeur de la fonction-objectif pour cette solution.
La résolution graphique d'un programme linéaire implique de tracer la fonction objectif (ligne d'isoprofit pour une maximisation ou ligne d'isocoût pour une minimisation) et de la déplacer parallèlement à elle-même dans la direction d'optimisation jusqu'à ce qu'elle atteigne le dernier point de la région admissible.
Indiquer comment serait modifiée la réponse à la question (b) si le membre droit de la contrainte (2) passait de 10 à 12 : déterminer la région admissible du modèle modifié (P’), puis donner la nouvelle solution optimale et la valeur de z correspondante.
Résoudre graphiquement le modèle (P) dans le cas où c1 = 3 et c2 = 3.
Indiquer comment serait modifiée la réponse à la question précédente si le membre droit de la contrainte (2) passait de 10 à 12.
Foire Aux Questions (FAQ) sur la Recherche Opérationnelle
Qu'est-ce qu'un problème de transport en recherche opérationnelle ?
Un problème de transport est un modèle de programmation linéaire qui cherche à optimiser la distribution de biens depuis plusieurs sources (ex: usines) vers plusieurs destinations (ex: entrepôts) afin de minimiser le coût total de transport, tout en respectant les capacités de production et les demandes. C'est un outil fondamental en logistique et gestion de la chaîne d'approvisionnement.
Pourquoi utilise-t-on des méthodes comme le coin nord-ouest ou Vogel pour les problèmes de transport ?
Ces méthodes sont des heuristiques utilisées pour trouver rapidement une solution de base initiale réalisable aux problèmes de transport. Bien qu'elles ne garantissent pas toujours une solution optimale, elles fournissent un point de départ pour des algorithmes d'optimisation plus complexes, et sont souvent utilisées pour des estimations rapides ou comme première étape dans des méthodes itératives.
Quel est l'intérêt de la résolution graphique pour les programmes linéaires ?
La résolution graphique est une méthode visuelle et intuitive pour résoudre des programmes linéaires à deux variables. Elle permet de comprendre géométriquement les concepts clés comme la région admissible, les contraintes actives et comment la fonction objectif se déplace pour trouver la solution optimale. C'est un excellent outil pédagogique avant d'aborder des méthodes algébriques plus complexes.