Captulo 3: El problema de Hitchcock (Problema de Transporte) 3.1 Presentacin del Problema de Hitchcock o Problema de Transporte

3.2Formulacin Matemtica del Problema de Hitchcock

3.3Algoritmo de solucin

3.4 Ejemplo de un Problema de Hitchcock

3.1 Presentacin del Problema de HitchcockConsidrese una empresa que fabrica un cierto producto en varias plantas de suministro, y que debe satisfacer la demanda de distintas bodegas o depsitos por ese producto.O bien, considrese una ciudad o regin dividida en zonas: algunas que generan viajes y otras que atraen viajes. Problema: Cunto producto (viajes) despachar desde cada punto de oferta (planta de produccin o zona generadora de viajes) hasta cada punto de demanda (depsito o zona atractora de viajes) para satisfacer la demanda considerando las restricciones de produccin, y simultneamente minimizando los costos de transporte? Problema de Transporte Problema de Hitchocock Problema de Distribucin

3.2 Formulacin del Problema de HitchcockNotacin:Si: oferta de la planta i (Oi: viajes generados por la zona i)Dj: demanda de la bodega j (Dj: viajes atrados por la zona j)cij : costo de enviar una unidad de producto de la planta i hasta la bodega j (costo de viajar de la zona i a la zona j) xij : cantidad de producto enviado de la planta i a la bodega j (viajes de la zona i a la zona j)

m: nmero de plantas (nmero de zonas que originan viajes)n: nmero de bodegas (nmero de zonas que atraen viajes)

Formulacin Matemtica del Problema de Hitchcock problema de programacin lineal ? funcin objetivo y restricciones linealespero las solucin debe ser entera

Se puede demostrar que si Si y Dj son enteros i,j (y as es en la prctica) entonces la solucin ptima del problema anterior [3.1] - [3.4] es tambin entera

Luego, si Si y Dj son enteros positivos la restriccin [3.4] puede cambiarse por una nueva [3.5]: Ahora se tiene un PPL propiamente tal, con solucin entera (y se pueden usar las herramientas conocidas para resolver PPL)

Representacin de Redes S1S2SmS3- D1- D2- Dn- D3OfertaDemanda

Tabla del Problema de Hitchcock

bodegaplanta123n1c11x11c12x12c13x13.c1nx1n2c21x21c22x22c23x23.c2nx2nmcm1xm1cm2xm2cm3xm3.cmnxmn

Tabla Tecnolgica del Problema de Transporte

x11x12. x1nx21x22. x2nx31x32. x3nxm1xm2.xmn123..m1 1

1 1 1

.

1 1 1

..1 1 1 S1 S2 S3.. Sm123..n-1 -1 -1 -1-1 -1 -1 -1-1 -1 -1 -1-1 -1 -1 -1 -D1 -D2 -D3 . -Dnc11c12. c1nc21c22. c2nc31c32. c3ncm1cm2. cmn

Esta estructura especial del problema puede ser aprovechada antes de aplicar el mtodo SIMPLEX para PPL. Muchos problemas (no solo de transporte) presentan esta estructura

Por eso el problema de transporte es considerado un tipo especial (y de los ms importantes) de problema de programacin lineal

Consideracin Adicional:

Para que exista solucin factible debe cumplirse : En muchos problemas se puede esperar un exceso de oferta (no en el caso de viajes de personas) pero es conveniente suponer oferta igual a la demanda:

qu representa xi ?

Ahora se puede escribir el Problema de Transporte en forma estndar:[3.6][3.7][3.8][3.9]

Cmo resolver el problema [3.6]- [3.8]? Es inconveniente aplicar directamente el mtodo SIMPLEX: en aplicaciones reales el problema tiene grandes dimensiones. La estructura especial del problema, permite un mtodo de solucin ms prctico: La clave est en las relaciones de dualidad del problema

3.3 Algoritmo de SolucinEl algoritmo de solucin del Problema de Transporte est basado en el Teorema de la Complementaridad de las Holguras: Si xij* i,j satisfacen las restricciones del problema primal Si vi* y wj* i,j satisfacen las restricciones del problema dual Y Si xij* (vi* + wj* - cij) = 0 i,j Entonces xij* es la solucin ptima del Problema de TransporteLos mtodos de solucin del Problema de Transporte se basan en procedimientos iterativos. En cada iteracin se cumplen 2 de las 3 condiciones anteriores

Cuando se cumplen las 3 condiciones solucin ptima

Los distintos mtodos de solucin difieren respecto de cuales son las condiciones se cumplen en cada iteracin.

El procedimiento aqu descrito, supone que en cada iteracin se cumple:

Factibilidad del problema primalComplementaridad de las holguras y en el ptimo adems se cumple que:

Factibilidad del problema dual

El mtodo Simplex aplicado al Problema de Transporte utiliza varias consideraciones:

En el conjunto de m+n restricciones hay slo m+n-1 linealmente independientes. Una restriccin no lo es, pues por construccin:

Existen n x m variables En consecuencia, toda solucin factible tendr n+m-1 variables en la base, y el resto fuera de la base

Al partir de una solucin primal factible, se cumple la factibilidad del problema primal

Como adems en cada iteracin debe cumplirse la complementaridad de las holguras: xij (vi + wj - cij) = 0 i,j

entonces para las variables bsicas se cumplir: cij - vi - wj = 0

y para las variables no bsicas debe cumplirse: cij - vi - wj = ij

La diferencia ij representa la mejora potencial de la funcin objetivo si se introduce en la base la variable xij

Luego, si ij < 0, ello implica que xij debiera entrar en la base y disminuir el valor de la funcin objetivo.por qu es esto?

3.4 Construccin de una Solucin Inicial FactibleEl algoritmo de solucin del Problema de Transporte requiere partir de una solucin inicial factible. Existen varios procedimientos para obtenerla. A partir de la tabla Simplex que resume las capacidades de produccin de las plantas y los requerimientos de las bodegasSe debe hacer una asignacin (dar un valor a las variables xij) de manera de satisfacer las restricciones de produccin y demanda. Es decir, encontrar una solucin factible del problemaEl procedimiento utilizado debe determinar las m+n-1 variables bsicas incluidas en cualquier solucin factible.

La Regla de la Esquina Superior Izquierda establece el siguiente procedimiento para encontrar la solucin inicial: A partir de la tabla Simplex vaca (sin asignaciones) pero establecidos los requerimientos de produccin y demanda

Partir seleccionando x11 (esquina superior izquierda) como variable bsica, asignndole el mayor valor posible, dadas las restricciones de produccin de esa fila y los requerimientos de demanda de esa columna.

De ah en adelante, si xij fue la ltima variable bsica seleccionada, la siguiente eleccin ser x i, j+1 si quedan productos disponibles en la planta i. De lo contrario la siguiente variable bsica elegida ser la x i+1, j

x33= 8x23= 2x22= 2Ejemplo: Dado un problema de 3 plantas, 3 bodegas y las capacidades de produccin y requerimientos de demanda que se indican, encontrar una solucin inicial factiblex12= 2

Planta / bodega123Si142438Dj2410

3.5 Ejercicio NumricoSea un problema de 3 plantas y 3 bodegas y una solucin inicial factible para los requerimientos de produccin y demanda.

planta / bodega123Si1c11 = 5x11 = 2c12 = 3 x12 = 2c13 = 8-42c21 = 14-c22 = 4x22 = 2c23 = 5x23 = 243c31 = 4-c32 = 2-c33 = 8x33 = 88Dj2410

Iteracin 1Para las variables bsicas: vi + wj = cij v1 + w1 = 5v1 + w2 = 3v2 + w2 = 4v2 + w3 = 5v3 + w3 = 8Para las variables no bsicas: ij = - vi wj + cij13 = v1 w3 + c13 = + 4 8 + 8 = + 421 = v2 w1 + c21 = + 3 9 +14 = + 831 = v3 w1 + c31 = + 0 9 + 4 = - 532 = v3 w2 + c32 = + 0 7 + 2 = - 5

Planta / bodega123Si1c11 = 5x11 = 2c12 = 3 x12 = 2c13 = 8-42c21 = 14-c22 = 4x22 = 2c23 = 5x23 = 243c31 = 4-c32 = 2-c33 = 8x33 = 88Dj2410

Sale x22

