simplexe1

La methode du simplexe Les problemes a solution degeneree Les deux phases du simplexe

Recherche Operationnelle

Ecole Nationale de Commerce et de Gestion Casablanca


1 La methode du simplexe

2 Les problemes a solution degeneree

3 Les deux phases du simplexe


Idees de base

Idees de base

1 Solution optimale : sommet (point extreme).

2 Idee fondamentale du simplexe : deplacement de sommet ensommet adjacent de maniere a ameliorer la fonction objectif.

3 Transformation des inegalites en egalites : forme standard duprogramme lineaire- systeme de m equations a n inconnues (m < n).

4 Identification algebrique des sommets : correspondance avecles bases d’un systeme d’equations.

Solution de base

1 Systeme de m equations lineaires a n inconnues (m < n) :infinite de solutions.

2 Si on fixe a zero (n −m) variables : systeme de m equations am inconnues possedant une solution unique (si la matrice estinversible). C’est une solution de base.


Solution de base realisable

Solution de base

Une solution de base d’un programme lineaire est la solutionunique du systeme de m equations a m inconnues obtenu en fixanta zero (n −m) variables (pourvu que la matrice du systeme soitinversible).Les variables fixees a zero sont appelees variables hors base et lesautres variables en base.

Solution de base realisable

On appelle Solution de base realisable une solution de base quiverifie les contraintes de positivite, c.a.d dont toutes lescomposantes sont positives ou nulles.


Forme canonique

Definition

Un programme lineaire est sous forme canonique lorsque toutes sescontraintes sont des inegalites (par exemple ≤)et toutes sesvariables sont non-negatives.

Forme canonique du programme lineaire (PL) : Exemple(production de peinture)

max z = 5x1 + 4x2

s.c

6x1 + 4x2 ≤ 24x1 + 2x2 ≤ 6

x2 ≤ 2−x1 + x2 ≤ 1

x1, x2 ≥ 0


Forme standard

Exemple (production de peinture)

On introduit les variables d’ecarts s1, s2, s3, s4 dans PL pour obtenirune forme standard du programme lineaire

max z = 5x1 + 4x2

s.c

6x1 + 4x2 + s1 = 24x1 + 2x2 + s2 = 6

x2 + s3 = 2−x1 + x2 + s4 = 1

x1, x2, s1, s2, s3, s4 ≥ 0

Dans ce cas on a n = 6 inconnues et m = 4 equations.


Geometrie des solutions de base

Prenons la Base = {s1, s2, s3, s4} : x1 = 0, x2 = 0 =⇒ s1 = 24 ;s2 = 6 ; s3 = 2 ; s4 = 1. Cette solution de base realisablecorrespond au sommet A(0 ; 0). La solution de base realisableassociee au sommet B(0,1) est(x1, x2, s1, s2, s3, s4) = (0, 1, 20, 4, 1, 0). Les variables x1, s4 sonthors base et x2, s1, s2, s3 sont en base.

Theoreme

Toute solution de base realisable correspond a un sommet dupolyedre.


Determination de la solution de base optimale

1 Nombre maximum de solutions de base :Cnm = n!m!(n−m)!

2 Algorithme ”bete et mechan” : enumeration de toutes lesbases.

3 Methode du simplexe : partir d’une solution de baseadmissible et passer a une solution de base voisine quiameliore la valeur de l’objectif.

4 Solution voisine : changement d’une variable en base.5 3 etapes :

Determination de la variable entrante.Determination de la variable sortante.Pivotage.


Algorithme du simplexe

1 Mise sous forme canonique du probleme lineaire

2 Ajout des variables d’ecart puis ecrire le programme lineairesous forme strandard.

3 Choix de la base realisable de depart.Dans le cas des bi ≥ 0, on peut prendre la solution triviale debase realisable suivante :(x1, · · · , xn, s1, s2, · · · , sm) = (0, · · · , 0, b1, b2, · · · , bm).Variables hors base : (xi )1≤i≤n. Variables en base : (sj)1≤j≤m.

Forme standard du PL :max z = c1x1 + c2x2 + · · ·

s.c

a11x1 + a12x2 +... a1nxn +s1 = b1

