TAZ-TFG-2014-932


Problemas de transporte y problemas de transporte con carga fija

García Narváez, Manuel
Calvete Fernández, Herminia Inmaculada (dir.)

Universidad de Zaragoza, CIEN, 2014
Métodos Estadísticos department,

Graduado en Matemáticas

Abstract: Entre los problemas más interesantes en el campo de la Investigación Operativa, tanto por sus aplicaciones como por los retos teóricos que presentan, figuran los que aparecen en el diseño de redes de distribución. El problema de transporte y el problema de transporte con carga fija son problemas de programación lineal y programación lineal entera, respectivamente. Una de las razones que justifican el estudio individualizado de estos problemas es que tienen una estructura matemática especial que ha permitido diseñar métodos de resolución más eficientes que los que se aplican a los problemas de programación lineal. El objetivo de este trabajo es estudiar el problema de transporte y el problema de transporte con carga fija, demostrar sus propiedades más relevantes y presentar algunos de los algoritmos que se han propuesto para su resolución, además de mostrar algún caso particular del problema de transporte con carga fija. En el Capítulo 1 se estudia el problema de transporte. Tras formularlo matemáticamente, se demuestran algunos resultados basados en las propiedades de la matriz de coeficientes y se presenta un método de resolución basado en el conocido algoritmo simplex. En el Capítulo 2 se estudia el problema de transporte con carga fija. Se formula como un problema de programación entera con variables binarias y se demuestran algunas propiedades que permiten relacionar su solución con la solución del problema de transporte obtenido cuando se relajan las restricciones de integridad de las variables binarias. A continuación, se presentan algunos algoritmos propuestos en la literatura para resolver el problema basados en distintas reformulaciones del mismo. El Capítulo 2 termina con una revisión bibliográfica actualizada sobre el problema. En el Capítulo 3 se estudia algún caso particular del problema de transporte con carga fija y algunas propiedades adicionales. Por último, en el apéndice se proporcionan los resultados de un breve estudio computacional en el que se han resuelto, usando Lingo, algunos problemas de transporte con carga fija generados aleatoriamente. Among the most interesting problems in Operation Research field include the ones that appear in the distribution network design, both for their applications as for the theoretical challenges which show. These problems can include, among other variants, the transportation problem, the travelling salesman problem, the vehicle routing problem with one or more stores, and so on. The transportation problem and the fixed charge transportation problem are linear programming problems and integer linear programming problems, respectively, i.e. they are optimization problems which attempt to maximize (or minimize) a linear function, subject to some restrictions which are linear equations or inequalities and, in the integer programming case, they include integer variables. One of the reasons for the individual study of these problems is that they have a special mathematical structure which has let built more efficient resolution methods than those applied to linear programming. We have to note that the transportation problems have, in general, many variables and constraints, even in not particularly complex distribution systems. Moreover, both problems have applications in many fields, especially in the design of the distribution process in a supply chain. The aim of this project is to study the transportation problem and the fixed charge transportation problem, proving their most relevant properties and introducing some resolution algorithm. The transportation problem is studied in Chapter 1. After formulating it, some results based on the coefficient matrix properties are proved, and a resolution method based on simplex algorithm is introduced. The fixed charge transportation problem is studied in Chapter 2. It is formulated as an integer programming problem with binary variables, and some properties which let link its solution with the transportation problem solution obtained after relaxing the integer restrictions are proved. After that, some resolution algorithm based on different reformulations of the problem are shown. Chapter 2 is ended up with a current bibliographic review and some particular cases of the fixed charge transportation problem.


Free keyword(s): problema de transporte ; problema de transporte con carga fija
Tipo de Trabajo Académico: Trabajo Fin de Grado

Creative Commons License

El registro pertenece a las siguientes colecciones:
Academic Works > Trabajos Académicos por Centro > facultad-de-ciencias
Academic Works > End-of-grade works



Back to search

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)