PROGRAMMATION LINEAIRE   RESOLUTION GRAPHIQUE   SIMPLEXE  DUAL  

La programmation linéaire est un sujet très vaste qui nécessiterait un cours exclusivement sur ce thème. Le temps consacré au département GEA est trop réduit pour aborder tous les problèmes. Seuls les cas simples y sont traités. Cependant un paragraphe supplémentaire intitulé "compléments" est intégré dans ce site, permettant de donner des idées sur ce qu'il y a lieu de faire lorsqu'on sort du cadre le plus simple.

Les étudiants du département GEA trouveront une approche plus dynamique du problème sur le logiciel "Mathématiques pour l'économie - algèbre linéaire" en libre accès en salle d'informatique.

 

---

 

On appelle Programmation Linéaire, le problème mathématique qui consiste à optimiser (maximiser ou minimiser) une fonction linéaire de plusieurs variables qui sont reliées par des relations linéaires appelées contraintes.

1) RESOLUTION GRAPHIQUE

Cette méthode 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 méthode générale du Simplexe, sans entrer dans la technique purement mathématique.

Soit à résoudre le problème suivant:
Maximiser la fonction objectif                  z = 1200 x1 + 1000 x2
sous les contraintes économiques             3 x1 + 4 x2 £ 160
                                                               6 x1 + 3 x2 £ 180
et les contraintes de signe                         x1 ³ 0    ;   x2 ³ 0
les inconnues x1 et x2 sont appelées variables d'activité

Les contraintes économiques et de signe sont représentées graphiquement par des demi-plans dont l'intersection est un ensemble convexe (c.à.d. tout segment de droite dont les extrémités appartiennent à l'ensemble est entièrement inclus dans cet ensemble). Les solutions, si elles existent appartiennent donc à cet ensemble appelé région des solutions admissibles.

Il s'agit donc de chercher à l'intérieur de ce domaine, le couple (x1 , x2) maximisant la fonction objectif.
Or l'équation  1200 x1 + 1000 x2 = z0 est représentée par une droite de pente constante (-1,2) dont tous les points (x1 , x2) fournissent la même valeur z0 pour la fonction économique.
En particulier, la droite 1200 x1 + 1000 x2 = 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,2
Pour respecter les contraintes, cette droite sera déplacée jusqu'à l'extrême limite où il n'y aura plus qu'un point d'intersection (éventuellement un segment) avec la région des solutions admissibles.     

   

On remarquera que la solution optimale se trouve nécessairement sur le pourtour de la région des solutions admissibles.
La solution se trouvant sur les deux droites d'équation 
3 x1 + 4 x2 = 160 
6 x1 + 3 x2 = 180
la résolution de ce système conduit à la solution x1 =16 , x2 = 28, d'où z = 47200.

2) METHODE DU SIMPLEXE

a) Forme canonique d'un Programme Linéaire

Max z = c1 x1   + c2 x2  + .......... +cn xn
                  a11 x1  + a12 x2 + .......... + a1n xn £ b1
                  a21 x1  + a22 x2 + .......... + a2n xn £ b2
                  ............................................................................
                  am1 x1 + am2 x2 + .......... + amn xn £ bm
              x1 ³ 0 ;   x2 ³ 0 ;  .........;  xn ³ 0

b) Forme standard d'un Programme Linéaire

On transforme les inégalités des contraintes économiques en égalités par introduction de variables supplémentaires positives ou nulles appelées variables d'écart.
ai1 x1  + ai2 x2 + .......... + ain xn £ bi    devient    ai1 x1  + ai2 x2 + .......... + ain xn + ti = bi
d'où la forme standard

Max z = c1 x1  +  c2 x2  + ..........+  cn xn
                  a11 x1  + a12 x2 + .......... + a1n xn  + t1 = b1
                  a21 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 ³ 0

c) Résolution

