3.3 Tipos de problemas de programación no lineal

Los problemas de programación no lineal se presentan de muchas formas

distintas. Al contrario del método símplex para programación lineal, no se dispone

de un algoritmo que resuelva todos estos tipos especiales de problemas. En su

lugar, se han desarrollado algoritmos para algunas clases (tipos especiales) de

problemas de programación no lineal. Se introducirán las clases más importantes

y después se describirá cómo se pueden resolver algunos de estos problemas.

Si la función objetivo f es lineal y el espacio restringido es un politopo, el problema

es de Programación lineal y puede resolverse utilizando alguno de los bien

conocidos algoritmos de programación lineal.

Si la función objetivo es cóncava (problema de maximización), o convexa

(problema de minimización) y el conjunto de restricciones es convexo, entonces se

puede utilizar el método general de Optimización convexa

Existe una variedad de métodos para resolver problemas no convexos. Uno de

ellos consiste en utilizar formulaciones especiales de problemas de programación

lineal. Otro método implica el uso de técnicas de Ramificación y poda, cuando el

problema se divide en subdivisiones a resolver mediante aproximaciones que

forman un límite inferior del coste total en cada subdivisión. Mediante

subdivisiones sucesivas, se obtendrá una solución cuyo coste es igual o inferior

que el mejor límite inferior obtenido por alguna de las soluciones aproximadas.

Esta solución es óptima, aunque posiblemente no sea única. El algoritmo puede

ser parado antes, con la garantía de que la mejor solución será mejor que la

solución encontrada en un porcentaje acotado. Ello se utiliza en concreto en

problemas importantes y especialmente difíciles y cuando el problema cuenta con

costes inciertos o valores donde la incertidumbre puede ser estimada en un grado

de fiabilidad apropiado.

Las condiciones de Karush-Kuhn-Tucker proporcionan las condiciones necesarias

para que una solución sea óptima.

Los tipos de problemas de programación no lineal son:

 Optimización no restringida.

 Optimización linealmente restringida.

 Programación cuadrática

 Programación convexa.

 Programación separable.

 Programación no convexa.

 Programación geométrica.

 Programación fraccional.

 Problema de complementariedad.