Exercices de programmation linéaire

IAE de Grenoble, CAAE
Cours de SIAD, Professeur B. Ballaz I Exercices de programmation linéaire
(1, 2, 3, 4, 5.1 et 5.2) sont dans l'objectif minimum.... 1 Résoudre par la méthode graphique :
Max [CA] : 4 xa + 6 xb
(1) 6 xa + 5 xb ? 30
(2) 3 xa + 9 xb ? 27
(3) xa ? 5
(4) xb ? 4
2 Avec le même système de contraintes (Exercice 1), chercher Min [Coûts] :
2 xa + 2 xb 3 Résoudre par la méthode graphique :
Min [Z] : xa + 2 xb
(1) 2 xa + xb ? 10
(2) xa + xb = 8
(3) xb ? 2 4 Vérifier les solutions graphiques des exercices 1, 2, 3 en utilisant le
solveur d'Excel. 5 Soit le programme linéaire suivant :
Min [Z] : 2 xa + 4 xb
(1) 6 xa + 2 xb ? 12
(2) 4 xa + 8 xb ? 32
(3) xa ? 5
(4) xb ? 2
5.1 Résoudre par la méthode graphique
5.2 Résoudre avec le solveur d'Excel
5.3 Que peut-on constater lorsque l'on examine le coût marginal des
variables d'écart hors base dans la solution optimale ?
5.4 Quelle conclusion en tirer ? Donner une interprétation géométrique. 6 Réduire le problème suivant à un programme linéaire à une seule
contrainte.
Min [Z] : 2 xa + 4 xb
(1) 6 xa + 2 xb ? 12
(2) xa ? 5
(3) xb ? 2 ( Piste : faire un changement de variable en utilisant les contraintes (2)
et (3), sachant que toute variable d'un PL est >=0 ) 7 Résoudre par la méthode graphique le problème suivant :
Min [Z] : 10 xa + 16 xb+ 8 xc
(1) xa + 2 xb ? 6
(2) xa + xb + xc ? 12
(Piste : utiliser le programme Dual) 8 Résoudre le Primal et le Dual de l'exercice 6 à l'aide du solveur
d'Excel, vérifier les propriétés de leurs solutions optimales. 9. Déterminer le plan de travail journalier optimal d'un atelier artisanal
qui fabrique des articles de poterie et des articles d'émaux, sachant
que :
- Il faut 1 h de temps de fabrication pour une poterie et 4h pour un
émail, la charge de travail pour les émaux ne doit pas dépasser celle
de la poterie de plus de 160 h.
- La production d'articles de poterie ne doit pas excéder de plus de 30
unités la production d'émaux
- Le nombre total d'articles fabriqués ne doit pas être supérieur à 80
unités par jour.
- Le bénéfice est de 20 E pour une poterie et de 60 E pour les émaux sur
cuivre.
On utilisera la méthode de résolution graphique et on vérifiera la solution
obtenue avec le solveur d'Excel.
(Solution optimale : Xpoterie = 32 ; Xemaux = 48 ; Bénéfice total = 3520) .
10. Un éleveur peut acheter deux types de produit, Bovo et Vogra, pour une
alimentation équilibrée de son troupeau. La composition (en kg) de ces
deux marques en composants nutritifs élémentaires et la ration minimale
quotidienne nécessaire (en kg) sont indiquées dans le tableau suivant :
| |Bovo |Vogra |Ration |
| | | |journalière |
|Composant A |0,1 |0 |0,4 |
|Composant B |0 |0,1 |0,6 |
|Composant C |0,1 |0,2 |2 |
|Composant D |0,2 |0,1 |1,7 |
|Coût d'achat au |100 |40 | |
|kg en E | | | | Quelles quantités d'aliments Bovo et Vogra notre éleveur doit-il acheter
chaque jour de façon à réaliser l'alimentation satisfaisante de coût
minimum ?
(méthode graphique et solveur).
(Solution Optimale : xBovo = 4 kg ; yVogra = 9 kg, Coût d'achat total =
760 E)
Exprimer le programme dual, le résoudre et vérifier les propriétés de la
dualité, chercher sa signification économique. II Arbre de décision : Cas SRD V3.0 Afin de renouveler sa gamme de véhicules équipés d'un moteur diesel, la
société SRD envisage de lancer un partenariat pour le co-développement d'un
nouveau moteur, avec son fournisseur spécialisé dans la motorisation
diesel.
Les choix possibles pour la conception du prototype et des préséries
industrielles sont les suivants :
1 - Moteur diesel « classique », reconditionné, dont le coût de
développement et d'industrialisation est évalué à 1 MEuros, avec la
certitude de pouvoir le réaliser. 2 - Moteur « turbo » diesel, dont le coût de développement serait de 1,6
MEuros, avec une probabilité de réussite estimée à 0,6. 3 - Moteur « Common Rail » diesel dont le coût de développement s'élève à
2MEuros, avec 50 % de chance de réussite. En fonction de la contrainte de temps imposée par les annonces faites par
les entreprises concurrentes, en cas d'échec de la première approche, une
deuxième approche différente de celle qui a échoué pourraient être tentée.
La première approche (Moteur diesel classique) reste toujours envisagée et
en ce qui concerne l'autre approche possible, du fait que certaines études
seront réutilisables et qu'un effet d'expérience sera obtenu, SRD espère
pouvoir améliorer leurs probabilités de réussite :
- option « Turbo », probabilité de réussite: 0,8
- option « Common Rail », probabilité de réussite: 0,7
Les coûts de développement resteraient les mêmes. Pour chacun de ces choix technologiques débouchant sur un nouveau produit,
la réussite commerciale éventuelle du lancement du nouveau produit conduit
les responsables de SRD à envisager deux hypothèses :
- une hypothèse basse, de probabilité 0,6, qui devrait dégager une
marge commerciale globale de 3 MEuros sur le cycle de vie du produit pour
l'approche « Turbo » ou « Common Rail », 1,5 MEuros pour l'approche
classique.
- une hypothèse haute, de probabilité 0,4 dont on estime qu'elle
améliorera de 100% la marge commerciale attendue, quelle que soit
l'approche retenue.
Avant de se lancer dans la réalisation du prototype, une étude préalable de
faisabilité sera demandée au fournisseur. Le coût de cette étude est évalué
à 0,2 MEuros et on estime à 80% la probabilité qu'elle conclut à la
faisabilité du projet, quel que soit le choix de technologie pour la
conception du prototype. La direction de SRD doit-elle se lancer dans ce nouveau projet ? Quel
serait son meilleur choix ? (Solution : l'espérance de gain optimale (0,688 ME) est obtenue en
choisissant l'approche Turbo, puis Classique en cas d'échec)