Programmation linéaire

Énoncé
Une usine produit deux modèles de machines, l'une que l'on appellera modèle A exige 2 kg de matière première et de 30 heures de fabrication et donne un bénéfice de 7 €. L'autre que l'on appellera B exige 4 kg de matière première et de 15 heures de fabrication et donne un bénéfice de 6 € . On dispose de 200 kg de matière première et de 1200 h de travail. Quelle production doit on avoir pour obtenir un bénéfice maximal ?
Comment résoudre un tel problème ?

La production dépend de deux paramètres

  • Le nombre de machine modèle A
  • Le nombre de machine modèle B
On veut déterminer le nombre de machines de chaque modèle afin d'obtenir un bénéfice maximal.
  1. Traduction des contraintes de ce problème.
Soit x le nombre de machines de modèle A à produire

Soit y le nombre de machines de modèle B à produire

Une première contrainte évidente : x et y sont tout deux positifs et plus exactement ce sont des entiers naturels : x 0 et y 0

Il s'agit dans un premier temps de traduire l'énoncé en un système :

Énoncé Traduction
Le modèle A exige 2 kg de matière première et de 30 heures de fabrication et donne un bénéfice de 7 € x machines de modèle A représente 2x kg de matière première, 30x heures de fabrication et un bénéfice de 7x €
Le modèle B exige 4 kg de matière première et de 15 heures de fabrication et donne un bénéfice de 6 € y machines de modèle A représente 4y kg de matière première, 15y heures de fabrication et un bénéfice de 6y €
On dispose de 200 kg de matière première.

2x + 4y 200

On dispose de 1200 h de travail.

30x + 15y 1200

Bénéfice =

7x + 6y
Les couples (x, y) d'entiers naturels doivent vérifier :
et doivent rendre maximum le nombre b = 7x + 6y
Ce dernier système est obtenu en isolant y dans les deux dernières inéquations.
2. Construction du polygone des contraintes.

Il faut d'abord déterminer les couples (x, y ) vérifiant le système .

La méthode graphique consiste à construire les demi-plans correspondant à chaque inéquation du système. Chaque demi-plan est délimité par une droite.
Les points de coordonnées (x, y) vérifiant l'inégalité x 0 sont les points appartenant au demi-plan des abscisses positives, ce demi-plan est délimité par la droite d'équation x = 0 .
Les points de coordonnées (x, y) vérifiant l'inégalité y 0 sont les points appartenant au demi-plan des ordonnées positives, ce demi-plan est délimité par la droite d'équation y = 0 .
Les points de coordonnées (x, y) vérifiant l'inégalité y -x/2 + 50 sont les points appartenant à l'un des demi-plans délimités par la droite d'équation y = -x/2+50 . Le demi-plan convenable celui qui est "au dessous" ( )de la droite d'équation y = - x/2 + 50.
Les points de coordonnées (x, y) vérifiant l'inégalité y -2x + 80 sont les points appartenant à l'un des demi-plans délimités par la droite d'équation y = -2x + 80 . Le demi-plan convenable celui qui est "au dessous" ( )de la droite d'équation y = - 2x + 80.
On choisit de colorié en gris la partie qui ne convient pas.
La partie qui contient les coordonnées acceptable est l'intérieur du polygone.
3 . Optimisation

On a vu que Bénéfice =7x + 6y

Le bénéfice est fonction de x et y. Si on veut par exemple un bénéfice de 300 € il faut que x et y vérifient 7x + 6y = 300 , c'est à dire encore y = - (7/6)x + 50 , il y a bien sur plusieurs possibilités, en fait plusieurs couple de nombres x et y sont solutions, ce sont les couples de coordonnées (x ; y ) de points appartenant à la droite d'équation y = - (7/6)x + 50
A n'importe quel bénéfice b correspond une droite D d'équation y = - (7/6)x + b/6 . toutes les droites tracées ont même coefficient directeur -(7/6) l'ordonnée à l'origine b/6 est variable par contre. Plus haut la droite coupe l'axe des ordonnées plus grand est b/6. ( plus grand est donc l'ordonnée à l'origine) . Il s'agit donc de déterminer une droite passant par des points du domaine qui coupe l'axe des ordonnées le plus haut possible.
Il faut déterminer les coordonnées du point d'intersection des deux droites, si elles sont entière le bénéfice maximum sera atteint pour x et y trouvés.
Le bénéfice maximum est donc atteint pour x = 20 et y =40 il est de : b = 7x + 6y = 140 + 240 = 380 €
Ce problème peut se résoudre avec la méthode du simplexe
Voir exemple paramétrable