Software disponible para Programación Lineal

Ing. Ricardo Otero

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Necesidad de implementación de Software Los problemas reales por lo general tienen

una gran cantidad de variables y restricciones que restringen su solución manual.

Los desarrollos actuales han logrado importantes avances en métodos efectivos de solución (MP1, SIMPLEX).

La necesidad de obtener respuestas inmediatas obliga a implementar métodos de solución más efectivos.

La flexibilidad debe ser una característica del modelo matemático y su método de solución.

Un problema de programación lineal con m variables y n restricciones puede tener hasta mCn vértices.

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Software Disponibe GLPK (LP, MP,) LPS (LP, MP) WinQSB (LP, MP) Gams (LP, MP, NLP) Lingo (LP, MP, NLP) Solver (LP, MP, NLP)

OS

CS

Optimización de Operaciones Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Solver Es una herramienta complemento de optimización que

se distribuye dentro de Microsoft Excel. Permite resolver problemas de Programación lineal,

entera, mixta, y en sus últimas versiones ha tenido gran avance en la solución de problemas de programación no lineal.

A pesar de ser software licenciado, su costo de adquisición no es alto.

Permite implementar y anidar las funciones disponibles en Excel para el refinamiento de los modelos.

Se pueden generar modelos de programación matemática con datos disponibles en otros archivos u otros computadores enlazados.

Es interactivo y de fácil acceso.

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

R Statistics Es un software de doble personalidad: Programa y Lenguaje de

Programación. Fue desarrollado bajo el lenguaje S de Bell Labs. Es distribuido de manera libre bajo el concepto de GNU. Diseñado para el análisis y procesamiento de grandes bases de

datos. Es un lenguaje de programación orientado a objetos. Es actualmente uno de los proyectos OS con mayor generación y

actualización de contenido de alta calidad. Es posible Instalar paquetes de una gran diversidad de temas

estadísticos y de optimización. Los paquetes desarrollados están disponibles gratis en internet bajo

la distribución del CRAN de R, que entre otras exige una documentación detallada para su uso y aplicación.

Su desarrollo está bajo la dirección de diversos grupos académicos como el R development Core Team

Es similar a SAS y Matlab.

Optimización de Operaciones Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

R stastics y Optimización Existen diferentes paquetes y API’s disponibles

para la implementación de diferentes métodos de optimización.

Contiene funciones internas para problemas de optimización de modelos matemáticos.

Permite la implementación de Lpsolve, Glpk, etc. La facilidad del manejo de bases de datos permite

tener los parámetros de los modelos actualizados. Es posible implementar servidores web externos

para aprovechar la computación paralela. En el siguiente enlace se encuentra una gran

cantidad de funciones de optimización:http://cran.r-project.org/web/views/Optimization.html

Optimización de Operaciones Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

LP Solve Es un programa de distribución libre bajo los

parámetros del GNU. Permite resolver problemas de programación lineal,

entera y mixta. Basado en el simplex revisado para PL y Branch and

Bound para programación entera. Lpsolve puede resolver problemas de hasta 100.000

variables. La comunidad de LPsolve, donde se pueden encontrar

foros, ejecutables, ejemplos, etc; está disponible en: http://groups.yahoo.com/group/lp_solve/

Permite la incorporación de diferentes lenguajes de modelación como MATHPROG.

Optimización de Operaciones Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

LP Solve Ejemplo Las funciones deben ser

lineales Cada comando debe estar

