72
Cours 4 : m ´ ethode r ´ evis ´ ee du simplexe Christophe Gonzales LIP6 – Universit´ e Paris 6, France

Cours 4 : méthode révisée du simplexegonzales/teaching/optimisation/cours/cours04.pdf · En route vers la methode r´ evis´ ee´ Point de depart :´ a chaque it` eration du simplexe,

  • Upload
    ngongoc

  • View
    225

  • Download
    0

Embed Size (px)

Citation preview

Cours 4 : methode revisee du simplexe

Christophe Gonzales

LIP6 – Universite Paris 6, France

En route vers la methode revisee

Point de depart :

a chaque iteration du simplexe, on recalcule entierement letableauseule une petite partie du tableau sert pour une iterationdonnee

=⇒ perte de temps

principe de la methode revisee du simplexe

Essayer de reconstruire cette petite partie a partir du tableaud’origine=⇒ a priori, moins de calculs a effectuer

methode utilisee pour resoudre les gros problemes lineaires(milliers de variables et de contraintes), en general peu denses(beaucoup de 0)

Cours 4 : methode revisee du simplexe 2/21

En route vers la methode revisee

Point de depart :

a chaque iteration du simplexe, on recalcule entierement letableauseule une petite partie du tableau sert pour une iterationdonnee

=⇒ perte de temps

principe de la methode revisee du simplexe

Essayer de reconstruire cette petite partie a partir du tableaud’origine=⇒ a priori, moins de calculs a effectuer

methode utilisee pour resoudre les gros problemes lineaires(milliers de variables et de contraintes), en general peu denses(beaucoup de 0)

Cours 4 : methode revisee du simplexe 2/21

En route vers la methode revisee

Point de depart :

a chaque iteration du simplexe, on recalcule entierement letableauseule une petite partie du tableau sert pour une iterationdonnee

=⇒ perte de temps

principe de la methode revisee du simplexe

Essayer de reconstruire cette petite partie a partir du tableaud’origine=⇒ a priori, moins de calculs a effectuer

methode utilisee pour resoudre les gros problemes lineaires(milliers de variables et de contraintes), en general peu denses(beaucoup de 0)

Cours 4 : methode revisee du simplexe 2/21

Relation tableau a l’iteration n – tableau d’origine (1/6)

Probleme de depart :

max 19x1 + 13x2 + 12x3 + 17x4s.c. 3x1 + 2x2 + x3 + 2x4 ≤ 255

x1 + x2 + x3 + x4 ≤ 1174x1 + 3x2 + 3x3 + 4x4 ≤ 420

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0

Introduction des variables d’ecart :

max 19x1 + 13x2 + 12x3 + 17x4s.c. 3x1 + 2x2 + x3 + 2x4 + x5 = 255

x1 + x2 + x3 + x4 + x6 = 1174x1 + 3x2 + 3x3 + 4x4 + x7 = 420

x1, x2, x3, x4, x5, x6, x7 ≥ 0

Cours 4 : methode revisee du simplexe 3/21

Relation tableau a l’iteration n – tableau d’origine (1/6)

Probleme de depart :

max 19x1 + 13x2 + 12x3 + 17x4s.c. 3x1 + 2x2 + x3 + 2x4 ≤ 255

x1 + x2 + x3 + x4 ≤ 1174x1 + 3x2 + 3x3 + 4x4 ≤ 420

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0

Introduction des variables d’ecart :

max 19x1 + 13x2 + 12x3 + 17x4s.c. 3x1 + 2x2 + x3 + 2x4 + x5 = 255

x1 + x2 + x3 + x4 + x6 = 1174x1 + 3x2 + 3x3 + 4x4 + x7 = 420

x1, x2, x3, x4, x5, x6, x7 ≥ 0

Cours 4 : methode revisee du simplexe 3/21

Relation tableau a l’iteration n – tableau d’origine (2/6)

Tableau d’origine :

3x1 + 2x2 + x3 + 2x4 + x5 = 255x1 + x2 + x3 + x4 + x6 = 117

4x1 + 3x2 + 3x3 + 4x4 + x7 = 420−z + 19x1 + 13x2 + 12x3 + 17x4 = 0

=⇒ base realisable = (x5, x6, x7)

Cours 4 : methode revisee du simplexe 4/21

Relation tableau a l’iteration n – tableau d’origine (2/6)

Tableau d’origine :

3x1 + 2x2 + x3 + 2x4 + x5 = 255x1 + x2 + x3 + x4 + x6 = 117

4x1 + 3x2 + 3x3 + 4x4 + x7 = 420−z + 19x1 + 13x2 + 12x3 + 17x4 = 0

Premiere iteration : faire entrer x1 et sortir x5 :

x1 + 23x2 + 1

3x3 + 23x4 + 1

3x5 = 8513x2 + 2

3x3 + 13x4 − 1

3x5 + x6 = 3213x2 + 5

3x3 + 43x4 − 4

3x5 + x7 = 80

−z + 13x2 + 17

3 x3 + 133 x4 − 19

3 x5 = −1615

Cours 4 : methode revisee du simplexe 4/21

Relation tableau a l’iteration n – tableau d’origine (3/6)

base (x1, x6, x7) = (85, 32, 80) =⇒ x2, x3, x4, x5 = 0

operations algebriques =⇒ toute solution realisable d’untableau est aussi solution realisable des tableaux precedents

Cours 4 : methode revisee du simplexe 5/21

Relation tableau a l’iteration n – tableau d’origine (3/6)

base (x1, x6, x7) = (85, 32, 80) =⇒ x2, x3, x4, x5 = 0

operations algebriques =⇒ toute solution realisable d’untableau est aussi solution realisable des tableaux precedents

Tableau d’origine :

3x1 + 2x2 + x3 + 2x4 + x5 = 255x1 + x2 + x3 + x4 + x6 = 117

4x1 + 3x2 + 3x3 + 4x4 + x7 = 420

Cours 4 : methode revisee du simplexe 5/21

Relation tableau a l’iteration n – tableau d’origine (3/6)

base (x1, x6, x7) = (85, 32, 80) =⇒ x2, x3, x4, x5 = 0

operations algebriques =⇒ toute solution realisable d’untableau est aussi solution realisable des tableaux precedents

Tableau d’origine :

3x1 = 255x1 + x6 = 117

4x1 + x7 = 420

Cours 4 : methode revisee du simplexe 5/21

Relation tableau a l’iteration n – tableau d’origine (3/6)

base (x1, x6, x7) = (85, 32, 80) =⇒ x2, x3, x4, x5 = 0

operations algebriques =⇒ toute solution realisable d’untableau est aussi solution realisable des tableaux precedents

Tableau d’origine : Premiere iteration :

3x1 = 255 x1 = 85x1 + x6 = 117 x6 = 32

4x1 + x7 = 420 x7 = 80

Cours 4 : methode revisee du simplexe 5/21

Relation tableau a l’iteration n – tableau d’origine (3/6)

base (x1, x6, x7) = (85, 32, 80) =⇒ x2, x3, x4, x5 = 0

operations algebriques =⇒ toute solution realisable d’untableau est aussi solution realisable des tableaux precedents

Tableau d’origine : Premiere iteration :

3x1 = 255 x1 = 85x1 + x6 = 117 x6 = 32

4x1 + x7 = 420 x7 = 80︸ ︷︷ ︸B

︸︷︷︸b

Cours 4 : methode revisee du simplexe 5/21

Relation tableau a l’iteration n – tableau d’origine (3/6)

base (x1, x6, x7) = (85, 32, 80) =⇒ x2, x3, x4, x5 = 0

operations algebriques =⇒ toute solution realisable d’untableau est aussi solution realisable des tableaux precedents

Tableau d’origine : Premiere iteration :

3x1 = 255 x1 = 85x1 + x6 = 117 x6 = 32

4x1 + x7 = 420 x7 = 80︸ ︷︷ ︸B

︸︷︷︸b

︸ ︷︷ ︸B−1B

Cours 4 : methode revisee du simplexe 5/21

Relation tableau a l’iteration n – tableau d’origine (3/6)

base (x1, x6, x7) = (85, 32, 80) =⇒ x2, x3, x4, x5 = 0

operations algebriques =⇒ toute solution realisable d’untableau est aussi solution realisable des tableaux precedents

Tableau d’origine : Premiere iteration :

3x1 = 255 x1 = 85x1 + x6 = 117 x6 = 32

4x1 + x7 = 420 x7 = 80︸ ︷︷ ︸B

︸︷︷︸b

︸ ︷︷ ︸B−1B

︸︷︷︸B−1b

Cours 4 : methode revisee du simplexe 5/21

Relation tableau a l’iteration n – tableau d’origine (3/6)

base (x1, x6, x7) = (85, 32, 80) =⇒ x2, x3, x4, x5 = 0

operations algebriques =⇒ toute solution realisable d’untableau est aussi solution realisable des tableaux precedents

Tableau d’origine : Premiere iteration :

3x1 = 255 x1 = 85x1 + x6 = 117 x6 = 32

4x1 + x7 = 420 x7 = 80︸ ︷︷ ︸B

︸︷︷︸b

︸ ︷︷ ︸B−1B

︸︷︷︸B−1b

=⇒ les tableaux du simplexe s’expriment en fonction de B−1

Cours 4 : methode revisee du simplexe 5/21

Relation tableau a l’iteration n – tableau d’origine (4/6)probleme a resoudre :max cT x

s.c.

{Ax = bx ≥ 0

base realisable =⇒ x =

[xBxN

]:

xB = (x1, x6, x7) xN = (x2, x3, x4, x5)

A = [ B N ] :x1 x2 x3 x4 x5 x6 x7 3 2 1 2 1 0 01 1 1 1 0 1 04 3 3 4 0 0 1

Ax = BxB + NxN

Ax = b =⇒ xB = B−1b − B−1NxN

Cours 4 : methode revisee du simplexe 6/21

Relation tableau a l’iteration n – tableau d’origine (4/6)probleme a resoudre :max cT x

s.c.

{Ax = bx ≥ 0

base realisable =⇒ x =

[xBxN

]:

xB = (x1, x6, x7) xN = (x2, x3, x4, x5)

A = [ B N ] :x1 x2 x3 x4 x5 x6 x7 3 2 1 2 1 0 01 1 1 1 0 1 04 3 3 4 0 0 1

Ax = BxB + NxN

Ax = b =⇒ xB = B−1b − B−1NxN

Cours 4 : methode revisee du simplexe 6/21

Relation tableau a l’iteration n – tableau d’origine (4/6)probleme a resoudre :max cT x

s.c.

{Ax = bx ≥ 0

base realisable =⇒ x =

[xBxN

]:

xB = (x1, x6, x7) xN = (x2, x3, x4, x5)

A = [ B N ] :x1 x2 x3 x4 x5 x6 x7 3 2 1 2 1 0 01 1 1 1 0 1 04 3 3 4 0 0 1

Ax = BxB + NxN

Ax = b =⇒ xB = B−1b − B−1NxN

Cours 4 : methode revisee du simplexe 6/21

Relation tableau a l’iteration n – tableau d’origine (4/6)probleme a resoudre :max cT x

s.c.

{Ax = bx ≥ 0

base realisable =⇒ x =

[xBxN

]:

xB = (x1, x6, x7) xN = (x2, x3, x4, x5)A = [ B N ] :

x1 x2 x3 x4 x5 x6 x7 3 2 1 2 1 0 01 1 1 1 0 1 04 3 3 4 0 0 1

=

3 0 01 1 04 0 1

︸ ︷︷ ︸

B

Ax = BxB + NxN

Ax = b =⇒ xB = B−1b − B−1NxN

Cours 4 : methode revisee du simplexe 6/21

Relation tableau a l’iteration n – tableau d’origine (4/6)probleme a resoudre :max cT x

s.c.

{Ax = bx ≥ 0

base realisable =⇒ x =

[xBxN

]:

xB = (x1, x6, x7) xN = (x2, x3, x4, x5)A = [ B N ] :

x1 x2 x3 x4 x5 x6 x7 3 2 1 2 1 0 01 1 1 1 0 1 04 3 3 4 0 0 1

=

3 0 01 1 04 0 1

2 1 2 11 1 1 03 3 4 0

︸ ︷︷ ︸

B︸ ︷︷ ︸

N

Ax = BxB + NxN

Ax = b =⇒ xB = B−1b − B−1NxN

Cours 4 : methode revisee du simplexe 6/21

Relation tableau a l’iteration n – tableau d’origine (4/6)probleme a resoudre :max cT x

s.c.

{Ax = bx ≥ 0

base realisable =⇒ x =

[xBxN

]:

xB = (x1, x6, x7) xN = (x2, x3, x4, x5)A = [ B N ] :

x1 x2 x3 x4 x5 x6 x7 3 2 1 2 1 0 01 1 1 1 0 1 04 3 3 4 0 0 1

=

3 0 01 1 04 0 1

2 1 2 11 1 1 03 3 4 0

︸ ︷︷ ︸

B︸ ︷︷ ︸

NAx = BxB + NxN

Ax = b =⇒ xB = B−1b − B−1NxN

Cours 4 : methode revisee du simplexe 6/21

Relation tableau a l’iteration n – tableau d’origine (4/6)probleme a resoudre :max cT x

s.c.

{Ax = bx ≥ 0

base realisable =⇒ x =

[xBxN

]:

xB = (x1, x6, x7) xN = (x2, x3, x4, x5)A = [ B N ] :

x1 x2 x3 x4 x5 x6 x7 3 2 1 2 1 0 01 1 1 1 0 1 04 3 3 4 0 0 1

=

3 0 01 1 04 0 1

2 1 2 11 1 1 03 3 4 0

︸ ︷︷ ︸

B︸ ︷︷ ︸

NAx = BxB + NxN

Ax = b =⇒ xB = B−1b − B−1NxN

Cours 4 : methode revisee du simplexe 6/21

Relation tableau a l’iteration n – tableau d’origine (5/6)

x =

[xBxN

]=⇒ cT =

[cT

B cTN

]z = cT x = 19x1 + 13x2 + 12x3 + 17x4

=⇒ cT = [19 13 12 17 0 0 0]

=⇒ cTB = [19 0 0] et cT

N = [13 12 17 0]

cT x = cTB xB + cT

NxN

xB = B−1b − B−1NxN =⇒ cTB xB = cT

B B−1b − cTB B−1NxN

z = cTB xB + cT

NxN =⇒ z = cTB B−1b − cT

B B−1NxN + cTNxN

=⇒ z = cTB B−1b + (cT

N − cTB B−1N)xN

Cours 4 : methode revisee du simplexe 7/21

Relation tableau a l’iteration n – tableau d’origine (5/6)

x =

[xBxN

]=⇒ cT =

[cT

B cTN

]z = cT x = 19x1 + 13x2 + 12x3 + 17x4

=⇒ cT = [19 13 12 17 0 0 0]

=⇒ cTB = [19 0 0] et cT

N = [13 12 17 0]

cT x = cTB xB + cT

NxN

xB = B−1b − B−1NxN =⇒ cTB xB = cT

B B−1b − cTB B−1NxN

z = cTB xB + cT

NxN =⇒ z = cTB B−1b − cT

B B−1NxN + cTNxN

=⇒ z = cTB B−1b + (cT

N − cTB B−1N)xN

Cours 4 : methode revisee du simplexe 7/21

Relation tableau a l’iteration n – tableau d’origine (5/6)

x =

[xBxN

]=⇒ cT =

[cT

B cTN

]z = cT x = 19x1 + 13x2 + 12x3 + 17x4

=⇒ cT = [19 13 12 17 0 0 0]

=⇒ cTB = [19 0 0] et cT

N = [13 12 17 0]

cT x = cTB xB + cT

NxN

xB = B−1b − B−1NxN =⇒ cTB xB = cT

B B−1b − cTB B−1NxN

z = cTB xB + cT

NxN =⇒ z = cTB B−1b − cT

B B−1NxN + cTNxN

=⇒ z = cTB B−1b + (cT

N − cTB B−1N)xN

Cours 4 : methode revisee du simplexe 7/21

Relation tableau a l’iteration n – tableau d’origine (5/6)

x =

[xBxN

]=⇒ cT =

[cT

B cTN

]z = cT x = 19x1 + 13x2 + 12x3 + 17x4

=⇒ cT = [19 13 12 17 0 0 0]

=⇒ cTB = [19 0 0] et cT

N = [13 12 17 0]

cT x = cTB xB + cT

NxN

xB = B−1b − B−1NxN =⇒ cTB xB = cT

B B−1b − cTB B−1NxN

z = cTB xB + cT

NxN =⇒ z = cTB B−1b − cT

B B−1NxN + cTNxN

=⇒ z = cTB B−1b + (cT

N − cTB B−1N)xN

Cours 4 : methode revisee du simplexe 7/21

Relation tableau a l’iteration n – tableau d’origine (6/6)

Definition d’un dictionnaireB = base, N = hors basexB = B−1b − B−1NxN

z = cTB B−1b + (cT

N − cTB B−1N)xN

=⇒ methode revisee du simplexe

Cours 4 : methode revisee du simplexe 8/21

Methode revisee du simplexe (1/8)

A chaque iteration de l’algorithme :

1 choisir une variable entrante2 choisir une variable sortante =⇒ (xB, xN)

3 faire une mise a jour de la solution realisable : xB

Exemple :

3x1 + 2x2 + x3 + 2x4 + x5 = 255x1 + x2 + x3 + x4 + x6 = 117

4x1 + 3x2 + 3x3 + 4x4 + x7 = 420−z + 19x1 + 13x2 + 12x3 + 17x4 = 0

=⇒ B =

3 0 01 1 04 0 1

xB = B−1b =

x1x6x7

=

853280

Cours 4 : methode revisee du simplexe 9/21

Methode revisee du simplexe (2/8)prochaine variable entrante : une variable dont le coefficientdans z est positif =⇒ calculer z

calcul de z = cTB B−1b + (cT

N − cTB B−1N)xN :

1 calculer yT = cTB B−1 =⇒ resoudre le systeme yT B = cT

B :

[y1 y2 y3] ·

3 0 01 1 04 0 1

= cTB = [19 0 0] =⇒ yT =

[193 0 0

]2 calculer hT = yT N :

hT = yT N =[19

3 0 0] 2 1 2 1

1 1 1 03 3 4 0

=[38

3193

383

193

]3 calculer cT

N = cTN − cT

B B−1N = cTN − hT :

cTN = [13 12 17 0]−

[383

193

383

193

]=[1

3173

133

−193

]

Cours 4 : methode revisee du simplexe 10/21

Methode revisee du simplexe (2/8)prochaine variable entrante : une variable dont le coefficientdans z est positif =⇒ calculer z

calcul de z = cTB B−1b + (cT

N − cTB B−1N)xN :

1 calculer yT = cTB B−1 =⇒ resoudre le systeme yT B = cT

B :

[y1 y2 y3] ·

3 0 01 1 04 0 1

= cTB = [19 0 0] =⇒ yT =

[193 0 0

]2 calculer hT = yT N :

hT = yT N =[19

3 0 0] 2 1 2 1

1 1 1 03 3 4 0

=[38

3193

383

193

]3 calculer cT

N = cTN − cT

B B−1N = cTN − hT :

cTN = [13 12 17 0]−

[383

193

383

193

]=[1

3173

133

−193

]

Cours 4 : methode revisee du simplexe 10/21

Methode revisee du simplexe (2/8)prochaine variable entrante : une variable dont le coefficientdans z est positif =⇒ calculer z

calcul de z = cTB B−1b + (cT

N − cTB B−1N)xN :

1 calculer yT = cTB B−1 =⇒ resoudre le systeme yT B = cT

B :

[y1 y2 y3] ·

3 0 01 1 04 0 1

= cTB = [19 0 0] =⇒ yT =

[193 0 0

]

2 calculer hT = yT N :

hT = yT N =[19

3 0 0] 2 1 2 1

1 1 1 03 3 4 0

=[38

3193

383

193

]3 calculer cT

N = cTN − cT

B B−1N = cTN − hT :

cTN = [13 12 17 0]−

[383

193

383

193

]=[1

3173

133

−193

]

Cours 4 : methode revisee du simplexe 10/21

Methode revisee du simplexe (2/8)prochaine variable entrante : une variable dont le coefficientdans z est positif =⇒ calculer z

calcul de z = cTB B−1b + (cT

N − cTB B−1N)xN :

1 calculer yT = cTB B−1 =⇒ resoudre le systeme yT B = cT

B :

[y1 y2 y3] ·

3 0 01 1 04 0 1

= cTB = [19 0 0] =⇒ yT =

[193 0 0

]2 calculer hT = yT N :

hT = yT N =[19

3 0 0] 2 1 2 1

1 1 1 03 3 4 0

=[38

3193

383

193

]

3 calculer cTN = cT

N − cTB B−1N = cT

N − hT :

cTN = [13 12 17 0]−

[383

193

383

193

]=[1

3173

133

−193

]

Cours 4 : methode revisee du simplexe 10/21

Methode revisee du simplexe (2/8)prochaine variable entrante : une variable dont le coefficientdans z est positif =⇒ calculer z

calcul de z = cTB B−1b + (cT

N − cTB B−1N)xN :

1 calculer yT = cTB B−1 =⇒ resoudre le systeme yT B = cT

B :

[y1 y2 y3] ·

3 0 01 1 04 0 1

= cTB = [19 0 0] =⇒ yT =

[193 0 0

]2 calculer hT = yT N :

hT = yT N =[19

3 0 0] 2 1 2 1

1 1 1 03 3 4 0

=[38

3193

383

193

]3 calculer cT

N = cTN − cT

B B−1N = cTN − hT :

cTN = [13 12 17 0]−

[383

193

383

193

]=[1

3173

133

−193

]Cours 4 : methode revisee du simplexe 10/21

Methode revisee du simplexe (3/8)

=⇒ cTN =

[13

173

133

−193

]

Apres la premiere iteration du simplexe :

x1 + 23x2 + 1

3x3 + 23x4 + 1

3x5 = 8513x2 + 2

3x3 + 13x4 − 1

3x5 + x6 = 3213x2 + 5

3x3 + 43x4 − 4

3x5 + x7 = 80

−z + 13x2 + 17

3 x3 + 133 x4 − 19

3 x5 = −1615

cTN = cT

N − cTB B−1N = coeffs hors base de la fonction objectif

pour la base (x1, x6, x7)

Cours 4 : methode revisee du simplexe 11/21

Methode revisee du simplexe (4/8)

cTN =

[13

173

133

−193

]choix de la variable entrante : n’importe quelle variable de coeffpositif dans cT

N

cTN = cT

N − cTB B−1N = cT

N − yT N

= [13 12 17 0]−[19

3 0 0] 2 1 2 1

1 1 1 03 3 4 0

=⇒ on n’est pas oblige de calculer tout cTN :

e.g., calculer cTN colonne par colonne et s’arreter quand on a un

nombre positif

Cours 4 : methode revisee du simplexe 12/21

Methode revisee du simplexe (4/8)

cTN =

[13

173

133

−193

]choix de la variable entrante : n’importe quelle variable de coeffpositif dans cT

N

cTN = cT

N − cTB B−1N = cT

N − yT N

= [13 12 17 0]−[19

3 0 0] 2 1 2 1

1 1 1 03 3 4 0

=⇒ on n’est pas oblige de calculer tout cTN :

e.g., calculer cTN colonne par colonne et s’arreter quand on a un

nombre positif

Cours 4 : methode revisee du simplexe 12/21

Methode revisee du simplexe (4/8)

cTN =

[13

173

133

−193

]choix de la variable entrante : n’importe quelle variable de coeffpositif dans cT

N

cTN = cT

N − cTB B−1N = cT

N − yT N

= [13 12 17 0]−[19

3 0 0] 2 1 2 1

1 1 1 03 3 4 0

=[1

3

=⇒ on n’est pas oblige de calculer tout cTN :

e.g., calculer cTN colonne par colonne et s’arreter quand on a un

nombre positif

Cours 4 : methode revisee du simplexe 12/21

Methode revisee du simplexe (4/8)

cTN =

[13

173

133

−193

]choix de la variable entrante : n’importe quelle variable de coeffpositif dans cT

N

cTN = cT

N − cTB B−1N = cT

N − yT N

= [13 12 17 0]−[19

3 0 0] 2 1 2 1

1 1 1 03 3 4 0

=[1

3173

=⇒ on n’est pas oblige de calculer tout cTN :

e.g., calculer cTN colonne par colonne et s’arreter quand on a un

nombre positif

Cours 4 : methode revisee du simplexe 12/21

Methode revisee du simplexe (4/8)

cTN =

[13

173

133

−193

]choix de la variable entrante : n’importe quelle variable de coeffpositif dans cT

N

cTN = cT

N − cTB B−1N = cT

N − yT N

= [13 12 17 0]−[19

3 0 0] 2 1 2 1

1 1 1 03 3 4 0

=[1

3173

133

=⇒ on n’est pas oblige de calculer tout cTN :

e.g., calculer cTN colonne par colonne et s’arreter quand on a un

nombre positif

Cours 4 : methode revisee du simplexe 12/21

Methode revisee du simplexe (4/8)

cTN =

[13

173

133

−193

]choix de la variable entrante : n’importe quelle variable de coeffpositif dans cT

N

cTN = cT

N − cTB B−1N = cT

N − yT N

= [13 12 17 0]−[19

3 0 0] 2 1 2 1

1 1 1 03 3 4 0

=[1

3173

133

−193

]

=⇒ on n’est pas oblige de calculer tout cTN :

e.g., calculer cTN colonne par colonne et s’arreter quand on a un

nombre positif

Cours 4 : methode revisee du simplexe 12/21

Methode revisee du simplexe (4/8)

cTN =

[13

173

133

−193

]choix de la variable entrante : n’importe quelle variable de coeffpositif dans cT

N

cTN = cT

N − cTB B−1N = cT

N − yT N

= [13 12 17 0]−[19

3 0 0] 2 1 2 1

1 1 1 03 3 4 0

=[1

3173

133

−193

]=⇒ on n’est pas oblige de calculer tout cT

N :

e.g., calculer cTN colonne par colonne et s’arreter quand on a un

nombre positif

Cours 4 : methode revisee du simplexe 12/21

Methode revisee du simplexe (5/8)

cTN =

[13

173

133

−193

]xB = B−1b =

x1x6x7

=

853280

3x1 + 2x2 + x3 + 2x4 + x5 = 255

x1 + x2 + x3 + x4 + x6 = 1174x1 + 3x2 + 3x3 + 4x4 + x7 = 420

−z + 19x1 + 13x2 + 12x3 + 17x4 = 0

choix de la variable entrante : x3

=⇒ augmenter la valeur de x3 tout en assurant que les valeursde xB restent positives

BxB + NxN = b =⇒ xB = B−1b − B−1NxN

soit a la colonne de N correspondant a x3 =⇒ xB = B−1b − B−1ax3

Cours 4 : methode revisee du simplexe 13/21

Methode revisee du simplexe (5/8)

cTN =

[13

173

133

−193

]xB = B−1b =

x1x6x7

=

853280

3x1 + 2x2 + x3 + 2x4 + x5 = 255

x1 + x2 + x3 + x4 + x6 = 1174x1 + 3x2 + 3x3 + 4x4 + x7 = 420

−z + 19x1 + 13x2 + 12x3 + 17x4 = 0

choix de la variable entrante : x3

=⇒ augmenter la valeur de x3 tout en assurant que les valeursde xB restent positives

BxB + NxN = b =⇒ xB = B−1b − B−1NxN

soit a la colonne de N correspondant a x3 =⇒ xB = B−1b − B−1ax3

Cours 4 : methode revisee du simplexe 13/21

Methode revisee du simplexe (6/8)

soit a la colonne de N correspondant a x3 =⇒ xB = B−1b − B−1ax3

calcul de d = B−1a : resoudre Bd = a :

3 0 01 1 04 0 1

d1d2d3

=

113

=⇒ d =

132353

=⇒

x1

x6

x7

=

85

32

80

− x3 ×

132353

≥ 0

0

0

=⇒ valeur max de x3 = 48 (ligne de x6) =⇒ x6 sort de la base

Cours 4 : methode revisee du simplexe 14/21

Methode revisee du simplexe (6/8)

soit a la colonne de N correspondant a x3 =⇒ xB = B−1b − B−1ax3

calcul de d = B−1a : resoudre Bd = a :

3 0 01 1 04 0 1

d1d2d3

=

113

=⇒ d =

132353

=⇒

x1

x6

x7

=

85

32

80

− x3 ×

132353

≥ 0

0

0

=⇒ valeur max de x3 = 48 (ligne de x6) =⇒ x6 sort de la base

Cours 4 : methode revisee du simplexe 14/21

Methode revisee du simplexe (6/8)

soit a la colonne de N correspondant a x3 =⇒ xB = B−1b − B−1ax3

calcul de d = B−1a : resoudre Bd = a :

3 0 01 1 04 0 1

d1d2d3

=

113

=⇒ d =

132353

=⇒

x1

x6

x7

=

85

32

80

− x3 ×

132353

≥ 0

0

0

=⇒ valeur max de x3 = 48 (ligne de x6) =⇒ x6 sort de la base

Cours 4 : methode revisee du simplexe 14/21

Methode revisee du simplexe (7/8)

d =

132353

Apres la premiere iteration du simplexe :

x1 + 23x2 + 1

3x3 + 23x4 + 1

3x5 = 8513x2 + 2

3x3 + 13x4 − 1

3x5 + x6 = 3213x2 + 5

3x3 + 43x4 − 4

3x5 + x7 = 80

−z + 13x2 + 17

3 x3 + 133 x4 − 19

3 x5 = −1615

=⇒ d = colonne de x3 apres la premiere iteration du simplexe

Cours 4 : methode revisee du simplexe 15/21

Methode revisee du simplexe (8/8)

Apres la premiere iteration du simplexe :

x1 + 12x2 + 1

2x4 + 12x5 − 1

2x6 = 6912x2 + x3 + 1

2x4 − 12x5 + 3

2x6 = 48

−12x2 + 1

2x4 − 12x5 − 5

2x6 + x7 = 0

−z − 52x2 + 3

2x4 − 72x5 − 17

2 x6 = −1887

d =

132353

=⇒ xB − 48× d =

85

32

80

− 48×

132353

=

69

0

0

xB − 48d =⇒ valeurs des variables en base =⇒ nouvel xB

Cours 4 : methode revisee du simplexe 16/21

Methode revisee du simplexe (8/8)

Apres la premiere iteration du simplexe :

x1 + 12x2 + 1

2x4 + 12x5 − 1

2x6 = 6912x2 + x3 + 1

2x4 − 12x5 + 3

2x6 = 48

−12x2 + 1

2x4 − 12x5 − 5

2x6 + x7 = 0

−z − 52x2 + 3

2x4 − 72x5 − 17

2 x6 = −1887

d =

132353

=⇒ xB − 48× d =

85

32

80

− 48×

132353

=

69

0

0

xB − 48d =⇒ valeurs des variables en base =⇒ nouvel xB

Cours 4 : methode revisee du simplexe 16/21

Synthese sur la methode revisee du simplexe

Iteration de l’algorithme revise du simplexe

B = base courante xB = valeur de la solution courante1 calculer yT tel que yT B = cT

B (=⇒ yT = cTB B−1)

2 choisir une colonne entrante : n’importe quelle colonne ade N telle que cT

a > yT a, ou cTa = coeff de la colonne a

dans cT

3 calculer d tel que Bd = a (=⇒ d ≈ valeur de la colonne aapres iteration du simplexe)

4 trouver le plus grand nombre t tel que xB − td ≥ 0si t = +∞ : probleme non bornesinon : au moins 1 ligne = 0 =⇒ variable sortant de la base

5 remplacer xB par xB − td , puis la ligne correspondant a lavariable sortante par t

6 remplacer dans B la colonne de la variable sortante parcelle de la variable entrante

Cours 4 : methode revisee du simplexe 17/21

Synthese sur la methode revisee du simplexe

Iteration de l’algorithme revise du simplexe

B = base courante xB = valeur de la solution courante1 calculer yT tel que yT B = cT

B (=⇒ yT = cTB B−1)

2 choisir une colonne entrante : n’importe quelle colonne ade N telle que cT

a > yT a, ou cTa = coeff de la colonne a

dans cT

3 calculer d tel que Bd = a (=⇒ d ≈ valeur de la colonne aapres iteration du simplexe)

4 trouver le plus grand nombre t tel que xB − td ≥ 0si t = +∞ : probleme non bornesinon : au moins 1 ligne = 0 =⇒ variable sortant de la base

5 remplacer xB par xB − td , puis la ligne correspondant a lavariable sortante par t

6 remplacer dans B la colonne de la variable sortante parcelle de la variable entrante

Cours 4 : methode revisee du simplexe 17/21

Synthese sur la methode revisee du simplexe

Iteration de l’algorithme revise du simplexe

B = base courante xB = valeur de la solution courante1 calculer yT tel que yT B = cT

B (=⇒ yT = cTB B−1)

2 choisir une colonne entrante : n’importe quelle colonne ade N telle que cT

a > yT a, ou cTa = coeff de la colonne a

dans cT

3 calculer d tel que Bd = a (=⇒ d ≈ valeur de la colonne aapres iteration du simplexe)

4 trouver le plus grand nombre t tel que xB − td ≥ 0si t = +∞ : probleme non bornesinon : au moins 1 ligne = 0 =⇒ variable sortant de la base

5 remplacer xB par xB − td , puis la ligne correspondant a lavariable sortante par t

6 remplacer dans B la colonne de la variable sortante parcelle de la variable entrante

Cours 4 : methode revisee du simplexe 17/21

Synthese sur la methode revisee du simplexe

Iteration de l’algorithme revise du simplexe

B = base courante xB = valeur de la solution courante1 calculer yT tel que yT B = cT

B (=⇒ yT = cTB B−1)

2 choisir une colonne entrante : n’importe quelle colonne ade N telle que cT

a > yT a, ou cTa = coeff de la colonne a

dans cT

3 calculer d tel que Bd = a (=⇒ d ≈ valeur de la colonne aapres iteration du simplexe)

4 trouver le plus grand nombre t tel que xB − td ≥ 0si t = +∞ : probleme non bornesinon : au moins 1 ligne = 0 =⇒ variable sortant de la base

5 remplacer xB par xB − td , puis la ligne correspondant a lavariable sortante par t

6 remplacer dans B la colonne de la variable sortante parcelle de la variable entrante

Cours 4 : methode revisee du simplexe 17/21

Synthese sur la methode revisee du simplexe

Iteration de l’algorithme revise du simplexe

B = base courante xB = valeur de la solution courante1 calculer yT tel que yT B = cT

B (=⇒ yT = cTB B−1)

2 choisir une colonne entrante : n’importe quelle colonne ade N telle que cT

a > yT a, ou cTa = coeff de la colonne a

dans cT

3 calculer d tel que Bd = a (=⇒ d ≈ valeur de la colonne aapres iteration du simplexe)

4 trouver le plus grand nombre t tel que xB − td ≥ 0si t = +∞ : probleme non bornesinon : au moins 1 ligne = 0 =⇒ variable sortant de la base

5 remplacer xB par xB − td , puis la ligne correspondant a lavariable sortante par t

6 remplacer dans B la colonne de la variable sortante parcelle de la variable entrante

Cours 4 : methode revisee du simplexe 17/21

Synthese sur la methode revisee du simplexe

Iteration de l’algorithme revise du simplexe

B = base courante xB = valeur de la solution courante1 calculer yT tel que yT B = cT

B (=⇒ yT = cTB B−1)

2 choisir une colonne entrante : n’importe quelle colonne ade N telle que cT

a > yT a, ou cTa = coeff de la colonne a

dans cT

3 calculer d tel que Bd = a (=⇒ d ≈ valeur de la colonne aapres iteration du simplexe)

4 trouver le plus grand nombre t tel que xB − td ≥ 0si t = +∞ : probleme non bornesinon : au moins 1 ligne = 0 =⇒ variable sortant de la base

5 remplacer xB par xB − td , puis la ligne correspondant a lavariable sortante par t

6 remplacer dans B la colonne de la variable sortante parcelle de la variable entrante

Cours 4 : methode revisee du simplexe 17/21

Calcul efficace de B−1 (1/4)

Efficacite de l’algo revise : calcul de yT B = cTB et de Bd = a

Bk : base apres k iterations

Bk ne differe de Bk−1 que par la colonne a rentrant a l’iteration k

supp que la colonne de a dans Bk soit la peme

a est la colonne qui rentre =⇒ a la k eme iteration, Bk−1d = a

calcul de Bk

Ek = matrice unite dont la peme colonne est remplaceepar dBk = Bk−1Ek 3 2 4

2 1 54 2 2

·1 3 0

0 1 00 4 1

Cours 4 : methode revisee du simplexe 18/21

Calcul efficace de B−1 (1/4)

Efficacite de l’algo revise : calcul de yT B = cTB et de Bd = a

Bk : base apres k iterations

Bk ne differe de Bk−1 que par la colonne a rentrant a l’iteration k

supp que la colonne de a dans Bk soit la peme

a est la colonne qui rentre =⇒ a la k eme iteration, Bk−1d = a

calcul de Bk

Ek = matrice unite dont la peme colonne est remplaceepar dBk = Bk−1Ek 3 2 4

2 1 54 2 2

·1 3 0

0 1 00 4 1

Cours 4 : methode revisee du simplexe 18/21

Calcul efficace de B−1 (1/4)

Efficacite de l’algo revise : calcul de yT B = cTB et de Bd = a

Bk : base apres k iterations

Bk ne differe de Bk−1 que par la colonne a rentrant a l’iteration k

supp que la colonne de a dans Bk soit la peme

a est la colonne qui rentre =⇒ a la k eme iteration, Bk−1d = a

calcul de Bk

Ek = matrice unite dont la peme colonne est remplaceepar dBk = Bk−1Ek 3 2 4

2 1 54 2 2

·1 3 0

0 1 00 4 1

Cours 4 : methode revisee du simplexe 18/21

Calcul efficace de B−1 (1/4)

Efficacite de l’algo revise : calcul de yT B = cTB et de Bd = a

Bk : base apres k iterations

Bk ne differe de Bk−1 que par la colonne a rentrant a l’iteration k

supp que la colonne de a dans Bk soit la peme

a est la colonne qui rentre =⇒ a la k eme iteration, Bk−1d = a

calcul de Bk

Ek = matrice unite dont la peme colonne est remplaceepar dBk = Bk−1Ek 3 2 4

2 1 54 2 2

·1 3 0

0 1 00 4 1

Cours 4 : methode revisee du simplexe 18/21

Calcul efficace de B−1 (2/4)

B0 = IB1 = E1

B2 = E1E2

B3 = E1E2E3

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

yT Bk = cTB =⇒ yT E1E2E3 . . . Ek = cT

B

(. . . (((yT E1)E2)E3) . . . Ek ) = cTB

calcul de y : 1 yTk Ek = cT

B2 yT

k−1Ek−1 = yTk

3 yTk−2Ek−2 = yT

k−14 .............k yT E1 = yT

2

Cours 4 : methode revisee du simplexe 19/21

Calcul efficace de B−1 (2/4)

B0 = IB1 = E1

B2 = E1E2

B3 = E1E2E3

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

yT Bk = cTB =⇒ yT E1E2E3 . . . Ek = cT

B

(. . . (((yT E1)E2)E3) . . . Ek ) = cTB

calcul de y : 1 yTk Ek = cT

B2 yT

k−1Ek−1 = yTk

3 yTk−2Ek−2 = yT

k−14 .............k yT E1 = yT

2

Cours 4 : methode revisee du simplexe 19/21

Calcul efficace de B−1 (2/4)

B0 = IB1 = E1

B2 = E1E2

B3 = E1E2E3

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

yT Bk = cTB =⇒ yT E1E2E3 . . . Ek = cT

B

(. . . (((yT E1)E2)E3) . . . Ek ) = cTB

calcul de y : 1 yTk Ek = cT

B2 yT

k−1Ek−1 = yTk

3 yTk−2Ek−2 = yT

k−14 .............k yT E1 = yT

2

Cours 4 : methode revisee du simplexe 19/21

Calcul efficace de B−1 (2/4)

B0 = IB1 = E1

B2 = E1E2

B3 = E1E2E3

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

yT Bk = cTB =⇒ yT E1E2E3 . . . Ek = cT

B

(. . . (((yT E1)E2)E3) . . . Ek ) = cTB

calcul de y : 1 yTk Ek = cT

B2 yT

k−1Ek−1 = yTk

3 yTk−2Ek−2 = yT

k−14 .............k yT E1 = yT

2

Cours 4 : methode revisee du simplexe 19/21

Calcul efficace de B−1 (3/4)

resolution pratique de yTk Ek = cT

B :

[y1

k y2k y3

k y4k

1 3 0 00 1 0 00 4 1 00 5 0 1

= [3 32 4 1]

Cours 4 : methode revisee du simplexe 20/21

Calcul efficace de B−1 (3/4)

resolution pratique de yTk Ek = cT

B :

[y1

k y2k y3

k y4k

1 3 0 00 1 0 00 4 1 00 5 0 1

= [3 32 4 1]

Cours 4 : methode revisee du simplexe 20/21

Calcul efficace de B−1 (3/4)

resolution pratique de yTk Ek = cT

B :

[y1

k y2k y3

k y4k

1 3 0 00 1 0 00 4 1 00 5 0 1

= [3 32 4 1]

=⇒

y1

k

y2k

y3k

y4k

=

3

Cours 4 : methode revisee du simplexe 20/21

Calcul efficace de B−1 (3/4)

resolution pratique de yTk Ek = cT

B :

[y1

k y2k y3

k y4k

1 3 0 00 1 0 00 4 1 00 5 0 1

= [3 32 4 1]

=⇒

y1

k

y2k

y3k

y4k

=

3

4

Cours 4 : methode revisee du simplexe 20/21

Calcul efficace de B−1 (3/4)

resolution pratique de yTk Ek = cT

B :

[y1

k y2k y3

k y4k

1 3 0 00 1 0 00 4 1 00 5 0 1

= [3 32 4 1]

=⇒

y1

k

y2k

y3k

y4k

=

3

4

1

Cours 4 : methode revisee du simplexe 20/21

Calcul efficace de B−1 (3/4)

resolution pratique de yTk Ek = cT

B :

[y1

k y2k y3

k y4k

1 3 0 00 1 0 00 4 1 00 5 0 1

= [3 32 4 1]

=⇒

y1

k

y2k

y3k

y4k

=

3

2

4

1

Cours 4 : methode revisee du simplexe 20/21

Calcul efficace de B−1 (3/4)

resolution pratique de yTk Ek = cT

B :

[y1

k y2k y3

k y4k

1 3 0 00 1 0 00 4 1 00 5 0 1

= [3 32 4 1]

=⇒

y1

k

y2k

y3k

y4k

=

3

2

4

1

=⇒ seul y2k necessite un calcul :

s − 1 additions

s − 1 multiplications

1 divisionCours 4 : methode revisee du simplexe 20/21

Calcul efficace de B−1 (4/4)

En pratique :

lorsque B0 6= I : factorisations triangulaires de B0

en general : factorisation de Bk a l’aide des Ek plus rapideque le calcul de B−1

k

si ca n’est plus le cas (trop d’iterations) : refactoriser Bkcomme si c’etait un nouveau B0

=⇒ methode revisee plus rapide que la methode standard surde grosses instances

Cours 4 : methode revisee du simplexe 21/21