• Author / Uploaded
• Nicolas Ariel Labra Ochoa

• Categories
• Transporte
• Física y matemáticas
• Matemáticas
• Ciencia
• Economias

Citation preview

Método de Transporte

Descripción del problema de transporte 1.Un conjunto de m puntos de suministro a partir de los cuales se envia un bien. El punto de suministro abastece a lo mas Si unidades. 2.Un conjunto de n puntos de demanda a los que se envía el bien. El punto de demanda j debe recibir a lo menos dj unidades del bien. 3.Cada unidad producida en el punto de suministro i y enviada al punto de demanda j incurre en un costo Cij

Método de Transporte 

Modelo 



Determinación de un plan de costo mínimo para transportar mercancías desde varia fuentes (ej. Fabrica, CD) a varios destinos (ej. Almacenes, Bodegas)

Objetivo del Modelo 

Determinar la cantidad (Xij) que se enviará de cada fuente de suministro (i) a punto de demanda (j), tal que minimice el costo total

Método de Transporte 

Supuesto 



El costo de transportar en una ruta es directamente proporcional al número de unidades transportadas

Datos del Modelo 





Nivel de oferta (recurso) en cada fuente u origen (Si) Cantidad de demanda en cada destino (dj) Costo de transporte unitario (Cij) del bien entre cada fuente de suministro (i) y cada destino (j)

Método de Transporte 

Representación del Modelo Fuentes de Suministro S1

1

Destinos c11, X11 1

Unidades de oferta

S2

2 2

. . .

. . .

Sm

m

n

cmn, Xmn

nodo

Red de m fuentes y n destinos

arco

Ruta por la cual se transporta el mercadería

d1

d2

dn

Unidades de demanda

Método de Transporte 

Función Objetivo Minimizar Z = Σ Σ cijxij m



Restricciones 

Σ xij ≤ Si

i = 1,2,…., m

La suma de los envíos a un destino debe satisfacer la demanda 



i=1 j=1

La suma de los envíos desde una fuente no puede ser mayor que su oferta 



n

Σ xij ≥ di

j = 1,2,…., n

No - Negatividad 

xij ≥ 0

para todas las i y j

Método de Transporte 

El modelo descrito implica que la oferta total (ΣSi) debe ser cuando menos igual a la demanda total(Σdj)



Cuando la oferta total es igual a la demanda total (ΣSi = Σdj) , la formulación resultante recibe el nombre de modelo de transporte equilibrado

Análisis de Caso MG Auto Co. 









MG Auto Co. tiene plantas en Los Ángeles, Detroit y Nueva Orleans. Sus centros de distribución principales están ubicados en Denver y Miami. Las capacidades de las tres plantas durante el trimestre próximo son de 1000, 1500 y 1200 automóviles. Las demandas trimestrales en los dos centros de distribución son de 2300 y 1400 vehículos. El costo de transporte de un automóvil por tren es aproximadamente de 8 centavos por milla.

Análisis de Caso MG Auto Co. 



El diagrama de la distancia recorrida (millas) entre las plantas y centros de distribución es el siguiente: El costo por automóvil calculado a partir del costo por milla recorrido (redondeados a números enteros) son los siguientes

Denver

Miami

Los Ángeles

1000

2690

Detroit

1250

1350

Nueva Orleans

1275

850

Denver

Miami

Los Ángeles

80

215

Detroit

100

108

Nueva Orleans

102

68

Análisis de Caso MG Auto Co. 

Variables de Decisión  xij = Nº de automóviles transportados de la planta i (fuente) al centro de distribución j (destino)



Función Objetivo  Minimizar Z = 80x11 + 215x12 + 100X21 + 108x22 + 102x31 + 68x32 Sujeto a  Restricciones de Capacidad en Planta



x31 + x 32

≤ 1000 ≤ 1500 ≤ 1200

x31 + x32

≥ 2300 ≥ 1400

x11 + x12 x21 + x22 

Restricciones de Demanda x11 +



x21 + x12 + x22

Restricciones de No – Negatividad xij ≥ 0 para todas las i y j

Análisis de Caso MG Auto Co. 

Uso de Tabla de Transporte 

Tabla en forma de matriz donde sus filas representan las fuentes y sus columnas representan los destinos. Los elementos de costo cij se resumen en la esquina superior derecha de la celda en la matriz (i,j) Destinos

Fuentes

Denver Los Ángeles Detroit Nueva Orleans

Demanda

Miami

c11 x11

c12 x12

c21 x21

c22 x22

c31 x31

c32 X32

2300

1400

Oferta 1000 1500 1200

Análisis de Caso MG Auto Co. 

Uso de Tabla de Transporte 

Los elementos de costo cij se resumen en la esquina superior derecha de la celda en la matriz (i,j) Destinos

Fuentes

Denver Los Ángeles Detroit Nueva Orleans Demanda

Miami

80 x11

215 x12

100 x21

108 x22

102 x31

68 X32

2300

1400

Oferta 1000 1500 1200

Análisis de Caso MG Auto Co. 

Suponga que en el caso MG Auto Co. No se desea enviar vehículos desde la planta de Detroit al centro de Distribución de Denver.

¿Cómo se puede incorporar esta condición en el modelo de MG Auto Co.?

Modelo de Transporte en Desequilibrio 

Cuando la oferta total (ΣSi) es menor que la demanda total (Σdj) 

Suponga que en el caso MG Auto Co. la capacidad de la planta en Detroit baja de 1500 a 1300  La oferta total (ΣSi = 1000+1300+1200 = 3500) < que la demanda total (Σdj = 2300 + 1400 = 3700)  No será posible cubrir la Dda. en los centros de distribución

Modelo de Transporte en Desequilibrio 

Reformulación del problema de transporte de manera que distribuya la cantidad faltante = 3700 – 3500 = 200  Agregar una Fuente (planta) Ficticia con capacidad igual a la capacidad que falta ( 200 automóviles)  Se permite que la planta ficticia, en condiciones normales, envíe su producción a todos los centros de distribución  Como la planta no existe y no habrá ningún envío físico, el costo de transporte unitario corresponde al costo de escasez, en caso de no existir se asigna costo cero.

Modelo de Transporte en Desequilibrio Destinos

Fuentes

Denver Los Ángeles

Detroit Nueva Orleans Planta Ficticia Demanda

Oferta

Miami

80

x11

215

x12 100

x21

108 x22

102 x31

68 X32

0 x41

0 X42

2300

1400

1000

1300 1200 200

Modelo de Transporte en Desequilibrio 

Cuando la oferta total (ΣSi) es mayor que la demanda total (Σdj) 

Suponga que en el caso MG Auto Co. la demanda en el centro de distribución de Denver disminuye a 1900  La oferta total (ΣSi = 1000+1500+1200 = 3700) > la demanda total (Σdj = 1900+ 1400 = 3300)

Modelo de Transporte en Desequilibrio 

Reformulación del problema de transporte de manera que distribuya la sobrante = 3700 – 3300 = 400  Agregar un Destino (centro de distribución) Ficticio con demanda igual al excedente de producción (400 automóviles)  Se permite que el destino ficticio, en condiciones normales, recibe automóviles desde todos los centros de distribución  Como el centro de distribución no existe y no habrá ningún envío físico, el costo de transporte unitario correspondiente es cero

