Download - Programación entera
5. Programación entera
5.1.1 Introducción y casos de aplicación
Sus pioneros fueron Wagner (1950) y Manne (1959). Tradicionalmente estos
modelos se han considerado como subclases de la programación lineal, sin
embargo, las variables de decisión que aparecen en ellos sólo toman valores
enteros, por lo que deben considerarse como problemas de programación entera.
No siempre es admisible que las variables de un problema lineal tomen valores
continuos, existen:
• Decisiones dicotómicas (si-no)
• Decisiones que deben tomarse en unidades discretas
Si se requiere que todas las variables sean enteras, se dice que se habla de
Programación Lineal Entera Pura; si se necesita que algunas de las variables de
decisión sean números enteros, se tiene un problema de Programación Lineal
Entera Mixta.
En algunas aplicaciones, sólo se permite que todas las variables tomen valores de
cero o uno, hablamos en estos casos de Programación Lineal Entera Binaria
(Digital); si se requiere que solamente algunas de las variables tomen valores de
cero o uno, se tiene un problema de Programación Lineal Entera Binaria Mixta.
La Programación Entera tiene gran cantidad de aplicaciones en todos los campos.
5.2 Definición y modelos de programación entera.
--- Programación Entera Pura Todas las variables están restringidas a tomar valores enteros.
Max (z) = cT y
sujeto a:
Ay < b
yj {0,1,2,...} j = 1,2,... n
--- Programación Entera Binaria
Max (z) = cT y
sujeto a:
Ay < b
yj {0,1} j = 1,2,... n
TIPOS DE ALGORITMOS DE PROGRAMACIÓN ENTERA Algoritmos de Programación Entera Pura (IP)
• Enumerativos:
• Branch and Bound
• Balas, etc
• De planos cortantes:
• Gomory
• Otros
Algoritmos de Programación Entera Mixta (MIP)
• Enumerativos:
• Branch and Bound
• Balas, etc
• De descomposición dual:
• Benders
• Otros
ALGORITMOS ENUMERATIVOSEnumeración explícita
Los algoritmos enumerativos obtienen la solución del problema a base de
enumerar, implícita o explícitamente, todas las soluciones posibles y escogiendo
la mejor de todas ellas.
La forma más inmediata de resolver problemas de Programación Entera
(PE) consistiría en calcular todas las posibles soluciones y buscar la mejor entre
ellas (enumeración explicita). Este método tiene graves inconvenientes. Por
ejemplo, en el caso de la programación entera binaria, el número de posibles
soluciones es 2 elevado al número de variables enteras.
En la siguiente figura se representa la combinatoria de un problema con cuatro
variables 0-1. Encima y debajo de cada nodo, se presentan los subíndices de
cuatro variables que toman valores “1” y “0”, respectivamente. Como puede
apreciarse, el árbol tiene 24 =16 nodos.
Combinatoria Enumeración ExplicitaDe esta forma, un problema con 10 variables binarias tendría. 210= 1.024
soluciones. Si el problema tuviera 20 variables, existirían. 220 = 1.048.276
soluciones. Ni el ordenador más potente sería capaz de enumerar todas las
soluciones cuando el número de variables es medianamente grande. Por ello,
resulta necesario acudir a métodos más sofisticados.
Enumeración ImplícitaLos métodos de enumeración implícita aplican un conjunto de reglas para
evitar enumerar soluciones in factibles o peores que la mejor solución factible que
se haya localizado hasta el momento.
5.3 Método de Ramificar y acotar
El método de ramificación y acotación, más conocido por su nombre en inglés
Branch and Bound, recibe su nombre precisamente por las dos técnicas en las
que basa su desarrollo, que son la ramificación y la acotación.
El método de ramificación y acotación comienza por resolver el PLA
(programación lineal entera), de modo que si la solución al PLA verifica las
condiciones de integridad, entonces también es la solución al problema entero, en
caso contrario se comienza con la ramificación del problema.
La ramificación consiste en dividir cada problema en dos nuevos subproblemas,
obtenidos mediante la imposición de restricciones excluyentes que dividen el
conjunto de oportunidades del problema original en dos partes, pero eliminando en
ambas partes la solución no entera del problema original.
Cuando en la solución al PLA una variable que ha de ser entera xi toma el valor
xbi no entero, entonces se generan a partir de dicho valor dos restricciones xi ≤
[xbi] y xi ≥ [xbi]+1 (siendo [xbi] la parte entera por defecto de xbi ), que añadidas
cada uno por separado al problema original, da lugar a dos nuevos subproblemas.
Vamos a explicar este proceso a través de un ejemplo particular:
Max F(x) = 8x1 + 10x2
s.a. 4x1 + 6x2 ≤ 248x1 + 3x2 ≤ 24x1≥0,x2≥0, x1,x2∈Z+
Resolviendo en primer lugar el PLA, es decirMax F(x) = 8x1 + 10x2
s.a. 4x1 + 6x2 ≤ 248x1 + 3x2 ≤ 24x1≥0,x2≥0
se obtiene la solución x1 = 2, x2 = 8/3, F(x) = 128/3, dado que ésta solución no es entera se ramifica a partir de la variable x2 del siguiente modo:
subproblema 1
Max F(x) = 8x1 + 10x2
s.a. 4x1 + 6x2 ≤ 248x1 + 3x2 ≤ 24 x2 ≥ 3x1≥0,x2≥0
solución x1=1,5, x2=3, F(x)=42
subproblema 2
Max F(x) = 8x1 + 10x2
s.a. 4x1 + 6x2 ≤ 248x1 + 3x2 ≤ 24 x2 ≤ 2x1≥0,x2≥0
solución x1=2,5, x2=2, F(x)=38
como la solución del subproblema 1, tiene el mayor valor de la función objetivo y no es entera ramificaremos este subproblema a partir de la variable x1, del siguiente modo:
subproblema 1.1Max F(x) = 8x1 + 10x2
s.a. 4x1 + 6x2 ≤ 248x1 + 3x2 ≤ 24 x2 ≥ 3x1 ≤ 1x1≥0,x2≥0
solución x1=1, x2=10/3,F(x)=124/3
subproblema 1.2Max F(x) = 8x1 + 10x2
s.a. 4x1 + 6x2 ≤ 248x1 + 3x2 ≤ 24 x2 ≥ 3x1 ≥ 2x1≥0,x2≥0
solución infactible.
dado que de todos los subproblemas todavía no ramificados (subproblemas 2, 1.1 y 1.2) el que tiene una mayor solución factible no entera es el subproblema 1.1, ramificaremos este subproblema a partir de la variable x2, es decir:
subproblema 1.1.1Max F(x) = 8x1 + 10x2
s.a. 4x1 + 6x2 ≤ 248x1 + 3x2 ≤ 24 x2 ≥ 3x1 ≤ 1 x2 ≤ 3x1≥0,x2≥0
solución x1=1, x2=3,F(x)=38
subproblema 1.1.2Max F(x) = 8x1 + 10x2
s.a. 4x1 + 6x2 ≤ 248x1 + 3x2 ≤ 24 x2 ≥ 3x1≤ 1 x2 ≥ 4x1≥0,x2≥0
solución x1=0, x2=4,F(x)=40
Dado que ya conocemos una solución entera x1=0, x2=4, F(x)=40, ésta solución
actuará como cota inferior y solamente deberán ser ramificados aquellos
subproblemas con soluciones factible no enteras que tengan un valor para la
función objetivo que es 40. Como el único subproblema por ramificar es el
subproblema 2 y la función objetivo vale 38, el proceso se da por terminado,
siendo por tanto la solución óptima al problema entero
x1 = 0, x2 = 4, F(x) = 40el árbol del problema resuelto es el siguiente:
5.4 Método de planos cortantes.
Objetivo, agregar restricciones que eliminen la solución fraccional sin eliminar
ninguna solución entera.
En cada iteración la región factible es reducida hasta que una solución entera es
encontrada resolviendo el PL, la idea esencial es encontrar cortes válidos.
De dónde vienen estos cortes
(A) Específico a cada problema
(B) Enfoque general basado en PL
Consideremos el siguiente problema:
La empresa tiene un presupuesto para invertir de $14.000
Los datos proporcionados por la empresa se muestran a continuación:
Proyecto de inversión 1 2 3 4 5 6
Capital necesario $ 5 $ 7 $ 4 $ 3 $ 4 $ 6
Retorno $ 16 $ 22 $ 12 $ 8 $ 11 $ 19
Maximizar Z = 16x1 + 22 x2 + 12 x3 + 8 x4 + 11 x5 + 19 x6
s.a.
5x1 + 7x2 + 4x3 + 3x4 + 4x5 + 6 x6 ≤ 14
xj para j = 1 a 6
El problema se expresa en términos de programación lineal:
Maximizar Z = 16x1 + 22 x2 + 12 x3 + 8 x4 + 11 x5 + 19 x6
s.a.
5x1 + 7x2 + 4x3 + 3x4 + 4x5 + 6 x6 ≤ 14
0 ≤ xj ≤ 1 para j = 1 a 6
Solución óptima: x1= 1, x2 = 3/7, x3 = 0, x4= 0, x5 = 0, x6 = 1
¿Podemos encontrar una restricción valida (corte), que elimine esta solución?
Primer corte Maximizar Z = 16x1 + 22 x2 + 12 x3 + 8 x4 + 11 x5 + 19 x6
s.a.
5x1 + 7x2 + 4x3 + 3x4 + 4x5 + 6 x6 ≤ 14
0 ≤ xj ≤ 1 para j = 1 a 6
Solución óptima: x1= 1, x2 = 3/7, x3 = 0, x4= 0, x5 = 0, x6 = 1
Z= 44 3/7
5x1 + 7x2 + 6x6 ≤ 14 x1 + x2 + x6 ≤ 2
Segundo corte Maximizar Z = 16x1 + 22 x2 + 12 x3 + 8 x4 + 11 x5 + 19 x6
s.a.
5x1 + 7x2 + 4x3 + 3x4 + 4x5 + 6 x6 ≤ 14
x1 + x2 + x6 ≤ 2
0 ≤ xj ≤1 para j = 1 a 6
Solución óptima: x1 = 0, X2= 1, X3= 1/4, X4= 0, X5= 0, X6= 1
Z= 44
7X2 + 4X3 + 6X6 ≤ 14 ??
Tercer corte Maximizar Z = 16x1 + 22 x2 + 12 x3 + 8 x4 + 11 x5 + 19 x6
s.a.
5x1 + 7x2 + 4x3 + 3x4 + 4x5 + 6 x6 ≤ 14
x1 + x2 + x6 ≤ 2
x2 + x3 + x6 ≤ 2
0 ≤ xj ≤1 para j = 1 a 6
Solución óptima:
x1 = 1/3, X2= 1, X3= 1/3, X4= 0, X5= 0, X6= 2/3
Z= 44
5X1 + 7X2 + 4X3 + 6x6 ≤ 14 ???
Para conocer cuál de los 3 cortes es corte válido: Maximizar Z = x1 + x2 + x3 + x6
s.a.
5X1 + 7X2 + 4X3 + 6x6 ≤ 14
xj para j = 1, 2, 3, 6
Se colocan sucesivamente los que “ocupan” menos, hasta que no quepa ninguno más.En este caso caben solo 2: 1 y 3, y no hay espacio para 2 y 6, por lo tanto:x1 + x2 + x3 + x6 ≤ 2
Recordemos que después del tercer corte, se tiene:
Maximizar Z = 16x1 + 22 x2 + 12 x3 + 8 x4 + 11 x5 + 19 x6
s.a.
5x1 + 7x2 + 4x3 + 3x4 + 4x5 + 6 x6 ≤ 14
x1 + x2 + x6 ≤ 2 Restricciones redundantes
x2 + x3 + x6 ≤ 2
x1 + x2 + x3 + x6 ≤ 2
0 ≤ xj ≤ 1 para j = 1 a 6
Eliminando restricciones redundantes
Maximizar Z = 16x1 + 22 x2 + 12 x3 + 8 x4 + 11 x5 + 19 x6
s.a.
5x1 + 7x2 + 4x3 + 3x4 + 4x5 + 6 x6 ≤ 14
x1 + x2 + x3 + x6 ≤ 2
0 ≤ xj ≤ 1 para j = 1 a 6
Solución óptima:
x1 = 0, X2= 1, X3= 0, X4= 0, X5= 1/4, X6= 1
Z= 43 ¾
Z* ≤ 43
5.5 Algoritmo aditivo de Balas
Otro algoritmo enumerativo importante es el algoritmo aditivo. Es debido
originalmente a Egon Balas (1965). Se llama aditivo porque todas las operaciones
matemáticas que se realizan consisten en sumar o restar.
El procedimiento consiste en generar una secuencia de soluciones
parciales añadiendo en cada iteración una variable y considerando las soluciones
complementarias (resto de soluciones posibles). De esta forma, podemos por
enumeración implícita, eliminar conjuntos de soluciones sin necesidad de
evaluarlos exhaustivamente.
La selección de la variable añadida se hace en función de reducir al máximo la
infactibilidad en la solución actual y eliminar la redundancia.
Este método es un procedimiento de enumeración que encuentra el óptimo
en forma más rápida; en el método de Balas, la eficacia consiste en la evaluación
solo de unas soluciones. El método empieza poniendo todas las variables iguales
a cero y luego por medio de un procedimiento sistemático de forma consecutiva se
asigna a una por una de las variables el valor 1. Luego se reemplaza en cada una
de las restricciones y se averigua la infactibilidad. Por esta razón el método es
algunas veces llamado el algoritmo aditivo. Para describir el algoritmo, se
considera la forma general siguiente de un problema de Programación Lineal con
variables cero – uno:
Paso 1. La función objetivo debe ser del tipo minimización, con todos los
coeficientes no negativos.
Paso 2. Todas las restricciones deben ser del tipo £, con los lados derechos
negativos de ser necesario. Luego, estas restricciones se convierten a ecuaciones,
usando las variables auxiliares en el lado izquierdo de las restricciones.
Ejemplo: Max Z = 3 y1 + 2 y2 – 5 y3 – 2 y4 + 3 y5
Min W = – 3 y1 – 2 y2 + 5 y3 + 2 y4 – 3 y5
Reemplazamos: y1 = 1 – x1; y2 = 1 – x2; y3 = x3; y4 = x4; y5 = 1 – x5
Min W´ = 3 x1 + 2 x2 + 5 x3 + 2 x4 + 3 x5 – 8
Sujeta a:
Sustituimos W´ + 8 = W Min W = 3 x1 + 2 x2 + 5 x3 + 2 x4 + 3 x5
Siempre el problema nuevo a resolver consiste en la minimización de la función
objetivo, teniendo en cuenta la medida de la no factibilidad de la holgura. Cuando
la infactibilidad da el menor valor, continuamos con el siguiente paso; en el caso
de una infactibilidad cero, ésta corresponde a la solución óptima; si encontramos
varias infactibilidades iguales a cero, reemplazamos en la función objetivo y la
respuesta será la que haga esta función mínima.
x1 = 0; x2 = 0; x3 = 0; x4 = 0; x5 = 0 0 1; 0 – 2; 0 – 1; Infactibilidad 3
x1 = 0; x2 = 0; x3 = 0; x4 = 0; x5 = 0 0 2; 0 5; 0 – 12; Infactibilidad 12
x1 = 0; x2 = 0; x3 = 0; x4 = 0; x5 = 0 0 2; 0 – 2; 0 5; Infactibilidad 2
x1 = 0; x2 = 0; x3 = 0; x4 = 0; x5 = 0 0 0; 0 – 5; 0 – 1; Infactibilidad 6
x1 = 0; x2 = 0; x3 = 0; x4 = 0; x5 = 0 0 – 1; 0 2; 0 2; Infactibilidad 1
x1 = 0; x2 = 0; x3 = 0; x4 = 0; x5 = 0 0 2; 0 1; 0 2; Infactibilidad 0
Solución óptima única: x*1 = 0; x*2 = 0; x*3 = 0; x*4 = 0; x*5 = 1; W* = 3
Solución óptima única para el problema original:
y*1 = 1; y*2 = 1; y*3 = 0; y*4 = 0; y*5 = 0; Z* = 5