La programmation linéaire - publié le 19/04/2012

Résumé du document

1.1 Enoncé du problème

Une menuiserie industrielle fabrique des tables et des armoires. Pour ce faire, elle utilise de la main d'oeuvre dans trois ateliers : atelier1 (découpe), atelier2 (assemblage) et atelier3 (finition).
La fabrication d'une table nécessite 1 heure de main d'oeuvre dans l'atelier de découpe, 2 heures de main d'oeuvre dans l'atelier de d'assemblage et 3 heures de main d'oeuvre dans l'atelier de finition.
La fabrication d'une armoire nécessite 3 heures de main d'oeuvre dans l'atelier de découpe, 3 heures de main d'oeuvre dans l'atelier de d'assemblage et 2 heures de main d'oeuvre dans l'atelier de finition.
On ne dispose quotidiennement que de 180 heures de main d'oeuvre dans l'atelier de découpe, 210 heures dans l'atelier d'assemblage et 215 heures de main d'oeuvre dans l'atelier de finition.
On sait d'autre part que les tables laissent une marge unitaire de 50? et que les armoires laissent une marge unitaire de 60?.
Il s'agit de trouver le programme quotidien de fabrication qui laisse une marge totale maximale.

[...] 1.3 2ème étape : écriture algébrique des contraintes.
On va désigner par x le nombre de tables fabriquées quotidiennement et par y le nombre d'armoires fabriquées quotidiennement.
Il est clair que x et y sont des nombres positifs ou nuls (pas forcément entiers : la journée peut se terminer sans qu'on ait entièremment achevé une table ou une chaise ; il peut y avoir des « encours de fabrication »).
La fabrication d'une table consomme 1 heure de main d'oeuvre dans l'atelier1 et celle d'une armoire en consomme 3 dans le même atelier.

[...] La méthode qui consiste à classer les pentes des droites frontières pour trouver le point de sortie pourrait laisser penser que le graphique est inutile. Il n'en est rien, car il faut le construire pour s'assurer que toutes les droites sont bien frontières du domaine. Si une ou plusieurs d'entre elles ne servent pas de frontière (en général, ceci ne peut être découvert qu'en ayant construit le graphique), ce qui veut dire que les contraintes auxquelles elles correspondent sont automatiquement satisfaites dès que les autres le sont, il faut alors les supprimer avant de classer les pentes. (...)

Extraits

[...] Les trois droites ont été tracées dans le graphique ci-dessous. Il est facile de constater que pour chaque droite l'origine est dans le bon demi-plan vis avis des inégalités (si on ne fabrique rien, on ne dépassera pas les volumes de main d'œuvre attribué à chaque atelier). L'ensemble des solutions admissibles est donc situé à l'intérieur du pentagone OABCD entouré en bleu Un des multiples usages du domaine obtenu. Le segment OA correspond à des programmes de fabrications satisfaisant à toutes les contraintes sans fabriquer de tables et de même, le segment OD correspond à des programmes de fabrications satisfaisant à toutes les contraintes sans fabriquer d'armoires. [...]

[...] Les calculs montrent que cette marge sera de 8600€ et qu'il restera 200/3 d'heures disponibles dans l'atelier2, 325/3 d'heures disponibles dans l'atelier1, l'atelier3 étant saturé. On peut ainsi remarquer que la marge unitaire des tables a tellement augmenté (relativement à celle des armoires) que, compte tenu des contraintes, on décide de ne plus fabriquer d'armoires et donc de ne fabriquer que des tables. Sur le plan pratique, il convient de retenir une solution entière. En testant les points à coordonnées entières situés dans le domaine et près du point on découvre que c'est le point qui permet d'obtenir une marge totale maximale de 8580€. [...]

[...] Enfin le segment CD correspond aux programmes de fabrication permettant d'assurer le plein emploi dans l'atelier3 tout en satisfaisant aux autres contraintes. Les trois droites n'étant pas concourantes, on voit ainsi qu'il n'est pas possible d'assurer le plein emploi dans les trois ateliers simultanément. On peut le faire simultanément dans les ateliers 1 et 2 en se plaçant au point B=D1(D ou dans les ateliers 2 et 3 en se plaçant au point C=D2(D mais pas dans les ateliers 1 et 3 puisque le point E=D1(D3 est en dehors du domaine (ce qui fait que les autres contraintes ne pourraient être satisfaites). [...]

[...] Il est clair que x et y sont des nombres positifs ou nuls (pas forcément entiers : la journée peut se terminer sans qu'on ait entièremment achevé une table ou une chaise ; il peut y avoir des encours de fabrication La fabrication d'une table consomme 1 heure de main d'œuvre dans l'atelier1 et celle d'une armoire en consomme 3 dans le même atelier. La fabrication de x tables et y armoires va donc consommer x+3y heures de main d'œuvre dans l'atelier1 qui n'en dispose que de 180. On obtient donc l'inégalité : x+3y(180. De même, concernant l'atelier2, on obtient l'inégalité : 2x+3y(210 ; Et aussi, concernant l'atelier3, l'inégalité : 3x+2y(215. [...]

[...] La marge totale apparaît dans l'ordonnée à l'origine de cette droite : . Améliorer la marge totale, revient à augmenter l'ordonnée à l'origine. On va donc déplacer la droite d'essai parallèlement à elle-même vers le haut jusqu'à ce qu'elle ne rencontre plus le domaine. Le point du domaine par lequel cette droite va sortir du domaine nous fournira le programme de fabrication respectant les contraintes et laissant une marge totale maximale. Dans le graphique3 ci-dessous, trois droites de marge totale ont été tracées en pointillés. [...]