Introducción…………………………………………………………………………………i
Objetivo General…………………………………………………………………………….2
Objetivos Específicos…………………………………………………………………………2
Algoritmos de programación no lineal
Programación No Lineal…………………………………………………………………….3
Programación Cuadrática…………………………………………………………………..5
Conclusión…………………………………………………………………………………10
Recomendaciones………………………………………………………………………….11Bibliografía……………………………………………………………………………..….12
Glosario……………………………………………………………………………………..13
L
a programación cuadrática trata el problema de maximizar o minimizar una función objetivo cuadrático sujeta a restricciones de desigualdad lineales sobre las variables, al que denominaremos PCD. Si las restricciones son de igualdad, resulta el programa cuadrático con restricciones de igualdad,denominado PCI.
La resolución de un problema de programación cuadrática no difiere mucho a la de uno lineal. Mediante unas ecuaciones halladas en la parte teórica se puede plantear el problema cuadrático para ser resuelto con la primera etapa del dual simplex.
Algoritmos de programación no lineal
Programación No Lineal
En matemáticas, Programación no lineal (PNL) es el proceso de resolución deun sistema de igualdades y desigualdades sujetas a un conjunto de restricciones sobre un conjunto de variables reales desconocidas, con una función objetivo a maximizar, cuando alguna de las restricciones o la función objetivo no son lineales.
[pic]Formulación matemática del problema
El problema de programación no lineal puede enunciarse de una forma muy simple:
[pic]Maximizar una funciónobjetivo
O
[pic]Minimizar una función objetivo (de coste)
Donde
Métodos de resolución del problema
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 (problemade 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 ensubdivisiones 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 lamejor 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ónsea óptima.
Ejemplos
Ejemplo bidimensional
Un problema sencillo puede definirse por las restricciones:
? x1 ? 0
? x2 ? 0
? x12 + x22 ? 1
? x12 + x22 ? 2
Con una función objetivo a ser maximizada
F(x) = x1 + x2
Donde x = (x1, x2)
Ejemplo tridimensional
[pic]
Otro problema simple se define por las restricciones:
? x12 ? x22 + x32 ? 2
? x12 + x22 + x32 ?10
Con una función objetivo a ser maximizada
F(x) = x1x2 + x2x3
Donde x = (x1, x2, x3)
Programación Cuadrática
Teoría
Un modelo de programación cuadrática se define como sigue:
Maximice (o minimice) z = CX + XT DX
Sujeto a
AX ? b, X ? 0
Donde
La función XT DX define una forma cuadrática donde D es simétrica. La matriz D se define negativa si el problema es de…