Le simplexe

  La méthode du simplexe permet la recherche d'un optimum économique. Il s'agit par exemple, dans le cas d'un programme de production, de déterminer quelles seront les quantités à fabriquer pour optimiser le résultat, et ce en tenant compte des contraintes de production. Supposons une entreprise fabriquant deux produits A et B, passant tous deux dans les ateliers découpe (D) et finition (F) :

Atelier	Découpe	Finition	14,25 euros
Temps de fabrication de A	2 heures	3 heures
Temps de fabrication de B	2 heures	1 heure
Capacité maximale de production	200 heures	100 heures
Sachant que les marges unitaires des produits A et B sont respectivement de 20 € et 10 € , quelles seront les quantités à produire pour maximiser le résultat ? Le processus de résolution se fera en trois phases : la formalisation du problème, sa résolution et la détermination de la solution optimale. A lire : " initiation à la programmation linéaire et à l'algorithme du simplexe " .

Formalisation du problème

  Dans l'exemple présenté, nous avons une marge à maximiser, avec 20 € par produits A et 10 € par produits B, en tenant compte des contraintes de fabrication. On présente donc le programme de production sous formes d'équations en introduisant des variables d'écart (d et f), qui correspondent aux temps (en heures) non consommés dans les ateliers (D et F).

Forme canonique : Maximiser 20A + 10B avec A £ 0 et B ³ 0 2A + 2B £ 200 3A + B £ 150

Forme standard : Maximiser 20A + 10B + 0d + 0f avec A, B, d et f ³ 0 2A + 2B + d £ 200 3A + B + f £ 150

Remarque : il y a autant de variables d'écart (ici d et f) que d'inéquations.

Résolution du problème

  1. Dans la situation de départ, on dispose de 200 heures dans D et 150 heures dans F et on considère la production comme nulle (0 produits A et B). La marge totale est donc nulle... cette situation est résumée dans ce premier tableau :

Comment déterminer le pivot ? (représenté en rouge) :

• Colonne : les produits A ont une marge supérieure (20 €) . On va donc les privilégier.
• Ligne : dans l'atelier d on peut fabriquer 100 produits A mais on est limité à 50 dans l'atelier f.

  2. Le pivot du problème est à l'intersection : 3 . On va donc maintenant considérer A comme une ressource : on dit que A "entre dans la base" et que f "sort de la base". Remarquez que la ligne " f " disparait et laisse place à la ligne " A " :

Comment calculer les nouveaux éléments du tableau (passez votre curseur sur les cases pour un détail des calculs) ?

• première ligne : élément de la ligne 1 diminué de l'élément correspondant sur la ligne de pivot multiplié par 2/3.
• seconde ligne (ligne du pivot) : élément ligne 2 divisé par le pivot (3).
• troisième ligne : élément ligne 3 diminué de l'élément correspondant (même colonne) de la ligne de pivot multiplié par 20/3 (20 .

• Toujours pas compris ?! Exemple en image ...

3. On n'atteint la solution optimale que lorsque tous les éléments de la marge sont négatifs ou nuls. Il faut donc continuer (car il reste 10/3 dans la colonne B) ... ici, on atteint déjà l'otimum au troisième tableau, mais ce n'est pas une généralité.

Solution du problème

Résultat : le processus est terminé car tous les gains unitaires qui résulteraient d'une nouvelle substitution sont négatifs. Le programme optimum est 25 A et 75 B pour un résultat de 1.250 euros (25 × 20 € + 75 × 10 €).

Remarques :
- ici, d et f sont sortis de la base. Lorsqu'une variable d'écart reste dans la base et que le processus est terminé, celà signifie qu'elle n'est pas saturée et qu'il y a donc un "reste" qui ne sera pas consommé,
- dans le cas de la maximisation, les coefficients de la fonction sont tous négatifs, les variables hors base sont négatives et les variables en base sont nulles
- dans le cas de la minimisation, les coefficients de la fonction sont tous positifs, les variables hors base sont positives et les variables en base sont nulles

Transformation d'un PRIMAL en DUAL

PRIMAL
A 18 x + 18 y = 9.000
B 6x+24y = 6.000
C 20 x + 6 y = 7.200
x et y = 0
MIN : 1.200 x + 1.000 y

DUAL
18 a + 6 b + 20 c = 1.200
18 a + 24 b + 6 c = 1.000
MAX : 9.000 a + 6.000 b + 7.200 c

vous devez être inscrit pour poster sur le forum, voir ou déposer des commentaires sur cette page. N'attentez pas, l'inscription sur le site est gratuite !