Materia:
Investigación de operaciones
Docente:
Erika Lissette Minaya Mortera
Alumna:
Lidia Ivette Alor Santiago
Unidad 3:
Programación no Lineal
El trabajo que presentamos a continuación es un
tutorial de investigación de operaciones,
específicamente hablamos sobre el tema de
programación no lineal donde explicamos a
detalle los mas importe sobre programación no
lineal de manera que sea entendible.



Conceptos básicos de problemas de
programación no lineal.
Ilustración grafica de problemas de
programación no lineal.
Tipos de problemas de programación no
lineal.
El tema que abordamos está compuesto por los
siguientes epígrafes: introducción, definimos el
problema general de Programación no Lineal que
estudiamos, y daremos las definiciones y
resultados básicos que se emplearán a lo largo de
todo el tema. Asimismo, se recuerda el estudio
de los problemas irrestrictos (PI) y de los
problemas con restricciones de igualdad (PRI).
Una suposición importante de programación
lineal es que todas sus funciones (Función
objetivo y funciones de restricción) son lineales.
Aunque, en esencia, esta suposición se cumple
para muchos problemas prácticos, es frecuente
que no sea así. De hecho, muchos economistas
han encontrado que cierto grado de no linealidad
es la regla, y no la excepción, en los problemas de
planeación económica, por lo cual, muchas veces
es necesario manejar problemas de programación
no lineal.
La Programación no Lineal (PNL) es una parte
de la Investigación Operativa cuya misión es
proporcionar una serie de resultados y técnicas
tendentes a la determinación de puntos óptimos
para una función (función objetivo) en un
determinado
conjunto
(conjunto
de
oportunidades), donde tanto la función objetivo,
como las que intervienen en las restricciones que
determinan el conjunto de oportunidades
pueden ser no lineales.
Evidentemente, la estructura del problema puede
ser muy variada, según las funciones que en él
intervengan (a diferencia de la Programación
Lineal (PL) donde la forma especial del conjunto
de oportunidades y de la función objetivo
permiten obtener resultados generales sobre las
posibles soluciones y facilitan los tratamientos
algorítmicos de los problemas).
Ello ocasiona una mayor dificultad en la
obtención de resultados, que se refleja también
en la dificultad de la obtención numérica de las
soluciones.
Programación no lineal (PNL) es el proceso de
resolución de un sistema de igualdades y
desigualdades sujetas a un conjunto de restricciones
sobre un conjunto de variables reales desconocidas,
con un función objetivo a maximizar, cuando alguna
de las restricciones o la función objetivo no son
lineales.
De una manera general, el problema de programación no
lineal consiste en encontrar
maximizar
para
,
sujeta a :
en donde
y las
son funciones dadas de n
variables de decisión. No se dispone de un algoritmo que
resuelva todos los problemas específicos que se ajustan a
este formato. Sin embargo, se han hecho grandes logros en
lo que se refiere a algunos casos especiales.
Una combinación de variables instrumentales x se
dice que es factible para el problema (PNL) si
pertenece a X.
Así pues, el problema (PNL) consiste en encontrar
las variables de decisión factibles para el problema
para las cuales la función objetivo tome el mayor
valor posible. Si para un punto, la función objetivo
toma el valor máximo de todos los puntos situados
en algún entorno suyo, se dice que el máximo es
local. Si se encuentra un punto que produce el valor
máximo de f en todo el conjunto de oportunidades,
el máximo es global:
Definición 1.
Un punto x* ∈ X se dice que es un máximo local de
(PNL) si existe un entorno de x*, E(x*) tal que ∀ x ∈
E(x*) ∩ X, se verifica f(x*) ≥ f(x).
Definición 2.
Un punto x* ∈ X se dice que es un máximo global de
(PNL) si ∀ x ∈ X, se verifica f(x*) ≥ f(x).
Es importante tener en cuenta que esta formulación
del problema no supone pérdida de generalidad, ya
que si el objetivo fuese minimizar la función
objetivo, se puede maximizar su opuesta.
Por otro lado, cualquier restricción con ≥ se puede
convertir en una de ≤ sin más que cambiar de signo,
y las restricciones de igualdad se pueden
descomponer en dos, con las dos desigualdades. No
obstante, también enunciaremos los resultados más
importantes para el problema de mínimo.
Antes de pasar a estudiar los diferentes tipos de
problemas, vamos a enunciar dos teoremas cuya
utilidad es crucial en el tema que nos ocupa. Ambos
están orientados a poder asegurar la globalidad de
los óptimos obtenidos. En efecto, veremos que la casi
totalidad de los métodos y caracterizaciones
empleados en la resolución de problemas no lineales
sólo nos garantizan la obtención de óptimos locales.
El primero de los teoremas que enunciamos
(Teorema de Weierstrass) nos da las condiciones bajo
las cuales podemos asegurar la existencia de óptimos
globales en un problema. El segundo (Teorema Local
- Global) nos proporciona las condiciones que nos
permiten afirmar que un óptimo local es global. La
demostración de ambos teoremas puede encontrarse
en Caballero, González y Triguero (1992):
Teorema 1. Teorema de Weierstrass.
Dado el problema (PNL), si el conjunto de
oportunidades X es compacto y no vacío, y la
función objetivo f es continua en X, entonces el
problema (PNL) posee máximo y mínimo globales.
Teorema 2. Teorema Local - Global.
Dado el problema (PNL), si el conjunto de
oportunidades X es convexo, y la función objetivo f
es continua y cóncava (resp. convexa) en X, entonces
cualquier máximo (resp. mínimo) local de (PNL) es
global.
Teorema 3. Condiciones necesarias para óptimo
local.
a) Es condición necesaria de primer orden para que
x*∈ D, sea un óptimo local de f, que:
f '(x*) = 0.
En general, a los puntos tales que anulen la primera
derivada de una cierta función f les denominaremos
puntos críticos de dicha función.
b) Es condición necesaria de segundo orden para que
el punto crítico x* sea máximo local de f que:
f ''(x*) ≤ 0.
o bien, para mínimo local de f que
f ''(x*) ≥ 0.
Mínimo local estricto
Teorema 4.
Condiciones suficientes para óptimo local.
a) Si el punto crítico x´, es tal que f ''(x´) < 0, entonces
x* es un máximo local de f.
b) Si el punto crítico x´, es tal que f ''(x´) > 0 entonces
x* es un mínimo local de f.
Así pues, la condición necesaria de primer orden
exige que la primera derivada se anule en el punto
en cuestión y la de segundo orden que la segunda
derivada sea no positiva en el caso de máximo y no
negativa en el de mínimo. Por su parte, la condición
suficiente exige que los signos de las segundas
derivadas sean estrictos.
Ahora veremos que los resultados enunciados para
el caso n = 1 tienen su extensión natural al caso
general. En efecto, las generalizaciones de los
conceptos reales de primera y segunda derivadas al
caso de dimensión superior son los de gradiente y
hessiana respectivamente.
Así pues, veremos que la condición necesaria de
primer orden exige que se anule el gradiente de la
función, y las condiciones de segundo orden
suponen exigencias sobre el signo de la hessiana, es
decir, sobre el signo de la forma cuadrática
correspondiente a la matriz hessiana.
Ejemplo de Problema No Lineal Irrestricto
Ejemplo 1 Considere el problema
P) min−2x1 x2− 2x2 +x21+ 2x22
s.a. (x1+,x2 ) 3 R2
Las condiciones de primer orden son:
la condición necesaria de primer orden, que en el
caso n = 1 consiste en la anulación de la primera
derivada de la función en el punto, es decir todas las
derivadas parciales sean 0. De igual forma que en el
caso anterior, se denominará punto crítico de f a
cualquier punto x de D tal que ∇f(x) = 0.
∇ f(x) = 0 ) x = 1, x = 1
1
2
• El Hessiano de la función objetivo en (1, 1):
• H es definida positiva en todo D, y en particular en
(1, 1)
• El punto corresponde a un mınimo ´unico global
estricto de P)
Ejemplo 2 Considere el problema
P) min x4
• Tenemos que:
f’(x) = 4x3
f´´(x) = 12x2
• En ¯x = 0, f´(x) = 0 y f’’(x) = 0.
• El punto cumple con la condición necesaria de
2°orden.
• De esta información no se podrá inferir nada más,
pero:
f´´(x) = 12x2 >0 ¥x
f(x) es convexa
• Además es diferenciable, entonces x = 0 es un punto
mínimo local de P).
El objeto de la siguiente investigación es definir una
serie de conceptos relacionados con el problema
general de programación no lineal, así como el estudio
de las relaciones existentes entre cada uno de ellos y la
solución de dicho problema.
Los conceptos que estudiaremos serán los siguientes:
• Punto estacionario.
• Punto minimax, íntimamente relacionado con el
concepto de dualidad.
Veremos que, en general, será más directa la
demostración de la suficiencia de estas condiciones
para asegurar que tenemos una solución del
problema, para las que habrá que imponer
condiciones de regularidad sobre las restricciones
del problema, que llamaremos cualificaciones de
restricciones.
Un problema general de programación no lineal
consiste en encontrar los valores de ciertas variables
que maximizan o minimizan una función dada,
dentro de un conjunto definido por una serie de
restricciones de desigualdad, de forma que no hay
aseguradas condiciones de linealidad ni sobre la
función a optimizar ni sobre las funciones que
definen el conjunto dentro del cual buscamos dicho
óptimo.
Es decir, el problema consiste en:
o, de forma abreviada,
Donde:
y
y son ambas al menos de clase dos en todo su
dominio.
En ocasiones, para que el problema sea
económicamente significativo, es necesario que las
variables instrumentales sean no negativas, es decir,
x ≥ 0.
Asociadas al problema de maximización, podemos
definir la siguiente función:
• Función de LaGrange L:
donde λ ∈ Rm+ es el vector de multiplicadores
asociado al bloque de restricciones del problema,
también denominados multiplicadores de KuhnTucker.
Cualificaciones de restricciones.
En el caso en que no tuviéramos asegurada la
diferenciabilidad de las funciones de restricciones, la
cualificación más usada es la denominada
cualificación de restricciones de Slater tipo 1:
• Cualificación de Slater, tipo 1.
Dado el problema (PRD), se dice que se satisface la
cualificación de restricciones de Slater tipo 1 (en X) si
g es convexa en X y existe un x ∈ X tal que g(x) < b
(es decir, el conjunto de oportunidades tiene interior
no vacío).
La cualificación de restricciones que utilizaremos en
el caso diferenciable es:
• Cualificación de Restricciones de la Independencia
Lineal.
Dado el problema (PRD), se dice que se satisface la
cualificación de restricciones de la independencia
lineal en x si el conjunto D es abierto, gi , para i ∉ I es
continua en x y los vectores ∇gi(x), para i ∈ I, son
linealmente independientes.
Procedemos entonces, tras haber establecido ciertos
conceptos básicos en la sección anterior, a resolver el
problema
PDR
donde suponemos que se dan condiciones de
diferenciabilidad sobre f y g y que el conjunto D es
abierto. En esta situación, tenemos aseguradas ciertas
condiciones de diferenciabilidad sobre la función de
Lagrange L. Empezaremos definiendo el concepto de
punto estacionario de Kuhn-Tucker a partir de L. Dado el
problema (PRD) y la función de Lagrange L asociada a él,
diremos:
Que (x0, λ0), x0 ∈ D, λ0 ∈ Rm , es un punto estacionario de
Kuhn-Tucker (o punto estacionario de L)
si verifica las llamadas condiciones de Kuhn-Tucker
(dadas de dos formas equivalentes):
Podemos observar que estas condiciones pueden
formularse de la siguiente forma, supuesto que x0 es
un punto factible:
En el caso de formulación para mínimo, las
condiciones de punto estacionario son las mismas,
pero aplicadas a las lagrangianas para mínimo, con
lo cual cambia el signo con el que entran los
multiplicadores, quedando por tanto
Veamos seguidamente el teorema que lo relacionan
con
las
soluciones
del
problema
(PRD).
Empezaremos con el teorema de condiciones, el
teorema en el que se establecen qué condiciones
necesariamente deben verificar los óptimos de
(PRD).
Sea x0 un punto factible de (PRD) y sea I = { i / gi(x0) = bi}.
Supongamos que f y gi , con i ∈ I, son diferenciables en x0.
Además, supongamos que se verifica la cualificación de
restricciones de independencia lineal en x0. Si x0 es un
óptimo local del problema, entonces existen escalares no
negativos λi para i ∈ I, tales que:
Como se observa, gracias a la formulación de punto
estacionario de Kuhn-Tucker, este teorema afirma
que, si se verifica la cualificación de restricciones de
independencia lineal en x0, entonces necesariamente
todo óptimo local del problema es un punto
estacionario de Kuhn-Tucker.
El punto minimax de la función lagrangiana es otro
concepto relacionado con la solución de un problema de
optimización. Si bien su definición no le hace útil a la
hora de la resolución directa del problema, sí constituye
un paso intermedio muy importante en la obtención del
problema dual. Dado el problema (PRD), diremos que
(x0, λ0) ∈ D x Rm+ es un punto minimax de la función
lagrangiana L(x, λ) en el conjunto D x Rm+ si
La relación del punto minimax con la solución del
problema de programación no lineal se obtiene
de forma inmediata sin mas que tener en cuenta que:
• Si gi (x) - bi ≤ 0, entonces λi [gi(x) - bi] ≤ 0, luego
Así pues, si (x0, λ0) es un punto minimax, x0 es una
solución óptima del problema original.
Para el problema de mínimo, el punto minimax toma la
forma:
tomando además la función lagrangiana correspondiente
a este problema.
• Hay problemas donde resolver ∇f(x) = 0 es muy
difícil
• Alternativa: métodos numéricos y/o iterativos
– Búsqueda unidireccional
– Método de Newton
– Método del Gradiente o de Cauchy
Apuntes
• Método para funciones dos veces diferenciables
• Puede usarse para funciones de múltiples
variables
• P) de una sola variable: min f(x) con f’(x) y f’’(x)
conocidas.
• Sea xk un punto factible
• Se puede aproximar f(x) entorno a xk, a través de
una expansión de
Taylor de 2do grado:
Aproximación de Segundo Orden
• q(x) es una buena aproximación de segundo grado
para f(x) ya que:
1. q(xk) = f(xk)
2. q´(xk) = f*(xk)
3. q´´(xk) = f**(xk)
• Si f’’(xk) > 0 ' q(x) es convexa, y si f’’(xk) < 0 ' q(x) es
cóncava.
• Resolvemos min q(x), en vez de min f(x). Condición de
1er orden:
dqk/dx= f´(xk) + f’’(xk)(x − xk) = 0
• Despejando, y definiendo un nuevo xk+1 nos queda:
Interpretación del Método de Newton
• Condición de 1er orden para un extremos de f(x)
∇f(x) = 0
el método de Newton busca raíces def´(x)
• Gráficamente, el método consiste en que en el espacio
de la derivada def(x) se trace una recta que pase por el
punto (xk, f´(xk)) y que tenga pendiente f´´(xk), es decir
y − f´(xk) = (x − xk)f”(xk).
• Luego, el punto de intersección de esta recta con el
eje x determinará
xk+1, es decir, igualando y = 0.
• El método busca puntos extremos sean estos
mínimos o máximos.
• Para distinguir hay que mirar el signo de la 2a
derivada en cada punto:
– Deberá ser positivo al buscar mínimos y negativo
al buscar máximos.
• Este método no garantiza convergencia:
Descargar

archivo - WordPress.com