Modelos Lineales De Optimizacion

Tema 2: Modelos lineales de optimización con variables enteras.

Objetivos del tema:  Introducir la programación lineal entera y los dominios de aplicación.  Aprender a formular el modelo de un problema de programación lineal entera.  Modelar relaciones lógicas entre restricciones con variables binarias  Expresar un problema entero general como un problema binario  Modelarmatemáticamente y resolver en OPL varios problemas típicos de programación lineal entera  Expresar algunos comportamientos no lineales como problemas enteros

1
J.J. RUZ, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL 

Introducción En muchos problemas de programación lineal sólo tienen sentido aquellas soluciones de la región factible en las quetodas o algunas de las variables de decisión toman valores enteros. Este tipo de problema se denominan en general de programación lineal entera. Si todas las variables del problema deben ser enteras se habla de programación entera pura, pero si sólo algunas deben ser enteras y las restantes continuas se habla de programación lineal entera‐mixta. Cuando las variables enteras están restringidas alos dos valores 0‐1, se denominan variables binarias, y el problema correspondiente problema binario. Como veremos en el tema 6 de la asignatura, la resolución de los problemas enteros resulta más compleja que los continuos. En este caso la solución óptima no necesariamente tiene que coincidir con un vértice de la región factible del problema continuo, sino que puede estar en el interior o en lasaristas de dicha región, pero siempre en puntos con valor entero de sus coordenadas. Por ejemplo el siguiente modelo lineal entero puro tiene la solución óptima en el punto (3 2) bastante alejado del punto extremo ejemplo, (3, 2), donde tiene su valor óptimo el problema continuo.
x2

Minimizar -6x1  5 x2 subject to 3 x1  x2  11  x1  2 x2  5 x1 , x2  0, integer

 x1  2 x2  5Solución óptima del  problema continuo Solución óptima del  p problema entero

3x1  x2  11 x1

La utilización de variables enteras en general y binarias en particular amplía notablemente las posibilidades de modelado de la programación lineal, haciendo posible la disyunción de restricciones, la implicación lógica entre restricciones y en general la incorporación al modelo de ciertoscomportamientos no lineales de la realidad. En este tema exploraremos algunas de las nuevas posibilidades que introducen las variables enteras desde el punto de vista del modelado de problemas. También veremos su expresión en el leguaje OPL. En el tema 6 estudiaremos los métodos algorítmicos que se utilizan para resolverlos.J.J. RUZ, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL 

2

Dominios de aplicación de la Programación Entera Dominios de aplicación de la Programación Entera La programación entera resulta de interés en el modelado de los siguientes dominios de aplicación: Aplicaciones con entrada y salida de datos discretos Se trata de las aplicaciones en las que la programación entera se hace más evidente. Surgen cuando se quierenmodelar plantas que fabrican productos con valor añadido muy alto y en un número de unidades entero y relativamente pequeño, por ejemplo, vehículos de transporte, equipos electrónicos de alta tecnología, etc. Por el contrario, si los valores enteros que se manejan en estos problemas son elevados, podrían resolverse como si fuesen de programación lineal continua y posteriormente redondear la solución.Aplicaciones con relaciones lógicas entre variables o restricciones Ocurre en bastantes ocasiones reales que es necesario establecer relaciones lógicas entre las restricciones que se deben imponer. Por ejemplo, .“si se abre una fábrica en Zaragoza, se puede abrir también un almacén”. Este tipo de relaciones lógicas se pueden modelar introduciendo nuevas variables binarias....