La programmation linaire est un sujet trs vaste qui ncessiterait
un cours exclusivement sur ce thme. Le temps consacr au dpartement
GEA est trop rduit pour aborder tous les problmes. Seuls les cas
simples y sont traits. Cependant un paragraphe supplmentaire
intitul "complments" est intgr dans ce site, permettant de donner
des ides sur ce qu'il y a lieu de faire lorsqu'on sort du cadre le
plus simple.Les tudiants du dpartement GEA trouveront une approche
plus dynamique du problme sur le logiciel "Mathmatiques pour
l'conomie - algbre linaire" en libre accs en salle
d'informatique.
On appelle Programmation Linaire, le problme mathmatique qui
consiste optimiser (maximiser ou minimiser) une fonction linaire de
plusieurs variables qui sont relies par des relations linaires
appeles contraintes.1) RESOLUTION GRAPHIQUECette mthode n'est
applicable que dans le cas o il n'y a que deux variables. Son
avantage est de pouvoir comprendre ce que fait la mthode gnrale du
Simplexe, sans entrer dans la technique purement mathmatique.Soit
rsoudre le problme suivant:Maximiser la fonction objectif z = 1200
x1 + 1000x2sous les contraintes conomiques3 x1 + 4 x2 1606 x1 + 3
x2 180et les contraintes de signex1 0 ; x2 0les inconnues x1 et x2
sont appeles variables d'activitLes contraintes conomiques et de
signe sont reprsentes graphiquement par des demi-plans dont
l'intersection est un ensemble convexe (c..d. tout segment de
droite dont les extrmits appartiennent l'ensemble est entirement
inclus dans cet ensemble). Les solutions, si elles existent
appartiennent donc cet ensemble appel rgion des solutions
admissibles.
Il s'agit donc de chercher l'intrieur de ce domaine, le couple
(x1 , x2) maximisant la fonction objectif. Or l'quation 1200 x1 +
1000x2 = z0 est reprsente par une droite de pente constante (-1,2)
dont tous les points (x1 , x2) fournissent la mme valeur z0 pour la
fonction conomique. En particulier, la droite 1200 x1 + 1000x2 = 0
passe par l'origine et donne une valeur nulle la fonction
conomique.Pour augmenter la valeur de z0 et donc la fonction
conomique, il suffit d'loigner de l'origine (dans le quart de plan
x1 0;x2 0) la droite de pente -1,2Pour respecter les contraintes,
cette droite sera dplace jusqu' l'extrme limite o il n'y aura plus
qu'un point d'intersection (ventuellement un segment) avec la rgion
des solutions admissibles. On remarquera que la solution optimale
se trouve ncessairement sur le pourtour de la rgion des solutions
admissibles.La solution se trouvant sur les deux droites d'quation3
x1 + 4 x2 1606 x1 + 3 x2 180la rsolution de ce systme conduit la
solution x1 =16 , x2 28, d'o z = 47200.2) METHODE DU SIMPLEXEa)
Forme canonique d'un Programme LinaireMax z = c1 x1 + c2 x2 +
.......... +cn xn a11 x1 + a12 x2 + .......... + a1n xn b1a21 x1 +
a22 x2 + .......... + a2n xn
b2............................................................................am1
x1 + am2 x2 + .......... + amn xn bm x1 0 ; x2 0 ; .........; xn
0b) Forme standard d'un Programme LinaireOn transforme les ingalits
des contraintes conomiques en galits par introduction de variables
supplmentaires positives ou nulles appeles variables d'cart.ai1 x1
+ ai2 x2 + .......... + ain xn bi devient ai1 x1 + ai2 x2 +
.......... + ain xn + ti bid'o la forme standardMax z = c1 x1 + c2
x2 + ..........+ cn xn a11 x1 + a12 x2 + .......... + a1n xn + t1
b1a21 x1 + a22 x2 + .......... + a2n xn + t2
b2............................................................................am1
x1 + am2 x2 + .......... + amn xn + tm bm x1 0 ; x2 0 ; .........;
xn 0 ; t1 0 ; t2 0 ; .........; tm 0c) RsolutionAfin de comparer
avec la rsolution graphique, nous pouvons considrer que nous sommes
dans un espace n dimensions (nombre de variables d'activit). Les
contraintes dlimitent un polydre convexe, rgion des solutions
admissibles; la fonction objectif est un hyperplan que l'on va
dplacer le plus loin possible de l'origine, jusqu' l'extrme limite
o il n'y aura plus qu'un point d'intersection (ventuellement un
segment, un plan...) avec la rgion des solutions admissibles. La
solution se trouvant forcment sur le pourtour du polydre
admissible, la mthode du simplexe consiste en itrations qui font
passer d'un sommet du polydre un autre en slectionnant le sommet
adjacent maximisant la fonction objectif.Pour dmarrer l'algorithme,
il est ncessaire d'avoir une solution initiale. Dans le cas simple,
l'origine est solution, c..d. que la premire solution est x1 0 ; x2
0 ; .........; xn 0 ; t1 b1 ; t2 b2 ; .........;tm bm (ceci suppose
que les bi ne soient pas ngatifs pour satisfaire les contraintes de
signe)L'algorithme, bas sur la mthode du pivot de Gauss pour la
rsolution des systmes d'quations linaires, est prsent sous forme de
tableau.Soit rsoudre le programme linaire suivant sous sa forme
canonique3 x1 + 4 x2 1606 x1 + 3 x2 180Max z = 1200 x1 + 1000x2x1 0
; x2 0* Forme standard 3 x1 + 4 x2 + 1 t1 + 0 t2 160 6 x1 + 3 x2 +
0 t1 + 1 t2 180Max z = 1200 x1 + 1000x2 + 0 t1 + 0 t2x1 0; x2 0 ;
t1 0;t2 0* Tableau 0en ne conservant que les coefficients des
quations ci-dessus, on obtient le tableau de dpartHBBx1x2t1t2C
t13410160
t26301180
12001000000
Ce tableau nous donne la premire solution admissible:- Les
variables Hors Base (HB) sont nulles: x1 0; x2 =0(t1 ett2 en rouge
ne sont pas hors base; elles ne sont prsentes que pour rappeler
qu'il s'agit des colonnes des coefficients de ces deux variables)-
Les valeurs des variables dans la Base (B) se lisent dans la
colonne C: t1 = 160 ett2 =180- La dernire cellule (intersection de
C et ) donne la valeur de -z : -z = 0 donc z = 0- La ligne donne
les valeurs marginales ou taux marginal de substitution; elles
s'interprtent de la manire suivante: ce stade de la solution, une
augmentation de 1 unit dex1 ferait accrotre la fonction objectif de
1200, et une augmentation de 1 unit dex2 ferait accrotre la
fonction objectif de 1000.* Tableau 1On augmente la fonction
objectif en faisant entrer une variable dans la base, prenant la
place d'une variable qui va sortir de la base.Critre de slection de
la variable entrant dans la base:On slectionne la variable HB ayant
le plus grand coefficient positif dans la ligne .
x1 entre donc dans la basePour slectionner la variable sortant
de la base, il est ncessaire de rajouter une colonne R au tableau,
obtenue en faisant le rapport membre membre de la colonne C et de
la colonne de la variable entrant dans la base (x1)Remarques sur la
colonne R: - Un 0 dans la colonne C est remplac par un infiniment
petit positif pour effectuer le calcul de R- Dans la colonne R on
ne tient pas compte des valeurs ngatives ou indtermines
HBBx1x2t1t2CR
t13410160160/3
t2630118030
12001000000
Critre de slection de la variable sortant de la base:On
slectionne la variable dans la Base ayant le plus petit coefficient
positif dans la colonne R.
t2 sort donc de la baseHBBx1x2t1t2CR
t13410160160/3
t2630118030
12001000000
variable sortant
variable entrant
On appelle pivot (gal 6) l'intersection de la variable entrante
et de la variable sortantePour obtenir le tableau 1, on applique
les rgles suivantes:- Le pivot est gal 1- Les coefficients de la
ligne du pivot sont diviss par le pivot- Les coefficients de la
colonne du pivot sont nuls- Les autres coefficients sont obtenus
par la rgle du rectangle
La rgle du rectangle est la suivante:Remarque importante: d = d'
c b = 0 b = 0 ou c = 0 En consquence, si dans la colonne (resp.
ligne) du pivot il y a un 0, toute la ligne (resp. colonne)
correspondante reste inchange.En appliquant ces rgles on obtient le
tableau 1:HBBx1x2t1t2C
t105/21-1/270
x111/201/630
04000-200-36000
Ce tableau nous donne la deuxime solution admissible:- Les
variables Hors Base (HB) sont nulles: x2 0; t2 =0(x1 ett1 en rouge
ne sont pas hors base; elles ne sont prsentes que pour rappeler
qu'il s'agit des colonnes des coefficients de ces deux variables)-
Les valeurs des variables dans la Base (B) se lisent dans la
colonne C: t1 = 70 etx1 =30- La dernire cellule (intersection de C
et ) donne la valeur de -z : -z = -36000 donc z = 36000- La ligne
donne les valeurs marginales ou taux marginal de substitution;
elles s'interprtent de la manire suivante: ce stade de la solution,
une augmentation de 1 unit dex2 ferait accrotre la fonction
objectif de 400, et une augmentation de 1 unit det2 ferait diminuer
la fonction objectif de 200 (il est noter qu'une augmentation de 1
unit dela variable d'cart t2 revient diminuer le second membre de
l'quation correspondante de 1 unit).* Tableau 2:HBBx1x2t1t2CR
t105/21-1/27028
x111/201/63060
04000-200- 36000
variable sortant
variable entrant
d'o le tableau 2HBBx1x2t1t2C
x2012/5-1/528
x110-1/54/1516
00-160-120- 47200
Ce tableau nous donne la troisime solution admissible:- Les
variables Hors Base (HB) sont nulles: t1 0; t2 =0(x1 etx2 en rouge
ne sont pas hors base; elles ne sont prsentes que pour rappeler
qu'il s'agit des colonnes des coefficients de ces deux variables)-
Les valeurs des variables dans la Base (B) se lisent dans la
colonne C: x2 = 28 etx1 =16- La dernire cellule (intersection de C
et ) donne la valeur de -z : -z = - 47200 donc z = 47200- La ligne
donne les valeurs marginales ou taux marginal de substitution;
elles s'interprtent de la manire suivante: ce stade de la solution,
une augmentation de 1 unit det1 ferait diminuer la fonction
objectif de 160, et une augmentation de 1 unit det2 ferait diminuer
la fonction objectif de 120 (il est noter qu'une augmentation de 1
unit d'une variable d'cart revient diminuer le second membre de
l'quation correspondante de 1 unit).Critre d'arrt des itrations:Si
tous les coefficients de la ligne relatifs aux variables HB, sont
ngatifs ou nuls, la solution trouve est optimale.
Nous avons donc ici atteint la solution optimale.Remarques
importantes:- S'il existe une variable HB ayant un coefficient
positif dans la ligne et telle que tous les coefficients
correspondants dans le tableau soient nuls ou ngatifs, alors la
solution est infinie.- Si, la fin des itrations, une variable est
HB avec un coefficient nul dans la ligne , alors on a une arte
(plan,...) optimale. Les autres sommets solutions sont obtenus en
faisant rentrer cette variable dans la base.3) DUALA tout programme
linaire appel PRIMAL correspond un programme linaire appel DUAL
obtenu de la manire suivante:PRIMALDUAL
m contraintes d'infrioritn variables d'activitm variables
d'cartcriture en lignen contraintes de suprioritn variables d'cartm
variables d'activitcriture en colonne
exemplePRIMALDUAL
3 x1 + 4 x2 1606 x1 + 3 x2 180Max z = 1200 x1 + 1000x2x1 0 ; x2
03 y1 + 6 y2 4 y1 + 3 y2 Min w = 160 y1 + 180 y2y1 0 ; y2 0
A l'optimum, le primal et le dual sont lis par les rgles
suivantes:- les fonctions objectifs z et w ont la mme valeur
optimale- la valeur marginale d'une variable dans un programme est
gale l'oppos de la valeur optimale de la variable associe dans
l'autre programme et rciproquement.exemplePRIMALz =
47200x1x2t1t2
valeurs optimales162800
valeurs marginales00-160-120
DUALw = 47200u1u2y1y2
valeurs optimales00160120
valeurs marginales-16-2800
