LA PROGRAMMATION LINEAIRE : UN OUTIL DE MODELISATION

Dans les leons prcdentes, nous avons modlis des problmes en utilisant des graphes.
Nous abordons dans cette leon un autre type de modlisation. Un problme d'optimisation va tre
reprsent par un problme de programmation mathmatique : les variables de dcision sont des
variables numriques, la reprsentation des dcisions possibles et du critre fait appel des quations
ou fonctions mathmatiques. Plus prcisment, nous introduisons ici le problme particulier de
programmation linaire.

I Exemples dintroduction
Exemple 1
Le problme
L'entreprise "Nacege", spcialise dans la fabrication de matriels informatiques, propose son
catalogue d'ordinateurs des centaines de rfrence.
Pour simplifier, on ne s'intresse ici qu' deux types d'ordinateurs : le IM4 et le IM5.
Chacun d'eux comporte un processeur - le mme - mais les deux modles diffrent en particulier par
le nombre de barrettes mmoires.
Plus prcisment, le IM4 comporte 2 barrettes alors que le IM5 en comporte 6.
Le march pour ces composants est tel qu'on ne peut esprer acheter auprs des fournisseurs
habituels plus de 10 000 processeurs pour le trimestre venir et plus de 48 000 barrettes.
Une autre limitation risque dintervenir sur la production. Lassemblage est caractris, en particulier,
par une opration dlicate, qui pour lIM4 est de 3 minutes alors que pour lIM5 elle nest que dune
minute ; on ne dispose a priori pour lassemblage de ces deux types de machines que de 24 000
minutes pour le trimestre venir.
Enfin, compte tenu des conditions actuelles du march, on peut esprer retirer un profit de 400 euros
sur lIM4 et de 800 euros sur lIM5.
Le problme est de dterminer les quantits de chacun des deux types d'ordinateurs fabriquer de
manire obtenir le plus grand profit possible.
Modlisation du problme
Nous examinons dans lordre la reprsentation des dcisions, des dcisions possibles et du critre.
Les dcisions
Les dcisions concernent les quantits fabriquer, ce qui se reprsente naturellement par deux
nombres positifs x1 pour lIM4 et x2 pour lIM5.
Les dcisions possibles
Il sagit de reprsenter les diffrentes contraintes limitant la production de ces deux types
dordinateur.
La premire porte sur la limitation du nombre de processeurs disponibles : chaque machine utilise un
processeur et on peut en disposer de 10 000.
On doit donc imposer :
x1 + x2 10 000
De mme, le nombre de barrettes est limit. Compte tenu du nombre de barrettes dans chacun des 2
ordinateurs et du nombre de barrettes disponibles, cette contrainte se traduit par :
2x1 + 6x2 48 000
Enfin, la contrainte portant sur le temps d'assemblage s'crit :
La programmation linaire : un outil de modlisation

3x1 + x2 24000
Lensemble des dcisions possibles est donc caractris par lensemble des valeurs de x1 et x2
vrifiant :
x1 + x2 10 000
2x1 + 6x2 48 000
3x1 + x2 24 000
x1 0 x2 0
Le critre
On souhaite maximiser le profit qui est reprsent par : 400x1 + 800x2.
Le problme initial est donc modlis par le problme de programmation mathmatique suivant :
Max (400 x1 + 800 x2)
sous les contraintes
x1 + x2 10 000
2x1 + 6x2 48 000
3x1 + x2 24 000
x1 0x2 0
Le modle obtenu est un exemple de problme de programmation linaire.

Exemple 2
Prsentons dabord le problme.
Une entreprise disposant de plusieurs lieux de production doit transporter ses produits finis vers des
entrepts rgionaux pour rpondre aux besoins locaux.
Pour simplifier lexemple, on se contente de 2 usines avec 3 entrepts.
On peut a priori faire transiter le produit de n'importe quelle unit de production vers n'importe quel
entrept.
Chaque unit de production a une capacit limite. Supposons, par exemple, que la capacit de
production de lusine 1 (note U1) soit de 100 (en milliers de tonnes) et celle de lusine U2 de 150.
Les entrepts ont exprim une demande qui doit tre satisfaite : l'entrept 1, not E1, a une demande
de 50 (en milliers de tonnes), le deuxime 70 et le troisime 80.
Le cot de transport dpend bien sr du trajet effectuer et du mode de transport, donc de l'usine de
dpart et de l'entrept d'arrive.
Le cot de transport par tonne de lusine i (i = 1,2) vers lentrept j (j = 1,2,3) est donn dans le
tableau suivant.

