chapitre

Recherche opérationnelle

1

Plan du cours

Chapitre I : Introduction à la programmation linéaire ............................................................................... 2

Série 1 : Corrigés des exercices n° 1 à 2 et 5.......................................................................................... 4

Chapitre II : Résolution d’un PL par la méthode graphique ....................................................................... 9

Série 2 : Corrigés d’exercices ............................................................................................................... 20

Chapitre III : Résolution d’un PL par la méthode dite du « Simplexe ».................................................... 24

Série 3 : Corrigés d’exercices ............................................................................................................... 30

Chapitre IV : Méthode du Simplexe : Problème de minimisation et problème irrégulier.......................... 39

Chapitre V : Dualité.........................................................................................................................................

Chapitre VI : Ordonnancement ..........................................................................................................................

T.P. : Programme de résolution d’un PL : L.I.N.D.O.........................................................................................


2

R e c h e r c h e o p é r a t i o n n e l l e

18

CHAPITRE 1

Introduction à la programmation linéaire 02 20

05

I – I n t r o d u c t i o n La programmation linéaire est une classe de modèles mathématiques d’optimisation qui a pour objet la

maximisation ou minimisation d’une fonction linéaire de variables ( appelée fonction objectifs soumise à des contraintes (équations ou inéquations ).

Le terme « programmation » indique le fait que c’est un problème d’optimisation qui, du point de vue économique, concerne l’allocation efficace des rares ressources à certaines activités en vue de maximiser ( ou minimiser ) un certain objectif.

Le terme « linéaire » indique que les relations mathématiques qui lient ces activités aux variables sont linéaires.

L’une des décisions les plus fréquentes d’un gestionnaire est l’allocation des ressources entre des activités données en vue d’un objectif déterminé : La minimisation des coûts, la maximisation des profits où l’optimisation d’un critère quelconque de performance constitue l’une des préoccupations urgentes du chef d’entreprise surtout que ce dernier dispose de ressources limitées en matières premières, main d’œuvre et fonds.

Donc, la programmation linéaire fournit au décideur une méthode pour la recherche des solutions optimales à ces problèmes d’allocation.

I I – F o r m u l a t i o n d ’ u n m o d è l e d e d é c i s i o n 1 – Caractéristiques d’un programme linéaire (PL)

Un PL est caractérisé par : A – Sa fonction économique ou fonction objectif ou fonction linéaire notée Z :

Z = C1x1 + C2x2 + … + Cnxn x1,x2, …, xn = Variables

Remarque : Si c’est un profit, on parle alors de maximiser Z. S’il s’agit de coûts, l’on parle alors de minimiser Z tout en respectant les contraintes.

B – Des inconnues (x1,x2, …, xn) ou variables de décision. indépendantes dont on cherche les valeurs. C – Des contraintes qui doivent vérifier ces inconnues qui prennent la forme d’égalités ou inégalités.

2 – Formulation d’un PL Un menuisier fabrique des portes et des chaises. Quel est l’objectif du menuisier ?

⇒ Sa fonction objectif : Maximiser le profit.


3

Ce menuisier est soumis à des contraintes. On a : Z = C1x1+C2x2 Avec : x1 = la quantité produite de tables. x2 = la quantité produite de chaises. C1 = Prix de vente des tables. C2 = Prix de vente des chaises. Il est à noter que le profit unitaire généré par la vente d’une table est de 2D. Le profit unitaire généré par

la vente d’une chaise est de 3D. D’où : Z = 2x1 +3x2

Supposons que : - 1 unité produite de tables nécessite 2 unités d’heures de main d’œuvre et 3 unités de matières

premières. - 1 unité produite de chaises nécessite 4 unités d’heures de main d’œuvre et 2 unités de matières

premières. - Le menuisier dispose de 120 heures de main d’œuvre et de 140 unités de matières premières.

Disposer les données en tableau !

HM = Heures de main d’œuvre. MP = Matière première. ΠU = Profit unitaire (Π - pi – pour profit ).

Le programme linéaire s’écrit sous la forme : Max Z = 2 x1 +3 x2

Sous les contraintes : 2x1 + 4x2 ≤ 120 3x1 +2x2 ≤ 240 avec toujours x1 ≥ 0 et x2 ≥ 0 .

La formulation initiale d’un programme linéaire donne en général un problème sous la forme générale

qui est :

Max ou Min Z = C1x1 + C2x2+ … + Cnxn = ∑=

n

iii xC

1

S/C a11x1 + a12x2 + … + a1nxn ≥ b1 1er type . ≤ bi 2ème type . = bi 3ème type an1x1 + an2x2 + … + annxn Exemple de formulation Dans une raffinerie, on fait la distillation de 2 types de pétrole B1 et B2 pour déterminer 3 qualités

d’essences E1, E2 et E3. La raffinerie doit approvisionner un distributeur d’essence. La distillation de 100 litres de B1 fournit 10

litres de E1, 10 litres de E2 et 20 litres de E3 alors que la distillation de la même quantité de B2 fournit 50 litres de E1, 40 litres de E2 et 20 litres de E3.

La raffinerie doit satisfaire une commande de 500 litres de E1, 400 litres de E2 et 600 litres de E3. Sachant que les coûts par m3 sont de 20 d pour B1 et de 25 D pour B2, formulez le PL qui minimise le

coût des quantités des bruts utilisés pour la satisfaction de la demande.

x1 x2 Disposition HM 2 4 120 MP 3 2 240 ΠU 2 3


4


19

CHAPITRE 1

Correction d’exercices de la série n°1

02 2005

Rappels : Les étapes de la formulation d’un PL sont :

Fonction objectif : Max ou Min Z = C1x1 + C2x2+ … + Cnxn = ∑=

n

iii xC

1

Variables de décision : xj

Contraintes : a11x1 + a12x2 + … + a1nxn ≥ b1 1er type

. ≤ bi 2ème type . = bi 3ème type an1x1 + an2x2 + … + anmxn

Remarque : Les contraintes forment un système matriciel : A X = b .

C o r r i g é d e l ’ e x e r c i c e n ° 1

Fonction objectif : Minimiser les coûts des quantités de brut. <-> Zmin = C1x1 + C2x2 Variables de décision : x1 : Quantité de brut de B1.

x2 : Quantité de brut de B2. Contraintes : Contraintes de satisfaction des commandes.

D’où le PL suivant :

Min Z = 20x1 + 25x2

CS 10 x1 + 50 x2 ≥ 500

10 x1 + 40 x2 ≥ 400 20 x1 + 20 x1 ≥ 600

avec x1 et x2 ≥ 0

C o r r i g é d e l ’ e x e r c i c e n ° 2 Fonction objectif : Maximiser le profit <-> max Π Variables de décision :

Quantités produites d’interrupteurs de type A : x1 Π Quantités produites d’interrupteurs de type B :x2

Contraintes : La production est limitée par : a) 1re contrainte : Le temps de travail

T = nombre d’heures de travail disponibles t1 = nombre d’heures nécessaires pour fabriquer un interrupteur de type A.


5

t2 = nombre d’heures nécessaires pour fabriquer un interrupteur de type B. T = t1 x1 + t2 x2 ≤ T T1 = 2 t2 Si x1 = 0 , on fabrique le maximum de B c’.à.d. x2 = 1000. Nous avons = t2 x2 = T <-> 1000 t2 = T D’où : 2 t2 x1 + t2 x2 ≤ 1000 t2

2 x1 + x2 ≤ 1000

b) 2ème contrainte : L’isolant disponible x1 + x2 ≤ 600

c) 3ème contrainte : La quantité de fil de laiton

x1 ≤ 400 x2 ≤ 700

D’où le PL suivant : Max Π = 0,4 x1 + 0,3 x2

CS 2 x1 + x2 ≤ 1000

x1 + x2 ≤ 600 x1 ≤ 400 x2 ≤ 700

avec x1 et x2 ≥ 0

C o r r i g é d e l ’ e x e r c i c e n ° 5 xi = nombre de chauffeurs qui commencent le travail au début de la période i de 2 heures. Pour avoir ai pendant la période i, on essaie de définir les contraintes par période : Période : x1 + x2 + x3 + x4 + x5 + x6 + x7 +x8 + x9 + x10 +x11 + x12 ≥ a1

x1 + x10 + x11 + x12 ≥ a1 Période : x1 + x2 + x11 + x12 ≥ a2 Période : x1 + x2 + x3 + x12 ≥ a3 Période : x1 + x2 + x3 + x4 ≥ a4 Périodes 5 à 12 : xk-3 + xk-2 + xk-1 +xk ≥ ak Exemple pour la période : x2 + x3 + x4 + x5


6


26

CHAPITRE 1

Introduction à la programmation linéaire 02 20

05

3 – La formulation algébrique d’un programme linéaire A – Forme générale G Et Forme standard S La formulation initiale d’un programme linéaire donne en général un problème sous une forme générale

qui est la suivante : Forme générale G

Max ou Min Z = C1x1 + C2x2+ … + Cnxn = ∑=

n

jjj xC

1

CS a11x1 + a12x2 + … + a1nxn ≥ b1 1er type

. ≤ bi 2ème type . = bi 3ème type an1x1 + an2x2 + … + anmxn

Les variables de décision sont x1, x2, …, xn et la fonction économique à optimiser est représentée par Z. Les paramètres Cij, bi et aij sont des constantes connues d’avance. Trois types de contraintes sont généralement présentes : ≥ , ≤ ou = . Il y a aussi deux catégories de variables de décision : Certaines sont supposées ne prendre que des

valeurs non négatives alors que d’autres peuvent prendre toute valeur réelle. Un PL sous forme générale (G) peut être transformé en un PL équivalent sous forme standard notée A ou S.

Max Z = ∑=

n

jjj xC

1 < - > Max Z = C1x1 + C2x2+ … + Cnxn

CS ∑ jij xa ≤ bi

