Aplicaciones de Programación Lineal

2.1 Modelo de Transporte El objetivo general es encontrar el mejor plan de distribución, es decir, la cantidad que se debe enviar por cada una de las rutas desde los puntos de suministro hasta los puntos de demanda. El “mejor plan” es aquel que minimiza los costos totales de envío, produzca la mayor ganancia u optimice algún objetivo corporativo. Se debe contar con:

i) Nivel de oferta en cada fuente y la cantidad de demanda en cada destino. ii) Costo de transporte unitario de mercadería desde cada fuente a cada destino. 3

2.1 Modelo de Transporte

También es necesario satisfacer ciertas restricciones: 1. No enviar más de la capacidad especificada desde cada punto de suministro (oferta). 2. Enviar bienes solamente por las rutas válidas. 3. Cumplir (o exceder) los requerimientos de bienes en los puntos de demanda.

4

2.1 Modelo de Transporte

Gráficamente: Para m fuentes y n destinos

Esquemáticamente se podría ver como se muestra en la siguiente figura Fuentes Destinos C11, X11

s1

1

1

d1

s2

2

2

. . .

d2

. . .

sm

m Cmn, Xmn

donde

n

dn

Xij: cantidad transportada desde la fuente i al destino j Cij: Costo del transporte unitario desde la fuente i al destino j 5

2.1 Modelo de Transporte

Modelo general de PL que representa al modelo de Transporte

m

minimizar

n

Z   cij xij i 1 j 1

n

sa

x j 1

ij

m

x i 1

ij

 si

i=1,2,...,m

 dj

j=1,2,...,n

xij  o

para toda i y j

El modelo implica que al menos la oferta debe ser igual a la demanda 6

2.1 Modelo de Transporte

Modelo general de PL que representa al modelo de Transporte Modelo de transporte equilibrado: Oferta = Demanda

n

x

 Si

i=1, 2, 3,....,m

 xij  D j

j=1, 2, 3,....,n

j 1

ij

m

i 1

xij  0

para toda i y j 7

2.1 Modelo de Transporte

Aplicaciones del modelo de Transporte

El Modelo de Transporte no sólo es aplicable al movimiento de productos, sino que también, como modelo se puede aplicar a otras áreas tales como: • Planificación de la Producción • Control de Inventarios • Control de Proveedores • Otras

8

2.1 Modelo de Transporte

Ejemplo: RPG tiene cuatro plantas ensambladoras en Europa. Están ubicadas en Leipzig, Alemania (1);Nancy, Francia (2); Lieja, Bélgica (3), y Tilburgo, Holanda (4). Las máquinas ensambladoras usadas en estas plantas se producen en Estados Unidos y se embarcan a Europa. Llegaron a los puertos de Amsterdan (1), Amberes (2) y El Havre (3). Los planes de producción del tercer trimestre (julio a septiembre) ya han sido formulados. Los requerimientos (la demanda en destinos) de motores diesel E-4 son los siguientes:

2.1 Modelo de Transporte

Planta Cantidad de Motores (1) Leipzig 400 (2) Nancy 900 (3) Lieja 200 (4) Tilburgo 500 Total 2000 La cantidad disponible de máquinas E-4 en los puertos(oferta en orígenes) son: Puerto Cantidad de Motores (1) Amsterdan 500 (2) Amberes 700 (3) El Hevre 800 Total 2000

2.1 Modelo de Transporte

Los costos ($) de transporte de un motor desde un origen a un destino son: Al destino Desde el origen

1

2

3

4

1

12

13

4

6

2

6

4

10

11

3

10

9

12

4

11

Construcción del modelo de PL

2.1 Modelo de Transporte

1. Variables de decisión

Xij = número de motores enviados del puerto i a la planta j i = 1, 2, 3 j = 1, 2, 3, 4 2. Función Objetivo Minimizar Z = 12 X11 + 13 X12 + 4X13 + 6X14 + 6X21 + 4X22 + 10X23 + 11X24 + 10X31 + 9X32 + 12X34 + 4X14

12

2.1 Modelo de Transporte 3. Restricciones: 1) Oferta: La cantidad de elementos enviados no puede exceder la cantidad disponible X11 + X12 + X13 + X14  500

X21 + X22 + X23 + X24  700 X31 + X32 + X33 + X34  800 2) Demanda: Debe satisfacerse la demanda de cada planta X11 + X21 + X31  400 X12 + X22 + X32  900 X13 + X23 + X33  200 X14 + X24 + X34  500 y de no negatividad Xij  0 para i=1, 2, 3; j= 1, 2, 3, 4 13

2.1 Modelo de Transporte

Solución del Modelo de Transporte

2.1 Modelo de Transporte

Algoritmos Específicos 2.1.1 Regla de la esquina noroeste (MEN) 2.1.2 Método por aproximación de Vogel (MAV) 2.1.3 Método del costo mínimo (MCM) 2.1.4 Método del paso secuencial y 2.1.5 DIMO (método de distribución modificada)

15

2.1 Modelo de Transporte

Descripción de los algoritmos La regla de la esquina noroeste, el método de aproximación de Vogel y el método del costo mínimo son alternativas para encontrar una solución inicial factible.

El método del escalón y el DIMO son alternativas para proceder de una solución inicial factible a la óptima.

Por tanto, el primer paso es encontrar una solución inicial factible, que por definición es cualquier distribución de ofertas que satisfaga todas las demandas 16

2.1 Modelo de Transporte

Descripción de los algoritmos Una vez obtenida una solución básica factible, el algoritmo procede paso a paso para encontrar un mejor valor para la función objetivo. La solución óptima es una solución factible de costo mínimo

Para aplicar los algoritmos, primero hay que construir una tabla de transporte.

17

2.1 Modelo de Transporte

Tabla Inicial Origen 1

1 C11

Destinos 2 3 C12 C13

4 C14

....

n C1n

2

C21

C22

C23

C24

....

C2n

3

C31

C32

C33

C34

....

C3n

...

....

.....

....

....

....

Cm1

Cm2

Cm3

Cm4

....

Cmn

m

Ofertas

Demanda

18

2.1 Modelo de Transporte

Tabla Inicial del Ejemplo Plantas Puertos 1

1

2 12

3 13

4 4

Oferta 6 500

2

6

4

10

11 700

3 Demanda

10 400

9 900

12 200

4 500

800 2000

19

2.1 Modelo de Transporte

2.1.1 Regla de la esquina Noroeste Se inicia el proceso desde la esquina izquierda superior Se ubican tantas unidades como sea posible en la ruta Cantidad de Unidades = Mínimo(disponibilidad, demanda) Las siguientes asignaciones se hacen o bien recorriendo hacia la derecha o bien hacia abajo. Las demandas se satisfacen recorriendo sucesivamente de izquierda a derecha y las ofertas se destinan recorriendo de arriba hacia abajo.

20

2.1 Modelo de Transporte

Primera asignación

Plantas Puertos 1

1

2 12

3 13

4 4

Oferta 6

400 2

100 6

4

10

500

11 700

3 Demanda

10 0 400

9 900

12 200

4 500

800 2000

21

2.1 Modelo de Transporte

Hasta cuarta asignación

Plantas Puertos 1

1

