programacion lineal

Programación lineal entera y mixta

101

5 Programación lineal entera y mixta
5.1 Introducción
En algunas situaciones que pueden representarse con modelos lineales, nos encontramos con que
sólo tienen sentido aquellas soluciones de la región factible en las que todas o algunas de las variables de decisión sean números enteros. Estas situaciones pueden representarse mediante modelosmatemáticos ligeramente diferentes de la programación lineal. Si todas las variables de decisión
deben ser enteras, tenemos un problema de programación lineal entera. Si sólo algunas variables de
decisión deben ser enteras, pudiendo ser reales las demás, se trata de un problema de programación
lineal mixta.
En algunos casos, todas o algunas de las variables enteras sólo pueden tomar los valores de 0o 1. A
estas variables se les llama variables binarias. De este modo tenemos tres tipos de variables:
a)

Variables no enteras o reales

b)

Variables enteras

c)

Variables binarias

La posibilidad de utilizar variables enteras o binarias amplía notablemente las posibilidades de modelización matemática. El precio por una mayor versatilidad de la herramienta es el de una mayorcomplejidad en la resolución del modelo. Esta complejidad se debe a los siguientes hechos:
Para las variables enteras del modelo, el razonamiento que se empleó para mostrar que la solución
óptima era un vértice (o una combinación convexa de vértices) de la región factible no es válido: en un
caso general, los vértices de la región factible no tienen porqué ser números enteros. En consecuencia,
lasolución óptima se encontrará en el interior de la región factible, por lo que el método símplex, empleado de forma directa, no proporcionará la solución óptima.
A diferencia del problema con variables reales, el número de soluciones de un modelo de programación lineal entera es finito, por lo que podría plantearse la posibilidad de encontrar la solución mediante la exploración de todas lassoluciones posibles. Sin embargo, el número de soluciones a explorar
para un problema mediano puede ser muy elevado: en principio, para un problema con n variables
enteras debemos explorar 2n soluciones (excluyendo quizás algunas descartadas por las restricciones).
Para n = 30, tenemos 230 = 1.073.741.924 soluciones posibles.
Se han desarrollado metodologías que permiten explorar de manera máseficiente que la mera enumeración el conjunto de soluciones posibles. Gran número de estas metodologías emplean la lógica del
branch and bound, y están incorporadas a la mayoría de programas informáticos que resuelven modelos lineales. Seguidamente se muestra este procedimiento y cómo resolver modelos de programación
entera mediante programas informáticos.

© Los autores, 2002; © Edicions UPC, 2002.102

Métodos cuantitativos en organización industrial I

5.2 Metodología de resolución: algoritmo branch and bound
Un primer paso para la resolución de un modelo de programación lineal entera es resolver, mediante el
método símplex, el problema lineal asociado. Se trata de un problema lineal con la misma función objetivo y restricciones que el modelo original, pero al que se hanrelajado la condición de que todas o
algunas de las variables de decisión sean enteras. Si la solución así obtenida es entera, habremos encontrado la solución del modelo de programación lineal entera. En caso contrario (el más frecuente), la
solución así obtenida es una primera aproximación a la solución del modelo.
Resulta tentador redondear los valores no enteros a enteros en la solución obtenidapara el problema
lineal asociado. Esto sólo se puede hacer si los valores de las variables son tan grandes que el redondeo no afecta excesivamente al resultado final, pero se debe tener cuidado al hacerlo pues se corren
dos riesgos:
1.

Es posible que la solución redondeada no sea factible.

2.

Aún siendo factible, no existe ninguna de garantía que la solución sea óptima.

Estos dos...