PDF de programación - Método simplex para redes (representaciones gráficas)

15.053

Método simplex para redes
(representaciones gráficas)

Cálculo del flujo de un árbol de expansión

1

1

-6

2

7

3

1

3

6

-4

Árbol con ofertas y
demandas. (Suponemos
que el flujo de
los demás arcos
es igual a 0)

2

4

5

3

¿Cuál es el flujo
en el arco (4,3)?

Método simplex para redes (representaciones gráficas)

2

Método simplex para redes (animaciones)

Cálculo del flujo de un árbol de expansión

Cálculo del flujo de un árbol de expansión

1

1

-6

2

7

3

1

3

6

-4

2
4

2

5

3

Para calcular flujos,
se repite el árbol
y se halla un arco
cuyo flujo venga
determinado de
modo único.

¿Cuál es el flujo
del arco (5,3)?

1

1

-6

2

7

3

¿Cuál es el flujo
del arco (3,2)?

1

3

6

-4

2
4

2

3
5

3

3

Método simplex para redes (animaciones)

4

Método simplex para redes (animaciones)

Cálculo del flujo de un árbol de expansión

Cálculo del flujo de un árbol de expansión

1

1

2

-6
6
3

3
5

3

6

-4

2

1

2
4

5

¿Cuál es el flujo
del arco (2,6)?

7

3

Método simplex para redes (animaciones)

1

1

2

-6
6
3

4
6

-4

3
5

3

2

1

2
4

6

¿Cuál es el flujo
del arco (7,1)?

7

3

Método simplex para redes (animaciones)

Cálculo del flujo de un árbol de expansión

Cálculo del flujo de un árbol de expansión

1

1

2

-6
6
3

4
6

-4

3
5

3

2

1

2
4

7

¿Cuál es el flujo
del arco (1,2)?

3

7

3

Método simplex para redes (animaciones)

1

1

4

2

4
6

-4

-6
6
3

3
5

3

2

1

2
4

8

3

7

3

Nota: hay dos métodos
distintos para calcular
el flujo en (1,2), y ambos
dan como resultado
un flujo igual a 4. ¿Se trata
de una coincidencia?

Método simplex para redes (animaciones)

Cálculo de multiplicadores simplex para un árbol de expansión

Cálculo de multiplicadores simplex para un árbol de expansión

-6

7

1

5

-4

6

Tenemos este árbol de
expansión con costes en los arcos.
¿Cómo podemos elegir los
potenciales de nodos de modo
que los costes reducidos de
los arcos sean iguales a 0?

Recuerde: el coste
reducido de (i,j) es
cij - πi + πj

Método simplex para redes (animaciones)

3
3

2

1
5

-2
4

9

Tenemos este árbol de
expansión con costes en los arcos.
¿Cómo podemos elegir los
potenciales de nodos de modo
que los costes reducidos de
los arcos sean iguales a 0?

-6

7

1

5

-4

6

Recuerde: el coste
reducido de (i,j) es
cij - πi + πj

Método simplex para redes (animaciones)

3
3

2

1
5

-2
4

10

Cálculo de multiplicadores simplex para un árbol de expansión

Cálculo de multiplicadores simplex para un árbol de expansión

0
1

5

-4

6

-6

7

3
3

2

1
5

-2
4

11

El problema del
flujo de coste mínimo
contiene una
restricción redundante.

Podemos definir π1
arbitrariamente.
Supondremos que πi = 0.

¿Cuál es el
multiplicador simplex
para el nodo 2?

Método simplex para redes (animaciones)

0
1

5

-4

6

-6

7

El coste reducido
de (1,2) es
c12 - π1 + π2 = 0.

Por tanto, 5 - 0 + π 2 = 0.

¿Cuál es el
multiplicador simplex
para el nodo 7?

Método simplex para redes (animaciones)

-5
3
3

2

1
5

-2
4

12

Cálculo de multiplicadores simplex para un árbol de expansión

Cálculo de multiplicadores simplex para un árbol de expansión

0
1

5

-4

6

-6

7
-6

-5
3
3

2

1
5

-2
4

13

El coste reducido
de (1,2) es
c71 - π7 + π1 = 0.

Por tanto, -6 - π 2 +0 = 0.

¿Cuál es el
multiplicador simplex
para el nodo 3?

Método simplex para redes (animaciones)

0
1

5

-4

6

-6

7
-6

-5
3
3

2

1
5

-2
-2
4

14

¿Cuál es el
multiplicador simplex
para el nodo 6?

Método simplex para redes (animaciones)

Cálculo de multiplicadores simplex para un árbol de expansión

Cálculo de multiplicadores simplex para un árbol de expansión

0
1

5

-4

6

-1

-6

7
-6

-5
3
3

2

1
5

-2
-2
4

15

¿Cuál es el
multiplicador simplex
para el nodo 4?

Método simplex para redes (animaciones)

0
1

5

-4

6

-1

-6

7
-6

-5
3
3

2

1
5

-4

-2
-2
4

16

¿Cuál es el
multiplicador simplex
para el nodo 5?

Método simplex para redes (animaciones)

Cálculo de multiplicadores simplex para un árbol de expansión

Algoritmo simplex para redes

0
1

6

-1

-6

7
-6

5

-4

-1

-5
3
3

2

1
5

