Recherche operationnelle semestre 2 emfb annee universitaire
Télécharger PDFCette série d'exercices de Recherche Opérationnelle, destinée aux étudiants de 3ème année (Fin et EMFB), couvre des problèmes fondamentaux d'optimisation pour l'année universitaire 2014-2015.
Exercice 1 : Problème d'optimisation de production d'un artisan
Un artisan fabrique deux articles, A et B, nécessitant chacun deux opérations : un usinage et un traitement thermique. Le produit A subit un usinage d'une heure et un traitement thermique de 3 heures. Le produit B subit un usinage de 2 heures et un traitement thermique d'une heure.
De plus, 2 kg de matière première sont nécessaires pour la composition de A et 1 kg pour celle de B. La fabrication de B se termine par un travail de finition qui dure une heure.
Toutes les 3 semaines, l'artisan dispose de l'atelier d'usinage pendant 80 heures et du four pendant 120 heures. Durant cette période, il ne peut pas consacrer plus de 35 heures au travail de finition ni stocker plus de 90 kg de matière première.
Les marges bénéficiaires s'élèvent, respectivement, à 30 dinars pour l'article A et 20 dinars pour l'article B.
- Formuler un programme linéaire correspondant au plan de production de l'artisan.
- Déterminer le plan de production optimal par la méthode graphique et le dictionnaire de simplexe.
Exercice 2 : Optimisation du revenu agricole
Un agriculteur a le choix entre deux types de culture : A et B. Il souhaite obtenir le revenu maximum de ses cultures. Pour maximiser son profit, il voudrait produire le maximum possible. Cependant, des limites lui sont imposées :
- La part de sa propriété vouée à la culture est limitée à 9 hectares.
- Sa famille et lui-même peuvent fournir au mieux 4 500 heures de travail.
- Enfin, le commerce international lui impose un quota minimum sur le type A de 6,6 hectares.
Nous savons aussi que :
- 1 kg de la récolte du type A nécessite 0,0012 hectare et 0,9 heure de travail.
- 1 kg de la récolte du type B nécessite 0,0015 hectare et 0,5 heure de travail.
À la fin de la saison, on estime vendre à 40 D/kg le type de culture A et 60 D/kg le type de culture B.
- Formuler un programme linéaire relatif à ce problème de production.
- Déterminer le plan de production optimal par le dictionnaire de simplexe qui permet de maximiser le revenu de l'agriculteur.
Exercice 3 : Optimisation des mélanges de café
Un négociant de café importe deux variétés de café verts (Colombien et Brésilien) qu'il torréfie et revend sous forme de mélanges.
Une tonne de café vert colombien coûte à l'achat 2 800 dinars et permet de produire 800 kilogrammes de café torréfié. Ce dernier a un indice de qualité de 16.
Une tonne de café vert brésilien coûte 2 700 dinars et donne 900 kilogrammes de café torréfié avec un indice de qualité de 12.
Le même équipement est partagé pour la torréfaction des deux cafés, et il est disponible 160 heures par mois. Son débit normal est de 40 kilogrammes de café torréfié par heure pour le colombien, et 50 kilogrammes par heure pour le brésilien.
Le négociant vend deux mélanges de café torréfié : Le Suprême au prix de 6 dinars le kilo, et L'Insipide, au prix de 4 dinars le kilo.
- L'indice de qualité du mélange Suprême doit être d'au moins 15.
- Le mélange Insipide ne peut pas contenir plus de 90 pour cent en poids de café torréfié d'origine brésilienne.
- Pour maintenir une image de qualité, on souhaite que le mélange Suprême assure au moins 70 pour cent du revenu des ventes chaque mois.
- Le négociant ne peut pas acheter plus de 8 tonnes de café vert colombien ni vendre plus de 4 000 kilos de mélange Suprême par mois.
Formulez deux programmes linéaires (différents mais équivalents) visant au profit mensuel maximum. Dans la première formulation, les variables de décision représentent des quantités vendues. Dans la seconde, les variables de décision représentent des quantités achetées.
Exercice 4 : Optimisation de la production multi-départements
Une unité d'un certain produit P est fabriquée par l'assemblage de 4 unités d'un élément A et 3 unités d'un élément B. Dans la fabrication de A et B, on utilise deux types de matière première (M1 et M2) disponibles en quantités de 100 et 200 unités respectivement par mois.
Les éléments A et B sont fabriqués dans trois départements utilisant chacun un processus de production différent. La technologie utilisée est résumée dans le tableau ci-après qui indique les "entrées" de matières M1 et M2 et les "sorties" d'unités A et B par "application" du processus de production par département.
| Département | Entrée de matière | Sortie d'élément | ||
|---|---|---|---|---|
| M1 | M2 | A | B | |
| 1 | 8 | 6 | 7 | 5 |
| 2 | 5 | 9 | 6 | 9 |
| 3 | 3 | 8 | 8 | 4 |
L'entreprise veut déterminer le nombre d'applications de chaque processus de production (de chaque département) qui permettrait de maximiser le nombre total d'unités de produit P.
Formuler un programme linéaire (PL).
Exercice 5 : Plans de découpage de rouleaux de papier
La compagnie de papier Nord-Ouest produit et commercialise des rouleaux de papier de quatre longueurs différentes : 12 pouces, 5 pouces, 3,5 pouces et 2 pouces. Tous les rouleaux ont une même longueur de 100 pieds. La compagnie ne fabrique que des rouleaux de 12 pouces de largeur, appelés des rouleaux standards. Les autres largeurs sont obtenues par le découpage des rouleaux standards.
La compagnie est en train d'envisager les six plans de découpage suivants (voir tableau), dont chacun résulte en une chute inférieure ou égale à 1 pouce.
| Plan de découpage | Largeur du rouleau | Chute en pouces | ||
|---|---|---|---|---|
| 5 pouces | 3,5 pouces | 2 pouces | ||
| 1 | 0 | 0 | 6 | 0 |
| 2 | 2 | 0 | 1 | 0 |
| 3 | 0 | 2 | 2 | 1 |
| 4 | 1 | 2 | 0 | 0 |
| 5 | 1 | 0 | 3 | 1 |
| 6 | 0 | 1 | 4 | 0,5 |
- Peut-on trouver un 7ème plan de découpage qui donne une chute inférieure ou égale à 1 pouce ?
-
Les demandes minimales pour les rouleaux obtenus par le découpage sont données par le tableau suivant :
Largeur du rouleau Demande minimale 5 pouces 1 500 3,5 pouces 2 000 2 pouces 500
Exercice 11 : Optimisation du transport aérien
On doit organiser un pont aérien pour transporter 1 600 personnes et 90 tonnes de bagages. Les avions disponibles sont de deux types : 12 du type A et 9 du type B.
- Le type A peut transporter, à pleine charge, 200 personnes et 6 tonnes de bagages.
- Le type B peut transporter, à pleine charge, 100 personnes et 6 tonnes de bagages.
La location d'un avion du type A coûte 800 000 F ; la location d'un avion du type B coûte 200 000 F.
Formuler un programme linéaire pour minimiser le coût de la location tout en respectant les capacités de transport.
Exercice 12 : Analyse de dictionnaires du simplexe
Les dictionnaires ci-dessous ont été obtenus après exécution de quelques itérations de la méthode du simplexe sur différents problèmes. Quelles conclusions pouvez-vous tirer sur la base de l'information contenue dans ces dictionnaires ? Les conclusions possibles sont par exemple :
- la solution courante est optimale, et vaut ... ;
- le problème est non borné parce que ... ;
- le problème est non réalisable parce que ... ;
- la solution courante n'est pas optimale ; dans ce cas, calculez la solution optimale.
a) min z
z = 5 - 12x1 - 5x3
x2 = 4 - 6x1 - x3
x4 = 5 - 4x1 - 4x3
x5 = 6 - x1 - 5x3
avec x1, x2, x3, x4, x5, x6 ≥ 0
b) max z
z = 2 + 20x1 + 4x4 - 5x3
x2 = 4 + x1 - 2x4
x5 = 6 - x1 + 3x4 - 5x3
x6 = 4 - 2x1 + 4x4 - x3
avec x1, x2, x3, x4, x5, x6 ≥ 0
c) max z
z = 5 - 3x1 - 12x2
x4 = 2 - 5x1 - 2x2
x3 = 5 - 2x1 - 3x2
x5 = 3 + x1 - 2x2
avec x1, x2, x3, x4, x5 ≥ 0
Exercice 13 : Optimisation de production en usine (Examen mai 2013)
Supposons qu'une usine fabrique 2 pièces P1 et P2 usinées dans deux ateliers A1 et A2. Les temps d'usinage sont pour P1 de 3 heures dans l'atelier A1 et de 6 heures dans l'atelier A2. Pour P2, les temps sont de 4 heures dans l'atelier A1 et de 3 heures dans l'atelier A2.
Le temps de disponibilité hebdomadaire de l'atelier A1 est de 160 heures et celui de l'atelier A2 est de 180 heures.
La marge bénéficiaire est de 1 200 pour une pièce P1 et 1 000 pour une pièce P2.
La question est : Quelle production de chaque type doit-on fabriquer pour maximiser la marge hebdomadaire ?
- Écrire le programme linéaire et résoudre graphiquement ce problème.
- Résoudre ce programme linéaire en utilisant le dictionnaire de simplexe.
- Résoudre ce programme linéaire en utilisant l'algorithme de simplexe.
Exercice 14 : Programme linéaire non borné (Examen mai 2013)
Soit le programme linéaire suivant :
Maximiser Z = 5x1 + 4x2
Sous les contraintes suivantes :
- x1 - 2x2 ≤ 5
- x1 ≤ 10
- x1, x2 ≥ 0
Note : L'objectif et les contraintes ont été interprétés pour correspondre à une structure de programme linéaire cohérente, compte tenu du format original.
Montrer que ce programme linéaire est non borné.
Exercice 15 : Programme linéaire standard et solution optimale (Juin 2013)
Soit le programme linéaire suivant :
Maximiser Z = x1 + 2x2
Sous contraintes :
- x1 + 2x2 ≤ 3
- x1 + x2 ≤ 12
- x1, x2 ≥ 0
Note : Les contraintes ont été interprétées pour correspondre à une structure de programme linéaire cohérente, compte tenu du format original. La première contrainte ambiguë `1 2 3 12 x x` a été transformée en `x1 + 2x2 ≤ 3` et la seconde `1 2 x x3 12` en `x1 + x2 ≤ 12`.
- Écrire le programme linéaire standard.
- Trouver une solution de base initiale.
- Trouver la solution optimale de ce programme.
Exercice 16 : Résolution de programme linéaire par le simplexe (Juin 2013)
Soit le programme linéaire suivant :
Maximiser Z = 2x1 + 3x2
Sous contraintes :
- x1 + 2x2 ≤ 18
- x1 + x2 ≤ 18
- x1 + x2 ≤ 8
- x1, x2 ≥ 0
Note : Les contraintes ont été interprétées pour correspondre à une structure de programme linéaire cohérente, compte tenu du format original, en assumant que `1 2 x x3 18` et `1 2 3 18 x x` étaient des formulations répétitives ou mal transcrites de contraintes impliquant x1 et x2.
- Écrire le programme linéaire standard.
- Trouver une solution de base initiale.
- Trouver la solution optimale de ce programme.
Foire Aux Questions (FAQ) sur la Recherche Opérationnelle
La recherche opérationnelle est une discipline qui utilise des méthodes scientifiques et mathématiques pour prendre de meilleures décisions.
Qu'est-ce qu'un programme linéaire (PL) ?
Un programme linéaire est un modèle mathématique pour l'optimisation d'une fonction objectif linéaire, soumise à un ensemble de contraintes linéaires. Il est largement utilisé pour résoudre des problèmes de planification, d'allocation de ressources, de production, et bien d'autres, où l'objectif est de maximiser (par exemple, le profit) ou de minimiser (par exemple, le coût).
Quand utilise-t-on la méthode du simplexe ?
La méthode du simplexe est un algorithme itératif populaire et efficace pour résoudre des programmes linéaires. Elle est utilisée lorsque le problème a plusieurs variables de décision et contraintes, rendant la résolution graphique impossible ou trop complexe. Elle permet de trouver une solution optimale en explorant les sommets du polyèdre de faisabilité.
Qu'indique un programme linéaire non borné ?
Un programme linéaire est dit non borné si la fonction objectif peut être augmentée (pour une maximisation) ou diminuée (pour une minimisation) indéfiniment sans violer les contraintes. Graphiquement, cela signifie que la région de faisabilité s'étend à l'infini dans la direction de l'amélioration de la fonction objectif, sans aucune limite.