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


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


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


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


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


- 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.

Documents

11 transporte