TeoraEl Problema de transporteUn tipo especial de problemas, es el llamado problema de transporte, en el que se presenta la situacin de quehay que llevar cierta cantidad de elementos ( productos, personas,etc.,) de uno o varios lugares que se conocerncomo orgenes, a otro u otros lugares que llamaremos destinos, en los cuales, se requieren dichos elementos.Como hay un costo unitario de transportacin de cada orgen a cada destino, el objetivo del problemaes minimizar el costo total de transportacin.Entonces si en el i-simo orgen hay una oferta de elementos denotada por ai, para llevar al j-simo destinodonde se requiere satisfacer una demanda denotada por bj, entonces la variable xij seala el nmero de unidadesa transportar del orgen i al destino j, con un costo unitario cij, y de este modo el modelo de PL viene dado por:Sin embargo dadas las caractersticas de este modelo, se creo un algoritmo llamado precisamenteel "algoritmo de transporte", que simplifica el hallazgo de los resultados ptimos ( si estos existen), y queadems permiten resolver otros problemas derivados de problema original de transporte.Este algoritmo en primer lugar seala que la informacin del problema se puede representar en una matrizcomo la que se describe a continuacin:Con este arreglo matricial es posible aplicar un conjunto de mtodos que permiten obtener en 1a. Instanciasoluciones bsicas, y posteriormente soluciones ptimas. Los mtodos se agrupan en dos categoras que sonlos mtodos de aproximacin, entre los cuales se mencionan:a) Mtodo de la esquina noroccidental.b) Mtodo de costo mnimo.c) Mtodo de aproximacin Vogel (MAV)y los mtodos de optimizacin entre los cuales se mencionan:a) Mtodo del banquillo.b) Mtodo de multiplicadores.En todos los mtodos antes de empezar a aplicarlos, primero se debe checar la condicin de equilibrioes decir, que la suma de toda la oferta sea igual a la suma de toda la demanda.De no cumplirse esta condicin ser necesario agregar a la matriz un fila o columna (segn sea el caso) con la oferta o demanda faltante,pero con costos unitarios de transportacin igual a cero.

x11c11x21c21x12c12x22c22x2nc2nx1nc1nxmncmnxm2cm2xm1cm1O 1RG 2E N .E S .

m1 2 . . . na1

a2

...

amb1 b2 . . . bn

Esquina NoroccidentalMTODO DE LA ESQUINA NOROCCIDENTALEste mtodo es el ms sencillo de aplicar y por lo tanto tambin es el menos eficiente ya que aunqueproporciona un asolucin bsica incial, esta, se encuentra muy alejada de la sdolucin ptima y por lo tantoimplica trabajar ms en la bsqueda de la solucin ptima.Se aplica del modo siguiente:1) Recolectar los datos del problema.2) Checar la condicin de equilibrio. De no existir utilizar lo ya mencionado con anterioridad.3) hacer el arreglo matricial.4) A la casilla noroccidental de la matriz asignar el mayor nmero de unidades posible de acuerdo a lasiguiente condicin min[ai,bj]5) Ajustar la oferta o la demanda de la fila o columna que no haya quedado satisfecha. Si ambas fila ycolumna quedaron satisfechas, ajustar la oferta o la demanda de cualquiera de ellas a cero, el cultambin es asignable.6) repetir el procedimiento anterior en la casilla contigua de la fila o columna que no haya quedado satisfecha.7) Continuar con el procedimiento hasta que queden satisfechas todas las filas y columnas de la matriz8) El costo total de trasportacin se obtiene multiplicando el nmero de unidades asignadas a cada casilla conel costo unitario respectivo y luego sumando los productos.NOTA: Las casillas con asignacin se llamaran variables bsicas y las casillas vacas variables no bsicas.El nmero de variables bsicas de una solucin debe ser igual a m + n - 1.Ejemplo.- Una compaa tiene tres fbricas ubicadas en D.F., Monterrey y Guadalajara, en las cualesla produccin diaria de cierto producto es de 15, 25 y 5 unidades respectivamente. Dicho producto se vende en cuatropickup centers ubicados en guadalajara , D.F., Puebla y Veracrz, en los cuales la demanda del producto es de 5, 15,15 y 10 unidades respectivamente.Los costos unitarios de transportacin de cada fbrica a cada pickup center se da en la matriz siguiente:Pickup CenterFbricaGuadalajaraD.F.PueblaVeracrzD.F.1002011Monterrey127920Guadalaja.0141618Cuantas unidades hay que transportar de cada fbrica a cada pickup center de modo que se minimice el costo totalde transportacin?TotalOFERTA =1525545TotalDEMANDA=515151045m =3filasEl problema esta balanceado.n =4columnasGuad,D.F.PueblaVeracrzOferta1002011D.F.5101510127920Mty.5155252050141618Guad.55Demanda5151510Variables bsicas5x11x12Costo total de transportacin =410pesosx22Nmero de asignaciones =m +n - 1 =6x23x24x34Min f(x) = 10x11 + 0x12 + 20x13 + 11x14 + 12x21 + 7x22 + 9x23 + 20x24 + 0x31 + 14x32 + 16x33 + 18x34sujeta a x11 + x12 + x13 + x14 = 15x21 + x22 + x23 + x24 = 25x31 + x32 + x33 + x34 = 5x11 + x21 + x31 = 5x12 + x22 + x32 = 15x13 + x23 + x33 = 15x14 + x24 + x34 = 10xij 0