a21x1 + a22x2 +... a2nxn +s2 = b2

... ... ... ... ....am1x1 + am2x2 +... amnxn +sm = bm

x1 · · · , xn, s1 · · · , sm ≥ 0;


Algorithme du simplexe : presentation en tableau

Forme standard du PL (production de peinture) :max z = 5x1 + 4x2

s.c 6x1 + 4x2 + s1 = 24x1 + 2x2 + s2 = 6x2 + s3 = 2−x1 + x2 + s4 = 1x1, x2, s1, s2, s3, s4 ≥ 0

On a bi ≥ 0; i = 1, · · · , 4, donc on peut prendre la solution de baserealisable (x1, x2, s1, s2, s3, s4) = (0, 0, 24, 6, 2, 1) comme point dedepart.Les variables hors base sont : x1 et x2

Les variables en base sont : s1, s2, s3, s4.

Il y a plusieurs manieres d’implementer l’algorithme du simplexe.La methode du tableau est l’une des plus efficaces.



Le premier tableau du simplexe est :

↓ var .base z x1 ↓ x2 s1 s2 s3 s4 sol θi

Lo |z −1 5 4 0 0 0 0 0

← L1|s1 0 (6) 4 1 0 0 0 24 4

L2|s2 0 1 2 0 1 0 0 6 6

L3|s3 0 0 1 0 0 1 0 2 −

L4|s4 0 −1 1 0 0 0 1 1 −

Comme il y a deux nombres positifs (5 et 4) dans la ligne Lo :(ligne des coefficients de la fonction objectif), la solution de baserealisable obtenue n’est pas optimale.On applique la procedure de determination de la variable entranteet celle sortante, on trouve :

1 x1 entre en base (plus grand coefficient positif de z ; ligne Lo)2 s1 sort de base (plus petit rapport positif de θi = bi

ai1)



Dans le premier tableau,le pivot est egal a 6 (indique entreparenthese).Pour calculer le second tableau du simplexe on applique latechnique de pivotage :Les lignes du nouveau tableau du simplexe sont donnees par :Lo = Lo − 5

6L1 = (5, 4, 0, 0, 0, 0, 0)− 56 (6, 4, 1, 0, 0, 0, 24) = (...)

L1 = 16L1 = 1

6 (6, 4, 1, 0, 0, 0, 24) = (1, 4/6, 1/6, 0, 0, 0, 4)L2 = L2 − 1

6L1 = (1, 2, 0, 1, 0, 0, 6)− 16 (6, 4, 1, 0, 0, 0, 24) = (...)

L3 = L3 − 06L1 = (0, 1, 0, 0, 1, 0, 2)

L4 = L4 − −16 L1 = (−1, 1, 0, 0, 0, 1, 1) + 1

6 (6, 4, 1, 0, 0, 0, 24) = (...)


Simplexe du tableau

Le second tableau du simplexe est :

↓ var .base z x1 ↓ x2 s1 s2 s3 s4 sol θi

Lo |z −1 0 23 −5

6 0 0 0 −20

L1|x1 0 1 23

16 0 0 0 4 6

← L2|s2 0 0 ( 43 ) −1

6 1 0 0 2 32

L3|s3 0 0 1 0 0 1 0 2 2

L4|s4 0 0 53

16 0 0 1 5 3

Comme il ya un nombre strictement positif (2/3) dans la ligne Lo ,la solution de base realisable obtenue n’est pas optimale.On applique la procedure de determination de la variable entranteet celle sortante, on a :

1 x2 entre en base (plus grand coefficient positif de z ; ligne Lo)

2 s2 sort de base (plus petit rapport positif de θi = biai2

)


Simplexe du tableau

Dans le second tableau du simplexe,le pivot est egal a 43 indique

entre parenthese. Pour calculer le troisieme tableau du simplexe onapplique la technique de pivotage :Les lignes du nouveau tableau du simplexe sont donnees par :

Lo = Lo −2343

L2 = (0, 23 ,

−56 , 0, 0, 0,−20)− 1

2 (0, 43 ,

−16 , 1, 0, 0, 2)

L1 = L1 −2343

L2 = (1, 23 ,

16 , 0, 0, 0, 4)− 1

