en une : Le raisonnement par récurrence

Programmation linéaire

Mathematiques > sujets expliqués - 21/04/2009 - correction
                
Bonjour,
Alors plusieurs petites choses avant de rentrer dans le vif du sujet. Tout

d'abord un petit rappel sur la prog linéaire: ce sont des problèmes

d'optimisation ou la fonction objectif (celle que tu cherches a minimiser ou

maximiser selon les cas) ainsi que les contraintes sont linéaires. Si certains

des termes utilisés ici ne sont pas clairs je te conseille d'aller voir ce

qu'ils signifient tout de suite car c'est la base!
Donc ici (on commence par l'exercice 1) on veut minimiser le coût total du

transport de tous les produits, avec des conditions particulières à respecter

(tel magasin doit avoir tant d'unité, tel entrepot a tant d'unité de produit

etc...)
Donc tout d'abord il faut modeliser le problème:
- la fonction objectif va être le coût total du transport. Il faut donc

introduire la matrice Q des quantités transportées entre chaque entrepot et

magasin. Q est alors de la même taille que la matrice de coûts unitaires (que

l'on notera C) et la matrice C.Q ( "." n'est pas le produit usuel des matrices,

mais le produits terme a terme: par exemple C.Q(1,1)= C(1,1)*Q(1,1) ) représente

le coût total; et donc la fonction objectif!
Maintenant listons les contraintes (qui vont donc faire intervenir Q):
- Q>=0 (tous les termes de Q st positifs) tout simplement parce que les

quantités que l'on transporte sont forcément positives ou nulles!
- on note D le vecteur ligne des quantités demandées; pour tout magasin M,

$\sum_{E\in entrepots}^{}$Q(M,E) = D(M) cad la quantité dans chaque

magasins, venant de tout entrepots, doit être egale à la demande!
- enfin, on note Disp le vecteur ligne des quantités disponibles dans chaque

entrepot; pour tout entrepot E: $\sum_{M \in magasins}^{}$Q(M, E) <=

Disp(E) ; la quantité de produit exporté par un entrepot vers les différents

magasins ne peut etre supérieure à son stock!
2/ cf la pj .xls
3/ Pour utiliser le solver d'excel, il est probable que tu doives l'installer

avant (je l'ai cherché et j'ai du l'installer!) Pour cela option excel >

Complements > complement solver. Une fois installé tu devrais avoir une option

solver qui apparait dans ta barre!
Maintenant pour l'utiliser: lance le solver (moi c'est dans l'onglet donnees

mais j'utilise 2007). Il te demande cellule cible a definir: tu mets la case ou

tu calcules la fonction objectif (dans mon doc c'est la cellule K14)
Ensuite il te demande si c'est un min, max, valeur -> min.
Cellules variables c'est bien sur ton tableau des quantités Q!
Puis tu dois rajouter les contraintes (ça peut paraître fastidieux mais en

rajoutant des cases bien choisies correspondant au stock total dans un magasin

ou un entrepot ca se fait très bien: regarde ma feuille excel)
Ensuite tu solves et excel te donne la réponse: cout minimal total=96 ainsi que

les quantites que tu vas transporter de chaque entrepot à chaque magasin (ton

tableau s'est rempli!)
Pour les questions 4 et 5, je te laisse jouer avec le doc excel. Il suffit de

changer quelques chiffres et de relancer le solver pour voir ce qui se passe.

COncernant l'exercice 2, c'est exactement la même chose sauf que le tableau (ou

matrice!) a une taille de 3*3 au lieu de 3*6! Je te laisse donc le faire tout

seul pour que tu puisses voir si tu as compris (suis exactement le même

raisonnement que dans l'ex1 pour modeliser le pb)

J'espère que cela a pu t'aider. Il est assez difficile d'aider à distance mais

j'ai essayé d'être le plus clair possible.

Alexandre
Documents attachés :     
. voir
. téléchager