Costo MnimoMtodo de Costo Mnimo.Este mtodo es ms eficiente que el anterior y se aplica del modo siguiente:1) Recolectar los datos del problema.2) Checar la condicin de equilibrio. De no existir utilizar lo ya mencionado con anterioridad.3) hacer el arreglo matricial.4) a la casilla de la matriz con el costo unitario ms pequeo asignar el mayor nmero de unidades posible partiendo de la condicinde min(ai,bj), en caso de empate romper arbitrariamente.5) Tachar en la matriz la fila o columna que haya quedado satisfecha y ajustar la oferta o la demanda segn sea el caso a la otra. So ambasfila y columna quedan satisfechas solamente se tacha una, y a la otra se le ajusta su oferta o demanda a cero el cul tambin es asignable.6) Repetir lo anterior hasta que solamente quede una fila o columna de la matriz sin tachar a la cual se le asignaran las ofertas o demandasrestantes.7) El costo total de trasportacin se obtiene multiplicando el nmero de unidades asignadas a cada casilla conel costo unitario respectivo y luego sumando los productos.NOTA: Las casillas con asignacin se llamaran variables bsicas y las casillas vacas variables no bsicas.El nmero de variables bsicas de una solucin debe ser igual a m + n - 1.m =3Utilizar el mismo ejercicio del mtodo anterior.n =4Guad,D.F.PueblaVeracrzOferta1002011D.F.150150127920Mty.151025100141618Guad.5050Demanda5151510Costo total de transportacin =335pesosNmero de asignaciones =m +n - 1 =6

