Programación Cuadrática y Sistemas Lineales.
Programación Entera y Métodos de Corte.
Universidad de los Andes-CODENSA
Programación Lineal Entera-Mixta
Un problema de programación lineal entera-mixta (PPLEM) es un PPL en el que
algunas de las variables toman valores enteros. Si todas las variables enteras son
binarias (0/1) el problema se denomina 0/1 PPLEM. Si todas las variables son
enteras, el problema se denomina problema de programación lineal entera (PPLE).
Hay dos técnicas de resolución de este tipo de problemas:
La de bifurcación y acotación (BA) y la de los cortes de Gomory (CG). La BA es la
que más se utiliza y la más eficiente computacionalmente. También hay una nueva
técnica Hibrida de Bifurcación y Corte (BC). Las variables binarias son muy
potentes para modelar ciertas no linealidades de diversa naturaleza que ocurren
con una cierta frecuencia en Ingeniería. Algunos ejemplos son:
1. Conjuntos alternativos de restricciones.
2. Restricciones condicionales.
3. Funciones discontinuas.
4. Funciones no convexas a trozos.
Un PPLEM en forma estándar es de la forma
Minimizar
n
Z   cjxj
j 1
sujeto a
n
 a ij x j  bi ; i  1, 2 ,..., m
j 1
x j  0;
x j  ;
j  1, 2 ,..., n
para todos a a lg un j  1, 2 ,..., n
donde N se utiliza para denominar al conjunto {0, 1,2, …}. Un ejemplo de la
región factible en este caso se muestra a continuación en la figura 1:
Figura 1. Conjunto de soluciones factibles de un PPLEE.
El método de bifurcación y acotación resuelve el PPLEM mediante una secuencia
de PPL que se obtiene relajando las condiciones de integralidad e incluyendo
restricciones adicionales.
El número de restricciones adicionales aumenta a medida que el método progresa.
Estas restricciones separan la región factible en subregiones factibles
complementarias.
Inicialmente se fijan cotas inferiores y superiores de la solución óptima. La
estrategia de bifurcación disminuye la cota superior y aumenta la inferior. La
diferencia de ambas es una medida de la proximidad de la solución actual a la
óptima, si ésta existe.
Cuando se minimiza, se puede encontrar una cota inferior relajando las
restricciones de integralidad del problema original y resolviendo el PPL resultante.
De la misma forma, el valor de la función objetivo para cualquier solución del
problema inicial es una cota superior del valor óptimo.
Este método puede parar debido a tres razones:
1. El problema actual no es factible.
2. La solución actual satisface las condiciones de integralidad.
3. La cota inferior obtenida es mayor que la superior actual.
Una bifurcación se aborta por infactibilidad, integralidad o acotación.
Para resolver un PPLEM se tienen las siguientes etapas:
 Etapa 1: Iniciación. Fijar una cota superior (∞) y una inferior (-∞) a la
solución óptima. Resolver el PPLEM relajando las condiciones de integralidad.
Si este problema es infactible, el original también lo es y no hay solución. Si la
solución es entera, es óptima. En otro caso, la cota inferior se actualiza con el
valor de la solución óptima obtenida.
 Etapa 2: Bifurcación. Usando una variable candidata a entera xk que no es
entera, se generan dos problemas, por bifurcación, a partir del original, tal
como sigue. Si el valor de la variable xk es a.b, donde a y b son sus partes entera
y fraccional, respectivamente, el primer problema bifurcado es el original
relajado con la restricción xk ≤ a, y el segundo, el original relajado con la
restricción complementaria xk ≥ a + 1. Estos problemas se sitúan en una lista de
procesado y se consideran secuencialmente o en paralelo para su resolución.
 Etapa 3: Solución. Resolver el problema siguiente en la lista de procesado.
 Etapa 4: Actualización de cotas. Si la solución del problema actual es
entera y el correspondiente valor de su función objetivo es menor que la cota
superior en curso, se actualiza ésta a éste y se almacena el problema como
candidato a óptimo. En otro caso, si el valor de la función objetivo está entre
ambas cotas, se actualiza la cota inferior con dicho valor, y se procede a bifurcar
añadiendo los dos problemas a la lista de procesado.
 Etapa 5: Corte. Si la solución suministrada por el problema en curso es entera,
no es posible la bifurcación, por lo que se aborta la bifurcación debido a la
integralidad de la solución. Si la solución no es entera y el valor de la función
objetivo es mayor que la cota superior actual, no se puede mejorar la solución
por esa rama, por lo que se aborta el proceso por esa rama, debido a acotación.
Si el problema en curso no es factible, no es posible continuar por esa rama, por
lo que se aborta el proceso, debido a infactibilidad.
 Etapa 6: Optimalidad. Si la lista de procesado está no vacía se continúa con la
