Page 155 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

planos de corte.

Este método resuelve problemas lineales con restricciones enteras usando algoritmos regulares sim-
plificados. Cuando se obtiene una solución óptima que tiene un valor no entero para una variable
que ha de ser entera, el algoritmo de planos de corte se usa para encontrar una restricción lineal más
adelante que sea satisfecha por todos los puntos factibles enteros. Si se encuentra esa desigualdad,
se añade al programa lineal, de tal forma que resolverla nos llevará a una solución diferente que es-
peramos que sea “menos fraccional”. Este proceso se repite hasta que se encuentre una solución
entera (que podemos demostrar que es óptima) o hasta que no se hallen más planos de corte.

En este punto comienza la parte del algoritmo de ramificación y poda. Este problema se divide en
dos versiones: una con restricción adicional en que la variable es más grande o igual que el siguiente
entero mayor que el resultado intermedio, y uno donde la variable es menor o igual que el siguiente
entero menor. De esta forma se introducen nuevas variables en las bases según el número de varia-
bles básicas que no son enteros en la solución intermedia, pero son enteros de acuerdo con las res-
tricciones originales. Los nuevos programas lineales se resuelven empleando un método simplificado
y después el proceso es repetido hasta que una solución satisfaga todas las restricciones enteras.

Durante el proceso de ramificación y poda, los planos de corte se pueden separar más adelante, y
pueden ser cortes globales válidos para todas las soluciones enteras factibles, o cortes locales que
son satisfechos por todas las soluciones llenando todas las ramas de la restricción del subárbol de
ramificación y poda actual.

el proBleMa del ageNte vIajero (travelINg SaleSperSoN tSp)

Para programación dinámica, el algoritmo del agente viajero tiene una complejidad de O(n 2 ). Ahora,
2 n
lo que se va a tratar de explicar es el algoritmo visto bajo la óptica de ramificación y acotamiento. El
uso de una buena función de acotamiento permitirá que el algoritmo, bajo el paradigma de ramifica-
ción y acotamiento, en algunos casos, pueda ser resuelto en mucho menor tiempo que el requerido
en programación dinámica.

Sea G = (V, E) una gráfica definida como una instancia del problema del agente viajero, y sea c el
ij
costo de la arista <i, j>, c = ∞ si <i, j> E y sea | V | = n. Sin pérdida de generalidad, se puede
ij
asumir que cualquier recorrido inicia y termina en el vértice 1. De esta forma la solución del espacio
S está dado por S = {1, , 1| es la permutación de (2, 3,..., n)}. |S| = (n – 1)! El tamaño de S
puede ser reducido restringiendo S, de modo que (1, i , i , . . ., i , 1) S si y solo si < i,..., i > E,
1 2 n-1 j j+1
0 ≤ j ≤ n – 1, i = i = 1. S puede estar organizado dentro de un árbol de estados.
0 n
La figura 7.3 muestra la organización del árbol para el caso de una gráfica completa con |V| = 4.
Cada nodo hoja L es una solución y representa el recorrido definido por el trayecto desde la raíz has-
ta L. En la figura 7.3 el nodo 14 representa el recorrido i = 1, i = 3, i = 4, i = 2 y i = 1.
0 1 2 3 4
149