ALGORITMO DE RAMIFICACIÓN Y ACOTAMIENTO
PARA PROGRAMACIÓN ENTERA MIXTA
A continuación se estudiará el
problema general de programación
entera
mixta, PEM,
donde algunas variables (por ejemplo,
I de ellas) están
restringidas a valores enteros (pero no necesariamente sólo
0 y 1), y el resto son variables
continuas comunes. Por conveniencia
en la notación, se ordenará estas
variables de manera que las primeras I de ellas sean variables con restricción de enteros. La forma general del problema que se
va a estudiar es:
Minimizar Z =
n
Σ
j − 1
c
j x j ,
.
Sujeta ha
n
Σ
j − 1
a ij
x j
≤ b i ,
Para i = 1, 2… m,
A
x j ≥ 0,
para j = 1,2 ,
… ,
n ,
x j es entero ,
para j = 1,2 ,
… ,
I ; I ≤ n
(Cuando I = n, este problema se convierte en uno de PE pura.)
Se describirá un algoritmo básico de ramificación y acotamiento para resolver este problema que, un
poco más elaborado, ha proporcionado
el enfoque estándar a la PEM. La estructura de este
algoritmo fue desarrollada por R.
J. Dakin, con base en un algoritmo anterior que se debe a A.
H. Land y A. G. Doig.
Estructuralmente, este algoritmo es
bastante parecido
al algoritmo
de PEB que se presentó en la sección anterior.
De nuevo la solución de un
relajamiento de PL proporciona la base tanto
para el paso de acotamiento como
para el de sondeo. De hecho, sólo se necesitan cuatro cambios al algoritmo de PEB para manejar la generalización de variables
enteras binarias generales y de PE pura
a PE mixta.
+
Un cambio involucra la elección de
la variable de ramificación. Antes se elegía de manera automática la siguiente variable en el orden natural (x1, x2,…, xn). Ahora, las únicas variables que se toman
en cuenta son las variables con restricción de enteras que tienen
un valor no entero en la solución óptima
del relajamiento
de PL para el subproblema actual.
La regla para elegir entre estas variables
será seleccionar la primera en
el orden natural.
(Los paquetes de producción casi
siempre utilizan una regla más complicada.)
El segundo cambio se refiere a los
valores asignados a la variable de ramificación
para crear los nuevos subproblemas. Antes, la variable binaria se fijaba en 0 y 1, respectivamente, para los
dos nuevos subproblemas. Ahora, la
variable general con restricción de entera puede tener un número grande de valores enteros posibles, y sería ineficiente crear y analizar muchos
subproblemas mediante la determinación
de cada valor entero de la variable.
Entonces, se crean sólo dos nuevos
subproblemas (como antes) al especificar
dos intervalos de
valores de la variable.
Para
aclarar cómo se
procede, sea xj la variable de ramificación actual y xj* su
valor (No entero) en la solución óptima del relajamiento de PL del subproblema
actual. Se usa corchetes para denotar
|
j
|
= entro más grande
≤ x j ,
por lo cual, para los intervalos de valores de los dos nuevos subproblemas se tiene
x j ≤ [x j
y x j
≥ x
j
+ 1,
Respectivamente. Cada desigualdad se convierte en una restricción
adicional del
x j ≤ 3 y x j ≥ 4
Son las restricciones adicionales
respectivas de los dos nuevos subproblemas.
Grafico 1
Ilustración del fenómeno de una variable de ramificación
recurrente, donde x1 se
convierte en una variable de
ramificación tres veces por tener un
valor no entero en la solución óptima del relajamiento
de PL en tres nodos.
Cuando se combina los dos cambios
al algoritmo de PEB que se acaban de describir, puede ocurrir un interesante fenómeno de una variable
de ramificación
recurrente. Para ilustrarla, como
se muestra en la
figura, sea j =
1 en el ejemplo anterior.
donde xj= 32 y considere el nuevo
subproblema con x1 ≤ 3. Cuando se resuelve el
= 14.
Entonces, x1 recurre
como variable de ramificación y los
dos nuevos subproblemas creados tienen la restricción
adicional x1 ≤ 1 y x1 ≥ 2,
respectivamente (así como
la
restricción adicional anterior, x1 ≤ 3). Más adelante, cuando se
resuelva el relajamiento de PL de un
descendiente de, por ejemplo, x1 ≤ 1,
se supondrá que
3
El tercer cambio se hace en el paso de acotamiento. Antes, con un problema de PE pura
y coeficientes enteros en la función objetivo, el valor de Z de
la solución
óptima
Del relajamiento de PL del
subproblema se redondeaba hacia abajo para obtener la cota, puesto que
cualquier solución factible del
problema debía tener una Z entera. Ahora, con algunas variables sin la restricción de integridad, la cota es el valor de Z sin redondear.
El cuarto (y último) cambio al algoritmo
de PEB para obtener el algoritmo
de PEM se refiere a la prueba de
sondeo 3. Antes, con un problema de
PE pura, la prueba consistía en que la solución al relajamiento de PL del subproblema fuera entera,
puesto que esto aseguraba una solución
factible y, por lo tanto, óptima del subproblema.
Ahora, con un problema de PE mixta,
la prueba requiere que sólo las variables restringidas a enteras tengan
valores enteros en la solución
óptima del relajamiento de PL del
subproblema, puesto que esto es suficiente
para asegurar que la solución es factible y, por lo tanto, óptima para el subproblema.
La incorporación de estos cuatro
cambios
al resumen que se presentó en la sección
anterior sobre el algoritmo de programación entera binaria conduce al siguiente
resumen del nuevo algoritmo
de programación entera mixta.
Resumen
del
algoritmo de ramificación y acotamiento de PEM
Paso inicial: se establece Z* = −∞. Se
aplica el paso de acotamiento, el
paso de sondeo y la prueba de optimalidad
que se describe después del problema
completo. Si no queda sondeado, se clasifica este problema como el único
subproblema restante para
realizar la primera iteración completa
No hay comentarios.:
Publicar un comentario