Application à la Programmation Linéaire

 

Introduction Beaucoup de problèmes de la vie réelle consiste à  maximiser ou  minimiser  une certaine quantité sujette à quelques contraintes. La programmation linéaire est une façon d’aborder ce genre de problèmes. Nous verrons des exemples de maximiser ou de minimiser une expression  linéaire  sujette à des contraintes linéaires. Cette technique s’applique à une grande variété de problèmes dans l'industrie et la science.

 

1) Cas des deux variables: une approche géométrique

Problème général Soit z=ax+by une fonction linéaire de deux variables x et y, trouver les valeurs de x et y qui maximisent ou minimisent la fonction z sujette aux contraintes linéaires :

 

 

 

et

 

(Dans les conditions ci-dessus, n'importe quel symbole peut être utilisé). La fonction z dans le problème ci-dessus s’appelle la fonction objective. Un vecteur (x, y) qui satisfait toutes les conditions est appelé une solution admissible. L’ensemble de toutes les solutions admissibles est appelé la région admissible.

 

Noter que chaque contrainte de la forme ax+by=c représente une droite dans le plan (x-y) et chaque contrainte de la forme  représente un demi-plan qui comprend la droite-frontière .

 

La région admissible est alors une intersection d’un nombre fini de droites et des demi-plans. Si la région admissible peut être enfermée dans un cercle suffisamment grand, elle s'appelle limitée; autrement elle s'appelle illimitée.

 

 

 

 

 

 

 

 

Si une région admissible est vide  (ne contient aucun point), alors les contraintes ne sont pas compatibles et le problème n’admet pas de solutions. Les points de la frontière d’une  région admissible  qui sont des intersections des droites frontières de cette région s’appellent les points extrêmes de la région admissible.  Le résultat principal qui traite un problème de programmation linéaire est donné par le théorème suivant :

 

Si la région admissible d’un problème de programmation linéaire est non vide et limitée, alors la fonction objective atteint un maximum et un minimum et ces deux valeurs sont atteintes sur des points extrêmes de la région admissible. Si la région admissible est illimitée, alors il se peut que  la fonction objective n’atteint pas une valeur maximum ou minimum; cependant, si elle atteint une valeur maximum ou minimum, cette valeur est atteinte à un point extrême.

 

Exemple 1 Un fabricant de sucrerie possède 130 livres de chocolat-cerises et 170 livres de chocolat-menthes en stock. Il décide de les vendre sous forme de deux mélanges différents. Un mélange contiendra moitié chocolat-cerises et moitié chocolat- menthes en poids se vendra pour $2,00 par livre. L'autre mélange contiendra un tiers chocolat-cerises et deux-tiers chocolat-menthes en poids et se vendra pour $1,25 par livre. Combien de livres de chaque mélange le fabricant de sucrerie devrait-il préparer afin de maximiser son revenu?

 

Solution Appelons A le mélange de moitié cerises et  moitié  menthes, et B le mélange d'un tiers cerises et de deux-tiers menthes. Soit x le nombre de livres de A à préparer et  y le nombre de livres de B à préparer. La fonction  revenu peut alors être écrite comme :

 

 

 

Puisque chaque livre de A contient une demi-livre de cerises et chaque livre de B contient un tiers livre de cerises, le nombre total de livres de cerises utilisées dans les deux mélanges est

 

 

 

De même, le nombre total de livres de menthe utilisées dans les deux mélanges est :

 

 

 

Comme le fabricant peut utiliser au plus 130 livres de chocolat-cerises et 170 livres de chocolat-menthes, on a les contraintes suivantes :

 

 

 

De plus, on a  Alors, le problème ci-dessus est réduit au problème suivant: trouver les valeurs de x et y qui maximisent   sujet aux contraintes :

 

 

 

 

 

Pour résoudre ce problème, on utilise les techniques du programmation linéaire vus ci-haut. On commence par tracer la région admissible et trouver nos points extrêmes :

 

 

 

La région admissible est limitée sans ce cas, ce qui implique qu’une solution optimale du problème est atteinte sur un des points extrêmes. Le tableau suivant montre les valeurs de la fonction objective en chacun de ces points :

 

 

 Point extrême

Valeur de  z=2x+1.25y

(0, 0)

0

(0, 255)

318.75

(180, 120)

510.00

(260, 0)

520.00

 

Le tableau montre que la plus grande valeur de z est 520,00 et la solution optimale correspondante est (260, 0). Ainsi le fabricant de sucrerie obtient un revenu maximal de $520 quand il produit 260 livres du mélange A et rien du mélange B.

 

Exemple 2 Le département d'environnement du comté d'Osgood opère deux centres de recyclage : Centre 1 et Centre 2. Le coût d’opérer le premier centre est $40 par jour de huit heures. En moyen, 140 livres de verre et 60 livres d'aluminium sont déposées au Centre 1 quotidiennement. Centre 2 coûte $50 par chaque jour de huit heures et reçoit 100 livres de verre et 180 livres d'aluminium par jour. Pour encourager une compagnie de recyclage à ouvrir une usine en ville, le département a promis de fournir au moins 1540 livres de verre et 1440 livres d'aluminium par semaine. Combien de jours par semaine le département devrait-il ouvrir chaque centre pour réduire au minimum son coût et pour satisfaire toujours aux besoins de la compagnie de recyclage?

 

Solution. Soient x, y les nombres de jours ouvrables par semaine du Centre 1 et Centre 2 respectivement.  Avec la terminologie de la  programmation linéaire, le problème devient : 

 

Minimiser la fonction                         

 (coût d’opérer les deux centres)

 

sujette aux contraintes :

 

 

 

 

 

 

 

Le diagramme suivant montre la région admissible et les points extrêmes du problème :

 

 

 

 

 

 

La région admissible est illimitée dans ce cas avec trois points extrêmes finis. Deux de ces points sont faciles à voir du graphe : (0, 15.4), (24, 0). Le troisième  peut être calculé algébriquement comme point d’intersection de deux droites: (6.94, 5.69).  Comme la région est illimitée, on peut aussi supposer qu’il y des point extrêmes ``infinis`` et comme le problème est de minimiser et non pas maximiser, on peut voir que ces points ne sont pas ``optimaux``.On évalue alors la fonction objective aux points extrêmes finis :

 

Point extrême

Valeur de z=40x+50y

(0, 15.4)

770

(24, 0)

960

(6.94, 5.69)

562.10

 

 

Le coût minimal est alors $562,10 et il est atteint lorsque Centre 1 est ouvert pour à peu près 7 jours par semaine (huit heures par jour) et Centre 2 est ouvert pour à peu près 6 jours par semaine (huit heures par jour).

 

2) Programmation linéaire avec plus de 2 variables