2 12

400 2

3 13

4 4

Oferta 6

100 6

4

10

Demanda

10

9

100 0 400 0 900

12 200

500

0

700

700

800 2000

11

700 3

100

4 500

22

2.1 Modelo de Transporte

Esquina Noroeste: Solución final factible Plantas Puertos 1

1

2 12

400 2

3 13

4 4

Oferta 6

100 6

4

10

Demanda

10

9

12

500

0

700

0

800 2000

11

700 3

100

4

100 200 500 0 400 0 900 200 500

Valor FO: 400*12+100*13+700*4+100*9+200*12+500*4= $14.200 23

2.1 Modelo de Transporte

2.1.2 Método de aproximación de Vogel (MAV) MAV usa información de costos mediante el concepto de costo de oportunidad para determinar una solución inicial factible. Seleccionar en una fila la ruta más barata y la que le sigue. Hacer su diferencia (penalidad), que es el costo adicional por enviar una unidad desde el origen actual al segundo destino y no al primero. En nuestro caso, para el puerto1, C13 y C14; Penalidad = 6 - 4 MAV asigna un costo de penalidad por no usar la mejor ruta en esta fila.

24

2.1.2 Método de aproximación de Vogel

2.1 Modelo de Transporte

Lo anterior se repite para cada fila y cada columna, esto es, determinar todas las penalidades Los pasos iterativos de MAV son los siguientes: 1. Identificar la fila o columna con la máxima penalidad. 2.Colocar la máxima asignación posible a la ruta no usada que tenga menor costo en la fila o columna seleccionada en el punto 1 (los empates se resuelven arbitrariamente) 3. Reajustar la oferta y demanda en vista de esta asignación. 4. Eliminar la columna en la que haya quedado una demanda 0 (o la fila con oferta 0), de consideraciones posteriores. 5. Calcular los nuevos costos de penalidad. 25

2.1.2 Método de aproximación de Vogel

2.1 Modelo de Transporte

El MAV continúa aplicando este proceso en forma sucesiva hasta que se haya obtenido una solución factible.

Los resultados obtenidos se muestran en las siguientes tablas

26

2.1.2 Método de aproximación de Vogel

2.1 Modelo de Transporte

Paso 0: Cálculo de penalidades Plantas Puertos 1

1

2 12

3 13

4

Oferta

4

Penalidades 2

6 500

2

6

4

10

11

2 700

3 Demanda Penalidades

10

9

12

4

400

900

200

500

4

5

6

2

5 800 2000

Paso 1: Identificar máxima penalidad (fila o columna) Calculadas todas las penalidades, la mayor corresponde a la columna 3 (penalidad = 6) 27

2.1.2 Método de aproximación de Vogel

2.1 Modelo de Transporte

Paso 2: Asignación de unidades (MIN(oferta,demanda)) Paso 3:Reajuste de oferta y demanda Plantas Puertos 1

1

2 12

3 13

4 4

Oferta 6

200 2

6

4

300 10

500

11 700

3 Demanda

10 400

9 900

12 0 200

4 500

800 2000

28

2.1.2 Método de aproximación de Vogel

2.1 Modelo de Transporte

Paso 4: Eliminar columna (fila) con demanda (oferta) 0 Plantas Puertos 1

1

2 12

3 13

4 4

Oferta 6

200 2

6

4

300 10

500

11 700

3 Demanda

10 400

9 900

12 0 200

4 500

800 2000

29

2.1.2 Método de aproximación de Vogel

2.1 Modelo de Transporte

Paso 5: Calcular los nuevos costos de penalidad Plantas Puertos 1

1

2 12

3 13

4 4

Oferta 6

200 2

6

4

300 10

Penalidades 6 500

11

2 700

3 Demanda Penalidades

10

9

400

900

4

5

12 0 200

4 500

5 800 2000

2

30

2.1.2 Método de aproximación de Vogel

2.1 Modelo de Transporte

Repitiendo los pasos anteriores, finalmente se llega a la siguiente solución Plantas Puertos 1

1

2 12

3 13

4 4

200 2

6

4

Oferta 6

300 10

300

500

0

700

11

700 3

10 400

Demanda

9 200

400

900

12

4

200 600 800 0 200 200 500 2000

¿Es solución factible? ¿m + n - 1 = 6? SI Costo: 200*4+300*6+700*4+400*10+200*9+200*4 = $12.000 31

2.1.3. Método del Costo Mínimo

2.1 Modelo de Transporte

Fundamento Asignar la mayor cantidad de unidades a una ruta disponible de costo mínimo Algoritmo 1. Dada una tabla de transporte 2. Asignar la mayor cantidad de unidades a la variable (ruta) con el menor costo unitario de toda la tabla. 3. Tachar la fila o columna satisfecha. 4. Ajustar oferta y demanda de todas las filas y columnas 5. Si hay más de una fila o columna no tachada repetir los puntos 2, 3 y 4 32

2.1.3. Método del Costo Mínimo (cont.)

2.1 Modelo de Transporte

Ejemplo: Aplicar MCM a la tabla de transporte Plantas Puertos 1

1

2 12

3 13

4 4

Oferta 6 500

2

6

4

10

11 700

3

10

Demanda

Paso 2

400

9 900

12 200

4 500

800 2000

Existen tres rutas costo mínimo. Elijamos la 1_3 Unidades a asignar = MIN(200,400) = 200 33

2.1.3. Método del Costo Mínimo (cont.)

2.1 Modelo de Transporte

Paso 3: Tachar fila o columna (columna 3) Plantas Puertos 1

1

2 12

3 13

4 4

Oferta 6

200

2

6

4

300

10

500

11 700

3

10

Demanda

400

9 900

12 0 200

4 500

800 2000

Paso 4

Ajustar ofertas y demandas (fila 1 y columna 3)

Paso 5

Aún quedan más de una fila o columna sin tachar. Ir a paso 2 34

2.1.3. Método del Costo Mínimo (cont.)

2.1 Modelo de Transporte

Paso 2: Ruta de costo menor -> 3_4 (ó 2_2) Unidades = MIN(500,800) = 500 Paso 3: Tachar columna 4 Paso 4: Tachar ajustar fila 3 y columna 4 Plantas Puertos 1

1

2 12

3 13

4 4

Oferta 6

200

2

6

4

300

10

500

11 700

3

10

9

12

4 500

Demanda

Paso 5

400

900

0 200

0 500

300

800 2000

Aún quedan más de una fila o columna sin tachar. Ir a paso 2 35

2.1.3. Método del Costo Mínimo (cont.)

2.1 Modelo de Transporte

Paso 2: Ruta de costo menor -> 2_2 Unidades = MIN(700,900) = 300 Paso 3: Tachar fila2 Paso 4: Tachar ajustar fila 2 y columna 2 Puertos 1

1

2 12

3 13

4 4

Oferta 6

200

2

6

4

10

10

9

12

Paso 5

400 200 900

0 200

0

700

4 500

Demanda

500

0

700

3

300

0 500

300

800 2000

Aún quedan más de una fila o columna sin tachar. Ir a paso 2 36

2.1.3. Método del Costo Mínimo (cont.)

2.1 Modelo de Transporte

Paso 2: Ruta de costo menor -> 3_2 Unidades = MIN(200,300) = 200 Paso 3: Tachar columna 2 Paso 4: Tachar ajustar fila 3 y columna 2 Puertos 1

1

2 12

3 13

4 4

Oferta 6

200

2

6

4

10

10

9

12

200

Demanda

Paso 5

400 200 900

0

700

4 100 500

0 200

500

0

700

3

300

0 500

300

800 2000

Aún quedan más de una fila o columna sin tachar. Ir a paso 2 37

2.1.3. Método del Costo Mínimo (cont.)

2.1 Modelo de Transporte

Paso 2: Ruta de costo menor -> 3_1 Unidades = MIN(400,100) = 100 Paso 3: Tachar fila 3 Paso 4: Tachar ajustar fila 3 y columna 1 Puertos 1

1

2 12

3 13

4 4

Oferta 6

200

2

6

4

10

10

Demanda

Paso 5

9

100

200

300 400

200 900

12

0

700

4 100 500

0 200

500

0

700

3

300

0 500

300

0

800 2000

Aún quedan más de una fila o columna sin tachar. Ir a paso 2 38

2.1.3. Método del Costo Mínimo (cont.)

2.1 Modelo de Transporte

Paso 2: Ruta de costo menor -> 1_1 Unidades = MIN(300,300) = 300 Paso 3: Tachar fila 1 ó columna 1 (sólo una de ellas) Paso 4: Tachar ajustar fila 1 y columna 1 Puertos 1

1

2 12

3 13

300

2

4 4

Oferta 6

200

6

4

10

10

Demanda

Paso 5

9

100

200

300 400

200 900

300

500

0

700

0

700

3

0

12

4 100 500

0 200

0 500

300

0

800 2000

Queda sólo una fila sin tachar. Terminar 39

2.1.3. Método del Costo Mínimo (cont.)

2.1 Modelo de Transporte

¿Es solución factible? ¿m + n - 1 = 6? SI Costo: 300*12+200*4+700*4+100*10+200*9+500*4 = $12.000 Comparación de los resultados Método MEN MAV MCM

Rutas 6 6 6

Costo $14.200 $12.000 $12.000

Conclusión Los tres métodos entregan soluciones básicas factibles, pero ninguno asegura que la solución sea óptima. 40

2.1.4. Método de Pasos Secuenciales

2.1 Modelo de Transporte

Fundamento Este método comienza con una solución inicial factible. En cada paso se intenta enviar artículos por una ruta que no se haya usado en la solución factible actual, en tanto se elimina una ruta usada actualmente. En cada cambio de ruta debe cumplirse que: 1. La solución siga siendo factible y 2. Que mejore el valor de la función objetivo El procedimiento termina cuando no hay cambio de rutas que mejoren el valor de la función. 41

2.1.4. Método de pasos secuenciales (cont..)

2.1 Modelo de Transporte

Algoritmo

1

Usar la solución actual (MEN, MAV o MCM) para crear una trayectoria única del paso secuencial. Usar estas trayectorias para calcular el costo marginal de introducir a la solución cada ruta no usada.

2

Si todos los costos marginales son iguales o mayores que cero, terminar; se tendrá la solución óptima. Si no, elegir la celda que tenga el costo marginal más negativo (empates se resuelven arbitrariamente)

3

Usando la trayectoria del paso secuencial, determine el máximo número de artículos que se pueden asignar a la ruta elegida en el punto 2 y ajustar la distribución adecuadamente.

4

Regrese al paso 1 42

2.1.4. Método de pasos secuenciales (cont..)

Algoritmo

2.1 Modelo de Transporte

Paso 1

a) Ponga un signo + en la celda de interés no ocupada b) Ponga un signo - en una celda usada de la misma fila c) Ponga un + en una celda usada de la misma columna

El proceso continúa alternando los signos + y - tanto en las filas como en las columnas hasta que se obtenga una sucesión de celdas (trayectoria) que satisfagan dos condiciones 1. Hay un signo + en la celda desocupada original de interés, y 2. Cualquier fila o columna que tenga un signo + debe tener también un signo - y viceversa. 43

2.1 Modelo de Transporte

2.1.4. Método de pasos secuenciales (cont..)

Paso 1

Algoritmo

Plantas Puertos 1

1

2 12

400 2

3 13

4 4

Oferta 6

100 6

4

10

Demanda

10

9

12

500

0

700

0

800 2000

11

700 3

100

4

100 200 500 0 400 0 900 200 500

Solución básica factible obtenida aplicando el método de la Esquina Noroeste 44

2.1 Modelo de Transporte

2.1.4. Método de pasos secuenciales (cont..)

Paso 1

Algoritmo

Plantas Puertos 1

1

2 12

400 2

100 6

3 13 4

4 4 + 10

Oferta 6

Demanda

10

500

0

700

0

800 2000

11

700 3

100

9

12 4 100 + 200 - 500 0 400 0 900 0 200 0 500

Trayectoria 1: +C13-C12+C32-C33 45

2.1 Modelo de Transporte

2.1.4. Método de pasos secuenciales (cont..)

Algoritmo

Paso 1 Plantas

Puertos 1

1

2 12

400

100

2

6

3 13 4

4 4 + 10

Oferta 6

Demanda

10

500

0

700

0

800 2000

11

700 3

100

9

12 4 100 + 200 - 500 0 400 0 900 0 200 0 500

Costos de las Trayectorias 1: +(4)-(13)+(9)-(12)= -12

2: +(6)-(13)+(9)-(4) = -2

3: +(6)-(4)+(13)-(12)= 3

4: +(10)-(4)+(9)-(12) = 3

5: +(11)-(4)+(9)-(4) = 12

6: +(10)-(9)+(13)-(12)= 2 46

2.1.4. Método de pasos secuenciales (cont..)

Algoritmo

2.1 Modelo de Transporte

Paso 2

1: +(4)-(13)+(9)-(12)= -12

2: +(6)-(13)+(9)-(4) = -2

3: +(6)-(4)+(13)-(12)= 3

4: +(10)-(4)+(9)-(12) = 3

5: +(11)-(4)+(9)-(4) = 2

6: +(10)-(9)+(13)-(12)= 2

La solución factible NO es óptima !!

Se selecciona la trayectoria 1 (costo marginal más negativo)

47

2.1 Modelo de Transporte

2.1.4. Método de pasos secuenciales (cont..)

Algoritmo

Paso 3 (Generación de la nueva tabla)

¿Cuántas unidades se pueden asignar a la ruta elegida?

Acción

Ruta

Aumentar 1 unidad

1_3

Disminuir 1 unidad

1_2

Aumentar 1 unidad

3_2

Disminuir 1 unidad

3_3

Unidades disponibles en celdas decrecientes 100

200

48

2.1 Modelo de Transporte

2.1.4. Método de pasos secuenciales (cont..)

Paso 3 (Generación de la nueva tabla)

Algoritmo

Plantas Puertos 1

1

2 12

13 - 100 4

400 2

3

6

4 4 + 10

Oferta 6

Demanda

10

500

0

700

0

800 2000

11

700 3

100

9

12 4 200 + 100 - 500 0 400 0 900 0 200 0 500

Costo: $13.000 49

