PROGRAMMATION LINEAIRE   FORME USUELLE D'UN PL   FORME NON USUELLE D'UN PL   METHODE DES PENALITES   METHODE DES DEUX PHASES

1) FORME USUELLE D'UN PROGRAMME LINEAIRE

 Considérons la forme usuelle d'un Programme Linéaire:

Max ou Min 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

La résolution du problème à Maximum a été vue précédemment. La résolution du problème à Minimum ne pose pas de difficulté; il suffit, dans le critère de sélection de la variable entrant dans la base, de remplacer "plus grand coefficient positif "par "plus grand coefficient négatif" et dans le critère d'arrêt des itérations de remplacer "coefficients négatifs ou nuls " par "coefficients positifs ou nuls".

2) FORME NON USUELLE D'UN PROGRAMME LINEAIRE

La résolution du problème précédent nécessite les assertions suivantes:

• Les seconds membres sont non-négatifs: bi ³ 0   (nécessaire pour avoir une solution initiale)
• Les variables d'activité sont non-négatives : xi ³ 0
• Les contraintes sont de type " £ "

Que peut-on faire lorsque ces conditions ne sont pas respectées?

a) Un second membre est négatif

Il suffit de multiplier la contrainte par -1. Ceci a pour effet de changer le sens de l'inégalité [voir c)]

b) Une variable d'activité n'est pas contrainte à la non-négativité

Tout nombre, positif ou négatif, peut toujours être écrit comme la différence de deux nombres non-négatifs (par exemple, - 4 = 6 - 10). Il suffit donc de remplacer la variable d'activité par la différence de deux nouvelles variables d'activité non-négatives (le nombre de variables d'activité augmente de 1).

c) Une contrainte n'est pas du type " £ "

Nous distinguons deux cas: la contrainte est du type " ³ " ou du type " = "

- Contrainte du type " ³ "
Il suffit de rajouter une variable d'écart non-négative
ai1 x1  + ai2 x2 + .......... + ain xn ³ bi    devient    ai1 x1  + ai2 x2 + .......... + ain xn - ti = bi
Il est à noter qu'il n'y a plus de solution initiale évidente: en effet pour x1 = 0 ; x2 = 0 ;  .........; xn = 0,  ti = -bi, ce qui n'est pas une solution admissible car ti doit être non-négative. Tout se passe comme si cette variable d'écart était une variable d'activité et que nous étions en présence d'une contrainte de type " = " que nous allons traiter maintenant.

- Contrainte du type " = "
Dans le cas usuel les variables d'écart introduites étaient représentatives des contraintes. Suivant le même principe, nous rajoutons une variable non-négative, dite variable artificielle, qui sera représentative de la contrainte dans la base.
ai1 x1  + ai2 x2 + .......... + ain xn = bi    devient    ai1 x1  + ai2 x2 + .......... + ain xn + ei = bi
Il est clair que pour que la contrainte d'égalité soit respectée il faut que ei = 0. La solution initiale étant x1 = 0 ; x2 = 0 ;  .........; xn = 0,  ei = bi, l'algorithme doit permettre de mettre hors base cette variable artificielle afin qu'elle soit nulle lorqu'on atteindra la solution optimale. Si ceci n'est pas possible, le problème n'aura alors pas de solution.

Exemple de forme non-usuelle

      (1)       3 x1  + 4 x2  - 2 x3 £ 10
      (2)       6 x1  + 3 x2 + 5 x3 = 20
      (3)      -2 x1 + 5 x2  - 4 x3 £ -5
        (4)      x1 ³ 0 ;  x3 ³ 0
Max  z = 12 x1 + 10 x2 + 8 x3

(1) On rajoute une variable d'écart t1
    3 x1 + 4 x2 - 2 x3 + t1 = 10
(2) On rajoute une variable artificielle e2
    6 x1 + 3 x2 + 5 x3 + e2 = 20
(3) On multiplie par -1
       2 x1 - 5 x2 + 4 x3 ³ 5
     On rajoute une variable d'écart t3 et une variable artificielle e3
      2 x1 - 5 x2 + 4 x3 - t3 + e3 = 5
(4) x2 n'est pas contrainte à la non-négativité
     x2 = x'2 - x''2

Finalement le problème se ramène à la forme standard suivante
3 x1 + 4 x'2 - 4 x''2 - 2 x3 + t1 = 10
6 x1 + 3 x'2 - 3 x''2 + 5 x3 + e2 = 20
2 x1 - 5 x2 + 5 x''2 + 4 x3 - t3 + e3 = 5
x1 ³ 0;  x'2 ³ 0;  x''2 ³ 0;  x3 ³ 0;  t1 ³ 0;  t3 ³ 0;  e2 ³ 0;  e3 ³ 0
Max  z = 12 x1 + 10 x'2 - 10 x''2 + 8 x3