xj ≥ 0 < - >

a11x1 + a12x2 + … + a1nxn ≤ b1 a21x1 + a22x2 + … + a2nxn ≤ b2 ................................................ ................................................ ................................................ an1x1 + an2x2 + … + annxn ≤ bn

La forme générale (G) se caractérise par le fait que c’est un problème où toutes les contraintes sont du type ≤ et les variables de décision sont non négatives.

Sa forme standard (S) est :

Max Z = ∑ jj xC

CS ∑ jij xa = bi


7

xj ≥ 0 La forme standard se caractérise par des contraintes sous forme d’équations (égalité = ). B – Passage de la forme générale à la forme standard Un certain nombre de transformations algébriques permettent le passage de la forme générale à la

forme standard :

B1 – Si le problème consiste à minimiser Z <-> Min Z = ∑=

n

jjj xC

1 , on doit changer le sens

d’optimisation i.e :

Min Z = ∑=

n

jjj xC

1 <-> Max Z = ∑

=

−n

jjj xC

1)(

B2 – Si le sens d’inégalité des contraintes est de type supérieur ou égal ≥, l’on doit changer le sens d’inégalité (≤) :

∑ jij xa ≥ bi <-> ∑ − jij xa )( ≤ -bi

B3 – Si les contraintes sont de type (=), on doit convertir l’égalité en inégalité :

∑ jij xa = bi <-> ∑ jij xa ≥ bi <->

⎪⎪⎪

⎩

⎪⎪⎪

⎨

⎧

≤

≤−⇔≥

∑

∑∑

b

b- )( b

i

i

jij

ijijjij

xa

xaxa

et

B4 – Convertir une inégalité en égalité en introduisant des variables d’écart :

∑ jij xa ≤ bi <-> ∑ jij xa + Si = bi

∑ jij xa ≥ bi <-> ∑ jij xa - Si = bi

Remarque : Les variables d’écart n’apportent aucune contribution à la fonction objectif. B5 – Dans le cas où les variables de décision sont libres ou sans contrainte de signe, l’on doit remplacer la variable xj par 2 variables non négatives. En d’autres termes, si xj est libre, on introduit :

xj+ et xJ

- ≥ 0 telles que :

xj = xj+ - xJ

-

Quelques définitions et rappels Un PL sous forme standard (S) peut être écrit sous une forme matricielle en utilisant la notation

suivante :


8

A = Matrice des coefficients techniques (aij)

⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

=

nmnn

m

m

aaa

aaaaaa

A

............

....

....

21

22221

11211

C = Matrice des cj X = matrice des xi

⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

=

nc

cc

C

.....2

1

⎟⎟⎟⎟⎟⎟⎟⎟⎟

⎠

⎞

⎜⎜⎜⎜⎜⎜⎜⎜⎜

⎝

⎛

=

nx

xx

X

.....2

1

Pour avoir Max Z :

Max Z = C’ X -- C’ est une matrice transposée de C <-> tC.

CS AX =b

x ≥ 0

Une solution possible au PL est un vecteur X qui satisfait les contraintes AX = b.


9


26

CHAPITRE 2

Résolution d’un PL Méthode graphique

02 2005

L’objet principal de ce chapitre est de proposer une méthode de résolution d’un problème linéaire ne

comportant que 2 variables de décision. La méthode consiste en la délimitation de l’intersection des demi-plans représentant les inéquations des

contraintes et en la recherche dans ce domaine des points donnant l’optimum de la fonction objectif.

I D é f i n i t i o n s 1 - Solution possible non réalisable

Elle respecte le principe de la non négativité et se trouve en dehors du polyèdre. Autrement dit, elle ne vérifie pas les contraintes fonctionnelles.

2 – Solution possible et réalisable

Elle se trouve à l’intérieur du polyèdre. Autrement dit, elle vérifie toutes les contraintes ( contraintes fonctionnelles et contraintes de signe ).

3 – Solution réalisable de base ( notée SRB )

C’est un point extrême, sommet ou point extrémal du polyèdre :

4 – Solution réalisable non optimale C’est un point quelconque du domaine se trouvant à l’intérieur du polyèdre.

5 – Solution optimale C’est une solution réalisable de base maximisant la valeur de Z ( lorsque l’optimisation est une

maximisation). Elle est obtenue en déplaçant la droite z vers le haut parallèlement à elle-même (même pente = même

coefficient directeur de la droite : y = a x -- a est la pente, le coefficient directeur ) jusqu’au dernier contact avec un point extrême du polyèdre.

A

B

C

D


10

I I – R e c h e r c h e d e l a s o l u t i o n o p t i m a l e

La recherche de l’optimum à l’aide de la méthode graphique ne peut s’appliquer aux problèmes de + de 2 variables de décision.

La méthode graphique présente l’avantage d’être simple et permet l’illustration de certains principes de base pour une méthode plus générale ( méthode du Simplexe ).

1 – Représentation graphique des contraintes fonctionnelles

Dans la région des solutions possibles, on se propose de déterminer l’ensemble des solutions réalisables c’.à.d. qui vérifient simultanément toutes les contraintes fonctionnelles. Pour cela, il nous faut d’abord connaître l’ensemble des points qui respectent chacune de ces contraintes, chaque contrainte fonctionnelle étant en relation linéaire correspond à un seul demi-plan limité par la droite qui représente cette contrainte au sens de l’égalité.

La connaissance des demi-plans qui respectent la contrainte résulte d’une simple évaluation d’un point

quelconque non situé sur la droite. Dans la pratique, on utilise le point origine de coordonnées (0,0). L’intersection des demi-plans constitue le polyèdre convexe : C’est le domaine des possibilités,

domaine de disponibilité, polygone des contraintes.

2 - Recherche de la solution optimale Sachant que la droite qui correspond au profit Max doit traverser le domaine des solutions réalisables et

qu’un déplacement vers le haut de cette droite fait croître la valeur de Z, le dernier point touché, le plus éloigné de l’origine correspond à la solution optimale.

Remarque : A l’origine, x1 = 0 x2 = 0 Z = 0 T.A.F. : Comment représenter la droite de la fonction objectif ? Max Z = C1 x1 + C2 + x2

xCC

CZx

2

1

22 −=

21

2

12 C

ZxCCx +

−=

Constante12

12 +−= x

CCx

En général, On fixe Z = 0, nous avons un premier point O de coordonnées ( 0,0 ), nous savons que par 2 points passe

une droite, il suffit de déterminer un deuxième point :

⎟⎟⎠

⎞⎜⎜⎝

⎛=+−==Δ 0 : 0

21

2

12 C

ZnbxCCxz

O( 0,0 ) A( ?, ? ).

ΔZ : Courbe de niveau Il suffit de représenter ΔZ pour le 1er niveau qui correspond à Z/C2 = 0 <-> Z = 0


11

3 – Solutions optimales : Différents cas possibles 1er cas : Pas de solution, le polyèdre est vide.

2ème cas : Il y a une solution unique optimale, elle se situe toujours à un sommet du polygone. 3ème cas : La solution optimale se situe sur un côté du polygone. Dans ce cas, la pente de la fonction

objectif (Z) est identique à celle de la droite qui porte ce côté, plusieurs solutions optimales existent et fournissent le même gain.

4ème cas : Solutions infinies : La solution optimale se trouve rejetée à l’infini.

-5 -4 -3 -2 -1 0 1 2 3 4 5

-5 -4 -3 -2 -1

1 2 3 4 5


12

Exemple applicatif : soit le PL suivant : Max Z = 25 x1 + 15 x2

CS

2 x1 +2 x2 ≤ 240 3 x1 + x2 ≤ 140 x1 ≥ 0 et x2 ≥ 0 T.A.F. : Résoudre graphiquement ce PL !

Corrigé : 1re étape : Représentation des droites des contraintes Δ1 = 2 x1 + 2 x2 = 240 ⇔ x2 = 120 –x1 -- A(0,120) B(120,0) Δ2 = 3 x1 + x2 = 140 ⇔ x2 = 140 – 3 x1 -- C(0,140) D(40,20) 2ème étape : Représentation de la droite de la fonction objectif Z

A

B

C

D

E


13

ΔZ = x2 = 12

1 xCC

−

ΔZ = x2 = 11525 x−

ΔZ = x2 = 135 x−

-- O(0,0) E(120,-200) ⇒ La solution optimale est le point B. B = Δ1 ∩ Δ2 3ème étape : Déterminer les coordonnées de B ⇔ Résoudre le système suivant :

⎩⎨⎧

=+=+1403

24022

21

21

xxxx

et par substitution l’on a :

⎩⎨⎧

==

⇔⎩⎨⎧

=−=

⎩⎨⎧

=−+−=

10x110x

10120x

1401203

120

1

2

1

12

11

12

xx

xxxx

d’où B(10,110) d’où Z* = 1900


14


05

CHAPITRE 2

Résolution d’un PL Méthode graphique

03 2005

Exemple applicatif n°2 : soit le PL suivant : Min Z = 24 x1 + 20 x2

CS

x1 + x2 ≥ 30 x1 + 2 x2 ≥ 40 x1 ≥ 0 et x2 ≥ 0 T.A.F. : Résoudre graphiquement ce PL !

Corrigé : 1re étape : Représentation des droites des contraintes Δ1 = x1 + x2 = 30 ⇔ x2 = 30 –x1 -- A(0,30) B(30,0) Δ2 = x1 + 2 x2 = 40 ⇔ x2 = 20 – ½ x1 -- C(0,20) D(40,0) 2ème étape : Représentation de la droite de la fonction objectif Z

ΔZ = x2 = 12

1 xCC

−

ΔZ = x2 = 12024 x−

ΔZ = x2 = 156 x− -- O(0,0) E(5,-6)

Pour un problème de minimisation, on fait descendre la courbe ΔZ ⇒ le 1er point touché par ΔZ est alors le point D (40,0) = dernier point touché ⇔ 24 * 40 + 20 * 0 = 960 ⇒ Z* = 960.

A

B

C

D O

E


15

Ce problème de minimisation ne diffère de celui de la maximisation que par la recherche des courbes de niveau qui donne la plus petite valeur de la fonction objectif tout en satisfaisant toutes les contraintes.

Graphiquement, on déplace la droite de la fonction objectif parallèlement à elle-même à l’intérieur du domaine des possibilités. La fonction objectif diminue de valeur à mesure qu’on se rapproche de l’origine des axes. Cela correspond à l’optimum puisqu’il s’agit d’un point de minimisation.

Différentes solutions possibles d’un PL par la méthode graphique 1er cas : Problème impossible Min Z = 3 x1 + 2 x2

CS x1 + 2 x2 ≤ 2

2 x1 + 4 x2 ≥ 8 x1 ≥ 0 et x2 ≥ 0 Soient Δ1 = x1 + 2 x2 = 2 ⇔ x2 = 1 – ½ x1 -- A(0,1) B(2,0) Δ2 = 2 x1 + 4 x2 = 8 ⇔ x2 2 – ½ x1 -- C(0,2) D(4,0)

ΔZ = -23

− x1 -- O(0,0) E(2,-3)

L’espace des solutions réalisables est vide ; c’est un problème impossible. 2ème cas : Problème à solutions multiples Max Z = x1 + 3 x2

CS 2 x1 + 6 x2 ≤ 30

x1 ≤ 10 x2 ≤ 4

x1 ≥ 0 et x2 ≥ 0

Soient Δ1 = 2 x1 + 6 x2 = 30 ⇔ x2 = 12

315

2630

xx

−⇔−

-- A(0,5) B(3,4)

Δ2 = x1 = 10 ⇔ Δ3 =x2 = 4

ΔZ = -31

− x1 -- O(0,0) E(3,-1)

-3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11

-2

-1

1

2

3

4

5

6 A B


16

L’ensemble des points décrits par le segment [B,D] représente les solutions optimales du PL. C’est un problème à solutions multiples :

D = Δ1 ∩ Δ2 ⇔ )4,3(43

43154

4315

2

1

2

1

2

12 Dxx

x

x

x

xx⇒

⎩⎨⎧

==

⇔⎪⎩

⎪⎨⎧

=

−=⇔

⎪⎩

⎪⎨⎧

=

−= ⇒ Z* = 15.

3ème cas : Problème avec solutions non-bornées Max Z = -2 x1 + 3 x2

CS x1 ≤ 5

2 x1 –3 x2 ≤ 6 x1 ≥ 0 et x2 ≥0 Soient : Δ1 = 5

Δ2 = x2 = -2 +32 x1 -- A(0,-2) B(3,0)

ΔZ = x2 = 32 x1 -- O(0,0) C(3,2)

⇒ On peut augmenter la valeur de la fonction objectif indéfiniment ( déplacement de ΔZ vers le haut ). Donc, la solution est non bornée.

4ème cas : Problème de dégénérescence Max Z = x1 +x2

CS 3 x1 + 2 x2 ≤ 40

x1 ≤ 10 x2 ≤ 5 x1 ≥ 0 et x2 ≥ 0

Soient : Δ1 =3 x1 + 2 x2 = 40 ⇔ x2 = 121

2320

2340

xxx

−=⇔−

-- A(0,20) B((20,-10)

Δ2 = x1 = 10 Δ3 = x2 = 5 ΔZ = x2 = - x1 -- O(0,0) C(20,-20)

La solution optimale B(10,5) est dite dégénérée si trois contraintes concourent en ce point.

-1 0 1 2 3 4 5 6

-3

-2

-1

1

2

3

4

5

A

B

C

0

A

B

C


17

Exemple applicatif n°1 Max Z = 100 x1 + 200 x2

CS x1 + x2 ≤ 150

4 x1 +2 x2 ≤ 440 x1 + 4x2 ≤ 480

x1 ≤ 90 x1 ≥ 0 et x2 ≥ 0

Corrigé

Soient les droites suivantes : Δ1 = x1 +x2 =150 ⇔ x2=150 – x1 -- A(0,150) B(150,0) Δ2 = 4 x1 + 2 x2=440 ⇔ x2 = 220 –2 x1 -- C(0,220) D(110,0)

Δ3 = x1 +4 x2 = 480 ⇔ x2 = 120 –14 x1 -- E(0,120) F(480,0)

Δ4 = x1 =90

ΔZ =-100200 x1 ⇔ -12 x1 -- O(0,0) G(220,-110)

H est la solution optimale. H= Δ1 ∩ Δ3 ⇔

⎩⎨⎧ x1 +x2 = 150 x1 +4 x2 = 480 ⇔ - = 330 ⇔ x2 = 110

x1 = 150-110 ⇒ x1 = 40 ⇒ H(40,110) � * = 40 * 100+110 * 200= 26000 � * = 26000


18

Exemple applicatif n°2 Max Z = 30 x + 70 y

CS 4 x + 10 y ≤ 80

14 x +8 y ≤ 112 x + y ≤ 10

x ≥ 0 et y ≥ 0 Exemple applicatif n°3 Max Z = 8 x + 2 y

CS 2 x -6 y ≤ 12

5 x +4 y ≤ 40 x + 2 y ≥ 12 y ≤ 6

x ≥ 0 et y ≥ 0

Corrigé Soient les droites suivantes :

Δ1 = 2 x – 6 y = 12 ⇔ y= 2 x – 12 6 ⇔ y = 13 x -2 -- A(0,-2)

B(6,0)

Δ2 = 5 x + 4 y = 40 ⇔ 10 –54x -- C(0,10)

D(8,0)

Δ3 = x + 2 y =12 ⇔ y = 6 –12x -- E(0,6)

F(12,0) Δ4 = y = 6 ΔZ = y = –4 x -- O(0,0) G(1,-4)

-5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13

-5 -4 -3 -2 -1

1 2 3 4 5 6 7 8 9 10 11

A

B

C

D

E

F

H


19

La solution optimale est le point J = Δ2 ∩ Δ3 ⇒ Le système suivant est donc à résoudre :

⎩⎨⎧x + 2 y =12

5 x + 4 y = 40 ⇔ ⎩⎨⎧2 x + 4 y = 24

5 x + 4 y = 40 ⇔ 3 x = 16 ⇒ x = 163 et y = 10

3

� * = 8 * 163 + 2 * 10

3 ⇔ � * = 1283 + 20

3 = 1483

⇒ � * = 1483 .


20


12

CHAPITRE 2

Correction des exercices de la série n°2

03 2005

E x e r c i c e n ° 1

Fonction Objectif : Max Π = 100 x1 +200 x2

Variables de décision : x1 : Surface allouée à la culture des tomates. x2 : Surface allouée à la culture des piments.

Contraintes : Main d’œuvre : x1 + 4 x2 ≤ 480 Eau : 4 x1 +2 x2 ≤ 440 Surface de terrain : x1 +x2 ≤ 150 Limitation du bureau du périmètre irrigué : x1 ≤ 90 Avec x1 ≥ 0 et x2 ≥ 0

Résolution : Voir exemple applicatif n° 1 du 052 2005.

E x e r c i c e n ° 2 Fonction objectif :

Minimiser le nombre de pilules à prescrire. Variables de décision :

x1 = Nombre de pilules de petite taille. x2 = Nombre de pilules de grande taille.

Contraintes :

Au moins 12 graines d’aspirine 2 x1 +x2 ≥ 12 Au moins 74 grains de bicarbonate 5 x1 + 8 x2 ≥ 74 Au moins 24 grains de codéine x1 +6 x2 ≥ 24


21

Résolution graphique Soient :

Δ1 = 2 x1 + x2 = 12 ⇔ x2=12-2 x1 -- A(0,12) B(6,0)

Δ2 = 5 x1 + 8x2 =74 ⇔ =374 –5

8 x1 -- C(2,8) D(10,3)

Δ3 = x1 + 6 x2 =24 ⇔ x2= 4 –16 x1 -- (E(0,4) F(12,2)

ΔZ = x2= -x1 -- O(0,0) G(2,-2)

Le point C(2,8) constitue la solution optimale, d’où � * = 10.

E x e r c i c e n ° 3 Fonction objectif:

Max Π = 900 x1 + 1000 x2

Variables de décision: x1 : nombre d’unités du produit P1 x2 : nombre d’unités du produit P2

A

B

C

D

E

F

G


22

Contraintes :

Contraintes de temps 11 x1 + 9 x2 ≤ 9900 7 x1 + 12 x2 ≤ 8400 6 x1 + 16 x2 ≤ 9600 avec x1 ≥ 0 et x2 ≥ 0

Résolution Δ2 = 11 x1 + 9 x2 = 9900 ⇔ x2=1100 - -11

9 x1 A(0,1100) B(900,0)

Δ2 = 7 x1 + 12 x2 = 8400 ⇔ x2=700 – 712 x1 C(0,700) D(1200,0)

Δ3 = 6 x1 + 16 x2 = 9600 ⇔ x2= 600 –38 x1 E(0,600) F(1600,0)

ΔZ = x2 = - 910 x1 O(0,0) G(1000,-900)

La solution optimale est H = Δ3 ∩ Δ2


23

⇒ ⎩⎨⎧7 x1 + 12 x2 = 8400

6 x1 + 16 x2 = 9600

⇒ 34 (6 x1 + 16 x2 ) = 9600 * 3 4 ⇒

⎩⎪⎨⎪⎧ 7 x1 +12 x2 = 8400

92 x1 +12 x2 = 7200

⇒ 52 x1 = 1200 ⇒ x1 = 1200 * 2

5 = 480 x2 = 420

d’où � * = 900 * 480 + 1000 * 420= 852000 ⇒ Z* = 852000


24


12

CHAPITRE 3

La méthode du « Simplexe »

03 2005

I - I n t r o d u c t i o n On a présenté dans le chapitre précédent une procédure graphique pour résoudre un PL à 2 variables. Par

contre, dans la plupart des problèmes réels, on a plus de 2 variables à déterminer. Une procédure algébriques pour résoudre les PL avec plus de 2 variables fera l’objet de ce chapitre.

C’est la méthode du « Simplexe ». Une implémentation de cette procédure a permis de résoudre des PL avec un peu plus de quelques milliers de variables. Le programme LINDO qu’on présentera supporte au plus 200 variables et 100 contraintes.

Dans ce chapitre, la méthode du Simplexe est présentée pour les problèmes de la forme : Max tC x

CS A x ≥ b

x ≥ 0 et en utilisant le problème de l’agriculteur (cf. Série n°2, ex n°1) :

Max Z = 100 x1 + 200 x2

CS x1 + x2 ≤ 150

4 x1 +2 x2 ≤ 440 x1 + 4x2 ≤ 480

x1 ≤ 90 x1 ≥ 0 et x2 ≥ 0

I I – M i s e s o u s f o r m e s t a n d a r d La mise sous forme standard consiste à introduire des variables supplémentaires ( 1 pour chaque

contrainte ) de manière à réécrire les inégalités ( ≤ ) sous la forme d’égalités. Chacune de ces variables représente le nombre de ressources non utilisées. On les appelle “variables d’écart”.

La forme générale s’écrit donc :

Max C1x1 + C2x2+ … + Cnxn

CS a11x1 + a12x2 + … + a1nxn ≤ b1

a21x1 + a22x2 + … + a2nxn ≤ b2 ................................................ ................................................ ................................................ an1x1 + an2x2 + … + annxn ≤ bn


25

La forme standard serait alors : Max C1x1 + C2x2+ … + Cnxn + 0 S1 + 0 S2 + … + 0 Sn

CS a11x1 + a12x2 + … + a1nxn + S1 = b1

a21x1 + a22x2 + … + a2nxn + S2 = b2 ......................................................................................... ......................................................................................... ......................................................................................... an1x1 + an2x2 + … + anmxn Sm = bm

Exemple : La forme standard du problème de l’agriculteur est : Max Z = 100 x1 + 200 x2 + 0 S1 + 0 S2 + 0 S3 + 0 S4

CS x1 + x2 + S1 = 150

4 x1 + 2 x2 + S2 = 440 x1 + 4 x2 + S3 = 480 x1 + S4 = 90 x1 ≥ 0, x2 ≥ 0, S1 ≥ 0, S2 ≥ 0, S3 ≥ 0 et S4 ≥ 0

I I I – R e v u e a l g é b r i q u e d e l a m é t h o d e d u S i m p l e x e

La question qui se pose est : Que demande-t-on d’une procédure algébrique? En premier lieu, on note que les contraintes du problème forment un système de 4 équations et 6

variables Or, il y a un nombre infini de solutions à ce système. Une procédure algébrique pour la résolution d’un PL doit être capable de retrouver les solutions des systèmes d’équations où il y a plus de varibales que de contraintes.

En deuxième lieu, on peut noter que ce nesont pas toutes les solutions qui vérifient toutes les contraintes qui sont solutions au PL; ils doivent en plus satisfaire les contraintes de non négativité. Ainsi, un procédure algébrique doit être capable d’éliminer de l’ensemeble des solutions qui satisfait les contraintes celles qui n’arrivent pas à satisfaire les contraintes de non négativité.

Finalement, une procédure algébrique pour résoudre lesPL doit être en mesure de choisir parmi lesoslutions réalisables celles qui maximisent la fonction objectif.

La méthode du Simplexe est une procédure algébriquee qui tient compte de ces 3 considérations. Pour illustrer cette procédure, supposons que x2 = 0 et S1 = 0 :

On a x2=S1 =0 D’où le système suivant :

⎩⎨⎧ X1= 150

4 x1 + S2 = 440x1 + S3 =480x1 + S4 =90

D’où les solutions suivantes : x1 = 150 x2 = 0 S1 = 0 S2 = -160 S3 = 330


26

S4 = -60 Les variables x1, S2, S3 et S4 , non nulles, sont dites « variables de base » ( notées VB ) et les

variables S1 et x2, nulles, sont dites « variables hors base » ( notées VHB). Généralement, si on a un PL standard constitué de n variables et m contraintes avec n ≥ m, alors

une solution de base ( c’est un extrême ) est obtenue en annulant n-m variables et en résolvant les m contraintes pour déterminer les valeurs des autres m variables.

On note qu’une solution de base n’est pas toujours réalisable. C’est le cas de la solution qu’on vient de trouver.

Une solution réalisable de base serait celle où :

⎩⎨⎧x1=x2=0

xj = 0 ⇔ ⎩⎨⎧S1 = 150

S2 = 440S3 =480S4 = 90

Cette solution correspond à un point extrêm de l’ensmeble des solutions réalisables qui est l’origine O.

Pour la méthode du Simplexe, une SRBi ( i.e. solution réalisable de base initiale ) est demandée. Une telle solution peut être retrouvée en annulant toutes les variables de décision ( ce qui correspond dans la méthode graphique au point d’origine O ).

Apartir de ce point, la méthode du Simplexe va générer successivement des solutions réalisables de base pour notre système d’équations en s’assurant que la valeur de la fonction objectif est en train d’augmenter jusqu’à localiser la solution optimale du problème qui est un point extrême de l’espace des solutions réalisables, donc une solution réalisable de base.

Ainsi, on peut décrire la méthode du Simplexe comme étant une procédure itérative qui passe de la SRBi à une autre solution réalisablede base jusqu’à atteindre la solution optimale.


27


19

CHAPITRE 3

La méthode du « Simplexe »

03 2005

R a p p e l s PL de l’agriculteur :

Forme générale Forme standard Max Z = 100 x1 + 200 x2

CS x1 + x2 ≤ 150

4 x1 +2 x2 ≤ 440 x1 + 4x2 ≤ 480

x1 ≤ 90 x1 ≥ 0 et x2 ≥ 0

Max Z = 100 x1 + 200 x2 + 0 S1 + 0 S2 + 0 S3 + 0 S4

CS x1 + x2 = 150

4 x1 +2 x2 = 440 x1 + 4x2 = 480

x1 = 90 x1 , x2 ≥ 0 et S1 , S2 , S3 , S4 ≥ 0

SRBi x1=x2=0 Π = 0

S1 = 150 S2 = 440 S3 = 480 S4 = 90

I V - L a m é t h o d e d u S i m p l e x e

A – Tableau du Simplexe initial ( à l’origine ) Cj 100 200 0 0 0 0

Ci VB Qi x1 x2 S1 S2 S3 S4 Ri 0 S1 150 1 1 1 0 0 0 150 0 S2 440 4 2 0 1 0 0 220 0 S3 480 1 4 0 0 1 0 120 ⇐VS 0 S4 90 1 0 0 0 0 1 ∞ Zj 0 0 0 0 0 0 0 Cj - Zj 100 200 0 0 0 0 ⇑

VE

Ri : Ratio . VE : Variable entrante ⇒ Correspond à la colonne Pivot. VS : Variable sortante ⇒ Correspond à la ligne Pivot. ∞ : lorsque division par zéro, tend vers l’infini. Cj – Zj : Effet de l’augmentation de la jème variable. On remarque qu’on a placé en première ligne les contributions unitaires de toutes les variabes (de

décision & d’écart ) dans la fonction objectif.


28

Dans la 3ème ligne, on retrouve la 1re contrainte. La valeur 150 représente la valeur de S1 relative à la solution réalisable de base initiale ou SRBi.

Dans la 1re colonne (Ci), on retrouve les contributions nulles des variables d’écart qui forment les SRBi.

B – Amélioration de la solution Pour améliorer la solution, il faut générer une autre solution de base (point extrême) qui augmente la

valeur de la fonction objectif, i.e. qu’on doit sélectionner une variable hors base ( VHB ) et variable de base (VB) et les permuter de telle façon que la nouvelle solution donne une plus grande valeurde la fonction objectif.

Pour savoir si l’on peut améliorer notre SRBi , nous allons introduire 2 nouvelles lignes au-dessous du tableau du Simplexe :

- La 1re ligne, notée Zj, représente la variation de la valeur de la fonction objectif qui résulte du fait qu’une unité de la variable corrrespondante à la jème colonne de la matrice A est amenée dans la base. Généralement, l’on a Zj = ∑aij Ci

- La 2ème ligne, notée Ci – Zj , représente l’effet net de l’augmentation d’une unité de la jème variable.

En analysant la ligne relative à l’évaluation nette Cj – Zj , on remarque qu’une augmentation d’une unité de la valeur x1 engendre un profit de 100D et qu’une augmentation d’une unité de la valeur de x2 engendre un profit supplémentaire de 200D .donc, si on a à choisir, on va opter pour une augmentation de la valeur de x2 . On dit que x2 est la variable entrante.

Le problème est maintenant jusqu’où on peut augmenter x2. Cette augmentation ne peut pas se faire indéfiniment. Sous l’hypothèse que x1 reste nulle, on a :

X1 + S1 = 150

2 x2 + S2 = 440 ⇒ S2 = 0, 2 x2 = 440 ⇒ x2 = 4402 ⇒ x2 = 220

4 x2 + S3 = 480 ⇒ S3 = 0, 4 x2 = 480 ⇒ x2 = 4804 ⇒ x2 = 120

S4 = 90 On peut voir que x2 peut prendre comme valeur maximale 120 ( Il ne faut pas oublier que les Si sont des

variables positives ). SRBi SRB

S1 = 150 S1 = S2 = 440 S2 = S3 = 480 x2 = 120 S4 = 90 S4 =

C – Calcul du tableau suivant Cj 100 200 0 0 0 0

Ci VB Qi x1 x2 S1 S2 S3 S4 Ri 0 S1 30 3

4 0 1 0 -14 0 40 ⇐VS

0 S2 200 72 0 0 1 -12 0 400

7

200 X2 120 14 1 0 0 1

4 0 480

0 S4 90 1 0 0 0 0 1 90 Zj 24000 50 200 0 0 50 0 Cj - Zj 50 0 0 0 -50 0 ⇑

VE


29

Si Cj – Zj ≤ 0 ⇒ La solution est optimale. Dans notre cas : Solution non optimale = SRB ⇒ Nouvelle itération indispensable. Ce qui reste à déterminer sont les coefficients aij de la nouvelle matrice A et les valeurs Qi des variables

de base. Ceci est réalisé en utilisant la règle du pivot : Étape : Diviser la ligne du pivot par la valeur de l’élément pivot pour trouver la

ligne transformée de la ligne du pivot. Étape : À chacune des variables de base, on associe la valeur 1 à l’intersection de la

ligne et de la colonne relatives à cette même variable et dans le reste de la colonne on trouve des zéros.

Étape : Pour calculer le reste des valeurs du tableau, on opère à des combinaisons linéaires dans le précédent tableau du Simplexe. Par exemple, pour calculer la nouvelle valeur qui va prendre la place de la valeur 150 devant la variable de base S1 on procède comme suit :

150 * 4 – (1 * 480 )4 =30

440 * 4 – 2 * 4804 =200

90 *4 – 0 * 4804 =90

1 * 4 – 1 * 14 = 34

D – Itération suivante

Cj 100 200 0 0 0 0 Ci VB Qi x1 x2 S1 S2 S3 S4

100 X1 40 1 0 43 0 -13 0

0 S2 60 0 0 -143 1 2

3 0

200 X2 110 0 1 -13 0 13 0

0 S4 50 0 0 -43 0 13 1

Zj 26000 100 200 2003 0 100

3 0

Cj - Zj 0 0 -2003 0 -100

3 0

Cj – Zj ≤ 0 ⇒ Solution optimale SRB : x1 = 40 X2 = 110 Π = 26000


30


26

CHAPITRE 3

Correction des exercices de la série n°3

03 2005

R a p p e l s : L a m é t h o d e d u s i m p l e x e Étape : FG ⇒ FS

FG : Max C1x1 + C2x2+ … + Cnxn

CS a11x1 + a12x2 + … + a1nxn ≤ b1

a21x1 + a22x2 + … + a2nxn ≤ b2 ................................................. ................................................. ................................................. an1x1 + an2x2 + … + anmxn ≤ bn

FS : C1x1 + C2x2+ … + Cnxn + 0 S1 + 0 S2 + … + 0 Sn

a11x1 + a12x2 + … + a1nxn + S1 = b1 a21x1 + a22x2 + … + a2nxn + S2 = b2 .................................................................................... .................................................................................... .................................................................................... an1x1 + an2x2 + … + anmxn Sn = bn

x ≥ 0 si ≥ 0

Étape : SRBi

On annule toutes les variables de décision dans les équations des contraintes :

SRBi

⎩⎪⎨⎪⎧S1 = b1

S2 =b2.....

Sn =bn

La SRBi correspond à l’origine.


31

Étape : Tableau initial du simplexe Cj C1 C2 C3 … 0 0 0

Ci VB Qi x1 x2 x3 … S1 S2 S3 … Ri 0 S1 b1 a11 a12 a13 … 1 0 0 … 0 S2 B2 a21 a22 a23 PIVOT 0 1 0 … Ligne

Pivot 0 S3 B3 a31 a32 a33 … 0 0 1 … 0 S4 B4 a41 a42 a43 … 0 0 0 … … … … … … … … … … … … … … … … … … … … … … … Zj Cj - Zj C

olonne pivot

VE = Cj – Zj la plus grande possible. VS = celle qui possède le ratio le plus faible positif.

Étape : 2ème tableau du simplexe - Diviser la ligne pivot par l’élément pivot. - Marquer 1 dans chaque intersection d’une VRB avec elle-même et 0 à chaque intersection d’une

VRB avec une autre VRB. - Cellules restantes : Procéder à des combinaisons linéaires comme suit :

Erreur ! L’algorithme sera répété jusqu’à obtention de la solution optimale qui correspond à Cj – Zj ≤ 0


A - FG ⇒ FS FG FS

Max Z = 2 x1 + 5 x2

CS x1 ≤ 400

x2 ≤ 300 x1 + x2 ≤ 600

avec x1 ≥ 0 et x2 ≥ 0

Max Z = 2 x1 + 5 x2 + 0 S1 + 0 S2 + 0 S3

CS x1 +S1 = 400

x2 + S2 = 300 x1 + x2 + S3 = 600

avec x1 , x2 ≥ 0 et S1 , S2 , S3 ≥ 0

B – SRBi S1 = 400 S2 = 300 S3 = 600


32

C – Tableau initial

Cj 2 5 0 0 0 Ci VB Qi x1 x2 S1 S2 S3 Ri 0 S1 400 1 0 1 0 0 ∞ 0 S2 300 0 1 0 1 0 300 ⇐VS 0 S3 600 1 1 0 0 1 600 Zj 0 0 0 0 0 0 Cj - Zj 2 5 0 0 0 ⇑

VE

D – Nouvelle matrice transformée

SRB = S1 x2 S3 1re étape : Diviser la ligne pivot par l’élément pivot. 2ème étape : Mettre 1 à chaque croisement de chaque variable de base avec elle-même. 3ème étape : Mettre 0 à chaque croisement de chaque variable de base avec une autre variable de base.

Cj 2 5 0 0 0 Ci VB Qi x1 x2 S1 S2 S3 Ri 0 S1 400 1 0 1 0 0 400 5 x2 300 0 1 0 1 0 ∞ 0 S3 300 1 0 0 -1 1 300 ⇐VS Zj 1500 0 5 0 5 0 Cj - Zj 2 0 0 -5 0 ⇑

VE

E – Nouvelle matrice transformée

SRB : S1 x1 x2

Cj 2 5 0 0 0 Ci VB Qi x1 x2 S1 S2 S3 0 S1 100 0 0 1 1 -1 5 x2 300 0 1 0 1 0 2 x2 300 1 0 0 -1 1 Zj 2100 2 5 0 3 2 Cj - Zj 0 0 0 -3 -2

Les Cj – Zj ≤ 0 ⇒ C’est la solution optimale

x1 = 300 x2 = 300 Πmax = 2100


33


A - FG ⇒ FS FG FS

Max Z = 100 x + 150 y

CS 10 x + 4 y + S1 ≤ 160

x + y + S2 ≤ 20 10 x + 20 y + S3 ≤ 300

avec x ≥ 0 et y ≥ 0

Max Z = 100 x + 150 y + 0 S1 + 0 S2 + 0 S3

CS 10 x + 4 y + S1 = 160

x + y + S2 = 20 10 x + 20 y + S3 = 300

avec x , y ≥ 0 et S1 , S2 , S3 ≥ 0

B – SRBi

S1 = 160 S2 = 20 S3 = 300

C – Tableau initial Cj 100 150 0 0 0

Ci VB Qi x y S1 S2 S3 Ri 0 S1 160 10 4 1 0 0 40 0 S2 20 1 1 0 1 0 20 0 S3 300 10 20 0 0 1 15 ⇐VS Zj 0 0 0 0 0 0 Cj - Zj 100 150 0 0 0 ⇑

VE


SRB = S1 S2 y 1re étape : Diviser la ligne pivot par l’élément pivot. 2ème étape : Mettre 1 à chaque croisement de chaque variable de base avec elle-même. 3ème étape : Mettre 0 à chaque croisement de chaque variable de base avec une autre variable de base.

Cj 100 150 0 0 0 Ci VB Qi x y S1 S2 S3 Ri 0 S1 100 8 0 1 0 -15 12.5

0 S2 5 12 0 0 1 - 1

20 10 ⇐VS

150 y 15 12 1 0 0 1

20 30

Zj 2250 75 150 0 0 7.50 Cj - Zj 25 0 0 0 -15

2


34

⇑ VE

E – Nouvelle matrice transformée

SRB : S1 x y

Cj 100 150 0 0 0 Ci VB Qi x y S1 S2 S3 0 S1 20 0 0 1 -16 6

10

100 x 10 1 0 0 2 - 110

150 y 10 0 1 0 -1 110

Zj 2500 100 150 0 50 5 Cj - Zj 0 0 0 -50 -5


x = 10 y = 10 Πmax = 2500


A - FG ⇒ FS FG FS

Max Z = 600 x1 + 540 x2 + 375 x3

CS x1 + x2 + x3 ≤ 12

x1 ≤ 5 80 x1 + 70 x2 +50 x3 ≤ 750

avec x1 , x2 et x3 ≥ 0

Max Z = 600 x1 + 540 x2 + 375 x3 + 0 S1 + 0 S2 + 0 S3

CS x1 + x2 + x3 +S1 = 12

x1 + S2 = 5 80 x1 + 70 x2 +50 x3 + S3 = 750

avec x1 , x2 ≥ 0 et S1 , S2 , S3 ≥ 0

B – SRBi S1 = 12 S2 = 5 S3 = 750

C – Tableau initial Cj 600 540 375 0 0 0

Ci VB Qi x1 x2 x3 S1 S2 S3 Ri 0 S1 12 1 1 1 1 0 0 12 0 S2 5 1 0 0 0 1 0 5 ⇐VS 0 S3 750 80 70 50 0 0 1 9,375 Zj 0 0 0 0 0 0 0 Cj - Zj 600 540 375 0 0 0


35

⇑ VE

D – Nouvelle matrice transformée SRB = S1 x1 S3

Cj 600 540 375 0 0 0 Ci VB Qi x1 x2 x3 S1 S2 S3 Ri 0 S1 7 0 1 1 1 -1 0 7

600 x1 5 1 0 0 0 1 0 ∞ 0 S3 350 0 70 50 0 -80 1 5 ⇐VS Zj 3000 600 0 0 0 600 0 Cj - Zj 0 540 375 0 -600 0 ⇑

VE

E – Nouvelle matrice transformée SRB : S1 x1 x2

Cj 600 540 375 0 0 0 Ci VB Qi x1 x2 x3 S1 S2 S3 Ri

0 S1 2 0 0 27 1 1

7 - 170 14

600 x1 5 1 0 0 0 1 0 5 ⇐VS

540 x2 5 0 1 57 0 -87 1

70 -358

Zj 5700 600 540 385,71 0 -17,14 7.71 Cj - Zj 0 0 -10.71 0 17.14 -7.71

⇑ VE

La variable sortante est celle qui possède le ration le plus faible positif ! F – Nouvelle matrice transformée

SRB : S1 = 0 S2 = 0 x2 = 540

Cj 600 540 375 0 0 0 Ci VB Qi x1 x2 x3 S1 S2 S3

0 S1 97 -17 0 2

7 1 0 - 170

0 S2 5 1 0 0 0 1 0

540 x2 757 8

7 1 57 0 0 1

70

Zj 5785,71 617,14 540 385,71 0 0 7,71 Cj - Zj -17.14 0 -10.71 0 0 -7.71

Les Cj – Zj ≤ 0 ⇒ C’est la solution optimale x = 0

y = 757

Πmax = 5785.71


36

E x e r c i c e n ° 4 A - FG ⇒ FS

FG FS Max Z = 50 x1 + 60 x2

CS x1 + 2 x2 ≤ 8

2 x1 + 2 x2 ≤ 10 9 x1 + 4 x2 ≤ 36

avec x1 ≥ 0 et x2 ≥ 0

Max Z = 50 x1 + 60 x2 + 0 S1 + 0 S2 + 0 S3

CS x1 + 2 x2 +S1 = 8

2 x1 + 2 x2 + S2 = 10 9 x1 + 4 x2 + S3 = 36

avec x1 , x2 ≥ 0 et S1 , S2 , S3 ≥ 0 B – SRBi

S1 = 8 S2 = 10 S3 = 36 C – Tableau initial

Cj 50 60 0 0 0 Ci VB Qi x1 x2 S1 S2 S3 Ri 0 S1 8 1 2 1 0 0 4 ⇐VS 0 S2 10 2 2 0 1 0 5 0 S3 36 9 4 0 0 1 9 Zj 0 0 0 0 0 0 Cj - Zj 50 60 0 0 0 ⇑

VE

D – Nouvelle matrice transformée SRB = x2 S2 S3

Cj 50 60 0 0 0 Ci VB Qi x1 x2 S1 S2 S3 Ri 60 x2 4 1

2 1 12 0 0 8

0 S2 2 1 0 -1 1 0 2 ⇐VS 0 S3 20 7 0 -2 0 1 20

7

Zj 240 30 60 30 0 0 Cj - Zj 20 0 -30 0 0 ⇑

VE

E – Nouvelle matrice transformée SRB : x2 x1 S3

Cj 50 60 0 0 0 Ci VB Qi x1 x2 S1 S2 S3 60 x2 3 0 1 1 -12 0

50 x1 2 1 0 -1 1 0 0 S3 6 0 0 5 -7 1 Zj 280 50 60 10 20 0 Cj - Zj 0 0 -10 -20 0

Les Cj – Zj ≤ 0 ⇒ C’est la solution optimale.


37

x1 = 2 x2 = 3 Πmax = 280

E x e r c i c e n ° 5 A - FG ⇒ FS

FG FS Max Z = 7 x1 + 5 x2 + 5x3 +4 x4

CS 2 x1 + 4x2 +2x3 + 3 x4 ≤ 45000

x1 +x2 ≤ 6000 x3 +x4 ≤ 7000 x1 + x3 ≤ 5000 x2 + x4 ≤ 6000

avec x1 , x2 , x3 et x4 ≥ 0

Max Z = 7 x1 + 5 x2 + 5x3 +4 x4 + 0 S1 + 0 S2 + 0 S3 + S4 + 0 S5

CS 2 x1 + 4x2 +2x3 + 3 x4 + S1 = 45000

x1 +x2 + S2 = 6000 x3 +x4 + S3 = 7000

x1 + x3 + S4 = 5000 x2 + x4 + S5 = 6000

avec x1 , x2 , x3 et x4 ≥ 0 et S1 , S2 , S3 , S4 et S5 ≥ 0 B – SRBi

S1 = 45000 S2 = 6000 S3 = 7000 S4 = 5000 S5 = 6000 C – Tableau initial

Cj 7 5 5 4 0 0 0 0 0 Ci VB Qi x1 x2 x3 x4 S1 S2 S3 S4 S5 Ri 0 S1 45000 2 4 2 3 1 0 0 0 0 22500 0 S2 6000 1 1 0 0 0 1 0 0 0 6000 0 S3 7000 0 0 1 1 0 0 1 0 0 ∞ 0 S4 5000 1 0 1 0 0 0 0 1 0 5000 ⇐VS 0 S5 6000 0 1 0 1 0 0 0 0 1 ∞ Zj 0 0 0 0 0 0 0 0 0 0 Cj - Zj 7 5 5 4 0 0 0 0 0 ⇑

VE


SRB : S1 = 0 S2 = 0 S3 = 0 x1 = 7 S5 = 0 Cj 7 5 5 4 0 0 0 0 0

Ci VB Qi x1 x2 x3 x4 S1 S2 S3 S4 S5 Ri 0 S1 35000 0 4 0 3 1 0 0 -2 0 8750 0 S2 1000 0 1 -1 0 0 1 0 -1 0 1000 ⇐VS0 S3 7000 0 0 1 1 0 0 1 0 0 ∞ 7 x1 5000 1 0 1 0 0 0 0 1 0 ∞ 0 S5 6000 0 1 0 1 0 0 0 0 1 6000 Zj 35000 7 0 7 0 0 0 0 7 0 Cj - Zj 0 5 -2 4 0 0 0 -7 0


38

⇑ VE

E – Nouvelle matrice transformée SRB : S1 = 0 x2 = 5 S3 = 0 x1 = 7 S5 = 0

Cj 7 5 5 4 0 0 0 0 0 Ci VB Qi x1 x2 x3 x4 S1 S2 S3 S4 S5 Ri

0 S1 31000 0 0 4 3 1 -4 0 2 0 310003

5 x2 1000 0 1 -1 0 0 1 0 -1 0 ∞ 0 S3 7000 0 0 1 1 0 0 1 0 0 7000 7 x1 5000 1 0 1 0 0 0 0 1 0 ∞

0 S5 5000 0 0 1 1 0 -1 0 1 1 5000 ⇐VS

Zj 7 5 2 0 0 5 0 2 0 Cj - Zj 0 0 3 4 0 -5 0 -2 0 ⇑

VE

F – Nouvelle matrice transformée

SRB : S1 = 0 x2 = 5 S3 = 0 x1 = 7 x4 = 4 Cj 7 5 5 4 0 0 0 0 0

Ci VB Qi x1 x2 x3 x4 S1 S2 S3 S4 S5 0 S1 16000 0 0 1 0 1 -1 0 -1 -3 5 x2 1000 0 1 -1 0 0 1 0 -1 0 0 S3 2000 0 0 0 0 0 1 1 -1 -1 7 x1 5000 1 0 1 0 0 0 0 1 0 4 x4 5000 0 0 1 1 0 -1 0 1 1 Zj 60000 7 5 6 4 0 1 0 6 4 Cj - Zj 0 0 -1 0 0 -1 0 -6 -4


x1 = 5000 x2 = 1000 x3 = 0 x4 = 5000 Πmax = 60000


39


02

CHAPITRE 4

Méthode du Simplexe Problème de minimisation

& problèmes irréguliers

04 2005

I – I n t r o d u c t i o n Dans le chapitre précédent, tous les PL qu’on a traités étaient du type :

Maximiser une fonction linéaire

CS Contraintes

(avec un second membre positif )

< - >

Max ∑

Ci xj

CS ∑

aij xi ≤ bi ( avec bi ≥ 0 )

( avec xi ≥ 0 et j : 1 .. n )

Or, dans beaucoup de problèmes réels, on peut retrouver des contraintes du type ≥ et/ou = ainsi que des problèmes où l’on a à minimiser au lieu de maximiser.

Dans ce chapitre, on étudiera les modifications à apporter à la méthode du Simplexe pour qu’elle puisse résoudre tous ces types de programmes.

I I – P r o b l è m e s d e m i n i m i s a t i o n e t p r o b l è m e s a v e c c o n t r a i n t e s m i x t e s A – Cas de minimisation

Cas d’un problème de minimisation avec contraintes du type ≤ :

Min Z = ∑

Cj xj

CS ∑

aij xj ≤ bi

si, dans un PL, la fonction objectif doit être minimisée, on peut résoudre le PL : - En changeant la règle de choix de la variable et de la règle d’arrêt. On choisit comme variable

entrante celle dont l’introduction réduit le plus la fonction objectif, i.e. celle dont le Cj – Zj est le plus grand négatif ; on s’arrête quand il n’est plus possible de réduire la fonction objectif i.e. lorsque toutes les Cj – Zj sont positives ou nulles.

- ☺ On peut résoudre le PL en le réduisant à un problème de maximisation ; ceci peut être accompli en prenant l’opposé de la fonction objectif :

Min Z = ∑

Cj xj ⇔ Max ( -Z ) = (-Cj) xj , les contraintes fonctionnelles et les contraintes formelles restant les mêmes. Dans ce cas, on peut


40

utiliser la méthode décrite pour le cas de maximisation en changeant le critère de sélection des V.E. de Cj - Zj à Zj –Cj .

La solution est optimale lorsque Zj – Cj est négative ou nulle.

B – Cas des contraintes fonctionnelles mixtes : Technique des variables artificielles

Nous avons vu dans le chapitre précédent qu’un PL sous la Forme Générale : peut être facilement mis sous forme canonique en introduisant des variables d’écart. Cependant le PL original contient des contraintes du type (=) ou ( ≥ ) et/ou des éléments de bi qui ne sont pas tous non négatifs.

FG Max Z = ∑

Cj xj

CS ∑

aij xi ≤ bi avec bi ≥ 0

avec xj ≥ 0 j : 1 .. n

Il peut être mis sous forme standard facilement mais ne sera pas sous forme canonique. On introduit dans cette section une méthode utilisant des variables artificielles à la forme canonique. On passe par les étapes suivantes :

1re étape : On part d’un Pl sous FG

Max Z = ∑

Cj – xj

CS ∑

aij xj ≤ bi

∑

aij xj = bi

∑

aij xj ≥ bi avec xj ≥ 0

2ème étape : Mettre le PL sous FS par l’introduction de variables d’écart. Les contraintes deviennent :

CS ∑

aij xj + Si = bi

∑

aij xj = bi

∑

aij xj - Si = bi avec xj ≥ 0 et Si ≥ 0


41

3ème étape : On introduit les variables artificielles et les contraintes deviennent :

CS ∑

aij xj + Si = bi

∑

aij xj + Ai = bi

∑

aij xj - Si + Ai = bi avec xj ≥ 0 , Si ≥ 0 et Ai ≥0

Exemple de détermination de la F.C. avec des contraintes mixtes

F.G. Max Z = - x1 – x2

CS 3 x1 + x2 = 3

4 x1 + 3x2 ≥ 6 x1 + 2 x2 ≤ 3 avec x1 et x2 ≥ 0

F.S. Max Z = - x1 – x2

CS 3 x1 + x2 = 3

4 x1 + 3x2 – S1 = 6 x1 + 2 x2 + S2 = 3 avec x1 , x2 ≥ 0 et S1 , S2 ≥ 0

F.C.

Max Z = - x1 – x2 + 0 S1 + 0 S2

CS 3 x1 + x2 + A1 = 3

4 x1 + 3x2 – S1 + A2 = 6 x1 + 2 x2 + S2 = 3 avec x1 , x2 ≥ 0 , S1 , S2 ≥ 0 et A1 , A2 ≥ 0

La question qui se pose maintenant est : quels sont les coefficients des variables artificielles introduites

dans la base dans la fonction objectif ? L’idée des variables artificielles est de leur affecter des coefficients non nuls et d’essayer de les annuler ce qui permettrait de trouver une F.C. complète et aussi une solution de base possible. La méthode de pénalité « Big M »

Puisque dans une contrainte où l’on a introduit une variable artificielle qui est dans la base et qui peut être positive, la contrainte en question n’est pas satisfaite, il faut donc faire sortir ces variables artificielles rapidement de la base (en premier lieu) en vue d’obtenir une solution de base possible. Pour faire sortir ces variables de la base rapidement et en premier lieu, on leur affecte un coefficient pénalisateur très grand dans la fonction économique.

Soit M > > ( M très grand positif ) . On écrit la fonction objectif de la sorte : Max Z = ii A M - S 0 +∑ jj xC Exemple : Max Z = - 2 x1 – x2 + 0 S1 + 0 S2 – M A1 - M A2 ( avec M >> 0 )

Le PL n’est pas sous forme entièrement canonique, car les coefficients des variables artificielles qui font


42

partie des variables de base ne sont pas nuls. Pour résoudre un PL avec des contraintes mixtes, il faut suivre la procédure suivante :

Introduire des coefficients pénalisateurs très grands attachés aux variables artificielles dans la fonction objectif.

Appliquer la méthode du Simplexe. Deux cas se présentent : 1er cas : Une variable artificielle au moins reste dans la base avec une valeur positive. Le problème n’a pas de solution. Malgré le poids pénalisateur très grand attaché à cette variable, il n’est pas possible de la rendre nulle. 2ème cas : toutes les variables artificielles sortent de la base ou bien il reste certaines artificielles dans la base mais avec valeurs nulles : Une solution de base possible est trouvée : C’est la solution optimale.

Exemples applicatifs

Exemple de minimisation avec contraintes ≥

FG

Soit le PL suivant : Min C = - 24 x1 + 20 x2

CS x1 + x2 ≥ 30

x1 + 2 x2 ≥ 40 avec x1 et x2 ≥ 0

FS

Min C = - 24 x1 + 20 x2 + 0 S1 + 0 S2

CS x1 + x2 - S1 = 30

x1 + 2 x2 – S2 = 40 avec x1 , x2 ≥ 0 et S1 , S2 ≥ 0

FC

Min C = - 24 x1 + 20 x2 + 0 S1 + 0 S2 + M A1 + M A2

CS x1 + x2 - S1 + A1 = 30

x1 + 2 x2 – S2 + A2 = 40 avec x1 , x2 ≥ 0 et S1 , S2 ≥ 0

Remarque : cas de minimisation : + M Ai cas de maximisation : - M Ai

SRBi A1 = 30 A2 = 40


43

Tableau initial

Cj 24 20 0 0 M M Ci VB Qi x1 x2 S1 S2 A1 A2 Ri M A1 30 1 1 -1 0 1 0 30 M A2 40 1 2 0 -1 0 1 20 ⇐VS Zj 70 M 2 M 3 M -M -M M M Zj – Cj 2 M – 24 3 M –20 - M - M 0 0

⇑ VE

Remarque : Minimiser C =∑

Cj xj +∑

M Ai . On dit qu’on a pénalisé C, car M est très grand, donc

minimise C prend le signe + M. Or M est très grand et on cherche un minimum donc cela pénalise C.

Maximiser Z= ∑

Cj xj - ∑

M Ai . On pénalise Z, car M est très grand. Donc Maximiser Z prend le

signe de – M. Or nous cherchons un maximum donc cela pénalise Z.

2ème itération : Matrice transformée SRB : A1 = M x2 = 20

Cj 24 20 0 0 M Ci VB Qi x1 x2 S1 S2 A1 Ri

M A1 10 12 0 -1

12

1 20 ⇐VS

20 x2 20 12 1 0 -1

2 0 ∞

Zj 10 M + 400 M2 +10 20 -M M

2 -10 M

Zj – Cj M2 -14 0 -M M

2 -10 0

⇑ VE

3ème itération

SRB : S2 = 0 x2 = 20 Cj 24 20 0 0

Ci VB Q x1 x2 S1 S2

0 S2 20 1 0 -12 1

20 x2 30 1 1 -1 0 Zj 600 20 20 20 30 Zj – Cj -4 0 -20 0 Zj – Cj ≤ 0 ⇒ solution optimale x1 = 0 x2 = 20


44

C* = 600 Exemple de minimisation avec contraintes mixtes

Min C = 6 x1 + 4 x2

CS 3 x1 + 2 x2 ≥ 18

2 x1 + 4 x2 = 20 2 x2 ≤ 8 avec x1 et x2 ≥ 0

Exemple de maximisation avec contraintes mixtes Max Z = 4 x1 + 3 x2

CS x1 + x2 = 10

x1 + 3 x2 ≤ 20 2 x1 – x2 ≥ 15 avec x1 et x2 ≥ 0


45


09

CHAPITRE 4

Méthode du Simplexe Problème de minimisation

& problèmes irréguliers

04 2005

E x e m p l e d e m i n i m i s a t i o n a v e c c o n t r a i n t e s m i x t e s FG

Min C = 6 x1 + 4 x2

CS 3 x1 + 2 x2 ≥ 18

2 x1 + 4 x2 = 20 2 x2 ≤ 8 avec x1 et x2 ≥ 0

Fc Min C = 6 x1 + 4 x2 + 0 S1 + 0 S2 + M A1 + M A2

CS 3 x1 + 2 x2 – S1 + A1 = 18

2 x1 + 4 x2 + A2 = 20 2 x2 + S2 = 8 avec x1 , x2 ≥ 0 S1 , S2 ≥ 0 , A1 , A2 ≥ 0

SRBi A1 = 18 A2 = 20 S2 =8

Tableau initial

Cj 6 4 0 0 M M Ci VB Qi x1 x2 S1 S2 A1 A2 Ri M A1 18 3 2 -1 0 1 0 9 M A2 20 2 4 0 0 0 1 5 0 S2 8 0 2 0 1 0 0 4 ⇐VS Zj 38 M 5 M 6 M -M 0 M M Zj – Cj 5M-6 6M-4 -M 0 0 0

⇑ VE


46

Cj 6 4 0 0 M M

Ci VB Qi x1 x2 S1 S2 A1 A2 Ri

M A1 10 3 0 -1 -1 1 0 103

M A2 4 2 0 0 -2 0 1 2 ⇐VS 4 x2 4 0 1 0 ½ 0 0 ∞ Zj 14M+16 5 M 4 -M -3M+2 M M Zj – Cj 5M-6 0 0 -3M+2 0 0

⇑ VE

Cj 6 4 0 0 M

Ci VB Qi x1 x2 S1 S2 A1 Ri M A1 4 0 0 -1 2 1 2 ⇐VS6 x1 2 1 0 0 -1 0 ∞

4 x2 4 0 1 0 12 0 8

Zj 4M+28 6 4 -M 2M-4 M Zj – Cj 0 0 -M 2M-4 0

⇑ VE

Cj 6 4 0 0

Ci VB Qi x1 x2 S1 S2

0 S2 2 0 0 -12 1

6 x1 4 1 0 -12 0

4 x2 3 0 1 14 0

Zj 36 6 4 -2 0 Zj – Cj 0 0 -2 0

Zj – Cj ≤ 0 ⇒ Solution optimale ⎩⎪⎨⎪⎧ x1 = 4

x2 = 3 coût minimum=36

Remarque

Nous résumons les différentes variables à introduire dans le modèle pour obtenir un PL initial de base : A- Dans chaque contrainte de type (≤ ) additionner des variables d’écart . B- Dans chaque contrainte de type (≥) soustraire une variable d’écart et ajouter une variable artificielle. C- Dans chaque contrainte de type (=) additionner des variables artificielles.

E x e m p l e d e m a x i m i s a t i o n a v e c


47

c o n t r a i n t e s m i x t e s FG

Max Z = 4 x1 + 3 x2

CS x1 + x2 = 10

x1 + 3 x2 ≤ 20 2 x1 – x2 ≥ 15 avec x1 et x2 ≥ 0

FC Max Z = 4 x1 + 3 x2 + 0 S1 + 0 S2 – M A1 - M A2

CS x1 + x2 + A1 = 10

x1 + 3 x2 + S1 = 20 2 x1 – x2 – S2 + A2 = 15 avec x1 , x2 ≥ 0 , S1 , S2 ≥ 0 et A1 , A2 ≥ 0

SRBi A1 =10 S1 =20 A2 = 15

Tableau initial du Simplexe A compléter !


48

A u t r e m é t h o d e p o u r l a r è g l e d u p i v o t 1re étape

On divise la ligne pivot par l’élément pivot et l’on obtient la nouvelle ligne pivot. C’est ce qu’on appelle « normalisation de la ligne pivot ». 2ème étape

Pour transformer une ligne autre que celle du pivot, on opère des combinaisons linéaires entre la ligne considérée et la nouvelle ligne de pivot de manière à remplacer la colonne de pivot par une colonne unité.

Pour cela, on retranche de la ligne considérée le produit de la nouvelle ligne de pivot par al avec al étant l’élément de la ligne à transformer dans la colonne de pivot :

TL = L – al * TLP Avec TL = C’est la transformée d’une ligne quelconque. L = C’est la ligne à transformer. TLP = Transformée de la ligne de pivot.

Exemple : Soit le T.I. suivant :

Cj 25 15 0 0 Ci VB Qi x1 x2 S1 S2 Ri 0 S1 240 2 2 1 0 120

0 S2 140 3 1 0 1 1403 ⇐VS

Zj 0 0 0 0 0 Cj – Zj 25 15 0 0

⇑ VE

TLP 140 3 3

3 13 0

3 13

TLP 140 3 1 1

3 0 13

L 240 2 2 1 0 al = élément de la ligne à transformer dans la colonne pivot = 2

al * TLP 2 * 140 3 2 * 1 2 * 13 2 *0 2 * 13

al * TLP 2803 2 2

3 0 23

TL = Transformée de la ligne L = L – al * TLP

TL 240-2803 2-2 2-23 1-0 0- 23

TL 4403 0 4

3 1 -23


49

D’où le tableau suivant : Cj 25 15 0 0

Ci VB Qi x1 x2 S1 S2 Ri 0 S1 440/3 0 4/3 1 -2/3

25 x1 140/3 1 1/3 0 1/3 Zj Cj – Zj

I V – L e s p r o b l è m e s i r r é g u l i e r s a / Les problèmes impossibles

On reconnaît que le problème est impossible si une ou plusieurs variables artificielles sont présentes dans la base dans le tableau du Simplexe optimal, ce qui signifie que la solution donnée par ce tableau n’est pas réellement réalisable.

Exemple FG

Max 4 x1 + 3 x2

CS x1 + x2 ≤ 2

3 x1 + x2 ≥ 10 avec x1 et x2 ≥ 0

FC Max 4 x1 + 3 x2 + 0S1 + 0 S2 – M A1

CS x1 + x2 + S1 = 2

3 x1 + x2 – S2 + A1 = 10 avec x1 , x2 ≥ 0 , S1, S2 ≥ 0 et A1 , A2 ≥ 0

SRBi S1 = 2 A1 = 10

Tableau initial

Cj 4 3 0 0 -M Ci VB Qi x1 x2 S1 S2 A1 Ri 0 S1 2 1 1 1 0 0 2 ⇐VS

-M A1 10 3 1 0 -1 1 103

Zj -10M -3M -M 0 M -M Cj – Zj 3M+4 3+M 0 -M 0

⇑ VE


50

Cj 4 3 0 0 -M

Ci VB Qi x1 x2 S1 S2 A1 4 x1 2 1 1 1 0 0

-M A1 5 0 -2 -3 -1 1 Zj 8-5M 4 4+2M 4+3M M -M Cj – Zj 0 -1-2M -4-3M -M 0

Cj – Zj ≤ 0 , mais il existe encore une variable artificielle dans la base ⇒ Il s’agit donc d’un problème impossible.

b/ Problèmes à solutions multiples

On identifie ce problème lorsque, dans la solution optimale, un des effets nets (relatif à une variable hors base : S1, S2 , …) est nul.

Cj Ci VB Qi X1 x2 S1 S2 x1 x2 Zj Cj – Zj 0 0 0 -3

S1 : Variable hors base dont l’effet est nul.

c / Problèmes avec solutions infinies On reconnaît ce problème lorsque la variable rentrante n’admet aucune limite sur sa valeur d’entrée

c’est-à-dire que tous les ratios sont négatifs ou nuls. Exemple

FG Max x1 + 2 x2

CS x1 + x2 ≥ 2

x2 ≤ 3 avec x1 et x2 ≥ 0

FC Max x1 + 2 x2 + 0 S1 + 0 S2 – M A1

CS x1 + x2 – S1 + A1 = 2

x2 + S2 = 3 avec x1 , x2 ≥ 0 , S1, S2 ≥ 0 et A1 ≥ 0 Après quelques itérations, on trouve le tableau suivant :

Cj 1 2 0 0 Ci VB Qi x1 x2 S1 S2 Ri 2 x2 3 0 1 0 1 ∞ 0 S1 1 -1 0 1 1 -1 Zj 6 0 2 0 2 Cj – Zj 1 0 0 -2

⇑ VE

Ce tableau montre que la variable x2 n’admet aucune limite sur sa valeur de sortie : Donc la solution est infinie.

Ratios négatifs ou

nuls


51

d / Le problème à solution dégénérée Un PL est dit dégénéré si une ou plusieurs variables dans la base optimale sont nulles. Exemple

FG Max Z = 2 x1 + 32 x3

CS x1 – x2 ≤ 2

2 x1 + x3 ≤ 4 x1 + x2 + x3 ≤ 3 avec x1 , x2 et x3 ≥ 0

FS Max Z = 2 x1 + 32 x3 + 0 S1 + 0 S2 + 0 S3

CS x1 – x2 + S1 = 2

2 x1 + x3 + S2 = 4 x1 + x2 + x3 + S3 = 3 avec x1 , x2 et x3 ≥ 0 et S1 , S2 et S3 ≥ 0

Tableau initial Cj 2 0 3

2 0 0 0

Ci VB Qi x1 x2 x3 S1 S2 S3 Ri 0 S1 2 1 -1 0 1 0 0 2 0 S2 4 2 0 1 0 1 0 2 ⇐VS 0 S3 3 1 1 1 0 0 1 3 Zj 0 0 0 0 0 0 0

Cj – Zj 2 0 32 0 0 0

⇑ VE

La variable rentrante est x1 , mais les 2 premières contraintes donnent la même valeur minimale ( même ratio ) de ratio.

Ceci indique que lorsque x1 passe à 2, les variables d’écart S1 et S2 vont s’annuler bien que l’une des 2 demeure encore dans la base.

Dans ce cas, il faut choisir arbitrairement de faire sortir de la base l’une ou l’autre des deux variables d’écart S1 ou S2.

D’où le tableau suivant : ( on choisit de faire sortir S1 )

Cj 2 0 32 0 0 0

Ci VB Qi x1 x2 x3 S1 S2 S3 Ri 2 x1 2 1 -1 0 1 0 0 -2 0 S2 0 0 2 1 -2 1 0 0 ⇐VS 0 S3 1 0 2 1 -1 0 1 ½ Zj 4 2 -2 0 2 0 0

Cj – Zj 0 2 32 -2 0 0


52

⇑ VE

S2 est une variable de base qui est nulle et la valeur de la fonction objectif est égale à 4. Cette solution de base est donc dite dégénérée :

SRB ⎩⎪⎨⎪⎧x1=2S2=0S3=1

π = 4

Continuons les itérations relatives à la méthode du simplexe :

Cj 2 0 32 0 0 0

Ci VB Qi x1 x2 x3 S1 S2 S3 Ri 2 x1 2 1 0 ½ 0 ½ 0 4 0 x2 0 0 1 ½ -1 ½ 0 0 ⇐VS 0 S3 1 0 0 0 1 -1 1 ∞ Zj 4 2 0 0 0 1 0

Cj – Zj 0 0 32 0 -1 0

⇑ VE

Ce tableau n’est pas optimal . x2 est une variable de base qui est nulle et la valeur de la fonction objectif est toujours égale à 4. Cette solution de base est donc dite dégénérée.

SRB ⎩⎪⎨⎪⎧ x1=2

x2=0S3 =1

π = 4

On remarque que ce passage d’une solution à une autre solution ne s’accompagne pas d’une augmentation de la valeur de la fonction objectif.

On peut facilement vérifier que nous sommes en train de cycler sans atteindre la solution optimale. Ce genre de « cyclage » dans la méthode du simplexe est dangereux et on doit l’identifier avant de commencer à résoudre le problème sinon on passera un temps énorme sans atteindre la solution optimale.

N.B. Il faut noter que ce n’est pas tout problème de dégénérescence qui peut conduire à un cyclage.

Documents

chapitre