2 (0, 43 ,

−16 , 1, 0, 0, 2)

L2 = 143

L2 = (0, 1, −18 ,

34 , 0, 0,

32 )

L3 = L3 − 143

L2 = (0, 1, 0, 0, 1, 0, 2)− 34 (0, 4

3 ,−16 , 1, 0, 0, 2)

L4 = L4 −5343

L2 = (0, 53 ,

16 , 0, 0, 1, 5)− 5

4 (0, 43 ,

−16 , 1, 0, 0, 2)


Simplexe du tableau

Le dernier tableau du simplexe est :

↓ v .base z x1 x2 s1 s2 s3 s4 sol

Lo |z −1 0 0 −34 −1

2 0 0 −21

L1|x1 0 1 0 14 −1

2 0 0 3

L2|x2 0 0 1 −16 1 0 0 3

2

L3|s3 0 0 0 0 0 1 0 12

L4|s4 0 0 0 0 0 0 1 52

Comme tous les nombres de la ligne Lo sont negatifs ou nuls, lasolution de base realisable obtenue(x1, x2, s1, s2, s3, s4) = (3, 3

2 , 0, 0,12 ,

52 ) est optimale.

La solution optimale est donc la suivante : (x1, x2) = (3, 32 ) et la

valeur maximale de la fonction objecftif est max z = 21.On a utilise toutes les matieres premieres M1, M2 (s1 = 0, s2 = 0)


Algorithe du simplexe : resume

DebutTant que qu’il existe un coefficient strictement positifdans la fonction objectif fairedebut

choisir la variable entrante dans la base : c’est la variableassociee au plus grand coefficit ce > 0.Si tous les aie ≤ 0 (les valeurs dans la colonne de lavariable entrante) STOPle probleme est non borne( max z = +∞)Sinon

Choisir la variable sortante xs telle quebsase

= min{ biaie, aie > 0, i = 1, · · · ,m}

PivotageFin debutFin Tant queSi tous les ci ≤ 0, la solution optimale est trouvee.

Fin debut


Les problemes a solution degeneree

Graphiquement, on appelle solution degeneree le point ou plusieurscontraintes concourent (un nombre superieur ou egale a troiscontraintes).Un programme lineaire est dit degeneree si une ou plusieursvariables dans la base optimale sont nulles.Ce probleme peut causer des difficultes pour l’algorithme dusimplexe (divergence), on parle d’un eventuel cyclage del’algorithme : On retrouve une base deja rencontree et on boucleindefiniment

Differentes methodes permettent d’eviter le cyclage : regle deBland, methode lexicographique, methode de perturbation. Lamethode de Bland est l’une des plus employees.La regle de Bland (1977) s’enonce de la facon suivante : Lorsque

plusieurs variables sont susceptibles d’entrer ou de sortir de la base,on choisit toujours celle qui a l’indice (le rang) le plus petit.


Les problemes a solution degeneree : exemple

On veut resoudre le PL suivant par la methode du simplexe :

max z = 5x1 + 3x2

s.c

4x1 + 2x2 ≥ 64x1 + x2 ≥ 10x1 + x2 ≤ 4

x1, x2 ≥ 0

On introduit les variables d’ecart s1, s2, s3 ≥ 0 ce qui conduit a :

max z = 5x1 + 3x2

s.c

4x1 + 2x2 + s1 = 124x1 + x2 + s2 = 10x1 + x2 + s3 = 4

x1, x2, s1, s2, s3 ≥ 0



On a bi ≥ 0; i = 1, · · · , 3. La solution de base realisable de depart :(x1, x2, s1, s2, s3) = (0, 0, 12, 10, 4)Les variales hors base sont : x1 et x2. Les variables en base sont :s1, s2, s3.

↓ base z x1 ↓ x2 s1 s2 s3 bi θi

Lo |z −1 5 3 0 0 0 0

L1|s1 0 4 2 1 0 0 12 3

← L2|s2 0 (4) 1 0 1 0 10 52

L3|s3 0 1 1 0 0 1 4 4

On applique la technique de pivotage et on obtient le secondtableau du simplexe



Il y a une seule variable condidate pour entrer en base : x2

↓ base z x1 ↓ x2 s1 s2 s3 bi θi