U1
U2

E1
4
3

E2
3
5

E3
6
3

Le problme est de dterminer les quantits transporter de chaque usine vers chaque entrept, de
manire minimiser le cot total de transport tout en respectant les contraintes de capacit des
usines et de demande des entrepts.

Le modle
Les dcisions
Elles portent sur les quantits transporter.
La quantit transporte (en milliers de tonnes) de l'usine i vers le dpt j est reprsente par la
variable positive xij (i = 1,2 et j = 1,2,3).

La programmation linaire : un outil de modlisation

Les dcisions possibles

Il sagit de traduire les contraintes limitant les dcisions. Il y a deux types de contraintes, celle portant
sur la capacit des usines et celle portant sur la demande des magasins.

- Limitation sur la capacit de production des usines

Il faut exprimer que, de chaque usine, ne peut partir une quantit suprieure ce quelle est capable
de produire.
Pour lusine U1, x11 + x12 + x13 reprsente, en milliers de tonnes, ce qui part vers les entrepts. La
contrainte sur la capacit de lusine U1 est traduite par :
x11 + x12 + x13 100
Pour l'usine 2, on a de mme :
x21 + x22 + x23 150
- Limitation sur la demande des entrepts
Ce qui arrive chaque entrept doit tre gal ce quil a demand. Pour lentrept E1, x11 + x21
reprsente la quantit qui lui est livre.
Sa demande tant de 50, on doit donc imposer :
x11 + x21 = 50
On a de mme pour les 2 autres entrepts :
x12 + x22 = 70
x13 + x23 = 80
Lensemble des dcisions possibles est donc caractris par lensemble des valeurs des xij vrifiant :
x11 + x12 + x13 100
x21 + x22 + x23 150
x11 + x21 = 50
x12 + x22 = 70
x13 + x23 = 80
xij 0 i = 1,2 j = 1,2,3
Le critre
On souhaite minimiser le cot total de transport.
Si on fait lhypothse que sur chaque trajet le cot est proportionnel aux quantits transportes, le
cot total scrit :
4 x11 + 3 x12 + 6 x13 + 3 x21 + 5 x22 + 3 x23
que lon souhaite minimiser.
Le problme initial est donc modlis par le problme de programmation mathmatique.
Min 4 x11 + 3 x12 + 6 x13 + 3 x21 + 5 x22 + 3 x23
sous les contraintes
x11 + x12 + x13 100
x21 + x22 + x23 150
x11 + x21 = 50
x12 + x22 = 70
x13 + x23 = 80
xij 0 i = 1,2 j = 1,2,3
Ce problme, appel "problme de transport classique", est, comme dans le premier exemple,
modlis par un problme de programmation linaire.

La programmation linaire : un outil de modlisation

II Dfinition dun problme de programmation linaire

Le modle type de programmation linaire peut tre retenu pour reprsenter de nombreux problmes.
Un problme sera modlis par un problme de programmation linaire si :
- les dcisions peuvent tre reprsentes par des nombres rels (gnralement positifs),
- les contraintes portant sur ces variables peuvent tre reprsentes par des quations ou des
inquations linaires c'est--dire que les variables n'interviennent qu'au premier degr (pas de carrs,
pas de produit de variables),
- le critre de choix peut tre reprsent par une fonction linaire des variables que l'on souhaitera
minimiser ou maximiser.
La forme gnrale dun problme de programmation linaire de n variables et p contraintes est :
min ou max c1x1 + c2x2 +....+ cj xj ++ cnxn
sous les contraintes
ai1 x1 + ai2 x2 ++ ain xn , ou = di
pour i = 1, ..p
xj 0 j = 1, ...,n
Les coefficients cj de la fonction objectif, les coefficients aij du premier membre des contraintes et les
seconds membres di des contraintes sont des donnes du problme.
Dfinitions
Une solution ralisable est un n-uplet (x1,...,xn) vrifiant toutes les contraintes.
Une solution optimale est une solution ralisable qui donne la fonction objectif la plus grande
(problme de maximisation) ou la plus petite valeur possible (problme de minimisation) sur
lensemble des solutions ralisables.
La valeur maximale (resp : minimale) de la fonction objectif ( ne pas confondre avec la solution
optimale) est la plus grande valeur (resp : la plus petite) que peut prendre la fonction objectif sur
lensemble des solutions ralisables.
Les exemples de problme qui relvent de la programmation linaire sont fort nombreux. On peut
citer :
- les problmes de mlange : quelle est la composition optimale dun produit ?
- les problmes de planification de production : quand et quel moment doit-on planifier la
production dun bien,
- les problmes de transport, gnralisation du problme de transport classique,
- les problmes de planification dhoraires,
- les problmes de dcoupe industrielle
.....