MAVMtodo de aproximacin Vogel (MAV)Este mtodo tambin llamado de penalizacin, es el mtodo ms eficiente de los de aproximacin, ya que la solucin obtenida se aproximabastante a la solucin ptime e incluso en algunas ocasiones se obtiene dicha solucin ptima.Se aplica del modo siguiente:1) Recolectar los datos del problema.2) Checar la condicin de equilibrio. De no existir utilizar lo ya mencionado con anterioridad.3) hacer el arreglo matricial.4) Por cada columna y cada fila de la matriz generar una penalizacin, la cual se obtiene sacando la diferencia entre el costo unitario mspequeo de la fila o columna y el que le sigue en valor.5) A la fila o columna con la penalizacin ms grande se elige para hacer la asignacin, la cual se debe dar a la casilla con el costounitario ms pequeo de dicha fila o columna( en caso de empate elegir arbitrariamente), en caso de empate elegir arbitrariamente.asignando el mayor nmero de unidades posible con el criterio de Min(ai,bj).6) Con lo anterior queda satisfecha la fila o columna la cual debe tacharse en la matriz. Si ambas quedan satisfechas solamente tache unay a la otra se la ajusta su oferta o demanda a cero segn sea el caso.7) Repetir el proceso anterior para las siguientes asignaciones, hasta que solamente quede una fila o columna sin tachar a la cual se leasignaran las ofertas o demandas restantes.8) El costo total de trasportacin se obtiene multiplicando el nmero de unidades asignadas a cada casilla conel costo unitario respectivo y luego sumando los productos.NOTA: Las casillas con asignacin se llamaran variables bsicas y las casillas vacas variables no bsicas.El nmero de variables bsicas de una solucin debe ser igual a m + n - 1.Utilizar el mismo ejercicio del mtodo anterior.Guad,D.F.PueblaVeracrzOfertap1p2p3p4100201110119D.F.150(15-0)1279202211Mty.1510(25-10)01416181422Guad.50(5-0)Demanda5151510p110777p2777p377p4m =3Costo total de transportacin =335pesosn =4Nmero de asignaciones =m +n - 1 =6

banquilloMTODO DE OPTIMIZACIN DEL BANQUILLO ( STEPPING STONE)Este mtodo es de tipo grfico y consiste en lo siguiente:1.- Inicie con una solucin bsica proporcionada por algno de los mtodos de aproximacin.2.- Por cada variable no bsica de la solucin construya un circuito con las siguientes caractersticas:a) El circuito es cerrado, empieza y termina en la casilla de la variable no bsica seleccionada.b) Se construye con segmentos verticales y horizontales.c) las esquinas del circuito deben ser casillas de variables bsicas.( excepto la casilla de inicio).d) el circuito es nico.3.- Poner a cada esquina del circuito un signo mas o signo menos en forma alternada, empezando conel signo ms a la casilla de la variable no bsica seleccionada.4.- Sumar algebricamente los costos unitarios de las esquinas del circuito.5.- El circuito con el costo ms negativo indica que variable no bsica se selecciona comovariable de entrada. Si hay empate romper arbitrariamente.NOTA: Si todos los circuitos tienen costo positivo o cero, no hay variable de entrada y porlo tanto, la solucin actual se puede considerar como la ptima.6.- Para elegir la variable de salida, se observa el circuito de la variable de entrada, y las esquinasque les haya tocado signo menos son las candidatas a salir, y de estas se elige la que tenga elmenor nmero de unidades asignadas. En caso de empate romper arbitrariamente.7.- Una vez seleccionadas las variables de entrada y salida, para generar una nueva solucin,se procede del modos siguiente:a) Asignar las unidades de la variable de salida a la variable de entrada.b) A las dems esquinas del circuito sumar o restar ese mismo nmero de unidadesdependiendo del signo que les haya tocado.8.- Checar que la nueva solucin no viole demandas u ofertas.9.- Calcular el nuevo costo total de transporte.10.- Repetir los pasos anteriores tantas veces como sea necesario hasta que ya nohaya variable de entrada, en cuyo caso la ltima solucin obtenida se considerarcomo la ptima.ejemplo.- Tomando la solucin bsica proporcionada por el MAV se tiene:X115x115Guad,D.F.PueblaVeracrzOfertaGuad,D.F.PueblaVeracrzOferta(+)10(-)02011(+)1002011D.F.1515D.F.5(-)1015(-)127920(-)127920Mty.00(+)151025Mty.010(+)152501416180141618Guad.55Guad.55Demanda5151510Demanda5151510x1318Guad,D.F.PueblaVeracrzOfertax131810(-)0(+)2011Guad,D.F.PueblaVeracrzOfertaD.F.151510(-)0201112(+)7920D.F.5(+)1015Mty.0015(-)102512(+)79200141618Mty.01015(-)25Guad.550141618Demanda5151510Guad.55Demanda5151510x14-2Guad,D.F.PueblaVeracrzOfertacosto =x24210(-)020(+)11Guad,D.F.PueblaVeracrzOfertaD.F.151510(+)020(-)1112(+)7920D.F.51015Mty.0101510(-)2512(-)79200141618Mty.01015(+)25Guad.550141618Demanda5151510Guad.55Demanda5151510x3219Guad,D.F.PueblaVeracrzOfertax32191002011Guad,D.F.PueblaVeracrzOfertaD.F.15151002011(+)127920D.F.51015Mty.00(-)151025(+)127920(-)0141618Mty.010(-)1525Guad.5(+)5(-)0141618Demanda5151510Guad.5(+)5Demanda5151510x3319Guad,D.F.PueblaVeracrzOfertax33211002011Guad,D.F.PueblaVeracrzOfertaD.F.15151002011(+)127920D.F.51015Mty.0015(-)1025(+)127(-)920(-)0141618Mty.0101525Guad.5(+)5(-)0141618Demanda5151510Guad.5(+)5Demanda5151510x3410Guad,D.F.PueblaVeracrzOfertax34121002011Guad,D.F.PueblaVeracrzOfertaD.F.151510(+)02011(+)1279(-)20D.F.510(-)15Mty.00151025(+)127920(-)0141618Mty.010(-)1525Guad.5(+)50141618Demanda5151510Guad.5(-)(+)5Demanda5151510x14-2Guad,D.F.PueblaVeracrzOferta1002011D.F.51015127920Mty.01015250141618Guad.55Demanda5151510nueva variable bsica x14nueva variable no bsica x24costo total =315