Aquí vemos los
multiplicadores simplex
asociados al árbol.
No dependen de
los flujos de arcos
ni de los costes de
arcos sin árbol.

T
L
U

2
1

4, 1$
2
5

4, 2$

3, 5 $

2, 4$

3
5, 5$

3, 4$

1, 4$

-4
4
4, 2$

5
-3

Problema del flujo de coste mínimo

Método simplex para redes (animaciones)

18

Método simplex para redes (animaciones)

-4

-2
-2
4

17

Flujos del árbol de expansión

Multiplicadores simplex y costes reducidos

T
L
U

2
1

0

2
5

1

2

1

3

3

3

0

-4
4
0

5
-3

Solución al árbol de expansión inicial

0
1

-2
2
3

0

0

0

0

3

3

2
4

Multiplicadores simplex
y costes reducidos iniciales

-4
4
?

5
-2

T
L
U

c45 = 2

¿Qué arcos no
cumplen las cond?

19

Método simplex para redes (animaciones)

20

Método simplex para redes (animaciones)

Adición al árbol de un arco que no cumple las condiciones y creación de un ciclo

Envío de flujo por el ciclo

u14, x14

4,0

1

2

4,1

3,2

2, 1

3
5, 3

3,3
1, 0

4
4, 0

5

Se ha añadido al árbol el arco (2,1)

T
L
U

¿Cuál es el
ciclo, y
cuánto flujo
es posible
enviar?

u14, x14

4,2

1

2

4,3

3,0

2, 1

3
5, 3

3,3
1, 0

4
4, 0

5

Se han enviado dos unidades
de flujo por el ciclo.

T
L
U

¿Cuál es el
siguiente árbol
de expansión?

21

Método simplex para redes (animaciones)

22

Método simplex para redes (animaciones)

Después del pivotaje

u14, x14

4,2

1

2

4,3

3,0

2, 1

3
5, 3

3,3
1, 0

4
4, 0

5

Árbol de expansión actualizado

T
L
U

En un pivotaje,
se añade un arco
a T y se retira
otro de T.

Actualización de los multiplicadores

0
1

-2

2
3

0

0

0

0

3

3

2
4

Multiplicadores y
costes reducidos actuales

-4
4
4

5
-2

T
L
U

¿Cómo podemos
hacer que cπ
21 = 0
y que otros arcos
del árbol tengan
coste reducido 0?

23

Método simplex para redes (animaciones)

24

Método simplex para redes (animaciones)

Al eliminar (2,1) de T, T se separa en dos partes

Multiplicadores actualizados y costes reducidos

0
1

-2

0

0

0

3

3

2
4

-4
4
4

0

2
5
3+∆
-2+∆
La adición de ∆ a los nodos de un lado
del árbol no afecta a los costes reducidos
de ningún arco, excepto al arco (2,1).
¿Por qué?

25

T
L
U

¿Qué valor de
∆ se deberá
elegir para que
el coste reducido
de (2,1) = 0?

Método simplex para redes (animaciones)

0
1

0

2
1

0

2

0

0

3

3

2
2

Multiplicadores y
costes reducidos actualizados

-4
4
2

5
-4

T
L
U

¿Es ésta la
solución óptima
al árbol?

26

Método simplex para redes (animaciones)

Adición al árbol de un arco que no cumple las condiciones y creación de un ciclo

Envío de flujo por el ciclo

4,2

1

2

4,3

3,0

2, 1

3
5, 3

3,3
1, 0

4
4, 0

5

Adición al árbol de expansión del arco (3,4)

T
L
U

¿Cuál es el
ciclo, y
cuánto flujo
es posible
enviar?

4,2

1

2

4,2

3,0

2, 2

3
5, 3

3,2
1, 0

4
4, 0

5

Se ha enviado una unidad de flujo
por el ciclo.

T
L
U

¿Cuál es la
siguiente solución
al árbol?

27

Método simplex para redes (animaciones)

28

Método simplex para redes (animaciones)

Siguiente solución al árbol de expansión

Multiplicadores actualizados

T
L
U

4,2

1

2

4,2

3,0

2, 2

3
5, 3

3,2
1, 0

4
4, 0

5

Esta es la solución actualizada
al árbol de expansión.

0
1

0

2
1

0

2

0

0

3

3

2
2

-4
4
2

5
-4

Estos son los multiplicadores actuales.

T
L
U

¿Cómo debemos
modificar los
multiplicadores?

29

Método simplex para redes (animaciones)

30

Método simplex para redes (animaciones)

Multiplicadores actualizados

Multiplicadores actualizados

0
1

0

2
1-4

0

2

0

0

3

3

2
2

-4 +∆
4
2

5

T
L
U

¿Qué valor
deberá tener ∆?

0

2

-2

0

3

3

0
2

0
1

0

2
1

-6
4
4

5
-4

Estos son los multiplicadores actuales.

Estos son los multiplicadores actualizados.

T
L
U

¿Es óptima
la solución
actual al árbol
de expansión?

31

Método simplex para redes (animaciones)

32

Método simplex para redes (animaciones)

Solución óptima

0

2

-2

0

3

3

0
2

0
1

0

2
1

Esta es la solución óptima.

-6
4
4

5
-4

T
L
U

Ningún arco
incumple las
condiciones de
optimalidad.

33

Método simplex para redes (animaciones)