2.1 Modelo de Transporte

2.1.4. Método de pasos secuenciales (cont..)

Algoritmo

Paso 4

Volver al Paso 1:

Para cada trayectoria evaluar costo marginal Plantas Puertos 1

1

2 12

3 13

400 2

4 4

Oferta 6

100 6

4

10

Demanda

10

9

12

500

0

700

0

800 2000

11

700 3

100

4

200 100 500 0 400 0 900 0 200 0 500

50

2.1 Modelo de Transporte

2.1.4. Método de pasos secuenciales (cont..)

Algoritmo

Paso 2: Elección de CMg menor Plantas

Puertos 1 2 3 Demanda

1

2 12

3 13 +12 100 4

4

Oferta

4

6 400 +10 100 500 6 10 11 -9 700 +3 +12 0 700 10 9 12 4 -10 200 100 500 0 800 0 400 0 900 0 200 0 500 2000

La celda más negativa es c 31 (-10) y la trayectoria es: C31 – C33 + C13 – C11

51

2.1 Modelo de Transporte

2.1.4. Método de pasos secuenciales (cont..)

Algoritmo

Paso 3 (Generación de la nueva tabla)

¿Cuántas unidades se pueden asignar a la ruta elegida?

Acción

Ruta

Aumentar 1 unidad

31

Disminuir 1 unidad

33

Aumentar 1 nidad

13

Disminuir 1 unidad

11

Unidades disponibles en celdas decrecientes 100

400

52

2.1 Modelo de Transporte

2.1.4. Método de pasos secuenciales (cont..)

Algoritmo Paso 3 (Generación de la nueva tabla) Plantas Puertos 1

1

2 12

3 13

300 2

4 4

Oferta 6

200 6

4

10

Demanda

10

9

100 200 0 400 0 900

12

500

0

700

0

800 2000

11

700 3

100

4

500 0 200 0 500

Costo: $12.000 53

2.1 Modelo de Transporte

2.1.4. Método de pasos secuenciales (cont..)

Algoritmo

Paso 4

Volver al Paso 1:

Para cada trayectoria evaluar costo marginal Plantas Puertos 1

1

2 12

3 13

300 2

4 4

Oferta 6

200 6

4

10

Demanda

10

9

100 200 0 400 0 900

12

500

0

700

0

800 2000

11

700 3

100

4

500 0 200 0 500

54

2.1 Modelo de Transporte

2.1.4. Método de pasos secuenciales (cont..)

Algoritmo

Paso 2: Determinar costos marginales Plantas

Puertos 1

1 12 300

2 3 Demanda

2

3 13 +2 200 4

6 +1 700 10 9 100 200 0 400 0 900

4

Oferta

4

6 0 100 500 10 11 +13 +12 0 700 12 4 +10 500 0 800 0 200 0 500 2000

Todas rutas son no negativas (positivas o cero) Solución factible óptima!!! $12.000 Compare esta solución con la obtenida con MAV y MCM ¿ ...? 55

2.1.5. Método de Distribución Modificada (DIMO)

2.1 Modelo de Transporte

Algoritmo 1. Usar la solución actual (NE, MAV o MCM) y las siguientes operaciones (a) y (b) para determinar el costo marginal de enviar material para cada una de las rutas no usadas.

Asociar a cada fila un índice ui y a cada columna un índice vj a) Hacer u1 = 0. Encuéntrese los índices de las filas u2, ..., um y los índices de las columnas v1, ...., vn tales que cij = ui + vj para cada celda usada. b) Sea eij = cij - (ui+vj) para cada celda no usada; eij será el costo marginal de introducir la celda (ruta) i, j a la solución. Los pasos 2 a 4 son los mismos que en el método secuencial. 56

2.1 Modelo de Transporte

2.1.5. Método de Distribución Modificada (DIMO) Aplicar el algoritmo al problema en estudio y comparar resultados obtenidos con los métodos anteriores Comentar resultados ¿Qué explica que existan dos soluciones óptimas factibles?

57

2.1 Modelo de Transporte 2.1.5. Método de Distribución Modificada (DIMO)

Aplicación

vj Plantas

Puertos 1

1

2 12

400

4

13

Oferta

4

6

100

2

ui

3

6

4

10

Demanda

10

9

12 200 200

100 0 400 0 900

Paso 0: Asociar índices

Costo por Ruta en uso motor ($) 11 12

500

0

700

11

700 3

100

4 500 700 800 500 2000

Ecuación u1 + v1 = 12

12

13

u1 + v2 = 13

22

4

u2 + v2 = 4

32

9

u3 + v2 = 9

33

12

34

4

u3 + v3 = 12 u3 + v4 = 4

58

2.1 Modelo de Transporte 2.1.5. Método de Distribución Modificada (DIMO)

Paso1.a) Solucionar la ecuación Existen 6 ecuaciones y siete variables entonces se hace u1 = 0 (puede ser cualquiera) y se determina el resto de los índices

v1 = 12

v2 = 13 u2 = - 9 u3 = -4

v3 = 16 v4 = 8

Paso 1.b) Calcular los costos marginales para cada celda no usada. eij = cij - (ui + vj)

59

2.1 Modelo de Transporte 2.1.5. Método de Distribución Modificada (DIMO)

Costos marginales para las celdas no usadas. eij = cij - (ui + vj) 1) e13 = c13 - (u1 + v3)= 4 - (0 + 16) = -12 2) e14 = c14 - (u1 + v4)= 6 - (0 + 8)

= -2

3) e21 = c21 - (u2 + v1)= 6 - (-9 + 13) = 2 4) e23 = c23 - (u2 + v3)= 10 - (-9 + 16) = 3 5) e24 = c24 - (u2 + v4)= 11 - (-9 + 8) = 12 6) e31 = c31 - (u3 + v1)= 10 - (-4 + 12) = 2

60

2.1 Modelo de Transporte 2.1.5. Método de Distribución Modificada (DIMO)

Plantas Puertos 1

1 12 400

2 3 Demanda

2

3 13

100

6 4 2 700 10 9 2 100 0 400 0 900

4 4 -12 10 3 12 200 200

Oferta 6 -2 100 500 11 12 0 700 4 500 700 800 500 2000

Paso 2: Prueba de Optimalidad. Hay costos negativos por lo tanto no es óptima La ruta de reasignación es: +C13 -C33 +C32 -C12 (más negativo, -12) 61

2.1 Modelo de Transporte 2.1.5. Método de Distribución Modificada (DIMO)

Paso 3: Asignación de unidades a la ruta elegida. Unidades disponibles a mover: Disminuir 1 unidad C12

100

Disminuir 1 unidad C33

200 Plantas

Puertos 1

1

2 12

3 13

400 2

6

4

4 4 100 10

700 3 Demanda

10

9

200 0 400 0 900

12 100 200

Oferta 6 100

500

0

700

11 4 500 700 800 500 2000 62

2.1.5. Método de Distribución Modificada (DIMO)

2.1 Modelo de Transporte

Vuelta al Paso 1: Costo por Ruta en uso motor ($) 11 12 13 4 22 4 32 9 33 12 34 4

Ecuación u1 + v1 = 12 u1 + v3 = 4 u2 + v2 = 4 u3 + v2 = 9 u3 + v3 = 12 u3 + v4 = 4

