modelo de transporte guía1
Post on 07-Jul-2018
221 Views
Preview:
TRANSCRIPT
-
8/18/2019 Modelo de Transporte Guía1
1/11
Modelo de Transporte.
Modelo General del Problema de Transporte.
Es un caso especial de problema de programación Lineal, en el que todos los
coeficientes de las variables en las restricciones tienen coeficiente uno (1), esto es:ai,j = 1 ;∀i ,∀ jGráficamente:
U NID
ADES DE DEM
A NDA
U NID
ADES DE OFER TA
Xi,j = Unidades a enviar desde la fuente i-ésima (i=1,...,m) al destino j-ésimo (j = 1,...,n)Ci,j = Costo de enviar una unidad desde la fuente i-ésima (i=1,...,m) al destino j-ésimo(j=1,...,n)ai = Disponibilidad (oferta) en unidades, de la fuente i-ésima (i=1,...,m)
b j = Requerimiento (demanda) en unidades, del destino j-ésimo (j=1,...,n)
-
8/18/2019 Modelo de Transporte Guía1
2/11
Formulación del Problema de Transporte como un modelo de PL
Xi,j = Unidades a enviar desde la fuente i-ésima (i=1,...,m) al destino j-ésimo (j = 1,...,n)
Minimizar Z = C11X11 +...+ C1jX1j +...+ C1nX1n +...+ Ci1Xi1 +...+ CijXij +...+ CinXin +...+
Cm1Xm1 +...+ CmjXmj +...+ CmnXmn
s. a:X11 +…+ X1j +…+ X1n = a1: : : :Xi1 +…+ Xij +…+ Xin = ai: : : :Xm1 +…+ Xmj +…+ Xmn = am
X11 +…+ Xij +…+ Xmn = b1: : : :X1j +…+ Xij +…+ Xmj = b j: : : :Xm1 +…+ Xmj +…+ Xmn = bn
Xij > 0∀i ,∀ j
Todo lo disponible esenviado
Todo lo enviado fuerequerido
!! No se pierde nada!!
Otra manera de formularlo
Minimice Z =1 1
m n
ij
i j
C X ij= =
∑ ∑
s.a:
1
; 1,...,n
ij i
j
X a i m=
= =∑ Todo lo disponible es enviado
1 ; 1,...,
m
ij ji X b j n= = =∑ Todo lo enviado fue requerido Xij > 0∀i ,∀ j
Como:
1 1 1
m n m
ij i
i j i
X a= = =
=∑∑ ∑
1 1
m n
i j
i j
a b
= =
=∑ ∑ Oferta = Demanda
1 1 1
m n n
ij j
i j j
X b= = =
=∑ ∑ ∑
Ejemplo 1 (Modelo de transporte estándar)
Una empresa automotriz tiene plantas en Los Ángeles, Detroit y Nueva Orleans. Suscentros de distribución principales son Denver y Miami. Las capacidades de las plantasdurante el trimestre próximo son 1000, 1500, y 1200 automóviles. Las demandas
trimestrales en los dos centros de distribución son de 2300 y 1400 vehículos. Eldiagrama de las distancias recorridas entre las plantas y los centros de distribución es:
-
8/18/2019 Modelo de Transporte Guía1
3/11
Denver Miami
Los Ángeles 1000 2690Detroit 1250 1350Nueva Orleans 1275 850
La compañía encargada del transporte de los automóviles cobra 8 centavos por milla porautomóvil. El costo de transporte por cada ruta, que representa a C ij en el modelooriginal:
Denver MiamiLos Ángeles 80 215Detroit 100 108Nueva Orleans 102 68
Sea Xij el número de automóviles transportados de la fuente i al destino j. Como laoferta total (= 1000 + 1500 + 1200 = 3700) es igual a la demanda (= 2300 + 1400 =3700), el modelo de transporte resultante está equilibrado. Por lo tanto, el siguientemodelo de PL que representa el problema tiene todas las restricciones de igualdad.
Minimizar Z = 80X11 + 215X12 + 100X21 + 108X22 + 102X31 + 68X32
sujeto a:X11+ X12 = 1000
X21+ X22 = 1500X
31+ X
32 = 1200
X11+ X21+ X31 = 2300X12+ X22+ X32 = 1400
Xij>=0, para todas las i y j
Un método mas resumido para representar el modelo de transporte consiste en utilizar loque se llama tabla simplex de transporte. Esta es una forma de matriz donde susrenglones representan las fuentes y sus columnas los destinos. Los elementos de costoCij se resumen en la esquina noroeste de la celda de la matriz (i,j). Por lo tanto, elejemplo planteado se puede resumir en la tabla siguiente:
DestinosDenver Miami Oferta
80 215Los ÁngelesX11 X12
1000
100 108DetroitX21 X22
1500
102 68
Fuentes
Nueva OrleansX31 X32
1200
Demanda 2300 1400
-
8/18/2019 Modelo de Transporte Guía1
4/11
Ejemplo 2 (Modelo de transporte no equilibrado)
En el ejemplo anterior, supongamos que la capacidad de la planta de Detroit es de 1300automóviles (en vez de 1500). Se dice que la situación esta desequilibrada debido a quela oferta total (= 3500) no es igual a la demanda total (= 3700). Nuestro objetivo
consiste en volver a formular el modelo de transporte de manera que distribuya lacantidad faltante (3700 – 3500 = 200) en forma óptima entre los centros de distribución.
Como la demanda es mayor que la oferta se puede agregar una planta ficticia con unacapacidad de 200. Se permite que dicha planta, en condiciones normales, envíe su“producción” a todos los centros de distribución. Físicamente, la cantidad de unidadesenviadas a un destino desde una planta ficticia representará la cantidad faltante en esedestino.
La única información que falta para completar el modelo son los “costos de transporte”unitarios de la planta ficticia a los destinos. Como la planta no existe, no habrá ningún
envío físico y el costo de transporte unitario es cero.
Denver Miami Los Ángeles 80 215 1000
Detroit 100 108 1300Nueva Orleans 102 68 1200Planta ficticia 0 0 200
Sin embargo, podemos enfocar la situación desde otro ángulo diciendo que se incurre enun costo de penalización por cada unidad de demanda insatisfecha en algún centro de
distribución. Por ejemplo, si se quiere que Miami reciba toda su demanda, se asigna uncosto elevado de transporte por unidad a la entrada del punto de origen ficticio a Miami.
De manera análoga, si la oferta es mayor que la demanda podemos añadir un destinoficticio que absolverá la diferencia. Por ejemplo, suponga que la demanda en Denverdisminuye a 1900. Cualquier automóvil enviado de una planta a un centro dedistribución ficticio representa un excedente en la planta.
Denver MiamiDestinoFicticio
Los Ángeles 80 215 0 1000
Detroit 100 108 0 1500Nueva Orleans 102 68 0 1200
-
8/18/2019 Modelo de Transporte Guía1
5/11
Ejercicio para entender la aplicación de la metodología:
Se cuenta con la siguiente tabla de transporte:
Destinos
1 2 3 4 Oferta10 2 20 111
X11 X12 X13 X14 15
12 7 9 202
X21 X22 X23 X24 25
4 14 16 18
Fuentes
3X31 X32 X33 X34
10
Demanda 5 15 15 15
Pasos para resolver un modelo de transporte
1. Balancear la tabla si j
b , lo cual se logra agregando un origen ficticio
(cuando < ) ó un destino ficticio (cuando
1 1
m n
i
i j
a= =
≠∑ ∑
j
1
m
i
i
a=
∑1
n
j
b=
∑1
m
i
i
a=
∑ >1
n
j
j
b=
∑ )
2. Determinar una solución básica factible inicial.3. Seleccionar la variable que entra, de entre las no básicas, utilizando la condición
de optimalidad del método simplex.4. Seleccionar la variable que sale, de entre las básicas, utilizando la condición de
factibilidad del método simplex.5. Determinar la próxima solución óptima, volviendo al paso 3.
2. Determinación de la solución inicial
Como el modelo de transporte está equilibrado, una de las ecuaciones del mismo debeser redundante. Por ello, el modelo tiene m+n-1 ecuaciones de restricciónindependientes, y por ende m+n-1 variables básicas.
La solución básica inicial factible puede obtenerse utilizando cualquiera de lossiguientes métodos:
2.1. Método de la esquina noroeste
Características. Sencillo y fácil de hacer.. No tiene en cuenta los costos para hacer las asignaciones.. Su solución no tiene porque ser cercana al óptimo.
Algoritmo
1. Empiece por la esquina noroeste y asigne lo máximo posible (lo menor entre la oferta
y la demanda, respectivamente) a esta ruta.
-
8/18/2019 Modelo de Transporte Guía1
6/11
2. Tache la fila o columna que se halla satisfecho. Si ambas fueron satisfechas, entoncestachar cualquiera de ellas. Actualizar la fila o columna no tachada.
3. Si lo que se tachó fue una columna, entonces moverse hacia la celda siguiente a laderecha, en caso contrario, hacia la celda de abajo.
4. Continuar hasta llegar a la esquina inferior derecha en la que se elimina fila ycolumna al mismo tiempo.
Solución para el ejercicio planteado:
2.2. Método del costo mínimo
Características. Es más elaborado que el método de la esquina noroeste.. Tiene en cuenta los costos para hacer las asignaciones.. No siempre es el más cercano al óptimo.
Algoritmo
1. Seleccione la ruta con el menor costo de toda la tabla, si hay empate, escojaarbitrariamente (Cualquiera de los empatados).
2. Asigne lo máximo posible entre la oferta y la demanda (El menor de los dos).
3. Tache la fila o columna satisfecha. Si ambas fueron satisfechas, entonces tachar unasola (cualquiera). Actualice la fila o columna no tachada.
4. Repetir todos los pasos anteriores hasta que todas las casillas queden asignadas.
Solución para el ejercicio planteado:
-
8/18/2019 Modelo de Transporte Guía1
7/11
2.3. Método de Vogel
Características. Es más elaborado que los anteriores, más técnico y con mayor trabajo.. Tiene en cuenta los costos, las ofertas y las demandas para hacer las asignaciones.. Generalmente se ubica cerca al óptimo.
Algoritmo
1. Calcule una penalización, dada por la diferencia entre el costo más pequeño y el
segundo costo más pequeño, para cada fila y para cada columna no tachada.
2. Selecciones entre las filas y columnas, la que tenga la mayor diferencia (en caso deempate, decida arbitrariamente).
3. Dentro de la fila o columna seleccionada, asigne lo máximo posible en la casilla conmenor costo.
4. Tache la fila o columna al igual que en los dos métodos previos.
5. Repita los pasos hasta que no se puedan calcular más penalizaciones, situación en la
cual debe aplicarse e método del costo mínimo hasta asignar todas las rutas o casillas.
Solución para el ejercicio planteado:
-
8/18/2019 Modelo de Transporte Guía1
8/11
3. Selección de la variable entrante
Se hace utilizando el método de multiplicadores. Este establece:
1. Se resuelve el sistema de ecuaciones (de m+n-1 ecuaciones y m+n variables) que seobtiene de la relación:
Para cada variable básica se cumple que U i + V j = C ij
Este sistema se resuelve asignando un valor arbitrario a cualquiera de las m+n variables,de forma tal que el sistema se reduzca a uno con n+m-1 ecuaciones y n+m-1 variables.
-
8/18/2019 Modelo de Transporte Guía1
9/11
2. Para cada variable no básica se cumple que C pq = U p + V q - C pq, donde U p y V q sonlos valores obtenidos en el paso anterior.
3. La variable que entra es la que posee el mayor C pq . Como el problema es deminimización, en caso de no haber valores de C pq positivos, se ha alcanzado el óptimo.
Solución para el ejercicio planteado:
Utilizando la solución inicial obtenida con el método de la esquina noroeste:
-
8/18/2019 Modelo de Transporte Guía1
10/11
4. Selección de la variable saliente
1. Se dibuja un circuito cerrado cuyas esquinas deben ser variables básicas ó la variableque entra. Dicho circuito posee ciertas características:
- Sólo puede contener segmentos horizontales o verticales.- Contiene un número par de esquinas.- Existe exactamente un lazo para una determinada variable de entrada.
2. Se asigna + y – a cada esquina, en forma alternada, empezando con la variables queentra, a la cual le corresponde un +.
3. La variable que sale es aquella casilla con signo negativo, que a su vez tenga el
menor valor actual. Los empates se rompen arbitrariamente.Solución para el ejercicio planteado:
-
8/18/2019 Modelo de Transporte Guía1
11/11
top related