1) 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

      

* 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) (situées sur la première ligne du tableau) 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; lorsqu'on travaille sur papier, il est préférable d'indiquer la position de ces variables par des points pour bien montrer que seules x1 et x2 sont hors base). Cela signifie qu'on fabrique 0 pièces P1 et 0 pièces P2.
- Les valeurs des variables dans la Base (B) (apparaissant dans la première colonne) se lisent dans la colonne C:  t1 = 160 et t2 =180. Cela signifie qu'il reste 160 heures d'utilisation possible de l'atelier A1 et 180 heures de l'atelier A2.
- La dernière cellule (intersection de C et D) donne la valeur de -z : -z = 0 donc z = 0. Cela signifie que la marge est égale à 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 croître la fonction objectif de 1200, et une augmentation de 1 unité de x2 ferait croître la fonction objectif de 1000. Cela signifie qu'à ce stade de la production si on augmente la production de 1 pièce de P1, la marge va augmenter de 1200 F et si on augmente la production de 1 pièce de P2, la marge va augmenter de 1000 F.

En effet, la solution actuelle est x1 = 0 ; x2 = 0 ; t1 = 160 ; t2 =180    
et    z =1200 . x1 + 1000 . x2 + 0 . t1 + 0 . t2 = 1200 . 0 + 1000 . 0 + 0 . 160 + 0 . 180 = 0
Si on augmente x1 de 1 unité,
 z =1200 . 1 + 1000 . 0 + 0 . 0 . 160 + 0 . 180 = 1200
Si on augmente x2 de 1 unité,
 z =1200 . 0 + 1000 . 1 + 0 . 0 . 160 + 0 . 180 = 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.

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)

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

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:

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). Cela signifie qu'on fabrique 0 pièces P2 et qu'il reste 0 heure d'utilisation disponible à l'atelier A2. La contrainte associée à t2 est dite saturée.
- Les valeurs des variables dans la Base (B) se lisent dans la colonne C:  t1 = 70 et x1 =30. Cela signifie qu'on fabrique 30 pièces P1 et qu'il reste 70 heures d'utilisation disponible à l'atelier A1.
- La dernière cellule (intersection de C et D) donne la valeur de -z : -z = -36000 donc z = 36000. Cela signifie que la marge est égale à 36000 F.
- 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 croî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é).Cela signifie qu'à ce stade de la production si on augmente la production de 1 pièce de P2, la marge va augmenter de 400 F et si on diminue la disponibilité de 1 heure à l'atelier A2, la marge va diminuer de 200 F.

En effet, la solution actuelle est x1 = 30 ; x2 = 0 ; t1 = 70 ; t2 =0    
et    z =1200 . x1 + 1000 . x2 + 0 . t1 + 0 . t2 = 1200 . 30 + 1000 . 0 + 0 . 70 + 0 . 0 = 36000
Si on augmente x1 de 1 unité, on ne peut garder x1 = 30 car la 2° contrainte 6 x1 + 3 x2 + 0 t1 + 1 t2 = 180 est saturée. On doit donc déterminer la valeur de x1 permettant d'augmenter x2 de 1 unité:
6 . x1 + 3 . 1 + 0 . 70 + 1 . 0 = 180 Û 6 x1 + 3 = 180 Û x1 = 29,5
d'où   z =1200 . 29,5 + 1000 . 1 + 0 . 70 + 0 . 0 = 36400, c.à.d. une augmentation de 400 F par rapport à la solution précédente.
Si on augmente t2 de 1 unité, la contrainte   6 x1 + 3 x2 + 0 t1 + 1 t2 = 180  devient  6 . x1 + 3 . x2 + 0 . 70 + 1 . 1 = 180
ou encore  6 x1 + 3 x2 = 179;  on a donc bien 1 heure de disponibilité en moins à l'atelier A2.
De plus puisque x2 = 0, on aura x1 = 179/6 au lieu de 30
d'où  z =1200 . 179/6 + 1000 . 1 + 0 . 70 + 0 . 1 = 35800, ce qui correspond à une baisse de 200 F.

* 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). Cela signifie qu'il reste 0 heure d'utilisation disponible aux ateliers A1 et A2. Les contraintes associées à t1 et t2 sont saturées.
- Les valeurs des variables dans la Base (B) se lisent dans la colonne C:  x2 = 28 et x1 =16. Cela signifie qu'on fabrique 16 pièces P1 et 28 pièces P2.
- La dernière cellule (intersection de C et D) donne la valeur de -z : -z = - 47200 donc z = 47200. Cela signifie que la marge est égale à 47200 F.
- 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é).

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.

Interprétation graphique de la méthode du simplexe:
Les différentes solutions obtenues à chaque tableau correspondent respectivement aux sommets O (x1 = 0 ; x2 = 0), A (x1 = 30 ; x2 = 0), B (x1 = 16 ; x2 = 28) du graphique. On a cheminé sur le pourtour du polyèdre des solutions admissibles, en sélectionnant parmi tous les sommets possibles celui donnant la valeur maximale à la fonction objectif.

2) DUAL

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

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.

Noter qu'aux 2 variables d'activité x1 et x2 du Primal sont associées 2 contraintes et donc 2 variables d'écart u1 et u2 dans le Dual. De même aux 2 contraintes du Primal auxquelles correspondent 2 variables d'écart t1 et t2, sont associées 2 variables d'activité y1 et y2 dans le Dual.

Le programme dual peut quelque fois apporter des interprétations économiques interessantes. D'un point de vue mathématique, il peut permettre de résoudre certains problèmes de minimisation.