Introduction à la Recherche Opérationnelle

Introduction à la

Recherche Opérationnelle

• ALGORITHME DE SIMPLEXE À L’AIDE DES VARIABLES

ARTIFICIELLES

• M-MÉTHODES

• SIMPLEXE EN 2 PHASES

Cours : Introduction à la Recherche Opérationnelle

ALGORITHME DE SIMPLEXE / VARIABLES ARTIFICIELLES

• En regardant la forme canonique d’un PL, nous remarquons dans lescontraintes l’existence des inégalités d’infériorités ‘ ≤ ’ et desvariables de décisions non négatives.

• Souvent, on commence simplexe au sommet x = (0, 0, …,0) quiappartient à l’espace de solution réalisable.

• Si la forme canonique n’est pas respectée et s’il existe unecontrainte de supériorité ‘ ≥ ’ on remarque ce qui suit :

• En premier temps, pour atteindre la forme standard:

– ajouter des variables d’écart non négatives.

– Puisqu’on a une inégalité ‘ ≥ ’, ces variables d’écart sont d’un signenégatif.

15/10/2019 16:03 2



• Ex 1: x1 + 3x2 ≥ 4 (x1, x2 ≥ 0)

Devient : x1 + 3x2 – t1 = 4 (x1, x2,t1 ≥ 0)

Si on souhaite initier l’algorithme de simplexe à l’origine (0,0) :

– t1 = 4 càd t1 = –4

Contradiction avec la contrainte de non négativité de t1

• Conclusion : le point origine X = (0,0,…,0) ne peut pas appartenir àl’espace de solution réalisable,

Lancement de l’algorithme avec une solution artificielle.

• Résultat : introduction aux équation(s) semblables, des variable(s)dites artificielle(s) pour contourner le problème.

15/10/2019 16:03 3



• Dans L’Ex 1, on passe de : x1 + 3x2 ≥ 4 (x1, x2 ≥ 0)

• à : x1 + 3x2 – t1 + v1 = 4 (x1, x2, t1, v1 ≥ 0) où v1 est la variableartificielle.

• Pour résoudre le nouveau PL, deux méthodes étroitement liées sontles plus citées dans la littérature:

M-Méthodes

simplexe en 2-Phases.

15/10/2019 16:03 4


ALGORITHME DE SIMPLEXE / V.A: M-MÉTHODES

• Appelées aussi Méthodes des grands M

• Après avoir inséré les variables artificielles dans la partie descontraintes, il faut modifier la fonction objectif de la manièresuivante :

• Etant donnée une valeur M très grande (M +∞), on ajoute à lafonction objectif les variables artificielles avec des coefficients –M,si le PL est un problème de maximisation et avec des coefficients M(+M) si le PL est un problème de minimisation et on résout lenouveau PL.

• IN FINE: Si la solution finale contient des variables artificielles nonnulles, alors le problème initial n’a pas de solution.

15/10/2019 16:03 5



• Exemple: PLVA1

Min x1 + x2

Sc2x1 + x2 ≥ 125x1 + 8x2 ≥ 74x1 + 6x2 ≥ 24x1 , x2 ≥ 0

après insertion des variables d’écart et des variables artificielles, le PLdevient:

Min Z = x1 + x2 + MA1 + MA2+ MA3

Sc2x1 + x2 - S1 + A1 = 125x1 + 8x2 - S2 + A2 = 74x1 + 6x2 - S3 + A3 = 24x1 , x2 , S1 , S2 , S3 , A1 , A2 ≥ 0

15/10/2019 16:03 6

Cours : Introduction à la Recherche Opérationnelle15/10/2019 16:03 7



15/10/2019 16:03 8

• Le tableau initial de simplexe devient (après remplacement desexpressions des Ai dans la fonction objectif)

• Relatif au sommet artificiel (0,0)

• Pb de minimisation, on choisit le coefficient négatif qui a la plus grandevaleur absolue : 1-15M (puisque M est très grand).

Iter 0 x1 x2 S1 S2 S3 A1 A2 A3

A1 2 1 -1 0 0 1 0 0 12

A2 5 8 0 -1 0 0 1 0 74

