Universidad de los Andes-CODENSA

Programación Cuadrática y Sistemas Lineales.

Programación Entera y Métodos de Corte.

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

sujeto a

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.

n

jjjxcZ

1

njunaatodosparax

njx

mibxa

j

j

n

jijij

,...,2,1 lg ;

,...,2,1 ;0

,...,2,1 ;1

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

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”.

21 xxZ

21

2

21

1

,

92

122

0

xx

x

xx

x

Etapa 1: Iniciación. Las cotas son +∞ y -∞. El problema relajado, que se designa como P0, es

Minimizar

sujeto a

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

sujeto a

21 xxZ

1

1 2

2

0

2 2 1

2 9

x

x x

x

21 xxZ 1

1 2

2

2

0

2 2 1

2 9

4

x

x x

x

x

Problema P2:

Minimizar

sujeto a

Etapa 3: Solución. La solución, no entera , del problema P1 es (Punto P2 en la figura):

x1 = 4.5; x2 = 4; Z = -8.5:

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:

Minimizar

sujeto a

21 xxZ 1

1 2

2

2

0

2 2 1

2 9

5

x

x x

x

x

1( )x

21 xxZ 1

1 2

2

2

1

0

2 2 1

2 9

4

4

x

x x

x

x

x

Problema P4:Minimizar

sujeto a

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

21 xxZ

1

1 2

2

2

1

0

2 2 1

2 9

4

5

x

x x

x

x

x

Etapa 4: Actualización de cotas. Por ser entera , 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:

( 1, 2 )x x

* * *1 24; 4; 8x x Z

El Método de los Cortes de GomoryUna 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:

Empleando la partición estándar del simplex obtenemos:

ó

Despejando xB se obtiene:

Ax b

( ) B

N

xB N b

x

B NBx Nx b

1 1B Nx B Nx B b

En forma matricial tenemos:

Empleando la notación estándar del Simplex

ó

Sea una variable básica no entera. La fila correspondiente a esta variable en la ecuación anterior es:

(1)

Puesto que la solución en curso es básica y factible, las variables , al ser no básicas, son nulas; entonces, , y puesto que es no entera, 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

(2)

donde para todo j es entero, y para todo j es una fracción no negativa menor que 1.

1 1B

N

xI B N B b

x

B

N

xI U b

x

B Nx Ux b

iBx

i jiB i j N

j

x u x b

jNx

Bb xiB

xib

; ij ij iju i f j

iji ijf

Análogamente se puede descomponer como:(3)

donde es un entero (positivo o negativo) y es una fracción no negativa menor que 1.

Algunos pueden ser nulos, pero es necesariamente positivo.

Sustituyendo las ecuaciones (2) y (3) en la ecuación (1) obtenemos:

ó

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 para todo j son no negativos, por lo que

es no negativo. El término de la derecha de la ecuación anterior

, es simultáneamente: Un entero, y menor que una fracción positiva,

, menor que 1, por lo tanto este termino es un entero no positivo.

ijf if

i i ib i f

ib

ii if

( )i j

iB ij ij N ij

x i f x i f

i j j

iB ij N ij Nij j

x i x i f f x

jNx

jij Nj

f x

jij Nij

f f x if

Entonces:

ó

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:

0jij Ni

j

f f x

0jij N i

j

f x f

iBx

PASOSCuando 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

cuya función admisible se muestra en la figura 4.

Figura 4. Ilustración gráfica de los Cortes de Gomory.

1 2120 80Z x x

2 1 2 6

7 1 8 2 28

1 0

2 0

1

x x

x x

x

x

x

El problema anterior relajado y en forma estándar es

Maximizar

sujeto a

la solución de este problema es (punto P1 de la Figura):

z* = 391.11

Teniendo

Si se usa x2 para generar corte obtenemos

1 2120 80Z x x

1 2 3

1 2 4

1 2 3 4

2 6

7 8 28

, , , 0

x x x

x x x

x x x x

** *1

*2

20 8 1

9 9 9; 14 7 2

9 9 9

B

xb x Y

x

2 3 4

7 2 14

9 9 9x x x

Por tanto se obtiene

y el corte es

ó

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:

21 21 21 21

22 22 22 22

22 2 2

7 2 21

9 9 92 2 2

09 9 9

14 5 51

9 9 9

y i f f

y i f f

b i f f

3

4

5 2 2 2 2 50 3 4

9 9 9 9 9 9

xx x

x

3 4

5

2x x

3 1 2

4 1 2

6 2 ,

28 7 8

x x x

x x x

Para obtener el primer corte (línea de trazos de la figura 4):

Así se reduce la región factible sin excluir soluciones enteras. El problema a resolver es ahora:

Maximizar

sujeto a

Nótese que el corte de Gomory se ha introducido usando la variable adicional x5.

Su solución es:

1 2

7

2x x

1 2120 80Z x x

2 1 2 3 6

7 1 8 2 4 28

53 4 5

21, 2, 3, 4, 5 0

x x x

x x x

x x x

x x x x x

*1

* * * *4*2

51

129

5380; ; 1 1

221 19

B

x

Z x x U

x

Usando x1 para generar un nuevo corte, puesto que

Por tanto, se puede escribir

y el corte queda:

Este segundo corte es función de las variable originales x1 y x2:

*1 1

5

2b x

1 51 3 5

9 2x x x

11 11 11 11

12 12 12 21

11 1 1

1 1 0 0

1 8 81

9 9 95 1 1

22 2 2

y i f f

y i f f

b i f f

35 5

5

1 8 8 1 90 0 , ó x

2 9 9 2 16

xx

x

1 2

55

16x x

El problema ahora consiste en:

Maximizar

sujeto a

Cuya solución es

1 2120 80Z x x

1 2 3

1 2 4

3 4 5

5 6

1 2 3 4 5 6

2 6

7 8 28

5

29

16, , , , , 0

x x x

x x x

x x x

x x

x x x x x x

*1*

* * *4*5*2

41116 1949

1 116377.5; x ; 9 0 1

16 21

7 98

B

x

xZ U

x

x

Usando x2 para generar un nuevo corte, puesto que tenemos:

Por ello:

y el corte resulta:

El tercer corte en función de las variables originales resulta:

27

8b

2 3 6

2 7

9 8x x x

41 41 41 41

42 42 42 42

44 4 4

1 1 0 0

2 2 20

9 9 97 7 7

08 8 8

y i f f

y i f f

b i f f

36 6

6

7 2 2 7 630 0 , ó

8 9 9 8 16

xx x

x

1 2 3x x

Finalmente el problema es

Maximizar

sujeto a

con solución:

1 2120 80Z x x

1 2 3

1 2 4

3 4 5

5 6

6 7

1 2 3 4 5 6 7

2 6

7 8 28

5

29

1663

16, , , , , , 0

x x x

x x x

x x x

x x

x x

x x x x x x x

*3*4

* * *5*6*1

0

7

9360; 2

63

163

B

x

x

Z x x

x

x

Puesto que es entera es la solución del problema original buscada: * * *

1 23; 0; 360x x Z

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.