Il est possible de résoudre un problème de programmation linéaire de trois variables graphiquement, sauf que les points extrêmes seront plus difficiles à voir. Il est par contre impossible de résoudre un tel problème avec quatre variables ou plus en utilisant une approche graphique. L’algorithme du simplex développé  par Danzig nous donne une méthode algébrique pour trouver les points extrêmes de la région admissible et par suite  résoudre un problème de programmation linéaire en évaluant la fonction objective en ces points.

 

Découvert par George Dantzig dans les années 40, l'algorithme du simplex est une méthode simple de résoudre des problèmes de programmation linéaires. L'idée est d'identifier certains points admissibles de base et montrer que la valeur maximum (si elle existe) de la fonction objective est atteinte à un de ces points. Nous expliquerons l'algorithme seulement pour un problème de programmation linéaire standard qui a la forme suivante:

 

Maximiser la fonction objective:

 

 

 

des variables x1, x2,…, xn sujette aux contraintes:

 

 

 

 

Sous la forme ci-dessus, le fait que la fonction objective est linéaire est crucial, mais la condition que les variables sont non-négatives et le fait que nous maximisions f  au lieu de la minimiser  ne sont pas des restrictions graves. La condition que les constantes bj sont non -négatives est sérieuse bien qu'elle soit satisfaite dans beaucoup d'applications pratiques. Pour le cas non standard, consultez SVP certains des liens ci-dessous.

 