A3 1 6 0 0 -1 0 0 1 24

Z ’ 1 1 0 0 0 M M M 0

Z 1-8M 1-15M M M M 0 0 0 110M



15/10/2019 16:03 9

• Relatif au sommet artificiel (0,4)

• intersection des droites relatives aux contraintes x1 ≥ 0 et x1 + 6x2 ≥ 24


A1 11/6 0 -1 0 1/6 1 0 -1/6 8

A2 22/6 0 0 -1 4/3 0 1 -4/3 42

x2 1/6 1 0 0 -1/6 0 0 1/6 4

Z (5-33M)/6 0 M M (1-9M)/6 0 0 (15M-1)/6 4+50M



15/10/2019 16:03 10

• l’Itération 2 correspond au sommet artificiel (48/11 , 36/11) intersection des droites relatives aux contraintes 2x1 + x2 ≥ 12 et x1 + 6x2 ≥ 24


x1 1 0 -6/11 0 1/11 6/11 0 -1/11 48/11

A2 0 0 2 -1 1 -2 1 -1 26

x2 0 1 1/11 0 -2/11 -1/11 0 6/33 36/11

Z 0 0 5/11 -2M M -M + 1/11 3M-5/11 0 2M-1/11 84/11+26M



15/10/2019 16:03 11

• l’Itération 3 correspond au sommet réel (126/11 , 23/11) intersection des

droites relatives aux contraintes 5x1 + 8x2 ≥ 74 et x1 + 6x2 ≥ 24

Iter 3 x1 x2 S1 S2 S3

x1 1 0 0 -3/11 4/11 126/11

S1 0 0 1 -1/2 1/2 13

x2 0 1 0 1/22 -5/22 23/11

Z 0 0 0 5/22 -3/22 149/11



15/10/2019 16:03 12

• Remarques

Les sommets correspondants aux itérations 0,1 et 2 sont des sommetsartificiels (qui n’appartiennent pas à l’espace de solution).

Les tableaux correspondants auxdites itérations contiennent desvariables artificielles dans les variables de bases.

Le sommet correspondant à l’itération 4 est un sommet réel quiappartient à l’espace de solution (disparition de toutes les variablesartificielles de la base).



15/10/2019 16:03 13

• Pas de coefficient non positif pour les variables hors base (Puisque on estdevant un problème de minimisation)

• d’où l’itération actuelle est finale et la solution optimale est atteinte via lescoordonnées (2,8) et sa valeur est 10.

• Cette méthode entraine des erreurs d’arrondi lors de son automatisation.

Iter 5 x1 x2 S1 S2 S3

x1 1 0 -8/11 1/11 0 2

S3 0 0 2 -1 1 26

x2 0 1 5/11 -2/11 0 8

Z 0 0 3/11 1/11 0 10


ALGORITHME DE SIMPLEXE / V.A: MÉTHODE 2 PHASES

• Cette méthode, remédie au problème des erreurs d’arrondientrainées par les calculs de la M-Méthode.

• Après avoir inséré les variables artificielles (non négatives) dans lapartie des contraintes, on résout le PL en 2 phases:

15/10/2019 16:03 14



