investigación de operaciones - · pdf file2 investigación de operaciones modelos...

1

Investigación de Operaciones

Modelos matemáticos aplicados a las organizaciones:

2. El Problema de Transporte:

Forma Estándar: El problema de transporte incluye m fuentes u orígenes, a cada una de las

cuales corresponde una disponibilidad ai (i = 1, 2, ..., m) unidades de un producto homogéneo;

y n destinos , cada uno los cuales requiere bj(j = 1,2, ..., n)unidades de este producto. Los

números ai y bj son enteros positivos (programación entera).

El costo Cij de transportar una unidad de producto del orígen i al destino j se da para cada i y

para cada j. El objetivo es desarrollar un programa de transporte que cumpla las demandas, a

partir del inventario actual y con un costo de embarque (transporte) mínimo, esto es:

∑∑==

=n

j

j

m

i

i ba11




Forma Estándar: Para garantizar la ecuación anterior, se debe crear un destino ficticio con una demanda igual al excedente, si la demanda total es menor que el suministro total, o un origen ficticio con un suministro igual al faltante, si la demanda total excede al suministro total.

Sea Xij el número (desconocido) de unidades que se despachan del orgien i al destino j. Entonces, el modelo matemático para este problema es:

.:

),...,2,1(

),...,2,1(:

:min

1

1

11

enterasynegativasnoXlastodascon

njbX

miaXscondicionelascon

XCZimice

ij

m

i

jij

n

j

iij

n

j

ijij

m

i

∑

∑

∑∑

=

=

==

==

==

=

2




El algoritmo de transporte: La primera aproximación al modelo matemático para este problema, es siempre entera y por lo tanto es siempre la solución óptima. En vez de determinar la primera aproximación mediante una aplicación directa del método simplex, puede resultar más eficiente utilizar el cuadro de transporte.

El algoritmo de transporte es el método simplex especializado para el cuadro de transporte, e implica:

1. Encontrar una solución básica inicial2. Prueba de optimalidad3. Mejora de la solución cuando no es la óptima4. Repetir los pasos 2 y 3 hasta que se obtenga la s olución óptima.




Cuadro de transporte:

bn...b3b2b1Demanda

amXmn...Xm3Xm2Xm1m

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

a2X2n...X23X22X212

a1X1n...X13X12X111

Suministron...321

C11 C12 C13 C1n

C21

Cm1

C22 C23 C2n

Cm2 Cm3 CmnOrigen

es

Destinos

En general, un problema que tiene m nodos de oferta y n nodos de demanda tendrá m + n –1restricciones, es decir, m+ n – 1 celdas no vacías.

3




EJEMPLO :

CCC posee tres plantas de ensamblado de microcomputadoras. La que se encuentra localizada en San Francisco tiene una capacidad de producción mensual de 1700 unidades, la que está localizada en Los Ángeles tiene una capacidad de producción mensual de 2000 unidades y la de Phoenix tiene una capacidad de producción mensual de 1700 unidades. Las microcomputadoras son vendidas a través de tiendas al menudeo. Para el mes siguiente, la tienda que se encuentra en San Diego ha hecho un pedido de 1700 unidades, la que se encuentra en Barstow tiene un pedido de 1000 unidades, la de Tucson ha pedido 1500 unidades y la situada en Dallas tiene un pedido de 1200 unidades. El costo de envío de una microcomputadora desde cada planta de ensamblado a cada una de las diferentes tiendas detallistas se presenta en la siguiente tabla. Como gerente de distribución usted desea encontrar un programa de envíos al menor costo.




EJEMPLO :

Costo de embarque ($/máquina) de plantas a tiendas:

8356Phoenix

10874Los Ángeles

6235San Francisco

DALLASTUCSONBARSTOWSAN DIEGO

TIENDASPLANTAS

4




EJEMPLO :

Red de distribución de CCC:




Cuadro de transporte para CCC:

Mercados minoristas

1200150010001700Demanda

1700Phoenix

2000Los Ángeles

1700San Francisco

SuministroDallasTucsonBarstowSan DiegoPlantas

5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

5




1. SOLUCIÓN BÁSICA INICIAL: Métodos

• Método del costo mínimo o matriz mínima

• Método del costo mínimo por fila

• Método del costo mínimo por columna

• Regla del Extremo Noroccidental o Esquina Noroeste

• Método de Vogel




1. SOLUCIÓN BÁSICA INICIAL: Método del Costo Mín imo ó Matriz Mínima• Se escoge la celda con el menor costo de embarque y se le asigna la máxima cantidad

posible sin infringir las restricciones y reduciendo la demanda y el suministro en la cantidad respectiva.

Mercados minoristas

120015000

10001700Demanda

1700Phoenix

2000Los Ángeles

1700200

1500San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

6




1. SOLUCIÓN BÁSICA INICIAL: Método del Costo Mín imo ó Matriz Mínima• Se elige la celda con el siguiente menor costo de embarque y se repite el proceso.

Mercados minoristas

120015000

1000800

1700Demanda

1700Phoenix

2000Los Ángeles

1700200

1500200San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8





Mercados minoristas

120015000

1000800

17000

Demanda

1700Phoenix

2000300

1700Los Ángeles

1700200



5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

7





Mercados minoristas

120015000

1000800

17000

Demanda

1700900

800Phoenix

2000300

1700Los Ángeles

1700200



5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8





Mercados minoristas

1200300

15000

1000800

17000

Demanda

1700900

900800Phoenix

2000300

1700Los Ángeles

1700200



5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

8





Mercados minoristas

1200300

15000

1000800

17000

Demanda

1700900

900800Phoenix

2000300

3001700Los Ángeles

1700200



5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8




1. SOLUCIÓN BÁSICA INICIAL: Método del Costo Mín imo ó Matriz Mínima

• Costo total del embarque para la solución básica inicial:(3x200)+(2x1500)+(4x1700)+(10x300)+(5x800)+(8x900) = $24.600

Mercados minoristas

1200150010001700Demanda

1700900800Phoenix

20003001700Los Ángeles



5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

9




1. SOLUCIÓN BÁSICA INICIAL: Método del Costo Mín imo por fila• Se selecciona una fila y se escoge la celda con el menor costo de embarque asignándole

la máxima cantidad posible sin infringir las restricciones y reduciendo la demanda y el suministro en la cantidad respectiva.

Mercados minoristas

120015000

10001700Demanda

1700Phoenix

2000Los Ángeles

1700200

1500San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8




1. SOLUCIÓN BÁSICA INICIAL: Método del Costo Mín imo por fila• En la misma fila, se selecciona la celda con el siguiente menor costo de embarque

asignándole la cantidad necesaria para agotar el suministro de la misma.

Mercados minoristas

120015000

1000800

1700Demanda

1700Phoenix

2000Los Ángeles

1700200



5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

10




1. SOLUCIÓN BÁSICA INICIAL: Método del Costo Mín imo por fila• Se avanza a la fila siguiente, seleccionando la celda con el menor costo y asignándole la

máxima cantidad posible, cumpliendo con las restricciones.

Mercados minoristas

120015000

1000800

17000

Demanda

1700Phoenix

2000300

1700Los Ángeles

1700200



5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8




1. SOLUCIÓN BÁSICA INICIAL: Método del Costo Mín imo por fila• En la misma fila siguiente, se selecciona la celda que permita asignar la cantidad necesaria

para agotar el suministro de la misma.

Mercados minoristas

120015000

1000500

17000

Demanda

1700Phoenix

2000300

3001700Los Ángeles

1700200



5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

11




1. SOLUCIÓN BÁSICA INICIAL: Método del Costo Mín imo por fila• En la última fila, se seleccionan las celdas (3,2) y (3,4) que permitan agotar el suministro

de Phoenix y cumplir las demandas de Barstow y Dallas.

Mercados minoristas

12000

15000

1000500

17000

Demanda

17001200500Phoenix

2000300

3001700Los Ángeles

1700200



5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8




1. SOLUCIÓN BÁSICA INICIAL: Método del Costo Mín imo por fila


Mercados minoristas

1200150010001700Demanda

17001200500Phoenix




5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

12




1. SOLUCIÓN BÁSICA INICIAL: Método del Costo Mín imo por columna• Se selecciona una columna y se escoge la celda con el menor costo de embarque

asignándole la máxima cantidad posible sin infringir las restricciones y reduciendo la demanda y el suministro en la cantidad respectiva.

Mercados minoristas

12001500100017000

Demanda

1700Phoenix

20003001700

Los Ángeles

1700San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8




1. SOLUCIÓN BÁSICA INICIAL: Método del Costo Mín imo por columna• Se avanza a la columna siguiente y se escoge la celda con el menor costo de embarque y

se repite el proceso.

Mercados minoristas

1200150010000

17000

Demanda

1700Phoenix

2000300

1700Los Ángeles

1700700

1000San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

13




1. SOLUCIÓN BÁSICA INICIAL: Método del Costo Mín imo por columna• Se avanza a la columna siguiente y se escoge la celda con el menor costo de embarque y

se repite el proceso.

Mercados minoristas

12001500800

10000

17000

Demanda

1700Phoenix

2000300

1700Los Ángeles

1700700



5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8




1. SOLUCIÓN BÁSICA INICIAL: Método del Costo Mín imo por columna• Para cumplir con la demanda de la columna seleccionada, se escoge la celda con el

siguiente menor costo y se repite el proceso.

Mercados minoristas

12001500800

10000

17000

Demanda

1700900

800Phoenix

2000300

1700Los Ángeles

1700700



5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

14




1. SOLUCIÓN BÁSICA INICIAL: Método del Costo Mín imo por columna• En la última columna, se eligen las celda (3,4) y (2,4), se les asigna la cantidad necesaria

para cumplir con la demanda de Dallas y agotar los suministros de Phoenix y Los Ángeles.

Mercados minoristas

12001500800

10000

17000

Demanda

1700900

900800Phoenix

2000300

3001700Los Ángeles

1700700



5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8




1. SOLUCIÓN BÁSICA INICIAL: Método del Costo Mín imo por columna


Mercados minoristas

1200150010001700Demanda

1700900800Phoenix




5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

15




1. UNA SOLUCIÓN BÁSICA INICIAL:

Regla del extremo noroccidental: Empezando con la celda (1,1) del Cuadro de Transporte

(extremo noroccidental), asigne a X11 tantas unidades como sea posible, sin ir en contra de las

restricciones. Éste será el menor valor entre a1 y b1. En seguida, se continua moviendo una

celda a la derecha, si queda algún suministro o, si no, una celda abajo. En cada paso, asigne

tanto como sea posible a la variable, considerando las restricciones: la suma de las

asignaciones de cada fila no puede exceder ai, , la suma de las asignaciones de cada columna

no puede exceder bj; además ninguna asignación puede ser negativa, pero puede ser cero.

NOTA: El cero que indica que no es posible asignación, porque se ha completado la oferta o

la demanda, puede colocarse desplazándose a la derecha o hacia abajo.




1. UNA SOLUCIÓN BÁSICA INICIAL: Regla del extremo noroccidental

• Se empieza con la celda (1,1) asignándole a X11 el menor valor entre a1 = 1700 y

b1 = 1700, en este caso de igualdad se asigna 1700 cumpliendo con la demanda y

agotando el suministro existente.

Mercados minoristas

1200150010001700Demanda

1700Phoenix

2000Los Ángeles



5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

16





• Se continua con la celda de la derecha, es decir, (1,2). La asignación anterior agotó el

suministro en la planta de San Francisco, por tal razón se asigna a X12 = 0.

Mercados minoristas

1200150010001700Demanda

1700Phoenix

2000Los Ángeles



5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8





• Se avanza una celda hacia abajo (2,2) y se asigna a X22 la máxima cantidad posible,

cumpliendo con las restricciónes, es decir, X22 = 1000, dejando un suministro de 1000

unidades en esta planta y cumpliendo la demanda de Barstow.

Mercados minoristas

1200150010001700Demanda

1700Phoenix




5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

17





• Se avanza una celda a la derecha (2,3) y se asigna a X23 las 1000 unidades restantes del

suministro en la planta de Los Ángeles, agotando así, el suministro y disminuyendo en 1000

la demanda de Tucson.

Mercados minoristas

1200150010001700Demanda

1700Phoenix




5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8





• Se avanza a la celda (3,3) asignándole a X33 = 500 unidades con las cuales se completa la

demanda de Tucson y el suministro en la planta de Phoenix disminuye en esa cantidad.

Mercados minoristas

1200150010001700Demanda

1700500Phoenix




5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

18





• Se continua con la última celda (3,4) y se asigna a X34 = 1200 unidades, agotando el

suministro de Phoenix y satisfaciendo la demanda para Dallas.

Mercados minoristas

1200150010001700Demanda

17001200500Phoenix




5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8





• Costo total del embarque para la solución básica inicial:(5x1700)+(7x1000)+(8x1000)+(3x500)+(8x1200) = $34.600

Mercados minoristas

1200150010001700Demanda

17001200500Phoenix




5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

19




1. UNA SOLUCIÓN BÁSICA INICIAL: Método de Vogel

2121Diferencias

1700

2000

1700

Suministro

Mercados minoristas

1200150010001700Demanda

2Phoenix

3*1700Los Ángeles

1San Francisco

DiferenciasDallasTucsonBarstowSan DiegoPlantas

5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8





22

11

22*

1X

Diferencias

1700

2000

1700

Suministro

Mercados minoristas

1200150010001700Demanda

2 2Phoenix

3* 11700Los Ángeles

1 11000San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

20





222

111

22*X

1XX

Diferencias

1700

2000

1700

Suministro

Mercados minoristas

1200150010001700Demanda

2 2 5*2001500Phoenix

3* 1 23001700Los Ángeles

1 1 47001000San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8





• Costo total del embarque para la solución básica inicial:(3x1000)+(6x700)+(4x1700)+(10x300)+(3x1500) + (8x200)= $23.100

1700

2000

1700

Suministro

Mercados minoristas

1200150010001700Demanda

2001500Phoenix

3001700Los Ángeles


DallasTucsonBarstowSan DiegoPlantas

5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

21




2. PRUEBA DE OPTIMALIDAD: Determinar si el plan de embarque actual tiene el menor costo total, mediante el cálculo del costo reducido para cada celda vacía ó utilizando el Método de Distribución Modificada (MODI) . El costo reducido representa el cambio en el costo total que se obtendría al enviar una unidad a esa celda vacía. Si un costo reducido es negativo , el plan de embarque actual no es óptimo.

Pasos Costo Reducido:

• Cálculo de costos reducidos : por cada celda vacía, se encuentra el ciclo único que inicia y termina en esa celda. Utilizando el ciclo, se calcula el costo reducido de esta celda.

• Verificación de los costos reducidos : Si todos los costos reducidos calculados en el paso anterior son no negativos, el plan de embarque actual es óptimo. En otro caso, se procede con la MEJORA DE LA SOLUCIÓN.




2. PRUEBA DE OPTIMALIDAD: Para el caso de CCC, utilizaremos la solución inicial obtenida con el método de costo mínimo.Se selecciona una celda vacía del cuadro actual (por ejemplo, (1,1)) y se supone que se asigna una unidad a esa celda a un costo de $5:

Mercados minoristas

1200150010001700Demanda

1700900800Phoenix


17001500200+1

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

Inicio

22




2. PRUEBA DE OPTIMALIDAD: Como se ha excedido en una unidad el suministro y la demanda para la fila y la columna respectivamente, se debe enviar una unidad menos en alguna otra celda, sin utilizar ninguna de las celdas vacías restantes. Se disminuye entonces, la celda (1,2):

Mercados minoristas

1200150010001700Demanda

1700900800Phoenix


17001500200-1+1

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

Inicio




2. PRUEBA DE OPTIMALIDAD: El cambio anterior implica que la demanda de la columna 2 no es satisfecha en una unidad. Esta unidad puede ser repuesta enviando una unidad adicional en la celda (3,2):

Mercados minoristas

1200150010001700Demanda

1700900800+1

Phoenix


17001500200-1+1

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

Inicio

23




2. PRUEBA DE OPTIMALIDAD: El suministro de la fila 3 se excedio en una unidad, para reducir este suministro, se disminuye la celda (3,4):

Mercados minoristas

1200150010001700Demanda

1700900-1

800+1

Phoenix


17001500200-1+1

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

Inicio




2. PRUEBA DE OPTIMALIDAD: El proceso de mantener el equilibrio entre el suministro y la demanda, continúa hasta que se equilibra la columna de la celda inicial:

Mercados minoristas

1200150010001700Demanda

1700900-1

800+1

Phoenix

2000300+1

1700Los Ángeles

17001500200-1+1

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

Inicio

24




2. PRUEBA DE OPTIMALIDAD: Con el equilibrio entre suministro y demanda, es posible calcular el cambio en los costos totales de embarque, es decir, el costo reducido de la celda (1,1):

Mercados minoristas

1200150010001700Demanda

1700900-1

800+1

Phoenix

2000300+1

1700-1

Los Ángeles

17001500200-1+1

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

Inicio




2. PRUEBA DE OPTIMALIDAD: Por cada celda del ciclo que requiere un envío adicional de una unidad (indicada por un +1), se incurre en un costo adicional igual al costo unitario de embarque en esa celda. Así mismo, por cada celda que requiere una disminución en el envío de una unidad (indicado por un –1), se presenta un ahorro igual al costo de envío unitario en dicha celda. Sumando y restando los costos y los ahorros adicionales de las celdas del ciclo se obtiene el cambio neto en los costos totales de embarque si una unidad es enviada en la celda vacía elegida.

Para la celda (1,1) el cambio neto es:

Costo Reducido = (5) – (3) + (5) – (8) + (10) – (4)= +5

Este costo reducido indica que por cada unidad enviada de San Franciso a San Diego (Celda (1,1)), el costo total de embarque aumenta en $5. En consecuencia, no es conveniente para CCC utilizar esta celda con el fin de crear un mejor plan de embarque.

25




2. PRUEBA DE OPTIMALIDAD: En seguida, es necesario calcular un costo reducido para cada celda vacía.Celda vacía (1,4):

Mercados minoristas

1200150010001700Demanda

1700900-1

800+1

Phoenix


1700+1

1500200-1

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

Inicio

Costo Reducido = (6) – (8) + (5) – (3)= +0




2. PRUEBA DE OPTIMALIDAD: Celda vacía (2,2):

Mercados minoristas

1200150010001700Demanda

1700900+1

800-1

Phoenix

2000300-1+1

1700Los Ángeles



5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

Inicio

Costo Reducido = (7) – (10) + (8) – (5)= +0

26





Mercados minoristas

1200150010001700Demanda

1700900+1

800-1

Phoenix

2000300-1+1

1700Los Ángeles

17001500-1

200+1

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

Inicio

Costo Reducido = (8) – (10) + (8) – (5) + (3) – (2)= +2





Mercados minoristas

1200150010001700Demanda

1700900-1

800+1

Phoenix

2000300+1

1700-1

Los Ángeles



5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

Inicio

Costo Reducido = (6) – (8) + (10) – (4)= +4

27





Mercados minoristas

1200150010001700Demanda

1700900+1

800-1

Phoenix


17001500-1

200+1

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8Inicio

Costo Reducido = (3) – (5) + (3) – (2)= -1




2. PRUEBA DE OPTIMALIDAD: Verificación de Costos ReducidosEn cada celda vacía se coloca el costo reducido calculado para la misma. Como se observa, el costo reducido de –1 para la celda (3,3), indica que el plan de embarque no es óptimo.

Mercados minoristas

1200150010001700Demanda

1700900-1

800+4

Phoenix

2000300+2+0

1700Los Ángeles

1700+0

1500200+5

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

28




3. MEJORA DE LA SOLUCIÓN:Como el plan actual no es óptimo, se construye un nuevo plan entero factible, cuyo costo total de embarque sea menor que el del actual, así:

• Escoger la celda cuyo costo reducido es más negativo (Para el ejemplo CCC es la celda (3,3))

• Determine el número máximo de unidades que pueden ser enviadas a la celda identificadaen ítem anterior, recordando que cada unidad enviada a esa celda reduce los costos totales de embarque en el valor del costo reducido.




3. MEJORA DE LA SOLUCIÓN: Determinar el número máximo de unidades :• Se localizan todas las celdas del ciclo de costo reducido negativo, en las que es necesaria

una disminución en el número de unidades enviadas para mantener el equilibrio entre suministro y demanda, estas son (1,3) y (3,2)

Mercados minoristas

1200150010001700Demanda

1700900+1

800-1

Phoenix


17001500-1

200+1

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8Inicio

29




3. MEJORA DE LA SOLUCIÓN: Determinar el número máximo de unidades :• Entre las celdas (1,3) y (3,2), se identifica aquella en la que actualmente se envía el menor

número de unidades, en este caso, 800 unidades de la celda (3,2).

Mercados minoristas

1200150010001700Demanda

1700900+1

800-1

Phoenix


17001500-1

200+1

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8Inicio




3. MEJORA DE LA SOLUCIÓN: Determinar el número máximo de unidades :• Se envía la cantidad identificada (800) a la celda elegida (3,3), por ser la que más

disminuye el costo total de embarque (en $1 por unidad enviada) y se modifican en consecuencia, las cantidades enviadas en cada celda del ciclo:

Mercados minoristas

1200150010001700Demanda

1700900800+1-1

Phoenix


1700700-1

1000+1

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

30




3. MEJORA DE LA SOLUCIÓN: Determinar el número máximo de unidades :• Como resultado de las modificaciones, la cantidad enviada a la celda (3,2) ha disminuido a

cero. Ahora esta celda ha quedado vacía:

Mercados minoristas

1200150010001700Demanda

1700900800+1

0-1

Phoenix


1700700-1

1000+1

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8




3. MEJORA DE LA SOLUCIÓN: • Nuevo Costo total del embarque para la solución mejorada:

(3x1000)+(2x700)+(4x1700)+(10x300)+(3x800) + (8x900) = $23.800

Mercados minoristas

1200150010001700Demanda

1700900800Phoenix




5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

31




Se realiza nuevamente el paso No. 2 PRUEBA DE OPTIM ALIDAD, calculando los costos reducidos para las celdas vacías del nuevo plan de embarque:

Mercados minoristas

1200150010001700Demanda

1700900800+1+4

Phoenix

2000300+3+1

1700Los Ángeles

1700-1

7001000+4

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8




Con la verificación de los costos reducidos, se obs erva el valor de –1 para celda (1,4), indicando que el plan de embarque no es óptimo:

Mercados minoristas

1200150010001700Demanda

1700900800+1+4

Phoenix

2000300+3+1

1700Los Ángeles

1700-1

7001000+4

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

32




Se continúa con el paso No. 3 MEJORA DE LA SOLUCIÓN , identificando la celda con el costo reducido más negativo (1,4) y determinando la cantidad máxima que puede ser enviada a ésta celda (700 unidades):

Mercados minoristas

1200150010001700Demanda

1700900-1

800+1

Phoenix


1700+1

700-1

1000San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8




MEJORA DE LA SOLUCIÓN: Se envían las 700 unidades a la celda (1,4) y modifican las cantidades del ciclo, manteniendo el equilibrio ent re demanda y suministro:

Mercados minoristas

1200150010001700Demanda

1700200-1

1500+1

Phoenix


1700700+1

0-1

1000San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

33




Nuevo Costo total del embarque para la solución mej orada:

(3x1000)+(6x700)+(4x1700)+(10x300)+(3x1500) + (8x20 0) = $23.100

Mercados minoristas

1200150010001700Demanda

17002001500Phoenix




5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8




Se realiza el paso No.2 PRUEBA DE OPTIMALIDAD, util izando los costos reducidos de las celdas vacías, para verificar si el plan de emb arque es óptimo:

Mercados minoristas

1200150010001700Demanda

17002001500+0+4

Phoenix

2000300+3+0

1700Los Ángeles

1700700+1

1000+5

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

34




Como se observa todos los costos reducidos de las c eldas vacías son no negativos, lo cual indica que el plan de embarque es óptimo para CCC, con un costo de $23.100

Mercados minoristas

1200150010001700Demanda

17002001500+0+4

Phoenix

2000300+3+0

1700Los Ángeles

1700700+1

1000+5

San Francisco


5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8




2. PRUEBA DE OPTIMALIDAD: Utilizando el MODI (Método de la Distribución Modificada)

Escogemos la solución inicial obtenida con el Método de la Matríz Mínima Z = 24.600

Mercados minoristas

1200150010001700Demanda

1700900800Phoenix




5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

35




2. PRUEBA DE OPTIMALIDAD: Utilizando el MODI (Método de la Distribución Modificada)Para calcular los costos reducidos en las celdas vacías, el MODI requiere calcular un valor Uipara cada fila i, y un valor Vj para cada columna j. Estos valores se eligen para que por cada celda no vacía de la fila i y columna j, el costo del embarque unitario Cij sea igual al valor de la fila Ui más el valor de la columna Vj.

Mercados minoristas

1200150010001700Demanda

1700900800Phoenix (u3)

20003001700Los Ángeles (u2)

17001500200San Francisco(u1)

SuministroDallas(V4)

Tucson(V3)

Barstow(V2)

San Diego(V1)

Plantas

5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8





Para la celdas con asignación:u1 + v2 = 3 u1 + v3 = 2 u2 + v1 = 4u2 + v4 = 10 u3 + v4 = 8 u3 + v2 = 5

Se resuelve esogiendo la fila con mayor número de variables básicas e igualando una de ella a 0, los resultados son los siguientes:

u1 = 0 u2 = 4 u3 = 2v1 = 0 v2 = 3 v3 = 2 v4 = 6

Los costos reducidos para las celdas vacías se calculan con la siguiente ecuación:

Costo reducido/celda vacía (i, j) = Cij – u i - v j

36





Mercados minoristas

1200150010001700Demanda

17009003-2-2=-18006-2-0=4Phoenix (u3)

20003008-4-2=27-4-3=01700Los Ángeles (u2)

17006-0-6=015002005-0-0=5 San Francisco(u1)


Tucson(V3)

Barstow(V2)

San Diego(V1)

Plantas

5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

Como uno de los costos reducidos es negativo, se puede obtener una mejor solución.





Se haya el circuito correspondiente al Costo Reducido negativo y se realiza la reasignación respectiva, así

Mercados minoristas

1200150010001700Demanda

1700900-1800Phoenix (u3)




Tucson(V3)

Barstow(V2)

San Diego(V1)

Plantas

5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

37





El plan de embarque mejorado tiene un costo de:(3x1000)+(2x700)+(4x1700)+(10x300)+(3x800)+(8x900) = $23.800

Mercados minoristas

1200150010001700Demanda

17009008000Phoenix (u3)




Tucson(V3)

Barstow(V2)

San Diego(V1)

Plantas

5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8




2. PRUEBA DE OPTIMALIDAD: Utilizando el MODI (Método de la Distribución Modificada)Se realiza nuevamente la prueba de optimalidad para comprobar que el plan actual sea óptimo:


Se resuelve esogiendo la fila con mayor número de variables básicas e igualando una ellas a 0, los resultados son los siguientes:

u1 = 0 u2 = 3 u3 = 1v1 = 1 v2 = 3 v3 = 2 v4 = 7



38





Mercados minoristas

1200150010001700Demanda

17009008005-1-3=16-1-1=4Phoenix (u3)

20003008-3-2=37-3-3=11700Los Ángeles (u2)

17006-0-7=-170010005-0-1=4 San Francisco(u1)


Tucson(V3)

Barstow(V2)

San Diego(V1)

Plantas

5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

Como uno de los costos reducidos es negativo, se puede obtener una mejor solución.





Se haya el circuito correspondiente al Costo Reducido negativo y se realiza la reasignación respectiva, así:

Mercados minoristas

1200150010001700Demanda

1700900800Phoenix (u3)


1700-17001000San Francisco(u1)


Tucson(V3)

Barstow(V2)

San Diego(V1)

Plantas

5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

39






Mercados minoristas

1200150010001700Demanda

17002001500Phoenix (u3)




Tucson(V3)

Barstow(V2)

San Diego(V1)

Plantas

5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8




2. PRUEBA DE OPTIMALIDAD: Utilizando el MODI (Método de la Distribución Modificada)Se realiza nuevamente la prueba de optimalidad para comprobar que el plan actual sea óptimo:


Se resuelve esogiendo la fila con mayor número de variables básicas e igualando una ellas a 0, los resultados son los siguientes:

u1 = 0 u2 = 4 u3 = 2v1 = 0 v2 = 3 v3 = 1 v4 = 6



40





Mercados minoristas

1200150010001700Demanda

170020015005-2-3=06-2-0=4Phoenix (u3)

20003008-4-1=37-4-3=01700Los Ángeles (u2)

17007002-0-1=110005-0-0=5San Francisco(u1)


Tucson(V3)

Barstow(V2)

San Diego(V1)

Plantas

5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

Como todos los costos reducidos son no negativos, se ha llegado a la solución óptima.






Mercados minoristas

1200150010001700Demanda

17002001500Phoenix (u3)




Tucson(V3)

Barstow(V2)

San Diego(V1)

Plantas

5 3 2 6

4 7 8 10

Origen

es

Destinos

6 5 3 8

41




EJERCICIO:

Una compañía de renta de autos tiene problemas de distribución, debido a que los acuerdos de renta permiten que los autos se entreguen en lugares diferentes a aquéllos en que originalmente fueron rentados. Por el momento, hay dos lugares (orígenes-fuentes) con 15 y 13 autos en exceso, respectivamente, y cuatro lugares (destinos) en los que se requieren 9, 6, 7 y 9 autos, respectivamente. Los costos unitarios de transporte (en dólares) entre los lugares son los siguientes:

31191814Origen 2

30211745Origen 1

Destino 4Destino 3Destino 2Destino 1




Cuadro de transporte:Como la demanda total (9+6+7+9=31) excede al suministro total (15+13=28), se crea un origen ficticio con un suministro igual a las 3 unidades faltantes. Los costos de embarque asociados a este origen son cero. Las asignaciones positivas a partir de este origen a un destino representan autos que no pueden ser entregados debido a faltantes en el suministro.

132

9769Demanda

33(Ficticio)

151

Suministro4321

45 17 21 30

14 18 19 31

Origen

es

Destinos

0 0 0 0

42




EJERCICIO:

Resuelva el ejercicio utilizando:• Programación Lineal• Algoritmo del transporte

• Solución Inicial:• Esquina noroeste• Matriz mínima• Vogel, etc.

• Prueba de Optimalidad:• Costos reducidos• MODI (Método de la distribución modificada)

investigación de operaciones - · pdf file2 investigación de operaciones modelos...

Documents