Blog sobre la Gestión e Investigación de Operaciones con tutoriales y ejercicios resueltos.
Categoría: Programación Lineal
Programación Lineal. Ejercicios resueltos de Programación Lineal, Método Simplex, Método Simplex de 2 Fases, Método Simplex Dual, Dualidad en Programación Lineal, Análisis de Sensibilidad o Postoptimal. Tutoriales en Excel de Solver, What’sBest! y OpenSolver.
En la aplicación del Método Simplex al hacer el cálculo del mínimo cuociente o condición de factibilidad, se puede romper un empate en la razón o cuociente mínimo en forma arbitraria. En este caso, al menos una variable básica será cero en la siguiente iteración, afirmándose en este caso que la nueva solución es degenerada. La implicancia práctica de dicha condición indica que el modelo tiene al menos una restricción redundante.
Solución Óptima Degenerada
Consideremos el siguiente modelo de Programación Lineal el cual resolveremos a través del Método Simplex y que de forma complementaria representaremos gráficamente con Geogebra:
Llevamos el problema anterior a su forma estándar de minimización, agregando y , como variables de holgura de las restricciones 1 y 2, respectivamente.
Que da origen a la siguiente tabla inicial del Método Simplex:
Para favorecer la rapidez de convergencia del algoritmo seleccionamos como la variable que ingresa a la base. A continuación calculamos el criterio de factibilidad (mínimo cuociente): (al existir empate seleccionaremos arbitrariamente la variable como aquella que deja la base. Luego se actualiza la tabla:
Ahora ingresa a la base. El criterio de factibilidad determina que: deja la base. Se realiza entonces una nueva iteración:
Se alcanza la solución óptima degenerada del problema lineal. Notar que . Como éste es un problema bidimensional, la solución está sobredeterminada y una de las restricciones es redundante tal como se corrobora en la representación gráfica:
En la práctica conocer que algunos recursos (como los asociados a una restricción) son superfluos puede ser valioso durante la implementación de la solución. Desde el punto de vista teórico, la degeneración tiene dos implicaciones: se genera el fenómeno de ciclos o círculos (es posible que el Método Simplex repita una serie de iteraciones sin mejorar el valor de la función objetivo, tal como se observo en el ejemplo anterior e incluso eventualmente nunca terminar los cálculos); el segundo aspecto teórico surge al examinar las iteraciones 1 y 2. Las dos, aunque difieren en la clasificación de las variables básicas y no básicas, producen valores idénticos para todas las variables y el valor objetivo ( ).
El siguiente artículo trata de un problema de planificación financiera el cual se aborda a través de la Programación Lineal y se resuelve computacionalmente haciendo uso del complemento Solver de Excel. En este contexto se presenta un problema de inversión en distintos instrumentos financieros en los cuales se planifica invertir al inicio de cada uno de los próximos 10 años (horizonte de planificación), considerando los siguientes montos disponibles al comienzo de cada año (independiente de los retornos obtenidos producto de las mismas inversiones en años anteriores).
Los instrumentos disponibles son:
Depósito a plazo (anuales) con un retorno de 4,5% anual.
Bono a 6 años plazo con retorno de 4,9% anual.
Bono a 9 años plazo con retorno de 5,2% anual.
Se busca formular un modelo de optimización que posea los mayores retornos al término del décimo año (o inicio del año 11). Para ello se propone el siguiente problema de Programación Lineal:
Problema de Planificación Financiera
Variables de Decisión: Se establecen las posibilidades de inversión en los distintos instrumentos financieros. Notar que dado el período de maduración de los mismos se define la factibilidad de invertir en ellos en cada uno de los años. Por ejemplo, como el depósito anual tiene una maduración de un año se puede invertir en él en cada uno de los años del período de planificación. No así, por ejemplo, con el Bono a 9 años plazo el cual se puede invertir sólo al inicio del año 1 y 2.
Función Objetivo: Se desea maximizar el dinero obtenido al finalizar el período de planificación correspondiente al término del año 10 (o inicio del año 11).
Restricciones: Para cada año se limita las posibilidades de inversión según los instrumentos disponibles, el presupuesto del período y el retorno de los instrumentos que ya maduraron. Por ejemplo, en el año 1 se puede invertir en cada una de las 3 alternativas respetando el presupuesto de MM$20. En el año 2 nuevamente se puede invertir en las 3 alternativas y el presupuesto disponible corresponderá a los MM$20 de dicho período (según se detalla en la tabla al inicio) y eventualmente se podrá hacer uso del retorno de la inversión del depósito anual realizado en el año 1. Si, por ejemplo, se invierte los MM$20 en el depósito anual a inicio del año 1, entonces el presupuesto disponible para el año 2 será: 20+1,045(20)=MM$40,9.
A continuación se presenta un extracto de los resultados que provee la implementación computacional del modelo anterior haciendo uso de Solver. Las celdas color amarillo corresponde a la solución óptima, alcanzando un valor óptimo de MM$402,64.
Es interesante analizar la estructura de la solución óptima alcanzada. En el año 1 y 2 se invierte la totalidad del presupuesto en el Bono a 9 años plazo; en los años 3, 4 y 5 se invierte de forma exclusiva en los bonos a 6 años plazo; finalmente del año 5 al año 10 se invierte en el depósito anual.
¿Quieres tener el archivo Excel con la resolución en Solver de este problema?. Recomiéndanos en Facebook, Google o Twitter utilizando la herramienta de redes sociales a continuación y accede de forma gratuita e inmediata a la descarga del archivo (el enlace de descarga con el nombre “Descarga el Archivo” se mostrará abajo una vez que nos hayas recomendado).
Las bodegas enfrentan requerimientos variables de almacenamiento de un mes a otro. Esto se explica entre otros factores por la estacionalidad y variabilidad de la demanda, cambio en los niveles de producción, retraso en el despacho de los productos, políticas de la empresa, etc. En la actualidad es común que las empresas externalicen la totalidad o parte del servicio de almacenamiento (bodegas) de modo que se utilizan instalaciones de un tercero para guardar productos de inventario. Una decisión relevante en este contexto es determinar cuánto espacio arrendar y por cuánto tiempo, de modo de satisfacer las necesidades de almacenamiento a un costo mínimo.
El siguiente ejemplo toma en cuenta esta situación y propone una política óptima de arriendo de espacio en bodega para una empresa para los próximos 5 meses. Se conoce cuanto espacio necesita en cada uno los próximos meses. Dado que los requerimientos son muy diferentes, podría resultar económico arrendar sólo lo necesario en cada mes de acuerdo a los requerimientos dados. Sin embargo, el costo total para arrendar de una vez por varios periodos consecutivos es más económico que hacerlo mes a mes sobre el mismo lapso de periodos, por lo tanto puede considerarse la opción de ir cambiando en el tiempo la cantidad de superficie arrendada al menos una vez pero no todo los meses, agregando nuevos periodos de arriendo y/o dejando los que expiraron su periodo. Los requerimientos (en miles de m²) y el costo total de arrendar en cualquier mes por periodos de uno, dos, tres, cuatro o cinco meses consecutivos (en $ por m²), se resumen en la siguiente tabla:
Formule y resuelva con Solver un modelo de Programación Lineal que minimice el costo total de arriendo, de modo de satisfacer los requerimientos por espacio en los próximos 5 meses.
Variables de Decisión:
Función Objetivo: Minimizar los costos asociado al arriendo de la bodega durante el período de planificación de 5 meses.
Restricciones:
Por ejemplo los requerimientos de 30 mil m² del primer mes (restricción 1) se pueden satisfacer con arriendos que se gestionan en el mes 1 por una duración de 1, 2, 3, 4 o 5 meses. Análogamente las necesidades del mes 2 (20 mil m²) se pueden enfrentar con arriendos planificados anteriormente (mes 1) con una duración de 2, 3 o 4 meses (notar que no tiene sentido arrendar por 5 meses en el mes 2) como también con arriendos gestionados en dicho período por 1, 2, 3 o 4 meses (se propone al lector seguir dicho razonamiento de modo de corroborar que las restantes restricciones son correctas).
A continuación se muestra un extracto de la resolución computacional del problema anterior haciendo uso de Solver de Excel:
La solución óptima consiste en arrendar 30 m² en el mes 1 por un total de 5 meses, luego en el mes 3 se arriendan 10 m² adicionales por sólo un período, para finalmente en el mes 5 arrendar 20 m² por un mes. De esta forma se satisfacen los requerimientos de espacio en bodega para cada mes del horizonte de planificación a un costo mínimo de $76.500 (valor óptimo).
¿Quieres tener el archivo Excel con la resolución en Solver de este problema?. Recomiéndanos en Facebook, Google+ o Twitter utilizando la herramienta de redes sociales a continuación y accede de forma gratuita e inmediata a la descarga del archivo (el enlace de descarga con el nombre “Descarga el Archivo” se mostrará abajo una vez que nos hayas recomendado).
El origen exacto de la Investigación de Operaciones no está del todo establecido. Algunos autores postulan que Charles Babbage (1791-1871) es el padre de la Investigación de Operaciones debido a su contribución en la investigación de los costos de transporte y sistemas de clasificación del correo en England’s universal Penny Post en el año 1840.
Sin embargo, usualmente se considera que la Investigación de Operaciones como disciplina se origina formalmente durante la Segunda Guerra Mundial (WWII) en los esfuerzos de los planificadores militares y científicos ingleses por apoyar los procesos de toma de decisiones propios de la guerra con una base analítica y cuantitativa. El objetivo era descubrir la forma más eficiente de utilizar los limitados recursos militares a través de la aplicación de técnicas cuantitativas.
En este contexto el Problema de la Dieta fue uno de las primeros problemas de optimización estudiados en el período de 1930 a 1940. Las fuerzas armadas norteamericanas deseaban suministrar una dieta saludable a sus soldados y al mismo tiempo minimizar el costo asociado a su prestación. La premisa era el alimento es un pertrecho (munición), no lo despedicies!. Uno de los primeros investigadores en estudiar el problema fue George Stigler quien hizo una conjetura de la solución óptima a través de la utilización de un método heurístico.
Una vez terminada la Segunda Guerra Mundial los conceptos de la Investigación de Operaciones son aplicados en otros contextos relacionados a los negocios, la industria y la sociedad. En la década de 1950 la Investigación de Operaciones evoluciona hacia una profesión, comenzándose a conformar las primeras sociedades nacionales del área, junto al nacimiento de revistas especializadas y departamentos académicos en las universidades. En 1955 se crea la Sociedad de Investigación de Operaciones en India siendo uno de los primeros miembros de la Federación Internacional de Sociedades de Investigación Operativa (International Federation of Operational Research SocietiesIFORS).
La industria petroquímica fue una de las primeras en adoptar ampliamente la Investigación de Operaciones para mejorar el desempeño de las plantas productivas. La empresa Chevron, líder mundial en la industria energética desarrolla un software llamado Petro destinado al apoyo del proceso de compra y mezcla de combustibles, alcanzando ahorros anuales del orden de 400 millones de dolares.
Actualmente la Investigación de Operaciones es utilizada a nivel mundial tanto en organizaciones publicas como privadas, además de ser un área activa de investigación académica. Al respecto algunos de los campos de acción más frecuentes son:
Gobierno Local (despliegue de servicios de emergencia, planificación de personal, etc)
Un listado actualizado de casos de éxito de la Investigación de Operaciones se puede consultar directamente desde el sitio web de INFORMS (Institute for Operations Research and the Management Sciences) teniendo la posibilidad de buscar aplicaciones específicas por sector industrial, área funcional de la empresa y beneficio alcanzado.
Queda de manifiesto el enfoque multidisciplinario de las áreas de aplicación donde la utilización de modelos de optimización son una contribución significativa a los complejos procesos de tomas de decisiones. Dichos modelos de optimización pueden ser tanto determinísticos como probabilísticos que actualmente son materias de estudios en cursos del área en carreras de pregrado y postgrado relacionadas a la Ingeniería Industrial y otras ingenierías afines.
La Investigación de Operaciones o Investigación Operativa (en inglés OR u Operations Research) es una disciplina que consiste en la aplicación de métodos analíticos avanzados con el propósito de apoyar el proceso de toma de decisiones, identificando los mejores cursos de acción posibles.
En este contexto la Investigación de Operaciones utiliza técnicas de modelamiento matemático, análisis estadístico y optimización matemática, con el objetivo de alcanzar soluciones óptimas o cercanas a ellas cuando se enfrentan problemas de decisión complejos. Se espera que las decisiones alcanzadas mediante el uso de un modelo de investigación operativa sean significativamente mejores en comparación a aquellas decisiones que se podrían tomar haciendo uso de la simple intuición o experiencia del tomador de decisiones. Lo anterior es particularmente cierto en aquellos problemas de naturaleza real complejos, que consideran cientos, incluso miles de variables de decisión y restricciones.
La Investigación de Operaciones se complementa con otras disciplinas como la Ingeniería Industrial y la Gestión de Operaciones. En términos estrictos un modelo de optimización considera una función objetivo en una o varias variables que se desea maximizar (por ejemplo el ingreso o beneficio asociado a un plan de producción) o por el contrario minimizar (por ejemplo los costos de una firma, el riesgo asociado a una decisión, la pérdida de un alternativa, etc). Los valores que pueden adoptar las variables de decisión usualmente están restringidos por restricciones que adoptan la forma de ecuaciones y/o inecuaciones que buscan representar las limitantes asociadas a la problemática.
El enfoque de la Investigación de Operaciones es el modelaje. Un modelo es una herramienta analítica que nos sirve para lograr una visión bien estructurada de la realidad. Así, el propósito del modelo es proporcionar un medio para analizar el comportamiento de las componentes de un sistema con el fin de optimizar su desempeño (identificar el mejor curso de acción posible).
Una visión esquemática del proceso asociado a la construcción de un modelo de optimización se presenta a continuación:
1. Definición del problema: Se debe definir el problema para el cual se busca proponer un curso de acción. ¿Es un problema relevante? ¿es posible tomar una buena decisión sin la necesidad de resolver un modelo de optimización? ¿cuáles son sus alcances? ¿cuáles son los factores que influyen en el desempeño del sistema?, etc. La calidad del modelo de optimización dependerá en gran parte de la asertividad en la definición del problema de decisión.
2. Construcción de un modelo: Un modelo de optimización considera necesariamente una abstracción o simplificación de la realidad. Por un lado se busca que el modelo sea representativo del problema real que se busca representar pero que al mismo tiempo sea simple de modo de favorecer su resolución haciendo uso de un algoritmo ad-hoc. Alcanzar este equilibrio no es trivial. Por ello ante un mismo problema puede existir más de un modelo de optimización que lo represente con distintos niveles de detalle y abstracción.
3. Solución del modelo: Una vez construido el modelo de optimización se deben identificar las alternativas de resolución para el mismo. Para ello se puede hacer uso de programas computacionales que utilizan algoritmos de resolución específicos dependiendo de las características del modelo. Por ejemplo, para resolver un problema de Programación Lineal (las variables de decisión se representan como funciones lineales tanto en la función objetivo como restricciones) se puede utilizar el Método Simplex.
4. Validación: Se verifica que la solución alcanzada cumpla con las condiciones (restricciones) impuestas al problema.
5. Implementación y control de la solución: Una vez verificada la solución se procede a su implementación. Cabe destacar que esto puede lugar a actualizaciones del modelo de optimización tanto en términos del modelo como el valor de los parámetros estimados. Por ejemplo, si el modelo de optimización corresponde a un Plan Maestro de la Producción (PMP) y se genera un cambio en el valor de la hora hombre de los trabajadores será necesario actualizar el valor del parámetro que representa dicho costo para posteriores instancias de resolución.
En la actualidad el uso de modelos de optimización es cada vez más frecuente en la toma de decisiones. Este mayor uso se explica, principalmente, por un mejor conocimiento de estas metodología en las diferentes disciplinas, la creciente complejidad de los problemas que se desea resolver, la mayor disponibilidad de software y el desarrollo de nuevos y mejores algoritmos de solución.
Las sub disciplinas más destacadas en la Investigación de Operaciones moderna son:
y 
, como variables de holgura de las restricciones 1 y 2, respectivamente.
como la variable que ingresa a la base. A continuación calculamos el criterio de factibilidad (mínimo cuociente): 
(al existir empate seleccionaremos arbitrariamente la variable 
ingresa a la base. El criterio de factibilidad determina que: 
. Como éste es un problema bidimensional, la solución está sobredeterminada y una de las restricciones es redundante tal como se corrobora en la representación gráfica:
