Accueil » Publications » Le Bulletin Vert » Spécial journées » 256-257. Programmation linéaire.
  APMEP   256-257. Programmation linéaire.

Article du bulletin 256-257

- 22 janvier 2013 -

par L. GUERBER

Professeur à la Faculté de Droit et de Sciences Économiques de Clermont

1. Quelques problèmes de la vie économique.

L’alimentation, pour être rationnelle, doit fournir à l’organisme un certain nombre de produits considérés comme essentiels, destinés à assurer l’entretien des tissus, à être brûlés dans l’organisme, à assurer le minimum d’apport de certains principes de manière à écarter les maladies par carence. C’est ainsi que l’on estime que la ration d’un homme normal doit comporter des protides, des glucides, des lipides, etc. de façon à lui fournir environ 2500 calories par jour tout en lui apportant des doses, supérieures à certains seuils, de vitamines, par exemple : plus de 50 mg de vitamine C (dont la carence est liée à l’apparition du scorbut).

Par ailleurs, on connait la teneur en protides, glucides, lipides, etc., des différents aliments ; sur les Tables, on lit le nombre de calories apportées par les divers aliments : par exemple 150 g de radis en apportent 18, mais ISO g de boudin grillé en apportent 725. Enfin on connait la richesse en vitamines C par exemple, de la plupart des fruits acides tels que le citron.

Connaissant le coût de divers aliments, on peut se proposer de rechercher une alimentation de coût minimum qui apporte, à l’organisme, les qualités nutritives [1] indispensables en quantités suffisantes.

De telles recherches furent effectivement menées par George Stigler dès 1945 en opérant sur 77 aliments, 9 principes nutritifs et en utilisant les prix aux U.S.A. en 1939 puis ceux de 1944 : il observa une hausse d’environ 50 %.

Actuellement, ce sont essentiellement dans le cadre de l’alimentation du bétail (par exemple des porcs du Minnessota) que de telles recherches sont effectivement poursuivies, en fonction des prix journaliers des denrées. Certains économistes, également, se penchent sur de tels problèmes dans le cadre de l’aide aux pays sous-alimentés.

1.2. Problèmes d’investissement

A chaque instant, l’E.D.F. doit être en mesure de fournir une quantité d’énergie supérieure à celle qui lui est demandée. On peut, pour simplifier, se limiter à 3 paramètres :

  • l’énergie annuelle consommée qui se mesure en GWh ($1GWh = 10^{6} KWh$) ;
  • la puissance de pointe exprimée en MW ($1 MW = 10^{3} KW$) correspondant à la moyenne des heures de pointes des jours ouvrables ;
  • la puissance garantie correspondant aux moyennes horaires des jours ouvrables d’hiver, exprimée, elle aussi, en MW.
    Pour satisfaire cette demande, l’E.D.F. dispose de divers modes de production avec les centrales « au fil de l’eau », les centrales thermiques, les centrales nucléaires, l’usine marémotrice de la Rance... etc. Connaissant les caractéristiques de ses diverses usines et leur coût de fonctionnement l’E.D.F. peut définir la production de coût minimum.
    Par ailleurs, on connait la progression de la demande d’énergie en fonction du temps, aussi l’E.D.F. doit-elle se définir un programme d’implantation de nouvelles usines. Elle est donc amenée à étudier les investissements de coût minimum (qui ne seront pas forcément des décisions conduisant ultérieurement à des coût de production ou d’entretien minimum).

1.3. Problèmes de production

Une même entreprise fabrique le plus souvent divers produits ; par exemple une menuiserie produit différents modèles de chaise ; une usine fabrique différents types d’engrais ; une raffinerie livre surle marché de l’essence de qualités variées, du gas-oil, du fuel-oil et du gaz. Un problème qui se pose journellement est de définir le meilleur programme de fabrication de façon à satisfaire la demande extérieure et améliorer au maximum le bénéfice ou réduire au minimum les dépenses d’exploitation.
C’est un problème numérique de cette catégorie qui servira de support à l’étude que nous allons faire.

1.4. Problèmes d’affectation.

