Aplicaciones de la Programación Lineal: El Problema de Transporte

FACULTAD DE TURISMO Y FINANZAS GRADO EN FINANZAS Y CONTABILIDAD Aplicaciones de la Programación Lineal: El Problema de Transporte. Trabajo Fin de Grado presentado por Isabel María Ramos Pérez, siendo la tutora del mismo la profesora Asunción Zapata Reina. Vº. Bº. de la Tutora: Alumna: Dª Asunción Zapata Reina Dª Isabel María Ramos Pérez Sevilla. Mayo de 2016 GRADO EN FINANZAS Y CONTABILIDAD FACULTAD DE TURISMO Y FINANZAS TRABAJO FIN DE GRADO CURSO ACADÉMICO [2015-2016] TÍTULO: APLICACIONES DE LA PROGRAMACIÓN LINEAL: EL PROBLEMA DE TRANSPORTE AUTOR: ISABEL MARÍA RAMOS PÉREZ TUTOR: Dra Dª ASUNCIÓN ZAPATA REINA DEPARTAMENTO: ECONOMÍA APLICADA III ÁREA DE CONOCIMIENTO: MÉTODOS CUANTITATIVOS PARA LA ECONOMÍA Y LA EMPRESA RESUMEN: En este trabajo se analiza una herramienta muy útil para la toma de decisiones en cualquier organización: la programación lineal. Comprende la planificación de actividades, realizando una asignación eficiente de los recursos escasos entre fines alternativos. Es por ello que se utiliza en múltiples áreas: producción, asignación de tareas, logística, marketing, mezclas, gestión de carteras,... Dentro la gestión y organización de una empresa, se puede aplicar, entre otros fines, para que las empresas aumenten sus beneficios, que disminuyan sus gastos o incluso para conseguir la asignación más eficiente de horarios. Se considera en este proyecto el problema de transporte, que tiene en cuenta los costes de transporte, parte importante de los gastos de algunas empresas, y, en concreto, se estudia el caso de una empresa del sector agrícola. PALABRAS CLAVE: Programación Lineal; Solución Óptima; Coste; Transporte. Grado en Finanzas y Contabilidad Facultad de Turismo y Finanzas – Universidad de Sevilla -2- TFG-FICO. Aplicaciones de la Programación Lineal: El Problema de Transporte. -I- ÍNDICE CAPÍTULO 1: INTRODUCCIÓN .............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................. 1 CAPÍTULO 2: PROGRAMACIÓN LINEAL 3 2.1. INTRODUCCIÓN 3 2.2. FORMULACIÓN MATEMÁTICA DE UN PROBLEMA DE PROGRAMACIÓN LINEAL 4 2.3. CONCEPTOS Y RESULTADOS BÁSICOS DE PROGRAMACIÓN LINEAL 5 2.4. MÉTODO GRÁFICO: RESOLUCIÓN DE UN PROBLEMA DE PROGRAMACIÓN LINEAL 8 2.5. ALGORITMO DE RESOLUCIÓN: MÉTODO SIMPLEX 10 2.5.1. Introducción 10 2.5.2. Formulación Matemática del Método Simplex 11 2.6. LINGO 16 2.6.1. Funcionamiento del programa LINGO 17 2.6.2. Interpretación de los datos 18 2.7. APLICACIONES . 19 2.7.1. Introducción … 19 2.7.2. Ámbitos de Aplicación de la Programación Lineal… 20 CAPÍTULO 3: EL PROBLEMA DE TRANSPORTE…… 23 3.1. INTRODUCCIÓN… … 23 3.2. PLANTEAMIENTO 23 3.3. ALGORITMO DE RESOLUCIÓN 27 3.4. SOFTWARE … 33 CAPÍTULO 4: APLICACIÓN PRÁCTICA DEL PROBLEMA DE TRANSPORTE 37 CAPÍTULO 5: CONSIDERACIONES FINALES 43 BIBLIOGRAFÍA……… 45 TFG-FICO. Aplicaciones de la Programación Lineal: El Problema de Transporte. -1- CAPÍTULO 1 INTRODUCCIÓN La Investigación de Operaciones o Investigación Operativa (IO) es una rama de las matemáticas que utiliza modelos matemáticos y algoritmos como apoyo en un proceso de tomas de decisiones. Es una herramienta utilizada en la planificación de actividades, optimizando un objetivo y teniendo en cuenta las restricciones propias de cada actividad. En concreto, este proyecto se centra en la programación lineal. Un modelo de programación lineal permite determinar una estrategia óptima, escogida de un gran número de decisiones posibles, mediante la minimización o maximización de una función lineal denominada función objetivo, de forma que las variables estén sujetas a una serie de restricciones que se expresan mediante un sistema de ecuaciones lineales. La linealidad de todas las funciones que intervienen en el modelo facilita su tratamiento y permite la utilización de algoritmos propios de resolución. De este modo, la programación lineal, dentro de la optimización matemática, es una herramienta útil para la buena gestión de una empresa, cuyo objeto es reducir sus gastos y aumentar sus beneficios. El objetivo de este trabajo es poner de manifiesto la potencialidad de la programación lineal en múltiples situaciones que se plantean en muchos campos tales como: Marketing, Producción, Finanzas, Logística, Ingeniería, etc… En particular, dentro de la Logística, se analiza el problema de transporte, en la búsqueda de una reducción de costes. El proyecto consta de cuatro capítulos. Tras esta introducción, el capitulo dos trata de los principales aspectos de la programación lineal: una introducción histórica, la formulación general, la resolución mediante el método gráfico, el método simplex y el programa informático LINGO, así como las áreas en las que se puede aplicar la programación lineal. Los contenidos de este capítulo se ilustran con un ejemplo práctico. Al problema de transporte (también denominado problema de redes), de indudable interés público y económico tanto por su utilidad como por su eficiencia, se le ha dedicado dos capítulos. El capítulo tres se centra en el modelo de transporte, en su planteamiento y en el algoritmo de resolución, así como en un ejemplo práctico que se resolverá por el método de la esquina noroeste para obtener una solución factible y por el método de los multiplicadores (modi) para obtener la solución óptima, analizando los costes marginales. Asimismo se utiliza un programa informático denominado WINQBS, muy útil para la resolución de problemas en los que intervienen muchas variables. Se analiza en el capítulo cuatro un caso práctico del modelo de transporte de la empresa agrícola Antonio Martínez Legal e Hijos S.L, utilizando el programa informático WINQBS antes mencionado. Finalmente, el capítulo cinco está dedicado a las conclusiones del trabajo. Ramos Pérez, Isabel María -2- TFG-FICO. Aplicaciones de la Programación Lineal: El Problema de Transporte. -3- CAPÍTULO 2 PROGRAMACIÓN LINEAL. 2.1 INTRODUCCIÓN. La programación lineal es una herramienta matemática que ha tenido gran impacto desde mediados del siglo XX en el estudio y desarrollo de la actividad económica. Hoy en día es un instrumento muy utilizado en la administración y en la empresa. Hay que tener cuidado con no confundir el significado de programación con el término de computación (programación pertenece al término programar). En este contexto, la programación está relacionada con el sinónimo planeación o planificación. Y el adjetivo lineal se refiere a que todas las funciones matemáticas deben ser funciones lineales. Se utiliza la programación lineal como apoyo para la toma de decisiones en las que se exige optimizar (maximizar o minimizar) una función lineal (denominada función objetivo) que está sujeta a determinadas limitaciones (restricciones), también dadas por expresiones lineales. Los métodos más usados para resolver los problemas de programación lineal son los algoritmos de pivote y, en concreto, los algoritmos simplex. Los modelos matemáticos de optimización se dividen en modelos determistas y modelos estocásticos. En los primeros, los parámetros son conocidos con certeza absoluta y en los segundos, los parámetros tienen una distribución de probabilidad asociada. Los modelos determistas se clasifican en modelos lineales y no lineales. Los modelos lineales pueden ser enteros o continuos, y los modelos no lineales pueden ser convexos o no convexos. La programación lineal es un modelo determinista lineal. Han sido muchos los personajes matemáticos y economistas que han contribuido a lo largo de los años al desarrollo de la programación lineal. Gaspar Monge en 1776 fue el primero que se interesó por el problema de programación lineal. Sin embargo, el primero en intuir (aunque de forma imprecisa) los métodos que actualmente denominamos programación lineal fue Jean Baptiste-Joseph Fourier en 1826, con el método de eliminación para la solución de un sistema de desigualdad. Ya en el siglo XX, John Von Neumann en 1928, contribuyó al estudio de la programación lineal al demostrar el teorema de maximin o minimax. Una de las más importantes aportaciones fue la realizada por Leonid Vitalevich Kantorovitch. En 1939 publicó una monografía titulada Métodos Matemáticos de Organización y Planificación de la Producción, donde, por primera vez, se trata una extensa gama de problemas con una teoría matemática precisa y bien definida, llamada hoy en día programación lineal. Entre 1941 y 1942, Tjalling Charles Koopmans y Leonid Vitalevich Kantorovich, estudiaron el problema de transporte, también denominado el problema de Koopmans- Kantorovich. Ambos recibieron por este estudio el Premio Nobel de Economía en 1975. Leonid Kantorovich formuló técnicas parecidas a las de Dantzig en la economía y muchas antes de que él publicara el algoritmo simplex. George Joseph Stigler en 1945, planteó el problema del régimen alimenticio óptimo, conocido ahora como el problema de la dieta. En la segunda guerra mundial, se utiliza la programación lineal a fin de reducir los gastos en el ejército y aumentar las pérdidas del enemigo (se mantuvo en secreto hasta 1947). Una vez finalizada la guerra, la industria usó esta metodología para la planificación diaria. La contribución de George Bernard Dantzig a la programación lineal fue quizás una de las más importantes a efectos operativos. En 1947 publicó el algoritmo simplex para la resolución de problemas de programación lineal y formuló el enunciado general Ramos Pérez, Isabel María -10- X2 10 9 8 7 6 5 4 3 REGIÓN 2 FACTIBLE 1 0 X1 1 2 3 4 5 6 7 8 9 10 Gráfica 2.4. Solución Factible Que Maximiza La Función Objetivo. Fuente: Elaboración propia. Una solución óptima de x1=2 y x2=4 con un valor de la función de Z=32, indica que la empresa debe fabricar a la semana dos lotes del producto 1 y cuatro lotes del producto 2, con una ganancia total de 32.000€ a la semana. Es recomendable la utilización del método gráfico para resolver un problema lineal siempre y cuando existan sólo dos variables de decisión. 2.5 ALGORITMO DE RESOLUCIÓN: MÉTODO SÍMPLEX. 2.5.1 Introducción. El algoritmo de resolución de los problemas de programación lineal, el más destacado, tanto por su importancia histórica como por su utilización, es el método simplex. El método simplex fue desarrollado por Dantzig a mediados del siglo XX, aunque no alcanzó la popularidad que actualmente tiene hasta el desarrollo de los ordenadores. Este método es el algoritmo estándar de resolución de problemas de programación lineal. Es un procedimiento iterativo que comienza por buscar una solución básica factible que, si es posible, es el origen de coordenadas. En cada iteración, se mueve de la solución básica factible actual a una mejor solución básica factible adyacente (este movimiento siempre se produce por una arista de la frontera de la región factible). Continuará este proceso (de pasar de una solución actual a otra adyacente) hasta llegar a la solución óptima. En la gráfica 2.5 se muestran las iteraciones que efectúa el método simplex hasta llegar a la solución óptima. Se inicia la iteración en el origen (punto A), donde x1 = 0 y x2 = 0, y cuyo valor objetivo Z es igual a cero. Una vez examinado el punto A, al no ser una solución óptima (porque se puede mejorar), se itera al punto B y así sucesivamente, hasta llegar a la solución factible que maximice o minimice la función objetivo (solución óptima). 32 =4x1 + 6x2 (2,4) TFG-FICO. Aplicaciones de la Programación Lineal: El Problema de Transporte. -11- Gráfica 2.5 Iteración del Método Simplex. Fuente: Elaboración propia. Cuando el origen es factible, se deberá seguir los pasos que se describen en el siguiente apartado, pero si el origen no es factible, existen algoritmos de búsqueda de una solución básica factible inicial, como el método de la doble fase y el método de penalizaciones. En la gráfica 2.5, se puede observar que el origen es factible porque pertenece a la región factible. 2.5.2 Formulación Matemática del Método Simplex. Para empezar a utilizar el método simplex hay que convertir las restricciones funcionales de desigualdad en restricciones de igualdad equivalentes. Esta conversión se logra mediante la introducción de las variables de holgura. Sea la formulación estándar de un problema de programación lineal: Max z = ct x s. a, Ax = b x ≥ 0 donde A es una matriz de orden mxn, c y x son vectores con n componentes y b es un vector con m componentes, con m<n. La matriz A se parte en dos matrices, una, B, con m vectores lineales independientes y la otra, N, con n-m vectores linealmente dependientes A = [B, N]. Si se considera una solución básica factible del problema, x0, asociada a una base B, y el conjunto de índices de las variables I = {1,2,…., n} siendo I=IBυIN, de esta forma puede escribirse: x0 = B-1 b Ө Sea z0 el valor de la función objetivo en x0, y consideremos el vector c particionado cB como c = cN . En estas condiciones se tiene que: X2 10 9 8 7 6 5 4 B C 3 2 D 1 0 A X1 1 2 3 4 5 6 7 8 9 10 (2,4) El origen de coordenadas es una solución factible. Ramos Pérez, Isabel María -12- zo = ct x0 = (cBt , cNt) B-1 b = cBt B-1b Ө xB Por otra parte una solución factible arbitraria, x puede considerarse como x = xN donde xB≥Ө, xN≥Ө, y b = Ax= BxB + NxN. Multiplicando por la inversa de B y denotando por Pj, donde j= 1,2,….,n a las columnas de la matriz de A, se obtiene: xB= B-1 b – B-1 NxN = B-1 b- ΣB-1 Pjxj jЄIN Y el valor de la función objetivo en x, se escribe como: z = ct x = ctB xB + ctN xN = ctB (B-1 b- ΣB-1 Pjxj) + Σcjxj = cBtB-1b + Σ(cj –cBtB-1Pj)xj jЄIN jЄIN jЄIN Denotando zj = z0 + Σ (cj - zj)xj, donde jЄIN, se obtiene: z = z0 + Σ(cj - zj)xj jЄIN La expresión de z proporciona una guía en el proceso de mejora de la solución básica factible x0. Los valores cj - zj representan el rendimiento marginal de las variables no básicas. Esta diferencia recoge el rendimiento directo de la variable cj, y el rendimiento indirecto es recogido por zj, resultando del reajuste del resto de las variables al hacer positivo el valor de la variable xj, a esto se le denomina costes reducidos. Si cj - zj ≤ 0, la solución x0 no es mejorable, por lo que es óptima. Es posible aumentar el valor de la función objetivo si ck – zk> 0, para ello hay que aumentar el valor de alguna variable no básica, jЄIN, tal que cj – zj > 0, que actualmente tiene valor cero. Como se expresó al principio, este método propone pasar de la solución básica factible actual, a otra solución básica factible en las que las variables no básicas seguirán tomando valor cero. Para aplicar este logaritmo, se utiliza tablas como la que se muestra a continuación: cB cN cB I=B-1B B-1N B-1b Ө cNt - cBt B-1N cBt B-1b Tabla 2.3.Tabla Simplificada del Método Simplex. Fuente: Elaboración a partir de Arévalo et al (2005, pp. 149). Cada tabla está asociada a una base. En dicha base se ha de representar las coordenadas de las columnas de la matriz del sistema, por lo que en los lugares correspondientes a la base están las columnas de la matriz identidad. En la última fila se escriben los costes reducidos y el valor de la función objetivo en la solución básica factible. Las columnas no básicas son los vectores B-1Pj, y en la columna de la derecha aparecen los valores de las variables básicas xB= B-1b. A partir de la anterior tabla, es posible cambiar de base. Sólo hay que realizar transformaciones elementales sobre las filas. Se pasará a una tabla que representa un punto extremo adyacente. TFG-FICO. Aplicaciones de la Programación Lineal: El Problema de Transporte. -13- Al realizar la actualización de la tabla a través de transformaciones elementales, la matriz B-1 se encuentra en la tabla asociada a la solución básica factible en las columnas correspondientes a la base canónica de la tabla inicial. Para determinar si esta es solución óptima hay que comprobar si cjzj ≤ 0. En caso contrario, si cjzj ≥ 0, se elegirá el mayor (para el caso de maximizar o menor para el caso de minimizar), y se examinará la columna a la que pertenece (columna pivote). Se elegirá de esa columna el número denominado elemento pivote. La fila pivote tendría que salir por completo de la tabla y entraría otro Pn+m de las variables originales. Este proceso de intercambio se basa en las operaciones de filas de Gauss- Jordan. Identifica la columna de la variable de entrada como columna pivote y la fila de la variable de salida como fila pivote. La intersección de la columna pivote se conoce como elemento pivote. De forma abreviada, se puede decir que habrá que elegir la columna Pk correspondiente a aquella variable de xk con mayor valor ck – zk> 0. Como ck – zk> 0, si conviene aumentar xk todo lo posible. Al aumentar el valor de esta variable, las variables básicas se modifican para conservar la factibilidad según la siguiente ecuación: XB= B-1 b- ΣB-1 Pjxj = B-1 b – B-1 Pkxk jЄIN Siguiendo a Arévalo et al (2005), esta ecuación se escribe por componentes como: xB1 b1 V1k - - - - = - - - xk - - - xBm bm Vmk donde b = B-1b y Vk = B-1Pk, se obtiene XB= b - Vkxk 1. Si Vk≤ Ө, el valor de xk puede crecer indefinidamente sin que ninguna de las variables básicas se haga negativa, por lo que la solución x, tal que XB=b - Vkxk, con xk arbitrariamente grande y todos los otros componentes no básicos nulas, es factible y su valor objetivo z = z0 + (ck - zk)xk tiende a infinito al crecer xk. Este es el caso de un problema ilimitado. 2. Si Vik>0, para algún i= 1,2,…,m entonces xBi decrece cuando xk crece. En este caso, xk puede aumentar hasta que alguna variable básica se haga nula. En esta variable básica, xBr, será aquella tal que bi/Vik sea mínimo para los Vik>0. De lo anterior, se obtiene que xk pasa a ser una variable básica con un valor mín1≤i≤m bi/Vik, siéndo Vik>0. Además, xBr deja de ser una variable básica. Todas las demás variables se reajustan según la expresión XB= b - Vkxk. Para darle entrada a este nuevo Pk, se tendrá que construir una nueva tabla, denominada tabla de salida. Para obtener la nueva solución básica factible, y reemplazarla, se prepara la base en dos pasos: 1. Fila pivote: Se realizará la siguiente operación: Nueva fila pivote = Fila pivote actual ÷ Elemento pivote. Ramos Pérez, Isabel María -14- 2. Para las demás filas: Nueva fila = Fila actual ± Coeficiente de la columna pivote x Nueva fila pivote (calculada en el punto 1) Para concluir con la formulación matemática, al principio se mencionó que el método simplex permite pasar de una solución básica factible a otra adyacente mejor. Este procedimiento se realiza mediante los criterios de entrada y salida en la base y los reajustes de las variables, se expresa de la siguiente forma: ENTRADA xi pasa a ser básica si k es tal que ck-zk = max1≤i≤m{ cj-zj , cj-zj >0} SALIDA xBr deja de ser básica si r es tal que bi = min1≤i≤m{ bi, Vik>0 } Vik Vik REAJUSTE KЄIN xk= bi/Vik rЄIN xBr = 0 iЄIN i≠r xB = b – Vkxk jЄIN j≠k xN = 0 La n-m variables nulas se conocen como variables no básicas. Las m variables restantes se llaman variables básicas y su solución se conoce como solución básica. El procedimiento de búsqueda del óptimo puede terminar de dos formas posibles: 1. Optimalidad. Si cj-zj ≤ 0, la solución básica factible actual no es mejorable, por lo que es una solución óptima. 2. Problema ilimitado. Si ck-zk > 0 y Vk ≤ ө, el valor de la función objetivo puede crecer de forma ilimitada. Este proceso de seguir construyendo tablas de salida terminará cuando todos los cj - zj sean nulos o negativos. El criterio de entrada del problema de minimización queda: ENTRADA xi pasa a ser básica si k es tal que ck-zk = maxjЄIN { cj-zj , cj-zj < 0} El criterio de salida y el reajuste de las variables no cambian. Para ver más claro todo el procedimiento efectuado anteriormente, se resolverá el ejemplo utilizado en el apartado 2.3 por el método simplex. Max 4 x1 + 6 x2 S. a, 2x1 ≤ 6 (Planta 1) 4 x2 ≤ 16 (Planta 2) 4x1 + 2x2 ≤ 16 (Planta 3) x1 ≥ 0, x2 ≥ 0 TFG-FICO. Aplicaciones de la Programación Lineal: El Problema de Transporte. -15- El primer paso es convertir todas las restricciones de desigualdad en restricciones de igualdad. Para ello debemos utilizar las variables de holguras: 2x1 + x3 = 6 4 x2 + x4 =16 4x1 + 2x2 + x5 =16 Las variables de holgura para este caso serán x3, x4 y x5. Por lo tanto, la primera tabla del simplex es la siguiente: P1 P2 P3 P4 P5 B CB 4 6 0 0 0 xB P3 0 2 0 1 0 0 6 P4 0 0 Pivote 4 0 1 0 16 P5 0 4 2 0 0 1 16 cj-zj 4 6 0 0 0 Z = 0 Tabla 2.4.Entrada método simplex. Fuente: Elaboración propia. En la Tabla 2.4 las variables básicas son x3, x4 y x5 y las variables no básicas son x1 y x2. Los valores de las variables son x1= 0, x2= 0, x3= 6, x4= 16 y x5= 16 con una función objetivo de Z = CB3 * XB3+ CB4 * XB4+ CB5 * XB5 = 0*6 + 0*16 + 0*16 = 0. Para determinar si esta es la solución óptima del problema, calculamos los valores cj-zj y se elige el mayor valor, que en este caso es el número 6. En la misma columna (columna pivote) a la que pertenece el número 6, se escogerá el valor aij tal que proporcione el menor valor de los cocientes entre las cantidades de la última columna (xB) y las dicha columna pivote, y en este caso es el 4 (elemento pivote). La fila (fila pivote) a la que pertenece el número 4. Por tanto, P4 tendrá que salir de la base, y entra en la base P2. En la Tabla 2.4 están marcadas la columna pivote y la fila pivote y el elemento pivote es el número 4. Veamos cómo le damos salida a P4 y entrada a P2, por medio del siguiente proceso: 1. La nueva fila pivote P2 = Fila pivote actual P4 ÷ Elemento pivote 4. 0/4 4/4 0/4 1/4 0/4 16/4 2. Fila P5 se puede mejorar y para ello en este caso se ha cogido la fila actual P5 menos dos veces la nueva fila pivote ya dividida por 4 (calculado en el anterior punto). 4 - 2*0 2 - 2*1 0 - 2*0 0 - 2*1/4 1 - 2*0 16 - 2*4 A continuación, en la Tabla 2.5 se muestra la tabla del algoritmo, una vez realizados los cálculos anteriores: Ramos Pérez, Isabel María -16- P1 P2 P3 P4 P5 B CB 4 6 0 0 0 xB P3 0 2 0 1 0 0 6 P2 6 0 1 0 1/4 0 4 P5 0 4 0 0 - 1/2 1 8 cj-zj 4 0 0 -1,50 0 Z = 24 Tabla 2.5.Salida método simplex. Fuente: Elaboración propia. Se puede observar que la estructura de la nueva Tabla 2.5 es similar a la de la tabla inicial. Para un valor de la función objetivo Z*= 24 (Z= CB3 * XB3+ CB2 * XB2+ CB5 * XB5 = 0*6 + 6*4 + 0*8 = 24) los valores serían, x1= 0, x2= 4, x3=6, x4= 0 y x5= 8. Una vez elaborada la Tabla 2.5, volvemos a repetir todo el proceso explicado anteriormente. Lo primero es ver el mayor valor de cj-zj, en este caso es el número 4, en la columna pivote elegimos el elemento pivote que es el 4 (el mayor). Por lo que P5 sale y entra P1. Este intercambio se hace mediante el mismo procedimiento. Una vez realizados todos los cálculos necesarios, se obtiene la siguiente la siguiente Tabla 2.6: P1 P2 P3 P4 P5 B CB 4 6 0 0 0 xB P3 0 0 0 1 1/4 - 1/2 2 P4 6 0 1 0 1/4 0 4 P1 4 1 0 0 - 1/8 1/4 2 cj-zj 0 0 0 -1 -1 Z* = 32 Tabla 2.6.Salida método simplex. Fuente: Elaboración propia. Los valores asociados a la Tabla 2.6 son x1= 2, x2= 4, x3= 2, x4= 0 y x5=0 con una función objetivo de 32000€ (Z*= CB3 * XB3+ CB2 * XB2+ CB1 * XB1 = 0*2 + 6*4 + 4*2 = 32) de beneficios. Dado que todos los valores cj-zj son nulos o negativos, ha finalizado la resolución del problema por el método simplex. La solución óptima es producir dos lotes del producto uno y cuatro lotes del producto dos. Pero, ¿cuál es el significado x3= 2? Esta variable de holgura nace en la restricción de x1 en la planta 1 y su verdadero significado es que el producto uno no consume todas las horas disponibles en la planta 1, ya que sobran dos horas de producción. 2.6 LINGO. Existen múltiples programas informáticos que resuelven problemas de programación lineal como: Solver, WinQSB, Tora y LINGO. De estos programas vamos a utilizar el programa LINGO. LINGO es un producto de LINDO Systems, Inc., que también comercializa un optimizador orientado por completo a hojas de cálculos llamado What´sbest! para grandes problemas industriales, así como una subrutina adicional llamada LINDO API. El software LINGO incluye un interfaz con el subprograma LINDO que ha sido una introducción popular a la programación lineal para muchas personas. TFG-FICO. Aplicaciones de la Programación Lineal: El Problema del Transporte -17- Este programa informático es una herramienta que ayuda a resolver modelos de optimización lineal y no lineal de forma rápida, fácil y eficiente. Incluye un potente lenguaje de modelado, un entorno completo para los problemas de construcción y edición, la capacidad de leer y escribir en Excel y bases de datos, y un conjunto de solucionadores incorporado. Imagen 2.1. Logotipo software LINGO. 2.6.1 Funcionamiento del programa LINGO. Este programa informático trabaja con dos clases de documentos: 1. Documentos con extensión .lg4: Aquí se introducen los datos del modelo a resolver. Este documento se crea en el menú File y se debe elegir la opción New. Una vez introducidos los datos, se puede guardar el documento en el menú File y Opción Save. Para escribir en este documento se ha de utilizar el lenguaje específico de LINGO. Se puede encontrar este lenguaje en el menú Edit. En la opción Paste Function se desplegarán varios comandos y funciones en lenguaje LINGO, y la opción Mathematical/Trigonometrical. Ahí se encuentran todas las funciones matemáticas como exponenciales, logaritmos, etc.... 2. Documentos con extensión .lgr: Este documento lo utiliza LINGO para escribir la solución. Lo más interesante de este documento, es que se pueden modificar los datos, borrar información no deseada, añadir explicaciones, comentarios, etc.… Ahora se mostrará cómo introducir los datos en LINGO, utilizando el ejemplo del apartado 2.3. El modelo matemático correspondiente al ejemplo es: Max 4 x1 + 6 x2 S. a, 2x1 ≤ 6 4 x2 ≤ 16 4x1 + 2x2 ≤ 16 x1 ≥ 0, x2 ≥ 0 La forma de escribirlo en LINGO para introducir los datos en el documento .lg4, será: [BENEFICIO]max=4*x+6*y; [PRODUCTO1]2*x<6; [PRODUCTO2]4*y<16; [PRODUCTO1Y2]4*x+2*y<16; Ramos Pérez, Isabel María -18- Los anteriores datos se han de introducir en LINGO de la siguiente forma: 1. Delante de la función objetivo se introduce Max= o Min=. 2. Las desigualdades ≤ y ≥ se escribe <= o >= aunque se puede abreviar a < o >. La igualdad se escribe sólo (=). 3. Nunca se pueden eludir los signos de multiplicación (*). 4. Cada instrucción ha de terminar con punto y coma (;) 5. Las etiquetas deben ir entre corchetes [ ], aunque son opcionales, sirven para poder relacionar la solución que proporciona LINGO. Estas no pueden contener espacios en blancos ni signos especiales. Sí pueden contener números, pero no pueden empezar por él. 6. LINGO no distingue entre mayúsculas o minúsculas. 7. Se pueden insertar comentarios, poniendo al principio un signo de exclamación (!) y acabarla con punto y coma (;). LINGO no leerá estas líneas. 2.6.2 Interpretación de los datos. Una vez abierto el programa LINGO, solo hay que introducir los datos como se muestra la figura 2.1: Figura 2.1. Introducción del Planteamiento en el Programa LINGO. Fuente: Elaboración Propia. Después de introducir los datos, para obtener la solución óptima basta con utilizar la opción solve , y se abrirá un cuadro de diálogo. La figura 2.2 muestra la solución óptima del problema, en la columna variable aparecen los valores para las variables: habría que producir dos lotes del producto 1 (x) y del producto 2 cuatro lotes (y). TFG-FICO. Aplicaciones de la Programación Lineal: El Problema del Transporte -19- Figura 2.2. Solución Problema de Programación Lineal Mediante el Programa LINGO. Fuente: Elaboración Propia. En la columna slack or surplus nos da que el valor óptimo de Z es 32, por lo que al producir los productos 1 y 2 en las cantidades expuestas anteriormente la empresa obtendrá un beneficio de 32000€. También aparecen los valores de las variables de holgura: la fila del producto 1, cuyo slack or surplus es de dos, indica que en la planta 1 sobran dos horas de producción. Las dos siguientes filas son cero por lo que en las plantas dos y tres no sobrarían horas de producción. 2.7 APLICACIONES. 2.7.1 Introducción. La programación lineal es una herramienta indispensable en la toma de decisiones (toma de decisión operativa y táctica en la gestión empresarial). Esta toma de decisiones se puede aplicar en todos los ámbitos relacionados con asuntos empresariales, industriales, agrícolas, de gestión, militares, ingeniería, medicina, etc.…. Por ejemplo, los campos de aplicación pueden estar relacionados con marketing, producción, asignación de tareas, finanzas, logística, etc.…. La variedad de situaciones a las se pueden aplicar estas descripciones es sin duda muy grande, puede abarcar desde la asignación de instalaciones de producción de los productos hasta la asignación de los recursos nacionales a las necesidades de un país; desde la selección de una cartera de inversiones hasta la selección de los patrones de envío; desde la planeación agrícola hasta el diseño de una terapia de radiación, etc. No obstante, el ingrediente común de todas estas situaciones es la necesidad de asignar recursos a las actividades mediante la elección de los niveles de éstas. Ramos Pérez, Isabel María. -26- Para ilustrar el estudio del un problema de transporte, se planteará el siguiente caso práctico: La empresa Mantecosa S.L, dedicada a la fabricación y distribución de mantecados, cuenta con dos fábricas una ubicada en Sevilla y la otra en Almería, y tres centros de distribución: Granada, Huelva y Córdoba. La fábrica de Sevilla tiene disponibles 8000 kilos de mantecados, mientras Almería tiene unas existencias de 6000 kilos de mantecados. Se estima que la demanda de cada centro de distribución es de 3000 kilos para Granada, 4000 kilos para Huelva y 7000 kilos para Córdoba. Por otro lado, los costes de transporte unitarios asociados desde cada fábrica hasta cada centro de distribución se detallan a continuación: GRANADA HUELVA CÓRDOBA SEVILLA 15 11 8 ALMERÍA 7 14 12 Tabla 3.2.Coste Unitario de Transportar desde los Orígenes hasta los Destinos. Fuente: Elaboración Propia. Se desea saber qué cantidad de kilos de mantecados se debe enviar desde las fábricas a cada uno de los centros de distribución, de tal forma que los costes de envío sean mínimos. Se empieza planteando el problema de transporte de la siguiente forma: Las variables xij representan el número de unidades que se distribuyen del origen i al destino j, donde i= 1,2 y j=1,2,3. En la Tabla 3.2 se tienen los costes unitarios cij por trasladar del origen i al destino j, entonces la función que representa los costes de transporte de todas las unidades estará dada por la función objetivo: m n Z= Σ Σ cij xij = 15x11 + 11 x12 + 8 x13 + 7 x21 + 14 x22 + 12 x23 i=1 j=1 Por otra parte, se comprueba que la oferta (s) sea igual a la demanda (d), es decir: m n Σ si = Σ dj i=1 j=1 2 Σ si = 8000 + 6000 =14000 i=1 3 Σ dj = 3000 +4000 + 7000 = 14000 j=1 Los kilos de mantecados que pueden ser enviados desde cada fábrica a cada centro de distribución xij, deben cumplir las restricciones de la oferta: 3 Σ x1j = x11 + x12 + x13 = 8000 j=1 3 Σ x2j = x21 + x22 + x23 = 6000 j=1 TFG-FICO. Aplicaciones de la Programación Lineal: El Problema de Transporte. -27- Por otro lado, las restricciones de la demanda que tiene cada centro de distribución se expresan mediante las igualdades: 2 Σ xi1 = x11 + x21 = 3000 i=1 2 Σ xi2 = x12 + x22 = 4000 i=1 2 Σ xi3 = x13 + x23 = 7000 i=1 3.3 ALGORITMO DE RESOLUCIÓN. Existen varios métodos para obtener una solución básica factible para un modelo de transporte: método de la esquina noroeste, método de Vogel y método de costo mínimo. Posteriormente para llegar a la solución óptima factible, se deberá utilizar uno de los siguientes: método del banquillo o método de los multiplicadores (modi). Tanto por su importancia como por su facilidad, se explicará el Método de la Esquina Noroeste para obtener la solución básica y posteriormente el Método Modi para calcular la solución óptima. El método de la esquina noroeste toma como punto de partida una matriz con orígenes, destinos, ofertas y demandas, tal y como se mostró en la Tabla 3.1. Antes de construir la tabla, hay que verificar que la oferta total sea igual a la m n demanda total Σ si = Σ dj, o lo que es lo mismo, que el problema esté equilibrado. i=1 j=1 Una vez construida la tabla inicial con oferta o demanda artificial (si el problema no está equilibrado), el procedimiento para obtener una solución básica factible mediante el método de la esquina noroeste, se tendrá que seguir los siguientes pasos: 1. En la casilla de la celda (1,1), que es la celda de la esquina noroeste de la tabla, habría que asignar tantas unidades de producto como sea posible. Hay que tener en cuenta que no exceda de la demanda ni de la oferta. 2. Cancelar la fila o columna que ha quedado satisfecha, ajustar la oferta o la demanda que no haya sido satisfecha. 3. Si en el paso 2 se ha cancelado una columna, hay que desplazarse a la celda de la derecha y si se ha cancelado una fila, se desplazará hacia la celda de abajo. En ambos casos se asignarán tantas unidades como sea posible. Después se deberá cancelar la fila o columna satisfecha y ajustar la oferta y la demanda. Este proceso se repetirá hasta terminar o completar la tabla. Las celdas con unidades asignadas se denominan celdas básicas y las restantes son denominadas celdas no básicas. Los valores obtenidos en las celdas básicas corresponden a los valores de las variables xij. Al sustituir en la función objetivo la variable xij por su valor, se obtiene el coste total de distribuir los productos. 4. La tabla obtenida es una solución básica factible, aunque puede ser que esta solución no sea óptima. Para determinar si es óptimo, se debe calcular los costes marginales de las celdas no básicas. Al calcular los costes marginales, si estos son positivos la solución es una solución óptima factible; si por el contrario, todos o algunos de ellos son negativos la solución aunque es factible Ramos Pérez, Isabel María. -28- no es óptima. Para averiguar si la solución es óptima se utilizará el método modi. A partir de la tabla inicial calculada por el método de la esquina noroeste se ha obtenido una solución básica factible. Ahora, mediante el método modi, se llegará a la solución óptima. El método modi calcula los costes marginales de las celdas nulas del siguiente modo: 1. Calcular los multiplicadores ui y vj (fila i y de la columna j) y los costes marginales, cm, para cada variable básica xij. Los multiplicadores ui y vj están asociados a toda celda básica, su expresión es: Celda (i,j) ui + vj = cij Los valores de los multiplicadores se obtienen suponiendo un valor arbitrario para uno de los multiplicadores y se calcula el resto. Los costes marginales asociados a todas las celdas no básicas: Celda (i,j) cm = cij - ui - vj 2. Si todos los cm son positivos, la tabla inicial es una solución factible óptima y el proceso habrá terminado. Si alguno de los cm es negativo, la solución factible no es óptima. Entonces se deberá proceder de la siguiente forma. Se elegirá la celda con mayor valor negativo, se creará un circuito y se hará que las celdas no básicas pasen a ser básicas, y a su vez que las básicas pasen a ser no básicas. Se creará un circuito donde todas las celdas han de ser celdas básicas (lo que significa que la trayectoria del circuito ha de tener variable básica y así encontrar la trayectoria de la variable no básica que entrará en la solución), aunque el punto de partida no es una celda básica. El circuito empieza y termina en la celda no básica designada. 3. Se deberá ajustar el valor de las variables básicas de xij en las celdas del circuito, para satisfacer las restricciones de la oferta y de la demanda. Se comenzará por sumar la variable Ө a la celda seleccionada en el punto 2 (cm más negativo) y en el sentido de las agujas del reloj habrá que ir alternando restar y sumar Ө en cada celda de la trayectoria, hasta regresar a la celda primera. Después, resolver para cada Ө y ajustar la solución. Para determinar el valor de Ө, hay que tener en cuenta que el valor de la variable xij debe ser mayor o igual a cero. Se le dará el mayor valor posible a Ө, resolver el sistema de desigualdades xij ± Ө ≥ 0, despejar Ө y elegir el valor máximo, sustituir Ө por su valor en la tabla y resolver para ajustar la solución. 4. En esta nueva tabla obtenida, habrá que determinar si es una solución óptima factible, para ello se volverá a empezar todo el método descrito anteriormente del punto 1 al 3. Para mostrar todo el procedimiento efectuado anteriormente, se resolverá el caso práctico de Mantecosa S.L, del apartado anterior. El planteamiento del problema de transporte es el siguiente: TFG-FICO. Aplicaciones de la Programación Lineal: El Problema de Transporte. -29- m n Min Z= Σ Σ cij xij = 15x11 + 11 x12 + 8 x13 + 7 x21 + 14 x22 + 12 x23 i=1 j=1 3 s.a, Σ x1j = x11 + x12 + x13 = 8000 j=1 3 Σ x2j = x21 + x22 + x23 = 6000 j=1 2 Σ xi1 = x11 + x21 = 3000 i=1 2 Σ xi2 = x12 + x22 = 4000 i=1 2 Σ xi3 = x13 + x23 = 7000 i=1 xij ≥ 0, para toda i y j Una vez planteado el problema de transporte, lo primero es construir lo que se denomina tabla inicial. Esta tabla inicial concentra toda la información de los costes unitarios de transporte de todos los orígenes a todos los destinos, la oferta y la demanda de cada origen y destino. La tabla inicial nos sirve para determinar los valores de las variables de decisión. Los pasos a seguir para construir esta tabla inicial con la que se obtiene una solución factible son: 1. Verificar que la oferta y la demanda son iguales. 2. La tabla debe contener i filas y j columnas, donde i es el número de orígenes y j es el número de destinos. 3. En la intersección de cada fila y columna, debe aparecer el coste de transportar una unidad desde el origen al destino. 4. En la columna oferta se pondrá la oferta de cada origen y en la fila demanda se pondrá la demanda de cada destino. De esta forma, se construye la Tabla 3.3 inicial del problema de transporte. Para obtener una solución básica factible se utilizará el método de la esquina suroeste. Este método se basa en asignar a la celda (1,1) la mayor cantidad posible entre 3000 y 8000, en este caso 3000, se cancela (2,1) debido a que la demanda ya está satisfecha. Al cancelarse una columna, este método obliga a trasladarse a la celda (1,2), y volvemos a hacer lo mismo, le asignamos tantas unidades como sea posible entre 4000 y 5000 (como diferencia entre 8000-3000) y así sucesivamente. Ramos Pérez, Isabel María. -30- Origen Costo por unidad distribuida Oferta Destino GRANADA HUELVA CÓRDOBA SEVILLA 15 11 8 8000 3000 4000 1000 ALMERÍA 7 14 12 6000 0 0 6000 Demanda 3000 4000 7000 Tabla 3.3. Solución Básica Factible del Método de la Esquina Noroeste. Fuente: Elaboración Propia. Los valores asociados a la Tabla 3.3 son x11=3000, x12=4000, x13=1000 y x23=6000, con un Z= 3000x15 + 4000x11 + 1000x8 + 6000x12= 169000€. Una vez obtenida la solución básica factible, se debe comprobar si es una solución óptima. Para ello hay que calcular los costes marginales de las celdas nulas o celdas no básicas. En este caso, se utilizará el método de los multiplicadores (modi). Calculamos los multiplicadores ui y vj, donde ui + vj = cij, se obtiene: u1 + v1 = 15 u1 + v2= 11 u1 + v3= 8 u2 + v3 =12 Se supone un valor arbitrario para u1 = 0 y se calcula el resto: v1 = 15 v2= 11 v3 = 8 u2 = 4 Los costes marginales asociados a las celdas no básicas cm = cij - ui - vj, es: Celda (2,1) cm = c21 – u2 – v1 = 7 – 4 – 15 = -12. Celda (2,2) cm = c22 – u2 – v2 = 14 – 4 – 11= -1 Al ser los costes marginales negativos, esta solución básica factible no es solución óptima. Se elegirá la celda de mayor coste marginal en valor absoluto, en este caso (2,1) y le sumamos Ө hacemos en el sentido de las agujas del reloj un circuito alternando +Ө y –Ө, como se observa en la Tabla 3.4 (con esto se consigue ajustar las xij). TFG-FICO. Aplicaciones de la Programación Lineal: El Problema de Transporte. -31- Origen Costo por unidad distribuida Oferta Destino GRANADA HUELVA CÓRDOBA SEVILLA 15 11 8 8000 3000 - Ө 4000 1000 + Ө ALMERÍA 7 14 12 6000 0 + Ө 0 6000 - Ө Demanda 3000 4000 7000 Tabla 3.4. Ajustar las xij, Siguiendo el Circuito de las Flechas. Fuente: Elaboración Propia. Para obtener el valor de Ө, se plantea un sistema de desigualdades: Ө ≥ 0 3000 - Ө ≥ 0 1000 + Ө ≥ 0 6000 - Ө ≥ 0 El valor máximo que satisface todas las desiguales de Ө es 3000, por lo que se procede a realizar los ajustes en las celdas sustituyendo Ө por 3000, obteniendo la siguiente Tabla 3.5: Origen Destino Oferta GRANADA HUELVA CÓRDOBA SEVILLA 15 11 8 8000 0 4000 4000 ALMERÍA 7 14 12 6000 3000 0 3000 Demanda 3000 4000 7000 Tabla 3.5. Nueva Solución Básica Factible. Fuente: Elaboración Propia. Volvemos a repetir el procedimiento, para ver si la Tabla 3.5 es una solución óptima. Los multiplicadores son: u2 = 0, v1 = 7, v2= 15, v3 = 12 y u1 = -4. Los costes marginales asociados: Celda (1,1) cm = c11 – u1 – v1 = 15 – (- 4) – 7= 12. Celda (2,2) cm = c22 – u2 – v2 = 14 – 0 – 15= -1. Ramos Pérez, Isabel María. -32- La Tabla 3.5 no es una solución óptima, los costes marginales asociados a la celda (2,2) son negativos. Se vuelve hacer el circuito alternando +Ө y –Ө, empezando por la celda (2,2). El mayor valor de Ө que es 3000. Se obtiene la solución básica factible que se indica en la Tabla 3.6: Origen Destino Oferta GRANADA HUELVA CÓRDOBA SEVILLA 15 11 8 8000 0 1000 7000 ALMERÍA 7 14 12 6000 3000 3000 0 Demanda 3000 4000 7000 Tabla 3.6. Nueva Solución Básica Factible. Fuente: Elaboración Propia. Comprobamos si la Tabla 3.6 es una solución óptima. Los multiplicadores son: u1 = 0, v1 = 4, v2= 11, v3 = 8 y u2 = 3. Los costes marginales asociados son: Celda (1,1) cm = c11 – u1 – v1 = 15 – 0 – 4 = 11. Celda (2,3) cm = c22 – u2 – v2 = 14 – 3 – 18= 1. Al ser los costes marginales positivos, la Tabla 3.6 es una solución óptima, con x12=1000, x13=7000, x21=3000 y x22=3000, con un Z= 1000x11 + 7000x8 + 3000x7 + 3000x14= 82300€. Esto quiere decir que la fábrica de Sevilla ha de transportar al centro de distribución de Huelva 1000 kilos de mantecados y 7000 kilos de mantecados para el centro de distribución de Córdoba. La fábrica de Almería debe enviar 3000 kilos de mantecados a cada uno de los centros de distribución de Granada y Huelva. El coste de transportar las mercancías desde los orígenes a los destinos es de 130000€. El organigrama de la solución óptima es: 3000 3000 8000 1000 4000 3000 6000 7000 7000 Organigrama 3.1. Solución Óptima para la Distribución de los Productos de Mantecosa. Fuente: Elaboración Propia. SEVILLA ALMERÍA HUELVA CÓRDOBA GRANADA TFG-FICO. Aplicaciones de la Programación Lineal: El Problema de Transporte. -33- 3.4. SOFTWARE. Para la resolución de problemas de transporte los programas más comunes son: Excel, LINGO, LINDO, WINQBS y MPL/CPLEX. WINQSB 2.0 es un paquete de herramientas muy versátil que permite el análisis y resolución de modelos matemáticos, problemas administrativos, de producción, proyectos, inventarios, transporte, entre muchos otros. "Linear and integer programming “ es el módulo de WINQSB creado con el fin de resolver problemas de programación lineal y programación lineal entera. Imagen 3.1. Logotipo software WINQSB. Una vez instalado el programa informático WINQSB 2.0, nos deberá aparecer una carpeta con el nombre WINQSB, al abrirla nos aparecen las siguientes imágenes: Figura 3.1. Opciones de Cálculo del Programa WINQSB. Fuente: Elaboración Propia. Para resolver este tipo de problema hay que escoger la opción linear and integer programming (marcada en gris). Para empezar a trabajar con los datos, en la ventana de inicio seleccionamos el botón o desde el menú file y después new problema. Para identificar las variables e introducir los datos de nuestro problema de transporte, nos aparecerá el siguiente cuadro de diálogo: Ramos Pérez, Isabel María. -34- Figura 3.2. Elección del Número de Variables, Restricciones y Objetivo del problema. Fuente: Elaboración Propia. La figura 3.2 muestra cómo ha de introducirse los datos. Hay que introducir el número de variables, en nuestro caso 6. El número de restricciones, en este caso 5. El criterio de la función objetivo es minimización. Para el formato de entrada de los datos (data entry format) se recomienda utilizar la opción spreadsheet matrix form, ya que con esta opción se introducen los datos de forma matricial (como se muestra en la siguiente figura). En el tipo de variable (default variable type), la mejor opción para nuestro caso son las variables enteras no negativas. Una vez realizado todo lo anterior, aparece el siguiente cuadro: Figura 3.3. Cuadro para Introducir los Datos del Problema. Fuente: Elaboración Propia. En la primera fila aparecen los valores de la función objetivo. Las restricciones de la función objetivo están recogidas a continuación. LowerBound es el mínimo valor que puede tomar la variable. UpperBound es el máximo valor que puede tomar la variable, donde M es un valor predeterminado y significa un número muy grande. R. H. S. representa el lado derecho de la restricción. Para obtener la solución, seleccionamos la opción solve and analize y nos aparecerá el siguiente cuadro de diálogo. Una vez que aceptamos, aparece la solución óptima del método de transporte: TFG-FICO. Aplicaciones de la Programación Lineal: El Problema de Transporte. -35- Figura 3.4. Opción Óptima Obtenida por del Programa WINQSB. Fuente: Elaboración Propia. Interpretar cada uno de los valores del cuadro anterior, es más importante que obtener la solución óptima, dado que de dicha interpretación podremos extraer un buen análisis de los resultados: Solution value: Valor de la solución, es el valor que toman las variables de decisión en la solución óptima, en este caso nos indica que la fábrica de Sevilla ha de transportar al centro de distribución de Huelva 1000 kilos de mantecados y 7000 kilos de mantecados para el centro de distribución de Córdoba. La fábrica de Almería debe enviar 3000 kilos de mantecados a cada uno de los centros de distribución de Granada y Huelva. Unit Cost or Profit: Es el coste unitario de transportar desde el origen i hasta destino j. Total Contribution: Es el coste total de transportar desde el origen i hasta destino j. Se obtiene, al multiplicar el valor de una variable por el coste unitario. Objective Function: Muestra el resultado de la función objetivo, en este caso la solución óptima tiene una función objetivo de 130000€. Por lo tanto, es el coste total de transportar los mantecados desde las dos fábricas hasta los tres centro de distribución. Ramos Pérez, Isabel María. -42- Por lo tanto, el coste total que la empresa soportaría sería de 48927,37euros. Si comparamos la forma actual que la empresa distribuye sus naranjas con los obtenidos mediante el problema de transporte, se aprecia una distribución totalmente distinta, y el coste de transporte ha disminuido en 1813,06 euros (48927,37€ - 47114,31€). TFG-FICO. Aplicaciones de la Programación Lineal: El Problema de Transporte. -43- CAPÍTULO 5 CONSIDERACIONES FINALES. La programación lineal abarca cualquier tipo de problema que pretenda asignar de la mejor forma posible (de forma óptima) los recursos limitados a actividades que compiten entre sí por ellos. Por lo tanto, es tan amplia su utilidad que se puede aplicar a cualquier actividad empresarial. Aunque es una herramienta muy importante para solucionar problemas, su uso tiene algunas ventas y desventajas:  Ventajas de la programación lineal: 1. Aumenta la rentabilidad de la empresa, mediante una reducción de los costes o un aumento en los beneficios. 2. Es un método eficiente para la resolución de problemas de gran envergadura. 3. Se pueden utilizar los programas informáticos que resuelven rápidamente los problemas.  Desventajas de la programación lineal: 1. No tiene en cuenta otros factores que le pueden afectar a la hora de tener la solución. 2. Sólo se pueden resolver problemas cuyas ecuaciones sean lineales. 3. A la hora de recopilar los datos algunos puede difíciles o cuantiosos de obtener. 4. La formulación es difícil de entender si no se tiene buenos conocimientos en matemáticas. Por otra parte, el algoritmo de resolución es una herramienta útil para la toma de decisiones sobre la forma más eficiente de transportar, al menor coste posible, como se pone de manifiesto en el estudio realizado. Esta herramienta tiene otras utilidades como: decidir si alguno de los orígenes o destinos ha de ser eliminado o por el contrario, hay que añadir un nuevo centro de origen o destino, y también, se puede usar para elegir entre distintos medios de transportes. En el análisis de la empresa realizado en el capítulo anterior se observa, que si la empresa no tuviera tanto poder de negociación y asumiera los gastos de transporte, el empresario estaría pagando un 3,71% más en transportar sus productos. Por lo tanto, al aplicar el problema de transporte la empresa reduciría su coste total anual de transporte en 1813,06 €. De este modo, la programación lineal es una herramienta funcional, aplicable a múltiples problemas que aparecen en la realidad empresarial y cotidiana de cualquier tipo de sociedad, siendo imprescindible para gestionar una sociedad, ya que facilita la toma de decisiones. Ramos Pérez, Isabel María. -44- TFG-FICO. Aplicaciones de la Programación Lineal: El Problema de Transporte. -45- Bibliografía Arévalo, M.T.; Camacho, E.; Mármol, A.; Monroy, L. (2005): Programación Matemáticas para la Economía, Delta, Publicaciones Universitarias, Madrid. Brennier, Y. (2003): “Extended Monge–Kantorovich theory,” Lecture Notes in Math, 1813, 91- 122. Dantzig, G.B. (1948):"Linear Programming," in Problems for the Numerical Analysis of the Future, Proceedings of Symposium on Modern Calculating Machinery and Numeri-cal Methods, UCLA, July 29-31, , Appl. Math., Series 15, National Bureau of Standards, June 1951, pp. 18-21. Dantzig, G.B. (1963): Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 627. Fourier, J. (1826): Solution d’une question particulière du calcul des inégalités, Nouveau Bulletin des Sciences par la Societé philomatique, Paris. Hammond, F.; Sydsaeter, K. (2006): Essential Mathematics for Economic Analysis, Prentice Hall, England. Hillier, F.S.; Lieberman, G.J. (2010): Introducción a la Investigación de Operaciones, Mc Graw Hill, México. Hitchcock, F. L. (1941): The Distribution of a Product from Several Sources to Numerous Localities, American Mathematical Society, EEUU. Kantorovich, L.V. (1939): Mathematical Methods for Production Organization and planning, Leningrad Leningrad State University, Russia. Kantorovich, L.V. (1940): On a Efficient Methods for Solving some classes of extre-mun problems, Doklady, 28, (3), 212-215. Karmarkar, N. (1984): “A New Polynomial Time Algorithm for Linear Programming” Combinatorica, 4, (4), 373-395. Khachiyan, L. (1979): “A Polynomial Algorithm in Linear Programming”, Doklady, 244, (5), 1093- 1096. Koopmans, T.C. (1942): Exchange Ratios between Cargoes on Various Routes: Non- Refrigerated Dry Cargoes), Memorandum for the Combined Shipping Adjustment Board, Washington D.C. Monge, G. (1781): Mémoire sur la Théorie des Déblais et de Remblais. Histoire de l’Académie des Sciences de Paris, avec les Mémories de Mathématique et de Physique pour la Même Anneé, Registres de Cette Académie, 666-704. Neumann, J. V. (1928): “Theorie der Gesellschaftsspiele”, Mathematische Annalen, 100, 295- 320. Prawda, J. (2004): Métodos y Modelos de Investigación de operaciones: Modelos Determinísticos l, Limusa, México. Rufián-Lizana, A.; Ruiz-Garzón, G.; Osuna-Gómez, R. (2011): Métodos de Optimización Matemática: Manual para la resolución de problemas de optimización aplicados a la toma de decisiones empresariales, Alvalena, Sevilla. Ruiz-Garzón, G. (2013): Métodos cuantitativos para la toma de decisiones empresariales: Ejercicios, Servicio de Publicaciones de la Universidad de Cádiz, Cádiz. Stigler, G.F. (1945): ``The Cost of Subsistence´´, Journal of Farm Economics, 27, (2), 303-314. Taha, H.A. (2012): Investigación de Operaciones, Pearson Educación, México. Winston, W.L. (1987): Operations Research: Applications and Algorithms, PWS-KENT, Publishing Company, Boston. Ramos Pérez, Isabel María. -46- TFG-FICO. Aplicaciones de la Programación Lineal: El Problema de Transporte. -47-