P/B123Si1x11 = 2x12 = 2-42-x22 = 2x23 = 243--x33 = 88Dj2410

P/B123Si1x11 = 2x12 = 2-42--x23 = 443-x32 = 2x33 = 68Dj2410

Iteracin 2

P/B123Si1x11 = 2x12 = 2-42--x23 = 443-x32 = 2x33 = 68Dj2410

P/B123Si1x11 = 2-x13 = 242--x23 = 443-x32 = 4x33 = 48Dj2410

Iteracin 3

P/B123Si1x11 = 2-x13 = 242--x23 = 443-x32 = 4x33 = 48Dj2410

P/B123Si1--x13 = 442--x23 = 443x31 =2x32 = 4x33 = 28Dj2410

Iteracin 4

Anlisis de sensibilidadVariable no bsica : Cuanto debe variar el costo cij para que la variable xij contine siendo no bsica?

ij 0 cij vi + wj

Ejemplo en el ejercicio anterior c12 v1 + w2 = 0 +2 = 2Luego c12 debe tener un valor mnimo de 2

b)Variable bsica : Cuanto debe variar el costo cij para que la variable xij contine siendo bsica?

cij = vi + wj

Ejemplo en el ejercicio anterior c23 = c23 + x11 = v1 w1 + c11 = 0 4 + 5 = + 1 12 = v1 w2 + c12 = + 0 2 + 3 = + 121 = v2 w1 + c21 = 3-x 4 +14 = 13 -x 0 22 = v2 w2 + c22 = 3-x 2 + 4 = 5 -x 0

Ejercicio II. Considrese una empresa que fabrica 10.000 unidades de un cierto producto. Los compromisos de venta son de 3.000 unidades para el cliente 1 y 4.000 unidades para el cliente 2. Sin embargo, el cliente 1 est dispuesto a adquirir hasta 2.000 unidades adicionales y el cliente 2 el mximo posible de la produccin no comprometida. A la empresa le interesa colocar todos sus productos.

Sea cij el costo de transporte de una unidad de producto desde la planta i hasta el cliente j. Sea x1j el nmero de unidades desde la plata nica al cliente j. El envo al cliente 1 debe ser de un mnimo de 3.000 unidades y un mximo de 5.000 unidades. El envo al cliente 2 debe ser de un mnimo de 4.000 unidades y un mximo de 7.000 unidades. Cuantas unidades deben ser enviadas a cada cliente, de manera de cumplir los compromisos, minimizando los costos de transporte?

a) Formulacin como un Problema de Programacin LinealMinimizar c11x11 + c12x12

s.a.:

x11 + x12 = 10.000 (restriccin oferta)x11 3.000x11 5.000x12 4.000x11 7.000x1j 0

b) Formulacin como un Problema de Hitchcock Para formular el problema se puede desdoblar cada cliente en dos. Al cliente 1 se enviar la demanda comprometida mnima a la bodega I. Y se le enviar a la bodega ficticia II produccin no comprometida con un mximo de 2000 unidades. Al cliente 2 se enviar la demanda comprometida mnima a la bodega IV. Y se le enviar a la bodega ficticia III produccin no comprometida con un mximo de 3.000 unidades.Es necesario tambin crear una planta ficticia con una produccin de 2.000 unidades para satisfacer la restriccin

Esta produccin ficticia es la que se repartir entre las bodegas II y IV dado que en conjunto demandan 5.000 unidades y solo hay un remanente de 3.000 unidades no comprometidos.

12IIIIVIIIPlantaBodegasOfertas10.0002.0003.0002.0004.0003.000Demandas

Costos: c1 I = c11 c1 II = c11 c1 III = c12 c1 IV = c12 c2 I = c2 II = 0 c2 III = c2 IV = 0 Formulacin:

Min: c11 x1 I + c11 x1 II + c12 x1 III + c12 x1 IV + c2 I x2 I + c2 II x2 II + c2 III x2 III + c2 IV x2 IVs.a.x1 I + x1 II + x1 III + x1 IV = 10.000x2 I + x2 II + x2 III + x2 IV = 2.000 x1 I + x2 I = 3.000 x1 II + x2 II = 2.000x1 III + x2 III = 4.000 x1 IV + x2 IV =3.000 xij 0