Afin de comparer avec la résolution graphique, nous pouvons considérer que nous sommes dans un espace à n dimensions (nombre de variables d'activité). Les contraintes délimitent un polyèdre convexe, région des solutions admissibles; la fonction objectif est un hyperplan que l'on va déplacer le plus loin possible de l'origine, jusqu'à l'extrême limite où il n'y aura plus qu'un point d'intersection (éventuellement un segment, un plan...) avec la région des solutions admissibles.
La solution se trouvant forcément sur le pourtour du polyèdre admissible, la méthode du simplexe consiste en itérations qui font passer d'un sommet du polyèdre à un autre en sélectionnant le sommet adjacent maximisant la fonction objectif.
Pour démarrer l'algorithme, il est nécessaire d'avoir une solution initiale. Dans le cas simple, l'origine est solution, c.à.d. que la première solution est x1 = 0 ;  x2 = 0 ;  .........;  xn = 0 ;  t1 = b1 ;  t2 = b2 ;  .........; tm = bm   (ceci suppose que les bi ne soient pas négatifs pour satisfaire les contraintes de signe)
L'algorithme, basé sur la méthode du pivot de Gauss pour la résolution des systèmes d'équations linéaires, est présenté sous forme de tableau.

Soit à résoudre le programme linéaire suivant sous sa forme canonique
         3 x1 + 4 x2 £ 160
         6 x1 + 3 x2 £ 180
Max  z = 1200 x1 + 1000 x2
         x1 ³ 0 ;  x2 ³ 0

* Forme standard
                      3 x1 +       4 x2 + 1 t1 + 0 t2 = 160
                      6 x1 +       3 x2 + 0 t1 + 1 t2 = 180
Max   z = 1200 x1 + 1000 x2 + 0 t1 + 0 t2
                     x1 ³ 0 ;  x2 ³ 0 ;  t1 ³ 0 ;  t2 ³ 0

* Tableau 0
en ne conservant que les coefficients des équations ci-dessus, on obtient le tableau de départ

HB B	x1	x2	t1	t2	C
t1	3	4	1	0	160
t2	6	3	0	1	180
D	1200	1000	0	0	0

Ce tableau nous donne la première solution admissible:
- Les variables Hors Base (HB) sont nulles: x1 = 0 ;  x2 = 0   (t1 et t2 en rouge ne sont pas hors base; elles ne sont présentes 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 et t2 =180
- La dernière cellule (intersection de C et D) donne la valeur de -z : -z = 0 donc z = 0
- La ligne D donne les valeurs marginales ou taux marginal de substitution; elles s'interprètent de la manière suivante: à ce stade de la solution, une augmentation de 1 unité de x1 ferait accroître la fonction objectif de 1200, et une augmentation de 1 unité de x2 ferait accroître la fonction objectif de 1000.

* Tableau 1
On augmente la fonction objectif en faisant entrer une variable dans la base, prenant la place d'une variable qui va sortir de la base.

 

Critère de sélection de la variable entrant dans la base: On sélectionne la variable HB ayant le plus grand coefficient positif dans la ligne D .

x1 entre donc dans la base

 

Pour sélectionner la variable sortant de la base, il est nécessaire 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 e pour effectuer le calcul de R
- Dans la colonne R on ne tient pas compte des valeurs négatives ou indéterminées

HB B	x1	x2	t1	t2	C	R
t1	3	4	1	0	160	160/3
t2	6	3	0	1	180	30
D	1200	1000	0	0	0

 

Critère de sélection de la variable sortant de la base: On sélectionne la variable dans la Base ayant le plus petit coefficient positif dans la colonne R .

t2 sort donc de la base

 

HB B x1  x2 t1  t2 C R  t1 3  4 1 0 160 160/3   t2 6 3 0 1 180 30   D 1200  1000 0 0 0	variable sortant
variable entrant

On appelle pivot (égal à 6) l'intersection de la variable entrante et de la variable sortante
Pour obtenir le tableau 1, on applique les règles suivantes:

 

- Le pivot est égal à 1 - Les coefficients de la ligne du pivot sont divisés par le pivot - Les coefficients de la colonne du pivot sont nuls - Les autres coefficients sont obtenus par la règle du rectangle

 

La règle du rectangle est la suivante:

Remarque importante: d = d' Û c b = 0 Û b = 0 ou c = 0
En conséquence, si dans la colonne (resp. ligne) du pivot il y a un 0, toute la ligne (resp. colonne) correspondante reste inchangée.

En appliquant ces règles on obtient le tableau 1:

HB B	x1	x2	t1	t2	C
t1	0	5/2	1	-1/2	70
x1	1	1/2	0	1/6	30
D	0	400	0	-200	-36000

Ce tableau nous donne la deuxième solution admissible:
- Les variables Hors Base (HB) sont nulles: x2 = 0 ;  t2 = 0   (x1 et t1 en rouge ne sont pas hors base; elles ne sont présentes 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 et x1 =30
- La dernière cellule (intersection de C et D) donne la valeur de -z : -z = -36000 donc z = 36000
- La ligne D donne les valeurs marginales ou taux marginal de substitution; elles s'interprètent de la manière suivante: à ce stade de la solution, une augmentation de 1 unité de x2 ferait accroître la fonction objectif de 400, et une augmentation de 1 unité de t2 ferait diminuer la fonction objectif de 200 (il est à noter qu'une augmentation de 1 unité de la variable d'écart t2 revient à diminuer le second membre de l'équation correspondante de 1 unité).

* Tableau 2:

HB B x1  x2 t1  t2 C  R  t1 0  5/2 1 -1/2 70  28  x1 1 1/2 0 1/6 30  60  D 0 400 0 -200 - 36000	variable sortant
variable entrant

d'où le tableau 2

HB B	x1	x2	t1	t2	C
x2	0	1	2/5	-1/5	28
x1	1	0	-1/5	4/15	16
D	0	0	-160	-120	- 47200

Ce tableau nous donne la troisième solution admissible:
- Les variables Hors Base (HB) sont nulles: t1 = 0 ;  t2 = 0   (x1 et x2 en rouge ne sont pas hors base; elles ne sont présentes 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 et x1 =16
- La dernière cellule (intersection de C et D) donne la valeur de -z : -z = - 47200 donc z = 47200
- La ligne D donne les valeurs marginales ou taux marginal de substitution; elles s'interprètent de la manière suivante: à ce stade de la solution, une augmentation de 1 unité de t1 ferait diminuer la fonction objectif de 160, et une augmentation de 1 unité de t2 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é).

 

Critère d'arrêt des itérations: Si tous les coefficients de la ligne D, relatifs aux variables HB, sont négatifs ou nuls, la solution trouvée 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 D et telle que tous les coefficients correspondants dans le tableau soient nuls ou négatifs, alors la solution est infinie.
- Si, à la fin des itérations, une variable est HB avec un coefficient nul dans la ligne D, alors on a une arête (plan,...) optimale. Les autres sommets solutions sont obtenus en faisant rentrer cette variable dans la base.

3) DUAL

A tout programme linéaire appelé PRIMAL correspond un programme linéaire appelé DUAL obtenu de la manière suivante:

 

PRIMAL	DUAL
m contraintes d'infériorité n variables d'activité m variables d'écart écriture en ligne	n contraintes de supériorité n variables d'écart m variables d'activité écriture en colonne

 

 

exemple

PRIMAL	DUAL
3 x1 +       4 x2 £ 160                     6 x1 +       3 x2 £ 180 Max z = 1200 x1 + 1000 x2 x1 ³ 0    ;   x2 ³ 0	3 y1 +     6 y2 ³ 1200                   4 y1 +     3 y2 ³ 1000 Min w = 160 y1 + 180 y2 y1 ³ 0    ;   y2 ³ 0

 

A l'optimum, le primal et le dual sont liés par les règles suivantes:
- les fonctions objectifs z et w ont la même valeur optimale
- la valeur marginale d'une variable dans un programme est égale à l'opposé de la valeur optimale de la variable associée dans l'autre programme et réciproquement.

 

exemple

PRIMAL	z = 47200  x1 x2 t1 t2  valeurs optimales  16 28 0 0  valeurs marginales  0 0 -160 -120
DUAL	w = 47200  u1 u2 y1 y2  valeurs optimales 0  0 160 120  valeurs marginales  -16 -28 0 0

 

VOIR LA SUITE EN RECHERCHE OPERATIONNELLE AVANCEE (SUITE 2) important svp