simplex.doc - site Patrick GRANDADAM

ALGO-LANGAGE C++ CHAPITRE : LES FONCTIONS.
SUJET : Ecrire un programme qui résout un problème de programmation linéaire avec
comme point de départ La saisie du tableau de calcul et comme résultat le
tableau à la fin des itérations.
EXPOSE DE LA METHODE MANUELLE A TRAVERS UN EXEMPLE : Problème d'optimisation de production de papier :
Deux qualités de papier peuvent être produites sur la machine de production
de l'entreprise. Les limites hebdomadaires de production sont de 400 tonnes
de qualité X et 300 tonnes de qualité Y. On dispose de 160 heures de
production et en une heure, on peut produire 5 tonnes de X ou 2,5 tonnes de
Y.
La marge financière est de 20 F la tonne de X et 50 F la tonne de Y.
Sachant que les quantités absorbables par le marché sont très supérieures à
celles que l'on peut produire dans l'usine, trouver les quantités optimales
de X et de Y à produire pendant la semaine pour maximiser la marge de
l'entreprise. 1. Mettre le problème en équations ou inéquations.
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . c'est la
fonction économique : Z, on cherche à maximiser Z. 2. Transformer les inéquations en équations
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
3. Trouver une solution évidente !
x = . . . y = . . . e1 = . . . e2 = . . .
e3 = . . .
4. Représenter le tout en tableau :
| | |x |y |e1 |e2 |e3 | |
| | | | | | | | |
|e1 | |1 |0 |1 |0 |0 |400 |
|e2 | |0 |1 |0 |1 |0 |300 |
|e3 | |0.2 |0.4 |0 |0 |1 |160 |
| | |20 |50 |0 |0 |0 |0 |
5. La solution est assez nulle (z=0) il faut bien le dire ! Il faut
l'améliorer .... on fait entrer une variable dans la base de solutions :
la variable qui va entrer dans la solution est celle qui a le
coût marginal le plus grand ; ici c'est ... . . qui a un coût
marginal à . . . . . Cette colonne s'appelle colonne pivot.
7. Il faut déterminer la variable qui sort de la base :
on calcule les grandeurs suivantes :
400/0 : plus l'infini
300/1 : 300
160/0.4 : 400
on choisit la ligne qui a le rapport le plus faible : la ligne 2
est la ligne pivot.
l'intersection ligne pivot, colonne pivot est le pivot.
8. On refait un tableau où e2 est remplacée par y:
| | |x |y |e1 |e2 |e3 | |
| | | | | | | | |
|e1 | | | | | | | |
|y | | | | | | | |
|e3 | | | | | | | |
| | | | | | | | |
9. les variables de base forment une matrice unité
| | |x |y |e1 |e2 |e3 | |
| | | | | | | | |
|e1 | | | 0 | 1 | |0 | |
|y | | | 1 | 0 | | 0 | |
|e3 | | | 0 | 0 | | 1 | |
| | | | 0 | 0 | | 0 | |
10. quand ou trouve un 0 dans la colonne pivot , on recopie la ligne
correspondante
| | |x |y |e1 |e2 |e3 | |
| | | | | | | | |
|e1 | | 1 |0 |1 |0 |0 |400 |
|y | | |1 |0 | |0 | |
|e3 | | |0 |0 | |1 | |
| | | |0 |0 | |0 | |
11. quand ou trouve un 0 dans la ligne pivot , on recopie la colonne
correspondante
| | |x |y |e1 |e2 |e3 | |
| | | | | | | | |
|e1 | |1 |0 |1 |0 |0 |400 |
|y | |0 |1 |0 | |0 | |
|e3 | |0.2 |0 |0 | |1 | |
| | |20 |0 |0 | |0 | | 12. les termes de la ligne pivot sont divisés par le pivot :
| | |x |y |e1 |e2 |e3 | |
| | | | | | | | |
|e1 | |1 |0 |1 |0 |0 |400 |
|y | |0 |1 |0 |1 |0 |300 |
|e3 | |0.2 |0 |0 | |1 | |
| | |20 |0 |0 | |0 | | 14. il reste 4 cases à calculer par la règle du rectangle : ? ? ? ? ?
? ? ?
? ? le rectangle tourne ?
?
autour du pivot ?
?' ' ? - ?? / ?
| | |x |y |e1 |e2 |e3 | |
| | | | | | | | |
|e1 | |1 |0 |1 |0 |0 |400 |
|y | |0 |1 |0 |1 |0 |300 |
|e3 | |0.2 |0 |0 |-0.4 |1 |40 |
| | |20 |0 |0 |-50 |0 |-15000 |
il reste des coûts marginaux positifs (dernière ligne), on
reprend l'algorithme à la recherche de la colonne pivot :
- colonne pivot : 1
- ligne pivot : 3
on obtient le tableau :
| | |x |y |e1 |e2 |e3 | |
| | | | | | | | |
|e1 | |0 |0 |1 |2 |-5 |200 |
|y | |0 |1 |0 |1 |0 |300 |
|x | |1 |0 |0 |-2 |5 |200 |
| | |0 |0 |0 |-10 |-100 |-19000 |
tous les coûts marginaux sont négatifs, la solution optimale est
trouvée :
il faut produire :
200 x,
300 y,
le bénéfice est de 19000 F.
SECOND SUJET : Ce sujet nécessite un tableau de même dimension que le précédent ; Il
va donc vous permettre d'effectuer un contrôle de votre programmation
avec un jeu d'essai différent de celui du premier sujet (si d'aventure
le hasard était de votre côté pendant l'écriture de votre programme :
c'est une boutade !).
Ecrire un programme qui résout le problème de programmation linéaire
suivant :
Un fabriquant d'ordinateurs possède en stock des cartes électroniques
A, B, C, qui entrent dans la fabrication de 2 sortes d'ordinateurs :
X, Y.
Pour assembler un X, il faut 5A, 2B, 1C.
Pour assembler un Y, il faut 3A, 3B, 3C.
Il reçoit une commande très importante de produits X et Y.
Son stock est actuellement de 30 A, 24 B, 18C.
Sa marge brute sur le produit X est de 4000 francs (çà n'est pas un
PC !).
Sa marge brute sur le produit Y est de 3000 francs (çà n'est toujours
pas un PC !).
Il va livrer x produits X, y produits Y, pour réaliser une marge
maximum.
Calculer x et y ainsi que la marge soit optimale.
Le résultat à trouver est :
il faut fabriquer 3 produits X, 5 produits Y, la marge sera
alors de 27 000 francs.
TROISIEME SUJET : Ce sujet nécessite un tableau de dimensions différentes des
précédents ; Il va donc falloir aménager votre programme pour prendre
en compte ces nouvelles conditions.
Ecrire un programme qui résout le problème de programmation linéaire
suivant : (examen CAPET)
La société GARNIER fabrique et vends 3 produits P1, P2, P3, dans les
conditions suivantes :
Les produits P1, P2 et P3 sont fabriqués dans le même atelier et
nécessitent les heures de main d'oeuvre suivantes :
2 heures par unité P1,
4 heures par unité P2,
3 heures par unité P3.
Le temps d'activité mensuel maximum de cet atelier est de 34 600
heures.
Les produits P1 et P2 sont fabriqués sur un même type de machine et
nécessitent :
0,1 heure de marche pour un produit P1,
0,25 heure de marche pour un produit P2.
Le temps d'activité mensuel maximum de ce type de machine est de 1
100 heures.
Le produit P3 est fabriqué sur un autre type de machine en une heure,
le temps de marche de ce type de machine est de 5000 heures dans le
mois.
Les produits P1, P2 et P3 sont vendus 150, 200, 180 francs.
Une récente étude a permis d'estimer à 2 112 500 francs le chiffre
d'affaire mensuel maximum réalisable sur la totalité des trois
produits.
Une étude des coûts de production internes à l'entreprise a permis de
déterminer la marge sur coûts variables pour les trois produits qui
s'établit à 56 francs pour P1, 80 pour P2, 70 pour P3.
Le résultat à trouver est :
Il faut fabriquer 4750 produits P1, 2500 produits P2, 5000 produits
P3.
La marge sera alors de 816 000 francs. EVOLUTION DU SUJET :
Pour faciliter le travai