Programación No Lineal no Convexo

A diferencia de la Programación Lineal donde sus distintas aplicaciones corresponden a problemas de optimización convexos (situación que facilita la resolución computacional), en Programación No Lineal no existen garantías a priori que permita garantizar que un modelo en particular será un problema convexo.

Es decir, una aplicación de Programación No Lineal puede ser un problema convexo o un problema no convexo.

En este artículo abordaremos a través de un ejemplo sencillo las dificultades prácticas y algorítmicas asociadas a la resolución de un modelo de Programación No Lineal no convexo.

Consideremos el siguiente modelo matemático no lineal con restricciones:

problema-no-lineal-no-conve

Una primera aproximación a su resolución consiste en graficar la función anterior utilizando Geogebra:

grafico-de-funcion-no-conve

Se puede observar que la función es no convexa, constatándose adicionalmente la presencia de mínimos locales (por ejemplo los Puntos B y C) y mínimo global (Punto A).

En este sentido la expectativa que debiéramos tener al implementar este problema computacionalmente es obtener la solución óptima para un valor de x en el intervalo entre [4,5] (por simple inspección) lo que corresponde al Punto A de la gráfica anterior.

Una alternativa de resolución computacional para este problema es utilizar AMPL como lenguaje de programación matemática y MINOS 5.5 como solver de resolución. El código de la implementación y los resultados alcanzados se muestra a continuación:

solucion-ampl-problema-no-c

La solución óptima encontrada por el algoritmo corresponde a x=1 (Punto C) lo que permite alcanzar un valor en la función objetivo igual a cero: f(1)=0. Claramente según nuestro gráfico esta solución corresponde sólo a un mínimo local aun cuando el programa sugiere que es el mínimo global del problema.

Otra alternativa de resolución consiste en la utilización de Solver. En primera instancia el algoritmo converge a la solución x=1 con f(1)=0.

solucion-solver-problema-no

Sin embargo, si manualmente editamos el valor de la celda color amarillo B3 (variable de decisión) a «2» y reoptimizamos con Solver se obtiene lo siguiente:

reoptimizacion-pnl-solver

Se alcanza ahora una nueva solución con x=2,45608774 con f(2,45608774)=-1,41869663 lo que corresponde al Punto B de nuestro gráfico y que si bien corresponde a un mínimo local provee un valor menor en la función objetivo al ser comparado con el Punto C. En este contexto resulta razonable considerar el valor «4» para la celda cambiante como punto de partida para una nueva reoptimización:

reoptimizacion-2-pnl-solver

Ahora obtenemos lo que correspondería al mínimo global del problema (Punto A) con solución óptima x=4,64443285 y valor óptimo f(4,64443285)=-3,63143221.

Finalmente hemos resuelto el problema con What’sBest! donde en el siguiente tutorial de nuestro canal de Youtube mostramos los detalles de la implementación:

Luego de reoptimizar sobre la solución local alcanzada en primera instancia se obtiene el mínimo global del problema (Punto A):

solucion-whatsbest-problema

Conclusiones: Las principales dificultades enfrentadas al intentar resolver un modelo de Programación No Lineal no convexo es no tener la certeza si la solución obtenida a través de una herramienta computacional corresponde a un mínimo local o mínimo global.

Con las herramientas presentadas en este artículo fue necesario reoptimizar sobre soluciones obtenidas en primera instancia  para encontrar la solución óptima del problema. Cabe destacar que en este ejemplo al disponer de una representación gráfica del problema sabíamos de antemano cuál era la solución del problema lo cual nos permitía contrastar los resultados computacionales. En este sentido claramente un modelo de mayor complejidad (por ejemplo, un mayor número de variables de decisión y/o restricciones) una aproximación intuitiva no tiene sentido práctico.

En este contexto una de las principales áreas actuales de desarrollo de la Investigación de Operaciones es proveer de métodos numéricos de resolución que permita abordar de forma eficiente la complejidad de esta categoría de problemas de optimización.

Solver, Premium Solver Pro y What’sBest! en la resolución del Problema de Localización y Transporte