Modelo de Transporte en Desequilibrio

Fuente Los Ángeles Detroit Nueva Orleans Demanda

Destino Denver

Miami

80 x11

215 x12

100 x21

108

102 1900

0 x13

x22

x31

Centro Ficticio

0 x23

68 X32 1400

0 X33 400

Oferta 1000 1500 1200

Modelo de Transporte en Lindo MODEL SETS: PLANTAS/P1,P2,P3,…./:CAP; DEMANDAS/D1,D2,…./:DEM; ARCOS(PLANTAS,DEMANDAS):COSTOS,EMBARQUE; ENDSETS MIN=@SUM(ARCOS:COSTOS*EMBARQUES) @FOR(DEMANDAS(J): @SUM(PLANTAS(I):EMBARQUE(I,J))≥DEM(J)); @FOR(PLANTAS(I): @SUM(DEMANDAS(J):EMBARQUE(I,J))≤CAP(I)); DATA: CAP=1000,1300,1200; DEM=2300,1200; COSTOS=80,215, 100, 108 102, 68; ENDDATA END

Solución del Método Simplex de Transporte 



Formato de la tabla de transporte  m orígenes  n destinos  Si recursos en el origen i  Demanda di en el destino j  Costo Cij por unidad distribuida desde el origen i al destino j

Costo por Unidad Distribuida Fuentes (origen)

1 2 . m Demanda

Formato tabla de coeficientes de restricciones X11

X12

…

X1n

X21

X22

…

X2n

…

Xm1

1 2

…

.

.

.

m 1 2 … n

……

Recursos

Destinos 1

2

C11 C21 . Cm1 d1

C12 C22 . Cm2 d2

Xm2

…

……

n

…….

C1n C2n . Cmn dn

S1 S2 . Sm

Xmn

S1 S2 … Sm

Restricciones de Origen

d1 d2 … dn

Restricciones de Demanda

Solución del Método Simplex de Transporte 

Método Simplex Simplificado o Simplex de Transporte 1. El método simplex de transporte no utiliza variables artificiales 2. La fila (0) actual se puede obtener sin usar ninguna otra fila, con solo calcular los valores de ui y vj. 

Como cada variable básica debe tener coeficiente cero en la fila (0), estos valores se pueden obtener resolviendo el sistema de ecuaciones:  cij - ui - vj = 0 para cada i y j tal que Xij es variable básica



Lo cual se puede hacer de manera directa de la tabla de costos

Reglón cero de tabla simplex después de cualquier iteración VB

EC

Z

Xij

Xj

Xm+j

Z

0

-1

Cij - ui - vj

M-ui

M-vj

LADO DERECHO



ui = múltiplo del reglón i original que se resto (de manera directa o indirecta) del reglón 0 original en todas las iteraciones del método simplex que condujeron al tableau actual



vj = múltiplo del reglón m+j original que se resto (de manera directa o indirecta) del reglón 0 original en todas las iteraciones del método simplex que condujeron al tableau actual

Reglón cero de tabla simplex después de cualquier iteración 

Si Xij es una variable no básica Cij - ui - vj se interpreta como la tasa a la que cambiaria Z si se aumenta el valor de Xij



El reglón 0 puede obtenerse sin utilizar ningún otro reglón, tan solo con calcular los valores de ui y vj de manera directa.



Como cada variable básica debe un coeficiente igual a cero en el reglón 0, estos valores se pueden obtener de ui y vj si de resuelve el sistema de ecuaciones Cij – ui – vj = 0 para toda i,j tal que Xij es VB

Solución del Método Simplex de Transporte 

Método Simplex Simplificado o Simplex de Transporte 3. La variable básica que sale se puede identificar de manera sencilla, ya que el modelo permite ver cómo debe cambiar la solución cuando crece el valor de la variable entrante. 

Como resultado, la nueva solución básica se puede identificar sin cálculos posteriores en la tabla simplex

Solución del Método Simplex de Transporte 

Para el desarrollo del modelo de transporte a mano es conveniente registrar esta información en la tabla simplex de transporte Destinos

1

……

2

Recursos

n

1

c11

c12

……

C1n

2

c21

C21

……

c2n

S1 S2

Fuentes …… cm1

3m Demanda

cm1

d1

d2

… cmn

…… …..

dn

vj 

Información adicional que se agrega en cada celda: Si Xij es una variable básica

Si Xij es una variable no básica

cij (Xij)

cij cij – ui - vj

Sm Z=

ui

Solución del Modelo de Transporte 

Etapa : Determinar una solución factible inicial   



Destinos Recursos

Regla de la Esquina Noroeste Método de Costo Mínimo Método de Aproximación de Vogel

1

2 10

1

Etapa : Determinar la variable que entra, que se elige entre las variables no-básicas. Si todas estas variables satisfacen la condición de optimidad Origen 2 (método Simplex), detenerse; de lo contrario continuar con el paso 3

x11

Etapa : Determinar la variable que sale (condición de factibilidad) de entre las variables de la solución inicial básica actual y obtener una nueva solución básica. Regresar al paso 2

3 Demanda

0 x12

12 x21

4 20

x13 7

x22 0



3

14

11 x14

9 x23 16

15

20 x24

25

18

x31

x32

x33

x34

5

15

15

10

5 45

Solución Básica: Regla de la Esquina Noroeste 

Determinación de la Solución Inicial Se requiere que ΣSi = Σdj 



Este requisito da origen a m + n – 1 ecuaciones independientes Por lo tanto, una solución factible debe incluir m + n – 1 variables básicas.

Solución Básica: Regla de la Esquina Noroeste 













Asignar la máxima cantidad posible a la variable X11 de manera que se satisfaga totalmente la demanda (columna) o bien, se agote el recurso (fila). Se tacha la columna ( o fila) haciendo que las variables sean iguales a cero. Cuando simultáneamente se satisfacen una columna o fila, solo se tacha una de ellas. Esta condición garantiza la ubicación automática de las variables NO-básicas cero, si las hay. Ajustar la cantidad de recursos y demanda de todas las filas y columnas no tachados. La cantidad factible máxima se asigna al primer elemento de la nueva columna (fila). El proceso se termina cuando se deja de tachar exactamente una fila o una columna.

Solución Básica:

N

Regla de la Esquina Noroeste 

X11 = 5 Como se satisface la demanda , se tacha la columna 1  Los recursos en la fila 1 se reducen a 10

O

Destinos Recursos



1

2

3

10 1

x11= 5 X11

0 x12

12 Origen 2

x21

3 Demanda

20 x13

7 x22

0

4

14

11 x14

9 x23 16

15 / 10

20 x24

25

18

x31

x32

x33

x34

5

15

15

10

5 45

Solución Básica:

N

Regla de la Esquina Noroeste 

X11 = 5 Como se satisface la demanda , se tacha la columna 1  Los recursos en la fila 1 se reducen a 10

O

Destinos Recursos





1

3

10 1

X12 = 10 Como se agota el recurso se tacha la fila  Falta satisfacer una demanda de 5 unidades en la columna 2

2 0