Etapa 3. En otro caso, el proceso concluye. Si hay un candidato a óptimo, éste
da la solución. En otro caso, el problema es infactible. Este algoritmo revuelve
la solución óptima o informa sobre su no existencia en la Etapa 1 ó la 6.
Cualquier variable que no sea entera puede ser candidata para la bifurcación. La
elección de cuál elegir es un problema que debe resolverse basándose en el
conocimiento sobre el problema de que se trate. Los problemas de la lista de
procesado pueden procesarse mediante las estrategias de “anchura primero” o
“altura primero” o una mezcla de ambas. La figura 2 muestra ambas alternativas.
Figura 2. Estrategias de (a) “búsqueda en anchura”, y (b) “búsqueda en profundidad”.
Una estrategia de “altura primero” genera rápidamente problemas restringidos que
generalmente suministran buenas cotas superior e inferior. Además suministra
rápidamente problemas infactibles y, por tanto, el abortado de las ramas. Una
estrategia de “anchura primero” procesa problemas muy parecidos, lo cual puede
explotarse convenientemente. Las técnicas de computación paralela pueden
explotarse con ambas estrategias.
El Método de Bifurcación y Acotación
Ejemplo
Minimizar

sujeto a
Z   x1  x 2
 x1
2 x1

0
 2 x2

1
2 x2

9
x1 , x 2


La región factible es la que se muestra en la figura 3.
Figura 3. Estrategias de (a) “búsqueda en anchura”, y (b) “búsqueda en profundidad”.
 Etapa 1: Iniciación. Las cotas son +∞ y -∞. El problema relajado, que se
designa como P0, es
Minimizar
sujeto a
Z   x1  x 2
 x1
2 x1

0
 2 x2

1
2 x2

9
con solución, no entera, en el punto P1 en la figura: x1 = 5; x2 = 4.5; Z = -9.5.
Se actualiza la cota superior de -∞ a -9.5.
 Etapa 2: Bifurcación. La variable x2, genera los dos problemas con las
restricciones x2≤4 y x2≥5.
Problema P1:
Minimizar Z   x1  x 2
sujeto a
 x1
2 x1

0
 2 x2

1
2 x2

9
x2

4
Problema P2:
Minimizar Z   x1  x 2
sujeto a
 x1
2 x1

0
 2 x2

1
2 x2

9
x2

