Résolution avec la méthode du simplexe

Controle de gestion

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour,

Je doit apprendre la méthode du simplexe (et les moyennes mobiles) et je bloque.

J'ai mon équation :

2x + 2y = 200

3x + 1y = 100

j'ai omis l'équation total pour simplifier (max mcv).

je réalise mon tableau en ajoutant les variables d'écarts:

Lettre A B e1 e2 Total
A 2 2 1 0 200
B 3 1 0 1 100

Puis je choisit le pivot 3 (le plus grand chiffre, pas compris cette partie): Je divise la ligne par le pivot pour avoir 1 :

Lettre A B e1 e2 Total
A 0 200
B 1 0.33 0 0.33 33.33

Mais arrivé la je bloque complétement. J'ai regardé la correction.

Au dessus du pivot, on met 0;

Pour B = 2 + (-2 * 0.33) = 1.33

Je trouve la ligne en utilisant la méthode mais je bloque par la suite lorsque les chiffres sont dans la colonne au dessous du pivot et cette méthode ne fonctionne pas pour les autres cas plus compliqués.

En vous remerciant.

+0 -0
Staff

Salut,

Je déplace dans la section Sciences, ce sera plus adapté. :)

Pour ton problème, c'est une simple combinaison linéaire que tu dois effectuer : $L_1-\dfrac 23L_2\to L_1$. Par contre, j'ai du mal à comprendre ce que représentent $e_1$ et $e_2$

I don't mind that you think slowly, but I do mind that you are publishing faster. – W. Pauli

+0 -0
Auteur du sujet

Merci pour ta réponse rapide :)

Je ne comprend pas ta formule.

Pourquoi 2/3 ? L1 ? et L2 ?

E1 et E2 sont les variables d'écarts car il part d'une inéquations.

On recherche la production maximale pour faire le plus de profit.

+0 -0

Salut, je ne comprend pas trop ton problème, de ce que je me souviens, le simplexe sert en optimisation linéaire. Il y a la fonction à optimiser et les contraintes.

La "direction" que tu prends pour optimiser est celle qui sera la plus favorable à l'augmentation de ta fonction.

Tes deux équations sont-elles ces contraintes ? (peut être en remplaçant le = par <= ?)

+0 -0
Auteur du sujet

Tu as tout à fait raison.

Mes 2 équations sont bien des contraintes.

Je ne suis pas très math, je simplifie au maximum pour m'y retrouver.

les <= sont les contraintes de départ que j'ai déjà transformé (remplacement <= en =).

les = sont les équations que je dois "résoudre".

J'ai omis la fonction économique (max).

J'espère que j'arrive à être clair.

+0 -0
Staff

Si possible peux-tu mettre la fonction à maximiser, sinon ça va être difficile de t'expliquer les calculs. Je sens que tu n'as pas très bien compris le truc, donc je vais tenter de t'expliquer. Juste, il me faut une formulation correct de ton énoncé au départ.

+0 -0

Et attention, les contraintes seront des "=" dans le cas ou elles sont dites saturées. Toutes les contraintes ne sont pas forcément saturées. C'est même impossible si tu as plus de contraintes.

Un conseil : fait un dessin de ton problème :
Trace tes deux droites
$2x + 2y = 200$ et $3x + 1y = 100$ (donc $y=100-x$ et $y=100-3x$ )

L'aire qui est sous les deux droites représente ton espace admissible, c'est à dire que tous les points de cette aire sont valides par rapport aux contraintes.

Tu as d'ailleurs sûrement deux autres contraintes : $x>=0$ et $y>=0$ non ?

Trace ensuite la pente de ta fonction objectif (prend par exemple deux points qui satisfont $f(x,y)=0$ ).

En améliorant ta solution tu vas faire "translater" la droite de ta fonction objectif perpendiculairement à elle-même, jusqu'au moment où tu arrives dans un "coin" de ton espace admissible. Ce sera ton optimum.

