Upload
nicolas-ariel-labra-ochoa
View
340
Download
3
Tags:
Embed Size (px)
Citation preview
Método de Transporte
Descripción del problema de transporte1.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)
arco
Método de Transporte Representación del Modelo
Fuentes de Suministro Destinos
c11, X11
cmn, Xmn
Red de m fuentes y n destinos
Ruta por la cual se transporta el mercadería
1
2
m
.
.
.
S1
S2
Sm
Unidades de oferta
1
2
n
.
.
.
d1
d2
dn
Unidades de
demanda
nodo
Método de Transporte Función Objetivo
Minimizar Z = Σ Σ cijxij
Restricciones La suma de los envíos desde una fuente no puede ser
mayor que su oferta Σ xij ≤ Si i = 1,2,…., m
La suma de los envíos a un destino debe satisfacer la demanda Σ xij ≥ di j = 1,2,…., n
No - Negatividad xij ≥ 0 para todas las i y j
m n
i=1 j=1
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:
Denver Miami
Los Ángeles 1000 2690
Detroit 1250 1350
Nueva Orleans
1275 850
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 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 Plantax11 + x12 ≤ 1000
x21 + x22 ≤ 1500 x31 + x 32 ≤ 1200
Restricciones de Demandax11 + x21 + x31 ≥ 2300
x12 + x22 + x32 ≥ 1400 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)
FuentesDestinos
OfertaDenver Miami
Los Ángelesc11 c12
1000x11 x12
Detroitc21 c22
1500x21 x22
Nueva Orleansc31 c32
1200x31 X32
Demanda 2300 1400
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)
FuentesDestinos
OfertaDenver Miami
Los Ángeles80 215
1000x11 x12
Detroit100 108
1500x21 x22
Nueva Orleans102 68
1200x31 X32
Demanda 2300 1400
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
FuentesDestinos
OfertaDenver Miami
Los Ángeles80 215
1000x11 x12
Detroit100 108
1300x21 x22
Nueva Orleans102 68
1200x31 X32
Planta Ficticia0 0
200x41 X42
Demanda 2300 1400
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
FuenteDestino
OfertaDenver Miami Centro Ficticio
Los Ángeles
80 215 01000x11 x12 x13
Detroit100 108 0
1500x21 x22 x23
Nueva Orleans
102 68 01200
x31 X32 X33
Demanda 1900 1400 400
Modelo de Transporte en Desequilibrio
Modelo de Transporte en LindoMODEL
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
Formato tabla de coeficientes de restricciones
Fuentes (origen)
Costo por Unidad Distribuida
RecursosDestinos
1 2 …… n
1
2.
m
C11
C21
.
Cm1
C12
C22
.
Cm2
C1n
C2n
.
Cmn
S1
S2
.
SmDemanda d1 d2 ……. dn
X11 X12 … X1n X21 X22 … X2n … Xm1 Xm2 … Xmn
1 S1
S2
…
Sm
Restricciones de
Origen
2
…. . .
m
1 d1
d2
…
dn
Restricciones de
Demanda
2 ……
…
n
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
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
VB EC Z Xij Xj Xm+jLADO
DERECHO
Z 0 -1 Cij - ui - vj M-ui M-vj
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 u i y vj si de resuelve el sistema de ecuaciones C ij – 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
Información adicional que se agrega en cada celda:
DestinosRecursos ui
1 2 …… n
Fuentes
1c11 c12 ……
C1n S1
2c21 C21 ……
c2n S2
…… …
3mcm1 cm1 ……
cmn Sm
Demanda d1 d2 ….. dnZ =
vj
Si Xij es una variable básica
cij
(Xij)
Si Xij es una variable no básica
cij
cij – ui - vj
Solución del Modelo de Transporte Etapa : Determinar una solución
factible inicial Regla de la Esquina Noroeste Método de Costo Mínimo Método de Aproximación de Vogel
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 (método Simplex), detenerse; de lo contrario continuar con el paso 3
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
DestinosRecursos
1 2 3 4
Origen
1
10 0 20 11
15x11 x12 x13 x14
2
12 7 9 20
25x21 x22 x23 x24
3
0 14 16 18
5x31 x32 x33 x34
Demanda 5 15 15 10 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: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
Destinos
Recursos
1 2 3 4
Origen
1
10 0 20 11
15x11 x12 x13 x14
2
12 7 9 20
25x21 x22 x23 x24
3
0 14 16 18
5x31 x32 x33 x34
Demanda 5 15 15 10 45
/ 10X11 = 5
N
O
Solución Básica: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
X12 = 10 Como se agota el recurso se
tacha la fila Falta satisfacer una demanda
de 5 unidades en la columna 2
Destinos
Recursos
1 2 3 4
Origen
1
10 0 20 11
15X11 =5 x12 x13 x14
2
12 7 9 20
25x21 x22 x23 x24
3
0 14 16 18
5x31 x32 x33 x34
Demanda 5 15 15 10 45
/ 10
/5
N
O
X12=10
Solución Básica: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
X12 = 10 Como se agota el recurso se
tacha la fila 1 Falta satisfacer una demanda
de 5 unidades en la columna 2 X22 = 5
Como se satisface la demanda, se tacha la columna 2
Los recursos en la fila 2 se reducen a 20 unidades
Destinos
Recursos
1 2 3 4
Origen
1
10 0 20 11
15X11 = 5 X12 = 10x13 x14
2
12 7 9 20
25x21 x22 x23 x24
3
0 14 16 18
5x31 x32 x33 x34
Demanda 5 15 15 10 45
/ 10
/5
/ 20
N
O
X22 = 5
Solución Básica: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
Destinos
Recursos
1 2 3 4
Origen
1
10 0 20 11
15X11 = 5 X12 = 10x13 x14
2
12 7 9 20
25x21 X22 = 5 x23 x24
3
0 14 16 18
5x31 x32 x33 x34
Demanda 5 15 15 10 45
/ 10
/5
/ 20/ --- 5
N
O
X23=15
Solución Básica: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 X24 = 5
Como se agota el recurso se tacha la fila 2
Falta satisfacer una demanda de 5 unidades en la columna 4
Destinos
Recursos
1 2 3 4
Origen
1
10 0 20 11
15X11 = 5 X12 = 10x13 x14
2
12 7 9 20
25x21 X22 = 5 X23 = 15x24
3
0 14 16 18
5x31 x32 x33 x34
Demanda 5 15 15 10 45
/ 10
/5
/ 20/ --- 5
/5
N
O
X24 = 5
Solución Básica: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
X24 = 5 Como se agota el recurso se
tacha la fila 2 Falta satisfacer una demanda
de 5 unidades en la columna 4 X34 = 5
Como se satisface simultánea-mente la demanda y se agota la oferta, solo se tacha la fila 3 o la columna 4.
El proceso termina
Destinos
Recursos
1 2 3 4
Origen
1
10 0 20 11
15X11 = 5 X12 = 10x13 x14
2
12 7 9 20
25x21 X22 = 5 X23 = 15X24 = 5
3
0 14 16 18
5x31 x32 x33 x34
Demanda 5 15 15 10 45
/ 10
/5
/ 20/ --- 5
/5
N
O
X34 = 5
Solución Básica: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
Destinos
Recursos
1 2 3 4
Origen
1
10 0 20 11
15X11 = 5 X12 = 10 x13 x14
2
12 7 9 20
25x21 X22 = 5 X23 = 15 X24 = 5
3
0 14 16 18
5x31 x32 x33 X34 = 5
Demanda 5 15 15 10 45
N
O
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 Los empates se rompen en forma
arbitraria Ajustar los recursos (fila) y demanda
(columna) Tachar la fila o columna satisfecha
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
DestinosRecurso
s1 2 3 4
Origen
1
10 0 20 11
15x11 x12 x13 x14
2
12 7 9 20
25x21 x22 x23 x24
3
0 14 16 18
5x31 x32 x33 x34
Demanda 5 15 15 10 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 4
Origen
1
10 0 20 11
15x11 x12 x13 x14
2
12 7 9 20
25x21 x22 x23 x24
3
0 14 16 18
5x31 x32 x33 x34
Demanda 5 15 15 10 45
X12 =15--- 0
--- 0
X31=5--- 0
--- 0
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 2 3 4
Origen
1
10 0 20 11
15x11 x12 x13 x14
2
12 7 9 20
25x21 x22 x23 x24
3
0 14 16 18
5x31 x32 x33 x34
Demanda 5 15 15 10 45
X12 =15--- 0
--- 0
X31 =5--- 0
--- 0
X23 =15
--- 0
--- 10
X11 = 0
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 2 3 4
Origen
1
10 0 20 11
15x11 x12 x13 x14
2
12 7 9 20
25x21 x22 x23 x24
3
0 14 16 18
5x31 x32 x33 x34
Demanda 5 15 15 10 45
X12 =15--- 0
--- 0
X31 =5--- 0
--- 0
X23 =15
--- 0
--- 10
X11 = 0 X14 = 0
X24 =10
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) 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)
Filas
F1: 10 – 0 = 10;Penalización = 10 F2: 9 – 7 = 2; Penalización = 2 F3: 14 – 0 = 14; Penalización = 14
DestinosRecursos Penalización
1 2 3 4
Origen
110 0 20 11
15 10x11 x12 x13 x14
212 7 9 20
25 2x21 x22 x23 x24
30 14 16 18
5 14x31 x32 x33 x34
Demanda 5 15 15 10
DestinosRecursos
1 2 3 4
Origen
110 0 20 11
15 x11 x12 x13 x14
212 7 9 20
25x21 x22 x23 x24
30 14 16 18
5x31 x32 x33 x34
Demanda 5 15 15 10
Solución Básica:Método de Aproximación de Vogel (VAM)
PASO 1
Columnas
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
DestinosRecursos Penalización
1 2 3 4
Origen
110 0 20 11
15 10x11 x12 x13 x14
212 7 9 20
25 2x21 x22 x23 x24
30 14 16 18
5 14x31 x32 x33 x34
Demanda 5 15 15 10
DestinosRecursos Penalización
1 2 3 4
Origen
110 0 20 11
15 10x11 x12 x13 x14
212 7 9 20
25 2x21 x22 x23 x24
30 14 16 18
5 14x31 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) PASO 2: Identifique la fila o columna con la
mayor penalización, rompiendo empates en forma arbitraria. Fila 3
Asigne el mayor valor posible a la variable con el costo más bajo de la fila o columna seleccionada.
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)
DestinosRecursos Penalización
1 2 3 4
Origen
110 0 20 11
15 10x11 x12 x13 x14
212 7 9 20
25 2x21 x22 x23 x24
30 14 16 18
5 14x31 x32 x33 x34
Demanda 5 15 15 10Penalización 10 7 7 7
DestinosRecursos Penalización
1 2 3 4
Origen
110 0 20 11
15 x12 x13 x14
212 7 9 20
25x22 x23 x24
30
0X31=5
Demanda 0 15 15 10
Penalización
140
X31 = 5
0
0
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éngaseb) Si solo hay una fila (columna) con oferta
(demanda) positiva sin tachar, determínese las variables básicas de la fila (columna) a través del método de costo mínimo
c) Si todas las filas y columnas sin tachar tienen oferta y demanda cero (asignadas), determínese las variables 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. (Las filas y columnas con oferta y demanda cero asignadas no deben utilizarse para determinar penalizaciones.
Nuevo conjunto de penalizaciones ( la fila 3 con oferta cero no se
utiliza)
DestinosRecursos Penalización
1 2 3 4
Origen
110 0 20 11
15 11x12 x13 x14
212 7 9 20
25 2x22 x23 x24
30
0 ---X31=5
Demanda 0 15 15 10
Penalización - 7 11 9
DestinosRecursos Penalización
1 2 3 4
Origen
110 0 20 11
15 x12 x13 x14
212 7 9 20
25x22 x23 x24
30
0X31=5
Demanda 0 15 15 10
Penalización
Solución Básica:Método de Aproximación de Vogel (VAM) Nuevo conjunto de penalizaciones
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
DestinosRecursos Penalización
1 2 3 4
Origen
110 0 20 11
15 11x12 x13 x14
212 7 9 20
25 2x22 x23 x24
30
0 ---X31=5
Demanda 0 15 15 10
Penalización - 7 11 9
DestinosRecursos Penalización
1 2 3 4
Origen
110 0 20 11
15 x12 x13 x14
212 7 9 20
10X22 X23 =15 x24
30
0X31=5
Demanda 0 15 0 10
Penalización
Solución Básica:Método de Aproximación de Vogel (VAM) Nuevo conjunto de penalizaciones
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
DestinosRecursos Penalización
1 2 3 4
Origen
110 0 20 11
15 11x12 x14
212 7 9 20
10 13X22 X23 =15 x24
30
0 -X31=5
Demanda 0 15 0 10
Penalización - 7 - 9
DestinosRecursos
Penalización1 2 3 4
Origen
110 0 20 11
15 x12 x14
212 7 9 20
0X22 = 10 X23 =15 x24
30
0X31=5Demanda 0 5 0 10
Penalización
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
Costo = 5*0 + 10*11 + 10*7 + 15*9 + 0*20 + 5*0 = $ 335
DestinosRecursos
Penalización1 2 3 4
Origen
110 0 20 11
15 x12 x14
212 7 9 20
0X22 = 10 X23 =15 x24
30
0X31=5Demanda 0 5 0 10
Penalización
DestinosRecursos
Penalización1 2 3 4
Origen
110 0 20 11
15 X12 = 5 X14 = 10
212 7 9 20
0X22 = 10 X23 =15 X24 = 0
30
0X31=5Demanda 0 5 0 10
Penalización
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.
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.
PlantasCentros de Distribución
1 2 3 4
1 800 1300 400 700
2 1100 1400 600 1000
3 600 1200 800 900
Esquina Noroeste
Plantas Centros de Distribución
Recursos1 2 3 4
1 500 750 300 450
1210 2
2 650 800 400 600
17 8 9
3 400 700 500 550
11 1 10
Demada 10 10 10 10 $ 22.500
Modelo de Transporte
Plantas Centros de Distribución
Recursos1 2 3 4
1 500 750 300 450
12X11 X12 X13 X14
2 650 800 400 600
17X21 X22 X23 X24
3 400 700 500 550
11X31 X32 X33 X34 Demada 10 10 10 10 Z = ?
Costo Minimo
Plantas Centros de Distribución
Recursos1 2 3 4
1 500 750 300 450
12 10 2
2 650 800 400 600
17 10 7
3 400 700 500 550
1110 1
Demada 10 10 10 10 $ 20.650
Vogel
Plantas Centros de Distribución
Recursos1 2 3 4
1 500 750 300 450
12 2 10
2 650 800 400 600
17 7 10
3 400 700 500 550
1110 1
Demada 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:
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.
PlantaCiudad
1 2 3123
600320500
700300480
400350450
PlantaCiudad
Recursos1 2 3
1 600 700 400
25
2 320 300 350
40
3 500 480 450
30
Dda. 30 35 25
Modelo de Transporte
PlantaCiudad
Recursos1 2 3
1 600 700 400
25
2 320 300 350
40
3 500 480 450
30
4 1000 1000 M
13
Dda. 36 42 30 Z = ?
Costo Minimo
PlantaCiudad
Recursos1 2 3
1 600 700 400
25 25
2 320 300 350
40 40
3 500 480 450
3023 2 5
4 1000 1000 M
1313
Dda. 36 42 30 $ 49.710
Esquina Noroeste
PlantaCiudad
Recursos1 2 3
1 600 700 400
2525
2 320 300 350
4011 29
3 500 480 450
30 13 17
4 1000 1000 M
13 13
Dda. 36 42 30 $ 41.110
Vogel
PlantaCiudad
Recursos1 2 3
1 600 700 400
25 25
2 320 300 350
40 40
3 500 480 450
3023 2 5
4 1000 1000 M
1313
Dda. 36 42 30 $ 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: X11 = 5, X12= 10,
X22 = 5, X23= 15,
X24 = 5, X34= 5
Con Costos c11 = 10 c12 = 0
c22 = 7 c23 = 9
c24 = 20 c25 = 18
Recurso
10 0 20 1115
5 1012 7 9 20
255 15 5
0 14 16 185
5Demanda 5 15 15 10
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 = X12: u1 + v2 = c12 v2 = X22: u2 + v2 = c22 u2 = X23: u2 + v3 = c23 v3 = X24: u2 + v4 = c24 v4 = X34: u3 + v4 = c34 u3 =
Recurso
10 0 20 1115
5 1012 7 9 20
255 15 5
0 14 16 185
5Demanda 5 15 15 10
u1 =
v1 = v2 =
u2 =
u3 =
v3 = v4 =
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 v1 = 10 X12: u1 + v2 = 0 v2 = 0 X22: u2 + v2 = 7 u2 = 7 X23: u2 + v3 = 9 v3 = 2 X24: u2 + v4 = 20 v4 = 13 X34: u3 + v4 = 18 u3 = 5
Recurso
10 0 20 1115
5 1012 7 9 20
255 15 5
0 14 16 185
5Demanda 5 15 15 10
u1 = 0
v1 = 10v2 = 0
u2 = 7
u3 = 5
v3 = 2 v4 = 13
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ásicaXjj : ui + vj = cij
Sea u1= 0 X11: u1 + v1 = 10 v1 = 10 X12: u1 + v2 = 0 v2 = 0 X22: u2 + v2 = 7 u2 = 7 X23: u2 + v3 = 9 v3 = 2 X24: u2 + v4 = 20 v4 = 13 X34: u3 + v4 = 18 u3 = 5
Recurso
10 0 20 1115
5 1012 7 9 20
255 15 5
0 14 16 185
5Demanda 5 15 15 10
u1 = 0
v1 = v2 =
u2 =
u3 =
v3 = v4 =
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 Recurso
10 0 20 1115
5 1012 7 9 20
255 15 5
0 14 16 185
5Demanda 5 15 15 10
u1 = 0
v1 = 10 v2 = 0
u2 = 7
u3 = 5
v3 = 2 v4 = 13 Recurso
10 0 20 1115
5 10 C13* C14*
12 7 9 2025C21* 5 15 5
0 14 16 185C31* C32* C33* 5
Demanda 5 15 15 10
u1 = 0
v1 = 10 v2 = 0
u2 = 7
u3 = 5
v3 = 2 v4 = 13
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
X13 C13* = u1 + v3 – C13
X14 C14* = u1 + v4 – C14
X21 C21* = u2 + v1 – C21
X31 C31* = u3 + v1 – C31
X32 C32* = u3 + v2 – C32
X33 C33* = u3 + v3 – C33
Recurso
10 0 20 1115
5 1012 7 9 20
255 15 5
0 14 16 185
5Demanda 5 15 15 10
u1 = 0
v1 = 10 v2 = 0
u2 = 7
u3 = 5
v3 = 2 v4 = 13
Determinación de la Variable de Entrada
Multiplicadores asociados a las Variable Básica
Soluciones de Variables No Básicas, Xpq :
C* = up + vq – Cpq X13: C*13 = u1 + v3 – C13 = 0 + 2 – 20 = -18
X14: C*14 = u1 + v4 – C14 = 0 + 13 – 11 = 2
X21: C*21 = u2 + v1 – C21 = 7 + 10 – 12 = 5
X31: C*31 = u3 + v1 – C31 = 5 + 10 – 0 = 15
X32: C*32 = u3 + v2 – C32 = 5 + 0 – 14 = - 9
X33: C*33 = u3 + v3 – C33 = 5 + 2 – 16 = - 9
Recurso
10 0 20 1115
5 1012 7 9 20
255 15 5
0 14 16 185
5Demanda 5 15 15 10
u1 = 0
v1 = 10 v2 = 0
u2 = 7
u3 = 5
v3 = 2 v4 = 13
Uso de la tabla de costos para determinar C*pq asociada a las variables no
básicas, Xpq : C*pq = up + vq – Cpq
Recurso
10 0 20 1115
5 1012 7 9 20
255 15 5
0 14 16 185
5Demanda 5 15 15 10
Determinación de la Variable de Entrada
u1 = 0
v1 = 10 v2 = 0
u2 = 7
u3 = 5
v3 = 2 v4 = 13 Recurso
10 0 20 1115
5 10 C*13= C*13=
12 7 9 2025C*23= 5 15 5
0 14 16 185C*31= C*32= C*33= 5
Demanda 5 15 15 10
u1 = 0
v1 = 10 v2 = 0
u2 = 7
u3 = 5
v3 = 2 v4 = 13
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 SalePrueba 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
DestinosRecurso
s1 2 3 4
Origen
110 0 20 11
155 10
212 7 9 20
255 15 5
30 14 16 18
5X31 5Demanda 5 15 15 10
Determinación de la Variable que SalePrueba 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
DestinosRecurso
s1 2 3 4
Origen
1(-) 10 (+) 0 20 11
155 10
212 (-) 7 9 (+) 20
255 15 5
3(+) 0 14 16 (-) 18
5X31 5Demanda 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.
DestinosRecursos
1 2 3 4
Origen
110 0 20 11
155 (-) 10 (+)
212 7 9 20
255 (-) 15 5 (+)
30 14 16 18
5X31 5 (-)
Demanda 5 15 15 10
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. Destinos
Recursos1 2 3 4
Origen
110 0 20 11
15X11= 0 X12= 15
212 7 9 20
25X22= 0 15 X23= 10
30 14 16 18
55
Demanda 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??
ResumenEntra X31
Fuentes
Destinos
Recurso ui
Fuentes
Destinos
Recurso ui1 2 3 4
1 2 3 4
1 10 0 20 11
15 0
1(-) 10 (+) 0 20 11
15 5 10 -18 2 5 10
2 12 7 9 20
25 7
2 12 (-) 7 9 (+) 20
25 5 5 15 5 5 15 5
3 0 14 16 18
5 5
3(+) 0 14 16 (-) 18
5 15 -9 -9 5 X31 5
Demanda 5 15 15 10$ 410
Demanda 5 15 15 10
vj 10 0 2 13 vj
Entra X31 Sale X34
Fuentes
Destinos
Recurso ui
Fuentes
Destinos
Recurso ui1 2 3 4
1 2 3 4
1 10 0 20 11
15
1 10 0 20 11
15 -70 15 0 15 -18 2
2 12 7 9 20
25
2 12 7 9 20
25 0 0 15 10 5 0 15 10
3 0 14 16 18
5
3 0 14 16 18
5 -175 5 -24 -24 -15
Demanda 5 15 15 10$ 335
Demanda 5 15 15 10
vj vj 17 7 9 20
ResumenEntra X21
Fuentes
Destinos
Recurso ui
Fuentes
Destinos
Recurso ui1 2 3 4
1 2 3 4
1 10 0 20 11
15 -7
1(-) 10 (+) 0 20 11
15 0 15 -18 2 0 15
2 12 7 9 20
25 0
2(+) 12 (-) 7 9 20
25 5 0 15 10 X21 0 15 10
3 0 14 16 18
5 -17
3 0 14 16 18
5 5 -24 -24 -15 5
Demanda 5 15 15 10$ 0
Demanda 5 15 15 10
vj 17 7 9 20 vj
Entra X21 Sale X11
Fuentes
Destinos
Recurso ui
Fuentes
Destinos
Recurso ui1 2 3 4
1 2 3 4
1 10 0 20 11
15
1 10 0 20 11
15 -7 15 -5 15 -18 2
2 12 7 9 20
25
2 12 7 9 20
25 00 0 15 10 0 0 15 10
3 0 14 16 18
5
3 0 14 16 18
5 -125 5 -19 -19 -10
Demanda 5 15 15 10$ 335
Demanda 5 15 15 10
vj vj 12 7 9 20
ResumenEntra X14
Fuentes
Destinos
Recurso ui
Fuentes
Destinos
Recurso ui1 2 3 4
1 2 3 4
1 10 0 20 11
15 -7
1 10 (-) 0 20 (+) 11
15 -5 15 -18 2 15 X14
2 12 7 9 20
25 0
2 12 (+) 7 9 (-) 20
25 0 0 15 10 0 0 15 10
3 0 14 16 18
5 -12
3 0 14 16 18
5 5 -19 -19 -10 5
Demanda 5 15 15 10$ 335
Demanda 5 15 15 10$ 335
vj 12 7 9 20 vj
Sale X24
Fuentes
Destinos
Recurso ui
Fuentes
Destinos
Recurso ui1 2 3 4
1 2 3 4
1 10 0 20 11
15
1 10 0 20 11
15 -7 5 10 2 5 -11 10
2 12 7 9 20
25
2 12 7 9 20
25 00 10 15 0 10 15 -2
3 0 14 16 18
5
3 0 14 16 18
5 -125 5 -7 -7 0
Demanda 5 15 15 10$ 315
Demanda 5 15 15 10OPTIMO
vj vj 12 7 9 18
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 G
A 0
B 5
C 10 10 15 5
Optimo 1:De A Unidades CostoA F 10 5A G 10 0B F 30 5C D 10 10C E 15 10C G 20 5
Solución Optima No Degenerada Z *1 = $550
Soluciones Múltiples
Optimo 2:
D E F GA 10 10B 30C 15 30
De A Unidades CostoA D 10 5A F 10 5B F 30 5C E 15 10C G 30 5
Solución Optima Degenerada Z*2 = $550
Soluciones MúltiplesOptimo 3:
D E F GA 20B 10 20C 15 30
DE A Unidades CostoA F 20 5B D 10 5B F 20 5C E 15 10C G 30 5
Solución Optima 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
D1
D2
Nodos puros de Oferta
Nodos puros de Demanda
A1
A2
Nodos de Transbordo
F1
F2
F3
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
800
900
500
1200
1000
D3
D2
D1
T1
T2
P1
P2
3
4
42
5
8
65
39
RED - MODELO DE ASIGNACION
800
900
500
1200
1000 T1
T2
P1
P2
XP1T1XP1T2
X T2D2X P2T1
XP2T2
X T1D1
XT1D2
XD
1D2
XD
2D3X
T2D3
D2
D1
D3
PROBLEMA PROGRAMACION LINEAL
F.O. Mín Z = 3XP1T1 + 4XP1T2 + 2XP2T1 + 5XP2T2 + 8XT1D1 + 6XT1D2 + 4XT2D2 + 9XT2D3 + 5XD1D2 + 3XD2D3
s.a.
P1: XP1T1 + XP1T2 = 1000P2: XP2T1 + XP2T2 = 1200T1: XP1T1 + XP2T1 = XT1D1 + XT1D2
T2: XP2T2 = XT2D2 + XT2D3
D1: XT1D1 = XD1D2 + 800D2: XT1D2 + XT2D2 + XD1D2 = XD2D3 + 900D3: XT2D3 + XD2D3 = 500
Xij > 0
PROBLEMA PROGRAMACION LINEAL
EJEMPLO DE TRANSBORDO
• Nodos puros de Oferta
• Nodos de Transbordo
• Nodos puros de Demanda
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)
P1, P2
D3
T1, T2, D1, D2
MODELO DE ASIGNACIONPROBLEMA DE TRANSPORTE
800
900
500
1200
1000
T1
P1XP1T1
XP1T2 XP2T1
XT1D2
XD1D2
XD2D3
D1
P2
T1
T2
T2
D2
D1
D2
D3
XT2D3
XP2T2XT1D1
XT2D2
MODELO
DESTINO
FUENTET1 T2 D1 D2 D3 OFERTA
P1
P2
T1
T2
D1
D2
DEMANDA
NODOS PUROS DE OFERTAY 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
Demanda en un Nodo puro de Demanda
Oferta Original
Demanda Original
Un nodo puro de oferta no posee amortiguador
Un nodo puro de demanda no posee amortiguador
MODELO
DESTINO
FUENTET1 T2 D1 D2 D3 OFERTA
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
Demanda en un Nodo de Transbordo
Oferta Original
Amorti-guador
Demanda Original
Amorti-guador
+
+
La oferta necesariamente posee un amortiguador, mientras que a veces se encuentra oferta original
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
400
400
200
300
500
200
P1
P2
T1
T2
D1
D2
D2
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 original300
200
300
600
400
200
P1
P2
T1
T2
D1
D2
D2
MODELO
DESTINO
FUENTET1 T2 D1 D2 D3 OFERTA
P1 1000
P2 1200
T1 B1
T2 B2
D1 B3
D2 B4
DEMANDA B1 B2B3+80
0B4+90
0500
Se obtiene la 1ª solución mediante método de Vogel
P1
T1Ofta
Dda
1000
1200
B1
900+B4800+B3B1 B2 500
3
T2 D1 D3D2
P2
T1
B2
B3
B4
T2
D1
D2
3
5
M
M
M
M
M
M
M
M
M
M
M
M M
M
M
M
M
4
5
M
2
8 6
4 9
M
M
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 < B3 < 1400
0 < B2 < 1400 0 < B4 < 500
EJEMPLO DE TRANSBORDO
P1
T1Ofta
Dda
1000
1200
500
3T2 D1 D3D2
P2
T1
T2
D1
D2
3
5
M
M
M
M
M
M
M
M
M M
M
M
M M
M
M
M
M
4
5
M
2
8 6
4 9
M
1
3
M
5
M
1 1 M 1 6
800
*
800
1000
1400
400
500
B1
B2
B3
B4
B1 B2 800+B3900+B4
2
*
MM
M
3
* *
MM
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 = 500Si 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
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
EJEMPLO DE TRANSBORDO
m + n - 1 = 10Sin 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 TRANSBORDOOfta
Dda
1000
1200
500
3
3
5
M
M
M
M
M
M
M
M
M M
M
M
M M
M
M
M
M
4
5
M
2
8 6
4 9
M
800
800
1000
1400
400
500
0
0
0
0
P1
T1 T2 D1 D3D2
P2
T1
T2
D1
D2
B1
B2
B3
B4
B1 B2 800+B3900+B4
Se deben calcular todos los precios sombra
EJEMPLO DE TRANSBORDOOfta
Dda
1000
1200
500
3
3
5
M
M
M
M
M
M
M
M
M M
M
M
M M
M
M
M
M
4
5
M
2
8 6
4 9
M
800
800
1000
1400
400
500
0
0
0
0
E
E
E
+M
+M
+M
+M +M
+M
+2
Ya que ij > XJ
0 i,jA Solución óptima
E E
E
EE
EE
E
E
E
P1
T1 T2 D1 D3D2
P2
T1
T2
D1
D2
B1
B2
B3
B4
B1 B2 800+B3900+B4
EJEMPLO DE TRANSBORDOSolución óptima del ejemplo de transbordo:
XJ = ( XP1T2, XP2T1, XP2T2, XT1T2, XT1D1,
XP1T2
XP2T1
XP2T2
XT1T2
XT2T2
XT2D2
XD1T2
= 1400
= 1000
= 800
= 0
= 400La solución no es única,
pues es una solución degenerada
XT2T2, XT2D2, XD1T2, XD2T2, XD2D3 )
XT1D1
XD2T2
XD2D3= 800 = 500
= 0
= 0
= 0
Z = (1000*4) + (800*2) + (400*5) + (800*8) + (1400*4) + (500*3) = 21.100 ($100)