Paso1.a) Solucionar la ecuación Se hacer u1 = 0 y se determina el resto de los índices v1 = 12

v2 = 1 v3 = 4 v4 = -4 u2 = 3 u3 = 8

Paso 1.b) Calcular los costos marginales para cada celda no usada. eij = cij - (ui + vj) 63

2.1 Modelo de Transporte 2.1.5. Método de Distribución Modificada (DIMO)

Costos marginales para las celdas no usadas. eij = cij - (ui + vj) 1) e12 = c12 - (u1 + v2)= 13 - (0 + 1) = 12 2) e14 = c14 - (u1 + v4)= 6 - (0 - 4)

= 10

3) e21 = c21 - (u2 + v1)= 6 - (3 + 12) = -9 4) e23 = c23 - (u2 + v3)= 10 - (3 + 4) = 3 5) e24 = c24 - (u2 + v4)= 11 - (3 - 4) = 12 6) e31 = c31 - (u3 + v1)= 10 - (8 + 12) = -10

64

2.1 Modelo de Transporte 2.1.5. Método de Distribución Modificada (DIMO)

Plantas Puertos 1 2

1 400

2 12

3 13 + 19 4

6 0 700 3 + 10 9 -1 200 Demanda 0 400 0 900

4 4 100 10 3 12 100 200

Oferta 6 1 100 500 11 12 0 700 4 500 700 800 500 2000

Paso 2: Prueba de Optimalidad. Hay costos negativos por lo tanto no es óptima La ruta de reasignación es: +C31 -C33 +C13 -C11 65

2.1 Modelo de Transporte 2.1.5. Método de Distribución Modificada (DIMO)

Paso 3: Asignación de unidades a la ruta elegida. Unidades disponibles a mover: Disminuir 1 unidad C11

400

Disminuir 1 unidad C33

100 Plantas

Puertos 1

1

2 12

3 13

300 2

6

4

4 4 200 10

700 3

10

9

12

100 200 Demanda 0 400 0 900

200

Oferta 6 100

500

0

700

11 4 500 700 800 500 2000 66

2.1 Modelo de Transporte 2.1.5. Método de Distribución Modificada (DIMO)

Vuelta al Paso 1: Costo por Ruta en uso motor ($) 11 12 13 4 22 4 31 10 32 9 34 4

Ecuación u1 + v1 = 12 u1 + v3 = 4 u2 + v2 = 4 u3 + v1 = 10 u3 + v2 = 9 u3 + v4 = 4

Paso1.a) Solucionar la ecuación u1 = 0 y se determina el resto de los índices v1 = 12

v2 = 11 v3 = 4 v4 = 6 u2 = - 7 u3 = -2

Paso 1.b) Calcular los costos marginales para cada celda no usada. eij = cij - (ui + vj) 67

2.1 Modelo de Transporte 2.1.5. Método de Distribución Modificada (DIMO)

Costos marginales para las celdas no usadas. eij = cij - (ui + vj) 1) e12 = c12 - (u1 + v2)= 13 - (0 + 11) = 2 2) e14 = c14 - (u1 + v4)= 6 - (0 + 6)

= 0

3) e21 = c21 - (u2 + v1)= 6 - (-7 + 12) = 1 4) e23 = c23 - (u2 + v3)= 10 - (-7 + 4) = 13 5) e24 = c24 - (u2 + v4)= 11 - (-7 + 6) = 12 6) e33 = c33 - (u3 + v3)= 12 - (-2 + 4) = 10

68

2.1 Modelo de Transporte 2.1.5. Método de Distribución Modificada (DIMO)

Plantas Puertos 1

1 12 300

2

2

3 13 0 4

6 1 700 3 10 9 100 200 Demanda 0 400 0 900

4 4 200 10 13 12 10 200

Oferta 6 0 100 500 11 12 0 700 4 500 700 800 500 2000

Paso 2: Prueba de Optimalidad. No hay costos negativos por lo tanto es óptima VO = 300*12+200*4+700*4+100*10+200*9+500*4=$12.000 Ver Transporte RPG Equilibrio

69

2.1 Modelo de Transporte

2.1.6. Modelo de Transporte: Situaciones Especiales

1. Solución en problemas de maximización de transporte 2. El caso en que la oferta excede a la demanda. 3. Eliminación de rutas inaceptables. 4. Degeneración en problemas de transporte. 5. Propiedades especiales del modelo de transporte

70

2.1 Modelo de Transporte

2.1.6. Modelo de Transporte: Situaciones Especiales

1. Solución en problemas de maximización de transporte.

a) Se utilizan los beneficios marginales en lugar de los costos. Se asignará unidades a la celda que tenga el mayor valor marginal y el procedimiento concluirá cuando todas las rutas tengan valores marginales negativos. b) Convertir la tabla de beneficios en una tabla de costo: Se busca el beneficio mayor, en cada celda se le resta al mayor el beneficio de la celda. Ejemplo: 71

2.1 Modelo de Transporte

2.1.6. Modelo de Transporte: Situaciones Especiales Tabla de beneficios Destinos 2

1 Fuentes

1 2 3

Tabla de costo

14

19

12

17

19

15

16

20

11

Destinos 2

1 Fuentes

1 2 3

3

Mayor = 20

3

6

1

8

3

1

5

4

0

9 72

2.1 Modelo de Transporte

2.1.6. Modelo de Transporte: Situaciones Especiales 2. El caso en que la oferta excede a la demanda. Se utiliza un destino ficticio en la tabla de transporte. Se considera como nulo el costo de enviar una unidad a dicho destino desde cada una de las fuentes (orígenes). Si la demanda es mayor que la oferta el problema no tiene solución factible, sin embargo el administrador podría abastecer toda la demanda que sea posible a un costo mínimo. Se utiliza un origen ficticio. El costo de abastecer cualquier destino desde dicho origen será cero. Sin embargo podría haber un cargo por orden no cubierta. Ver Transporte RPG (O>D) y (O= 0 i=1,...,4, j=1,....,4 85

Métodos de Solución Existen varias formas de obtener la solución: a) Listar todas las alternativas posibles con sus costos y seleccionar la de menor costo (algoritmo exhaustivo) b) Método Húngaro: método iterativo a) Listar todas las alternativas: ¿Cuántas alternativas posibles existen? - El primer trabajo se puede asignar de n formas formas posibles - El segundo de n-1 formas - El último sólo de 1 forma En total existen n! formas de hacer la asignación completa 86

Método Húngaro: Paso 0: Construir la matriz de asignación Para obtener la solución óptima cada nueva matriz de asignación debe satisfacer: Propiedad 1: Todos los números son no negativos Propiedad 2: Cada fila y cada columna tiene al menos una celda con un valor cero Paso 1: a) Reducción de filas: Restar el costo menor de cada fila a la fila correspondiente y/o b) Reducción de columnas: Restar el costo menor de cada columna a la columna correspondiente Con esto se crea una nueva matriz con las propiedades 1 y 2 87

Método Húngaro: Paso 2: Determinar si la matriz es reducida (Prueba de Optimalidad). Trazar el menor número de líneas rectas sobre las filas y columnas para cubrir todos los ceros. Si el número de rectas es igual al número de filas o columnas se dice que esta matriz es reducida. Si la matriz no es reducida pasar al paso 3, sino pasar al paso 4