X11 =5 X12 x12 =10 12



Origen 2

x21

3 Demanda

20 x13

7 x22

0

4

14

11 x14

9 x23 16

20 x24

25

18

x31

x32

x33

x34

5

15 /

15

10

5

15 / 10

5 45

Solución Básica:

N

Regla de la Esquina Noroeste 

X11 = 5

O

Destinos

Como se satisface la demanda , se tacha la columna 1  Los recursos en la fila 1 se reducen a 10 



X12 = 10 Como se agota el recurso se tacha la fila 1  Falta satisfacer una demanda de 5 unidades en la columna 2

Recursos 1

1

Como se satisface la demanda, se tacha la columna 2  Los recursos en la fila 2 se reducen a 20 unidades

0

X11 = 5 X12 = 10 12

Origen 2

x21

3 Demanda

4 20

x13

7 X22x22 =5

0

X22 = 5 

3

10





2

14

11 x14

9 x23 16

20 x24

25 / 20

18

x31

x32

x33

x34

5

15 /

15

10

5

15 / 10

5 45

Solución Básica:

N

Regla de la Esquina Noroeste 

X23 = 15  Como se satisface la demanda , se tacha la columna 3  Los recursos en la fila 2 se reducen a 5

O

Destinos Recursos 1

2

3

10 1

0

X11 = 5 X12 = 10 12

Origen 2

x21

Demanda

20 x13

7

14

11 x14

9

X22 = 5 X23 x23 =15 0

3

4

16

20 x24

25 / --20 5

18

x31

x32

x33

x34

5

15 /

15

10

5

15 / 10

5 45

Solución Básica:

N

Regla de la Esquina Noroeste 

X23 = 15 Como se satisface la demanda , se tacha la columna 3  Los recursos en la fila 2 se reducen a 5

O

Destinos Recursos





1

3

10 1

0

X11 = 5 X12 = 10

X24 = 5 Como se agota el recurso se tacha la fila 2  Falta satisfacer una demanda de 5 unidades en la columna 4

2

12



Origen 2

x21

Demanda

20 x13

7

11 x14

9

14

16

25 / --20 5

18

x31

x32

x33

x34

5

15 /

15

10 /

5

15 / 10

20

X22 = 5 X23 = 15 X24x24= 5 0

3

4

5

5 45

Solución Básica:

N

Regla de la Esquina Noroeste 

X23 = 15 Como se satisface la demanda , se tacha la columna 3  Los recursos en la fila 2 se reducen a 5

O

Destinos





X24 = 5 Como se agota el recurso se tacha la fila 2  Falta satisfacer una demanda de 5 unidades en la columna 4

Recursos 1

X34 = 5

1

0

X11 = 5 X12 = 10 12

Origen 2

x21

3

4 20

x13

7

11 x14

9

14

16

25 / --20 5

18

x31

x32

x33

X34x34= 5

5

15 /

15

/ 10 5

5

15 / 10

20

X22 = 5 X23 = 15 X24 = 5 0

Como se satisface simultáneamente la demanda y se agota la oferta, solo se tacha la fila 3 o la Demanda columna 4.  El proceso termina 

3

10





2

5 45

Solución Básica:

N

Regla de la Esquina Noroeste 

Solución Básica Inicial  Las variables básicas son:  X11=5, X12=10,  X22=5, X23=15,  X24=5 y X34=5 



Las variables restantes son No- básicas e iguales a cero

El costo de transporte asociado es: Z = 5*10 + 10*0+ 5*7 + 15*9 + 5*20 + 5*18 = $ 410

O

Destinos Recursos 1

2

3

10 1

0

X11 = 5 X12 = 10 12

Origen 2

x21

Demanda

20 x13

7

11 x14

9

14

16

15

20

X22 = 5 X23 = 15 X24 = 5 0

3

4

25

18

x31

x32

x33

X34 = 5

5

15

15

10

5

45

Solución Básica: Método del costo Mínimo 

Asignar el valor más grande posible a la variable con el menor costo unitario en toda la tabla 

Ajustar los recursos (fila) y demanda (columna)



Tachar la fila o columna satisfecha





1

Los empates se rompen en forma arbitraria





Destinos

Si una fila o columna se satisfacen simultáneamente solo una puede tacharse

Repetir el proceso asignando el mayor valor posible a la variable con menor costo unitario, hasta que quede una columna o fila sin tachar Determinar el resto de las variables sin asignación

2

3

10 1

x11

0 x12

12

Origen 2

x21 0

3 Demanda

4 20

x13

7 x22 14

Recurso s

9 x23 16

11 x14

15

20 x24

25

18

x31

x32

x33

x34

5

15

15

10

5 45

Solución Básica: Método del costo Mínimo 

X12 y X31 tienen costos c12 = 0 y c31 = 0, se elige X12  





X12 = 15 Se satisface la demanda y la oferta. La nueva demanda es cero y la nueva oferta es cero Se tacha la columna 2

Se elige X31  



X31 = 5 Se satisface la demanda y la oferta. La nueva demanda es cero y la nueva oferta es cero Se tacha la fila 3

Destinos Recursos 1

2

3

10 1

x11

0 X12x12 =15

12 Origen 2

x21

3

Demanda

20 x13

7 x22

0

4

14

11 x14

9 x23 16

20 x24

25

18

Xx3131 =5

x32

x33

x34

--5

--15 0

15

10

0

15 --- 0

--- 50 45

Solución Básica: Método del costo Mínimo 

Se elige X23, c23 = 9  





X23 = 15 Se satisface la demanda. La nueva demanda es cero y la nueva oferta es 25 -15 = 10 Se tacha la columna 3

Se elige X11, c11 = 10 

 

Como la demanda y oferta restantes son cero X11 = 0 Se tacha la columna 1

Destinos Recursos 1

1

Origen 2

2 10

0

x11= 0 X11

X12x12 =15

12

7

x21

x22 0

3

Demanda

3

4 20

x13

x14 9

X23x23 =15

14

11

16

20 x24

x32

x33

x34

--5

--15 0

--15

10

0

--25 10

18

Xx =5 3131

0

15 --- 0

--- 50 45

Solución Básica: Método del costo Mínimo 

Como solo queda una columna sin tachar se determinan las variables básicas remanentes:  





X14 = 0 X24 = 10

Costo = 0*10 + 15*0 + 0*11 + 15*9 + 10*20 + 5*0 = $ 335

Este costo es menor que el obtenido por la regla de la Esquina Noroeste

Destinos Recursos 1

1

Origen 2

2 10

0

x11= 0 X11

X12x12 =15

12

7

x21

x22 0

3

Demanda

3

4 20

x13

11 X14 =0 x14

9

20

X23x23 =15

X24x24 =10

16

18

14

Xx =5 3131

x32

x33

x34

--5

--15 0

--15

10

0

0

15 --- 0

--25 10

--- 50 45

Solución Básica: Método de Aproximación de Vogel (VAM) 

Método heurístico que suele producir una mejor solución inicial que los dos métodos anteriores.



VAM suele producir una solución inicial óptima, o próxima al óptimo



Costa de tres pasos

Solución Básica: Método de Aproximación de Vogel (VAM) 

Destinos