finaliazdo por “;” “/*” es para escribir

comentarios En Matrix se puede

apreciar la representación matricial del problema.

En Result se presenta la solución del problema y el análisis de sensibilidad.

En opciones se puede ajustar los métodos de solución y número de iteraciones.

La precisión de la respuesta debe ser cercana a 0.

Función Objetivo

Restricciones

Precisión Respuesta

Resultados

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Considreaciones LP solve Caracterización de variables:

Free x, int x, bin x. Tipos de solución:

Parse error, optimal solution, unbounded, infeasible.

Es posible exportar: Solución, Matriz A, Sensibilidad.

Lenguajes Soportados MATHPROG, CPLEX, LINGO, XPRESS, LPFML

El análisis de sensibilidad no tiene en cuenta las restricciones enteras.

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Ejemplo Una empresa fabrica dos tipos distintos de

productos (A y B). Cada uno de ellos genera un ingreso por $50 y 120$ respectivamente. El producto B consume el doble de materia prima de A, pero, el producto A requiere el triple de mano de obra – en horas – que el producto B. Si sólo disponen de 40 unidades de materia prima y 60 horas disponibles de mano de obra, y además se sabe que por limitaciones de planta no se pueden elaborar más de 30 productos tipo B. ¿Cuántas cantidades de producto deben fabricarse?. Realizar el análisis de Sensibilidad

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Solución en LP solve Para resolver el modelo

F9. Se debe verificar la

sintaxis antes de correr el modelo.

Se debe incluir el objetivo del problema (max, min), seguido por ‘:’.

Es posible poner nombre a las restricciones.

Después de nombrar las restricciones se debe especificar el tipo de variables (free, int, bin).

Cada una de las líneas debe estar finalizada por ‘;’.

Planteamiento del modelo

Presentación Solución

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Cantidad máxima que podemos variar los coeficientes de la F.O. sin cambiar la solución óptima

Análisis de Sensibilidad LP Solve

Valores permisibles: Cantidad máxima que podemos variar los coeficientes del RHS para ganar o perder una cantidad proporcional al precio sombra. (Sin cambiar la Base)

Precio Sombra: Cantidad de mejora de la función objetivo, (aumenta en max y disminuye en min) por cada unidad que se relaje la restricción.

Gradiente Reducido: Cantidad que debe aumentar (max), disminuir (min) el coeficiente de la F.O. para que la variable tome un valor diferente de 0. (Val Abs)

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Consideraciones Solver Se debe plantear la formulación en hoja de cálculo con

base a las celdas relacionadas. Tanto las restricciones como la función objetivo deben

estar en función de las celdas de las variables de decisión.

Se debe especificar en opciones la no negatividad y linealidad del problema.

Se debe ser cuidadoso con el manejo de unidades, se recomienda verificar la configuración regional del complemento y del software.

Es posible agregar todas las restricciones de una sola vez, incluyendo todo el vector de valores.

Al final, si el problema tiene solución solver permite escoger los informes de solución y sensibilidad.

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Solución en Solver

Coeficientes Función Objetivo

Límites Restricciones RHS

Valores Variables Decisión (dados por solver)

Valor Función Objetivo (En función de Variables de decisión)

Recursos de restricciones usados

Matriz de Coeficientes de restricciones

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Análisis de Sensibilidad en Solver

Informe de Resultados: Presenta el valor de la

función objetivo, la solución y el consumo de recursos

de las restricciones.

Informe de Sensibilidad:

Presenta los precios sobra y costos

reducidos.

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Formulación en MATHPROG Permite resolver problemas implementado

formulación compacta. Se debe crear cada uno de los subconjuntos

asociados al problema. La formulación debe estar acorde a los

subconjuntos establecidos. Se debe establecer los parámetros y a qué

subconjunto pertenece. Al final del problema se deben especificar la

información de los parámetros.

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Conceptos El término set es una palabra reservada por el

programa y se implementa para definir los conjuntos.

El término param está reservado por el programa y se implementa para crear los parámetros asociados al problema. Se debe especificar a qué subconjunto pertenece.

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Variables de decisión var es un término reservado por el programa

y sirve para definir las variables de decisión. Se debe especificar los conjuntos asociados a ella.

minimize es un término reservado por el programa y permite definir las restricciones asociadas al problema.

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Restricciones s.t. es un término reservado por el programa y

permite definir las restricciones asociadas al problema.

Es posible asignar un nombre a las restricciones y a la función objetivo.

Se debe especificar a qué subconjunto pertenece las restricciones

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Datos Para agregar información sobre los parámetros se

debe especificar el comando data. Se debe especificar los valores y/o el tamaño de

los subconjuntos. Se deben definir el valor de cada parámetro,

separado por un espacio.

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá

Ejercicio Resolver el problema 2 de formulación

compacta con LP solve y MathProg

Optimización de Operaciones - Ing. Ricardo Fernando Otero - Pregrado Ingeniería Industrial – Pontificia Universidad Javeriana Sede Bogotá