(attention, ici tu peux faire un dessin car tu n'as que deux variables de décisions x et y, mais si tu en as 4 ou plus, tu ne peux plus (on est dans un espace a 3 dimensions…))

Edit : un pdf qui a l'air bien fait avec des illustrations pour expliquer ici.
ps : Tu n'as pas besoin de transformer les max en min tant que tu sais ce que tu fais (et si ton prof ne te demande pas de le faire).

Édité par Fab

+0 -0
Auteur du sujet

Merci pour vos réponse.

Fab : J'ai fait des représentations graphiques (comme sur la page 18 du PDF); tu as raison cela est plus clair pour la compréhension.

J'ai regardé le PDF mais je n'y comprend rien :) (équations page 42 et suivant). Je souhaite obtenir les tableaux page 75 (variable entrée etc.).

Je vais mettre l'énoncé complet de l'exercice que j'ai à résoudre (saroupille).

Une entreprise fabrique deux produits A et B, passant tous deux dans les ateliers découpe et finition.

Atelier Découpe(en heure) Finition (en heure)
Temp fabrication A 2 3
Temp fabrication B 2 1
Capacité max de prod 200 100

Quel est le programme de production qui maximise le Résultat, sachant que les marges unitaires des produits A et B sont respectivement de 20 € et 10 € ?

+0 -0
Staff

Cette réponse a aidé l'auteur du sujet

Je vais essayer de te pondre une réponse complète pour ce problème (donc avec solution). J'espère qu'à partir de ça, tu pourrais comprendre le raisonnement qu'il faut faire de manière générale.

Etape 1 : Modélisation du problème

La première chose qu'il faut faire quand tu es confronté à ce genre de problème, c'est de trouver les variables qui vont permettre de modéliser le problème. Ici, tu souhaite avoir comme modèle un programme linéaire.

Dans ce cas précis, qu'est-ce que tu cherches à connaître ? Ou plus simplement, qu'est-ce qu'il faudrait fournir à l'entreprise afin qu'elle maximise ses bénéfices ?

Ici, l'entreprise veut savoir combien d'unités des produit A et B par heure elle doit fabriquer.

Cela implique donc deux variables que je vais appeler $x_A$ et $x_B$ respectivement pour les produits $A$ et $B$. Jusqu'ici, je suppose que ça doit être clair pour toi.

On obtient donc comme modèle :

Variables : $x_A$ et $x_B$ : unités du produit $i$ à fabriquer par heure

Contraintes :

$$2 x_A + 2 x_B \leq 200$$
(contrainte $D$)
$$3 x_A + 1 x_B \leq 100$$
(contrainte $F$) $x_A,x_B \geq 0$

Fonction objectif :

max $20x_A + 10 x_B$

Résoudre le modèle à l'aide de l'algorithme du Simplexe

L'idée de l'algorithme, c'est de traiter seulement des contraintes d'égalités. Il faut donc dans un premier temps transformer nos inégalités en égalités. On fait ça car comme pour le pivot de Gauss, on sait manipuler facilement des égalités.

Ajouter des variables au modèle

Cette opération de passer d'inégalités vers des égalités demandent de changer implicitement le modèle. On va rajouter des nouvelles variables que l'on appelle des variable d'excédant. Elles représente en quelque sorte la marge de manoeuvre qu'il y a pour saturé une contrainte.

A titre d'exemple, si on prend la contrainte $D$, et on pose $x_A=x_B=40$. Alors la contrainte est satisfaite car $2\times 40 + 2\times 40 = 160$ et $160\leq200$. Mais la contrainte n'est pas saturée car $160 \neq 200$.

Si maintenant, on transforme notre contrainte $D$ en rajoutant une variable d'excédant $e_A$ ainsi :

$$2 x_A + 2 x_b + e_A = 200$$

En gardant les mêmes valeurs pour $x_A$ et pour $x_B$ on va avoir $e_A=40$. $e_A$ n'intervient pas dans le modèle intiale, certes, mais ici, elle donne quand même une info supplémentaire : elle nous dit qu'il manque 40 unités de découpent par heure pour atteindre la production maximale.

On va voir que cette information sera intéressante une fois qu'on aura la solution à notre problème.

Il faut donc ajouter une variable d'excédant pour chaque contrainte qui n'est pas une égalité.

On obtient donc un nouveau modèle avec deux variables supplémentaires $e_D$ et $e_F$ qui sont chacune les variables d'excédant pour les contraintes $D$ et $F$ respectivement.

La fonction objectif n'a pas changé bien sûr puisque ces variables ne vont pas influer sur les bénéfices de l'entreprises. Ce sont des variables artificielles qui servent seulement à la résolution dudit problème.

Résolution du problème par la phase 2 du simplexe

Notre modèle ici est très simple et contient seulement des contraintes (sauf pour les variables) de la forme $... \leq ... $. Cela implique que la solution $x_A=x_B=0$ est une solution admissible, c'est à dire qu'elle ne viole pas les contraintes. Bien sûr, ce n'est pas la solution recherchée.

Si on rajoute des contraintes de la forme $ ... \geq ...$ il se peut que $x_A=x_B=0$ ne soit pas une solution admissible (par exemple $x_A \geq 20$). Il faut alors utiliser la phase $1$ du simplexe.

Mais comme dans notre cas, tout va bien, on passe directement à la phase $2$.

Cependant, comme nos contraintes sont des égalités, cela veut dire que $e_D=200$ et $e_F=100$ (tu peux vérifier que les contraintes sont satisfaites).

On adopte lorsqu'on apprend le simplexe, une représentation tabulaire des équations :

Lettre $x_A$ $x_B$ $e_D$ $e_F$ Total
D 2 2 1 0 200
F 3 1 0 1 100
F.O. 20 10 0 0 0

Tu vois que contrairement à ce que tu as donné dans ton premier post, j'ai rajouté une ligne. Il se trouve en fait que cette ligne est la plus importante dans l'algorithme du simplexe et c'est elle qui va diriger la résolution.

Comment interpréter cette dernière ligne ?

Le $20$ dans la colonne $x_A$ indique que si j'augmente la valeur de $x_A$ (qui pour le moment est $0$) je ferai augmenter de $20$ les bénéfices de l'entreprise (ma fonction objectif). Ce $20$ est appelé coût marginal. La dernière case en bas à droite indique l'opposée de la valeur courante de ma fonction objectif. Ici évidemment la solution vaut $0$ (on ne fabrique rien).

Pourquoi l'opposée ? Je n'ai pas beaucoup d'intuition si ce n'est qu'une histoire de maths (la valeur absolue est la même de toute façon).

De plus on distingue deux types de variables : les variables qui ont un coût marginal de $0$ et les autres. On appelle les variables hors base les variables qui ont un coût marginal différent de $0$ et donc à l'opposé, les variables qui ont un coût marginal de $0$ sont les variables en base.

Dans notre cas, $x_A$ et $x_B$ sont hors base tandis que $e_D$ et $e_F$ sont dans la base.

Tout le but du simplexe va donc être de faire entrer $x_A$ et $x_B$ dans la base (et pour des problèmes plus compliqués de faire tout un jeu entre faire entrer et faire sortir les variables de la base).

Choisir la nouvelle variable (aussi appelé le pivot)

Le pivot est une variable hors base que l'on va faire entrer dans la base. Il n'y a pas de méthode plus efficace pour choisir une nouvelle variable. On utilise donc ce qu'on appelle une heuristique. C'est à dire que l'on fait un choix qui, on l'espère est en général plus efficace. Ici, le choix que l'on fait c'est de prendre la variable qui aura un coût marginal positif le plus élevé. Dans notre cas c'est $x_A$. J'insiste sur positif car cela veut dire que ça va faire augmenter ta fonction objectif. Si le coût marginal est négatif cela veut dire que tu fais descendre ta fonction objectif (ici tu es en maximisation donc tu ne veux surtout pas faire ça).

Donc on sait qu'on va prendre $x_A$ et qu'on va faire augmenter sa valeur. Maintenant, la question qu'on se pose c'est de combien au maximum on peut augmenter la valeur de $x_A$ ?

Calculer la valeur maximale de cette variable

L'algorithme du simplexe va chercher à maximiser la valeur de cette variable. Dans notre cas $x_A$. La maximiser, ça revient à dire que l'on va la faire monter, jusqu'à saturer une contrainte (car les variables $e_i=0$).