88

Método Húngaro: Paso 3: Movimiento De todas las celdas no cruzadas identifique una con el menor valor y haga lo siguiente: a) Restar el valor a cada celda no cruzada b) Sumar el valor a cada celda de intersección de rectas Volver al paso 2

89

Método Húngaro:

Paso 4: Solución óptima (Asignación) Primero se asigna a las que tengan sólo una alternativa, se van marcando y así sucesivamente Determinar el costo: Se suman todos los costos correspondientes a las asignaciones (o sumar todos los pi y qj). ¿Qué valor se obtiene al sumar todos los valores que se restaron en las reducciones de filas y columnas?

90

Ejemplo: Aplique el método Húngaro al ejemplo Paso 0: Matriz de Asignación

F M O P qj

1 24 14 15 11

2 10 22 17 19

3 21 10 20 14

4 11 15 19 13

pi

Nota: En negrita los menores de cada fila 91

Paso 1: Reducción de filas y columnas

F M O P qj

F M O P qj

1 14 4 0 0

2 0 12 2 8

3 11 0 5 3

4 1 5 4 2 1

pi 10 10 15 11

1 14 4 0 0

2 0 12 2 8

3 11 0 5 3

4 0 4 3 1 1

pi 10 10 15 11

92

Paso 2: Determinar si la matriz es reducida

F M O P qj

1 14 4 0 0

2 0 12 2 8

3 11 0 5 3

4 0 4 3 1 1

pi 10 10 15 11

No es reducida: sólo tres rectas (para ser reducida deben ser 4) Ir al paso 3 93

Paso 3: Movimiento (Seleccionar el menor: restar a las no tachadas, sumar a las intersecciones)

F M O P qj

F M O P qj

1 14 4 0 0

2 0 12 2 8

3 11 0 5 3

4 0 4 3 1 1

pi 10 10 15 11

1 15 4 0 0

2 0 11 1 7

3 12 0 5 3

4 0 3 2 0 1+1

pi 10 10 15 11

Volver al paso 2 !! 94

Iteración paso 2:

F M O P qj

1 15 4 0 0

2 0 11 1 7

3 12 0 5 3

4 0 3 2 0 1+1

pi 10 10 15 11

Se tachan todos los ceros con cuatro rectas, por tanto es óptima Ir al paso 4 !!

95

Paso 4: Asignación

F M O P qj

1 15 4 0 0

2 0 11 1 7

3 12 0 5 3

4 0 3 2 0 1+1

pi 10 10 15 11

Costo = c12 + c23 + c31 +c44 = 10+10+15+13 = 48 Costo   pi   q j

=10 + 10 + 15 + 11 + 1 + 1 = 48 Ver Asignación RPG

96

Modelo de Asignación: Otras consideraciones El modelo de asignación de RPG es un modelo de minimización en el cual el número de vicepresidentes es igual al número de plantas, y todas las asignaciones posibles son aceptables. Consideremos ahora modelos tipo asignación donde no todas las condiciones anteriores se cumplen. En particular se considerarán situaciones en las que: 1 Hay una desigualdad entre el número de “personas” por asignar y el número de “destinos” que requieren personas asignadas. 2 Hay un modelo de maximización 3 Existen asignaciones inaceptables 97

Modelo de Asignación: Otras consideraciones 1. Ofertas y demandas desiguales a) Oferta mayor que la demanda Suponer que el presidente de RPG quiere auditar a la planta de Tilburgo, por tanto tendrá que decidir cual de los cuatro vicepresidentes debe asignar a cada una de las tres plantas restantes. Solución: Se elimina la restricción que requería un vicepresidente para Tilburgo. El resultado de este cambio es que la holgura para uno de los cuatro vicepresidentes será 1 en la nueva solución óptima Ver Asignación RPG (O>D) 98

Modelo de Asignación: Otras consideraciones 1. Ofertas y demandas desiguales b) Demanda mayor que la oferta Suponer que el vicepresidente de Personal tiene que viajar a Illinois durante la primer semana de junio, por lo tanto no puede participar en la auditoría en Europa. Solución: Se agrega un vicepresidente ficticio (igual al modelo de transporte) para obtener una solución factible, pero es claro que una de las plantas quedará sin auditar.

99

Modelo de Asignación: Otras consideraciones 2. Hay un modelo de maximización La respuesta de asignación es un beneficio y no un costo Ejemplo: Suponga que RPG tiene que asignar vendedores a sus territorios de venta. Existen cuatro personas bien capacitadas listas para ser asignadas y tres territorios requieren un nuevo vendedor. Uno de los vendedores no será asignado. En este caso la asignación de un vendedor cualquiera a un territorio se mide por el incremento marginal esperado en la contribución de dicha asignación a las ganancias.

100

Modelo de Asignación: Otras consideraciones 2. Hay un modelo de maximización La matriz de ganancia es la siguiente

Contribución del Vendedor\a A B C D

Territorio 1 $ 40 $ 18 $ 12 $ 25

Territorio 2 $ 30 $ 28 $ 16 $ 24

Territorio 3 $ 20 $ 22 $ 20 $ 27

Ver Asignación Vendedores RPG 101

Modelo de Asignación: Otras consideraciones 3. Situaciones con asignaciones inaceptables

Ejemplo: Suponga que el presidente de RPG no tiene el menor deseo de que el vicepresidente de Operaciones realice una auditoría a la Planta Nancy.

Solución: Asignar un costo arbitrariamente alto a esta “ruta”, de tal modo que al restar de él cualquier número finito se obtiene siempre un valor mayor que otros números relevantes Ver Asignación RPG inaceptable 102

2.3 Modelo de Transbordo Este modelo permite que las unidades no vayan directamente desde un origen a un destino, sino que pasen por nodos intermedios o transitorios. Cada origen, punto intermedio y destino final se representan como nodos y se conectan a través de arcos dirigidos Restricción en cada nodo transitorio: suma flujos entrantes = suma flujos saliente También se puede representar por medio de una matriz donde un mij = 1 cuando existe un enlace directo entre el nodo i y el nodo j; y mij = 0 cuando no hay enlace directo entre estos nodos

103

Modelo de Transbordo: Algoritmo 1

Inicialización: Encuentre un plan de embarque factible que satisfaga todas las restricciones de suministro y demanda, al mismo tiempo que mantiene un equilibrio en todos los nodos de transbordo.

2

Prueba de Optimalidad: Pruebe el plan de embarque actual para ver si es óptimo, es decir, si es el plan que incurre en los costos totales mínimos. Si es así, deténgase con la solución óptima, sino vaya al paso 3.

3

Movimientos: Use el hecho de que el plan de embarque actual no es óptimo para crear un nuevo plan de embarque factible con menos costo total que el actual. Vaya al paso 2.

104