5
Etapa 3: Solución. La solución, no entera( x 
en la figura):
x1 = 4.5; x2 = 4; Z = -8.5:
1
)
, del problema P1 es (Punto P2
 Etapa 4: Actualización de cotas. Puesto que el valor -8.5 está entre las dos
cotas, se actualiza la cota inferior de -9.5 a -8.5 y se bifurca de nuevo.
La variable x1, genera los problemas con las restricciones x1≤4 y x1≥5.
Problema P3:
 x1
 0
Minimizar Z   x1  x 2
2 x1
sujeto a
x1
 2 x2

1
2 x2

9
x2

4

4
Problema P4:
Minimizar
Z   x1  x 2
 x1
sujeto a
2 x1
x1

0
 2 x2

1
2 x2

9
x2

4

5
 Etapa 5: Corte. No ocurre nada en esta etapa.
 Etapa 6: Optimalidad. Puesto que la lista de procesado no está vacía se va a la





Etapa 3 con P2.
Etapa 3: Solución. El problema P2 es infactible, por lo que no ocurre nada en
esta etapa.
Etapa 4: Actualización de cotas. No ocurre nada.
Etapa 5: Corte. Puesto que el problema es infactible, se aborta esta rama.
Etapa 6: Optimalidad. Puesto que la lista de procesado no está vacía se va a la
Etapa 3 con P3.
Etapa 3: Solución. La solución, entera, del problema P3 (punto P3 de la figura
3) es: x1 = 4; x2 = 4; Z = -8
 Etapa 4: Actualización de cotas. Por ser entera ( x1, x 2






, y estar el valor -8
entre las cotas, se actualiza la cota superior de +∞ a -8, y se almacena este
problema como candidato a óptimo.
Etapa 5: Corte. Por ser entera, se aborta el proceso en esta rama.
Etapa 6: Optimalidad. Puesto que la lista de procesado no está vacía se va a la
Etapa 3 con P4.
Etapa 3: Solución. El problema P4 es infactible, por lo que no ocurre nada.
Etapa 4: Actualización de cotas. No ocurre nada.
Etapa 5: Corte. Por ser no factible, se aborta esta rama.
Etapa 6: Optimalidad. Puesto que la lista de procesado está vacía, y hay
candidato a óptimo, éste da la solución:
x1  4; x 2  4; Z   8
*
*
*

)
El Método de los Cortes de Gomory
Una alternativa al método anterior es el método de los cortes de Gomory. En
cada iteración de este método, se resuelve el problema original relajado incluyendo
restricciones adicionales, que reducen la región factible sin excluir soluciones
enteras. En cada iteración se añade una restricción adicional, que se denomina
corte de Gomory. Esta técnica genera progresivamente una envolvente convexa de
la región factible y de esta forma se obliga a satisfacer las condiciones de
integralidad. La región factible del problema es:
Ax  b
Empleando la partición estándar del simplex obtenemos:
ó
(B
 xB 
N )
b
x
 N
BxB  N xN  b
Despejando xB se obtiene:
1
1
xB  B N xN  B b
En forma matricial tenemos:

I
 xB 
1
1
B N 

B
b

 xN 

Empleando la notación estándar del Simplex
 xB 
U 
b
x
 N 
I
ó
xB  U xN  b
Sea x B una variable básica no entera. La fila correspondiente a esta variable en la
ecuación anterior es:
i
xB   ui j xN  b i
i
j
(1)
j
Puesto que la solución en curso es básica y factible, las variables x N , al ser no
básicas, son nulas; entonces, b  x B , y puesto que x B es no entera, b i tiene que ser
no entera. Por otra parte, todo elemento uij puede expresarse como la suma de un
entero (positivo o negativo) y una fracción no negativa menor que 1, es decir
j
i
u ij  iij  f ij ;  j
donde
que 1.
iij
para todo j es entero, y
f ij
(2)
para todo j es una fracción no negativa menor
Análogamente
bi
se puede descomponer como:
bi  ii  f
(3)
i
donde i i es un entero (positivo o negativo) y f i es una fracción no negativa menor
que 1.
Algunos f ij pueden ser nulos, pero f i es necesariamente positivo.
Sustituyendo las ecuaciones (2) y (3) en la ecuación (1) obtenemos:
x B   ( iij  f ij ) x N  i i  f
i
j
i
j
ó
x B   iij x N  i i  f i   f ij x N
i
j
j
j
j
El término de la izquierda tiene que ser entero dado que todas las variables lo son,
y entonces, el de la derecha tiene que ser también entero.
Adicionalmente, fij para todo j, y x N para todo j son no negativos, por lo que
 f ij x N es no negativo. El término de la derecha de la ecuación anterior
j
f i   f ij x N , es simultáneamente: Un entero, y menor que una fracción positiva, f
i
j
, menor que 1, por lo tanto este termino es un entero no positivo.
j
j
j
Entonces:
ó
f i   f ij x N  0
j
j
 f ij x N j  f i  0
j
La última desigualdad se llama el corte de Gomory asociado a la variable básica
Cuando se quiere resolver un PPLE se utilizan los siguientes pasos:
xB .
i
PASOS
Cuando se quiere resolver un PPLE se utilizan los siguientes pasos:
 Paso 1: Iniciación. Resolver el problema inicial relajado. Si no es acotado
(infactible), parar; el problema original es no acotado (infactible).
 Paso 2: Control de Optimalidad. Si la solución es entera, parar, es la
óptima. En otro caso, ir a la Etapa siguiente.
 Paso 3: Generación de Corte. Usar una variable básica con un valor no
entero para generar un corte de Gomory.
 Paso 4: Solución del Problema. Añadir un corte de Gomory al problema en
curso, resolverlo, y continuar con la Etapa 2.
Debe señalarse que el número de restricciones crece con el número de iteraciones,
ya que se añade una nueva en cada una de ellas Por ello, es conveniente usar el
MPE, ya que el problema original se transforma en infactible y el dual en no
óptimo, pero factible.

Ejemplo
Maximizar
sujeto a
Z  1 2 0 x1  8 0 x 2
2 x1
 x2

6
7 x1
8 x2

28

0
x2

0
x1

x1
cuya función admisible se muestra en la figura 4.
Figura 4. Ilustración gráfica de los Cortes de Gomory.
El problema anterior relajado y en forma estándar es
Maximizar
sujeto a
Z  1 2 0 x1  8 0 x 2
2 x1
 x2
 x3
7 x1
 8 x2

6
 x4

28
x1 , x 2 , x 3 , x 4

0
la solución de este problema es (punto P1 de la Figura):
z* = 391.11
Teniendo
 20 
 8
x   9 
b  x  *
;
 x 2   14 


 9 
*
B
*
1
 9
Y 
 7

 9
*
Si se usa x2 para generar corte obtenemos
x2 
7
9
x3 
2
9
x4 
14
9
1
9

2 

9 

Por tanto se obtiene
y 21

y 22

b2

i21

i22

i2

f 21

f 22

f2


7

1

9
2

9


0
9
14
2
2

9


1
9
5

9
f 21

f 22

f

2
2
9
2
9
5
9
y el corte es
2

9 9
5
ó
2   x3 
   0
9   x4 
2

x3  x 4 
x3 
9
2
9
x4 
5
9
5
2
Nótese que el corte puede expresarse en función de variables originales x1 y x2. En
efecto, usando las igualdades del problema relajado en forma estándar, x3 y x4 se
expresan:
x 3  6  2 x1  x 2 ,
x 4  2 8  7 x1  8 x 2
Para obtener el primer corte (línea de trazos de la figura 4):
x1  x 2 
7
2
Así se reduce la región factible sin excluir soluciones enteras. El problema a
resolver es ahora:
Maximizar
Z  1 2 0 x1  8 0 x 2
sujeto a
2 x1
 x2
7 x1
8 x 2
 x3
 x4
x3
 x4
 x5

6

28

5
2
x1,
x 2,
x 3,
x 4,
x5

0
Nótese que el corte de Gomory se ha introducido usando la variable adicional x5.
Su solución es:
5
Z  380;
*

 x1*  
 *
*
xB   x4   

 x*  
 2


2
5
2
1


;





 1

*
U  1

 1

1
9

1 
2

9

Usando x1 para generar un nuevo corte, puesto que
x1  x 3 
1
x5 
9
b 1  x1 
*
5
2
5
2
Por tanto, se puede escribir
y11

i11

f 11

y12

i12

f 12

b1

i1

f1

1

1

1

0

f 11

0

1

8

f 21

8
f1

9
5
9

2
2

1

2
y el corte queda:

 0
2 
1
8   x3 
8
1
9

0

x

,
ó
x

5
5
 
9   x5 
9
2
16
Este segundo corte es función de las variable originales x1 y x2:
x1  x 2 
55
16
9
1
2
El problema ahora consiste en:
Maximizar
Z  1 2 0 x1  8 0 x 2
sujeto a
2 x1
 x2
7 x1
8 x2
 x3
 x4
x3
x1 ,
x2 ,
x3 ,
 x4
x4 ,
 x5

6

28

5
2
x5
 x6

x5 ,
x6

9
16
0
Cuya solución es
Z  377.5;
*
*
xB
 41 
 16 
 x1*   49 

 * 
 16 
x
  4*   
;
x 
9
5

 * 
 x 2   16 
 7 


 8 

 1

 1
*
U 
 0


 1

1
9

1
1

2

9

Usando x2 para generar un nuevo corte, puesto que
x 2  x3 
2
9
x6 
b2 
7
8
tenemos:
7
8
Por ello:
y 41

i41

f 41

1

1

0

f 41

0
y 42

i42

f 42

2

0

2

f 42

2
b4

i4

f4

f

9
7
9

8
0

7

8
y el corte resulta:

 0
8 
7
2   x3 
2
7
63

0

x

,
ó
x

6
6
 
9   x6 
9
8
16
El tercer corte en función de las variables originales resulta:
x1  x 2  3
4
9
7
8
Finalmente el problema es
Maximizar
sujeto a
Z  1 2 0 x1  8 0 x 2
2 x1
 x2
7 x1
 8 x2
 x3
 x4
x3
 x4
 x5
x2 ,
x3 ,
con solución:
x4 ,
 x6
x5 ,
*

28

5

9
16
x6
 x7

x6 ,
x7

 0
x   7

 * 
x
 4  9
*
x B   x 5*    2 

 * 
63

 x6  
 x *   16 
 1 

 3
*
3
Z  360;
6
2
x5
x1 ,

63
16
0
Puesto que es entera es la solución del problema original buscada:
x1  3;
*
x 2  0;
*
Z  360
*
Bibliografía
 “Formulación y Resolución de Modelos de Programación Matemática en Ingeniería y
Ciencia”, Enrique Castillo, Antonio J. Conejo, Pablo Pedregal, Ricardo García, Natalia
Alguacil, 2002.
Descargar

ppt - Laboratorio de Matemáticas Aplicadas