¿Qué complemento de Excel es mejor para resolver un modelo de optimización: SolverPremium Solver Pro o What’sBest!?. Esta consulta fue enviada por uno de nuestros seguidores de México y en este artículo trataremos de presentar algunos argumentos que permitan al lector formar una opinión al respecto. Para ello utilizaremos como caso aplicado la resolución del Problema de Localización y Transporte (Programación Entera Mixta). A continuación te presentamos los resultados que alcanzamos con Solver, Premium Solver Pro y What’sBest!.

Resolución con Solver: Se alcanza una solución factible con un costo total asociado de US$12.617.919.

solver-pem

Resolución con Premium Solver Pro: Se alcanza una solución factible con un costo total de US$12.414.340.

solver-premium-pro-pem

Resolución con What’sBest!: Se alcanza una solución factible con un costo total de US$12.414.340. Notar sin embargo que la solución óptima difiere de la alcanzada al implementar el modelo con Premium Solver Pro aun cuando tiene asociado idéntico valor de la función objetivo.

whatsbest-pem

Comentarios: Se puede apreciar que la versión básica de Solver genera una solución factible con un costo mayor a la obtenida tanto con Premium Solver Pro y What’sBest!. Lo anterior sugiere la conveniencia de implementar este tipo de problemas con una herramienta de resolución mejorada. Adicionalmente, en la medida que un modelo de optimización crece en tamaño y complejidad es recomendable poder contrastar los resultados obtenidos con distintas herramientas de resolución de modo de tener una mayor claridad si las soluciones obtenidas son sólo factibles o eventualmente óptimas. A continuación encontrarás un tutorial que hemos subido a Youtube con la resolución del problema de localización y transporte.

Cómo descargar e instalar Premium Solver en Excel 2010

Solver es sin duda junto a What’sBest! la herramienta más popular para resolver modelos de optimización utilizando Microsoft Excel como plataforma. En efecto la versión gratuita que utilizamos de Solver es desarrollada por Frontline Systems Inc, empresa que ofrece un importante número de herramientas y motores de resolución que son de gran utilidad para enfrentar problemas de naturaleza real aplicados en la industria.

En el siguiente artículo nos referiremos a cómo descargar e instalar la versión de prueba de Premium Solver que está disponible en forma gratuita por un período de 15 días y la cual nos permite enfrentar la resolución de modelos de Investigación Operativa significativamente mayores tanto en el número de variables de decisión como restricciones, que aquellos posibles de abordar con la versión tradicional de Solver.

Adicionalmente, al contar con algoritmos de resolución mejorados se favorece la confiabilidad de las soluciones encontradas y los tiempos de procesamiento.

A continuación presentamos el procedimiento detallado para descargar e instalar la versión de prueba de Premium Solver en un computador con Excel versión 2010.

Paso 1: Ingresar a Frontline Systems Inc, completando la información requerida en el formulario de suscripción.

registro-solver-premium

Paso 2: Descargar la versión de prueba compatible con la versión de Excel que dispongamos. En este tutorial se muestra la instalación de la versión de 64 bits. Una vez que estamos seguros de nuestra elección seleccionamos «Download Now».

descargar-premium-solver

Si tienes Excel 2010 y deseas saber de cuántos bits es la versión que utilizas ejecuta Excel y en el menú Archivo selecciona la opción Ayuda. En la esquina inferior derecha se mostrará la cantidad de bits de tu versión bajo el titulo «Acerca de Microsoft Excel».

excel-2010-64-bits

Paso 3: Revisa tu cuenta de correo electrónico (la que proporcionaste en el formulario de suscripción del Paso 1) y anota las 2 contraseñas que te han sido asignadas (en la imagen a continuación éstas han sido protegidas con color azul y rojo).

correo-con-password-premium

Paso 4: Una vez completada la descarga ejecuta el archivo «SolverSetup64.exe» (o el nombre que corresponda según la versión de Excel que estés utilizando).

solversetup64

A continuación se desplegará el asistente para la instalación del programa. (Seleccionar «Next»).

solver-installshield

Ahora debemos ingresar los password que hemos recibido por correo electrónico (Paso 3) para continuar con la activación del programa:

password-activation-solver

Luego debemos aceptar los acuerdos de la licencia del programa y seleccionar «Next».

acuerdo-licencia-solver

En estos momentos la licencia del programa ya ha sido activada y continuamos el proceso de la instalación seleccionando «OK».