Consideraciones: • Los pasos del algoritmo son análogos a los del algoritmo de pasos sucesivos (escalón). • Tanto los nodos origen como los destinos pueden ser a su vez nodos de transbordo. • Al igual que el modelo de transporte, puede haber desequilibrio, en ese caso se agregan fuentes o destinos ficticios con costo cero. • El numero total del sistema está dado por el total de la oferta o de la demanda. • A cada nodo de transbordo se asigna un suministro (demanda) igual a su suministro (demanda) original (cero, si no coincide originalmente con un destino) más el total de unidades del sistema. Esto permite que todas las unidades puedan pasar por un empalme dado. 105

Ejemplo 1: Determínese un programa de embarque que cubra todas las demandas a un costo mínimo total para los datos correspondientes al siguiente grafo (costo en $). 8

+15 1 +95

3

4

3

5 4

2

3 7

2

4

+70

-30

-30

2 6 -45

106

Solución • • • • •

Los sitios 1 y 2 son orígenes Los sitios 5 y 6 son destinos El sitio 3 es origen y empalme El sitio 4 es destino y empalme La oferta es mayor que la demanda por tanto se requiere un destino ficticio que demande 75 unidades • Agregar 180 unidades a cada empalme (oferta y demanda) • El costo de las unidades que van de un empalme (como origen) a él mismo (como destino) y de cualquier origen al sitio ficticio es cero. • A las rutas no permitidas se les asocia un valor relativamente alto (por 1.000)

107

La tabla inicial es:

3

Destinos 5

4

6

F

Oferta 95

1 3

1000

8

1000

0

Orígenes

2

70 2

7

1000

1000

0

3

195 0

3

4

4

0

4 Demanda

180 1000 180

0 210

1000 30

2 45

0 75

108

La tabla final es:

1

3 20

4 3

Orígenes

2

1000

8

F 75 1000

Oferta 95 0 70

90

7 30

0 4 Demanda

6

70 2

3

Destinos 5

1000 30

3

1000

0

45 4

195 4

0

180 1000 180

180 0 210

1000 30

2

0 45

75

Costo = 20*3+75*0+70*2+90*0+30*3+30*4+45*4+180*0=$590 109

Ejemplo 2: Una corporación necesita transportar 70 unidades de un producto, del sitio 1 a los sitios 2 y 3 en cantidades de 45 y 25 unidades, respectivamente. Las tarifas cij (en miles de pesos por unidad) de carga aérea entre los sitios comunicados por carguero se dan en la tabla, en la cual las líneas punteadas indica que no hay servicio disponible. Determínese un programa de embarque que asigne el número requerido de artículos a cada destino, a un costo mínimo de transporte. Ningún embarque requiere de vuelo directo, se permiten los envíos empleando puntos intermedios.

1 2 3 4

1

2

3

4

.... 38 56 34

38 ... 27 ...

56 27 ... 19

34 ... 19 ... 110

Ejemplo 3:

100

7

1

2 4

8

4

6

6

6 200

3

2 4

150

3

120

8

Nodos de transbordo

5

9

80

10

70

8 7

7 5 4

7

5 6

11

110

111

Planteamiento del modelo PL : Plantear el modelo de PL para el ejemplo mostrado en el grafo anterior.

112

2.4. Modelos de Redes 2.4.1 Teoría de Grafos 2.4.2 Modelo de la Ruta más corta 2.4.3 Modelo del Árbol Expandido Mínimo 2.4.4 Problema del Flujo Máximo

113

2.4.1 Introducción a la Teoría de Grafos Grafo no dirigido: Un grafo no dirigido G consiste en un conjunto V de vértices (o nodos) y un conjunto E de lados (ramas o enlaces) tales que cada lado e ε E está asociado a un par no ordenado de vértices v y w. Si un lado e está asociado a un único par de vértices v y w, entonces e= (v,w) o e=(w,v). Grafo dirigido: Un grafo dirigido (o digrafo) G consiste en un conjunto V de vértices (o nodos) y un conjunto E de lados (o ramas) tales que cada lado e ε E está asociado a un par ordenado de vértices. Si un lado e está asociado a un par ordenado único de vértices v y w, se escribe e = (v,w). 114

2.4.1 Introducción a la Teoría de Grafos Se dice que un lado e = (v,w) de un grafo (dirigido o no dirigido) es incidente en v y w. Se dice que los vértices v y w son incidentes en e y también son vértices adyacentes. Si G es un grafo (dirigido o no dirigido) con un conjunto de vértices V y un conjunto de lados E, se escribe G = (V,E) Nodo (Vértice): Un círculo de una red utilizada para representar una planta, almacén o tienda. Nodo de Suministro: Nodo desde le cual los productos se van a enviar. 115

2.4.1 Introducción a la Teoría de Grafos Nodo de demanda: Nodo que va a recibir los productos para cumplir con una demanda conocida. Nodo de transbordo: Nodo que recibe productos desde otros nodos para su distribución. Arco (enlace): Línea de una red que conecta un par de nodos. Se le utiliza para representar una ruta válida desde el nodo origen al nodo de distribución.

116

2.4.1 Introducción a la Teoría de Grafos Arco dirigido: Indica el sentido de movimiento de los productos. Camino: Una secuencia de nodos en una red unidos por arcos (dirigidos o no dirigidos) Trayectoria (lazo): Es un camino cerrado (ciclo) donde el primer nodo es a su vez el último.

117

2.4.1 Introducción a la Teoría de Grafos Representación de un grafo: Un grafo se puede representar matemáticamente como: a) Una matriz b) Una lista enlazada c) Árbol Representación Matricial i) Matriz de Adyacencia ii) Matriz de costo (beneficio)

118

2.4.1 Introducción a la Teoría de Grafos (cont.) Matriz de Adyacencia: Para un grafo G, es una matriz A de dimensión NxN, donde A[i,j] es verdadero (1) si, y sólo si, existe un arco que vaya del vértice i al vértice j. En ausencia de arco directo se representa generalmente por 0.

Ejemplo:Dado el siguiente grafo encontrar su matriz de adyacencia

119

2.4.1 Introducción a la Teoría de Grafos (cont.) 1

2

3

4 1 1

2

3

1

1

2 3 4

4

1 1 1 120

2.4.1 Introducción a la Teoría de Grafos (cont.) Matriz de Costo: Para un grafo G etiquetado, es una matriz C de dimensión NxN, donde A[i,j] es el costo (valor de la etiqueta) si, y sólo si, existe un arco que vaya del vértice i al vértice j. En ausencia de arco directo se representa generalmente por infinito (costo extremadamente alto, para la simulación se hace uso de un valor fuera de contexto). Ejemplo:Dado el siguiente grafo encontrar su matriz de costo

121

2.4.1 Introducción a la Teoría de Grafos (cont.) 10

1 15

2 12

20 5

3

1 1

4

2

3

10

15

2 3 4

4

12 20 5 122

2.4.1 Introducción a la Teoría de Grafos (cont.)

Para un grafo no dirigido, tanto la matriz de adyacencia como la matriz de costo son simétricas, esto es:

A[i,j] = A[j,i] ó

C[i,j] = C[j,i]

123

