El método primal-dual en problemas de transporte generalizado no-estándar

Abstract

Los métodos de resolución del problema del transporte presentan una gran complejidad computacional y ofrecen un número muy grande de posibles soluciones, siendo por ello necesario buscar otro tipo de métodos de solución. Teniendo en cuenta esta necesidad y la estructura especial del problema se han propuesto algunos métodos de resolución más eficientes que se apoyan en la forma matricial del modelo matemático [1]. El presente proyecto va a basarse en la aplicación del método primal-dual en el problema del transporte generalizado no estándar mediante la programación de un código en Matlab. Primeramente, va a definirse el problema del transporte en su forma estándar y el concepto de dualidad. Después de esto, el siguiente punto se centrará en la definición y características del problema generalizado y su transformación a forma estándar. A continuación, llegará el grueso del proyecto consistente en la aplicación del método primal-dual al problema generalizado, desarrollándose en este apartado la formulación matemática del problema y el algoritmo de resolución de este. También se resolverán una serie de ejercicios, manualmente y a través de la implementación del código diseñado, ejemplificando las diferentes variaciones del problema que pueden darse en función de los signos que presenten las restricciones de oferta y demanda. Finalmente, el documento llegará a su fin con una sección en la que se dará una explicación detallada del funcionamiento del código en Matlab y una descripción de las variables y parámetros de que consta.

The methods for solving the transport problem are computationally very complex and offer a very large number of possible solutions, making it necessary to look for other types of solution methods. Taking into account this need and the special structure of the problem, some more efficient solution methods have been proposed that rely on the matrix form of the mathematical model [1]. The present project will be based on the application of the primal-dual method to the non-standard generalised transport problem by programming a code in Matlab. First, the transport problem in its standard form and the concept of duality will be defined. After this, the next point will focus on the definition and characteristics of the generalised problem and its transformation to standard form. This will be followed by the bulk of the project consisting of the application of the primal-dual method to the generalised problem, developing in this section the mathematical formulation of the problem and the algorithm for solving it. A series of exercises will also be solved, manually and through the implementation of the designed code, exemplifying the different variations of the problem that may occur depending on the signs of the supply and demand restrictions. Finally, the document will end with a section in which a detailed explanation of the operation of the Matlab code and a description of its variables and parameters will be given.