Metodos Enumeracion Algoritmo Lexicografico

Autora: Dra.Sc. Isabel Alonso Berenger
Dpto. de Matemática. Facultad de Matemática y Computación
Universidad de Oriente
MODELOS DE OPTIMIZACIÓN DISCRETOS
MATERIAL No.5: Métodos de enumeración. Algoritmo de Lawler y
Bell. Ejemplo.
OBJETIVO: Conocer en que consisten los Métodos de Enumeración

y el Algoritmo de Lawler y Bell como caso particular de los
mismos.
Métodos de Enumeración.
Los métodos deenumeración aprovechan la ventaja que proporciona un
PLE finito; para el cual el conjunto de valores enteros, que son soluciones
posibles, es finito. Teniendo esto en cuenta realizan una búsqueda en ese
conjunto y así en un número finito de pasos encuentran el óptimo.
El algoritmo de Lawler y Bell es uno de estos algoritmos de enumeración, en
este caso de enumeración parcial y resuelve elsiguiente problema:

Max go (x)
S. A.
con

gij

gi1(x) - gi2(x) ≤ 0,

i = 1,...,m

xj:binaria j = 1,...,n,

x = (x1, x2,..., xn);

(1)

donde las funciones g0 y

(i = 1,..., m; j = 1, 2) son monótonas decrecientes en cada unas de las variables

x1, ..., xn, o sea, si x1 ≥ x2 ⇒ g(x1) ≤ g(x2).
Ejemplo:
Verifiquemos que h(x1, x2, x3) = -x1x2 - x1x3, con x1, x2, x3 binarias es
una función decreciente.

 0 
 0
 0
 
↓

 0
 
 0
1
 
↓

 0
 
1
 0
 
↓

 0
 
1
1
 
↓

1
 
 0
 0
 
↓

0

0

0

0

0

1
 
 0
1
 
↓

1
 
1
 0
 
↓

1
 
1
1
 
↓

−1 −1 − 2

Las hipótesis del problema se cumplen para funciones lineales.

Ejemplo: Sea la función g(x) =16x1 - 2x2 + x3 + 5x5 - 6x7, expresarla como la
suma de dos funciones monótonasdecrecientes.
g11(x) = -2x2 - 6x7
-2x2 - 16x
gg(x)=
- x73- -(-16x
5x5 1 - x3 - 5x5)
12(x)= -16x

Los problemas binarios son transformados con facilidad a la forma (1) ya
que las funciones gi1 y gi2 son conformadas agrupando los coeficientes de igual
signo en la i-ésima fila.
En cuanto a la función objetivo, ésta puede hacerse monótona decreciente
por una simple transformación de las variables, es decir,cuando la variable xj
tiene su correspondiente coeficiente de costo cj > 0, la misma puede ser
reemplazada por un x’j = 1 - xj, dando lugar a un problema binario cuyo
coeficiente c no es positivo. De forma general, cualquier PLE puede ser expresado
según (1) por transformación arbitraria de las funciones en polinomios y
agrupamiento de los coeficientes de igual signo.
El algoritmo de Lawler y Bellconsiste en evaluar algunos de los vectores del
conjunto {0, 1}n, es decir, del conjunto:

{0, 1}n = [{x∈Rn / xj=0 ó xj=1}; j = 1,..., n].
Ahora bien, podemos preguntarnos ¿Cuáles vectores evaluar?. Eso
claramente dependerá de los criterios que establezca dicho algoritmo. Pero será
interesante saber también ¿En que orden considerar los vectores?
A esta última pregunta puede contestarse que en elorden lexicográfico, que es
l

〈

un orden total de Rn . Debe recordarse que x y ⇔ para la primera componente xi

≠ yi se tiene que xi
Ejemplo:

 (0, 1, 0) = x  l
(1, 0, 0) = y  x 〈 y



Sin embargo, como es conocido, no todos los vectores son comparables en el
orden normal. Recordar que en el orden normal de Rn, x < y ⇔ ∀i se cumple que

xi < yi.
Definición:
Dado x ∈ {0, 1}n; x ≠ (1, 1,..., 1); el sucesor lexicográfico de x es el menor
elemento del conjunto {0, 1}n que es mayor que x; el antecesor lexicográfico de
x ≠ (0, 0, ..., 0) es el mayor elemento menor que x.

Observaciones:
♦ Aquí mayor y menor se refiere al orden lexicográfico.
♦ El sucesor lexicográfico del vector x lo denotaremos x + 1.
♦ El antecesor lexicográfico del vector x lo denotaremos x - 1.

Ejemplos:
1. x =(0, 1, 0, 0, 1, 1)
x + 1 = (0, 1, 0, 1, 0, 0)
2. x = (0, 1, 0, 1, 1, 1)
x – 1 = (0, 1, 0, 1, 1, 0)
3. x = (0, 1, 0, 1, 0, 0)
x + 1 = (0, 1, 0, 1, 0, 1)
x –1 = (0, 1, 0, 0, 1, 1)

Definición:

Dado x ∈ {0, 1}n, se denota x* al menor elemento mayor que x no
comparable con x según el orden normal de Rn , (x
Ejemplo:
x = (0, 1, 0, 1, 0, 0)
Mayores lexicográficamente son:
x+1= (0, 1,...

Leer documento completo

Regístrate para leer el documento completo.