QUESTION : Formulation d'un programme linéaire
Mots-clé : programmation linéaire, P.L ; algorithme du simplexe ; polyèdre,
sommet, ..... L'examen de Z montre que pour augmenter sa valeur numérique, il
faut ...
part of the document
rand nombre de questions posées lors de lexamen ne portaient que sur la confirmation dune lecture correcte de lénoncé.
Bonne continuation,
J.C. Jacquemin 29 mai 2002
QUESTION 1 : Formulation dun programme linéaire
K. Roth, le jardinier de Madame la comtesse, dispose dune surface de 90 m² dans le potager du château pour y cultiver ses propres légumes quil vend dans leur totalité au marché du village.
Il a décidé cette année de ne planter sur ce lopin de terre que des oignons et des poireaux dont les plants sont produits par ses soins.
Pour planter les oignons, il a le choix entre deux variétés. Dans le cas des oignons dhiver, il les plante profondément et accorde à chaque plant une superficie au sol de 2dm² ; dans le cas des oignons dété, il les plante en surface en leur laissant une superficie de 4dm². Les oignons plantés en profondeur ont un taux de survie de 81% et se vendent 0,25¬ /pièce tandis que les autres sont 90% à survivre et se vendent 0,19¬ /pièce.
Il peut également planter des poireaux : soit d été, soit d hiver. Les poireaux d hiver ont un taux de survie de 84% et ceux d été de 75%. La botte de 5 poireaux d hiver se vend 2,4¬ tandis que la botte de 10 poireaux d été se vend 1,82¬ .
Un poireau d hiver occupe 0,6dm² contre 0,3dm² pour un poireau d été.
Pour être présent sur le marché toutes les semaines sans interruption, il faut quun tiers de la production (en nombre de pièces produites) soit assuré tant pour lhiver que pour lété. Il faut également que le nombre de bottes de poireaux produites nexcède pas la moitié du nombre doignons produits.
K. Roth dispose de suffisamment de plants de chaque type de légume pour occuper sa partie de potager.
Quel est lassortiment de plants qui maximisera les recettes de K. Roth sur le marché du village au cours de lannée à venir ?
Formulez le problème comme un programme linéaire.
Ecrivez son dual et interprétez deux variables de ce dernier.
Solution :
(N.B. Après un rapide survol des copies, 4 formulations alternatives différentes acceptables ont été proposées par les étudiants lors de lexamen, celle qui suit est la plus proche littéralement de lénoncé, mais il en est de plus compactes.)
Variables de décision :
XOH, XOE, XPH, XPE ( 0 représentent respectivement le nombre de plants doignons dhiver, doignons dété, de poireaux dhiver et de poireaux dété qui seront plantés par K. Roth.
Objectif :
MAX Z, avec Z, les recettes totales exprimées en ¬ perçues par K. Roth sur le marché du village au cours de l année prochaine. Il ne peut évidemment vendre que les plants arrivés à maturité qui ont survécu.
Z = (0,25.0,81)XOH + (0,19.0,9)XOE + (0,48.0,84)XPH + (0,182.0,75)XPE
Contraintes :
Occupation du sol :
2XOH + 4XOE + 0,6XPH + 0,3XPE ( 9000 dm²
3 contraintes de gamme :
Sur la production dété :
0,9XOE + 0,75XPE ( 1/3(0,81XOH + 0,9XOE + 0,84XPH + 0,75XPE)
ou
0,27 XOH 0,6 XOE + 0,28 XPH 0,5 XPE ( 0
Sur la production dhiver :
0,81XOH + 0,84XPH ( 1/3(0,81XOH + 0,9XOE + 0,84XPH + 0,75XPE)
ou
- 0,54 XOH + 0,3 XOE 0,56 XPH + 0,25 XPE ( 0
Générale entre oignons et poireaux :
½.(0,81XOH + 0,9XOE) ( 0,84/5 XPH + 0,75/10XPE
ou
-0,405XOH - 0,45XOE + 0,168XPH + 0,075 XPE ( 0
Le programme linéaire : (résumé)
MAX Z
Z = 0,2025XOH + 0,171XOE + 0,4082XPH + 0,1365XPE
s.c.q.
2XOH + 4XOE + 0,6XPH + 0,3XPE ( 9000
0,27 XOH 0,6 XOE + 0,28 XPH 0,5 XPE ( 0
- 0,54 XOH + 0,3 XOE 0,56 XPH + 0,25 XPE ( 0
- 0,405XOH - 0,45XOE + 0,168XPH + 0,075 XPE ( 0
Tableau de conversion primal dual
MinY1240,60,39000Y20,270,60,280,50Y3-0,540,30,560,250Y4-0,405-0,450,1680,0750Max0,20250,1710,40820,1365(
Donc le programme dual peut sécrire :
Min W = 9000 Y1
s.c.q.
2Y1 + 0,27Y2 0,54Y3 0,405Y4 ( 0,2025
4Y1 + 0,6Y2 + 0,3Y3 0,45Y4 ( 0,171
0,6Y1 + 0,28Y2 + 0,56Y3 + 0,168Y4 ( 0,4082
0,3Y1 + 0,5Y2 + 0,25Y3 + 0,075Y4 ( 0,1365
Y1, Y2, Y3, Y4 ( 0
Y1, sera la contribution marginale au chiffre daffaires de K. Roth sur le marché du village dun dm² supplémentaire de culture dans son potager.
Y2, sera la contribution marginale au chiffre daffaires de K. Roth sur le marché du village dun relâchement dune unité (de la contrainte de production dun tiers de la production totale) sur la production dété.
QUESTION 2 : stocks
La S.A. D. ALIAT est spécialisée dans la production de bouquets variés de fleurs fraiches. Toute sa production est livrée à différentes organisations qui lui commandent régulièrement et de façon continue 650 bouquets par semaine, vendus 62,5¬ /pièce.
La fabrication des bouquets se fait par lots. Chaque lot de bouquets occasionne des frais fixes de 100 ¬ (nettoyage et rangement des tables de travail, préparation des matériaux, etc.) et le prix de revient de chaque bouquet est de 45¬ .
Etant donné les conditions de conservation et la qualité différente des fleurs, les frais de possession par semaine de stockage s élèvent à 3% du prix de vente.
La S.A. D. ALIAT peut fabriquer 150 bouquets par jour. Une semaine compte sept jours.
Quelle quantité de bouquets la S.A. D. ALIAT doit-elle composer par lot ?
Ecrivez la fonction à optimiser.
Résolvez analytiquement le problème.
Répondez également aux questions suivantes :
Quelle capacité maximale de stockage (en nombre de bouquets) faut-il prévoir ?
Dans la comptabilité analytique de la S.A, on a prévu dinscrire le coût hebdomadaire de possession de bouquets, à quel montant se chiffre-t-il ?
Idem pour les frais fixes de préparation des lots de bouquets.
Solution
Il sagit du modèle manufacturier. Le graphique est le graphique standard (voir syllabus).
Données :
r (rythme de la demande) = 650bqts/sem.
p (rythme de la production) = 150bqts/jour ou 1050bqts/sem.
l (coût de lancement/lot) = 100¬ .
s (coût de possession/bqt/sem.) = 3% de 62,5¬ = 1,875¬ .
L unité de temps de référence sera la semaine, vu les questions sur les montants hebdomadaires demandés dans la comptabilité analytique.
On cherche Q la quantité de bouquets à fabriquer en une fois.
Le profit par cycle (¬ ) : Pc (Q) =
-100 + (62,5-45)Q 1,875[Q/(2.650)].[Q(1-(650/1050)] =
-100 + 17,5Q [(1,875.Q².400)/(1300.1050)] = -100 + 17,5Q (5Q²/650.14)
a) Le profit par unité de temps (semaine) : P(Q) = Pc(Q).(650/Q) =
[-100 + 17,5Q (2,5Q²/650.7)].(650/Q) = - 65000/Q + 11375 5Q/14
b) On maximise P(Q).
dP(Q)/dQ = 65000/Q² - 5/14 à égaler à 0 ( Q² = (65000.14)/5 = 182000.
Donc Q*= 426,615 ( 427 bouquets par lots.
c) La capacité maximale de stockage à prévoir est égale au stock maximal accumulé jusquà la fin de la production dun lot.
Le stock saccroît de 1050 650 = 400 bouquets par semaine quand la production est en cours. La production dure 426,615/1050 = 0,4063 semaines, donc le stock maximal sera égal à 400. 0,4063 = 162,52 ( 163 bouquets.
Le profit par semaine : P(Q) = - 65000/Q + 11375 5Q/14, le premier terme est égal au coût de lancement par semaine (en ¬ ) ; le dernier au coût hebdomadaire de possession., donc :
Le coût hebdomadaire de possession = 5Q/14 = 152,36¬ .
Le coût hebdomadaire de lancement doit lui être égal, vérification : 65000/426,615 = 152,36¬ .
QUESTION 3 : Analyse de sensibilité
Les ingrédients de base des compositions de G.FROI, glacier bien connu de tous, sont des mesures de praliné, de vanille et de chocolat dont les disponibilités quotidiennes une fois épuisées ne peuvent être renouvelées au cours de la journée. Il dispose aussi d'un stock quotidien de cuillères plastiques qu'il utilise pour garnir ses spécialités.
Les tableaux suivants présentent respectivement le tableau initial et le tableau final après résolution du problème original par la méthode simplexe. Les unités de la fonction objectif sont des ¬ .
Etant donné sa formation en programmation linéaire, il décide de négocier avec le fournisseur de mesures de chocolat pour en augmenter la disponibilité quotidienne.
Il vous est demandé de justifier, par analyse de sensibilité :
a)- pourquoi il négocie avec le fournisseur de chocolat et non avec le fournisseur de vanille. :
Parce que (sans autres informations) c est la ressource qui est associée à la valeur duale la plus élevée par mesure : 2¬ ; au lieu de 2/3 ¬ par mesure de vanille. Les autres ressources n étant marginalement pas intéressantes.
b)- le prix maximal qu il peut admettre de payer pour une mesure additionnelle de chocolat ;
Il est égal à la valeur duale de la ressource, soit 2¬ .
c)- le nombre de mesures additionnelles de chocolat qu'il peut acquérir au plus sans devoir changer de solution de base ;
Il sagit dappliquer une analyse de sensibilité à laugmentation dune ressource. Changer de solution de base implique un pivotage. Donc on demande quelle augmentation maximale des mesures de chocolat ((, avec ( ( 0 ) est tolérable jusquà la première irréalisibilité. On calcule donc les modifications du côté droit via la propriété fondamentale 2 :
(b*1= 1.( = (
(b*2= 0.( = 0
(b*3= -2.( = -2(
(b*4= -1.( = -(
En ajoutant ces modifications au côté droit, il faut trouver la valeur maximale de ( qui ne rend pas négative la valeur modifiée, soit :
10 + ( ( 0 ; 10 + 0 ( 0 ; 10 - 2( ( 0 ( ( ( 5 ; 10 - ( ( 0 ( ( ( 10.
Donc ( = 5.
d)- revenant aux tableaux présentés infra, que se passera-t-il si les mesures de vanille coûtant plus cher, la marge de la spécialité C passe à 3 ¬ au lieu de 4 alors que l incorporation de la vanille dans la spécialité C a été réduite de moitié ?
N.B. On entend par mesure additionnelle, une mesure qui vient s ajouter au stock quotidien disponible originalement.
(S=Superglaçon, C=Cristalchoco)
S C S1 S2 S3 S4
Z -2 -4 0 0 0 0 0
S1 1 0 1 0 0 0 10 mesures de chocolat
S2 0 2 0 1 0 0 20 fois 3 mesures de vanille Tableau initial
S3 2 1 0 0 1 0 40 mesures de praliné
S4 1 2 0 0 0 1 40 cuillères plastiques
Z 0 0 2 2 0 0 60
S 1 0 1 0 0 0 10
C 0 1 0 1/2 0 0 10 Tableau final
S3 0 0 -2 -1/2 1 0 10
S4 0 0 -1 -1 0 1 10
Il sagit de la modification des coefficients dune variable de base, la variable x2 (C) :
On a : (c2 = -1 et (a22 = -1, les propriétés fondamentales 3 et 4 sont mises en uvre.
Par la p.f. 3, on a : (z*2 - c2 = -(c2 + y*2. (a22 = -(-1) + 2.(-1) = -1
Par la p.f. 4, on a :
(a*12 = s*12. (a22 = 0.(-1) = 0
(a*22 = s*22. (a22 = 1/2 .(-1) = -1/2.
(a*32 = s*32. (a22 = -1/2.(-1) = 1/2
(a*42 = s*42. (a22 = (-1).(-1) = 1
Donc en ajoutant ces modifications au tableau final, on, obtient :
Z 0 -1 2 2 0 0 60
S 1 0 1 0 0 0 10
C 0 1/2 0 1/2 0 0 10 Tableau modifié
S3 0 1/2 -2 -1/2 1 0 10
S4 0 1 -1 -1 0 1 10
On rétablit la cohérence :
Z 0 0 2 3 0 0 80
S 1 0 1 0 0 0 10
C 0 1 0 1 0 0 20 Tableau revu
S3 0 0 -2 -1 1 0 0
S4 0 0 -1 -2 0 1 -10
Le tableau revu est irréalisable, on applique la MDS : S2 entre et S4 sort.
Z 0 0 1/2 0 0 1 65
S 1 0 1 0 0 0 10
C 0 1 -1/2 0 0 1/2 15 Nouveau tableau
S3 0 0 -3/2 0 1 -1/2 5 final.
S2 0 0 1/2 1 0 -1/2 5
Le profit a augmenté de 5¬ grâce à l augmentation de la production de C ((+ de 50%) permise par la moindre consommation de vanille et ce, malgré la diminution de la marge de C ((- de 25%).
QUESTION 4 : réseaux
GROZTADT, la capitale du ONZLAND doit adapter l infrastructure de communications desservant les services administratifs du gouvernement fédéral via les gaines de liaisons télématiques existantes représentées par les branches du réseau dont le schéma est dessiné infra. Ces gaines devront accueillir :
un câble optique de nouvelle génération permettant les branchements intermédiaires (en T) et permettant de relier entre eux, deux à deux, les 9 sites gouvernementaux identifiés par une lettre aux nuds du schéma ;
un nouveau réseau téléphonique crypté qui permettra de mettre en contact deux à deux tous les sites sauf le site I pour lequel ce câblage napparaît pas nécessaire.
Dans le cas de chacun des deux réseaux, le coût dinstallation est directement proportionnel à la longueur des gaines techniques dans lesquelles ils seront installés. De plus, les technologies du câble optique ainsi que de la téléphonie cryptée imposent de placer un backbone (câble principal dun seul tenant) le plus long possible pour éviter, autant que faire se peut, le branchement (en T) de lignes de plus bas niveau, réduisant lefficacité du système.
On vous demande le schéma dinstallation des deux réseaux, la longueur de chacun, le schéma dinstallation des deux backbones ainsi que la longueur de chacun.
Attention aux solutions multiples possibles entre lesquelles il faut choisir celle qui permet de rencontrer au mieux la contrainte portant sur les backbones.
N.B. Il est nécessaire, malgré la simplicité du schéma, de résoudre les problèmes demandés en suivant une démarche algorithmique explicite.
Il sagit de chercher un ou plusieurs arbres détendue minimale sur tous les nuds :
Solution :
1) DBACEHGJI avec un T en G vers F = AEM 1 (lg 21) dont BB1 (DBACEHGJI) lg 19.
2) DBACEHGJ avec un T en G vers F = AEM 2 (lg 19) dont BB2 (DBACEHGJ) lg 17.
Représentation du 1er arbre détendue minimale en bleu.
Dans ce réseau, il y a trois possibilités de câbles dun seul tenant (backbones) avec chaque fois un seul branchement en T :
FGJI : branchement en G vers les autres nuds du réseau, longueur 7.
FGHECABD : branchement en G vers les nuds J et I, longueur 16.
IJGHECABD : branchement en G vers le nud F, longueur 19.
Le câble dun seul tenant le plus long sera IJGHECABD (en doubles traits dans le schéma supra).
N.B. Un autre arbre détendue minimale était possible :
DBACEHGF avec un T en H vers I et J = AEM 1 (lg 21)
Représentation du 1er arbre détendue minimale alternatif en bleu.
Dans ce réseau, il y a trois possibilités de câbles dun seul tenant (backbones) avec chaque
fois un seul branchement en T :
FGHIJ : branchement en H vers les autres nuds du réseau, longueur 8.
FGHECABD : branchement en H vers les nuds J et I, longueur 16.
JIHECABD : branchement en H vers les nuds G et F, longueur 18.
Le câble dun seul tenant le plus long est JIHECABD (en doubles traits dans le schéma supra) mais ce nest pas le backbone le plus long possible puisque dans le cas précédent le câble
IJGHECABD était plus long dune unité (19 contre 18).
Pour le second arbre détendue minimale, il suffit délaguer la branche IJ de longueur 2, I étant un nud terminal, idem dans le backbone qui devient JGHECABD : branchement en G vers le nud F, longueur 17.
Fl.
Blô
F
6
B
Fl.
Blô
3
4
4
5
5
1
1
2
2
3
3
2
3
J
H
I
E
C
A
G
D
(
Fl.
Blô
F
6
B
2
4
4
5
2
3
3
2
3
J
H
I
E
C
A
G
D
Fl.
Blô
3
5
1
1
Fl.
Blô
F
6
B
2
4
4
5
2
3
3
2
3
J
H
I
E
C
A
G
D
Fl.
Blô
3
5
1
1
