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

Imágen de pdf Método simplex para redes (representaciones gráficas)

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

Publicado el 6 de Septiembre del 2017
1.183 visualizaciones desde el 6 de Septiembre del 2017
148,7 KB
6 paginas
Creado hace 18a (18/03/2002)
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)
  • Links de descarga
http://lwp-l.com/pdf6786

Comentarios de: Método simplex para redes (representaciones gráficas) (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad