Tema 6: Programación entera: Bifurcación y planos de corte.

Objetivos del tema:

 Introducir las principales técnicas de programación entera

 Introducir el método de bifurcación y acotación (Brach and Bound, B&B) para problemas de Programación Entera

 Analizar las diferentes estrategias que pueden utilizarse en cada una de las etapas del algoritmo B&B

 Utilizar el algoritmo B&B para resolver algunos problemas de Programación Lineal Entera Puros, Mixtos y Binarios

 Presentar algunas de las técnicas de preprocesamiento para problemas de Programación Lineal Entera Binaria

 Presentar un procedimiento para la generación de planos de corte en problemas de Programación Lineal Entera Binarios

 Introducir el método de los planos de corte de Gomoroy para Programación Lineal Entera

1
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Problemas de Programación Lineal Entera

Tal y como se vio en el Tema 2 en muchos problemas de programación lineal sólo tienen sentido aquellas soluciones de la región factible
en las que todas o algunas de las variables de decisión toman valores enteros. Este tipo de problemas se denominan en general
Problemas de Programación Lineal Entera (PPLE). En concreto:

• Si todas las variables del problema son enteras se habla de PPLE Pura.

• Si sólo algunas son enteras y las restantes son continuas se habla de PPLE Mixta.

• Si todas las variables enteras son binarias (0/1) el problema se denomina PPLE Binaria.

En ingeniería los problemas más frecuentes son los PPLE Mixta. Estos problemas proporcionan un marco de modelado flexible y
eficiente para formular y resolver muchos problemas de ingeniería. Un PPLE Mixta general se formula en forma estándar como:
n
Minimizar z  cj xj
j 1
n
sujeto a a
j 1
ij x j  bi ; i  1, 2,..., m

xj  0 ; j  1, 2,..., n
xj   ; j  1, 2,..., I ; I n

Este tema se proporciona una introducción a los principales algoritmos para obtener la solución a este tipo de problemas. En concreto, se
estudian los métodos siguientes:

• Método de bifurcación y acotación: La solución al PPLE original se obtiene resolviendo una secuencia ordenada de PPLs que se
obtienen relajando las restricciones de integralidad y añadiendo restricciones adicionales.

• Método de los planos de corte: En esta técnica, se resuelve el problema original relajado en el que se incluyen restricciones
adicionales, denominadas cortes de Gomoroy, que reducen la región factible sin excluir soluciones que cumplen las condiciones de
integralidad.

2
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Método de bifurcación y acotación para un PPLE Mixta.

El método de bifurcación y acotación (B&B, de Branch and Bound) resuelve un PPLE resolviendo una secuencia ordenada de PPLs que
se obtienen relajando las restricciones de integralidad y añadiendo restricciones adicionales. El número de restricciones adicionales crece
a medida que el método B&B progresa. Estas restricciones permiten separar la región factible en subregiones complementarias.

El método B&B establece inicialmente cotas inferior y superior del valor óptimo de la función objetivo. El mecanismo de bifurcación
aumenta progresivamente el valor de la cota inferior y disminuye también progresivamente el valor de la cota superior. La diferencia entre
estas cotas es una medida de la proximidad de la solución actual a la óptima, si ésta existe.

Al minimizar, se obtiene una cota inferior de la solución óptima relajando las restricciones de integralidad del PPLE inicial y resolviendo el
PPL resultante. Además, el valor de la función objetivo para cualquier solución del PPLE original es una cota superior de la solución
óptima. De manera análoga, al maximizar, la solución del PPL relajado es una cota superior para el óptimo y cualquier solución del PPLE
original es una cota inferior de la solución óptima.

A continuación se enumeran los pasos del algoritmo B&B para un PPLE Mixta:

Paso 1: Iniciación
1.1 Se establece una cota superior () y una cota inferior (−) de la solución óptima.
1.2 Se resuelve el PPLE Mixta inicial relajando las restricciones de integralidad.
1.2.a Si el problema relajado es infactible, el original también lo es y no hay solución.
1.2.b Si la solución obtenida satisface las condiciones de integralidad, es óptima.
1.2.c En cualquier otro caso, se actualiza el valor de la cota correspondiente con el valor de la función objetivo resultante.

Paso 2: Bifurcación
2.1 Empleando la variable xk que ha de ser entera y no lo es, se generan mediante bifurcación dos problemas. Si el valor de la
variable que ha de ser entera xk es a.b, donde a y b son sus partes entera y fraccional respectivamente, los problemas fruto de la
bifurcación son los siguientes.
2.1.a El primer problema es el PPLE relajado al que se la añade la restricción xk≤a
2.1.b El segundo es el PPLE relajado al que se le añade la restricción xk≥a+1

2.2 Estos problemas se colocan ordenadamente en una lista de problemas a procesar que son resueltos secuencialmente o en
paralelo. Obsérvese que la técnica de bifurcación propuesta cubre completamente el espacio de soluciones.

3
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Paso 3: Solución

3.1 Se resuelve el siguiente problema en la lista de problemas a procesar.

Paso 4: Acotación

4.1 Si la solución del problema actual satisface las condiciones de integralidad y el valor óptimo de su función objetivo es menor que la
cota superior actual, dicha cota se actualiza al valor óptimo de la función objetivo del problema resuelto, y el minimizador actual se
almacena como el mejor candidato a minimizador del problema original. En caso de maximizaciones, la cota inferior actual se
actualiza al valor óptimo de la función objetivo del problema resuelto si éste es menor que dicha cota inferior.

4.2 Si, por el contrario, la solución obtenida no satisface las restricciones de integralidad y el valor de la correspondiente función
objetivo esta entre las cotas inferior y superior, se actualiza el valor de la cota inferior al valor de la función objetivo del problema
resuelto y se procede a bifurcar de nuevo. En caso de maximizaciones, se actualiza el valor de la cota superior al valor de la
función objetivo del problema resuelto y se procede a bifurcar de nuevo.

4.3 Los problemas generados en el proceso de bifurcación se añaden a la lista de problemas que han de resolverse.

Paso 5: Poda

5.1 Poda por cotas: Tiene lugar si la solución no satisface las condiciones de integralidad y además el valor de la función objetivo del
problema resuelto es mayor que la cota superior para minimizaciones o menor que la cota inferior para maximizaciones. En este
caso no es posible obtener soluciones mediante bifurcaciones adicionales de esa rama.

5.2 Poda por infactibilidad: Tiene lugar si el problema es infactible.

5.3 Poda por integralidad: Tiene lugar si la solución del problema actual cumple las restricciones de integralidad.

Paso 6: Optimalidad

6.1 Si la lista de problemas a procesar no está vacía, se continua con el paso 3.

6.2 Si la lista de problemas a procesar está vacía, el procedimiento concluye.

6.3 Concluido el problema, si existe un candidato a minimizador, dicho candidato es el minimizador; en caso contrario, el problema es
infactible.

4
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
El algoritmo de B&B devuelve la solución óptima o notifica la infactibilidad bien en el paso 1 ó en el paso 6. El proceso de bifurcación
concluye por la poda de la rama correspondiente como consecuencia de una de las tres razones siguientes:

1. La solución del problema relajado es mayor que la cota superior disponible en el caso de minimizaciones, o menor que la cota inferior
disponible para el caso de maximizaciones.
2. El problema considerado es infactible.
3. La solución obtenida satisface las condiciones de integralidad.

Como puede verse, los pasos centrales del algoritmo B&B son la bifurcación, la acotación y la poda. La diferencia entre un algoritmo
B&B u otro radica en las diferentes estrategias que pueden llevarse a cabo a la hora de implementar tales pasos.

Estrategias de bifurcación y procesamiento

Cualquier variable que deba ser entera pero que no lo sea en la solución actual, es una variable candidata para bifurcación. Cuál escoger
no es una cuestión trivial, y su respuesta ha de basarse en la estructura del problema.

Los problemas almacenados para ser procesados pueden tratarse mediante estrategias en profundidad, en anchura o mixtas. La
siguiente figura ilustra las dos primeras alternativas. Normalmente el conocimiento técnico del problema permite establecer el tipo de
estrategia a utilizar.

Búsqueda en profundidad Búsqueda en anchura

• Una estrategia de procesado en profundidad origina rápidamente problemas fuertemente restringidos que producen buenas cotas
superiores e inferiores. De esta forma, da lugar a problemas infactibles y, por tanto, a una deseable eliminación de ramas.

• Por el contrario, una estrategia en anchura permite tratar problemas muy similares, de lo que pueden desprenderse ventajas
computacionales como es la reoptimización eficiente del problema relajado actual partiendo de la solución del anterior.

5
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Estrategias de acotación

La acotación es normalmente llevada a cabo mediante la denominada relajación lineal, consistente en la obtención de la cota a partir de
la resolución del PPL obtenido relajando las restricciones de integralidad del PPLE original.

Sin embargo, existen otras posibles relajaciones del PPLE original, como la relajación Lagrangiana en la que todo el conjunto de
restricciones (Ax ≤ b en notación matricial) es eliminado y la función objetivo del problema Maximixar z=cTx es reemplazada por
Maximizar zR=cTx – (Ax – b), donde  ≥0 es un vector fijo.

Si x* es una solución óptima del problema original z ≤ zR, por lo que resolviendo la relajación Lagrangiana el valor óptimo de zR
proporciona una cota válida para el problema original. Escogiendo adecuadamente el valor del vector  dicha cota tiende a ser similar
a la proporcionada por la solución de la relajación lineal, pero con la ventaja de que sin las restricciones del problema la resolución de la
relajación Lagrangiana puede llegar a ser mucho más rápida.

En contrapartida, la poda llevada a cabo tras la acotación mediante la relajación Lagrangiana no suele ser tan potente como la llevada a
cabo tras la relajación lineal. En general, dos son los factores deseables a la hora de escoger una u otra estrategia de acotación: (a) una
rápida resolución del problema relajado; y (b) la obtención de una buena cota. En general, la relajación lineal suele ofrecer un buen
compromiso entre ambos factores.

Estrategias de poda

Como se ha comentado anteriormente, la poda de la rama correspondiente tiene lugar por una de las tres razones siguientes:

1. La solución del problema relajado es mayor que la cota superior disponible en el caso de minimizaciones, o menor que la cota
inferior disponible para el caso de maximizaciones.
2. El problema considerado es infactible.
3. La solución obtenida satisface las condiciones de integralidad.

En cuanto al punto 1 puede optarse por convertir el problema a la forma estándar de maximización (tal y como se vio en el Tema 4) y
podar siempre que la solución del problema relajado sea inferior al óptimo actual.

En cuanto al punto 3, si el problema relajado y el subproblema generado mediante bifurcación tan sólo difieren en la falta de alguna
restricción, la poda puede simplemente basarse en comprobar si la solución óptima de dicha relajación es una solución factible para el
subproblema, ya que en este caso dicha solución también será óptima para este subproblema.

6
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Ejemplo 1: Método B&B para un PPLE Pura

Sea el siguiente PPLE Pura:

Minimizar z   x1  x2
sujeto a  x1  0 x2  0
2 x1  2 x2  1
z
2 x2  9
x1 , x2  

Se trata de obtener su solución mediante el método de B&B.

Solución: Método B&B para un PPLE Pura

Paso 1: Iniciación x2 z = -x1 -x2

2x1 -2x2 ≤ 1
1.1 La cota superior inicial es + y la inferior −.
5
1.2 El problema relajado, denominado P0, es el siguiente: 2x2 ≤ 9
4
Minimizar z   x1  x2
sujeto a  x1  0 x2  0 3
z 2 x1  2 x2  1
2 x2  9 2

Solución: z = -9.5 para el punto (x1=5, x2=4.5) 1

1.2c Esta solución no satisface las condiciones de integralidad (x2).

1 2 3 4 5 x1
Así, el valor de la función objetivo se emplea para actualizar la
cota inferior de – a -9.5 -x1 ≤ 0

7
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Solución: Método B&B para un PPLE Pura (continuación 1) x2 z = -x1 -x2
2x1 -2x2 ≤ 1
Paso 2: Bifurcación
5
2.1 La variable que ha de ser entera x2, mediante bifurcación da lugar
a los dos problemas siguientes: x2 ≤ 4

Problema P1 Problema P2
3
Minimizar z   x1  x2 Minimizar z   x1  x2
sujeto a  x1  0 x2  0 sujeto a  x1  0 x2  0 2

2 x1  2 x2  1 2 x1  2 x2  1
z z 1
2 x2  9 2 x2  9
x2  4 x2  5
1 2 3 4 5 x1
2.2 Estos problemas se colocan en la lista de problemas a procesar.
-x1 ≤ 0

Paso 3: Solución

3.1 Se resuelve el problema P1

Solución: z = -8.5 para el punto (x1=4.5, x2=4)

Paso 4: Acotación

4.2 Puesto que la solución obtenida no satisface las condiciones de integralidad (x1), y que el valor de la función objetivo (z=−8.5)
está entre los valores de las cotas inferior y superior, el valor actual de la cota inferior se actualiza de −9.5 a −8.5 (la solución
óptima está por tanto entre −8.5 y ).
El problema se vuelve a bifurcar. Para ello, la variable que deber ser entera pero no lo es (x1), mediante bifurcación da lugar a los
dos problemas P3 y P4 que incluyen las restricciones adicionales son x1 ≤ 4 y x1 ≥ 5 respectivamente.

4.3 Los problemas generados en el proceso de bifurcación se añaden a la lista de problemas que han de resolverse.

8
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Solución: Método B&B para un PPLE Pura (continuación 2) x2 z = -x1 -x2
2x1 -2x2 ≤ 1
Problema P3 Problema P4
5
Minimizar z   x1  x2 Minimizar z   x1  x2
sujeto a  x1  0 x2  0 sujeto a  x1  0 x2  0 x2 ≤ 4
2 x1  2 x2  1 2 x1  2 x2  1
z 2 x2  9 z 2 x2  9 3
x2  4 x2  4
x1  2 x2  4 x1  2 x2  5 2

Paso 5: Poda (No ocurre nada en este paso) 1

Paso 6: Control de optimalidad

1 2 3 5 x1
6.1 Puesto que la lista de problemas a procesar no está vacía, x1 ≤ 4
se continúa con el problema P2 en el paso 3. -x1 ≤ 0

Paso 3: Solución (El problema P2 es infactible; por tanto, nada tiene lugar en este paso)

Paso 4: Acotación (No ocurre nada en este paso)

Paso 5: Poda

5.2 Puesto que el problema P2 es infactible, la rama correspondiente se poda por infactibilidad.

Paso 6: Control de optimalidad

6.1 Puesto que la lista de problemas no está vacía, se continúa con el problema P3 en el paso 3.

Paso 3: Solución

3.1 Se resuelve el problema P3 Solución: z = -8 para el punto (x1=4, x2=4)

9
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Solución: Método B&B para un PPLE Pura (continuación 3)

Paso 4: Acotación

4.1 Puesto que la solución obtenida cumple las condiciones de integralidad (x1, x2  ), y el valor de la función objetivo (−8) está
entre las cotas inferior y superior, el valor de la cota superior se actualiza de + a −8, y el minimizador obtenido se almacena
como mejor candidato a minimizador del problema original.

Paso 5: Poda

5.3 Puesto que la solución actual satisface las condiciones de integralidad, no procede bifurcar adicionalmente, y la rama se poda.

Paso 6: Control de optimalidad

6.1 Puesto que la lista de problemas a procesar no está vacía, se continúa con el problema P4 en el paso 3.

Paso 3: Solución (El problema P4 es infactible, por tanto, no tiene lugar nada en este paso)

Paso 4: Acotación (No ocurre nada en este paso)

P0

Paso 5: Poda x2 ≤ 4 x2 ≥ 5

5.2 Puesto que el problema P4 es infactible, la rama correspondiente se poda por

infactibilidad. P1 P2

Paso 6: Control de optimalidad

x1 ≤ 4 x1 ≥ 5
*
6.2 Puesto que la lista de problemas a procesar está vacía, el procedimiento concluye. P3 P4

6.3 Concluido el proceso, como hay un candidato a minimizador, este candidato es la

solución del problema original:
*
Solución: z = -8 para el punto (x1=4, x2=4)
* No es posible otra bifurcación

10
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Ejemplo 2: Método B&B para un PPLE Mixta

Sea el siguiente PPLE Mixta:

Minimizar z  3 x1  2 x2
sujeto a x1  2 x2  x3  x4  5
2

2 x1  2 x2  x3  x4  3
z 2

x1 , x2 , x3 , x4  0
x2 , x3  

Se trata de obtener su solución mediante el método de B&B.

Solución: Método B&B para un PPLE Mixta

Paso 1: Iniciación

1.1 La cota superior inicial es + y la inferior −.

1.2 El problema relajado, denominado P0, es el siguiente:

Minimizar z  3 x1  2 x2
sujeto a x1  2 x2  x3  x4  52
z  2 x1  2 x2  x3  x4  32
x1 , x2 , x3 , x4  0

Solución: z = 0 para el punto (x1=0, x2=0, x3=2.5, x4=1.5)

1.2c Esta solución no satisface las condiciones de integralidad (x3  ).

Así, el valor de la función objetivo se emplea para actualizar la cota inferior de – a 0

11
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Solución: Método B&B para un PPLE Mixta (continuación 1)

Paso 2: Bifurcación

2.1 La variable que ha de ser entera x3, mediante bifurcación da lugar a los dos problemas siguientes:

Problema P1 Problema P2

Minimizar z  3 x1  2 x2 Minimizar z  3 x1  2 x2
sujeto a x1  2 x2  x3  x4  5
2
sujeto a x1  2 x2  x3  x4  5
2

2 x1  2 x2  x3  x4  3
2 x1  2 x2  x3  x4  3
z 2
z 2

x3  x4  2 x3  x4  3
x1 , x2 , x3 , x4  0 x1 , x2 , x3 , x4  0

2.2 Estos problemas se colocan en la lista de problemas a procesar.

Paso 3: Solución

3.1 Se resuelve el problema P1

Solución: z = 1.5 para el punto (x1=0.5, x2=0, x3=2, x4=0.5)

Paso 4: Acotación

4.1 Puesto que la solución obtenida satisface las condiciones de integralidad (x2, x3  ), y que el valor de la función objetivo (z=1.5)
es menor que el valor actual de la cota superior, ésta se actualiza de  a 1.5 (la solución óptima está por tanto entre 0 y 1.5), y el
minimizador encontrado se almacena como mejor candidato a minimizador del problema original.

Paso 5: Poda
5.3 Puesto que la solución actual satisface las condiciones de integralidad (para x2 y x3), la rama se poda y se continua con el paso 3.

Paso 3: Solución
3.1 Se resuelve el problema P2. Solución: z = 0.5 para el punto (x1=0, x2=0.25, x3=3, x4=1.25)

12
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Solución: Método B&B para un PPLE Mixta (continuación 2)

Paso 4: Acotación

4.2 Puesto que esta solución no satisface las condiciones de integralidad (x2) y el valor correspondiente de la función objetivo (0.5)
está entre las cotas interior y superior, la cota inferior se actualiza de 0 a 0.5 (la solución óptima está por tanto entre 0.5 y 1.5).
A continuación se procede a bifurcar sobre la variable x2, lo que da lugar a los dos problemas siguientes:

Problema P3 Problema P4

Minimizar z  3 x1  2 x2 Minimizar z  3 x1  2 x2
sujeto a x1  2 x2  x3  x4  5
2
sujeto a x1  2 x2  x3  x4  5
2

2 x1  2 x2  x3  x4  3
2
2 x1  2 x2  x3  x4  3
2

z x3  x4  3 z x3  x4  3
x2  x3  x4  0 x2  x3  x4  1
x1 , x2 , x3 , x4  0 x1 , x2 , x3 , x4  0

4.3 Los problemas generados en el proceso de bifurcación se añaden a la lista de problemas que han de resolverse.

Paso 5: Poda (No ocurre nada en este paso)

Paso 6: Control de optimalidad

6.1 Puesto que la lista de problemas a procesar no está vacía, se continúa con el problema P3 en el paso 3.

Paso 3: Solución (El problema P3 es infactible; por tanto, nada tiene lugar en este paso)

Paso 4: Acotación (No ocurre nada en este paso)

Paso 5: Poda

5.2 Puesto que el problema P3 es infactible, la rama correspondiente se poda por infactibilidad.

13
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Solución: Método B&B para un PPLE Mixta (continuación 3)

Paso 6: Control de optimalidad

6.1 Puesto que la lista de problemas no está vacía, se continúa con el problema P4 en el paso 3.

Paso 3: Solución

3.1 Se resuelve el problema P4

Solución: z = 2 para el punto (x1=0, x2=1, x3=4.5, x4=0.5)

Paso 4: Acotación (No ocurre nada en este paso)

Paso 5: Poda

5.1 Puesto que la solución obtenida no satisface las condiciones de integralidad (x3), y el valor correspondiente de la función
objetivo es mayor que el valor actual de la cota superior, no podrá lograrse una mejor solución que la disponible llevando a cabo
bifurcaciones adicionales. Así, la rama se poda por cotas.

P0

Paso 6: Control de optimalidad x3 ≤ 2 x3 ≥ 3

6.2 Puesto que la lista de problemas a procesar está vacía, el procedimiento concluye.
P1 P2
6.3 Concluido el proceso, como hay un candidato a minimizador, este candidato es la
x2 ≤ 0 x2 ≥ 1
solución del problema original:
*
P3 P4

Solución: z = 1.5 para el punto (x1=0.5, x2=0, x3=2, x4=0.5) * *

* No es posible otra bifurcación

14
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Ejemplo 3: Método B&B para un PPLE Binaria

Obtener la solución mediante el método de B&B del PPLE Binaria mostrado en la transparencia 5 del Tema 2 pero con los datos de la
siguiente tabla. Además, el capital total para la inversión es de 10 M euros.

Maximizar z  9 x1  5 x2  6 x3  4 x4
Decisiones Beneficio estimado Capital requerido
sujeto a 6 x1  3 x2  5 x3  2 x4  10
Instalar factoría en Zaragoza 9 M euros 6 M euros
x3  2 x4  1
Instalar factoría en Sevilla 5 M euros 3 M euros
z   x1  3 x2  5 x3  2 x4  0
Construir almacén en Zaragoza 6 M euros 5 M euros
 x2  5 x3  2 x4  0
Construir almacén en Sevilla 4 M euros 2 M euros x1 , x2 , x3 , x4  0,1

Solución: Método B&B para un PPLE Binaria

//Variables de decisión
dvar int x1 in 0..1;
Paso 1: Iniciación dvar int x2 in 0..1;
dvar int x3 in 0..1;
1.1 La cota superior inicial es + y la inferior −. dvar int x4 in 0..1;

1.2 El problema relajado, denominado P0, es el siguiente: //Función objetivo

maximize 9*x1 + 5*x2 + 6*x3 + 4*x4;
Maximizar z  9 x1  5 x2  6 x3  4 x4 //Restricciones
sujeto a 6 x1  3 x2  5 x3  2 x4  10 subject to {
6*x1 + 3*x2 + 5*x3 + 2*x4 <= 10;
x3  2 x4  1 x3 + x4 <= 1;
-x1 + x3 <= 0;
z   x1  3 x2  5 x3  2 x4  0 -x2 + x4 <= 0;
 x2  5 x3  2 x4  0 }

x1 , x2 , x3 , x4  [0,1]
solution (optimal) with objective 14:
x1 = 1;
Solución: z = 16.5 para el punto (x1=5/6, x2=1, x3=0, x4=1) x2 = 1;
x3 = 0;
x4 = 0;
1.2c Esta solución no satisface las condiciones de integralidad (x1{0,1}).
Así, el valor de la función objetivo se emplea para actualizar la cota superior de  a 16.5

15
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Solución: Método B&B para un PPLE Binaria (continuación 1)

Paso 2: Bifurcación

2.1 La variable que ha de ser binaria x1, mediante bifurcación da lugar a los dos problemas siguientes:

Problema P1 (x1=0) Problema P2 (x1=1)

Maximizar z  5 x2  6 x3  4 x4 Maximizar z  5 x2  6 x3  4 x4  9
sujeto a 3 x2  5 x3  2 x4  10 sujeto a 3 x2  5 x3  2 x4  4
x3  2 x4  1 x3  2 x4  1
z 3 x2  5 x3  2 x4  0 z 3 x2  5 x3  2 x4  1
 x2  5 x3  2 x4  0  x2  5 x3  2 x4  0
x2 , x3 , x4  [0,1] x2 , x3 , x4  [0,1]

2.2 Estos problemas se colocan en la lista de problemas a procesar.

Paso 3: Solución

3.1 Se resuelve el problema P1

Solución: z = 9 para el punto (x1=0, x2=1, x3=0, x4=1)

Paso 4: Acotación

4.1 Puesto que la solución obtenida satisface las condiciones de integralidad (x1, x2, x3, x4  {0,1}), y que el valor de la función objetivo
(z=9) es mayor que el valor actual de la cota inferior, ésta se actualiza de − a 9 (la solución óptima está por tanto entre 9 y 16.5),
y el maximizador encontrado se almacena como mejor candidato a maximizador del problema original.

Paso 5: Poda

5.3 Puesto que la solución actual satisface las condiciones de integralidad (x1, x2, x3, x4  {0,1}), la rama se poda por integralidad y
se continua con el paso 3.

16
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Solución: Método B&B para un PPLE Binaria (continuación 2)

Paso 3: Solución

3.1 Se resuelve el problema P2

Solución: z = 16.2 para el punto (x1=1, x2=4/5, x3=0, x4=4/5)

Paso 4: Acotación

4.2 Puesto que esta solución no satisface las condiciones de integralidad (x2, x4{0,1}) y el valor correspondiente de la función objetivo
(16.2) está entre las cotas interior y superior, la cota superior se actualiza de 16.5 a 16.2 (la solución óptima está ahora por tanto
entre 9 y 16.2).

A continuación se procede a bifurcar sobre la variable x2, lo que da lugar a los dos problemas siguientes:

Problema P3 (x1=1, x2=0) Problema P4 (x1=1, x2=1)

Maximizar z  6 x3  4 x4  9 Maximizar z  6 x3  4 x4  14
sujeto a 5 x3  2 x4  4 sujeto a 5 x3  2 x4  1
x3  2 x4  1 x3  2 x4  1
z  5 x3  2 x4  0 z  5 x3  2 x4  1
x4  0 x4  1
x3 , x4  [0,1] x3 , x4  [0,1]

4.3 Los problemas generados en el proceso de bifurcación se añaden a la lista de problemas que han de resolverse.

Paso 5: Poda (No ocurre nada en este paso)

Paso 6: Control de optimalidad

6.1 Puesto que la lista de problemas a procesar no está vacía, se continúa con el problema P3 en el paso 3.

17
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Solución: Método B&B para un PPLE Binaria (continuación 3)

Paso 3: Solución

3.1 Se resuelve el problema P3 Solución: z = 13 para el punto (x1=1, x2=0, x3=4/5, x4=0)

Paso 4: Acotación (En este caso, antes de acotar y bifurcar resolveremos P4, adoptando por tanto una estrategia en anchura)

Paso 5: Poda (No ocurre nada en este paso)

Paso 6: Control de optimalidad

6.1 Puesto que la lista de problemas a procesar no está vacía, se continúa con el problema P4 en el paso 3.

Paso 3: Solución

3.1 Se resuelve el problema P4 Solución: z = 16 para el punto (x1=1, x2=1, x3=0, x4=0.5)

Paso 4: Acotación

4.2 Ni P3 ni P4 satisfacen las condiciones de integralidad. Como la solución del problema P4 genera una cota superior a la
proporcionada por la solución del problema P3, se continua acotando desde P4. Puesto que su solución no satisface las
condiciones de integralidad (x4{0,1}) y el valor correspondiente de la función objetivo (16) está entre las cotas interior y superior,
la cota superior se actualiza de 16.2 a 16 (la solución óptima está ahora por tanto entre 9 y 16).

A continuación se procede a bifurcar sobre la variable x3 desde el problema P4, lo que da lugar a los dos problemas siguientes:

Problema P5 (x1=1, x2=1, x3=0) Problema P6 (x1=1, x2=1, x3=1)

Maximizar z  4 x4  14 Maximizar z  4 x4  20
sujeto a 2 x4  1 sujeto a x  0
z z 4
x4  [0,1] x4  [0,1]

4.3 Los problemas generados en el proceso de bifurcación se añaden a la lista de problemas que han de resolverse.

18
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Solución: Método B&B para un PPLE Binaria (continuación 4)

Paso 3: Solución

3.1 Se resuelve el problema P5

Solución: z = 16 para el punto (x1=1, x2=1, x3=1, x4=0.5)

Paso 4: Acotación (No ocurre nada en este paso, al igual que en el caso anterior, se espera a resolver P6)

Paso 5: Poda (No ocurre nada en este paso)

Paso 6: Control de optimalidad

6.1 Puesto que la lista de problemas a procesar no está vacía, se continúa con el problema P6 en el paso 3.

Paso 3: Solución (El problema P6 es infactible; por tanto, nada tiene lugar en este paso)

Paso 4: Acotación (No ocurre nada en este paso)

Paso 5: Poda

5.2 Puesto que el problema P6 es infactible, la rama correspondiente se poda por infactibilidad.

Paso 6: Control de optimalidad

6.1 Puesto aún están pendientes las bifurcaciones de los problemas P3 y P5, la lista de problemas a procesar no estará vacía tras las
bifurcaciones correspondientes.

Dado que el nodo P5 se ha creado más recientemente que el P3, y por tanto la resolución de los problemas obtenidos tras la
bifurcación será más eficiente que la de los asociados a P3, se continua bifurcando P5 en el paso 2.

19
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Solución: Método B&B para un PPLE Binaria (continuación 5)

Paso 2: Bifurcación

2.1 La variable que ha de ser binaria x4, mediante bifurcación da lugar a los dos problemas siguientes:

Problema P7 (P5 con x4=0) Problema P8 (P5 con x4=1)

Solución: z = 14 para el punto (x1=1, x2=1, x3=0, x4=0) Solución: No es factible

Paso 4: Acotación

4.1 Puesto que la solución de P7 satisface las condiciones de integralidad (x1, x2, x3, x4  {0,1}), y que el valor de la función objetivo
(z=14) es mayor que el valor actual de la cota inferior, ésta se actualiza de 9 a 14 (la solución óptima está por tanto entre 14 y 16),
y el maximizador encontrado se almacena como mejor candidato a maximizador del problema original.

Paso 5: Poda
P0
5.3 Puesto que la solución de P7 satisface las condiciones de integralidad (x1, x2, x3, x4  {0,1}),
x1 = 0 x1 = 1
la rama se poda por integralidad.
P1 P2
5.2 Puesto que el problema P8 es infactible, la rama correspondiente se poda por infactibilidad.

5.1 Puesto que P3 no satisface las condiciones de integralidad y además el valor de su función * x2 = 0 x2 = 1

objetivo (13) es menor que la cota superior (14), no es posible obtener soluciones mediante P3 P4
bifurcaciones adicionales de esa rama, y por tanto se poda por cotas.
* x3 = 0 x3 = 1

Paso 6: Control de optimalidad P5 P6

6.2 Puesto que la lista de problemas a procesar está vacía, el procedimiento concluye. x4 = 0 x4 = 1
*
6.3 Concluido el proceso, como hay un candidato a maximizador, este candidato es la P7 P8
solución del problema original:
Solución: z = 14 para el punto (x1=1, x2=1, x3=0, x4=0)
*
* No es posible otra bifurcación

20
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Técnicas de preprocesamiento para PPLE Binarios

En la mayoría de las ocasiones, la formulación del PPLE Binario proporcionado por el usuario puede ser inspeccionada con el fin de
reformular dicho problema de tal forma que su solución sea mucho más rápida sin eliminar ninguna región factible. Dicha reformulación
del problema original se basa en las tres técnicas siguientes:

1. Fijado de variables: Consiste en identificar aquellas variables cuyo valor puede fijarse a uno de sus posibles valores (0 ó 1) debido a
que para el otro valor la solución no es ni óptima ni factible.

2. Eliminación de restricciones redundantes: Consiste en identificar aquellas restricciones que ya están automáticamente incluidas en
otras para eliminarlas.

3. Estrechamiento de restricciones: También llamado reducción de coeficientes, consiste en endurecer ciertas restricciones con el fin
de reducir la región factible del problema relajado sin eliminar ninguna solución factible del PPLE Binario original.

1. Fijado de variables

Si un valor de una determinada variable no puede satisfacer una restricción incluso cuando el resto de variables utilizan sus mejores
valores para satisfacerla, entonces el valor de dicha variable debe ser fijado a su otro valor.

Por ejemplo, para las siguientes restricciones ≤ se puede fijar el valor de la variable x1 a 0, ya que para x1=1 las restricciones no son
satisfechas aún en el caso de utilizar los mejores valores (0 para una variable con coeficiente no negativo y 1 para una variable con
coeficiente negativo) para el resto de variables:

3 x1  2  x1  0 ya que 3(1)  2
3 x1  x2  2  x1  0 ya que 3(1)  1(0)  2
5 x1  x2  2 x3  2  x1  0 ya que 5(1)  1(0)  2(1)  2

El procedimiento general para chequear cualquier restricción ≤ consiste en identificar la variable con el mayor coeficiente positivo, y si la
suma de dicho coeficiente con el resto de coeficientes negativos es superior al término independiente situado al lado derecho de la
restricción, entonces el valor de dicha variable debe fijarse a 0. A continuación, el procedimiento debe repetirse para la siguiente variable
con el mayor coeficiente positivo, etc…

21
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Un procedimiento análogo puede utilizarse para fijar el valor de una variable a 1 en el caso de restricciones ≥, como se muestra a
continuación para la variable x1:

3 x1  2  x1  1 ya que 3(0)  2
3 x1  x2  2  x1  1 ya que 3(0)  1(1)  2
5 x1  x2  2 x3  2  x1  1 ya que 5(0)  1(1)  2(0)  2

Una restricción ≥ también nos puede permitir fijar el valor de una variable a 0, como se muestra a continuación:

x1  x2  2 x3  1  x3  0 ya que 1(1)  1(1)  2(1)  1

A continuación se muestra otro ejemplo en el que una restricción ≥ nos permite fijar el valor de una variable a 1 y el de otra a 0:

3 x1  x2  3 x3  2  x1  1 ya que 3(0)  1(1)  3(0)  2

y x3  0 ya que 3(1)  1(1)  3(1)  2

Análogamente, una restricción ≤ con el término independiente del lado derecho negativo, permite fijar el valor de una variable a

3 x1  2 x2  1  x1  0 ya que 3(1)  2(1)  1

y x2  1 ya que 3(0)  2(0)  1

A veces, fijar el valor de una variable en una restricción puede generar que se pueda fijar el valor de otras variables en otras restricciones.
Por ejemplo, supóngase la siguiente restricción:

3x1  x2  2 x3  2  x1  1 ya que 3(0)  1(1)  2(0)  2

que sobre x1  x4  x5  1 da lugar a x4  0 y x5  0

y sobre  x5  x6  0 da lugar a x6  0

22
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
En algunas ocasiones, es posible combinar una o más restricciones mutuamente exclusivas junto con otra restricción para fijar el valor de
alguna variable como en el ejemplo siguiente:

8 x1  42  5 x3  3 x4  2 
  x1  0 ya que 8(1)  max 4,5 (1)  3(0)  2
x2  x3  1

Para terminar, y sin entrar en más detalles, simplemente comentar que otras alternativas para el finado de variables que incluyen criterios
de optimalidad, y que el fijado de variables puede llegar a tener un impacto dramático en la reducción del tamaño del problema pudiendo
llegar al 50% o superior.

2. Eliminación de restricciones redundantes

Si una restricción funcional se satisface hasta para los peores valores de sus variables binarias, entonces es redundante y puede ser
eliminada del modelo.

• Para una restricción ≤ los peores valores de sus variables binarias son 1 siempre y cuando sus coeficientes sean no negativos y 0
en caso contrario.

• Para una restricción ≥ los peores valores de sus variables binarias son 0 siempre y cuando sus coeficientes sean no negativos y 1
en caso contrario.

Estos son algunos ejemplos:

3 x1  2 x2  6 es redundante, ya que 3(1)  2(1)  6

3 x1  2 x2  3 es redundante, ya que 3(1)  2(0)  3
3 x1  2 x2  3 es redundante, ya que 3(0)  2(1)  3

En la mayoría de los casos en los que una restricción resulta ser redundante, ésta no lo era en el modelo original, pero si en el modelos
resultantes tras el fijado de variables. Como puede observarse, esto ocurre en la mayoría de los ejemplos de las dos transparencias
anteriores.

23
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
3. Estrechamiento de restricciones

Considérese el problema siguiente:

Maximizar z  3x1  2 x2 Maximizar z  3x1  2 x2

Problema relajado
sujeto a 2 x1  3 x2  4 sujeto a 2 x1  3 x2  4
z z
x1 , x2  0,1 x1 , x2   0,1

Dicho problema tan solo tiene tres soluciones factibles,

x2
(0,0), (0,1) y (1,0), siendo (1,0) la óptima con un valor de z=3. z = 3x1 + 2x2

Solución óptima del

Sin embargo, como se muestra en la figura, la solución óptima problema relajado
1
del problema relajado es (1,2/3) con un valor de z=4.33, que no
2x1 + 3x2 ≤ 4
está demasiado cerca de la solución óptima del problema binario.
Solución óptima del
PPLE Binario
Así, el algoritmo B&B debería ejecutar varias iteraciones hasta
identificar el óptimo del problema binario. x1
1

Nótese ahora qué ocurre cuando la restricción funcional del problema 2 x1  3x2  4 es sustituida por esta otra x1  x2  1 :

El problema binario permanece igual, con tres soluciones factibles,

(0,0), (0,1) y (1,0), siendo (1,0) la óptima con un valor de z=3. x2
z = 3x1 + 2x2
Sin embargo, la región factible del problema relajado se ha reducido x1 + x2 ≤ 1
Sustancialmente hasta el punto de que su solución coincide con la del 1
Solución óptima de
problema binario original sin necesidad de llevar a cabo ninguna iteración ambos problemas,
relajado y PPLE Binario
del algoritmo B&B.

Así, se ha conseguido reducir la región factible sin eliminar ninguna solución

1 x1
factible del problema binario original.

24
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Procedimiento para el estrechamiento de restricciones

Como se ha visto en el ejemplo anterior, el método resulta bastante sencillo para dos variables, en donde la región factible es fácilmente
visualizable de forma gráfica. Sin embargo, los mismos principios para la reducción de la región factible sin eliminar ninguna solución del
problema binario original pueden aplicarse a un problema con cualquier número de variables siguiendo el procedimiento siguiente:

Sea la restricción a1 x1  a2 x2    an xn  b :
n
1. Calcular S  
j 1 / a j  0
aj

2. Identificar los a j  0 tal que S  b  a j

(a) Si no hay ninguno, no es posible reducir la región factible.

(b) Si a j  0 continuar con el paso 3. Si a j  0 continuar con el paso 4.

3. Calcular aj  S  b y b  S  a j , resetear aj  aj y b  b y volver al paso 1.

4. Incrementar a j a a j  b  S y volver al paso 1.

Ejemplo: Apliquemos dicho procedimiento a la restricción 2 x1  3 x2  4

1. S=5
2. Tanto a1 como a2 satisfacen la restricción del punto 2. Se toma a1 arbitrariamente.
3. La nueva restricción estrechada resulta ser: x1  3 x2  3

1. S=4
2. Tan solo a2 satisface la restricción del punto 2.
3. La nueva restricción estrechada resulta ser: x1  x2  1

1. S=2
2. Ningún aj satisface la restricción del punto 2.

25
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Generación de planos de corte pata PPLE Binarios

Un plano de corte (o simplemente corte) para cualquier PPLE es una restricción funcional que reduzca la región factible de la relajación
lineal del problema original sin eliminar sin eliminar ninguna de sus soluciones factibles. Así, por ejemplo, el método de estrechamiento de
restricciones visto anteriormente puede considerarse como un método de generación de planos de corte para PPLE Binarios.

Adicionalmente, existen otra serie de técnicas para generar planos de corte que reduzcan la región factible acelerando el proceso
mediante el cual el algoritmo B&B alcanza la solución óptima. A continuación se muestra una de tales técnicas para PPLE Binarios. Para
ilustrar dicho método, considérese de nuevo el problema mostrado en el Ejemplo 3.

Maximizar z  9 x1  5 x2  6 x3  4 x4 P0

sujeto a 6 x1  3 x2  5 x3  2 x4  10 x1 = 1
 x1  3 x2  5 x3  2 x4  0 P1 P2
z Algoritmo B&B con el plano de corte
 x2  5 x3  2 x4  0
x1 , x2 , x3 , x4  0,1 * x2 = 0 x2 = 1

P3 P4

Recuérdese que la solución de la relajación lineal asociada P0 es z = 16.5 para * x3 = 0 x3 = 1

el punto (x1=5/6, x2=1, x3=0, x4=1). P5 P6
Como se verá en el procedimiento mostrado en la siguiente transparencia, la primera de las restricciones
junto con el hecho de que las variables son binarias da lugar al siguiente plano de corte x1  x2  x4  2
* *
Nótese como dicho corte elimina parte de la región factible para el problema relajado P0 (incluida su solución óptima), pero no elimina
ninguna de las soluciones enteras factibles del problema original. Así, simplemente añadiendo dicho plano de corte al modelo original, el
rendimiento del algoritmo B&B mejora en los dos aspectos siguientes:

• En primer lugar, la solución óptima del nuevo problema relajado P0 resulta ser z = 15.2 para el punto (x1=1, x2=1, x3=0.2, x4=0), por lo
que la cota superior se actualiza de  a 15.2 en lugar de a 16.5.

• En segundo lugar, se necesita una iteración menos del método B&B para alcanzar la solución óptima ya que la solución óptima del
problema relajado P5 resulta ser z = 14 para el punto (x1=1, x2=1, x3=0, x4=0), podándose por tanto dicha rama por integralidad.
A continuación la rama correspondiente al nodo P3 se poda de nuevo debido al punto 5.1 resultando la solución de P5 el óptimo.

26
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Procedimiento para la generación de un plano de corte en PPLE Binaria

1. Considérese cualquier restricción funcional del tipo ≤ con todos los coeficientes no negativos.

2. Encontrar el conjunto de variables (denominado envoltura mínima de la restricción) tal que:

(a) La restricción no se satisface si cada variable de la envoltura mínima vale 1 y el resto 0.

(b) Pero la restricción pasa a ser satisfecha si el valor de cualquier variable de la envoltura mínima pasa de valer 1 a valer 0.

3. Denotando N como el número de variables de la envoltura mínima, el plano de corte resultante tiene la forma 
xi envoltura
xi  N  1
mínima

Ejemplo: Apliquemos dicho procedimiento a la restricción 6 x1  3 x2  5 x3  2 x4  10

1. La restricción satisface el criterio especificado en el paso 1.

2. La envoltura mínima está formada por las variables (x1, x2, x4), ya que:

(a) (1, 1, 0, 1) no satisface la restricción.

(b) Pero la restricción pasa a ser satisfecha si el valor de cualquiera de las variables (x1, x2, x4) pasa de valer 1 a valer 0.

3. Puesto que N=3, el plano de corte resultante es x1  x2  x4  2

Nótese que dicha restricción tiene una segunda envoltura mínima:

2. La envoltura mínima está formada por las variables (x1, x3), ya que:

(a) (1, 0, 1, 0) no satisface la restricción.

(b) Pero la restricción pasa a ser satisfecha si el valor de cualquiera de las variables (x1, x3) pasa de valer 1 a valer 0.

3. Puesto que N=2, el plano de corte resultante es x1  x3  1

27
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Método de los cortes de Gomoroy

Un método alternativo de solución de PPLE es el procedimiento de los cortes de Gomory. En esta técnica, se resuelve el problema
original relajado en el que se incluyen restricciones adicionales, que reducen la región factible sin excluir soluciones que cumplen las
condiciones de optimalidad. En cada iteración se añade una restricción que se denomina corte de Gomory. Este procedimiento genera
progresivamente una envoltura convexa de la región factible, lo que origina soluciones que cumplen las condiciones de integralidad.

Generación de un corte

La región factible del problema original es Ax = b, que empleando la partición estándar del simplex se escribe como:

x 
B N  B b  Bx B  Nx N  b  x B  B 1 Nx N  B 1b
 xN 

Denotando por U  B 1 N y b  B 1 b  x B  Ux N  b

Sea xB una variable básica que ha de ser entera pero no lo es.

La fila correspondiente a esta variable en la ecuación anterior es: xBi   uij xN j  bi

j

Puesto que la solución obtenida es básica y factible, la variables xNj, que son no básicas, son cero; por tanto, b  x B , y puesto que xBi
es no entera, b ha de ser no entera.
i

Por otra parte, cada elemento uij se puede expresar como suma de una parte entera (positiva, negativa o nula), eij, y una fracción no
negativa menor que 1, fij:

uij  eij  f ij ; j

De forma análoga, b se puede descomponer como b  e  f donde ei es un entero (positivo o negativo) y f i una fracción no
i i i i
negativa menor que 1. Obsérvese que algunos f ij pueden ser cero, pero f ha de ser positivo.
i

28
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Sustituyendo uij  eij  f ij ; j y bi  ei  f i en xBi   uij xN j  bi , se obtiene:
j

xBi    eij  f ij  xN j  ei  f i  xBi   eij xN j  ei  f i   f ij xN j

j j j

En la ecuación anterior, el término de la izquierda ha de ser entero puesto que todas sus variables son enteras. Por tanto, el término de la
derecha también será entero.

Por otra parte, tanto fij como xNj son no negativos para todo j, por tanto el término fj
ij xN j es no negativo.

Finalmente, el término de la derecha de la ecuación precedente, f i   f ij xN j es a la vez:

j

• entero, y

• menor que una fracción positiva, fi , menor que 1

y puesto que los enteros que satisfacen esa condición son 0,−1,−2, . . ., entonces f i   f ij xN j es un entero no positivo.
j

Por tanto f i   f ij xN j  0 ó f ij xN j  f i  0
j j

Esta última desigualdad se denomina corte de Gomory asociado a la variable básica xBi que ha de ser entera pero no lo es.

A continuación se resumen las ecuaciones utilizadas en el método de los cortes de Gomoroy:

1. U  B 1 N y b  B 1 b  x B  Ux N  b  xBi   uij xN j  bi
j

2. uij  eij  f ij ; j y bi  ei  f i

3. f i   f ij xN j  0
j

29
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Algoritmo de los cortes de Gomoroy para un PPLE

A continuación se enumeran los pasos del algoritmo de los cortes de Gomoroy para un PPLE:

Paso 1: Iniciación
1.1 Se resuelve el problema original sin restricciones de integralidad.
1.1.a Si la solución no está acotada, el problema original o no está acotado y se para.
1.2.b Si el problema es infactible, el problema original también lo es y se para.
1.2.c En cualquier otro caso, se continua con el paso siguiente.

Paso 2: Control de optimalidad

2.1 Si la solución obtenida cumple las condiciones de integralidad, se para dado que esta solución es óptima.

2.2 En cualquier otro caso, se continua con el paso siguiente.

Paso 3: Generación de un corte

3.1 Se emplea una variable básica que ha de ser entera pero no lo es para generar un corte de Gomory.

Paso 4: Resolución
4.1 Se añade el corte de Gomory obtenido al problema previamente resuelto, se resuelve el problema resultante y se continúa con el
paso 2.

Deben además tenerse en cuenta los aspectos siguientes:

• Obsérvese que el número de restricciones crece con el número de iteraciones.

• Puesto que en cada iteración se añade una nueva restricción, debe emplearse para la resolución del problema el método simplex
dual. Esto es así puesto que al añadir una nueva restricción, el problema primal correspondiente se hace infactible pero su dual
permanece factible, aunque no óptimo.

• Por tanto, para resolver el nuevo problema puede partirse de la solución dual del problema previo (sin restricción adicional), lo que
supone una ventaja computacional importante.

30
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Ejemplo 4: Algoritmo de los cortes de Gomoroy

Sea el siguiente PPLE Pura:

Maximizar z  120 x1  80 x2
sujeto a 122 x1  0 x2  6
7 x1  8 x2  28
z
x1 , x2  0
x1 , x2  

Se trata de obtener su solución mediante el método de los cortes de Gomoroy.

Solución: Algoritmo de los cortes de Gomoroy

Paso 1: Iniciación

1.1 El problema relajado, es el siguiente: x2

Maximizar z  120 x1  80 x2 2x1 + x2 ≤ 6 7x1 + 8x2 ≤ 28

sujeto a 122 x1  0 x2  x3  x4  6
3
z  127 x1  8 x2  x3  x4  28
x1 , x2 , x3 , x4  0
2

Solución: z = 391.11 para el punto (x1=5, x2=4.5) 1

x2 ≥ 0
 x*   20 
b  x B   1*    149  x1 ≥ 0
1 2 3 x1
 x2   9 

1.2c Se continua con el paso siguiente.

31
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Solución: Algoritmo de los cortes de Gomoroy (continuación 1)

Paso 2: Control de optimalidad

2.2 Como la solución obtenida no cumple las condiciones de integralidad, se continua con el paso siguiente.

Paso 3: Generación de un corte

3.1 Si se emplea la variable x2 para generar un corte de Gomory, se obtiene:

1
 2 1  1 0   89  91  7 2 14
U B N 1
   7 2
xBi   uij xN j  bi x2  x3  x4 
 7 8   0 1   9 9 j 9 9 9
x2
Por tanto, se obtiene:
7 2 2 2x1 + x2 ≤ 6 7x1 + 8x2 ≤ 28 Primer corte
u21  e21  f 21    1   f 21 
9 9 9 x1 + x2 ≤ 7/2
3
2 2 2
u22  e22  f 22   0  f 22 
9 9 9
14 5 5 2
b2  e2  f 2   1  f2 
9 9 9
1
5 2 2   x3 
Y el corte resulta ser: fi   f ij xN j 0      0
j 9 9 9   x4  x2 ≥ 0
1 2 3 x1
 x3  x4  5
2
x1 ≥ 0

Nótese que este corte puede expresarse en función de las variables originales x1 y x2, de la forma siguiente. Empleando las
restricciones de igualdad del problema relajado en forma estándar, x3 y x4 pueden expresarse en función de x1 y x2 :

x3  6  2 x1  x2
x4  28  7 x1  8 x2
Así, el corte en función de las variables x1 y x2 resulta ser x1  x2  72 , que como puede verse en la figura da lugar a una
reducción efectiva de la región factible y, sin embargo, no se excluye ninguna solución entera.

32
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Solución: Algoritmo de los cortes de Gomoroy (continuación 2)

Paso 4: Resolución
4.1 Se resuelve el nuevo problema con el primer corte añadido como restricción adicional. Obsérvese que el corte de Gomory se
escribe incluyendo una variable artificial x5:
x2
Maximizar z  120 x1  80 x2
sujeto a 122 x1  0 x2  x3  x4  x5  6 2x1 + x2 ≤ 6 7x1 + 8x2 ≤ 28 Primer corte
127 x1  8 x2  x3  x4  x5  28 x1 + x2 ≤ 7/2
z 3
x3  x4  x5  5
2

x1 , x2 , x3 , x4 , x5  0 2

 x1*   52 
    1
Solución: z = 380 para el punto (x1=5/2, x2=1) b  x B   x2*    1 
 x*   5 
 4 2 x2 ≥ 0
1 2 3 x1
Paso 3: Generación de un corte x1 ≥ 0
3.1 Si se emplea la variable x1 para generar un corte de Gomory, se obtiene:

1
 2 1 0   1 0   1  19 
     2
1 5
U  B 1 N   7 8 1    0 0    1 9
xBi   uij xN j  bi x1  x3  x5 
 0 0 1   1 1  1 1 j 9 2
     

Por tanto, se obtiene: Y el corte resulta ser:

u11  e11  f11  1  1 0  f11  0 1  8   x3 

fi   fij xN j  0  0    0
1 8 8 j 2  9   x5 
u12  e12  f12    1   f12 
9 9 9 9 55
5 1 1  x5  ó x1  x2 
b1  e1  f1   2  f1  16 16
2 2 2

33
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Solución: Algoritmo de los cortes de Gomoroy (continuación 3)

Paso 4: Resolución
4.1 Se resuelve el nuevo problema con el primer corte añadido como restricción adicional. Obsérvese que el corte de Gomory se
escribe incluyendo una variable artificial x6:
x2
Maximizar z  120 x1  80 x2
sujeto a 122 x1  0 x2  x3  x4  x5  x6  6 2x1 + x2 ≤ 6 7x1 + 8x2 ≤ 28 Primer corte
127 x1  8 x2  x3  x4  x5  x6  28 x1 + x2 ≤ 7/2
3
z x3  x4  x5  x6  5
2
Segundo corte
x5  x6  16
9
2 x1 + x2 ≤ 55/16
x1 , x2 , x3 , x4 , x5 , x6  0
 x1*   16
41

 *  7  1
b  x B   2*    498 
Solución: z = 377.5 para el punto (x1=41/16, x2=7/8)
x
 x   16 
 4*   9  x2 ≥ 0
Paso 3: Generación de un corte  x5   16  1 2 3 x1
x1 ≥ 0
3.1 Si se emplea la variable x2 para generar un corte de Gomory, se obtiene:
1
 2 1 0 0   1 0   1  19 
     2
7 8 1 0   0 0   1 2 7
1
UB N     9 xBi   uij xN j  bi x2  x3  x6 
 0 0 1 1   1 0   1 1  j 9 8
     
 0 0 0 1  0 1  0 1

Por tanto, se obtiene:

u21  e21  f 21  1  1  0  f 21  0 7  2   x3 
2 2 2 fi   fij xN j  0  0    0
u22  e22  f 22   0  f 22  j 8  9   x6 
9 9 9
63
b2  e2  f 2 
7
 0
5
 f2 
7  x6  ó x1  x2  3
8 8 8 16

34
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Solución: Algoritmo de los cortes de Gomoroy (continuación 4)

Paso 4: Resolución
4.1 Se resuelve el nuevo problema con el primer corte añadido como restricción adicional. Obsérvese que el corte de Gomory se
escribe incluyendo una variable artificial x7:
x2
Maximizar z  120 x1  80 x2
sujeto a 122 x1  0 x2  x3  x4  x5  x6  x7  6 2x1 + x2 ≤ 6 7x1 + 8x2 ≤ 28 Primer corte
127 x1  8 x2  x3  x4  x5  x6  x7  28 x1 + x2 ≤ 7/2
3
x3  x4  x5  x6  x7  5
z 2
Segundo corte
x5  x6  x7  169 x1 + x2 ≤ 55/16
2
x6  x7  63
16

x1 , x2 , x3 , x4 , x5 , x6 , x7  0 Tercer corte
1 x1 + x2 ≤ 3
(solución óptima)
Solución: z = 360 para el punto (x1=3, x2=0) x2 ≥ 0
1 2 3 x1
x1 ≥ 0

Paso 2: Control de optimalidad

2.1 Como la solución obtenida cumple las condiciones de integralidad, se para dado que esta solución es óptima.

//Variables de decisión
Solución: z = 360 para el punto (x1=3, x2=0) dvar int+ x1;
dvar int+ x2;

//Función objetivo
maximize 120*x1 + 80*x2;

//Restricciones
subject to {
solution (optimal) with objective 360: 2*x1 + x2 <= 6;
x1 = 3; 7*x1 + 8*x2 <= 28;
x2 = 0; }

35
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
Ejercicio 1:

Una empresa manufacturera transforma materia prima en dos productos distintos. Esta empresa dispone de 6 unidades de materia prima
y 28 horas de tiempo productivo. La manufactura de una unidad del producto I requiere 2 unidades de material y 7 horas de tiempo,
mientras que la producción del producto II requiere 1 unidad de material y 8 horas de tiempo. Los precios de venta de los producto I y II
son 120 y 80 euros respectivamente. Determínese el número de productos de cada tipo que ha de producir la empresa para maximizar su
beneficio.

Resuélvase el problema empleando el algoritmo de B&B.

Ejercicio 2:

Un operario especializado ha de reparar una instalación de alta montaña. Es conveniente que lleve consigo 5 equipos diferentes de
reparación. Sin embargo, el peso máximo a transportar está limitado a 60 unidades. El peso de cada equipo y un parámetro que
cuantifica su utilidad esperada aparecen en la siguiente tabla.

Equipo 1 2 3 4 5

Peso (unidades) 52 23 35 15 7

Utilidad (%) 100 60 70 15 15

¿Qué equipos ha de llevarse consigo el operario? . Para responder a dicha pregunta:

a) Resuélvase el problema empleando el algoritmo de B&B.

b) Comprobar si puede utilizarse alguna de las técnicas de preprocesamiento para PPLE Binarios estudiados.

a) Incluir todos los posibles planos de corte para PPLE Binarios.

b) Resuélvase el nuevo mediante B&B el problema obtenido tras dicho preprocesamiento e introducción de los planos de corte.

36
A. HERRÁN, INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA, MÁSTER UNIVERSITARIO EN INGENIERÍA DE SISTEMAS Y DE CONTROL
 Rafael del Vado Vírseda
[email protected]

APÉNDICE DEL TEMA 6

EJEMPLOS

1. ALGORITMO DE RAMIFICACIÓN Y ACOTACIÓN

2. ALGORITMO DE CORTE: PROGRAMACIÓN TOTALMENTE ENTERA
3. ALGORITMO DE CORTE: PROGRAMACIÓN ENTERA MIXTA
4. ALGORITMO DE BALAS: PROGRAMACIÓN 0-1
1. ALGORITMO DE RAMIFICACIÓN Y ACOTACIÓN
1. ALGORITMO DE RAMIFICACIÓN Y ACOTACIÓN
1. ALGORITMO DE RAMIFICACIÓN Y ACOTACIÓN
EJEMPLO 1
EJEMPLO 1
EJEMPLO 2
EJEMPLO 2
EJEMPLO 2
EJEMPLO 2
EJEMPLO 2
EJEMPLO 2
EJEMPLO 2
2. ALGORITMO DE CORTE: PROGRAMACIÓN TOTALMENTE ENTERA
2. ALGORITMO DE CORTE: PROGRAMACIÓN TOTALMENTE ENTERA
2. ALGORITMO DE CORTE: PROGRAMACIÓN TOTALMENTE ENTERA
3. ALGORITMO DE CORTE: PROGRAMACIÓN ENTERA MIXTA
3. ALGORITMO DE CORTE: PROGRAMACIÓN ENTERA MIXTA
3. ALGORITMO DE CORTE: PROGRAMACIÓN ENTERA MIXTA
4. ALGORITMO DE BALAS: PROGRAMACIÓN 0 - 1
4. ALGORITMO DE BALAS: PROGRAMACIÓN 0 - 1
EJEMPLO
EJEMPLO
EJEMPLO
EJEMPLO
EJEMPLO
EJEMPLO