vv

MultiplicadoresMtodo de MultiplicadoresEste mtodo de optimizacin se basa en las relaciones de costos entre las casillas.Se aplica del modo siguiente:a) Elegir una solucin bsica inicial proporcionada por alguno de los mtodos de aproximacin.b) Por cada fila de la matriz generar un multiplicador ui y por cada columna de la matriz generar un multiplicador vj, para lo cual seutiliza la siguiente relacin ui + vj = cij, por cada variable bsica de la matriz.c) Evaluar el costo para cada variable no b sica de la matriz con la siguiente relacin cij -ui - vj.d) La variable no bsica con el costo evaluado ms negativo se elige como variable de entrada (en caso de empate elegir arbitrariamente).e) para elegir la variable de salida, cosntruir un circuito para la variable de entrada del modo siguiente;1) El circuito empieza y termina en la casilla de la variable de entrada.2) Se deben utilizar segmentos horizontales y verticales solamente.3) En las esquinas del circuito debe haber variables bsicas.4) El circuito es nico y adems cerrado.f) Poner signos ms y menos a las esquinas del circuito comenzando con el signo ms en la casilla de la variable de entrada y luego menos y msalternadamente a las otras casillas.g) las casillas con signo menos son las candidatas a salir y de estas se elige la que tenga el menor nmero de unidades asignadas. En caso deempate romper arbitrariamente.h) A la variable de entrada asignarle las unidades de la variable de salida, y para equilibrar el problema, ese mismo nmero de unidadessumarla o restarla a las otras casillas del circuito de acuerdo al signo que les haya tocado.i) Repetir el procedimiento anterior tantas veces como sea necesario hasta que ya no haya variable de entrada.j) El costo total de trasportacin se obtiene multiplicando el nmero de unidades asignadas a cada casilla conel costo unitario respectivo y luego sumando los productos.v1=2v2=7v 3=9v4=20Guad,D.F.PueblaVeracrzOferta1002011u1 =-7D.F.1515127920u2 =0Mty.01510250141618u3 =-2Guad.505costo total335Demanda5151510Variables bsicasuivjcijui+vj=cijvalorVariables No bsicascij-ui-vjvalorx12u1v2c12u1+7=0u1 = -7x11c11-u1-v115x22u2v2c220+v2=7v2 = 7x13c13-u1-v311x23u2v3c230+v3=9v3 = 9x14c14-u1-v4-2x24u2v4c240+v4=20v4 = 20x21c21-u2-v110x31u3v1c31( -2 + v1 = 0)v1 = 2x32c32-u3-v29x34u3v4c34u3+20=18u3= -2x33c33-u3-v49Variable de salidav1=-6v2=1v 3=3v4=-6Guad,D.F.PueblaVeracrzOferta1002011u1 =-1D.F.51015127920u2 =6Mty.1015250141618u3 =6Guad.505costo total315Demanda5151510Variables bsicasuivjcijui+vj=cijvalorVariables No bsicascij-ui-vjvalorx12u1v2c12u1+1=0u1=-1x11c11-u1-v117x22u2v2c22u2+1=7u2=6x13c13-u1-v318x23u2v3c236+v3=9v3=3x14c24-u1-v420x24u2v4c14(-1+v4=11)v4=-6x21c21-u2-v112x31u3v1c316+v1=0v1=-6x32c32-u3-v27x34u3v4c34u3+12=18u3=6x33c33-u3-v47