La programmation linaire : un outil de modlisation

III Rsolution graphique d'un problme de programmation linaire

De manire trs gnrale, la rsolution dun problme de programmation linaire ncessite la mise en
oeuvre dun algorithme. Nous en verrons le principe dans la leon suivante.
Dans le cas o le problme ne comporterait que deux variables, on peut le rsoudre graphiquement.
Cette rsolution graphique permet de mettre en vidence certaines proprits que possde nimporte
quel problme de programmation linaire.
Considrons le problme de lexemple 1 :
Max (400 x1 + 800 x2)
x1 + x 2 10 000
2x1 + 6x2 48 000
3x1 + x2 24 000
x1 0 x2 0

(1)
(2)
(3)

A chaque couple de variables x1 et x2, on associe un point du plan dont les coordonnes
correspondent aux valeurs des variables.
Les variables tant positives, ces points sont situs dans l'orthant positif (le quart Nord-Est du plan).
Chaque contrainte permet de dlimiter une partie du plan.
Par exemple, la droite d'quation x1 + x2 = 10 000 dfinit 2 demi-plans.
Au-dessus de cette droite, les coordonnes des points du plan vrifient x1 + x2 > 10 000.
On est donc conduit exclure ces points.
On fait de mme pour les 2 autres
contraintes.
On trace les droites d'quation
x1 + 2x2 = 48 000 et
3x1 + x2 = 24 000
et on limine les points situs audessus de ces droites.

Les solutions ralisables du

problme correspondent aux points
du plan situs l'intrieur du
polydre O A B C D et sur ses bords.
Il s'agit maintenant de dterminer parmi tous ces points celui ou ceux qui correspondent la plus
grande valeur possible pour la fonction objectif 400 x1 + 800 x2
Considrons la droite dquation 400 x1 + 800 x2 = k o k est une constante.
Tous les points situs sur cette droite donnent lexpression 400 x1 + 800 x2 la mme valeur k.
Ils sont quivalents du point de vue du profit.
Si on dplace cette droite vers la droite, la valeur de k augmente.
La valeur limite pour k est obtenue pour la droite passant par le point B.

La programmation linaire : un outil de modlisation

On peut conclure que sur l'ensemble du domaine des solutions ralisables, celle qui donne la plus
grande valeur la fonction objectif correspond au point B dont les coordonnes peuvent tre calculs
comme point d'intersection des contraintes (1) et (2).
La solution optimale du problme est x1 = 3 000 x2 = 7 000
La valeur maximale de la fonction objectif est : 6 800 000.
Pour lentreprise, ceci signifie que la rpartition optimale entre les deux types dordinateurs est de
3000 ordinateurs de type IM4 et 7000 ordinateurs de type IM5 avec un profit maximal de 6 800 000
.
Lanalyse de cette solution montre que tous les processeurs et toutes les barrettes sont utiliss, mais
qu'il reste du temps dassemblage disponible.
On dit que les contraintes (1) et (2) sont satures ou lies : elles sont vrifies avec galit
loptimum alors que la contrainte (3) est non sature ou non lie : il y a une marge entre la valeur de
son premier et celle de son second membre loptimum.

IV Etude graphique de lanalyse de sensibilit

Problme 1
La modlisation et la rsolution du modle a t faite en supposant que le profit sur le IM4 tait de
400 . En fait, cette machine est trs bien accueillie sur le march et les cots de fabrication sont
moins levs que prvus. On peut donc esprer un profit plus important sur ce type de machine.
Faut-il en produire davantage quitte diminuer la production de l'IM5 ?
Le profit p 1 sur lIM4 devient un paramtre du problme qui s'crit maintenant :

La programmation linaire : un outil de modlisation

Max (p1 x1 + 800 x2)

