Repositorio Institucional de Documentos

Problemas de transporte y problemas de transporte con carga fija Manuel García Narváez Trabajo de fin del grado en Matemáticas Universidad de Zaragoza Introducción 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. Estos problemas pueden incluir, entre otras variantes, el problema de transporte, el problema del viajante, el problema de rutas de vehículos con uno o varios almacenes, los problemas de localización de infraestructuras con y sin problemas de rutas asociados, etc. El problema de transporte y el problema de transporte con carga fija son problemas de programación lineal y programación lineal entera, respectivamente, es decir, son problemas de optimización en los que se trata de maximizar (o minimizar) una función lineal, sujetos a unas determinadas restricciones que son ecuaciones o inecuaciones lineales que, además, en el caso de programación entera, incluyen variables que han de ser enteras. 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. Hay que tener en cuenta que los problemas de transporte tienen, en general, un gran número de variables y restricciones incluso en sistemas de distribución no especialmente complejos. Además, ambos problemas tienen aplicaciones en muchos campos, siendo especialmente importantes en el diseño del proceso de distribución en una cadena de suministro. 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. Este trabajo consta de tres capítulos. 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 2termina 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. III Índice general Introducción III 1. El problema de transporte 1 1.1. Planteamiento ...................................... 1 1.1.1. Formulación .................................. 1 1.1.2. Problema de transporte no balanceado ..................... 4 1.1.3. Propiedades de la matriz de coeficientes .................... 4 1.2. Algoritmo simplex para el problema de transporte ................... 6 1.2.1. Construcción de una solución inicial ...................... 7 1.2.2. Cálculo de los costes marginales de la solución ................ 8 1.2.3. Construcción de una nueva solución ...................... 8 2. El problema de transporte con carga fija 9 2.1. Introducción ....................................... 9 2.2. Formulación ....................................... 9 2.3. El problema de programación lineal con carga fija ................... 10 2.4. Un método aproximado de resolución ......................... 12 2.5. Evaluación del método aproximado de Balinski .................... 14 2.6. Un algoritmo basado en el procedimiento de Benders ................. 15 2.7. Un algoritmo basado en fijar las variables binarias ................... 18 2.8. Revisión bibliográfica actualizada ........................... 20 3. Casos particulares y propiedades del problema de transporte con carga fija 21 3.1. El problema de transporte con carga fija puro ..................... 21 3.2. El problema de asignación de profesores ........................ 23 3.3. La paradoja de más por menos ............................. 26 A. Resultados computacionales 29 Bibliografía 31 V Capítulo 1 El problema de transporte 1.1. Planteamiento El problema de transporte fue formulado tal y como lo conocemos en 1941 por el matemático americano Frank Lauren Hitchcock en su artículo "The distribution of a product from several sources to numerous localities", por lo que otro nombre que se le da es problema de Hitchcock. Sin embargo, sobre 1939, Leonid Kantorovich ya había mostrado diversas aplicaciones de problemas muy relacionados con el problema de transporte, además de formular el problema de transporte en forma continua. También trabajó en el problema, de manera independiente, Tjalling Koopmans, dado que trabajaba en el transporte de mercancías durante la Segunda Guerra Mundial, y quería reducir costes de transporte. No fue hasta 1951 cuando George Dantzig adaptó el método simplex que él mismo había creado para resolver el problema de transporte de una manera eficiente que perdura en la actualidad. 1.1.1. Formulación Consideramos morígenes (lugares que ofrecen un determinado producto), que denotamos Oi, i=1,...,m. Cada origen Oitiene una oferta de siunidades de dicho producto. Consideramos ndestinos (lugares que demandan el producto), que denotamos Dj,j=1,...,n. Cada destino Djtiene una demanda de djunidades del producto. Podemos suponer que si,dj>0 (si no, se deja de considerar el origen o destino correspondiente). También supondremos que el problema está balanceado, es decir, la oferta total es igual a la demanda total: m ∑ i=1si=n ∑ j=1dj Sea ci j el coste por unidad de producto enviada desde Oihasta Dj. En general, ci j >0, aunque podría ser ci j ≤0 si, por ejemplo, se quiere incentivar el uso de la ruta desde ihasta j. El problema de transporte tiene por objetivo determinar cómo debe realizarse la distribución de producto de manera que minimice el coste total asociado a enviar el producto desde los orígenes hasta los destinos. Si denotamos xi j a las unidades de producto enviadas desde Oihasta Dj, el problema de transporte se puede formular de la siguiente forma: 1 2Capítulo 1. El problema de transporte Minimizar m ∑ i=1 n ∑ j=1ci jxi j sujeto a x11 +···+x1n=s1 x21 +···+x2n=s2 ... xm1+···+xmn =sm x11 +x21 +... +xm1=d1 ......... x1n+x2n+... +xmn =dn xi j ≥0,i=1,...,m,j=1,...,n o, en forma abreviada: Minimizar m ∑ i=1 n ∑ j=1ci jxi j sujeto a n ∑ j=1xi j =si,i=1,...,m (oferta de Oi) m ∑ i=1xi j =dj,j=1,...,n (demanda de Dj) xi j ≥0,∀(i,j)(no negatividad) El problema de transporte es un problema de optimización lineal y, por lo tanto, puede resolverse con los algoritmos que se han desarrollado para este tipo de problema (algoritmo simplex [7,10,20], punto interior, etc). No obstante, las características del problema de transporte que estudiaremos a continuación han permitido adaptar el algoritmo simplex para hacerlo más eficiente. Como se puede observar, el problema tiene m×nvariables (xi j) y m+nrestricciones (excluyendo las de no negatividad). Cada variable aparece solamente dos veces en las restricciones (una en la restricción de oferta y otra en la de demanda), ambas con coeficiente 1. Esta propiedad tendrá gran importancia en el desarrollo de un algoritmo eficiente para la resolución del problema. Figura 1.1: Grafo de un problema de transporte Problemas de transporte y problemas de transporte con carga fija 1.1. Planteamiento 3 El grafo del problema de transporte (formado por los orígenes, los destinos y sus conexiones) es bipartito y completo; esto es, los nodos (orígenes y destinos) forman dos conjuntos tales que todas las conexiones van de un conjunto al otro; y además todas las conexiones (entre orígenes y destinos) son posibles. En la Figura 1.1 se muestra este grafo. Si una determinada conexión no existiera en el sistema real modelado, para plantear el problema se asociaría a la conexión inexistente una variable artificial, con un coeficiente en la función objetivo M, siendo Muna constante suficientemente grande. El problema de transporte puede representarse con una tabla m×nque muestra en cada iteración del algoritmo de resolución si,dj,ci j y la solución factible básica (s.f.b.) considerada. Las filas representan los orígenes y las columnas los destinos. La casilla de la fila iy columna jcontiene los valores xi j yci j. Esta tabla permitirá resolver el problema de transporte sin necesidad de usar las tablas del algoritmo simplex lo que, como ya se ha señalado, hace el método más sencillo y eficiente. Una posible forma detallada de dicha tabla puede verse en la Figura 1.2. En adelante la llamaremos tabla de transporte. Figura 1.2: Tabla del problema de transporte Para representar el problema de transporte en forma matricial, definimos los siguientes vectores y matrices: X= (x11,x12,...,x1n,x21,...,x2n,...,xmn)t c= (c11,c12,...,c1n,c21,...,c2n,...,cmn) b= (s1,s2,...,sm,−d1,−d2,...,−dn)t A= (A11,A12,...,A1n,A21,...,A2n,...,Amn) donde Ai j =ei−em+j, siendo ekun vector de Rm+ncon un 1 en el lugar k, y el resto ceros. Con estas notaciones, la formulación matricial del problema de transporte es: Minimizar cX sujeto a AX =b X≥0 La matriz de coeficientes Adel problema de transporte tiene dimensión (m+n)×mn, y tiene la siguiente forma: A=       1n0n... 0n 0n1n... 0n . . .. . .. . . 0n0n... 1n −In−In... −In        donde 1ny 0nson vectores 1×ncon todo unos y con todo ceros, respectivamente, e Ines la matriz identidad n×n. Autor: Manuel García Narváez 10 Capítulo 2. El problema de transporte con carga fija debemos tener que yi j =1, y viceversa. En cambio, si xi j =0, entonces no se utiliza la ruta (i,j), por lo que debemos tener que yi j =0, y viceversa. Además, salvo indicación expresa, supondremos que el problema está balanceado. El PTCF se puede expresar en forma matricial como: Minimizar cX +qY sujeto a AX =b yi j =1 si y sólo si xi j >0 yi j =0 si y sólo si xi j =0 X≥0 donde q= (q11,q12,...,qmn) El PTCF (y el problema de transporte) son casos particulares del problema de transporte cóncavo (PTC) [11]. Este problema tiene las mismas restricciones que el problema de transporte, pero se trata de minimizar la función objetivo ∑i j φi j(xi j), siendo φi j una función cóncava. El PTC suele aparecer al considerar economías de escala. Haciendo uso de esta clase de problemas, se puede ver, al menos teóricamente, que cualquier problema de programación entera con coeficientes enteros puede formularse como un PTCF. 2.3. El problema de programación lineal con carga fija El problema de programación lineal con carga fija, como hemos señalado anteriormente, fue estudiado por Hirsch y Dantzig en su artículo "The fixed charge problem" [16]. Aunque no resolvieron el problema, dedujeron algunas propiedades sobre su solución óptima. El problema de programación lineal con carga fija formulado por Hirsch y Dantzig es: Minimizar n ∑ i=1(αixi+βiyi) sujeto a PX =Q yi=1 si y sólo si xi>0 yi=0 si y sólo si xi=0 X≥0 donde αi,βison constantes, i=1,...,n;X= (x1,...,xn)tes el vector de variables de dimensión n;Q es un vector de coeficientes de dimensión m, con m<n; y Pes una matriz de coeficientes m×n. Hirsch y Dantzig proponen la siguiente interpretación de este problema. Consideremos una compañía que dispone de mmáquinas, cada una de las cuales puede realizar cualquiera de ntrabajos distintos. Sean ci j yhi j el coste y el tiempo empleado cuando la máquina jrealiza la operación i sobre una unidad de producto, respectivamente. Sea qi j el coste fijo asociado a preparar la máquina jpara realizar la operación i(supondremos despreciable el tiempo invertido en esta actividad). Sea xi j la cantidad de producto a la que la máquina jle realiza la operación i. Sea bila cantidad total de producto sobre la que hay que realizar la operación i. Sea cjel total de horas de disponibilidad de la máquina j. Sea yi j una variable binaria que toma el valor 1 si xi j >0 y 0 en caso contrario, i=1,...,n, j=1,...,m. Entonces, el problema de minimizar el coste total asociado a que el producto reciba las operaciones necesarias será el siguiente problema de programación lineal con carga fija: Problemas de transporte y problemas de transporte con carga fija 2.3. El problema de programación lineal con carga fija 11 Minimizar m ∑ i=1 n ∑ j=1(ci jxi j +qi jyi j) sujeto a n ∑ j=1xi j =bi,i=1,...,m m ∑ i=1hi jxi j =cj,j=1,...,n yi j =1 si y sólo si xi j >0 yi j =0 si y sólo si xi j =0 xi j ≥0,i=1,...,m,j=1,...,n El problema de programación lineal con carga fija es difícil de resolver en general. Sin embargo, en el caso particular de que las cargas fijas βisean todas iguales y no negativas, el problema se reduce a resolver un problema de programación lineal, como demuestra el siguiente teorema. Teorema 2.3.1. Sean φ(X) = n ∑ i=1αixi+βn ∑ i=1yi,φ1(X) = n ∑ i=1αixi con βconstante no negativa, funciones a minimizar sujetas a las restricciones del problema de programación lineal con carga fija. Suponemos que Q no está generado por menos de m columnas de P (hipótesis de no degeneración). Entonces existe un punto extremo ˆ X, con exactamente m componentes no nulas, en el que φyφ1se minimizan. Además, si un punto con m componentes no nulas minimiza φ1, entonces también minimiza φ. Demostración: Bajo la hipótesis de no degeneración, tenemos que cualquier vector Xde dimensión n que cumpla que PX =Qtiene al menos mcomponentes no nulas. Sea Xel conjunto de todos estos vectores X. Entonces, usando una desigualdad del mínimo y observando que n ∑ i=1yies el número de componentes no nulas del vector (x1,...,xn), tenemos que min X∈Xφ(X)≥min X∈Xφ1(X)+βmin X∈X n ∑ i=1 yi≥min X∈Xφ1(X)+mβ(2.1) Como φ1es una función lineal, minimizar φ1respecto a las restricciones del problema con carga fija es un problema de programación lineal, por tanto, existe un punto extremo ˆ X, con exactamente m componentes no nulas (por la hipótesis de no degeneración), que minimiza φ1. Tomando dicho punto y usando las desigualdades 2.1, tenemos que φ(ˆ X)≥min X∈Xφ(X)≥min X∈Xφ1(X)+mβ=φ1(ˆ X)+mβ=φ(ˆ X) Por tanto, llegamos a que φ(ˆ X) = min X∈Xφ(X), lo cual prueba las dos partes del teorema. Como consecuencia del Teorema 2.3.1., es posible usar el método simplex para resolver el problema de programación lineal con carga fija cuando las cargas fijas son iguales y no negativas. Hirsch y Dantzig también estudiaron una generalización del problema de programación lineal con carga fija, muy relacionado con el problema de transbordo. Las restricciones son las mismas que en el problema original, pero la función objetivo a minimizar es n ∑ i=1αixi+ p ∑ r=1βrδ rk ∑ i=(r−1)k+1 xi! donde n=kp (kes divisor de n); y δ(u)vale cero si ues cero, y uno si ues mayor que cero. Claramente, si k=1 y p=n, tenemos φ. También se puede ver que el mínimo del problema de programación lineal con carga fija generalizado se alcanza en un punto extremo. Autor: Manuel García Narváez 12 Capítulo 2. El problema de transporte con carga fija Teorema 2.3.2. La solución óptima del problema de programación lineal con carga fija es un punto extremo. La demostración se puede encontrar en [16], y se puede demostrar usando variedades, o directamente con la definición de punto extremo, viendo que para todo vector Xde ncomponentes existe un punto extremo X∗tal que φ(X∗)≤φ(X), siendo φla función objetivo del problema de programación lineal con carga fija. 2.4. Un método aproximado de resolución Como hemos señalado anteriormente, en 1961, el matemático americano Michel Balinski formula una solución aproximada del PTCF en su artículo "Fixed-cost transportation problems" [6]. Balinski formula el PTCF de la siguiente forma: Minimizar m ∑ i=1 n ∑ j=1(ci jxi j +qi jyi j) sujeto a n ∑ j=1xi j =si,i=1,...,m m ∑ i=1xi j =dj,j=1,...,n 0≤xi j ≤mi jyi j,i=1,...,m,j=1,...,n 0≤yi j ≤1,yi j entero,i=1,...,m,j=1,...,n (2.2) donde mi j =min (si,dj). Esta formulación es equivalente a la presentada en la sección 2.2. En efecto, veamos que la tercera y la cuarta restricción hacen que se cumplan las restricciones sobre las variables yi j. Si yi j =0, por la tercera restricción, xi j =0. Si xi j >0, yi j no puede ser cero por la tercera restricción y, para que se cumpla la cuarta, yi j debe ser uno. Además, si xi j =0, yi j puede ser cero o uno pero, como se está minimizando la función objetivo, será cero; y, por lo tanto, también se cumplirá el último requisito, que yi j =1 implica que xi j >0. Antes de explicar la aproximación de Balinski, estudiaremos algunas propiedades del PTCF. La primera es que este problema posee una solución óptima entera, como demuestra el siguiente teorema. Teorema 2.4.1. Existe una solución (X,Y)del PTCF tal que X es entero. Demostración: Sea (X0,Y0) = {x0 i j,y0 i j}una solución óptima del PTCF. Definimos el siguiente problema Minimizar m ∑ i=1 n ∑ j=1˜ci jxi j sujeto a n ∑ j=1xi j =si,i=1,...,m m ∑ i=1xi j =dj,j=1,...,n xi j ≥0,i=1,...,m,j=1,...,n (2.3) donde ˜ci j =ci j si y0 i j =1, y ˜ci j =Msi y0 i j =0, con Muna constante suficientemente grande. Entonces, X0es una solución óptima de (2.3). Por otro lado, este problema tiene una solución óptima entera X0, por ser un problema de transporte. Además, es inmediato comprobar que (X0,Y0)es una solución óptima del PTCF. Vamos a considerar el PTCF (2.2) sin las restricciones de integridad, que llamamos PTR (problema de transporte relajado): Problemas de transporte y problemas de transporte con carga fija 2.4. Un método aproximado de resolución 13 Minimizar m ∑ i=1 n ∑ j=1(ci jxi j +qi jyi j) sujeto a n ∑ j=1xi j =si,i=1,...,m m ∑ i=1xi j =dj,j=1,...,n 0≤xi j ≤mi jyi j,i=1,...,m,j=1,...,n 0≤yi j ≤1,i=1,...,m,j=1,...,n (2.4) Teorema 2.4.2. Si (¯ X,¯ Y) = {¯xi j,¯yi j}es una solución óptima del PTR, entonces ¯xi j =mi j ¯yi j. Demostración: Si ¯yi j =0, entonces ¯xi j =0, y se cumple la condición. Si, por el contrario, ¯yi j >0, supongamos que no se cumple la condición del teorema, es decir, ¯xi j <mi j ¯yi j. En este caso, podríamos encontrar un valor ¯y0 i j <¯yi j, que siguiera cumpliendo las restricciones del PTR, con menor valor de la función objetivo, contradiciendo que (¯ X,¯ Y)es una solución óptima del PTR. En consecuencia, si tenemos una solución óptima del PTR (¯ X,¯ Y) = {¯xi j,¯yi j}, entonces ¯yi j =¯xi j/mi j. Por tanto, resulta natural plantearnos el siguiente problema: Minimizar m ∑ i=1 n ∑ j=1(ci j +qi j/mi j)xi j sujeto a n ∑ j=1xi j =si,i=1,...,m m ∑ i=1xi j =dj,j=1,...,n xi j ≥0,i=1,...,m,j=1,...,n (2.5) Este problema es fácil de resolver por ser un problema de transporte. Sea {x0 i j}una solución óptima. A partir de ella podemos construir una solución factible del PTCF {x∗ i j,y∗ i j}, con x∗ i j =y∗ i j =0 si x0 i j =0 x∗ i j =x0 i j,y∗ i j =1 si x0 i j >0 Esta solución factible {x∗ i j,y∗ i j}es la que toma Balinski como aproximación a la solución óptima del PTCF. También podemos obtener una solución óptima {¯xi j,¯yi j}del PTR, con ¯xi j =x0 i j e ¯yi j =x0 i j/mi j por lo que resolver un PTR es equivalente a resolver un problema de transporte ordinario. De las soluciones {x∗ i j,y∗ i j}y{x0 i j}podemos deducir unas cotas para el valor óptimo de la función objetivo del PTCF. Sea {x0 i j,y0 i j}una solución óptima del PTCF. Definimos z0=m ∑ i=1 n ∑ j=1(ci jx0 i j +qi jy0 i j) z+=m ∑ i=1 n ∑ j=1(ci jx∗ i j +qi jy∗ i j) z−=m ∑ i=1 n ∑ j=1(ci j +qi j/mi j)x0 i j Es inmediato comprobar que la función objetivo del problema (2.5) evaluada en {x0 i j}tiene el mismo valor que la función objetivo del PTCF en {¯xi j,¯yi j}. Por tanto, como {x0 i j,y0 i j}es una solución factible del PTR, se tiene que z−≤z0. Además, como {x∗ i j,y∗ i j}es una solución factible del PTCF, también se tiene que z0≤z+. Así pues, z−≤z0≤z+(2.6) Autor: Manuel García Narváez 14 Capítulo 2. El problema de transporte con carga fija Balinski usó esta aproximación en varios ejemplos. Sin embargo, como la solución exacta no era conocida, no fue posible compararlas. El estudio y evaluación de esta aproximación la llevaron a cabo Robers y Cooper en un trabajo posterior. 2.5. Evaluación del método aproximado de Balinski En 1976, Philip Robers y Leon Cooper publicaron el artículo titulado "A study of the fixed charge transportation problem" [22], en el cual evalúan el método de aproximación de Balinski para la solución del PTCF expuesto en la sección 2.4. Dada la dificultad en aquel momento de encontrar la solución óptima para el PTCF en general, generaron una serie de problemas cuya solución óptima era conocida de antemano. Para analizar la solución proporcionada por el método de Balinski, utilizaron tres estadísticos, descritos en la Tabla 2.1. Tabla 2.1: Estadísticos Nombre Fórmula Descripción Índice de posición z0−z− z+−z− Mide donde se encuentra z0en el intervalo [z−,z+] Error porcentual 100 z+−z0 z0Mide la diferencia entre la solución real y la aproximada Anchura de intervalo porcentual 100 z+−z− z0Mide la anchura del intervalo [z−,z+] Una vez analizados los resultados, se pudo observar que la cota inferior de la solución del PTCF, z−, estaba muy por debajo de la solución real, por lo que, en general, no era un dato útil. También se comprobó que tanto el error porcentual como la anchura de intervalo porcentual eran grandes si el problema resuelto tenía cargas fijas grandes y, por el contrario, al disminuir las cargas, estos estadísticos disminuían también. Este hecho puede justificarse observando que, si {qi j}toman valores pequeños, el PTCF original y el problema (2.5) son similares. Estos estadísticos también aumentan (no linealmente) cuando el tamaño del problema aumenta. Sin embargo, cuando la proporción entre myndisminuye (hay muchos más destinos que orígenes), los estadísticos disminuyen. Intuitivamente, este hecho se justifica observando que, la demanda de un destino, al haber menos orígenes, puede ser satisfecha por un único origen en muchos casos en la solución óptima (ya que la solución tendrá como mucho m+n−1 valores no nulos). En esos casos, mi j =min (si,dj) = x0 i j, y el coste de transportar de iajes el mismo en los dos problemas, por lo que la solución del PTCF y del problema (2.5) será similar. En general, se puede deducir que la aproximación de Balinski da buenas soluciones, pero Robers y Cooper desarrollaron una mejora de este procedimiento que proporciona mejores resultados (al menos no peores). La modificación propuesta comienza calculando la solución de Balinski, que sabemos que es un punto extremo. A continuación, se determinan las s.f.b. adyacentes a esta y se elige la de menor coste en la función objetivo. Si el coste es menor que en la s.f.b. actual se sustituye esta por aquella y se aplica de nuevo el procedimiento de determinación de sus soluciones adyacentes; en caso contrario, el procedimiento acaba y se toma como solución la última s.f.b. calculada con el procedimiento. Con este método, se obtiene la solución óptima en la mayoría de los problemas estudiados en el artículo [22]. Problemas de transporte y problemas de transporte con carga fija 2.6. Un algoritmo basado en el procedimiento de Benders 15 2.6. Un algoritmo basado en el procedimiento de Benders En 1964, Kurt Spielberg publicó el artículo "On the fixed charge transportation problem" [24], en el que se propone el primer algoritmo para resolver el PTCF. Spielberg identifica el PTCF como un caso particular de un problema de programación entero mixto (PPEM) estudiado por Jacques Benders [8], lo cual hace posible construir un algoritmo iterativo que consiste en resolver sucesiva y alternativamente problemas de transporte y de programación entera. Para permitir una mejor asociación entre el PPEM y el PTCF, Spielberg escribe este último problema de la siguiente forma: Maximizar −(cX +qY) sujeto a AX ≤b⇔     n ∑ j=1xi j ≤si,i=1,...,m m ∑ i=1xi j ≥dj,j=1,...,n X≤MY ΨY=Y X,Y≥0 donde Y= (y11,y12,...,ymn)t,MyΨson las siguientes matrices diagonales M=     m11 m12 ... mmn      ,Ψ=     y11 y12 ... ymn      ymi j =min (si,dj). Notemos que, en esta formulación, se ha multiplicado por −1 la función objetivo. Además, se ha debilitado ligeramente la restricción de la oferta y la demanda, ya que al ser una desigualdad, permitimos que el origen ino tenga que distribuir toda su oferta y el destino jpueda recibir más que su demanda inicial (demanda mínima). De forma análoga a como hemos hecho en la sección 2.4, se puede comprobar fácilmente que la segunda y la tercera restricción fuerzan a que se cumplan las restricciones sobre las variables yi j. El PPEM se formula como: max{γtX+f(Y)|˜ AX +E(Y)≤a,X≥0,Y∈S} donde Ses un conjunto cerrado y acotado de vectores. Para su resolución, se consideran los siguientes problemas auxiliares max x0|x0 Y∈G(2.7) con G=∩x0 Y|u0x0+utE(Y)−u0f(Y)≤uta,(u0,u)t∈C,Y∈S, y max {γtX|˜ AX ≤a−E(¯ Y),X≥0}(2.8) donde x0,u0son escalares, ues un vector columna, ¯ Yes un vector Ysolución del primer problema (2.7), y C=u0 u|˜ Atu−γu0≥0,u≥0,u0≥0 Autor: Manuel García Narváez 16 Capítulo 2. El problema de transporte con carga fija La razón de considerar estos dos problemas es que, si tenemos (¯x0,¯ Y)solución óptima de (2.7), entonces (2.8) es factible, y su solución óptima es ¯ X, con γt¯ X=¯x0−f(¯ Y). Además, (¯ X,¯ Y)es solución óptima del PPEM. Por lo tanto, este problema se reduce a estudiar estos dos problemas auxiliares. Benders demostró que Gse puede aproximar por una secuencia de G(Qk),k=0,1,..., donde G(Qk) = ∩x0 Y|u0x0+utE(Y)−u0f(Y)≤uta,(u0,u)t∈Qk⊂C,Y∈S El paso 0 comienza con un subconjunto Q0de Ccualquiera. A continuación, con el objetivo de resolver el PPEM, consideramos, en el paso k, el problema max x0|x0 Y∈G(Qk)(2.9) análogo al problema (2.7), cuya solución óptima denotamos xk 0 Yk. Esta solución óptima existe si el problema original tiene solución óptima. A continuación, se resuelve el problema max {γtX|˜ AX ≤a−E(Yk),X≥0}(2.10) análogo al problema (2.8), o su correspondiente dual min {(a−E(Yk))tu|˜ Atu≥γ,u≥0}(2.11) El problema dual es un problema factible. En cuanto al problema (2.10), caben dos posibilidades (notemos que estamos en el paso k): 1. Es factible. En tal caso, los dos problemas, (2.10) y (2.11), tienen solución óptima finita, Xk,uk, respectivamente. Consideramos la función Fk≡F(uk,xk 0,Yk) = xk 0−f(Yk)−(a−E(Yk))tuk Se puede demostrar, observando que G⊂G(Qk), que Fk≥0. Si Fk=0, acaban las iteraciones y la solución del PPEM es X=XkeY=Yk. Si, por el contrario, Fk>0, entonces se considera Qk+1=Qk∪ 1 uk, y se va al paso k+1. 2. No es factible. Como el problema dual es factible, entonces ha de ser no acotado. Aplicando el método simplex, obtenemos ˆukvértice de Py ˜ukdirección extrema de C0, donde P={u|˜ Atu≥γ,u≥0}yC0={u|˜ Atu≥0,u≥0}. Si F(ˆuk,xk 0,Yk)≤0, se considera Qk+1=Qk∪ 0 ˜uk, y se va al paso k+1. Si F(ˆuk,xk 0,Yk)>0, se considera Qk+1=Qk∪ 0 ˜uk,1 ˆuk, y se va al paso k+1. Benders [8] demostró que el número de iteraciones necesarias para pasar de QkaQk+1es finito, por lo que el procedimiento termina con una solución del PPEM. Examinando el PTCF, podemos observar que es un caso particular del PPEM, sin más que tomar Problemas de transporte y problemas de transporte con carga fija 2.6. Un algoritmo basado en el procedimiento de Benders 17 γt=−c,f(Y) = −qY ˜ A=A Imn  E(Y)t= (0,...,0 | {z } m+n ,−m11y11,...,−mmnymn) at= (bt,0,...,0 | {z } mn ) La restricción ΨY=Yse incluye al restringir el dominio de los vectores Y,S, a vectores de componentes 0 ó 1. Las variables duales las expresamos como ut= (u1,...,um,v1,...,vn,w11,...,wmn). Así pues, los conjuntos CyG(Qk)pueden escribirse como C=u0 u|ui−vj+wi j +u0ci j ≥0; ui,vj,wi j,u0≥0,∀i,j G(Qk) = ∩(x0 Y|u0x0≤ −d(ui,vj)+ m ∑ i=1 n ∑ j=1 yi j(mi jwi j −qi ju0),(u0,ui,vj,wi j)t∈Qk) con d(ui,vj) = −uta=n ∑ j=1djvj−m ∑ i=1siui Siguiendo los pasos descritos anteriormente para resolver el PPLEM, si estamos en el paso k, se empieza resolviendo el problema (2.9), cuya formulación es ahora la siguiente: max(x0|uk 0x0≤ −d(uk i,vk j)+ m ∑ i=1 n ∑ j=1yi j(mi jwk i j −qi juk 0),yi j =0,1,k=0,1,...) Como se está resolviendo un problema de transporte, se debe imponer que m ∑ i=1siyi j ≥djy n ∑ j=1djyi j ≥si, lo que restringe el dominio de SeY, ya que la oferta total potencialmente disponible para cada destino debe, al menos, igualar su demanda, y cada origen puede enviar a lo sumo la totalidad de su oferta, respectivamente. A continuación, se resuelve el problema (2.10), cuya formulación es la siguiente: max{−cX|AX ≤b,xi j ≤mi jyk i j,xi j ≥0}(2.12) Se puede interpretar como un problema de transporte en el que la ruta (i,j)está prohibida si yk i j =0, ya que entonces xi j =0. Para resolver este problema, se le asocia un problema de transporte estándar en el que las rutas prohibidas tendrán un coste alto: max{−(c+Mk)tX|AX ≤b,xi j ≥0}(2.13) donde Mk i j =Msi yk i j =0, y Mk i j =0 si yk i j =1, siendo Muna constante positiva suficientemente grande. Hay que considerar dos casos: Caso 1: La solución óptima del problema (2.13) no depende de M. En este caso, esta es la solución del problema con rutas prohibidas (2.12). Resolviendo a su vez su problema dual, y aplicando la igualdad en las funciones objetivo del problema primal y del problema dual, se tienen todos los datos que permiten evaluar la función Fk=xk 0+d(uk i,vk j)+ m ∑ i=1 n ∑ j=1 yk i j(qi j −mi jwk i j) construir Qk+1y pasar al paso k+1. Autor: Manuel García Narváez 18 Capítulo 2. El problema de transporte con carga fija Caso 2: La solución del problema depende de M. En este caso, (2.12) no es factible. Por tanto, su dual es no acotado. Siguiendo el procedimiento descrito por Spielberg [24], se pueden obtener el vértice ˆuky la dirección extrema ˜ukde no acotación. A continuación se construye Qk+1y se pasa al paso k+1. 2.7. Un algoritmo basado en fijar las variables binarias En 1968, Paul Gray, en su artículo "Exact solution of the fixed-charge transportation problem" [15], propone un método para encontrar una solución exacta al PTCF basado en fijar las variables enteras y resolver el problema de transporte asociado. Consideremos la siguiente formulación del PTCF: Minimizar m ∑ i=1 n ∑ j=1(ci jxi j +qi jyi j) sujeto a n ∑ j=1xi j ≤si,i=1,...,m m ∑ i=1xi j ≥dj,j=1,...,n xi j ≤mi jyi j,i=1,...,m,j=1,...,n xi j ≥0,i=1,...,m,j=1,...,n yi j ∈ {0,1},i=1,...,m,j=1,...,n con mi j =min (si,dj). Supongamos que se han fijado los valores de las variables binarias yi j,i=1,...,m,j=1,...,n. Sean estos valores ¯yi j. El problema que resulta es un problema de transporte en el que la ruta (i,j) está prohibida si ¯yi j =0: Minimizar m ∑ i=1 n ∑ j=1ci jxi j sujeto a n ∑ j=1xi j ≤si,i=1,...,m m ∑ i=1xi j ≥dj,j=1,...,n xi j ≤mi j ¯yi j,i=1,...,m,j=1,...,n xi j ≥0,i=1,...,m,j=1,...,n (2.14) Ya vimos en la sección 2.6 anterior como abordar este problema. Si el problema (2.14) no tiene solución factible para {¯yi j}fijadas, entonces el PTCF tampoco la tiene para esos mismos valores de ¯yi j. Si (2.14) tiene solución óptima {¯xi j}, entonces {¯xi j,¯yi j}es una solución factible del PTCF. Teniendo en cuenta estos comentarios, se puede proponer el siguiente algoritmo para calcular la solución exacta del PTCF: Paso 1: Enumerar los posibles vectores ¯ Y= (¯y11,...,¯ymn). Paso 2: Resolver el problema (2.14) para cada ¯ Y. Paso 3: Para cada solución óptima del problema (2.14), calcular m ∑ i=1 n ∑ j=1(ci j ¯xi j +qi j ¯yi j). La solución óptima del PTCF es {¯x0 i j,¯y0 i j}para la que el cálculo anterior es mínimo. Este algoritmo no es eficiente desde el punto de vista del tiempo invertido en la resolución del problema, ya que el número de vectores ¯ Ya considerar es muy grande, por lo que Gray calculó cotas Problemas de transporte y problemas de transporte con carga fija 2.7. Un algoritmo basado en fijar las variables binarias 19 para la carga fija total de la solución óptima del PTCF con el fin de reducir el número de vectores ¯ Ya considerar. Supongamos que se tiene una solución factible del PTCF (por ejemplo, la que propone Balinski, descrita en la sección 2.4). Sea Z0el valor de su función objetivo. Sea Zmin el valor óptimo de la función objetivo del PTCF con cargas fijas nulas (se reduce a un problema de transporte ordinario). Entonces, CFmax =Z0−Zmin es una cota superior de la carga fija total de la solución óptima del PTCF. Esta cota se puede mejorar ya que, fijando los {¯y1j}, para j=1,...,n, y llamando Zmin1al valor óptimo de la función objetivo del PTCF con las {¯y1j}fijadas, tenemos que una cota superior mejorada es Z0−Zmin1, ya que Zmin1≥Zmin. La cota se puede ir mejorando fijando sucesivos valores {¯yi j}. Para reducir aún más el número de vectores ¯ Ya considerar en el algoritmo anterior, se pueden usar las siguientes propiedades: a) La solución óptima del PTCF es un punto extremo (Teorema 2.3.2., sección 2.3), por lo que si {x0 i j,y0 i j}es una solución óptima, el número de elementos no nulos de {x0 i j}es a lo sumo m+n−1, y, por tanto, lo mismo le ocurre al número de elementos no nulos de {y0 i j}. b) Como ya se ha señalado en la sección 2.6,n ∑ j=1djyi j ≥si,i=1,...,m, y m ∑ i=1siyi j ≥dj, j=1,...,n. c) Debe haber al menos una ruta abierta a cada destino. d) Para cada destino abastecido por un único origen, puede eliminarse el destino del estudio y reducir la oferta del origen en la demanda del destino considerado. Para cada origen que abastece un único destino puede eliminarse dicho origen del estudio y reducir la demanda de ese destino en la oferta del origen considerado. Utilizando estas últimas propiedades y las cotas antes calculadas, Gray desarrolla un algoritmo para reducir el número de vectores ¯ Ya considerar, de manera que pudiera aplicarse el algoritmo presentado anteriormente y resolver el PTCF: Inicialización: Paso 10: Reordenar los orígenes del PTCF en orden decreciente según su oferta. Paso 20: Para cada origen, calcular la demanda total para cada combinación de rutas abiertas. Si la oferta es mayor que la demanda en una combinación, entonces dicha combinación no es factible, y se le asigna una carga fija M, siendo Muna constante suficientemente grande. Paso 30: Para el resto de combinaciones, calcular el coste fijo total asociado. Paso 40: Para cada origen, ordenar las combinaciones de destinos en orden creciente según su coste fijo total. Paso 50: Crear una tabla, representando los orígenes en las filas, las combinaciones de destinos en las columnas, y los costes fijos totales en cada casilla. La denotamos tabla de costes fijos. Paso 60: Para cada fila de la tabla de costes fijos, buscar la mayor carga fija total permitida, que se obtiene restando a CFmax la suma de las cargas fijas más pequeñas de las otras filas. Acotación (supongamos que ya hemos aplicado esta parte para los primeros korígenes): Paso 70: Resolver el PTCF con las rutas abiertas especificadas desde el origen 1 hasta el k, y con todas las rutas desde el origen k+1 hasta el mabiertas. Paso 80: Calcular CFmax. Autor: Manuel García Narváez 26 Capítulo 3. Casos particulares y propiedades del problema de transporte con carga fija Finalmente, Hultberg y Cardoso analizaron el algoritmo computacionalmente, obteniendo resultados incluso mejores de los esperados en comparación con los algoritmos generales de resolución del PTCFP, pudiendo resolver problemas de tamaño considerablemente grande. 3.3. La paradoja de más por menos En 1998, Veena Adlakha y Krzysztof Kowalski estudiaron la "paradoja" de más por menos (PMM) en el PTCF, en el artículo "On the fixed-charge transportation problem" [1]. La PMM ocurre cuando, en un problema de transporte, es posible enviar más unidades de producto por un coste menor o igual, siempre que enviemos la misma cantidad (o más) desde cada origen y hasta cada destino, y todos los costes de transporte sean no negativos. A pesar de no ser una paradoja, se denomina así por lo contraintuitiva que es la propiedad. En el sencillo ejemplo de problema de transporte de la Figura 3.1 podemos observar este hecho: (a) PT 1 (b) PT 2 Figura 3.1: Ejemplo de PMM En azul se representan la oferta y demanda de cada origen y destino, respectivamente, en rojo se representa el coste lineal de cada ruta, y en verde se representa la cantidad de producto enviado por cada ruta. El mínimo coste en el PT1es 12, y se envían en total tres unidades de producto. En el PT 2, en el que hemos aumentado la oferta del nodo 1 y la demanda del nodo 3, la solución óptima tiene un coste de 4 y se envían en total cuatro unidades de producto. La PMM es una propiedad con importantes repercusiones económicas, tanto en el problema de transporte como en el PTCF, ya que es útil a la hora de incrementar las capacidades de las fábricas, de hacer fusiones, de llevar a cabo reducciones de personal, etc. Sin embargo, también puede conllevar el esfuerzo de intentar aumentar la demanda de un cierto mercado, ya que se tiene más oferta. Para identificar una solución óptima "más por menos", Adlakha y Kowalski proponen un procedimiento basado en localizar los puntos absolutos del PTCF relajado, el PTR (véase la sección 2.4), ya que, usando las desigualdades (2.6), si tenemos una solución "más por menos" para el PTR, también es una solución "más por menos" para su PTCF asociado. Definición 3.3.1. Un punto absoluto es una variable xi j del problema transporte que debe ser positiva en cualquier solución óptima del problema, independientemente de los valores de siy dj. Para calcular los puntos absolutos en un PTCF, en [1] se propone el siguiente algoritmo: Paso 1: Para cada k=1,...,m, calcular dk i j =Ck j −Ci j,i6=k,i=1,...,m,j=1,...,n, donde Ci j =ci j +qi j/mi j,mi j =min (si,dj). Paso 2: Para cada matriz (dk i j), calcular el mínimo valor ek ide cada fila, i=1,...,m,i6=k. Paso 3: Calcular la matriz (dk∗ i j ), con dk∗ i j =dk i j −ek i. Paso 4: Para cada k=1,...,m, calcular gk j=m ∑ i=1dk∗ i j . Paso 5: a) Si gk j6=0, para cualquier j,k, entonces no hay puntos absolutos. Problemas de transporte y problemas de transporte con carga fija 3.3. La paradoja de más por menos 27 b) Si gk j=0 para k=qyj=r, entonces xqr es un punto absoluto. Una forma alternativa al algoritmo simplex para resolver el PTR es con la ayuda de los puntos absolutos. Cuando encontremos uno, xqr, le asignamos el valor min(sq,dr). A continuación eliminamos del estudio la fila o columna cuya nueva oferta o demanda sea cero, y actualizamos drósq, respectivamente. Por último, con el nuevo problema construimos su PTR, y volvemos a empezar. Para encontrar una solución óptima "más por menos", Adlakha y Kowalski proponen el siguiente algoritmo: Paso 10: Formular el PTR del PTCF actual. Paso 20: Encontrar un punto absoluto del PTR,xqr. Si no hay, ir al Paso 60. Paso 30: Asignar xqr =max (sq,dr). Paso 40: Eliminar del estudio la fila qo columna rcorrespondiente. Paso 50: Volver al Paso 10. Paso 60: Resolver el PTR con el método simplex de transporte. Notemos que es posible que el PTCF no tenga puntos absolutos, en cuyo caso ha de resolverse con un procedimiento general. Sin embargo, se ha observado que en problemas reales la probabilidad de encontrarlos aumenta considerablemente en comparación con problemas "artificiales". Autor: Manuel García Narváez 28 Capítulo 3. Casos particulares y propiedades del problema de transporte con carga fija Problemas de transporte y problemas de transporte con carga fija Apéndice A Resultados computacionales Para finalizar este trabajo, se ha determinado el tiempo de resolución de varios PTCF generados aleatoriamente, resueltos con Lingo 12 con el procedimiento general de resolución de problemas de programación entera. En la Tabla A.1 se muestran los resultados: Tabla A.1: Solución de los PTCF Node problema Orígenes Destinos Dimensión Valor óptimo de la función objetivo Tiempo de CPU 1 6 20 120 21533 0 seg 2 6 40 240 79885 0 seg 3 10 50 500 53216 0 seg 4 10 100 1000 177220 1 seg 5 15 50 750 48163 0 seg 6 15 100 1500 123720 2 seg 7 20 100 2000 105553 5 seg 8 20 200 4000 324682 29 seg 9 25 100 2500 89482 2 seg 10 25 200 5000 256527 16 seg 11 30 60 1200 38890 1 seg 12 30 100 3000 87238 2 seg 13 40 100 4000 68154 1 seg 14 40 200 8000 193185 56 min 22 seg 15 70 100 7000 52460 4 seg 16 70 200 14000 141395 2 min 52 seg Las características del ordenador utilizado para resolver los PTCF son: PC Intel Core CPU de 2.4 GHz con 4 GB de RAM en Windows 7. Si mes el número de orígenes y nes el número de destinos en los PTCF, las características de estos problemas son: Se eligen m orígenes y n destinos distribuidos aleatoriamente por el cuadrado [0,1]×[0,1]. La demanda de cada destino es un número aleatorio entre dMin =10 y dMax =30. La capacidad de los almacenes es un número aleatorio entre cMin = (3·dMin ·n)/my cMax = (3·dMax ·n)/m. El coste variable entre el origen iy el destino jse calcula como [(10+100·d(i,j)], donde d(i,j) es la distancia euclídea entre iyj, y [·]es la función parte entera. 29 30 Capítulo A. Resultados computacionales El coste fijo de cada arco se calcula como un número aleatorio entre 2 y 3 por la capacidad de arco correspondiente. En la Tabla A.1 se observa que el tiempo invertido en resolver un PTCF es muy pequeño para problemas de dimensión menor que 8000, e inapreciable para problemas hasta dimensión 1000. Los dos PTCF que más han tardado en resolverse son los dos que más destinos tienen: 8000 y 14000, siendo el primero de ellos el que más tiempo le ha costado. Problemas de transporte y problemas de transporte con carga fija Bibliografía [1] Adlakha, V.; Kowalski, K.: On the fixed-charge transportation problem, Omega, The International Journal of Management Science 27 (1999), 381-388. [2] Adlakha, V.; Kowalski, K., Lev, B.: A branching method for the fixed charge transportation problem, Omega, The International Journal of Management Science 38 (2010), 393-397. [3] Adlakha V.; Kowalski K., Vemuganti R.R.: Heuristic algorithms for the fixed-charge transportation problem, Opsearch 43 (2006), 132-151. [4] Adlakha V.; Kowalski K., Wang S., Lev B., Shen W.: On approximation of the fixed charge transportation problem, Omega, The International Journal of Management Science 43 (2014), 64-70. [5] Agarwal Y.; Aneja Y.: Fixed-charge transportation problem: Facets of the projection polyhedron, Operations Research 60 (2012), 638-654. [6] Balinski, M.L.: Fixed-cost transportation problems, Naval Research Logistics Quarterly 8 (1961), 41-54. [7] M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear programming and network flows, John Wiley & Sons Inc, 3aedición, 2005. [8] Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik 4(1962), 238-252. [9] Buson E., Roberti R., Toth P.: A reduced-cost iterated local search heuristic for the fixedcharge transportation problem, Operations Research DOI: http://dx.doi.org/10.1287/ opre.2014.1288 (próximo a aparecer) (2014), 1-12. [10] G.B. Dantzig; M.N. Thapa, Linear programming. 1: Introduction, Springer, 1aedición, 1997. [11] C.A. Floudas; P.M. Pardalos, Encyclopedia of Optimization, Springer, 2aedición, 2009. [12] L.R. Ford; D.R. Fulkerson, Flows in networks, Princeton University Press, 1aedición, 1962. [13] R. Garfinkel; G.L. Nemhauser, Integer programming, John Wiley & Sons Inc, 1aedición, 1972. [14] Göthe-Lundgren, M.; Larsson, T.: A set covering reformulation of the pure fixed charge transportation problem, Discrete Applied Mathematics 48 (1994), 245-259. [15] Gray, P.: Exact solution of the fixed-charge transportation problem, Operations Research 19 (1971), 1529-1538. [16] Hirsch, W.M.; Dantzig G.B.: The fixed charge problem, Naval Research Logistics Quarterly 15 (1968), 413-424. 31 32 BIBLIOGRAFÍA [17] Hultberg, T.H.; Cardoso, D.M.: The teacher assignment problem: A special case of the fixed charge transportation problem, European Journal of Operational Research 101 (1997), 463-473. [18] Kowalski K., Lev B., Shen W., Tu Y.: A fast and simple branching algorithm for solving small scale fixed-charge transportation problem, Operations Research Perspectives, 1(2014), 1-5. [19] Lotfi M.M., Tavakkoli-Moghaddam R.: A genetic algorithm using priority-based encoding with new operators for fixed charge transportation problems, Applied Soft Computing, 13 (2013), 2711-2726. [20] K. Murty, Linear and combinatorial programming, John Wiley & Sons Inc, 1aedición, 1976. [21] G.L. Nemhauser; L.A. Wolsey, Integer and combinatorial optimization, John Wiley & Sons Inc, 1aedición, 1999. [22] Robers, P.; Cooper, L.: A study of the fixed charge transportation problem, Computers and Mathematics with Applications 2(1976), 125-135. [23] Sáez Aguado J.: Fixed charge transportation problems: a new heuristic approach based on Lagrangean relaxation and the solving of core problems, Annals of Operations Research, 172 (2009), 45-69. [24] Spielberg, K.: On the fixed charge transportation problem, Proceedings of the 1964 19th ACM National Conference (1964), 11.101-11.1013. [25] L.A. Wolsey, Integer programming, John Wiley & Sons Inc, 1aedición, 1998. [26] Xie F.; Jia R.: A heuristic algorithm for solving fixed-charge transportation problem, In proceeding of: 2009 WRI World Congress on Computer Science and Information Engineering, 2 (2009), 574-580. Problemas de transporte y problemas de transporte con carga fija