Cette valeur se calcule assez simplement. Pour chaque contrainte : on prend le nombre qu'il y a dans la colonne Total et on la divise par le coefficient du pivot (ici $x_A$).

Puis on prend le minimum.

Dans notre cas :

$$min(\frac{200}{2}, \frac{100}{3})) = \frac{100}{3}$$

En effet, si tu reprends les contraintes initiales, tu vois bien que si $x_A$ dépasse $33,333...$ alors la contrainte $F$ va être violée.

Choisir la variable qui va sortir de la base

La taille de la base est constante (c'est tout simplement le nombre de contraintes). Si on fait entrer une variable en base, il va bien falloir en faire sortir une autre. Ici on a le choix entre $e_D$ et $e_F$. On a vu qu'à l'étape précédente, il y avait une contrainte qui allait être saturée et qui déterminait la valeur maximale du pivot. On va donc prendre la variable d'écart associée à cette variable, qui vaudra donc à nouveau $0$ (comme la contrainte est saturée) et sera bien une variable hors base par définition.

Il reste donc seulement à faire les calculs. Si tu as compris les trois étapes précédents, le reste sera juste du calcul.

Actualiser le tableau

Pour le contrainte $F$ on a :

$$3x_A + x_B +e_F=100$$

Ce qui se réécrit

$$e_F=100- 3x_A - x_B$$

Ici, j'ai exprimé les variables de la base à gauche de l'égalité, et les variables hors base à droite. Si maintenant, $x_A$ rentre en base, il va falloir faire un petit changement : passer $x_A$ à gauche et $e_F$ à droite ce qui donne :

$$x_A = \frac{100}{3} - \frac{e_F}{3} - \frac{x_B}{3}$$

Ce qui dans le tableau, va correspondre à diviser la ligne par le coefficient de $x_A$ dans cette ligne.

Pour les autres lignes tu peux appliquer la même méthode : exprimer la ligne en fonction des variables en base et des variables hors bases et manipuler l'équation pour avoir la forme voulue.

Dans le tableau, cela se traduira à faire une opération de la forme du pivot de Gauss.

Par exemple pour la contrainte $D$, la nouvelle ligne sera :

$$3D-2F$$

On obtient donc le nouveau tableau suivant :

Lettre $x_A$ $x_B$ $e_D$ $e_F$ Total
D 0 $\frac{16}{3} $\frac{7}{3}$ 0 400
F 1 $\frac{1}{3}$ 0 $\frac{1}{3}$ $\frac{100}{3}$
F.O. 0 $\frac{10}{3}$ 0 $\frac{-20}{3}$ $\frac{-2000}{3}$

Terminaison de l'algorithme

L'algorithme s'arrête une fois que tu ne peux plus faire entrer de variables dans la base, c'est à dire quand tous les coûts marginaux sont négatifs ($0$ ou moins). Ici, tu vois que ce n'est pas le cas, tu peux encore faire entrer $x_B$ dans la base.

Normalement, tu as tout en main pour continuer et trouver la solution optimale.

Édité par Saroupille

+4 -0
Auteur du sujet

Merci pour ton post très complet et intéressant :) .

Je suis comptable et tes explications sont un peu compliqué par moment (malgré le soin apporté à la clarification de la méthode). Je souhaiterais des explications sur certains points.

Quesque le pivot de Gauss ?

Comment calcule tu les chiffres dans les cases avoisinantes ?

Quand le simplexe est terminé ?

Comment est lu le tableau final ?

Pourrait tu expliquer la fonction min ?

Pourquoi divise tu par 3 les autres ligne du tableau du simplexe ?

Dans le dernier tableau, pourquoi 16/3 ?

Le prof souhaite une résolution par tableau.

Je reproduit la correction :

N°1 :

Case A B e1 e2 Total
e1 2 2 1 0 200
e2 3 1 0 1 100
Capacité max de prod 20 10 0 0 0

N°2 :

Pivot = 3

Ce que je pense avoir compris:

  • Je prend le pivot et je divise la ligne par le pivot

  • Je met 0 dans la colonne du pivot

Case A B e1 e2 Total
e1 0 1.33 1 -0.66 133.33
B 1 0.33 0 0.33 33.33
Capacité max de prod 0 3.33 0 -6.67 -666.67