Lo |z −1 0 74 0 −5

4 0 −252

L1|s1 0 0 1 1 −1 0 2 2?

L2|x1 0 1 14 0 1

4 1 52 10

L3|s3 0 0 34 0 −1

4 1 32 2?

Les variables condidates de sortir de la base sont s1 et s3 : choisircomme variable sortante celle de plus petit indice, ici c’est s1



Il y a une seule variable condidate pour entrer en base : s2

↓ base z x1 x2 s1 ↓ s2 s3 bi θi

Lo |z −1 0 0 −74

12 0 −16

L1|x2 0 0 1 1 −1 0 2 −

L2|x1 0 1 0 −14

12 0 2 4

← L3|s3 0 0 0 −34

12 1 0 0

La variable condidate de sortir de la base est s3



↓ base z x1 x2 s1 s2 s3 sol

Lo |z −1 0 0 −1 0 −1 −16

L1|x2 0 0 1 −12 0 2 2

L2|x1 0 1 0 12 0 −1 2

L3|s3 0 0 0 −32 1 2 0

On remarque que tous les nombres de la ligne Lo sont negatifs ounuls. La solution optimale est donc trouvee et donnee par(x1, x2) = (2, 2) et la valeur maximale de la fonction objectif estmax z = 16.


Les deux phases du simplexe : methode en deux phases

1 Une solution de base admissible n’est pas toujours connue apriori.

2 Certains problemes n’admettent pas de solution admissible,donc il est impossible de trouver une base de depart.

3 La methode des deux phases va permettre de determinerune base admissible ou prouver que le probleme estimpossible.

L’astuce de la methode en deux phases consiste a ajouter desvariables de base �artificielles� dans les equations ou il n’y aaucune variable candidate naturelle.



DebutMettre les contraintes sous forme d’egalites ;Rendre positif le second membre des contraintes ;Introduire les variables artificielles ai dans les contraintes :n∑

j=1

aijxj + ai = bi , xj , ai ≥ 0

Sous ces contraintes, resoudre le PL auxiliaire : max(z) = −m∑i=1

ai

Si pour tout i ∈ {1, ...,m}, ai = 0⇔ max z = 0Alors Resoudre le PL initial en prenant comme solution de base

de depart la solution obtenue a l’issue de la premiere phaseSinon Il n’y a pas de solution relisable

Fin.

Proposition : Un (PL) admet une solution realisable si et seulementsi le probleme auxiliaire (PLA) admet une solution de baseoptimale avec ai = 0, i = 1, · · · ,m.



A la fin de la phase I :

1 si la valeur optimale max z de la fonction economique estnegative (i.e., max z < 0), alors le probleme original n’est pasrealisable

2 si la valeur optimale max z de la fonction economique estnulle i.e., le probleme original est realisable. Dans ce cas, laresolution du probleme original avec l’algorithme du simplexese poursuit en utilisant l’information du dernier tableau de laphase I.

La phase II reprendra l’objectif original. Le tableau de la phase IIs’obtient en modifiant le dernier tableau de la phase I de la faconsuivante :

On raye les variables artificielles ;

On exprime la fonction-objectif z en fonction des variableshors base du dernier tableau de la phase I, en excluant lesvariables artificielles


methode en deux phases ; exemple

On veut resoudre le PL suivant :

max z = 5x1 + 7x2

s.c

x1 + x2 ≥ 6x1 + ≥ 4

x2 ≤ 3x1, x2 ≥ 0

On introduit les variables d’ecart s1, s2, s3 ≥ 0 ce qui conduit a :

max z = 5x1 + 7x2

s.c

x1 + x2 − s1 = 6x1 + − s2 = 4

x2 + s3 = 3x1, x2, s1, s2, s3 ≥ 0



Les deux premieres equations necessitent l’introduction de deuxvariables artificielles a1, a2, on obtient le programme lineaireauxiliaire (PLA) :max z = −a1 − a2

s.c

x1 + x2 − s1 + a1 = 6x1 + − s2 + a2 = 4

x2 + s3 = 3x1, x2, s1, s2, s3, a1, a2 ≥ 0