Décrivons cet algorithme avec un exemple:

 

 

Maximiser:

 

sujette aux contraintes:

 

 

 

 

Solution La première étape est de convertir les inégalités dans les contraintes ci-dessus en égalités. Ceci peut être fait en ajoutant de nouvelles variables: x4, x5 et x6  appelées les variables d’écart, une dans chaque contrainte. Nous obtenons de cette façon un nouveau problème:

 

 

Maximiser:

 

 

 

sujette aux contraintes:

 

 

 

 

Si  (x1 , x2 ,…, x6) est une solution du nouveau problème, alors (x1, x2, x3) est une solution du problème original. En effet, les contraintes sont clairement satisfaites. De plus, si  (y1, y2, y3) était un autre point extrême pour le problème original donnant une plus grande valeur de f, alors en posant

 

 

 

 

on aurait un point extrême   pour le nouveau problème qui donnerait une valeur plus grande pour f, ce qui est une contradiction. Il suffit alors de résoudre le nouveau problème. Pour ceci, écrivez la relation  comme une quatrième équation pour obtenir un nouveau système linéaire dans lequel f est traité en tant qu'autre variable:

 

 

 

 

 

 

La matrice augmentée de ce système est :

 

 

 

 

 

 

 

 

Cette matrice s'appelle le tableau simplex initial pour le problème. Nous emploierons des opérations élémentaires sur les lignes de la matrice afin de créer  une suite des tels tableaux tout en gardant f à la dernière ligne de la matrice. Ceci est analogue à la modification de la matrice augmentée dans l'élimination Gaussienne, sauf qu'ici nous permettons seulement les solutions admissibles.

 

Notez que la manière avec laquelle les variables d’écart étaient introduites montre que les colonnes correspondant à ces variables se composent des 0 et d'un seul 1 et que les 1 de ces colonnes sont dans différentes lignes. Ces colonnes s'appellent les colonnes de base et les variables d’écart s'appellent les variables de base dans le tableau initial (elles sont indiquées avec  dans le tableau ci-dessus). Pour cette raison, il y a une solution évidente aux équations: donner la valeur zéro à chacune des variables x1, x2 et x3 et résoudre pour les variables de base :

 

 

 

 

 

En d’autres mots, (0,0,0,6,9,20) est une solution admissible qui donne la valeur 0 pour f. Une telle solution (avec des variables ``non-basic`` nulles) s’appelle une solution admissible de base.

 

L’idée principale de l’algorithme du simplex est donnée par le théorème suivant :

 

Si un problème de programmation linéaire standard admet une solution, il existe alors une solution admissible  de base qui donne une valeur maximale de la fonction objective. De telles solutions admissibles de base s'appellent des solutions optimales.

 

Notre but est alors de trouver un point admissible de base qui soit optimal. Notre construction employant des variables d’écart garantit une première solution admissible de base; nous vérifions après si elle est optimale.

 

La dernière ligne du tableau initial donne f en fonction des variables ``non-basic`` :

 

 

 

Le fait que quelques coefficients ici sont positifs suggère que cette valeur de f n’est pas optimale car si on  augmente les valeurs de x1 ou x2 , la valeur de f augmente aussi. Il semblerait meilleur d'augmenter x2 dans ce cas-ci puisqu'il a le plus grand des deux coefficients positifs (d'une manière équivalente, l'entrée la plus négative dans la dernière rangée du tableau). Ceci suggère alternativement que nous essayions de modifier le tableau de sorte que x2 devienne une nouvelle variable de base. Pour cette raison, x2 s'appelle la variable entrante. Sa colonne s'appelle la colonne pivot.

 