Toute entreprise de transport (par exemple la S.N.C.F., ou encore une société de location de voitures sans chauffeur telle Europcars, qui offre la location dans la ville choisie par le client d’une voiture de type choisi par le client) se trouve journellement en face de problèmes du type suivant :
disposant de véhicules donnés (wagons vides ou autos de marques données) en des points donnés, comment les acheminer au moindre coût, de façon à se trouver dans une seconde situation imposée.
Ce sont des considérations de ce genre que l’économiste anglais Ricardo [2] évoquait pour illustrer la nature du calcul économique en recherchant la meilleure affectation de divers ouvriers, inégalement habiles, à des tâches varié-s.

1.5. On pourrait penser que, dans ce problème d’affectation où il suffit

de connaître les coûts des diverses affectations, l’emploi des machines à calculer permet de tout évaluer rapidement et, par suite, de connaître l’optimum. Or, si pour 3 ouvriers et 3 tâches, il n’y a que 3 ! = 6 éventualités, il y en a déjà 10 !, soit plus de $ 3x10^6$ pour 10 ouvriers et 10 tâches ; pour 26 ouvriers et 26 tâches il y a 26 ! situations à envisager (une imprimante qui débite 1 500 lignes de 104 caractères par minute exigerait un emploi ininterrompu pendant plus de $10^{12}$ années pour simplement énumérer, par suite de 26 lettres, chacune de ces situations, alors que l’on attribue généralement à la terre une durée de vie probable de l’ordre de $10^{10} $ années !).

Cela montre, à l’évidence, combien un algorithme de calcul est nécessaire pour aborder des problèmes réels qui envisagent des centaines de postes différents. L’emploi simultané d’un algorithme et des ordinateurs augmente considérablement la puissance : c’est ainsi que le code « Marie Claire )) écrit par D. Pigot pour l’UNIV AC 1108 permet de traiter des problèmes faisant intervenir plusieurs milliers de relations.

2. Points communs aux problèmes qui précèdent programmes linéaires.

  • 2.1. Dans les problèmes que nous venons de citer, il s’agit toujours de déterminer des valeurs non-négatives d’inconnues, de façon à optimiser (c’ est-à-dire à rendre extrême) une fonction linéaire de ces inconnues tout en satisfaisant à certaines inégalités linéaires traduisant des contraintes.
    Par exemple dans le cas 1 d’une alimentation de coût minimum il faut trouver des quantités non-négatives des divers aliments à acheter ; la fonction à optimiser est un coût qu’il s’agit de minimiser, et l’on fait implicitement l’hypothèse que le coût est une fonction linéaire des quantités (c’est une hypothèse essentielle, quoique, pas toujours très réaliste, car, d’une part, les prix unitaires diminuent souvent avec l’augmentation des quantités, d’autre part, si l’optimum correspond à un poids précis de fruits du type cerise ou orange il est plus facile de l’approcher en cerises qu’en oranges. On fait également l’hypothèse que les apports des principes essentie1s ont lieu linéairement et que, par suite, pour reprendre les exemples numériques cités, $\lambda$ grammes de radis et $\mu$ grammes de boudin apportent à l’organisme $\lambda\frac {18}{150}+\mu\frac {725}{150}$ calories.
    11 convient également de noter que les valeurs utilisables des inconnues sont bien souvent entières : c’est ainsi que, pour un programme optimum de fabrication de divers modèles de chaises, on veut une réponse en nombres entiers, ce qui conduit au problème de la résolution en nombres entiers des problèmes précédents (c’était déjà le cas ci-dessus pour les oranges ou les cerises.
  • 2.2. Ayant souligné certains traits essentiels communs aux problèmes précédents nous allons, en utilisant un problème numérique de production, donner quelques définitions permettant de s’exprimer dans l’étude de ces questions.
    Soit un atelier fabriquant deux catégories de produits notés 1 et II. On se propose de déterminer un programme de fabrication rendant maximum le bénéfice global, sachant que le bénéfice est de 8 F sur un kg du produit l, et de 10 F sur un kg du produit II. Les contraintes de la fabrication imposent d’utiliser pour cette fabrication, trois machines $M_1, M_2, M_3$, dans un ordre d’ailleurs arbitraire, suivant les temps indiqués ci-dessous en minute pour l’obtention d’un kg de produit 1 ou II (mais le passage d’un produit sur une machine est continu).

Lire l'article dans son intégralité

(Article mis en ligne par Christiane Zehren)

[1] on les appelle aussi "nutriments"

[2] Ricardo David, auteur de "Principes d’économie politique" (1772-1823)


 Accueil   Plan du site   Haut de la page   Page précédente