Programación No Lineal Archivos - Página 3 de 3

7 Recursos Gratuitos para el estudiante de Investigación de Operaciones

En Internet existen recursos gratuitos valiosos para los estudiantes de los cursos de Investigación de Operaciones (conocido también como Investigación Operativa) que son de gran ayuda para complementar los conceptos tratados en el aula y la bibliografía. En el siguiente artículo ponemos en disposición de nuestros lectores algunos recursos que recomendamos:

1. Solver: Es sin duda la principal herramienta para resolver modelos de optimización de tamaño reducido utilizado por los alumnos de cursos de ingeniería. Este complemento de Excel se puede descargar desde el sitio web de Frontline en su versión comercial (Premium Solver Pro) para implementar modelos de mayor tamaño.

2. What’sBest!: Es la alternativa a Solver dado que funciona integrada en una planilla de cálculo (Excel). La interfaz es intuitiva y seguramente quién domine Solver no demorará mucho en aprender los elementos básicos de este programa. What’sBest! ha sido desarrollado por la empresa de software Lindo.

3. AMPL: Es un lenguaje de programación matemática que permite abordar la formulación y resolución de modelos de optimización de programación lineal, programación entera y programación no lineal (entre otros). Esta plataforma es popular para modelos de mayor complejidad que requieren para su resolución de algoritmos especializados.

4. GAMS: Es una herramienta de formulación matemática alternativa a AMPL que permite formular y resolver modelos de optimización de complejidad mayor.

5. NEOS Solvers: Es un portal que consolida una gran variedad de solvers (algoritmos) que permiten resolver distintas categorías de modelos de optimización formulados en un lenguaje matemático determinado (como AMPL y GAMS). El procedimiento es el siguiente: se selecciona un solver que permita resolver nuestro modelo (depende del lenguaje de programación matemática y el tipo de modelo), se sube el archivo del modelos (y/o datos) y se obtienen los resultados online.

6. Geogebra: Es un excelente programa que nos ayuda a graficar distintas formas geométricas y en particular resolver gráficamente modelos de optimización lineales o no lineales. Este programa se puede descargar gratuitamente e instalar en nuestro computador o alternativamente utilizar su aplicación web directamente sin necesidad de descargar el programa.

7. Método Simplex (ProgramacionLineal.net): Es una herramienta que permite resolver modelos de programación lineal a través del método simplex, mostrando paso a paso las respectivas iteraciones, solución óptima y valor óptimo.

8. Linear Programming: Versión en inglés de los principales artículos de este Blog que trata sobre la Investigación de Operaciones y en particular de la Programación Lineal, con recursos educativos y ejercicios resueltos.

Cómo resolver un modelo de Programación No Lineal con AMPL

La complejidad adicional que representan los modelos de Programación No Lineal en comparación a los modelos de Programación Lineal, justifica el desarrollo de algoritmos especializados que permitan abordar de forma más eficiente la resolución de este tipo de modelos.

En este contexto, uno de los lenguajes de programación matemática más conocidos y confiable para formular diversos modelos de optimización es AMPL (www.ampl.com). Su popularidad ha sido sustentada adicionalmente por el desarrollo de distintos algoritmos de resolución (o solvers) que son compatibles con AMPL y que permiten resolver modelos de Programación Lineal, Programación No Lineal, Programación Entera, entre otras.

Estos solvers han sido resultado del trabajo de prestigiosas universidades y centros de investigación, en algunos casos en conjunto con empresas de software. El servidor NEOS consolida esta información en Internet.

A continuación mostraremos cómo resolver un modelo de Programación No Lineal sencillo utilizando la versión estudiantil de AMPL y utilizando el solver de resolución MINOS versión 5.5. Para ello debemos descargar el archivo «amplcml.zip» a nuestro computador, descomprimir éste y luego ejecutar el archivo de nombre «ampl».

Consideremos el siguiente modelo de Programación No Lineal:

La sintaxis utilizada por AMPL es bastante intuitiva como se aprecia a continuación en la resolución del ejemplo:

var x1>=0; # definición de la variable x1 estableciendo condición de no negatividad.
var x2>=0; # definición de la variable x2 estableciendo condición de no negatividad.
minimize funcionobjetivo: (x1-2)^2+(x2-4)^2; # definición de la función objetivo. El nombre de la misma es arbitrario.
subject to restriccion1: 2*x1+4*x2<=12; # se define la inecuación correspondiente a la restricción 1.
subject to restriccion2: 4*x1+3*x2<=16; # se define la inecuación correspondiente a la restricción 2.
solve; # una vez implementado el modelo se ejecuta su resolución haciendo uso de MINOS 5.5 (opción por defecto)

La solución óptima es X1=1,2 y X2=2,4 con valor óptimo V(P)=3,2. (Puedes consultar aquí la Resolución Gráfica de este modelo). Adicionalmente se pueden corroborar los resultados a través de la aplicación de las condiciones de optimalidad de Karush-Kuhn-Tucker (KKT).

Diferencias entre la Programación No Lineal y la Programación Lineal

El supuesto de la proporcionalidad de la Programación Lineal (PL) no siempre es adecuado para representar de buena forma situaciones de naturaleza real que requieren de un modelo de optimización como apoyo para el proceso de toma de decisiones.

Cabe señalar que un modelo de Programación No Lineal (PNL) es aquel donde la función objetivo y/o las restricciones son funciones no lineales de las variables de decisión.

En este sentido la Programación No Lineal permite enfrentar una serie de aplicaciones prácticas que requieren una representación a través de funciones no lineales.

Algunos casos característicos de la Programación No Lineal son los problemas de minimización de distancia, economías o deseconomías de escala, carteras de inversión, ajuste de curva, entre otros.

En general cuando formulamos un modelo de optimización no lineal esperamos que éste sea más representativo de una situación real en comparación a un modelo lineal, sin embargo, a la vez asumimos que es probable que la complejidad de la resolución aumente. Por ello quien formule un modelo debe equilibrar la representatividad del mismo con la dificultad de la resolución.

A continuación presentaremos dos modelos de optimización que comparten las mismas restricciones (que asumiremos por simplicidad que son funciones lineales) y se diferencian por la naturaleza de la función objetivo (lineal y no lineal, respectivamente). Estos ejemplos nos ayudarán a explicar algunas diferencias entre la Programación Lineal y Programación No Lineal:

Si Resolvemos Gráficamente el modelo de Programación Lineal obtenemos la solución óptima en el vértice C (X=14/5 Y=8/5 y valor óptimo V(P)=20,8) lo cual corresponde a una Solución Básica Factible Óptima.

En efecto, una de las propiedades básicas de la Programación Lineal es que cuando un modelo admite solución, ésta se encontrará en un vértice (o tramo frontera en el caso Infinitas Soluciones Óptimas) del dominio de soluciones factibles. (Recomendación: Ver Teorema Fundamental de la Programación Lineal).

En cuanto a la resolución del modelo de Programación No Lineal, las curvas de nivel de la función objetivo no lineal tiene la forma de circunferencias concéntricas desde la coordenada (X,Y)=(2,4). Como la función objetivo es de minimización, buscamos la circunferencias de menor radio (o diámetro) que intercepte por primera vez el dominio de soluciones factibles. Esto se alcanza en (X,Y)=(1,2,2,4).

El resultado anterior se puede verificar mediante la aplicación de las condiciones de optimalidad que establece el Teorema de Karush-Kuhn-Tucker (KKT) al ser éste un problema de Programación No Lineal restringido.

Conclusión: Si un modelo de Programación No Lineal admite solución óptima, ésta se puede encontrar en cualquier punto del dominio de soluciones factibles.

Por ejemplo, si la función objetivo estuviese centrada en la coordenada (X,Y)=(2,1) ésta ya sería la solución óptima del problema. Notar que esta situación (solución en un punto interno del dominio factible) NO sería posible en la resolución de un modelo de Programación Lineal.

En los artículos de la categoría de Programación No Lineal analizamos algunos algoritmos especializados para la resolución de modelos no lineales como también herramientas computacionales para enfrentar este tipo de problemas.