PASO 1: 

Evaluar una penalización para cada fila (columna) restando el menor elemento de costo de la fila (columna) del elemento de costo menor siguiente en la misma fila (columna)

1

2 10

1

x11

0 x12

12 Origen

2

x21

Demanda

 

11 x14

9 x23

14

x24

16 x33

x34

5

15

15

10

Destinos

F1: 10 – 0 = 10;Penalización = 10 F2: 9 – 7 = 2; Penalización = 2 F3: 14 – 0 = 14; Penalización = 14

2

3

10 1

x11

0 x12

12 Origen

2

x21

x22 0

3 Demanda

20

7 14

11 x14

9 x23 16

5

Recursos Penalización

4

x13

25

18

x32

1

15

20

x31

Filas 

20 x13

x22

Recursos

4

7

0 3



3

15

10

25

2

5

14

20 x24 18

x31

x32

x33

x34

5

15

15

10

Solución Básica: Método de Aproximación de Vogel (VAM) Destinos 

1

PASO 1

2

3

10 1 

Columnas

x11

0 x12

   

C1: 10 – 0 = 10; Penalización = 10 C2: 7 – 0 = 7; Penalización = 7 C3: 16 – 0 = 16; Penalización = 16 C4: 18 – 11 = 7; Penalización = 7

2

x21

x22

Demanda

11 x14

7

0 3

20 x13

12 Origen

Recursos Penalización

4

9 x23

14

x24

16 x33

x34

5

15

15

10

Destinos 3

10 1

x11

0 x12

12 Origen

2

x21

x22 0

3

20

7

9

14

5

14

11 x14

x23

2

Recursos Penalización

4

x13

25

18

x32

2

10

20

x31

1

15

15

10

25

2

5

14

20 x24

16

18

x31

x32

x33

x34

Demanda

5

15

15

10

Penalización

10

7

7

7

Solución Básica: Método de Aproximación de Vogel (VAM) 

Destinos

PASO 2:  Identifique la fila o columna con la mayor penalización, rompiendo empates en forma arbitraria.  

1

2



Ajústese la oferta y la demanda y táchese la fila o columna satisfecha. Si una fila o columna se satisfacen al mismo tiempo, sólo una de ellas debe tacharse, y a la fila (columna) restante se le asigna una oferta (demanda) cero. Cualquier fila o columna con oferta o demanda cero no debe utilizarse para calcular penalizaciones futuras (en el paso 3)

x13 7

x21

x24

16

x32

x33

x34

5 0 10

15 7

15 7

10 7

Destinos 2

10 1

x12 12

Origen

3

0

2

x22

20 x13

2

0 5

14 14

11 x14

9 x23

25

Recursos Penalización

4

7

10

18

x31 X31 =5

1

15

20

x23

14

11 x14

9

x22 0

Demanda Penalización

20

x12

12 Origen

Recursos Penalización

4

0

x11

3 

3

10 1

Fila 3

Asigne el mayor valor posible a la variable con el costo más bajo de la fila o columna seleccionada.

2

15

20 x24

25

0 3 Demanda Penalización

0

X31=5 0

15

15

10

Solución Básica: Método de Aproximación de Vogel (VAM) 

