Universidad Tecnológica de Pereira – Colombia
Posgrado en Ingeniería – Maestría/Doctorado
Programación Lineal Entera
Antonio H. Escobar Z.
2013
Método de Balas
Enumeración implícita 0-1
Método Enumeración implícita 0-1 de Balas
• Metodología de solución exacta usada para resolver problemas
de PLE donde las variables asumen valores binarios: x  {0,1}.
• Usa conceptos de Branch and Bound pero no requiere resolver
PL´s, únicamente realiza operaciones de adición y
comparación en cada nodo.
• No modifica la matriz A y ocupa poco espacio de memoria.
• Su filosofía es la de descartar subespacios sin evaluarlos por
no ser promisorios por factibilidad o por optimalidad →
evaluación implícita.
Método Enumeración implícita 0-1 de Balas
• La solución inicial asume que todas las variables del problema
están en cero, para que sea óptima (cj ≥ 0).
• Una vez en el formato anterior, se realizan pruebas de sondaje
por factibilidad o por optimalidad para eliminar ramas del
árbol que no son promisorias. También se realizan pruebas de
fijación de variables en el valor cero o uno.
• Almacena la mejor solución factible (incumbente) después de
evaluar las 2n combinaciones posibles (n = número de
variables), implícitamente. La mejor solución encontrada es la
óptima.
Concepto de enumeración implícita
La solución óptima de un PLE 0-1 puede encontrarse de dos
formas:
1. Evaluando explícitamente todas las posibilidades: 2n
2. Evaluando un número reducido de posibilidades y
descartando las demás SIN EVALUARLAS. Filosofía de Branch
and Bound.
Concepto de enumeración implícita
La enumeración implícita debe cumplir dos requisitos básicos::
1. El esquema de enumeración debe asegurar que las 2n
soluciones
posibles
sean
enumeradas
implícita
o
explícitamente y de una manera no redundante.
2. Las pruebas de sondaje deben excluir el mayor número de
soluciones no interesantes o de baja calidad.
Método Enumeración implícita 0-1 de Balas
La solución óptima puede ser obtenida a través de:
1. Pruebas de sondaje → Excluyen el máximo número de
complementos.
2. Movimientos hacia adelante (Forward) → Adición de nuevas
variables a la solución parcial.
3. Movimientos hacia atrás (Backward)
realizados para eliminar complementos.
→
Movimientos
Porque aplicar el algoritmo de enumeración implícita 0-1 de Balas?
• Porque es un método exacto → garantiza el óptimo global.
• Porque es aplicable a cualquier problema entero con variables
canalizadas, ya que cualquier variable entera acotada puede
expresarse a través de variables binarias.
• Porque produce una solución SIN errores de redondeo (ya que
únicamente aplica sumas y comparaciones).
• Porque ocupa poco espacio de memoria.
• Porque no existe un método de PLE que sea bueno para
resolver todo tipo de problemas.
Porque aplicar el algoritmo de enumeración implícita 0-1 de Balas?
• Porque es un método que se complementa bien con otros
métodos que resuelven problemas de PLE tales como Branch
and Bound.
• Porque se adapta bien a problemas con muchas variables
binarias donde un número reducido de variables candidatas
asumen el valor 1.
•
Porque presenta rápida convergencia en problemas donde se
conoce una solución inicial factible de buena calidad.
•
Porque la eficacia de las pruebas de sondaje aumenta con el
número de restricciones.
PLE
PLE
PLE
PLE
0-1
En formato matricial:
Si:
Si:
N = { 1, 2, 3, 4, 5, 6, 7 } ;
J = { 6, -2, -4, 5 } → ( N – J ) = {1, 3, 7 }
J = { 6, -2, -4, 5 } → Un complemento de J es : {6, -2, -4, 5, 1, -3, 7 }
Ejercicio base: Resolver usando enumeración implícita 0-1 de Balas
• Los coeficientes de la función objetivo deben ser positivos y las
restricciones deben ser del tipo menor o igual (≤)
Hacemos cambio de variables:
se elimina temporalmente,
se agrega al final
coeficientes positivos
-8
Modificamos las desigualdades:
Forma estándar
Adicionamos las variables de holgura:
Para una cierta combinación de valores de las variables, las restricciones
son factibles si las variables de holgura son positivas o cero.
Si las variables xi asumen valor cero, el sistema inicial es óptimo e
infactible:
S1 = -2;
S2 = 0;
S3 = -1
El algoritmo aditivo de Balas resulta después de realizar algunas modificaciones
sugeridas por Glover en su esquema de enumeración.
A través de un ejercicio base se muestran las condiciones de inicio, las pruebas
de sondaje y las pruebas de adición y fijación de variables.
Condición inicial:
• Se puede iniciar con una solución factible encontrada, por ejemplo, a través
de una heurística. Esta solución será la incumbente inicial.
• Se puede iniciar con J0 = { ø } , solución parcial inicial vacía, y definir la
incumbente zmin = ∞ y la solución actual z0 = 0.
Para el ejercicio base:
N = {1, 2, 3, 4, 5}
J0 = { ø } → solución parcial inicial vacía.
zmin = ∞ → limitante superior (mejor solución binaria conocida).
z0 = 0
→ solución actual.
Prueba 1: (Balas).
Prueba de sondaje por infactibilidad.
Identifica las variables libres del problema que al ser promovidas al valor 1 empeoran la
infactibilidad de las restricciones que actualmente son infactibles. Los índices de estas
variables son almacenados en el vector At .
En el ejercicio base:
S0 = { S10 , S20 , S30 } = { -2, 0, -1 }
Las restricciones 1 y 3 son infactibles, por lo tanto esta prueba sólo se le realiza a estas
restricciones.
→ Prueba de sondaje por infactibilidad.
índices de variables
que tienen
coeficientes positivos en todas las
restricciones infactibles.
En el ejercicio base las restricciones 1 y 3 son infactibles:
S10 = -2;
S20 = 0;
S30 = -1
i=1
i=2
i=3
→
A0 = { 2, 5 }
En el ejercicio base:
→
N = { 1, 2, 3, 4, 5 } ; J0 = { ø } ;
A0 = { 2, 5 }
En consecuencia, N01 = ( {1, 2, 3, 4, 5 } – { ø } ) - { 2, 5 }
N01 = {1, 3, 4 }
Variables que al ser promovidas a 1
en la solución actual no empeoran
la infactibilidad.
A pesar de que pueden mejorar la factibilidad, empeoran la optimalidad.
También se define:
En el ejercicio base zmin = ∞ (no se tiene aún una incumbente ).
Además:
Entonces: si
N01 = {1, 3, 4 } ;
x1 = 1,
x3 = 1,
x4 = 1,
z0 = 0 + C 1 = 0 + 5
≥ ∞
z0 = 0 + C3 = 0 + 10 ≥ ∞
z0 = 0 + C4 = 0 + 3
≥ ∞
Ninguna variable en N01 empeora la optimalidad.
En consecuencia,
N01 = {1, 3, 4 } ; B0 = { ø } ;
N02 = N01 - B0 = {1, 3, 4 } – { ø }
N02 = {1, 3, 4 }
Si
N02
es vacio, la solución parcial es sondada y se realiza un movimiento hacia atrás.
selecciona los coeficientes negativos.
Observación importante:
Ct no contiene índices de variables, como las pruebas anteriores, contiene índices de
restricciones.
En el ejercicio base, las restricciones 1 y 3 son infactibles y
N02 = {1, 3, 4 }
Para i = 1 (restricción 1) :
Las variables de N02
mejorada:
se promueven a 1 y se observa si la infactibilidad no puede ser
1
0
1
1
Si puede ser mejorada, entonces no se agrega a C0
0
En el ejercicio base, las restricciones 1 y 3 son infactibles y
N02 = {1, 3, 4 }
Para i = 3 (restricción 3) :
Las variables de N02
mejorada:
se promueven a 1 y se observa si la infactibilidad no puede ser
0
1
0
Si puede ser mejorada, entonces no se agrega a C0
0
C0 = { ø }
Si C0 resulta diferente de vacío, existen restricciones que no pueden ser factibles, y la
solución actual debe ser sondada. Se realiza un movimiento hacia atrás.
•
Realmente se prueba el caso más favorable en la relación beneficio-costo (factibilidad vs
optimalidad).
•
Si no cumple el caso más favorable, entonces ninguno cumple y la solución actual puede
ser sondada.
Ejemplo:
parcial:
Suponer que nos encontramos en un nodo que presenta la siguiente solución
Jt = { 1, 2, -4 }
y además que se tienen las siguientes condiciones:
1. Función objetivo:
z = 10 x1 + 8 x2 + 12 x3 + 6 x4 + 20 x5
2. Nt2 = { 3, 5 }
3. Única restricción:
4.
4 x1 - 2 x2 - 6 x3 + 3 x4 - 4 x5 + S1t = - 6
Se conoce una incumbente (solución entera factible) zmin = 40
Según la solución parcial
x1 = 1 ; x2 = 1 ; x4 = 0 ; y
x3 = ? ; x5 = ?
En consecuencia, zt = 18 (solución actual):
1
1
?
0
?
z = 10 x1 + 8 x2 + 12 x3 + 6 x4 + 20 x5
Según la condición : Nt2
numérico definido.
=
= 18
{ 3, 5 } existen dos variables que aún no tienen un valor
En la restricción 4 x1 - 2 x2 - 6 x3 + 3 x4 - 4 x5 + S1t = - 6
resuelve la infactibilidad.
promover x3
Pero como afecta la optimalidad?
zt = 18
y con las nuevas variables: zt = 18 + 12 + 20 = 50
La nueva función objetivo supera la incumbente zmin :
50 > 40
y
x5
a 1
Según la solución parcial
x1 = 1 ; x2 = 1 ; x4 = 0 ; y
x3 = ? ; x5 = ?
Infactibilidad actual:
1
1
?
0
?
4 x1 - 2 x2 - 6 x3 + 3 x4 - 4 x5 + S1t = - 6
S1t = - 8
Puede verificarse que esta opción es inadecuada promoviendo sólo UNA de las
variables que se encuentran en Nt2 = { 3, 5 } con la prueba 3´ de GloverZionts:
1. Función objetivo:
2. Única restricción:
z = 10 x1 + 8 x2 + 12 x3 + 6 x4 + 20 x5
4 x1 - 2 x2 - 6 x3 + 3 x4 - 4 x5 + S1t = - 6
Para x3 :
S1t * c3 / a -13 = (- 8 * 12) / - 6 = 16
Para x5 :
S1t * c5 / a -15 = (- 8 * 20) / - 4 = 40
Se toma el menor:
r1 = 16
Para x3 :
S1t * c3 / a -13 = (- 8 * 12) / - 6 = 16
Para x5 :
S1t * c5 / a -15 = (- 8 * 20) / - 4 = 40
Se toma el menor:
r1 = 16
En el ejemplo, eliminar la infactibilidad por completo (si fuera posible)
usando la relación beneficio-costo
(infactibilidad-optimalidad) de la
variable x3 empeoraría la función objetivo en 16.
zt = 18 + 16 = 34
En este caso no queda sondado porque no empeora la incumbente:
34 < 40
En el ejercicio base, zmin = ∞ por lo tanto la prueba 3´ de Glover-Zionts no
sonda porque cualquier variable en N02 = { 1, 3, 4 } al ser promovida a 1
puede reducir la infactibilidad sin afectar la optimalidad.
En resumen:
x2 y x5 fueron descartadas por no ser promisorias.
x1 ; x3 y x4 no han sido descartadas por factibilidad ni por optimalidad.
Ya que no se puede sondar el nodo, las siguientes pruebas intentan adicionar
variables a la solución parcial que es:
J0 = {
ø}
• Intenta fijar los valores de las variables libres en 0 ó 1
garantizar factibilidad.
con el fin de
• Sólo considera variables libres.
• Identifica variables indispensables.
• No garantiza la promoción de variables a la solución parcial (puede fracasar).
Para el ejercicio base:
N = {1, 2, 3, 4, 5}
J0 = { ø } → solución parcial inicial vacía.
zmin = ∞ → limitante superior (mejor solución binaria conocida).
z0 = 0
→ solución actual.
N02 = { 1, 3, 4 } → variables libres
S1 = -2; S2 = 0; S3 = -1
N02 = { 1, 3, 4 } → variables libres
libres
i = 1 (infactible)
S10 = -2
libres
i = 1 (infactible)
Para i = 1:
S10 - ∑ [min (0, a1j ) ] - | a1j | < 0 ?
-2 - (-1 - 5 -1 ) - | a1j | < 0 ?
5
- | a1j | < 0 ?
para j = 1,3,5
para j = 1,3,5
Para i = 1:
S10 - ∑ [min (0, a1j ) ] - | a1j | < 0 ?
5
- | a1j | < 0 ?
j =1,3,4
para j = 1,3,4
j =1 → 5 - | a11 | = 5 - | -1 | = 4
no es menor que cero
j =3 → 5 - | a13 | = 5 - | -5 | = 0
no es menor que cero
j =4 → 5 - | a14 | = 5 - | -1 | = 4
no es menor que cero
Para i = 3:
S30 - ∑ [min (0, a3j ) ] - | a3j | < 0 ?
-1 - (-2 ) - | a3j | < 0 ?
1
- | a3j | < 0 ?
j =1,3,4
para j = 1,3,4
para j = 1,3,4
j =1 → 1 - | a31 | = 1 - | 0 | = 1
no es menor que cero
j =3 → 1 - | a33 | = 1 - | -2 | = -1
es menor que cero
j =4 → 1 - | a34 | = 1 - | 1 | = 0
no es menor que cero
Para i = 3:
j = 3 → 1 - | a33 | = 1 - | -2 | = -1
es menor que cero
•La prueba se cumple en la restricción 3 y para la variable x3
•Se observa el signo de a33 :
a33 < 0
x3 se fija en 1
• x3 se coloca en 1 y se elimina la opción: x3 = 0 porque no es
promisoria.
• La solución parcial: J0 = {
ø}
es ampliada. Por lo tanto:
J1 = { 3 }
• El conjunto de variables libres N02 = { 1, 3, 4 } se actualiza:
N12 = { 1, 4 }
• Se actualiza la solución actual z0 = 0 a:
z1 = 10
(
)
• No se actualiza la incumbente porque no se ha chequeado
factibilidad. Por lo tanto zmin = ∞
• Permite fijar una variable libre en el nivel 0.
• Realiza una prueba que combina factibilidad y optimalidad.
• Se realiza si la prueba de ampliación de Geoffrion fracasa (no
logra agregar variables a la solución parcial.
• Separa variables libres en dos grupos: promisorias por factibilidad
(que solas resuelvan la infactibilidad actual) y no promisorias por
factibilidad (sin capacidad para resolver solas la infactibilidad).
Las no promisorias las coloca en el subconjunto p.
• Entre las promisorias (N02 - p ) selecciona la que menos impacta
la función objetivo. Su costo se almacena en ch.
• Con cada una de las no promisorias (p) evalúa el empeoramiento
en la función objetivo a partir de ch.
Fija en cero las variables no promisorias cuyo costo, más el de la
promisoria menos costosa más el de la función objetivo actual
supera la incumbente:
Ch es el costo de la variable que menos afecta la optimalidad y que mejora en
mayor medida la factibilidad (sola elimina la infactibilidad).
En el ejercicio base, asumir que la prueba de ampliación de Geoffrion fracasa y
por lo tanto, N02 = { 1, 3, 4 }.
La prueba de ampliación de Glover-Zionts intenta adicionar variables a la
solución parcial que es:
J0 = {
Restricciones violadas: S10 = -2;
ø}
S30 = -1 (restricciones 1 y 3).
Para i=1:
S10 = -2
p:
índice de las variables en N02 = {1,3,4}
infactibilidad al ser promovidas a 1:
que solas no resuelven la
p  N02
tal que a1p > S10
a11 = -1
>
S10 = - 2
a14 = -1
>
S10 = - 2
p = {1,4}
Para i=1:
p = {1,4}
Ahora calculamos:
N02 = {1,3,4}
N02 - p = {1,3,4} - {1,4} = {3}
ch = min { cj / j  {3}; a1j < 0 }
ch = c3 = 10
ya que el único valor posible para j es 3.
ch = c3 = 10
p = {1,4}
Para p =1: x1 ; c1 = 5
ch + cp ≥ zmin - z0
?
ch + c 1 ≥ ∞ - 0 ?
10 + 5 ≥ ∞
No cumple la prueba, x1 no es cero
ch = c3 = 10
p = {1,4}
Para p = 4: cx4 ; c4 = 3
ch + cp ≥ zmin - z0
?
ch + c 4 ≥ ∞ - 0 ?
10 + 3 ≥ ∞
No cumple la prueba, x4 no es cero
Ni x1 ni x4 empeoran la optimalidad.
Suponer que en caso anterior zmin = 40 y z0 = 26
Para p =1: x1 ; c1 = 5
ch + cp ≥ zmin - z0
?
ch + c1 ≥ 40 - 26 ?
10 + 5 ≥ 14
Cumple la prueba, x1 = 0
Para p = 4: x4 ; c4 = 3
10 + 3 ≥ 14
No cumple la prueba, x4 no se fija en 0
• Es una prueba de ampliación (movimiento forward).
• Permite fijar una variable libre en el nivel 1.
• Realiza una prueba con una medida empírica de infactibilidad
total.
• Se promueva a 1 la variable que menos afecta la infactibilidad.
• Se aplica si fracasan las pruebas de ampliación de Geoffrion y de
Glover-Zionts.
c
En el ejercicio base, asumir que la prueba de ampliación de Geoffrion
Glover-Zionts fracasan y por lo tanto, N02 = { 1, 3, 4 }.
y de
La prueba 4 de balas (de ampliación) intenta adicionar variables a la solución
parcial que es:
J0 = {
Variables de holgura:
S10 = -2;
v1 = ∑
i=1,3
ø}
S10 = 0;
S30 = -1
min (0, Si0 - ai1 )
N02 = { 1, 3, 4 } ;
S10 = -2;
v1 = ∑
S10 = 0;
i=1,3
min (0, Si0 - ai1 );
S30 = -1
i=1
i=2
i=3
v1 = min (0, S10 - a11 ) + min (0, S20 - a21 ) + min (0, S30 - a31 )
v1 = min (0, -2 - (-1) ) + min (0, 0 - 2 ) + min (0, -1 - 0 ) = -1 -2 -1 = -4
v1 = - 4
N02 = { 1, 3, 4 } ;
S10 = -2;
v3 = ∑
S10 = 0;
i=1,3
min (0, Si0 - ai3 );
S30 = -1
i=1
i=2
i=3
v3 = min (0, S10 - a13 ) + min (0, S20 - a23 ) + min (0, S30 - a33 )
v3 = min (0, -2 - (-5) ) + min (0, 0 - 3 ) + min (0, -1 – (-2)) = 0 -3 + 0 = -3
v3 = - 3
N02 = { 1, 3, 4 } ;
S10 = -2;
v4 = ∑
S10 = 0;
i=1,3
min (0, Si0 - ai4 );
S30 = -1
i=1
i=2
i=3
v4 = min (0, S10 - a14 ) + min (0, S20 - a24 ) + min (0, S30 - a34 )
v4 = min (0, -2 - (-1) ) + min (0, 0 - 2 ) + min (0, -1 – 1 ) = -1 - 2 - 2 = -5
v4 = - 5
v1 = - 4 ;
v3 = - 3;
vj
*
= max { v1 , v3 , v4 }
vj
*
= max { -4, -3, -5 } = -3
v4 = - 5
v3
x3 es promovida a 1 porque es la que menos
afecta la infactibilidad.
x3 es promovida a 1.
Para el ejercicio base, la nueva solución es:
J1 = { 3 } ; N = {1,2,3,4,5} ;
Función objetivo:
N - J1 = {1,2,4,5} : variables libres
z = 5 x1 + 7 x2 + 10 x3 + 3 x4 + x5
z1 = 10 ; zmin = ∞
x3 es promovida a 1.
Se recalcula infactibilidad: x1 = x2 = x4 = x5 = 0; x3 = 1;
i=1
i=2
i=3
S11 = 3;
S11 = - 3;
S31 = 1
La solución es infactible. No se actualiza la incumbente
Observaciones:
1. Si existe empate se selecciona la de menor costo.
2. Si vj* = 0 no hay infactibilidad y Jt+1 (nueva solución parcial) es factible. Se
actualiza la incumbente y Jt+1 es sondado.
3. Pueden usarse otros criterios para fijar una variable en 1:
 xj = 1 : variable que produce menor infactibilidad en la restricción
más violada.
 xj = 1 : variable que elimine la infactibilidad en el mayor número de
restricciones.
 xj = 1 : variable que produce menor infactibilidad en la restricción
más violada y con bajo valor de cj.
 xj = 1 : variable que elimine la infactibilidad en el mayor número de
restricciones y con bajo valor de cj.
• Cuando una variable libre es fijada en 0 ó 1, a través de una de las pruebas
de ampliación:
 Se redefine el vector Jt (solución parcial);
 Se chequea factibilidad;
 Se inicia una nueva iteración.
• Si no es posible adicionar variables o una prueba de sondaje resulta exitosa,
se realiza un movimiento hacia atrás (backward).
: Regla LIFO
• Si un solución parcial es sondada, se realiza un movimiento hacia atrás
(backward).
• En el esquema de Balas, debe modificarse el valor de una variable que
aparezca en la solución parcial Jt.
• En la regla LIFO, la última variable en entrar es considerada en futuras
exploraciones.
Por ejemplo, sea Jt :
Jt = {2, -5, 3, 6, 1, 4}
Si esta solución parcial es sondada, la nueva solución parcial es definida por la
relación:
Jt+1 = {2, -5, 3, 6, -1}
: Regla LIFO
Jt = {2, -5, 3, 6}
Jt+1 = {2, -5, 3, -6 }
x2 = 0
x2 = 1
x5 = 1
x5 = 0
x3 = 1
x6 = 0
x6 = 1
S
• Tuan observó que el orden en que las variables son analizadas altera el
proceso de enumeración (lo hace más o menos rápido).
• Define una regla según la cual el elemento a ser complementado es aquel que
produce la menor cantidad de infactibilidad total en la solución parcial.
• Define un nuevo subconjunto J´´ que contiene las variables libres existentes
de izquierda a derecha entre variables subrayadas o desde la última en entrar
y el primer subrayado que se encuentre a la izquierda:
Si
Jt = {2, -5, 3, 6, 1, - 4}
J´´ = {3,6,1}
Si
Jt = {2, -5, 3, 6, 7}
J´´ = {3,6,7}
Para
•
Jt = {2, -5, 3, 6, 7}
J´´ = {3,6,7}
J´´ contiene las variables de la solución parcial que se encuentran en 1.
• El orden de los elementos 3, 6 y 1 es indiferente y lo realmente importante es
el orden y la posición de los elementos subrayados.
• El criterio para seleccionar u elemento de J´´ es permitir condiciones
favorables para producir complementos factibles rápidamente.
En el ejercicio base suponer que: Jt = {- 2, 1, 3, 4}
J´´ = {1,3,4}
y se realiza un movimiento backward siguiendo la prueba de Tuan:
1
1
0
1
1
0
0
1
1
0
0
1
1
0
St1 = 5;
St1 = - 7;
Que variable en 1 debe regresar a 0?
La que menos afecte la infactibilidad.
i=1
i=2
i=3
St1 = 0
En el ejercicio base suponer que: Jt = {- 2, 1, 3, 4}
1
1
0
1
1
J´´ = {1,3,4}
0
0
1
1
0
0
1
1
0
i=1
i=2
i=3
S11 = 5;
w1 = ∑
w3 = ∑
w4 = ∑
S11 = - 7;
im
im
im
S31 = 0
min (0, S11 + ai1 );
min (0, S31 + ai3 );
min (0, S41 + ai4 );
S11 = 5;
S11 = - 7;
w1 = ∑
min (0, Si1 + ai1 );
im
S31 = 0
i=1
i=2
i=3
w1 = min (0; 5 + (-1)) + min (0; -7 + 2) + min (0; 0 + 0)
w1 = 0 + (-5) + 0 = -5
S11 = 5;
S21 = - 7;
w3 = ∑
min (0, Si1 + ai3 );
im
S31 = 0
i=1
i=2
i=3
w3 = min (0; 5 + (-5)) + min (0; -7 + 3) + min (0; 0 + (-2))
w1 = 0 + (-4) + (-2) = -6
S11 = 5;
S21 = - 7;
w4 = ∑
min (0, Si1 + ai4 );
im
S31 = 0
i=1
i=2
i=3
w4 = min (0; 5 + (-1)) + min (0; -7 + 2) + min (0; 0 + 1)
w1 = 0 + (-5) + 0 = -5
w1 = - 5 ;
w3 = - 6;
w4 = - 5
wp = max { w1 , w3 , w4 }
wp = max { -5, -6, -5 } = -5
x1 se complementa ya que c1 > c4.
w3 o w4
x1 pasa a 0 y su complemento se sonda.
Jt = {2, -5, 1, 3, 4}
Entonces:
Jt+1 = {2, -5, -1, 3, 4}
Que es equivalente a:
Jt+1 = {2, -5, 3, 4, -1}
Ejemplo: Encontrar la solución óptima del siguiente PLE con variables binarias:
N = {1, 2, 3, 4, 5}
x1 = x2 = x3 = x4 = x5 = 0
J0 = { ø } → solución parcial inicial vacía.
zmin = ∞ → limitante superior (mejor solución factible conocida).
z0 = 0
→ solución actual.
S10 = -2;
S20 = 0;
S30 = -1 → infactibilidad inicial de cada
restricción
Variables libres con coeficiente positivo en
todas las restricciones violadas.
Para la primera iteración t = 0:
i=1
S10 = -2
i=2
S20 = 0
i=3
S30 = -1
→
A0 = { 2, 5 }
→
N = { 1, 2, 3, 4, 5 } ; J0 = { ø } ;
A0 = { 2, 5 }
N01 = ( N - J0 ) - A0
N01 = ( {1, 2, 3, 4, 5 } – { ø } ) - { 2, 5 }
N01 = {1, 3, 4 }
Como
N01 ≠
{ø}
Variables que al ser promovidas a 1
en la solución actual no empeoran
la infactibilidad.
no sonda el nodo inicial
Intenta excluir variables libres en N01 porque
afectan la optimalidad.
→
B0 = { ø }
N02 = N01 - B0 = {1, 3, 4 } – { ø }
N02 = {1, 3, 4 }
N02
no es vacia, la solución parcial no es sondada.
Identifica restricciones infactibles que no se
pueden factibilizar usando las variables en N02
N02 = {1, 3, 4 }
Para i = 1 (restricción 1) :
Las variables de N02
mejorada:
1
1
se promueven a 1 y se observa si la infactibilidad no puede ser
0
1
1
1
1
0
Si puede ser mejorada, entonces no se agrega a C0
N02 = {1, 3, 4 }
Para i = 3 (restricción 3) :
Las variables de N02
mejorada.
se promueven a 1 y se observa si la infactibilidad no puede ser
Si puede ser mejorada, entonces no se agrega a C0
La prueba no sonda por infactibilidad.
Calcula el costo relativo asociado a las
variables libres en N02
que pueden resolver
infactibilidad pero afectan la optimalidad mas
allá de la incumbente.
Como aún no se tiene una incumbente, zmin = ∞ no es posible afectar la
optimalidad.
No se realiza la prueba. No sonda.
Identifica variables indispensables en N02 para
alcanzar factibilidad y su valor 0 ó 1.
N02 = {1, 3, 4 }
S30 = -1
S10 = -2
Para i = 1:
S10 - ∑ [min (0, a1j ) ] - | a1j | < 0 ?
-2 - (-1 - 5 -1 ) - | a1j | < 0 ?
5
- | a1j | < 0 ?
j =1,3,4
para j = 1,3,4
para j = 1,3,4
S10 = -2
j =1 → 5 - | a11 | = 5 - | -1 | = 4
no es menor que cero
j =3 → 5 - | a13 | = 5 - | -5 | = 0
no es menor que cero
j =4 → 5 - | a14 | = 5 - | -1 | = 4
no es menor que cero
Para i = 3:
S30 - ∑ [min (0, a3j ) ] - | a3j | < 0 ?
-1 - (-2 ) - | a3j | < 0 ?
1
- | a3j | < 0 ?
j =1,3,4
para j = 1,3,4
para j = 1,3,4
S30 = -1
j =1 → 1 - | a31 | = 1 - | 0 | = 1
no es menor que cero
j =3 → 1 - | a33 | = 1 - | -2 | = -1
es menor que cero
j =4 → 1 - | a34 | = 1 - | 1 | = 0
no es menor que cero
• La prueba se cumple en la restricción 3 y para la variable x3
• Se observa el signo de a33 :
a33 < 0
x3 se fija en 1
• La solución parcial: J0 = {
ø}
es ampliada. Por lo tanto:
J1 = { 3 }
Siempre entra subrayada si la ampliación la realiza la prueba de
Geoffrion, ya que es una variable indispensable.
• Se incrementa el contador de iteraciones: t = 1.
• Se actualiza la solución actual z0 = 0 a:
z1 = 10
(
)
J0 = {
J1 = { 3 }
ø}
• No se actualiza la incumbente porque no se logra la factibilidad:
i=1
i=2
i=3
1
1
1
S11= 3
S21 = -3
S31 = 1
La restricción 2 es infactible con la nueva solución parcial.
Por lo tanto zmin = ∞
Variables libres con coeficiente positivo en
todas las restricciones violadas.
Para la iteración t = 1:
x1 = x2 = x4 = x5 = 0 ; x3 = 1
N - J1 = {1,2,4,5} : variables libres
i=1
S11= 3
i=2
S21 = -3
i=3
S31 = 1
→
A1 = { 1, 4 }
→
N = { 1, 2, 3, 4, 5 } ; J1 = { 3 } ;
A1 = { 1,4 }
N11 = ( N - J1 ) - A1
N01 = ( {1, 2, 3, 4, 5 } – { 3 } ) - { 1, 4 }
N11 = { 2,5 }
Como
N11 ≠
{ø}
Variables que al ser promovidas a 1
en la solución actual no empeoran
la infactibilidad.
no sonda el nodo de J1
Intenta excluir variables libres en N11 porque
afectan la optimalidad.
N11 = { 2,5 }
x2 = 1,
x5 = 1,
z1 + c2 = 10 + 7 = 17 ≥ ∞
z1 + c5 = 10 + 1 = 11 ≥ ∞
Ninguna variable en N11 afectan la optimalidad si fuesen promovidas a 1
→
B1 = { ø }
N12 = N11 - B1 = { 2,5 } – { ø }
N12 = { 2,5 }
N12
no es vacia, la solución parcial no es sondada.
Identifica restricciones infactibles que no se
pueden factibilizar usando las variables en N12
N12 = { 2,5 }
Para i = 2 (restricción 2) :
Las variables de N12
mejorada:
se promueven a 1 y se observa si la infactibilidad no puede ser
1
1
S21 = -3, - 6 – 2 > -3
Si puede ser mejorada, entonces no se agrega a C0
S2 = 5
No sonda
Calcula el costo relativo asociado a las
variables libres en N12
que pueden resolver
infactibilidad pero afectan la optimalidad más
allá de la incumbente.
Como aún no se tiene una incumbente, zmin = ∞ no es posible afectar la
optimalidad.
No se realiza la prueba. No sonda.
Identifica variables indispensables en N02 para
alcanzar factibilidad y su valor 0 ó 1.
N12 = { 2,5 }
S21 = -3
Para i = 2:
S21 - ∑ [min (0, a2j ) ] - | a2j | < 0 ?
-3 - (-6 - 2) - | a2j | < 0 ?
5
- | a2j | < 0 ?
j =2,5
para j = 2,5
para j = 2,5
S21 = -3
j =2 → 5 - | a22 | = 5 - | -6 | = -1
es menor que cero
j =5 → 5 - | a25 | = 5 - | -2 | = 3
no es menor que cero
• La prueba se cumple en la restricción 2 y para la variable x2
• Se observa el signo de a22 :
S21 = -3
a22 < 0
x2 se fija en 1
• La solución parcial: J1 = { 3 } es ampliada. Por lo tanto:
J2 = { 3 , 2 }
Siempre entra subrayada si la ampliación la realiza la prueba de
Geoffrion, ya que es una variable indispensable.
• Se incrementa el contador de iteraciones: t = 1.
• Se actualiza la solución actual z1 = 10 a:
z2 = 10 + 7 = 17
(
)
J0 = {
J1 = { 3 }
J2 = { 3 , 2 }
ø}
• Se actualiza la incumbente porque se logra la factibilidad:
i=1
i=2
i=3
1
1
1
1
1
1
La solución parcial:
S12= 0
S22 = 3
S32 = 0
x2 = 1 ; x3 = 1 ; x1 = x4 = x5 = 0 ;
Es factible. Se actualiza la incumbente:
zmin = 17 y se sonda.
J0 = {
J1 = { 3 }
J2 = { 3 , 2 }
ø}
Como
z2 = 17
(limitante inferior)
Y
zmin = 17
(limitante superior)
Y en J2 = { 3 , 2 } todas las variables están subrayadas (no existen
complementos factibles y de mejor calidad), y no se pueden realizar
pruebas de ampliación porque este nodo fue sondado, el proceso
finaliza con la siguiente solución óptima:
z* = 17
x2 = 1 ; x3 = 1 ; x1 = x4 = x5 = 0 ;
J0 = {
J1 = { 3 }
J2 = { 3 , 2 }
z* = 17
ø}
Recordar que el problema resuelto se obtuvo de la modificación de
otro PLE:
-8
Con:
Hacemos cambio de variables:
se elimina temporalmente,
se agrega al final
coeficientes positivos
-8
x2 = 1 ; x3 = 1 ; x1 = x4 = x5 = 0 ;
Es equivalente en el problema original a:
y1 = y2 = y3 = y4 = 1 ;
y5 = 0 ;
Además, para la función objetivo se tiene la siguiente equivalencia:
z* = 17
Por lo tanto, la función objetivo del PLE original es:
Z* = 17 – 8 = 9
Descargar

Método de enumeración implícita 0-1 (Balas).