Source: http://www.scribd.com/doc/17246047/VOGUEL-TRANSPORTE
Timestamp: 2015-10-06 21:11:32+00:00

Document:
P. 1VOGUEL TRANSPORTEVOGUEL TRANSPORTERatings: (0)|Views: 7,012|Likes: 68Published by faigtardMore info:Categories:Types, Business/Law, FinancePublished by: faigtard on Jul 10, 2009Copyright:Attribution Non-commercialAvailability:Read on Scribd mobile: iPhone, iPad and Android.download as PDF, TXT or read online from ScribdFlag for inappropriate content|Add to collectionSee moreSee lesshttps://www.scribd.com/doc/17246047/VOGUEL-TRANSPORTE07/03/2013pdftextoriginal V Congreso de Ingeniería de OrganizaciónValladolid-Burgos, 4-5 Septiembre 2003
Nuevos Algoritmos en el Problema de Transporte
, Germán Arana Landín
Doctor Ingeniero Industrial, Departamento Organización de Empresas. E.U.I.T.I.-San Sebastián-UPV. Correo-e: oeploruf@sc.ehu.es
Ingeniero de Organización Industrial, Departamento Organización de Empresas. E.U.I.T.I.-San Sebastián-UPV. Correo-e: oeparlag@sc.ehu.es
Una vez formulado el modelo matemático del problema de transporte, el siguiente paso esresolver el modelo, es decir, obtener los mejores valores numéricos para las variables de decisión. La forma en que se obtengan estos valores depende del tipo específico del modelo matemáticoutilizado. Por tanto, una vez definido el modelo, se podrá elegir un método apropiado pararesolverlo. En el problema de transporte, estos métodos pertenecen a una de estas dos categorías:
1.-Métodos óptimos
que permiten obtener los mejores valores para las variables de decisión, esdecir, aquellos valores que satisfacen simultáneamente todas las restricciones y proporcionan el mejor valor para la función objetivo.
2.-Métodos heurísticos,
que permiten obtener valores para las variables de decisión que satisfacen todas las restricciones. Aunque no necesariamente óptimos, estos valores proporcionanun valor aceptable para la función objetivo. En comparación con los métodos óptimos, los métodos heurísticos son computacionalmente máseficientes y, por tanto, se utilizan cuando la obtención de soluciones óptimas conlleva excesivotiempo o bien es imposible por ser el modelo matemático demasiado complejo. Este artículoaporta tres nuevos algoritmos para la obtención de soluciones iniciales, basados en los métodosheurísticos.
Programación Lineal. Problema del transporte. Algoritmo de Transporte. Métodosde obtención de una solución inicial. Algoritmo de optimización y mejora.
1. Introducción al problema de transporte
Una de las aplicaciones más interesantes de los problemas de programación lineal es elllamado problema de transporte, que resulta ser un modelo lineal que presenta una estructuraespecial. Este problema fue planteado y resuelto por F. L. Hitchcock[1] con anterioridad a laformulación del concepto general de la programación lineal, siendo debido a G. B. Dantzig[2]la aplicación de la programación lineal a la resolución del problema de transporte mediante elmétodo general del Simplex.Los métodos de resolución de este problema pertenece a la clase de los llamados modeloscombinatorios
que presentan una gran complejidad computacional y ofrecen un número muygrande de posibles soluciones, siendo por ello necesario buscar otro tipo de métodos desolución.
V Congreso de Ingeniería de OrganizaciónValladolid-Burgos, 4-5 Septiembre 2003
En consecuencia, los esfuerzos referentes a la búsqueda de métodos diferentes de resoluciónse han dirigido en un primer enfoque hacia los métodos que están basados en la utilización dealgoritmos matemáticos, es decir, que permiten obtener una solución óptima exacta
para el problema combinatorio, mediante la utilización de técnicas que permitan reducir la búsquedade soluciones (p.e. el método del Simplex, para la Programación Lineal).Alternativamente, se han propuesto determinados métodos heurísticos
que carecen de una base matemática formal y que están basados en la intuición. Sin embargo, permiten obtener una solución inicial próxima a la solución óptima con la ventaja de obtener ahorrosconsiderables en tiempo respecto a los métodos basados en algoritmos matemáticos, por loque estos últimos métodos no resultan ser apropiados para su utilización en problemas de grantamaño.Cada una de estas alternativas (métodos basados en algoritmos matemáticos y métodosheurísticos), presentan ventajas e inconvenientes. El presente artículo aporta tres nuevosmétodos para la resolución del problema de transporte basados en la segunda alternativa.Actualmente, el modelo de transporte presenta una gran variedad de aplicaciones en losdiferentes ámbitos de la empresa (comercial, industrial, etc.) que no tienen relación con eltransporte. Sin embargo, sigue hablándose del problema de transporte. Muchos problemaseconómicos que en principio nada tienen que ver con el problema de transporte, mediante lautilización de ciertas transformaciones pueden ser convertidos en un problema de transporte yen consecuencia, ser resueltos aplicando los métodos propios de este tipo de problemas.
El objetivo de los modelos
de transporte es encontrar la solución a un coste mínimo para larealización de un plan de envíos, transporte o distribución, desde cualquier grupo de centrosde abastecimiento llamados orígenes, a cualquier grupo de centros de
recepción llamadosdestinos, es decir, determinar la cantidad de productos o mercancías
que se deben enviar desde cada punto de origen a cada punto de destino, teniendo en cuenta las restricciones propias del problema referidas a las capacidades o disponibilidades
de los centros deabastecimiento y las demandas de los centros de destino, de manera que se minimicen loscostes totales de transporte o distribución. Los orígenes pueden ser fábricas, almacenes ocualquier punto o lugar desde el que se quiera enviar mercancías o productos. Los destinosson los puntos o lugares en donde se reciben dichas mercancías o productos.La resolución de este tipo de problemas se puede llevar a cabo utilizando el método delSimplex. Sin embargo, teniendo en cuenta la estructura especial del problema, se han propuesto algunos
métodos específicos de resolución,
que son más eficientes (en el tiempo),que la resolución a través del método del Simplex, basados en la la
forma matricial representando el problema del transporte mediante
tabla de transporte,
cuyo objetivo esresumir de manera conveniente todos los datos del problema en cuestión, para poder resolverlo mediante el llamado
3. Resolucion mediante el algoritmo de transporte
El proceso de resolución del problema de transporte se fundamenta en una serie dedefiniciones, propiedades y teoremas que posibilitan el posterior desarrollo de los resultados básicos obtenidos. Debido a las razones expuestas anteriormente con relación a la resolucióndel problema del transporte mediante la utilización del método del Simplex, se expone elmétodo de resolución que utiliza la forma matricial del citado problema mediante el algoritmode transporte
3.1 Algoritmo de transporte
El método general de resolución del problema de transporte consta de tres fases queconforman el denominado
Fase A.- Paso 1.
Escribir el problema de transporte en la forma matricial. Si el problema esno equilibrado, transformarlo en equilibrado. Ir al paso 2.
Fase B.- Paso 2.
Determinar una solución básica factible inicial. Ir al paso 3.
Fase C.- Paso 3.
Si la solución obtenida en el paso 2 es óptima, detener el proceso. En otrocaso, ir al paso 4.
Obtener una nueva solución que sea mejor que la anterior. Ir al paso3.
3.2 Determinación de una solución inicial
Dentro de la fase B, existen diferentes métodos para determinar una solución inicial entre losque cabe citar:-Northwest Corner Method o Método de la Esquina Noroeste (MEN)Inicialmente fue utilizado por G. B. Dantzig[2]. Es un método poco eficiente, ya que lassoluciones iniciales están alejadas de la solución óptima, y en general se necesitan bastantesiteraciones para alcanzar dicha solución debido a que en ninguna fase del proceso de búsqueda de una solución inicial factible se tiene en cuenta la información referente a loscostes unitarios de transporte y, por lo general, la solución obtenida difiere notablemente dela solución óptima.-Vogel’s Method o Método de Aproximación de Vogel (MAV)Este método requiere mayores esfuerzos de cálculos que el MEN; sin embargo, permiteobtener una solución inicial mejor que en el caso anterior puesto que tiene en cuenta lainformación de los costes de transporte, mediante los cálculos de las llamadas
penalizacionesde fila () y columna
, los cuales representan el posible coste de penalización que seobtendría por no asignar unidades a transportar a una determinada posición. Ha sido elmétodo más popular durante muchos años, en parte porque es relativamente fácil hacerlo amano. Este método también es denominado método de Balas-Hammer[4].
pf )(
Activity (61)FiltersAdd to collectionReviewAdd NoteLikeShowingAllMost RecentReviewsAll NotesLikesYou've already reviewed this. Edit your review.Post notePost reviewPost replyPost note and like1 hundred reads1 thousand readsRamon Angulo liked thisSanta Graciela Diaz Juarez liked thisMontesinos Claudia liked thisjaime andres mondragon liked thisAndrew Morales liked thisjoel_va1 liked thisRaul Cacacho liked thisMaria Belisa Arango Mena liked thisLoad more
More From This UserTaller Modelo Transporte[1]faigtardTaller Modelo Transporte[1]

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución