Programacion dinamica

Algunos problemas de optimización matemática se componen de variables enteras y/o
binarias lo que los convierte en problemas de tipo enteros y/o combinatoriales
respectivamente, por esta razón, su solución, a través de computadores, emplea tiempos
grandes cuando se usan técnicas exactas como Branch and Bound, Benders, Balas, entre
otras.
Procurando mejorar la búsqueda de soluciones a este tipo deproblemas se han
empleado, en los últimos tiempos, técnicas heurísticas y técnicas inteligentes como
Colonia de Hormigas, Recocido Simulado, Búsqueda Tabú, Algoritmos Genéticos,
Partículas Swarm, entre otras. En general, están basados en la aleatoriedad y en algunos
criterios obtenidos de la experiencia del diseñador para encontrar una buena solución.
Estas técnicas usan la función objetivo solopara evaluar la calidad de las soluciones, en
muchas ocasiones ignorando la información matemática (gradiente) del problema que se
encuentra en esta función.
En el trabajo planteado se plantea un problema sujeto a ciertas restricciones donde las
variables de decisión son enteras. Matemáticamente, la restricción de que las variables
de decisión deben ser enteras se plantea como un polinomio cuyasraíces corresponden a
los valores enteros de decisión posibles. El problema de la mochila es el usado para
mostrar la aplicación de la metodología propuesta.
La Programación No Lineal (PNL) provee una serie de herramientas que manipulan en
forma estricta los espacios de búsqueda de solución de los problemas, aprovechan
información matemática del problema para dirigirse en cada paso hacia un puntode
buena calidad, mejorando de esta manera la llegada a la solución. Además, PNL permite
el modelamiento de restricciones no lineales, una característica muy útil para la
formulación dada en el presente trabajo a los problemas que involucran variables
enteras. Estas características mencionadas se deben a que en problemas de PNL, el
cumplimiento de las condiciones de Karush-Kuhn-Tucker (condicionesde primer
orden) y algunas condiciones de segundo orden son requeridas para evaluar la
factibilidad y la optimalidad de los puntos que se van encontrando.
La metodología propuesta es aplicable también a problemas con no linealidad en la
función objetivo, en las restricciones de desigualdad y de igualdad. Los resultados
obtenidos muestran que esta propuesta es una alternativa eficiente para lasolución de
problemas de Programación Entera.

Programaci´on Din´amica
Marcel Goic F.1
1Esta es una versi´on bastante preliminar por lo que puede contar con numerosas faltas de ortografia y
errores no forzados. Si encuentran alguno favor de denunciarlo a mgoic@ing.uchile.cl
IN34A: Optimizaci´on Pag. 1
1. Introducci´on
Muchos problemas de programaci´on matem´atica determinan soluciones que repercutenen
la formulaci´on de los problemas a resolver en el pro’ximo per´ıodo o etapa. Una alternativa
es construir un ´unico modelo completo que tenga un gran conjunto de variables indexadas
por etapas e iternalizar las relaciones entre etapas como una restricci´on del problema.
Sin embargo esto pude agrandar mucho el tama˜no del problema. Surge as´ı Programaci´on
Din´amica (PD) como una alternativa dedescomposici´on en que resolvemos subproblemas
mas peque˜nos y luego los ligamos 2. As´ı, programaci´on din´amia consiste en solucionar el
presente suponiendo que en cada etapa futura siempre se tomaran las decisiones correctas.
2. Caracter´ısticas de un Problema de Programaci´on
Din´amica
Para que un problema pueda ser resuelto con la t´ecnica de programaci´on din´amica, debe
cumplir con ciertascaracter´ısticas:
Naturaleza secuencial de las decisiones: El problema puede ser dividido en etapas.
Cada etapa tiene un numero de estados asociados a ella.
La decisi´on ´optima de cada etapa depende solo del estado actual y no de las decisiones
anteriores.
La decisi´on tomada en una etapa determina cual ser´a el estado de la etapa siguiente.
En s´ıntesis, la pol´ıtica ´optima esde un estado s de...