N°3 :

Pivot = 0.33

Case A B e1 e2 Total
e1 -4 0 -1 -2 0
B 3 1 0 1 100
Capacité max de prod -10 0 0 -10 -1000

Solution :

A = 0

B = 100

Gain = 1000 €

Je vais relire ton post (qui doit déjà avoir apporté les solutions) pour mieux le comprendre.

Je n'ai pas compris le dernier tableau pourrais tu le réexpliquer.

Édité par banco29510

+0 -0

Salut, ce que je vais dire ne va pas t'aider pour le simplexe mais peux te simplifier la vie dans certains cas, vu que tu n'as que 2 variables ici tu peux te permettre d'utiliser une méthode graphique c'est : - simple - rapide - efficace - visuel

Pour ça tu traces 2 axes, l'un correspond à A (=x) l'autre à B (=y). Tu traces les droites

2x + 2y = 200

3x + 1y = 100

Tu devrais avoir une figure avec des coins.

Ensuite tu as juste à prendre ce que tu maximise (10x + 20y si je ne me trompe pas) tu traces la droite qui correspond et tu fait bouger une règle parallèlement à cette droite que tu viens de tracer, le dernier coin que tu croiseras sera celui qui maximise ta fonction sous ces contraintes.

j’espère que mon explication est plus ou moins claire.

P.S : j'ai du mal avec le Markdown ici

+0 -0
Staff

Je t'invite à rechercher par toi même sur ton moteur de recherche favori pour avoir d'autres explications et/ou intuitions. Par exemple il y a ce lien (un des premiers résultats sur Google : Méthode du simplexe) qui explique l'algorithme sur un exemple. Cependant, je ne trouve pas les calculs très détaillés.

Merci pour ton post très complet et intéressant :) .

Je suis comptable et tes explications sont un peu compliqué par moment (malgré le soin apporté à la clarification de la méthode). Je souhaiterais des explications sur certains points.

Quesque le pivot de Gauss ?

Regarde sur internet, mais c'est un algorithme qui permet de résoudre des $n$ équations avec $n$ inconnues.

Comment calcule tu les chiffres dans les cases avoisinantes ?

Pour la ligne où il y a le pivot, tu fais seulement une division par le coefficient du pivot. D'ailleurs le pivot est $x_A$. $3$ est seulement le coefficient associé.

Pour les autres lignes j'ai donné le calcul :

$$3D - 2F$$

Ce que j'appelle $n \times A$ (ici $n=3$), c'est le fait de prendre tous les coefficients de $A$ et de les multiplier par $3$.

Faire l'opération $C-D$ c'est pour chaque colonne du tableau faire $x_C$ - $x_D$.

Quand le simplexe est terminé ?

Je l'ai expliqué à la toute fin de mon poste. Sur la dernière ligne tu dois avoir que des coûts marginaux négatifs.

Comment est lu le tableau final ?

Il faudrait une bonne demi-heure à un prof pour expliquer les résultats du tableau final. Va voir sur internet d'autres explications.

Pourrait tu expliquer la fonction min ?

En une seule phrase :

$$min f(\vec{x}) = max f(-\vec{x})$$

Autrement dit, tu prends l'opposée de toutes les variables. Sinon, il doit y avoir une autre méthode plus tabulaire. Encore une fois, je t'invite à regarder des documents comme je t'ai cité plus haut. Car là, j'ai effectivement un trou de mémoire.

Pourquoi divise tu par 3 les autres ligne du tableau du simplexe ?

Les fractions rendent les choses exactes et explicitent. Je t'invite à t'en servir. Pour le reste j'y ai répondu juste au dessus je pense.

Dans le dernier tableau, pourquoi 16/3 ?

Tu fais référence à mon erreur TeX ? Ca pourrait être une erreur de calcul, mais il ne me semble pas. Tu es sûr du résultat de ton corrigé ?

Le prof souhaite une résolution par tableau.

Je reproduit la correction :

N°1 :

Case A B e1 e2 Total
e1 2 2 1 0 200
e2 3 1 0 1 100
Capacité max de prod 20 10 0 0 0

N°2 :

Pivot = 3