3) METHODE DES PENALITES ( ou du grand M)

Cette méthode permet de tenir compte des variables artificielles. On les pénalise en leur affectant un coefficient de valeur très élevée dans la fonction économique (- M pour un problème à maximum, + M pour un problème à minimum). Les pénalités ont pour objet de provoquer l'élimination des variables artificielles au fil des itérations. Normalement, à l'optimum (s'il existe) les variables artificielles sont hors base. Si celles-ci sont à l'optimum dans la base, avec une valeur non nulle, le programme n'a pas de solution.

Soit à résoudre le programme linéaire suivant sous sa forme canonique
         5 x1 + 6 x2 ³ 10
         2 x1 + 7 x2 ³ 14
Min  z = 3 x1 + 10 x2
         x1 ³ 0 ;  x2 ³ 0

* Forme standard
               5 x1 +   6 x2 - 1 t1 + 0 t2 +  1 e1   +  0 e2 = 10
               2 x1 +   7 x2 + 0 t1  - 1 t2 +  0 e1  +  1 e2 = 14
Min   z = 3 x1 + 10 x2 + 0 t1 + 0 t2 + M e1 + M e2
                     x1 ³ 0 ;  x2 ³ 0 ;  t1 ³ 0 ;  t2 ³ 0;  e1 ³ 0 ;  e2 ³ 0

* Tableau 0

HB B	x1	x2	t1	t2	e1	e2	C
e1	5	6	-1	0	1	0	10
e2	2	7	0	-1	0	1	14
D'	3	10	0	0	M	M	0

La ligne D' donne les coefficients de la fonction économique, mais pas les valeurs marginales des variables HB; de plus les variables artificielles sont dans la base et devraient donc avoir des valeurs marginales nulles.
De manière générale, dans tout tableau du simplexe, si on note ck les coefficients de la fonction économique et aik les coefficients du tableau,
* les valeurs marginales mj sont
     - nulles pour les variables dans la base
     - égales à cj - S aik ck  pour les variables hors base, la sommation étant faite sur toutes les variables de la base (les lignes du tableau)
* la valeur de la fonction économique est égale à - S aik ck

d'où le tableau 0 (les calculs annexes ont été rajoutés)

cj

3

10

0

0

M

M

aik ck

HB B

x1

x2

t1

t2

e1

e2

C

ck

x1

x2

t1

t2

C

e1

5

6

-1

0

1

0

10

M

5M

6M

-M

0

10M

e2

2

7

0

-1

0

1

14

M

2M

7M

0

-M

14M

D

3-7M

10-13M

M

M

0

0

-24 M

S aik ck

7M

13M

-M

-M

24M

* Tableau 1
Puisqu'on recherche un minimum, la variable entrante est celle qui a le plus grand coefficient négatif, c.à.d. x2. En fait il suffit de regarder le coefficient de M car M est très grand; le coefficient indépendant de M n'intervient que dans le cas où plusieurs variables ont le même coefficient pour M.

HB B x1  x2 t1  t2 e1  e2 C  R  e1 5  6 -1 0 1 0 10 5/3   e2 2 7 0 -1 0 1 14 2   D 3-7M 10-13M M M 0 0  -24M	variable sortant
variable entrant

la variable artificielle sortant de la base, va se trouver dans la ligne D avec un fort coefficient positif et ne pourra donc plus y entrer; on peut donc supprimer la colonne correspondante dans la suite des itérations, d'où le tableau 1

HB B	x1	x2	t1	t2		e2	C
x2	5/6	1	-1/6	0		0	5/3
e2	-23/6	0	7/6	-1		1	7/3
D	-16/3+(23/6)M	0	5/3-(7/6)M	M		0	-50/3-(7/3)M

* Tableau 2

HB B x1  x2 t1  t2    e2 C  R  x2 5/6  1 -1/6 0   0 5/3 -10   e2 -23/6 0 7/6 -1   1 7/3 2   D -16/3+(23/6)M 0 5/3-(7/6)M M   0  -50/3-(7/3)M	variable sortant
variable entrant

d'où le tableau 2

HB B	x1	x2	t1	t2			C
x2	6/21	1	0	-1/7			2
t1	-23/7	0	1	-6/7			2
D	1/7	0	0	30/21			-20

On a atteint la solution optimale qui est   x1 = 0; x2 = 2; t1 = 2; t2 = 0; z = 20.

Remarque: dans le cas particulier de cet exemple qui était sous forme standard, il aurait été plus rapide de traiter le problème dual et d'en déduire la solution du problème primal initial.

VOIR LA METHODE DES DEUX PHASES EN RECHERCHE OPERATIONNELLE SUITE 3 IPORTANT SVP