Antología de Investigación de Operaciones
Ingeniería en Sistemas Computacionales
Unidad 3
Programación No Lineal
3.1. Conceptos básicos de problemas de programación no lineal
La programación no lineal o Dinámica es una técnica matemática que a menudo resulta útil a tomar
una sucesión de decisiones interrelacionadas. Proporciona un procedimiento sistemático para determinar la
combinación de decisiones que maximice la efectividad global.
Contrastando con la programación lineal, no existe un planteamiento matemático estándar "del"
problema de programación dinámica. Más bien, la programación dinámica es un tipo general de enfoque
para resolver problemas y las ecuaciones particulares usadas deben desarrollarse para que se ajusten a cada
situación individual. Por lo tanto, se requiere un cierto grado de ingenio y de visión de la estructura general
de los problemas de programación dinámica, a fin de reconocer cuando un problema se puede resolver
mediante los procedimientos de esta programación y cómo se haría. Probablemente se puedan desarrollar
mejor estas aptitudes por medio de una exposición de una amplia variedad de aplicaciones de la
programación dinámica y de un estudio de las características que son comunes a todas estas.
Por fortuna, la programación dinámica suministra una solución con mucho menos esfuerzo que la
enumeración exhaustiva. (Los ahorros de cálculo serían enormes para versiones más grandes de un
problema.) La programación dinámica parte de una pequeña porción del problema y encuentra la solución
óptima para este problema más pequeño.
Entonces gradualmente agranda el problema, hallando la solución óptima en curso a partir de la
anterior, hasta que se resuelve por completo el problema original. En seguida se dan los detalles
involucrados en la implementación de esta filosofía general.
Considérese que las variables de decisión xn (n = 1,2,3,4) son el destino inmediato en la etapa n.
Así, la ruta seleccionada sería 1 - XI - X2 - X3 - X4 en donde X4 = 10. Sea fn(s, Xn) el costo total de la
mejor política global para las etapas restantes, dado que el vendedor se encuentra en el estado s listo para
iniciar la etapa n y se selecciona a XII como el destino inmediato. Dados s y n, denotemos por x el valor de
X*n que minimiza al fn(s, Xn) y sea f*(s) el valor mínimo correspondiente de fn(s, Xn) por tanto, f*n(s) =
fn(s, Xn). El objetivo es hallar f1*(1) y la pol1tica correspondiente. La programación dinámica hace esto,
hallando sucesivamente f4*(s),f3*(s), f2*(s) , a continuación, f1*(1).
56