• Phase 1 (PL1) : consiste à trouver un sommet artificiel delancement pour la phase initiale du simplexe (puisque le pointorigine (0,0) n'est pas un sommet réel: n’est pas une solutionréalisable).

• La partie des contraintes est la même qui contient éventuellementles variables artificielles (et les variables d’écart aussi).

• Quant à la fonction objectif elle représente la minimisation de lasomme des variables artificielles insérées :

• Minimiser r = R1 + R2 + … + Rk / k est le nombre de variableartificielles.

15/10/2019 16:03 15



• Avant de commencer à faire tourner le simplexe du PL1, il faut faireles transformations nécessaires pour rendre à nulle (0) les valeursdes Δj des variables artificielles. (puisque elles sont des variables debases).

• Si la solution de ce PL1 est strictement positive (valeur minimale dela somme des variables artificielles) :

Le PL n'a pas de solution possible,

Terminaison du processus.

• Sinon: passez à la phase 2.

15/10/2019 16:03 16



• Phase 2 (PL2):

Supprimer les colonnes des variables artificielles du tableau final de laphase 1.

La fonction objectif du PL2 est celle du PL initial.

Les contraintes du PL2 sont les contraintes arrêtées à la phase 1(extraites du tableau final).

Avant de commencer à faire tourner le simplexe du PL2, il faut faire,éventuellement, les transformations nécessaires pour rendre à nulle(0) les valeurs des Δj des variables de base.

• Rappel :

Dans la phase 2, nous utilisons la solution réalisable issue de la phase 1comme solution de base de départ pour le PL 2.

15/10/2019 16:03 17



• Exemple : PLVA2Max Z = 4x + y

SC

3x + y ≥ 3

4x + 3y ≥ 6

x + 2y ≤ 4

x,y ≥ 0

Insertion variables d’écart et variables artificielles

Max 4x + y

SC

3x + y – u + a1 = 3

4x + 3y - v + a2 = 6

x + 2y + w = 4

x,y,u,v,w,a1,a2 ≥ 0

15/10/2019 16:03 18



• PLVA2: Résolution graphique (confirmation)

15/10/2019 16:03 19



• PLVA2: Phase 1

Phase 1 : Max r = - a1 – a2 (ou Min r = a1 + a2 )

R1 : Dans la ligne r’, a1 et a2 sont des variables de base, donc ellesdoivent avoir des composantes nulles, d’où la màj pour avoir la ligne r.

15/10/2019 16:03 20

I0 x y u v w a1 a2

a1 3 1 -1 0 0 1 0 3

a2 4 3 0 -1 0 0 1 6

w 1 2 0 0 1 0 0 4

r’ 0 0 0 0 0 -1 -1 0

r 7 4 -1 -1 0 0 0 -9



• PLVA2: Phase 1

• L’itération 1 correspond au sommet artificiel (1,0). (Voir la figure FVA-2)

15/10/2019 16:03 21

I1 x y u v w a1 A2

x 1 1 / 3 -1 / 3 0 0 1 / 3 0 1

a2 0 5 / 3 4 / 3 -1 0 -4 / 3 1 2

w 0 5 / 3 1 / 3 0 1 -1 / 3 0 3

r 0 5 / 3 4 / 3 1 0 -7 / 3 0 -2



• PLVA2: Phase 1

• L’itération I2 correspond au sommet réel (3/5, 6/5). (Voir la figure FVA-2)

• On maximise r = -a1 – a2 et a1, a2 ≥ 0

• Arrêt Phase 1 car r a atteint 0.

15/10/2019 16:03 22

I2 x y u v w a1 a2

x 1 0 -3 / 5 1 / 5 0 3 / 5 -1 / 5 3 / 5

y 0 1 4 / 5 -3 / 5 0 -4 / 5 3 / 5 6 / 5

w 0 0 -1 1 1 1 -1 1

r 0 0 0 0 0 -1 -1 0



• PLVA2: Phase 2

• R2 : Même remarque que R1

15/10/2019 16:03 23

I3 x Y u v w

x 1 0 -3 / 5 1 / 5 0 3 / 5

y 0 1 4 / 5 -3 / 5 0 6 / 5

w 0 0 -1 1 1 1

Z’ 4 1 0 0 0 0

Z 0 0 8 / 5 -1 / 5 018/5

(3/5 , 6/5)



• PLVA2:

15/10/2019 16:03 24

I4 x y u v w

x 1 3 / 4 0 -1 / 4 0 3 / 2

u 0 5 / 4 1 -3 / 4 0 3 / 2

w 0 5 / 4 0 1 / 4 1 5 / 2

Z 0 -2 0 1 06

(3/2 , 0)



• PLVA2:

• Arrêt, Solution optimale Z* = 16 relative aux coordonnées (x,y) = ( 4, 0)

15/10/2019 16:03 25

I5 x y u v w

x 1 2 0 0 1 4

u 0 5 1 0 3 9

v 0 5 0 1 4 10

Z 0 -7 0 0 -416

(4 , 0)

Documents

Introduction à la Recherche Opérationnelle