QUESTION : Formulation d'un programme linéaire

ANNEE ACADEMIQUE 2001-2002
Le 29 mai 2002
PREMIERE LICENCE :
INTRODUCTION A LA RECHERCHE OPERATIONNELLE
EXAMEN : proposition de corrigé

(Document revu le 31 mai 2002)
Notes :

- Ceci n'est qu'une proposition de corrigé, d'autres interprétations
sont sans doute possibles et sont bien entendu admises si elles
correspondent à l'énoncé.

- Ce corrigé (du moins une partie importante de ce dernier) a été
produit en un très court laps de temps, des coquilles, voire des
erreurs de calculs, pourraient subsister ça et là, n'hésitez pas à me
communiquer (de préférence par courrier électronique) vos remarques.

- Si vos réponses divergent de celles qui sont proposées ici, ne vous
croyez pas en erreur pour autant. C'est la cohérence de votre démarche
qui importe, pas uniquement la réponse finale.

- Mes observations générales sur le déroulement de l'examen :

o Comme pour le test, vous avez été plus lents que la moyenne de
vos prédécesseurs.

o Vous avez été en moyenne également plus concentrés et appliqués.

o Vous étiez inquiets, un grand nombre de questions posées lors de
l'examen ne portaient que sur la confirmation d'une lecture
correcte de l'énoncé.

Bonne continuation,

J.C. Jacquemin 29 mai 2002
QUESTION 1 : Formulation d'un programme linéaire

K. Roth, le jardinier de Madame la comtesse, dispose d'une surface de 90 m²
dans le potager du château pour y cultiver ses propres légumes qu'il 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 d'hiver, 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,25E/pièce tandis que les autres sont 90% à survivre et se vendent
0,19E/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,4E tandis que la botte de 10 poireaux
d'été se vend 1,82E.
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 qu'un tiers de la production (en nombre de pièces produites) soit
assuré tant pour l'hiver que pour l'été. Il faut également que le nombre de
bottes de poireaux produites n'excède pas la moitié du nombre d'oignons
produits.
K. Roth dispose de suffisamment de plants de chaque type de légume pour
occuper sa partie de potager.
Quel est l'assortiment de plants qui maximisera les recettes de K. Roth sur
le marché du village au cours de l'anné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
l'examen, 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
d'oignons d'hiver, d'oignons d'été, de poireaux d'hiver et de poireaux
d'été qui seront plantés par K. Roth.

Objectif :

MAX Z, avec Z, les recettes totales exprimées en E 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 d'hiver :
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
| | | | | |Min | |
|Y1 |2 |4 |0,6 |0,3 |9000 | |
|Y2 |0,27 |0,6 |0,28 |0,5 |0 | |
|Y3 |-0,54 |0,3 |0,56 |0,25 |0 | |
|Y4 |-0,405|-0,45|0,168 |0,075 |0 | |
|Max |0,2025|0,171|0,4082|0,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 d'affaires de K. Roth sur le
marché du village d'un dm² supplémentaire de culture dans son potager.

Y2, sera la contribution marginale au chiffre d'affaires de K. Roth sur le
marché du village d'un relâchement d'une unité (de la contrainte de
production d'un 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,5E/pièce.
La fabrication des bouquets se fait par lots. Chaque lot de bouquets
occasionne des frais fixes de 100 E (nettoyage et rangement des tables de
travail, préparation des matériaux, etc.) et le prix de revient de chaque
bouquet est de 45E.
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 ?

a) Ecrivez la fonction à optimiser.
b) Résolvez analytiquement le problème.
c) 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 d'inscrire 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 s'agit 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) = 100E.
s (coût de possession/bqt/sem.) = 3% de 62,5E = 1,875E.

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 (E) : 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 d'un lot.
Le stock s'accroî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 E) ; le dernier au coût
hebdomadaire de possession., donc :
Le coût hebdomadaire de possession = 5Q/14 = 152,36E.
Le coût hebdomadaire de lancement doit lui être égal, vérification :
65000/426,615 = 152,36E.

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 E.

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 : 2E ; au lieu de 2/3 E par
mesure de vanille. Les autres ressources n'étant marginalement pas
intéressantes.
b)- le prix maximal qu'il peut admettre de payer pou