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.