Ceci est accompli en faisant des opérations élémentaires sur les lignes pour convertir la colonne pivot en colonne de base. La question est où localiser le 1. Nous ne mettons pas le 1 dans la dernière ligne parce que nous ne voulons pas changer f, mais il peut être placé à n'importe quel autre endroit dans la colonne pivot où l'entrée actuelle est  non nulle (dans l'exemple ci-dessus, toutes ces entrées de la colonne pivot sont bonnes). L'entrée choisie s'appelle le pivot, et elle est choisie comme suit:

  1. Le pivot doit être positif.
  2. Parmi les entrées positives disponibles, le pivot est celui qui produit le plus petit rapport une fois divisé par l’entrée la plus à droite dans sa ligne.

 

Retournons maintenant à notre exemple, nous récrivons le tableau initial et mettons le symbole   autour du pivot. Les rapports correspondant aux deux entrées positives dans la colonne pivot (colonne 2 ici) sont montrés à droite. Aucun rapport n'est calculé pour la ligne 2, parce que l'entrée correspondante dans la colonne de pivot est négative, par conséquent le pivot est 2.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Effectuons maintenant des opérations élémentaires sur les lignes pour convertir le pivot en 1 et toutes les autres entrées dans sa colonne en 0. Ceci donne la matrice:

 

 

 

 

 

 

 

 

 

Notez que l'ancienne variable de base x4 n'est plus une variable de base parce qu'elle a eu un 1 dans la même ligne que le pivot, il s'appelle maintenant la variable partante. Les nouvelles variables de base sont x2, x5, et x6, et la nouvelle solution admissible  (en prenant les nouvelles variables ``non-basic`` égales à zéro) est x2=0, x5=12, x6=11, et f=9. En d'autres termes, (0, 3, 0, 0, 12, 11) est la solution admissible qui donne la valeur f=9.

 

C'est meilleur qu'avant; f a augmenté de 0 à 9.

 

Répétons maintenant le processus. La dernière ligne ici donne

 

 

 

 

Il y a alors une chance d'augmenter f en transformant x1 en une variable de base (il a un coefficient positif). Par conséquent la première colonne est la colonne pivot et chacune des trois entrées au-dessus de la ligne inférieure est positive. Le tableau est déplacé une fois de plus, avec les rapports donnés et le prochain pivot (avec le plus petit rapport) est identifié par le symbole :  

 

 

 

 

 

 

 

 

 

 

Des opérations élémentaires sur les lignes donnent le troisième tableau avec x1, x2, x6 comme variables de base.

 

 

 

 

 

 

 

La solution admissible correspondante  (obtenue en posant x3=x4=x5=0) est

 

 

 

 

 

 

En d’autres mots,  (24/7, 9/7, 0, 0, 0, 65/7) est une solution admissible qui f=75/7.

 

 

Nous réclamons que c'est une solution optimale. La dernière ligne du troisième tableau donne

 

 

 

 

alors, comme  x3, x4 et x5 are non-négatives, f ne peut pas dépasser la valeur 75/7. La solution précédente donne f=75/5, ainsi elle doit être optimale. Ceci termine la solution de l'exemple.

 

 

Pour savoir plus sur la méthode du simplex, consultez les pages suivantes  (liens en anglais):

 

  1. The Simplex Method (A step by step description of the algorithm)
  2. Simplex Algorithm in 3D (Click to see graphical approach in 3D)
  3. Interactive Demo (Use this Java Applet program to solve your linear programming problem) 

 

 

 

 

 

 

Références :

 

ANTON, H. and C. RORRES. Elementary Linear Algebra: Applications Version, 8th ed. New York: John Wiley & Sons, Inc., 2000.

 

W. KEITH NICHOLSON. Linear Algebra with Applications, third ed. PWS Publishing Company, Boston, 1993.