Remarque : max z = −a1 − a2 = 0⇐⇒ a1 = 0, a2 = 0Tres important : il faut veiller a ce que la fonction objectif soitexprimee en fonction des variables hors-base. C’est une regle quidoit toujours etre verifiee : A tous les stades de la methode dusimplexe, la fonction objectif et les variables de base doivent etreexprimees en fonction des variables hors-base.



La solution de base realisable de depart pour PLA est :(x1, x2, s1, s2, s3, a1, a2) = (0, 0, 0, 0, 3, 6, 4)Les variales hors base sont : x1, x2, s1, s2. Les variables en basesont : s3, a1, a2.On doit exprimer les variables a1 et a2 en fonction de x1, x2, s1, s2

et les remplacer dans la fonction objectif. On a :−a1 = −x1 − x2 + s1 + 6−a2 = −x1 + s2 + 4D’ou−a1 − a2 = −2x1 − x2 + s1 + s2 + 10Maintenant, la methode du simplexe s’applique sans problemes :



Premiere phase :Le premier tableau du phase I :

↓ base z x1 ↓ x2 s1 s2 s3 a1 a2 bi

Lo |z −1 2 1 −1 −1 0 0 0 10

L1|a1 0 1 1 −1 0 0 1 0 6

← L2|a2 0 (1) 0 0 −1 0 0 1 4

L3|s3 0 0 1 0 0 1 0 0 3

x1 entre en base et a2 sort de la base, on elimine a2 du probleme.On applique la technique de pivotage et on obtient le secondtableau du phase I



Le second tableau du phase I :

↓ base z x1 x2 ↓ s1 s2 s3 a1 bi

Lo |z −1 0 1 −1 1 0 0 2

← L1|a1 0 0 (1) −1 1 0 1 2

L2|x1 0 1 0 0 −1 0 0 4

L3|s3 0 0 1 0 0 1 0 3

a1 sort et x2 entre en base, on elimine a1.On applique la technique de pivotage et on obtient le troisiemetableau du phase I.



↓ base z x1 x2 s1 s2 s3 bi

Lo |z 0 0 0 0 0 0 0

L1|x2 0 0 1 −1 1 0 2

L2|x1 0 1 0 0 −1 0 4

L3|s3 0 0 0 1 −1 1 1

la premiere phase est achevee puisque ci = 0, i = 1, · · · , 5.Une solution de base realisable est donc :x = (x1, x2, s1, s2, s3) = (4, 2, 0, 0, 1).Dans le dernier tableau, les deux variables ajoutees a1 et a2 sontsorties de la base. Donc a1 = 0 et a2 = 0, ce qui etait l’objectif. Ona donc trouve un point de depart pour resoudre le probleme original



Deuxieme phase :Le PL se formule sous la forme equivalente suivante :

max z = 5x1 + 7x2

s.c

x2 − s1 + s2 = 2x1 − s2 = 4

s1 − s2 + s3 = 1x1, x2, s1, s2, s3 ≥ 0

La solution de base realisable trouvee en phase I est :x = (x1, x2, s1, s2, s3) = (4, 2, 0, 0, 1). Les variables x1, x2, s3 sonten base et les variables s1, s2 sont hors base.On doit exprimer les variables x1 et x2 en fonction de s1, s2 et lesremplacer dans la fonction objectif. On a :5x1 = 5(4 + s2)7a2 = 7(2 + s1 − s2)D’ou5x1 + 7x2 = 34 + 7s1 − 2s2

Maintenant, la methode du simplexe s’applique sans problemes :



↓ base z x1 x2 s1 ↓ s2 s3 bi

Lo z −1 0 0 7 −2 0 −34

L1 x2 0 0 1 −1 1 0 2

L2 x1 0 1 0 0 −1 0 4

L3 s3 0 0 0 (1) −1 1 1

s1 entre en base et s3 sort de base.



↓ base z x1 x2 s1 s2 s3 bi

Lo z −1 0 0 0 5 −7 −41

L1 x2 0 0 1 0 0 1 3

L2 x1 0 1 0 0 −1 0 4

L3 s1 0 0 0 1 −1 1 1

La colonne de s2 ne comporte que des nombres ≤ 0, le problemeest donc non borne

Documents

simplexe1