activacion-solver-premium

Se debe seleccionar la carpeta donde se instalará el programa y podemos en este punto seleccionar simplemente aquella ubicación que  el programa selecciona por defecto.

carpeta-destino-solver

Es el momento de seleccionar el producto que deseamos activar. En este caso hemos seleccionado «Premium Solver Pro» que corresponde a la versión mejorada de la versión de Solver que se utiliza generalmente para fines académicos.

seleccion-premium-solver-pr

El asistente de instalación nos solicitará confirmar la instalación que hemos seleccionado («Install»).

listo-para-instalar-solver

Finalmente hemos completado la instalación del programa Premium Solver Pro y ya estamos en condiciones de poder utilizarlo para resolver modelos de optimización utilizando Microsoft Excel como plataforma.

instalacion-completa-solver

Cómo lograr un buen desempeño en un curso de Investigación de Operaciones

¿Cómo lograr un buen desempeño en un curso de Investigación de Operaciones?. Esta es una pregunta que usualmente recibimos de nuestros usuarios y probablemente te represente. En el Equipo de Gestión de Operaciones estamos convencidos que esto depende de varios factores y en este artículo te compartiremos nuestra visión al respecto.

1. Participa activamente en la sala de clases: Te recomendamos ser un ente activo del proceso de enseñanza. Si tienes dudas de las materias que el docente este explicando no dejes de preguntar. De seguro tu profesor no tendrá problemas en explicar nuevamente algo que no haya quedado suficientemente claro.

estudiante preguntando

2. Apoya tus estudios con un libro guía: Disponer de un texto guía es una gran ayuda cuando se requiere profundizar en un aspecto teórico de las materias y adicionalmente para revisar casos y ejercicios resueltos. Si cursas un curso introductorio de Investigación de Operaciones te recomendamos conseguir un libro que cubra las principales temáticas del área como la Programación Lineal, Programación Entera, Programación No Lineal y Cadenas de Markov. En nuestra experiencia docente te recomendamos los siguientes textos que los puedes adquirir a precios económicos: Investigacion de Operaciones – Hillier y Lieberman y Investigación de Operaciones, Taha 7° Edición.

3. Explota el potencial de Excel: El tamaño (cantidad de variables de decisión y restricciones) de los modelos de optimización que te sean asignados en clases son generalmente para un fin académico y por tanto no deberías tener inconvenientes en poder implementarlo en Solver o What’sBest!. En nuestro Blog podrás encontrar una serie de artículos que hemos dedicado a estas poderosas herramientas de resolución.

excel_logo

4. Descarga el Libro de Apuntes de Programación Lineal: Nuestro objetivo es ser un apoyo para tus estudios formales de Gestión e Investigación de Operaciones y en este contexto hemos desarrollado un libro de apuntes de programación lineal el cual podrás descargar de forma gratuita si nos recomiendas en las redes sociales.

ecover pl formulario

ecover pl formulario

5. Accede a Recursos Gratuitos para la Investigación de Operaciones: Te recomendamos leer nuestro artículo 7 Recursos Gratuitos para el estudiante de Investigación de Operaciones donde podrás encontrar datos útiles para tus estudios.

Esperamos que estos consejos te ayuden a lograr el objetivo de aprender y en consecuencia aprobar las materias de Investigación de Operaciones.

Gestión de Operaciones es Consultor Recomendado por Lindo Systems Inc.

Nos enorgullece informar que nuestro Equipo de Gestión de Operaciones ha alcanzado el estatus de Consultor Recomendado por Lindo Systems Inc, empresa desarrolladora de software para la optimización con base en Chicago, Estados Unidos, y que cuenta con una amplia gama de productos como What’sBest!, Lingo y Lindo API. A continuación un extracto de dicho reconocimiento:

consultor recomendado lindo

Si actualmente trabajas en una empresa y consideras que existe un potencial de mejora importante a través de la formulación y resolución de un modelo de optimización, no dudes en contactarnos indicando los antecedentes necesarios de modo de poder preparar un presupuesto para tu evaluación. Para ello puedes enviar tu información a través del Formulario de Contacto o si prefieres nos puedes escribir directamente al email: [email protected].