Download - 11 transporte
El Problema de Transporte
IO1 R.Delgadillo 2
El Problema de TransporteTópicos
Definición
Formulación
Casos que se presentan
Cuadro de Transporte
Algoritmo de transporte
Métodos de búsqueda de la solución básica inicial
IO1 R.Delgadillo 3
Definición
1
i
m
1
j
n
Origenes Destinos
a1
ai
am
b1
bj
bnDemandaOferta
c11 x11
cij xij
IO1 R.Delgadillo 4
Formulación PT
0
1,...,
,...,1
z
ij
m
ijij
n
jiij
jijij
i
x
njbx
miax
xcmin
IO1 R.Delgadillo 5
Formulación PT
xij = número de articulos enviados del origen i al destino j
El objetivo es de minimizar los costos de envios
Las primeras m restricciones dicen que no se puede enviar mas de lo disponible
las n siguientes restricciones dicen que cuando menos debe llegar lo requerido
IO1 R.Delgadillo 6
Formulación PT
Una condición necesaria y suficiente para que el problema de transporte tenga solución es que se cumpla que la oferta total sea igual que la demanda total
i jji ba
IO1 R.Delgadillo 7
Casos que se presentan Oferta = demanda
=> Forma normal del PT.
0
n 1,...,
,...,1
z
ij
m
ijij
n
jiij
jijij
i
x
jbx
miax
xcmin
IO1 R.Delgadillo 8
Casos que se presentan Oferta > demanda
=> generar destino ficticio n+1
tal que:
nota: Si
Cantidad no enviada desde el origen i a los destinos (de 1 a n)
jj
iin bab 1
01,nix
1,nix
01,nic
IO1 R.Delgadillo 9
Casos que se presentanObservación: Debemos de colocar toda la oferta a destinos (1,..,n)
una forma es asignarle un costo bastante alto
de esta forma
Lo que implica que se envia a los destinos (1,..,n)
0 1,nix
1,nic
IO1 R.Delgadillo 10
Casos que se presentan Oferta < demanda
=> generar origen ficticio n+1
tal que:
nota: Si
demanda insatisfecha del destino j
Obs: Igual asignaremos un costo alto a
ii
jjn aba 1
0,1 jmx
jmx ,1
0,1 jmc
jmc ,1
IO1 R.Delgadillo 11
Cuadro de transporte
1
i
m
1 j n
c11
cij
cmn
Ofert
Dem
a1
ai
am
b1 bj bn
Destin
origen
Demof
IO1 R.Delgadillo 12
Cuadro de transporte
Una Solución para el PT es dado en un cuadro de transporte :
Debe cumplir con las restricciones por igualdad
todos sus valores deben ser no negativos
debe tener (m+n-1) VB. Las VNB tienen valor cero
No formar ciclo
IO1 R.Delgadillo 13
Cuadro de transporte
Conceptos:
Celda básica: Es c/u de las celdas asociadas a una variable básica.
Arco básico: Es un segmento vertical o horizontal que une dos celdas básicas
Ciclo : Se dice que existe un ciclo cuando existe un conjunto de distintos arcos básicos que unen a una celda consigo mismo
IO1 R.Delgadillo 14
Cuadro de Transportes
Ejemplo:
*
* *
* *
*
Celda
Arco ciclo
* es posición
de una VB
* * *
*
IO1 R.Delgadillo 15
Algoritmo de TransporteEs el método simplex particularizado para el formato del cuadro.
Los pasos a seguir son:
1.-Determinación de una solución inicial básica factible
2.-prueba de la solución respecto de la condición de optimalidad
3.-mejora de la solución cuando no es óptima
4.-repetir los pasos 2 y 3 hasta obtener solución óptima
IO1 R.Delgadillo 16
Métodos de búsqueda de la solución básica inicial
Método de la esquina Nor-oeste
Método de Costo mínimo
Método Vogel
IO1 R.Delgadillo 17
Método de la esquina Nor-oeste
Chequear oferta = demanda
Asignar lo máximo posible (unidades) a la esquina nor-oeste del cuadro de envios que quede
IO1 R.Delgadillo 18
Método de Costo mínimoMétodo:
1.-Escoger el mínimo elemento del cuadro de costos
2.-Asigna a esta celda el maximo posible de unidades en el cuadro de envios
3.-Eliminase la fila o columna correspondiente a la oferta o demanda satisfecha
4.-Con la nueva matriz repetir los 1,2 y 3 hasta que las demandas sean satisfechas
IO1 R.Delgadillo 19
Método de VogelMétodo:
1.-Calcule una penalidad para cada fila y columna, como la diferencia entre los costos mas pequeños
2.-Seleccione la fila o columna con la penalidad mas grande
3.- Seleccione de esta fila o columna la celda de menor costo
4.- Asigna a esta celda el máximo posible de unidades en el cuadro de envíos
3.-Eliminase la fila o columna correspondiente a la oferta o demanda satisfecha
4.-Con la nueva matriz repetir los 1,2,3 y 4 hasta que las demandas sean satisfechas
IO1 R.Delgadillo 20
Determinación de la condición de optimalidad
La FO del problema de transporte puede ser escrito
Al multiplicarse las restricciones de las ofertas por
las restricciones de las demandas por , y sumar las restricciones a la FO
Obs:En toda base posible las VB deben tener coeficiente cero en la F.O.
Así:
ijjiijj
jjii
i xvucbvau )(z
0jiij vuc
iu
jv
IO1 R.Delgadillo 21
Determinación de la condición de optimalidad
De donde
Para las VB
=> para resolver el nuevo sistema de ecuaciones (# de incognitas = m+n,
# de ecc = m+n-1)
se da un valor a una de las incognitas (ej. U1=0) y se resuelve el sistema restante.
jiij vuc
IO1 R.Delgadillo 22
Determinación de la condición de optimalidad
Condición de óptimalidad:
Para todas las VNB
Si no se cumple la condición:
Variable que entra: El más negativo
Varible que sale:
Se fija un valor a la variable que entra y se construye con las variables existentes un ciclo, Asignando alternativamente los valores
0jiij vuc
IO1 R.Delgadillo 23
Determinación de la condición de optimalidad
- y a las celdas que se encuentran en las esquinas de dicho ciclo de forma que las condiciones sean mantenidas.
Se analiza cuál es el máximo valor que puede tomar sin hacer negativa ninguna de las asignaciones, la variable que se hace cero es la correspondiente a la variable que sale.