Ejemplos P

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
 Modelar matemáticamente yresolver 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 que todas oalgunas 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 a los dosvalores 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 las aristas dedicha región, pero siempre en puntos con valor entero de sus coordenadas.
Por ejemplo,
ejemplo el siguiente modelo lineal entero puro tiene la solución óptima en el punto (3,
(3 2),
2) bastante alejado del punto extremo
donde tiene su valor óptimo el problema continuo.
x2

Minimizar -6x1  5 x2

 x1  2 x2  5

Solución óptima del 
problema continuo

subject to
3 x1  x2  11

Solución óptima del problema entero
p

 x1  2 x2  5
x1 , x2  0, integer
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 ciertos comportamientos no lineales de larealidad.
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 quieren modelar plantas
que fabrican productos con valorañ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.

Aplicaciones de optimización combinatoria...