x1 + x 2 10 000
(1)
2x1 + 6x2 48 000
(2)
3x1 + x2 24 000
(3)
x1 0 x2 0
Analysons graphiquement les consquences de la variation du profit sur l'IM4.
La droite reprsentative du profit avait pour quation 400 x1 + 800 x2 = constante.
La variation du profit sur l'IM4 implique que le coefficient de x1 dans cette quation varie et donc que
la pente de la droite reprsentative du profit varie.
Tant que la pente de cette droite reste comprise entre celle des droites (1) et (2), le raisonnement fait
lors de la rsolution graphique conduit la conclusion que la solution associe au point B est toujours
optimale.
L'intervalle de variation de p 1 est donn par :
1/3 p 1/800 1 soit 800/3 p 1 800
On a donc mis en vidence un intervalle de variation du coefficient de x1 dans la fonction objectif sur
lequel la solution optimale n'est pas change.
Dans cet exemple, ceci nous conduit la conclusion que tant que le profit sur l'IM4 reste entre 800/3
et 800, il faut continuer produire 3000 units de lIM4 et 7000 pour l'IM5.
Pour ces mmes valeurs de p 1, la valeur maximale du profit total sera gale :
3 000 p 1 + 800* 7000 = 3 000 p 1 + 5 600 000
Problme 2
Un deuxime problme se pose : actuellement, le nombre de processeurs que l'on pourrait acqurir
est estim 10 000. Mais lincertitude sur les quantits susceptibles d'tre livres est grande.
On voudrait savoir quel serait l'impact sur la production d'une modification de cette quantit.
L'analyse graphique va nous apporter une rponse.
La contrainte portant sur le nombre de processeurs est reprsente par la droite (1) dont lquation
x1+ x2 = 10 000 passe x1 + x2 = 10 000 + !
Graphiquement cela signifie que la contrainte (1) se dplace paralllement elle-mme, vers le haut
si ! est positif, vers le bas si ! est ngatif.
On constate alors que le point B intersection des droites (1) et (2) en lequel se trouve actuellement la
solution optimale se dplace sur la droite (2).
Comme les pentes des droites (1) et (2) ne sont pas changes, la solution optimale reste
l'intersection des contraintes (1) et (2), condition cependant que ce point reste dans le domaine des
solutions ralisables.
Dans ces conditions, pour avoir la solution optimale, il suffit de dterminer les coordonnes du point
d'intersection des droites (1) et (2).
x1+ x2 = 10000 + !
et 2x1 + 6x2 = 48 000
soit x1 = 3 000 + 3 ! /2

et

x2 = 7 000 -

! /2

Ces valeurs correspondent la solution optimale, condition que cette solution soit ralisable.
x1 0 , x2 0 et la contrainte (3) doit rester satisfaite :
x1 0 3 000 + 3 ! /2 0 !
! - 2 000
x2 0 7 000 - ! /2 0 ! 14 000
Contrainte (3) satisfaite 3 (3 000 + 3 ! /2) + 7 000 soit - 2 000

! /2 24 000

! 2 000

! 2 000

La programmation linaire : un outil de modlisation

Tant que ! reste compris entre -2000 et 2000, la solution optimale reste lintersection des
contraintes (1) et (2) : cest dire que les processeurs et les barrettes continuent dtre utiliss
entirement alors quil reste toujours du temps dassemblage disponible. Les quantits fabriquer
dpendent cependant de ! , cest dire du nombre de processeurs disponibles.
Pour ! processeurs supplmentaires, la production de lIM4 augmente de 3 ! /2 alors que celle de
lIM5 diminue de ! /2.
La variation du profit sera alors gale 400* 3 ! /2 - 800* ! / 2 = 200 ! .
Chaque processeur supplmentaire pourrait faire augmenter le profit de 200, ou au contraire, toute
diminution de ce nombre de processeurs le fera diminuer de 200 par processeur en moins, et ceci sur
un intervalle allant de - 2000 processeurs + 2000 processeurs.
De cette information on doit pouvoir tirer les consquences sur lintrt que lon pourrait avoir
trouver un autre fournisseur susceptible de fournir lui-aussi ce matriel un prix qui, le cas chant,
pourrait tre suprieur au prix actuel, compte-tenu de ce que cela peut rapporter.
Nous venons de voir graphiquement quelles pouvaient tre les consquences dune variation dun
coefficient de la fonction objectif ou du second membre dune contrainte. Tout problme de
programmation linaire donne lieu ce type d'analyse et les rsultats obtenus ici sont gnraux.

La programmation linaire : un outil de modlisation