VARIABLE DE ENTRADAVARIABLE DE SALIDA

M.H.AMTODO HUNGARO DE ASIGNACINUna variante del problema de transporte, es el llamado problema de asignacin en el cual se presentan "m"trabajos, productos,etc., que se puede realizar en "n" talleres, mquinas o personas,etc., de tal modo querealizar el i-simo trabajo en la j-sima mquina lleva un tiempo tij o un costo cij. Entonces el objetivoes Minimizar el tiempo o el costo de realizacin de los trabajos en las mquinas.La informacin se vierte en la misma forma que en el problema de transporte, es decir, en una matrizen la que cada casilla representa una variable y en los recuadros de cada casilla se pone el tiempo o el costounitario.Ahora bin, la forma de aplicar el mtodo que permite resolver este tipo de problemas que se conoce comoel mtodo hungaro de asignacin, es la siguiente:a) Checar que el problema este balanceado, es decir, que el nmero de trabajos "m" sea igual al nmerode mquinas "n". De no ser as, el problema se balancea agregando un trabajo o una mquina ficticiasegn sea el caso, con tiempo o costos unitarios igual a cero.b) Construir la matriz.c) Restar el elemento de costo unitario ms pequeo de cada fila de los elementos de su misma filaincluyendo dicho elemento.d) En la matriz resultante del paso anterior, restar el elemento de costo unitario ms pequeo de cadacolumna, de los elementos de su misma columna incluyendo dicho elemento.e) Trazar el mnimo nmero de lneas horizontales y/o verticales que atraviesen los ceros de la matrizobtenida en el paso anterior ( no son vlidas las lneas diagonales).f) Si el nmero de lneas trazadas es igual al nmero de mquinas del problema, entonces la solucinptima se obtiene a partir de los ceros de la ltima matriz obtenida, de lo contrario continuar con losdems pasos.g) Restar el elemento de costo ms pequeo de la matriz que no haya sido cruzado por lnea algunaa los elementos de costo de la matriz que no hayan sido cruzados por lnea algunay sumarlo a aquellos elementos de costo que hayan quedado en la interseccin de doslneas.h) Repetir los ltimos tres pasos anteriores tantas veces como sea necesario hasta queel nmero de lneas trazadas sea igual al nmero de mquinas para obtener la solucin ptima.i) Calcular el tiempo total o el costo total sumando los tiempos o costos unitarios de las casillasasignadas.Ejemplo.- En una compaa llegaron pedidos de los productos A,B,C y D, los cuales dadas suscaractersticas se pueden fabricar en cualesquiera de 4 mquinas denotadas porM1, M2, M3 y M4. Los costos unitarios de fabricacin de cada producto en cada mquina se danen la matriz siguiente:QUE PRODUCTO HAY QUE ASIGNAR A CADA MQUINA PARA MINIMIZAR EL COSTO TOTAL DE FABRICACIN?MQUINASMQUINASA1463AB97109BC45117CD8785DMQUINASMQUINASAABBCCDDASIGNACIONESMQUINASPRODUCTO A MQUINAABCDCosto total =pesos

MBD0000929F.unknown

MBD0003088B.unknown