Ejemplo Introductorio Seymour Miles es el gerente de distribución de Zigwell. Zigwell distribuye sus motores oruga en cinco estados del medio oeste. Por lo regular, Seymour Miles tiene 10 aparatos E-9 in situ en lo que designaremos como local 1. Estos tractores deben ser enviados a los dos locales de construcción más importantes designados como 3 y 4. Se necesitan tres E-9 en el local 3 y siete en el local 4. Debido a itinerarios arreglados con anterioridad, relativos a la disponibilidad de conductores, los tractores solo pueden ser distribuidos de acuerdo con las rutas alternativas que se muestran en el grafo de la figura. La figura tiene un número +10 en el nodo 1, esto significa que hay 10 aparatos E-9 disponibles (oferta). Los indicadores -3 y -7 asociados a los locales 3 y 4, respectivamente, denotan los requerimientos (demandas) de éstos. 124

-3 3 c23 +10

u23 c12

1

2 u12

c24 u24 c25 u25

c34

u34 c43 u43 -7 4

c53

u53

c54 c54 5

Rutas alternativas para el destino 3 1-2-3, 1-2-4-3, 1-2-5-4-3, 1-2-5-3 125

Los costos cij son unitarios. Por ejemplo el costo de recorrer el arco (5,3) es c53 por cada tractor. Debido a los acuerdos sostenidos con los conductores, Zigwell debe cambiarlos en cada local que se encuentre sobre la ruta. Las limitaciones en la disponibilidad de conductores ocasionan que haya una cota superior en el número de tractores que pueden recorrer cualquier arco dado. Por ejemplo: u53 es la cota superior o capacidad en el arco (5,3). El problema de Sygmour consiste en encontrar un plan de embarque que satisfaga la demanda y las restricciones de capacidad a costo mínimo. 126

El problema en particular se conoce como modelo de transbordo con capacidades. Expresar el problema como un PL a) Variables de decisión

xij = número total de E-9 que se enviarán a través del arco (i,j). = flujo del nodo i al nodo j

127

b) Función Objetivo MIN Z

=C12X12+C23X23+C24X24+C25X25+C34X34+C43X43+C53X53+C54X54

c) Restricciones sa + X12

= 10

- X12+X23+X24+X25 -X23

= 0 -X43 -X53 +X34

-X24 -X25

+X43 +X53

= -3

-X34 -X54 = -7

Balance de flujo

+X54 = 0

0  xij  cij , todos los ar cos (i,j) de la red 128

Matriz Incidencia nodo-arco a

r

c

o

Nodo (1,2) (2,3) (2,4) (2,5) (4,3) (5,3) (3,4) (5,4)

LD

1

+1

0

0

0

0

0

0

0

10

2

-1

+1

+1

+1

0

0

0

0

0

3

0

-1

0

0

-1

-1

+1

0

-3

4

0

0

-1

0

+1

0

-1

-1

-7

5

0

0

0

-1

0

+1

0

+1

0

129

Formulación General del Modelo de Transbordo con Capacidades Xij denotan el flujo del nodo i al nodo j a lo largo del arco que conecta esos nodos. Lj representa la oferta en el nodo j minimice

s.a.



c x ij ij ij



x  x  L , j  1 , 2 ,...., n  jk kj j k k

0  xij  cij , todos los ar cos (i,j) de la red 130

Resolver para las siguientes capacidades y costos Capacidad de\ a Sitio 1 Sitio 2 Sitio 3 Sitio 4 Sitio 5

Sitio 1

Costo Unitario Sitio 1 de\ a Sitio 1 Sitio 2 Sitio 3 Sitio 4 Sitio 5

Sitio 2 10

Sitio 2

Sitio 3

Sitio 4

Sitio 5

4

3 2

3

4 3

5

Sitio 3

Sitio 4

Sitio 5

$45

$50 $60

$20

$100

$85 $10

$55

Ver transbordo con capacidades 131

2.4.2 Modelo de la Ruta más corta Situaciones: Se pueden dar dos casos para representar la red: a

Como grafo no dirigido

b

Como grafo dirigido

Cualquiera que sea el caso corresponde a grafos ponderados (con peso)

132

2.4.2 Modelo de la Ruta más corta a) Algoritmo: Grafo no dirigido 1 Considerénse todos los nodos que estén directamente conectados con el origen. Etiquetarlos con la distancia al origen y su nodo predecesor. Etiquetas temporales, [distancia, nodo]. 2 De entre todos los nodos con etiquetas temporales, escoger el que tenga la distancia menor y se marca como permanente. Si todos están con etiquetas permanentes se va al paso cuatro.

133

2.4.2 Modelo de la Ruta más corta (GND) Algoritmo: 3

Todo nodo que no tenga etiqueta permanente, tendrá etiqueta temporal o estará sin etiqueta. Sea L el último nodo con etiqueta permanente. Considerénse todas las etiquetas de los vecinos de L (directamente conectados a L mediante un arco). Para cada uno de estos nodos calcúlese la suma de su distancia a L. Si el nodo en cuestión no está etiquetado, asígnese una etiqueta temporal que conste de esta distancia y de L como predecesor. Si el nodo en cuestión ya tiene etiqueta temporal, cámbiese sólo si la distancia recién calculada es menor que la componente de distancia de la etiqueta actual. En este caso, la etiqueta contendrá esta distancia y a L como predecesor. Regresar al paso 2 134

2.4.2 Modelo de la Ruta más corta (GND) Algoritmo: 4 Las etiquetas permanentes indican la distancia más corta entre el nodo origen a cada nodo de la red. También indican el nodo predecesor en la ruta más corta hacia cada nodo. Para encontrar el camino más corto de un nodo dado, comiéncese en él y retroceda al nodo anterior. Continuar con el recorrido hasta llegar al origen.

135

2.4.2 Modelo de la Ruta más corta (GND) Ejemplo: Para el siguiente grafo encontrar la distancia más corta desde el nodo H al resto de los nodos. 7

1

8

2

6

3

7

H

4 1 4

1

3

3 3 1

5

1 6

2

2

136

2.4.2 Modelo de la Ruta más corta (GND) Solución: (8,H)

7

1

8

ó

2

6

3

7

H

(9,7)

(9,4)

4 1

(5,1) 4

1

3

(6,3) 1

1 (4,H)

2

6

3 3 5 2

(6,3) 1:Ver ejemplo 1 Ruta mas corta

2: Hacer problema 19 guía 2 (Ejemplo 2 Ruta mas corta

(8,2) 137

2.4.2 Modelo de la Ruta más corta (GD) b) Algoritmo de Dijkstra Es una técnica exhaustiva, esto es, prueba todas las alternativas posibles. Opera a partir de un conjunto S de vértices cuya distancia más corta desde el origen ya es conocida. Inicialmente S contiene sólo el nodo de origen. En cada paso se agrega algún vértice restante v a S, cuya distancia desde el origen es la más corta posible. Para cada paso del algoritmo, se utiliza una matriz D para registrar la longitud del camino más corto a cada vértice.

138

2.4.2 Modelo de la Ruta más corta (GD) Algoritmo de Dijkstra INICIO 0) V = {1, 2, 3, 4, ..., n} 1) S = {1} // nodo 1 se supone que es el origen 2) Para i=2 Hasta n Hacer 3) Di = C1i 4) Para i=1 Hasta n-1 Hacer 5) Elegir un vértice w en V-S tal que Dw sea un mínimo 6) agregar w a S 7) Para cada vértice v en V-S Hacer SI ((Dw+Cwv)