Modelos y Algoritmos de Optimización
Enviado por Cristián Lira Camilo • 22 de Noviembre de 2018 • Tarea • 496 Palabras (2 Páginas) • 99 Visitas
Tarea 2
Cristián Lira Camilo – IN77O Modelos y Algoritmos de Optimización – Otoño 2018
- Formulación de al relajar la restricción de tiempo:[pic 1]
Dada la siguiente formulación lineal del problema del camino más corto:[pic 2]
[pic 3] | [pic 4] |
[pic 5] | [pic 6] |
| [pic 7] |
[pic 8] |
Su relajación lagrangeana queda dada por:
[pic 9]
- Analizaremos la implementación de ambos métodos:
- Método del subgradiente:
- Inicialización: fijamos .[pic 10]
- A partir de los parámetros considerados hasta este punto, se resuelve y se obtiene el óptimo (digamos ). Para continuar, existen dos casos:[pic 11][pic 12]
- Si y además , se detiene el algoritmo. es la solución del problema original que relajamos.[pic 13][pic 14][pic 15]
- Si no se cumplen las hipótesis del punto ii)a, debemos volver al inicio del punto ii) para resolver la relajación lagrangeana usando los siguientes parámetros:
[pic 16]
[pic 17]
También debemos incrementar .[pic 18]
- Método de planos cortantes:
Con este método mantenemos en consideración que la solución óptima corresponde a un punto extremo. El algoritmo permite construir un problema lineal equivalente a la relajación lagrangeana, pero considerando solamente ciertas restricciones que toman en consideración un subconjunto de las SBF del problema relajado.
- Inicialización: fijamos una solución básica factible del poliedro de la relajación lagrangeana, vale decir, que pertenece al siguiente conjunto:
[pic 19]
[pic 20]
[pic 21]
[pic 22]
Si bien una vez generada la instancia se puede plantear un punto extremo más fácilmente gracias a la comprensión espacial del problema, un método puede ser comenzar desde el nodo de inicio , fijar en 1 algún arco y fijar en 0 el resto de los arcos en y también todos los contenidos en (para evitar volver al arco ). Al encontrarnos en un nodo , análogamente se fija en 1 un arco en y en 0 el resto de estos en y todos los de . Así hasta llegar al nodo objetivo. Si quedan arcos sin usar, se fijan en 0. Se asegura que a través de este algoritmo no se ciclará, sin embargo, es posible que se llegue a un nodo final diferente al necesario, se debe empezar desde el comienzo escogiendo un arco en distinto al inicial. Si el problema es factible, en algún momento el algoritmo señalará una ruta.[pic 23][pic 24][pic 25][pic 26][pic 27][pic 28][pic 29][pic 30][pic 31][pic 32]
...