PASO 3: a) si solo hay una filo o columna sin tachar deténgase 1 b) Si solo hay una fila (columna) con oferta (demanda) positiva sin tachar, determínese las variables básicas de la Origen 2 fila (columna) a través del método de costo mínimo 3 c) Si todas las filas y columnas sin tachar Demanda tienen oferta y demanda cero (asignadas), determínese las variables Penalización básicas cero a través del método de costo mínimo. Deténgase d) De lo contrario, calcúlense las penalizaciones de las filas y columnas no tachadas y después diríjase al paso 2. 1 (Las filas y columnas con oferta y demanda cero asignadas no deben utilizarse para determinar penalizaciones. Origen 2

1 10

x12 12

x13 7

x22 0 X31=5 0

Recursos Penalización

4 11 x14

9 x23

1

15

20 x24

25 0

15

15

10

Destinos 2 10

3 0

x12 12

Recursos Penalización

4 20

x13 7

x22

 Nuevo conjunto de penalizaciones

 ( la fila 3 con oferta cero no se utiliza)

Destinos 2 3 0 20

11 x14

9 x23

15

11

25

2

0

---

20 x24

0 3

X31=5

Demanda

0

15

15

10

Penalización

-

7

11

9

Solución Básica: Método de Aproximación de Vogel (VAM) Destinos 

Nuevo conjunto de penalizaciones

1

2 10

1 

La fila 1 y columna 3 empatan con penalización = 11. 

 



Se elige la columna 3 en forma arbitraria Se asigna X23 = 15 Se ajusta la demanda a cero y la oferta a 25-15 = 10 Se elimina la columna 3

0 x12

12 Origen

3

2

20 x13

7 x22

Recursos Penalización

4 11 x14 9

x23

15

11

25

2

0

---

20 x24

0 3

X31=5

Demanda

0

15

15

10

Penalización

-

7

11

9

1

Destinos 2 3 0 20

1 Origen

10

x12 12

2 3

Demanda Penalización

7 X22

0 X31=5 0

x13

Recursos Penalización

4 11 x14

9 X23 =15

15

20 x24

10 0

15

0

10

Solución Básica: Método de Aproximación de Vogel (VAM) 

Nuevo conjunto de penalizaciones

1

Se elige la fila 2 Se asigna X22 = 10  Se ajusta la oferta a cero y la demanda a 15-10 = 5  Se tacha la fila 2

10

1 Origen



Destinos 2 3 0 20 x12



7 X22

0 X31=5 0 -

3 Demanda Penalización

1 Origen

2 3

Demanda Penalización

10 12

9 X23 =15

15 7

1

0 -

15

11

10

13

0

-

20 x24

10 9

Destinos 2 3 0 20 x12 7 9 X22 = 10 X23 =15

0 X31=5 0

11 x14

12 2

Recursos Penalización

4

Recursos Penalización

4 11 x14 20 x24

15 0 0

5

0

10

Solución Básica: Método de Aproximación de Vogel (VAM) 

Siguientes Aplicaciones: X12 = 5; se tacha la columna 2  X14 = 10; se tacha la fila 1 y  X24 = 0

1





Costo = 5*0 + 10*11 + 10*7 + 15*9 + 0*20 + 5*0 = $ 335

10

1 Origen

12

2

X22 = 10 X23 =15 0 X31=5 0

3 Demanda Penalización

1 Origen

Destinos 2 3 0 20 x12 7 9

2 3

Demanda Penalización

Recursos Penalización

4 11 x14 20 x24

15 0 0

5

0

10

Destinos Penalizació Recursos n 1 2 3 4 10 0 20 11 15 X12 = 5 X14 = 10 12 7 9 20 0 X22 = 10 X23 =15 X24 = 0 0 0 X31=5 0 5 0 10



Una compañía tiene tres plantas que fabrican cierto producto que debe mandarse a cuatro centros de distribución. Las plantas 1,2 y 3 producen 12, 17 y 11 cargas mensuales, respectivamente. Cada centro de distribución necesita recibir 10 cargas al mes. La distancia en millas desde cada planta a los respectivos centros de distribución es la siguiente. Centros de Distribución Plantas 1

2

3

4

1

800

1300

400

700

2

1100

1400

600

1000

3

600

1200

800

900



El costo del flete por cada embarque es de $100 mas $0,50/milla



Se desea determinar cuántas cargas deben mandarse desde cada planta a cada uno de los centros de distribución para minimizar el costo total del transporte  Formule el problema como un problema de transporte construyendo la tabla de costos y requerimientos apropiada  Obtenga la solución inicial por el método del costo mínimo y posteriormente utilice esta solución inicial. para resolver el problema.

Modelo de Transporte Centros de Distribución Plantas Recursos 1 2 3 4 500 750 300 450 1 12 X11 X12 X13 X14 650 800 400 600 2 17 X21 X22 X23 X24 400 700 500 550 3 11 X31 X32 X33 X34 10 10 10 10 Demada Z=?

Esquina Noroeste Plantas 1 2

3 Demada

Centros de Distribución Recursos 1 2 3 4 500 750 300 450 12 10 2 650 800 400 600 17 8 9 400 700 500 550 11 1 10 10 10 10 10 $ 22.500

Costo Minimo Plantas 1 2 3 Demada

Centros de Distribución Recursos 1 2 3 4 500 750 300 450 12 10 2 650 800 400 600 17 10 7 400 700 500 550 11 10 1 10 10 10 10 $ 20.650 Vogel Plantas 1 2 3 Demada

Centros de Distribución Recursos 1 2 3 4 500 750 300 450 12 2 10 650 800 400 600 17 7 10 400 700 500 550 11 10 1 10 10 10 10 $ 20.300



Tres plantas generadoras de energía eléctrica, con capacidades de 25, 40 y 30 millones de kilowatts-hora (kWh), suministran electricidad a tres ciudades cuyas demandas máximas son de 30, 35 y 25 millones de kWh. El costo en unidades monetarias (u.m.) de la venta de corriente eléctrica a las diferentes ciudades, por millón de kWh es la siguiente: Planta 1 2 3



1 600 320 500

Ciudad 2 700 300 480

3 400 350 450

Durante el mes de agosto se incrementa un 20% de la demanda en cada una de las tres ciudades. Para satisfacer el exceso de demanda, la compañía eléctrica debe comprar electricidad adicional de otra red a un precio de 1000 u.m. por millón de kWh. Sin embargo, esta red no está conectada a la ciudad 3. 



Formule el problema como uno de transporte con el fin de establecer el plan de distribución más económico desde el punto de vista de la compañía eléctrica. Obtenga una solución inicial básica mediante los métodos de esquina noroeste, costo mínimo y Vogel.

Planta 1 2 3 Dda.

600

Ciudad 2 700

320

300

350

500

480

450

1

30

35

Recursos

3 400

25 40 30

25 Modelo de Transporte Planta 1 2 3 4 Dda.

600

Ciudad 2 700

320

300

350

500

480

450

1000

1000

M

1

36

42

Recursos

3 400

30

25 40 30 13 Z=?

Esquina Noroeste Planta 1 2

3 4 Dda.

1 600 25 320 11 500 1000 36

Ciudad 2 700 300 29 480 13 1000 42

Recursos

3 400

25

350 450 17 M 13 30

40

30 13 $ 41.110

Costo Minimo Planta 1 2 3 4 Dda.

1 600

Ciudad 2 700

Recursos

3 400 25

320

300

350

480

450

40 500 23 1000 13 36

2

5 1000

42

M 30

25 40 30 13 $ 49.710

Vogel Planta 1 2 3 4 Dda.

1 600

Ciudad 2 700

Recursos

3 400 25

320

300

350

480

450

40 500 23 1000 13 36

2

5 1000

42

M 30

25 40 30 13 $ 49.710

Determinación de la Variable de Entrada 

Prueba de Optimidad por Método de Multiplicadores  La variable que entra será la variable no básica de la solución inicial, con la variable C*pq más positiva 

Cálculo de C*pq 



Se asocian los multiplicadores ui y vj con la fila i y la columna j de la tabla

de transporte Para cada variable básica Xij de la solución actual, los multiplicadores ui y vj deben satisfacer la ecuación dada por:

ui + vj = Cij  

para cada variable Xij

Se producen m + n – 1 ecuaciones con m+n incógnitas Los valores de los multiplicadores se obtienen suponiendo un valor arbitrario para cualquiera de los multiplicadores (en general ui se hace igual a cero) y

se resuelven las m + n – 1 ecuaciones de los m + n – 1 multiplicadores desconocidos restantes 

La evaluación de cada variable no básica Xpq esta dada por:

C*pq = up + vq – Cpq

Determinación de la Variable de Entrada 

Solución Inicial Regla de Esquina Noroeste: 

Variables Básicas:



Con Costos c11 = 10 c22 = 7 c24 = 20

X11 = 5, X22 = 5, X24 = 5,

X12= 10, X23= 15, X34= 5

Recurso

c12 = 0 c23 = 9 c25 = 18

10 5

0

20

11

7

9

20

14

15 16

10 12 5 0

Demanda

5

15

15

5 18 5 10

15 25

5

Determinación de la Variable de Entrada 

Ecuaciones asociadas a la Solución Básica 

      

Multiplicadores asociados a las Variable Básica Xjj : ui + vj = cij Dado u1 X11: u1 + v1 = c11 v1 = v1 = v2 = v3 = v4 = X12: u1 + v2 = c12 v2 = 10 0 20 11 X22: u2 + v2 = c22 u2 = u1 = 5 10 X23: u2 + v3 = c23 v3 = 12 7 9 20 u = X24: u2 + v4 = c24 v4 = 2 5 15 5 X34: u3 + v4 = c34 u3 = 0 14 16 18 u3 =

Demanda

5

15

15

5 10

Recurso 15 25 5

Determinación de la Variable de Entrada 

Ecuaciones asociadas a la Solución Básica 

Multiplicadores asociados a las Variable Básica Xjj : ui + vj = cij

Sea u1= 0  X11: u1 + v1 = 10  X12: u1 + v2 = 0  X22: u2 + v2 = 7  X23: u2 + v3 = 9  X24: u2 + v4 = 20  X34: u3 + v4 = 18

v1 = 10 v2 = 0 u2 = 7 v3 = 2 v4 = 13 u3 = 5

v1 = 10 v2 = 0 v3 = 2 v4 = 13 Recurso u1 = 0

10 5

20

11

7

9

20

14

15 16

10 12

u2 = 7

5 0

u3 = 5 Demanda

0

5

15

15

5 18 5 10

15 25 5

Determinación de la Variable de Entrada 

Cálculo de multiplicadores de variables básicas usando la tabla de costos 

Multiplicadores asociados a las Variable Básica Xjj : ui + vj = cij

Sea u1= 0  X11: u1 + v1 = 10  X12: u1 + v2 = 0  X22: u2 + v2 = 7  X23: u2 + v3 = 9  X24: u2 + v4 = 20  X34: u3 + v4 = 18

v1 = 10 v2 = 0 u2 = 7 v3 = 2 v4 = 13 u3 = 5

v1 =

u1 = 0

10 5

v3 = 20

11

7

9

20

14

15 16

10 5 0

u3 = 5

v4 =

0

12

u2 =

Demanda

v2 =

15

15

5 18 5 10

Recurso 15

25 5

Determinación de la Variable de Entrada 

Multiplicadores asociados a las Variable Básica

Soluciones

de Variables No Básicas, Xpq Cpq* = up + vq – Cpq

v1 = 10 v2 = 0 v3 = 2 v4 = 13 Recurso u1 = 0

10 5

7

9

14

15 16

5 0

u3 = 5 5

20

11

10 12

u2 = 7

Demanda

0

15

15

20 5 18 5 10

15 25 5

v1 = 10 v2 = 0 v3 = 2 v4 = 13 Recurso u1 = 0

10 5

12 C21* 0 u3 = 5 C31* Demanda 5

u2 = 7

0 10 7 5 14 C32* 15

20 C13* 9 15 16 C33* 15

11 C14* 20 5 18 5 10

15 25 5

Determinación de la Variable de Entrada 

Multiplicadores asociados a las Variable Básica

Soluciones

de Variables No Básicas, Xpq Cpq* = up + vq – Cpq

v1 = 10 v2 = 0 v3 = 2 v4 = 13 Recurso u1 = 0

10

5

0 5

11

7

9

14

15 16

15

15

 

5

u3 = 5

20

10 12

u2 = 7

Demanda

0

15

20 5 18

5 10

25

 

5

 

X13 X14 X21 X31 X32 X33

     

C13* = u1 + v3 – C13 C14* = u1 + v4 – C14 C21* = u2 + v1 – C21 C31* = u3 + v1 – C31 C32* = u3 + v2 – C32 C33* = u3 + v3 – C33

Determinación de la Variable de Entrada 

Multiplicadores asociados a las Variable Básica v1 = 10 v2 = 0 v3 = 2 v4 = 13 Recurso

u1 = 0

10 5

20

11

7

9

20

14

15 16

10 12

u2 = 7

5 0

u3 = 5 Demanda

0

5

15

15

5 18 5 10

15

Soluciones

de Variables No Básicas, Xpq : C* = up + vq – Cpq   

25 5

  

X13: X14: X21: X31: X32: X33:

C*13 = u1 + v3 – C13 = 0 + 2 – 20 = -18 C*14 = u1 + v4 – C14 = 0 + 13 – 11 = 2 C*21 = u2 + v1 – C21 = 7 + 10 – 12 = 5 C*31 = u3 + v1 – C31 = 5 + 10 – 0 = 15 C*32 = u3 + v2 – C32 = 5 + 0 – 14 = - 9 C*33 = u3 + v3 – C33 = 5 + 2 – 16 = - 9

Determinación de la Variable de Entrada 

Uso de la tabla de costos para determinar C*pq asociada a las variables no C*pq = up + vq – Cpq

básicas, Xpq :

v1 = 10 v2 = 0 v3 = 2 v4 = 13Recurso u1 = 0

10 5

7

9

14

15 16

5 0

u3 = 5 5

20

11

10 12

u2 = 7

Demanda

0

15

15

20 5 18 5 10

15 25 5

v1 = 10 v2 = 0 10

u1 = 0

5

0 10

12

u2 = 7 C*23=

v3 = 2

5

20 C*13=

7

v4 = 13 Recurso 11 C*13=

9

15 0 14 16 C*33= u3 = 5 C*31= C*32= Demanda 5 15 15

20 5 18 5 10

15

25 5

Determinación de la Variable de Entrada 

La solución no es óptima

La variable que entra será la variable no básica de la solución inicial, con la variable C*pq más positiva La variable entrante es X31

Determinación de la Variable que Sale  Prueba

de Factibilidad: Construcción de un ciclo para la variable que entra 

Formar un ciclo cerrado con las variables básicas de la solución básica inicial y la variable entrante (X31)



Realizar el análisis de lo que sucede con las variables básicas actuales si la variable que entra (X31) se incrementa en una unidad 1 1 Origen 2 3 Demanda

10 5 12 0 X31 5

Destinos 2 3 0 20 10 7 9 5 15 14 16 15

15

Recurso s

4 11 20 5 18 5 10

15 25 5

Determinación de la Variable que Sale Prueba de Factibilidad 



Análisis de lo que sucede con las variables básicas actuales si la variable que entra (X31) se incrementa en una unidad Si X31 = 1 entonces:  X11 disminuye una unidad  X12 aumenta una unidad  X22 disminuye una unidad  X34 disminuye una unidad  X24 aumenta una unidad  X23 se mantiene

1 Origen 2 3

Demanda

Destinos Recurso s 1 2 3 4 (-) 10 (+) 0 20 11 15 5 10 12 (-) 7 9 (+) 20 25 5 15 5 (+) 0 14 16 (-) 18 5 X31 5 5 15 15 10

Determinación de la Variable que Sale 

La variable que sale se selecciona de entre las variables de esquina del ciclo que disminuirán (etiquetadas (-) en la tabla) cuando la variable que entra (X31) aumente arriba del nivel cero.



Se selecciona la variable más pequeña como la variable que sale, ya que será la primera en llegar al valor cero y cualquier disminución posterior la volverá negativa.

1 Origen 2 3 Demanda

Destinos 1 2 3 10 0 20 5 (-) 10 (+) 12 7 9 5 (-) 15 0 14 16 X31 5 15 15

Recursos

4 11 20

5 (+) 18 5 (-) 10

15 25 5

Determinación de la Variable que Sale 

Selección de la variable que sale (la mas pequeña) 

 

X11, X22 y X34 son las tres variables básicas que pueden salir, se puede tomar cualquiera de ellas. Se elige X34  Sale X34 = 0, entra X31 = 5

Se recalculan las otra variables básicas sumando o restando 5 dependiendo del signo (+) o (-) en la tabla Las variables básicas actuales con valor cero se consideran como variables positivas. 1 1 Origen 2 3 Demanda

10 X11= 0 12 0 5 5

Destinos Recursos 2 3 4 0 20 11 15 X12= 15 7 9 20 25 X22= 0 15 X23= 10 14 16 18 5 15

15

10

Determinación de la Variable que Sale 

El nuevo costo es 0*10 + 15*0 + 0*7 + 15*9 + 10*20 + 5*0 + 0*18 = $335



El costo de la primera iteración fue de $ 410.



La diferencia es $410 - $335 = $ 75 $75 = X31 ∙ C31* = 5 * 15



Se revisa la optimidad de la nueva solución básica calculando los nuevos multiplicadores ui, vj, Cpq*

¿La solución es óptima??

Resumen Entra X31 Destinos Fuentes

1 2 3 Demanda vj

1

2

3

10 5

0 10

12 5

7 5

0 15 5 10

Destinos

14 -9 15 0

4

20 -18 9 15 16 -9 15 2

11 2 20 5

18 5 10 13

Recurso

ui

Fuentes

15

0

1

25

7

2

5

5 $ 410

1

2 10

(-) 5

12

(+) 0 X31 Demanda 5 vj 3

3

(+) 0 10 (-) 7 5 14 15

Recurso

4 20 9

11 (+)

15

20 5

16 15

(-)

18 5 10

ui

15 25 5

Entra X31 Sale X34 Destinos Fuentes

1

1 10 0

Demanda vj

3 0

20

7 0

0 5 5

Recurso

4 11

15 12

2 3

2

Destinos

9 15

14 15

20 10

16 15

18 10

ui

Fuentes

15

1

25

2

5

3 $ 335

Demanda vj

1

2 10

0

0 15

12 5

7 0

0 5 5 17

3

14 -24 15 7

20 -18 9 15 16 -24 15 9

4 11 2 20 10

18 -15 10 20

Recurso

ui

15

-7

25

0

5

-17

Resumen Entra X21 Destinos Fuentes

1 2 3

1

2

3

10 0

0 15

4 20

-18

12 5

Destinos

7 0

9 15

0

11 2

14

20 10

16

18

5

-24

-24

-15

Demanda

5

15

15

10

vj

17

7

9

20

Recurso

ui

Fuentes

15

-7

1

25

0

2

5

-17

3 Demanda

$0

1

2 10

(-)

(+)

0 (+)

3

Recurso

4

0

20

11

7

9

20

15 12

X21

(-) 0

15

0

14

10 16

18

5 5

15

15

ui

15 25 5

10

vj

Entra X21 Sale X11 Destinos Fuentes

1 10

1 2

3 Demanda vj

2

Destinos 3

0

Recurso

4 20

11

15 12 0

7 0

0

9 15

14

20 10

16

18

5 5

15

15

10

ui

Fuentes

15

1

25

2

5

3 $ 335

1

2

3

10 -5

0 15

20 -18

12 0

4

7 0

0

11 2

9 15

14

20 10

16

18

5

-19

-19

-10

Demanda

5

15

15

10

vj

12

7

9

20

Recurso

ui

15

-7

25

0

5

-12

Resumen Entra X14 Destinos Fuentes

1 2 3

1

2

3

10 -5

0 15

12

0

Destinos 4 20

-18 7

0 0

14

5

-19

Demanda

5

15

vj

12

7

11 2

9

20

15 16 -19 15 9

10 18 -10 10 20

Recurso

ui

Fuentes

15

-7

1

25

0

2

5

-12

3 Demanda

$ 335

1

2

3

10 (-)

0

20

15 12

0

(+)

(+)

11

X14 7

9

14

15 16

10 18

15

10

0 0

Recurso

4

(-)

20

5 5

15

vj

ui

15 25 5 $ 335

Sale X24 Destinos Fuentes

1

3 Demanda vj

3

10

1 2

2

Destinos

0

20

5 7 10 0

11 10

12 0

Recurso

4

14

9

20

15 16

18

5 5

15

15

10

ui

Fuentes

15

1

25

2

5

3

$ 315

1

2

3

10 2

0 5

20 -11

12 0

4

7 10

0

11 10

9 15

14

20 -2

16

18

5

-7

-7

0

Demanda

5

15

15

10

vj

12

7

9

18

Recurso

ui

15

-7

25

0

5

-12

OPTIMO

Soluciones Múltiples 

Prueba de factibilidad en una minimización  



Si todos los C*pq < 0 la solución es óptima única; Si algunos C*pq = 0 la solución es óptima múltiple, cada celda igual a cero indica una ruta alterna, sin que varíe Z; Si se tienen varios C*pq > 0 se toma el más negativo y se asigna en dicha celda, es decir, se realizan nuevas asignaciones (reasignaciones).

Soluciones Múltiples 

Solución inicial D

E

F

A

0

B C

G

5 10

10

15

5

Optimo 1: De A Unidades A F 10 A G 10 B F 30 C D 10 C E 15 C G 20 Solución Optima No Degenerada Z *1 = $550

Costo 5 0 5 10 10 5

Soluciones Múltiples A B C

D 10

E

F 10 30

15

Optimo 2:

De A A B C C

G

30 A D F F E G

Unidades 10 10 30 15 30

Costo 5 5 5 10 5

Solución Optima Degenerada Z*2 = $550

Soluciones Múltiples Optimo 3: D A B C

E

10

F 20 20

15

DE A B B C C Solución Optima

G

30

A Unidades Costo F 20 5 D 10 5 F 20 5 E 15 10 G 30 5 Degenerada Z*3 = $550

Problemas deTransbordo

MODELO DE TRANSBORDO • Se reconoce mediante el uso de nodos intermedios o transitorios para el envío de recursos entre las distintas fuentes (oferta) y destinos (demanda) • Se construye una malla con orientación desde las fuentes (nodos de inicio) hacia los destinos (nodos de llegada), utilizando amortiguadores (nodos transitorios) que permiten recibir y transferir recursos. Las flechas que unen los nodos de la malla representan los eventuales flujos de recursos en la secuencia de distribución

MODELO DE TRANSBORDO  Luego, la malla permite convertir un modelo de transbordo en un modelo de transporte regular y resolverse como tal, utilizando los amortiguadores  Así, la malla reconoce tres tipos de nodos:  Nodos puros de Oferta: solo transfieren recursos  Nodos de Transbordo: entregan y reciben recursos  Nodos puros de Demanda: solo reciben recursos  El amortiguador debe ser suficientemente grande para permitir que los recursos se transfieran desde las fuentes hacia los destinos

ESQUEMA DE TRANSBORDO Un esquema simple del modelo de transbordo se expresa como una red de modelo de asignación

F1 A1

D1

A2

D2

Nodos de Transbordo

Nodos puros de Demanda

F2

F3

Nodos puros de Oferta

EJEMPLO DE TRANSBORDO • Dos fábricas de automóviles, P1 y P2, están conectadas a tres distribuidores, D1, D2 y D3, por medio de dos centros de tránsito, T1 y T2, de acuerdo con la red que se muestra en la siguiente diapositiva • Las cantidades de la oferta en las fábricas P1 y P2, son de 1000 y 1200 automóviles, y las cantidades de la demanda en las distribuidoras D1, D2 y D3, son de 800, 900 y 500 automóviles. El costo de envío por automóvil (en cientos de pesos) entre los pares de nodos, se muestra en los eslabones (arcos) de conexión de la red

RED - MODELO DE ASIGNACION 8 1000

D1

3 P1 4

T1

2

800

5

6

4

900

D2

5 1200

P2

T2

3 9

D3

500

PROBLEMA PROGRAMACION LINEAL D1

P1

XP1T1

T1

XD1D2

1000

D2 P2

XP2T2 T2

900

XD2D3

1200

800

D3

500

PROBLEMA PROGRAMACION LINEAL F.O. Mín Z = 3XP1T1 + 4XP1T2 + 2XP2T1 + 5XP2T2 + 8XT1D1 + 6XT1D2 + 4XT2D2 + 9XT2D3 + 5XD1D2 + 3XD2D3 s.a.

P1: P2: T1: T2: D1: D2: D3:

XP1T1 + XP1T2 = 1000 XP2T1 + XP2T2 = 1200 XP1T1 + XP2T1 = XT1D1 + XT1D2 XP2T2 = XT2D2 + XT2D3 XT1D1 = XD1D2 + 800 XT1D2 + XT2D2 + XD1D2 = XD2D3 + 900 XT2D3 + XD2D3 = 500 Xij > 0

EJEMPLO DE TRANSBORDO • Nodos puros de Oferta

P1, P2

• Nodos de Transbordo

T1, T2, D1, D2

• Nodos puros de Demanda

D3

El modelo de transbordo se convierte a un modelo de transporte con seis puntos de origen (P1, P2, T1, T2, D1 y D2) y cinco de destino (T1, T2, D1, D2 y D3)

MODELO DE ASIGNACION PROBLEMA DE TRANSPORTE 1000

P1 T1

1200

P2 T2 T1

D1 T2 D2 D1

D3 D2

800 900

500

MODELO DESTINO T1 FUENTE P1 P2 T1 T2 D1 D2

DEMANDA

T2

D1

D2

D3

OFERTA

NODOS PUROS DE OFERTA Y NODOS PUROS DE DEMANDA Las cantidades de la oferta y la demanda en los nodos puros de oferta y puros de demanda, queda:

Oferta en un Nodo puro de Oferta

Oferta Original

Un nodo puro de oferta no posee amortiguador Demanda en un Nodo puro de Demanda

Demanda Original

Un nodo puro de demanda no posee amortiguador

MODELO DESTINO T1

T2

D1

D2

D3

OFERTA

FUENTE P1

1000

P2

1200

T1 T2 D1 D2

DEMANDA

500

NODOS DE TRANSBORDO Las cantidades de la oferta y la demanda en los nodos de transbordo, se establece de acuerdo a: Oferta en un Nodo de Transbordo

Oferta + AmortiOriginal guador

La oferta necesariamente posee un amortiguador, mientras que a veces se encuentra oferta original Demanda en un Nodo de Transbordo

Demanda + AmortiOriginal guador

La demanda necesariamente posee amortiguador, mientras que en ocasiones hay demanda original

NODOS DE TRANSBORDO La oferta del nodo de transbordo T1 sí posee oferta original, mientras que la oferta del nodo de transbordo T2 no posee oferta original 200 D1 500

P1

400

T1 D2

400

D2

200

300 P2

T2

NODOS DE TRANSBORDO La demanda del nodo de transbordo T1 no posee demanda original, mientras que la demanda del nodo de transbordo T2 sí posee demanda original D1 400

P1

300

T1 D2

200

D2

300

600

P2

T2

200

MODELO DESTINO T1

T2

D1

D2

D3

OFERTA

FUENTE P1

1000

P2

1200

T1

B1

T2

B2

D1

B3

D2

B4

DEMANDA

B1

B2

B3+800 B4+900

500

Se obtiene la 1ª solución mediante método de Vogel

T1 3

4

P1 P2

T1 T2

D1 D2 Dda

T2

D1 M

D2 M

D3

Ofta

M

1000 2

5

M

M

M

1200 M

M

8

6

M

B1

M

M

M

4

9

B2

M

M

M

5

M

B3

M

M

M

M

3

B4

800+B3

900+B4

B1

B2

500

EJEMPLO DE TRANSBORDO Obtener la primera solución factible mediante Vogel, implica asignar el máximo número de unidades posible en las celdas de menor costo marginal, según los sucesivos gradientes No obstante, en ocasiones, la celda de menor costo marginal puede asociarse con un máximo número de unidades determinado por los amortiguadores. Luego, se requiere definir los rangos posibles para cada amortiguador 800 < B1 < 2200 0 < B2 < 1400

0 < B3 < 1400 0 < B4 < 500

EJEMPLO DE TRANSBORDO T1 P1 P2 T1 T2 D1 D2 Dda

3

T2 4

D1 M

D2 M

D3 M

1000 2

5

M

M

8

6

M

4

9

800 M

M

M

1400 M

M

M

M

M

5

M

M

M

3 500

B1

B2

1

1

800+B3 900+B4 M

1000

1

1200

3

B1

2

B2

5 M M

B3

M

B4

M M

M

400

800 M

M

Ofta

1

500 6

M M

EJEMPLO DE TRANSBORDO Al calcular los gradientes del método de Vogel, se van obteniendo los valores de los amortiguadores Valores de los amortiguadores:

B1 = 800 B2 = 1400 B3 = 0 B4 = 500

Si es que hay 2 o más gradientes de igual valor (como sucede con los gradientes + M ), entonces se asigna el máximo número de unidades posibles en aquella celda de menor costo unitario de transporte

EJEMPLO DE TRANSBORDO 1ª asignación: XD2D3 = 500, gradiente fila D2 = M 2ª asignación: XT1D2 = 1400, gradiente fila T2 = M 3ª asignación: XT1D1 = 800, gradiente fila T1 = M 4ª asignación: XP2T1 = 800, gradiente fila P2 = 3 5ª asignación: XP1T2 = 1000 6ª asignación: XP2T2 = 400

Asignación manual

Así, Vogel determina la 1ª solución básica factible, sin embargo falta verificar la condición de optimalidad e iterar vía simplex si es que se requiere

EJEMPLO DE TRANSBORDO m + n - 1 = 10

Sin embargo, la asignación inicial mediante método de Vogel tiene solamente 6 variables básicas

Deben ingresarse cuatro valores 0 a la base XT1T2 = 0, XT2T2 = 0, XD1T2 = 0, XD2T2 = 0 Luego, se deben calcular los precios sombra para verificar si la solución básica factible es o no es óptima

EJEMPLO DE TRANSBORDO T1 P1 P2 T1 T2 D1 D2 Dda

3

T2

D1

4

M

D2 M

D3 M

1000

1000 2

5 800

M

M 8

M

M

M 1200

0

M

6

M

4

9

B1

800

0 M

M

400 M

M

B2

1400 M

5

M

M

M

3

B3

0 M

M B1

0 B2

Ofta

500

800+B3 900+B4

Se deben calcular todos los precios sombra

500

B4

EJEMPLO DE TRANSBORDO

8

0

M

M M

0 M

0

E

ij > 0

9 1400

5

M

i,j



M

XJ

+M

1000

+M

1200 B1 B2 B3

500

B4

M 3

800+B3 900+B4

B2 A

B1

4

E

M

M

M

Ofta

M

E

M

E

M

800

0

+M

6

E

Ya que

M

+M

M

+M

E

Dda

400

800 M

M

+M

M

D3

E

D2

5

E

D1

1000

M

E

T2

M

D2

E

T1

2

4

E

P2

+2

D1

E

P1

3

T2

E

T1

500 Solución óptima

EJEMPLO DE TRANSBORDO Solución óptima del ejemplo de transbordo:

XJ = ( XP1T2, XP2T1, XP2T2, XT1T2, XT1D1, XT2T2, XT2D2, XD1T2, XD2T2, XD2D3 ) XP1T2 = 1000

XT2T2 =

XP2T1 = 800

XT2D2 = 1400

XP2T2 = 400

XD1T2 =

XT1T2 =

XD2T2 = 0 XD2D3 = 500

0

XT1D1 = 800

0 0

La solución no es única, pues es una solución degenerada

Z = (1000*4) + (800*2) + (400*5) + (800*8) + (1400*4) + (500*3) = 21.100 ($100)