Ce que je pense avoir compris:

  • Je prend le pivot et je divise la ligne par le pivot

  • Je met 0 dans la colonne du pivot

Case A B e1 e2 Total
e1 0 1.33 1 -0.66 133.33
B 1 0.33 0 0.33 33.33
Capacité max de prod 0 3.33 0 -6.67 -666.67

N°3 :

Pivot = 0.33

Case A B e1 e2 Total
e1 -4 0 -1 -2 0
B 3 1 0 1 100
Capacité max de prod -10 0 0 -10 -1000

Solution :

A = 0

B = 100

Gain = 1000 €

Je vais relire ton post (qui doit déjà avoir apporté les solutions) pour mieux le comprendre.

Je n'ai pas compris le dernier tableau pourrais tu le réexpliquer.

banco29510

Ce qui est étrange, c'est que tu n'as pas de question particulière, mais juste tu n'as pas compris l'algorithme. Pourtant je suppose que tu dois avoir un support de cours non ? Ce n'est pas expliqué dessus ?

+0 -0
Auteur du sujet

J'ai un niveau bac pro en math; depuis je n'en ait plus fait (préparation Bac+3). J'aurais bien fait l'impasse mais je suis sur de tomber dessus dans 1 mois :)

Le cours que j'ai reçu est plutôt obscure (formule mathématique avec des symboles, pas à pas bloquant) et à cause de problème organisationnel de l'école je ne peut pas le voir de visu (cours par correspondance - 500km pour aller le voir). Je peut le contacter par le forum ou il n'est pas présent et par mail mais manque de réactivité). J'ai compris le début du cours avec un livre trouvé dans le commerce ( et certains chapitres obscures avec ce même livre "l'essentiel du controle de gestion " éd les carrées).

Le point qui me bloque est l'actualisation du tableau. Je n'ai pas l’équation qui me permet de retrouver les chiffres des autres lignes du tableau.

Je pense que c'est le passage sur 3D - 2F (je ne comprend pas).

N * A ( n est le pivot je pense)

C - D ( xc et xd sont pour moi les variables e mais je n'en suis pas sur)

Il donne dans sa correction : x + (-x*x) soit :

ancienne case + ( - case du dessous * le pivot) = nouvelle case

Je retrouve la même chose sur le lien que tu m'a donné mais cela ne fonctionne pas lorsque j'essaie d’appliquer lorsque la case est situé en dessous du pivot.

J'avais laisser tomber le site (phpsimplex) car le tableau est compliqué.

J'avais trouvé une vidéo youtube ou il faisait un tableau :

a b
c d

Et en déduisait une équation qui donnait le résultat.

J'ai vérifié la correction, ce sont les chiffres qu'il donne.

+0 -0
Staff

Cette réponse a aidé l'auteur du sujet

J'ai un niveau bac pro en math; depuis je n'en ait plus fait (préparation Bac+3). J'aurais bien fait l'impasse mais je suis sur de tomber dessus dans 1 mois :)

Le cours que j'ai reçu est plutôt obscure (formule mathématique avec des symboles, pas à pas bloquant) et à cause de problème organisationnel de l'école je ne peut pas le voir de visu (cours par correspondance - 500km pour aller le voir). Je peut le contacter par le forum ou il n'est pas présent et par mail mais manque de réactivité). J'ai compris le début du cours avec un livre trouvé dans le commerce ( et certains chapitres obscures avec ce même livre "l'essentiel du controle de gestion " éd les carrées).

Le mieux à mon avis c'est de prendre un livre. Quand j'avais du apprendre le simplexe, j'avais pris ce livre : Linear Programming . Je l'ai trouvé génial car il est complet (il y a les preuves). Evidemment, seul les premiers chapitres sont intéressants pour toi.

Les preuves tu t'en fiches, mais il m'avait marqué car il donnait pas mal d'intuitions sur le fonctionnement de l'algorithme.

En cherchant un livre sur le pivot de Gauss, je suis tombé sur celui là : Linear Algebra. C'est un PDF d'algèbre linéaire, mais pour toi, seul les trois premiers chapitres sont intéressants. Surtout que la troisième chapitre couvre la méthode du simplexe.

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte