UNIVERSIDAD NACIONAL DE TRUJILLO
FACULTAD DE INGENIERÍA DE MINAS
CURSO:
INVESTIGACIÓN DE OPERACIONES MINERAS.
TEMA:
PROGRAMACIÓN NO LINEAL
AUTOR:
NEYRA RAMOS FLORENCIO ISAIAS.
UNIVERSIDAD NACIONAL DE TRUJILLO
CURSO:
INVESTIGACIÓN DE OPERACIONES MINERAS.
TEMA:
PROGRAMACIÓN NO LINEAL
Autor:
NEYRA RAMOS FLORENCIO ISAIAS
PROGRAMACIÓN NO
LINEAL
INTRODUCCIÓN:
En la Programación Lineal un supuesto importante es que todas sus funciones (objetivo y
de restricción) son lineales. Aunque, en esencia, este supuesto se cumple en el caso de
muchos problemas prácticos, con frecuencia no es así. Por lo tanto, 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.
DEFINICIÓN:
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 (o minimizar), cuando
alguna de las restricciones o la función objetivo no son lineales.
De manera general, el problema de programación no lineal consiste en encontrar
x=(x1, x2,…, xn) para
Maximizar o Minimizar f (x)
sujeto a
gi(x) ≤ bi, para i = 1, 2, . . ., m,
Y
x≥0
Donde f (x) y gi(x) son funciones dadas de n variables de decisión.
Max 3x1 + 5x2
Sujeto a: x1 ≤ 4
x1, x2 ≥ 0
(La solución no siempre esta en los extremos)
Max
Sujeto a: x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
x1,x2 ≥ 0
( La solución puede estar dentro de la región)
Max 3x1 + 5x2
Sujeto a: x1 ≤ 4
2x2 ≤ 14
x 1 , x2 ≥ 0
( La región puede ser no convexa y puede haber “tipos” de óptimos)
En la optimización no lineal, los conceptos de concavidad,
convexidad, región factible y conjunto convexo son muy
importantes, por lo que veremos cada uno de ellos.
• Una función cuya curvatura
siempre es “ hacia abajo” se
llama función cóncava.
• Una función que tiene siempre
una curvatura “hacia arriba” se
llama función convexa.
Un conjunto convexo es un conjunto de puntos tales que, para cada
par de puntos de la colección del segmento de recta que los une esta
totalmente contenido en la colección.
La región factible de un
problema de programación
no lineal es la zona que
contiene a todos los puntos
que cumplen con las
restricciones del modelo, es
decir, representa a todas las
posibles soluciones del
problemas
OPTIMALIDAD
Supongamos que tenemos una función representada en 3D y su
proyección en 2D.
Si tenemos la imagen de la función en todo su dominio podemos
encontrar el optimo global
Optimo Local
En problemas grandes esto no siempre es cierto. Y tenemos solo una perspectiva local o
de “vecindario”.
• Donde el vecindario es una parte del dominio de la función
• La mejor solución en un vecindario es un optimo local
Optimo Local: Una solución es un optimo local (mínimo o máximo
local) si es factible y su en un vecindario determinado no hay
puntos que sean factibles y que den un mejor valor en la función
objetivo
Optimo global
Una solución es un optimo global ( mínimo o máximo global) si es
factible y no hay otra solución factible ( en todo su dominio) que
tenga un mejor valor en la función objetivo.
Note que:
• Un optimo global será siempre un optimo local
• Lo opuesto no siempre es verdad
Ejemplo
MÉTODOS DE RESOLUCIÓN DEL PROBLEMA:
• 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
• Las condiciones de Karush-Kuhn-Tucker proporcionan las condiciones
necesarias para que una solución sea óptima.
TIPOS DE PROBLEMAS DE PROGRAMACIÓN NO LINEAL:
❖ 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.
ALGORITMOS SIN RESTRICCIÓN:
En esta sección se presentarán dos algoritmos para el problema no restringido: algoritmo de búsqueda directa
y el algoritmo de gradiente.
🠶 Método de búsqueda directa:
Se aplican principalmente a funciones estrictamente unimo- dales de una variable.
La idea de los métodos de búsqueda directa es identificar el intervalo de incertidumbre que comprenda al
punto de solución óptima. El procedimiento localiza el óptimo estrechando en forma progresiva el intervalo
de incertidumbre hasta cualquier grado de exactitud que se desee.
Métodos de búsqueda
dicótomo
ALGORITMOS
RELACIONADOS
Método de sección dorada
COMO EL ESTUDIO DE ESTA ESTRATEGIA ES ALGO COMPLEJO, SE TRATARÁ DE
SIMPLIFICAR SU COMPRENSIÓN, ESTUDIANDO PRIMERO LOS SIGUIENTES
CASOS DE FUNCIONES:
Función objetivo de una variable sin restricciones:
La optimización de una función de una sola variable puede lograrse con
relativa facilidad, por medio de la tabulación o de la graficación.
Función objetivo de varias variables sin restricciones:
Se trata de encontrar el conjunto de valores de las variables que determinen el
máximo/mínimo de la función objetivo.
Función objetivo de una sola variable con restricciones:
El modelo matemático general de la función objetivo de una variable con
restricciones es de la forma:
Función objetivo de varias variables con restricciones:
El siguiente es un modelo matemático que contiene una función objetivo de
varias variables, sujetas a restricciones tanto de igualdad como de desigualdad:
OPTIMIZACIÓN MEDIANTE EL MÉTODO DEL GRADIENTE :
Para la optimización de modelos de Programación No Lineal sin restricciones se dispone de
una categoría de métodos denominados “Algoritmos Generales de Descenso” entre los cuales
se destaca el Método del Gradiente o Método del Descenso más Pronunciado.
El cálculo de una dirección de descenso
Primer paso
Obtener la magnitud del paso α (alfa)
segundo paso
TIPOS DE PROBLEMAS NO-LINEALES
Tamaño de los Problemas:
• ESCALA PEQUEÑA: hasta 5 variables y restricciones puede ser resuelto a
mano
• ESCALA INTERMEDIA: de 5 a 100 variables.
• GRAN ESCALA: más de 100 y quizás 1000 variables y restricciones, para
cálculo científico (cray).
DIFERENCIAS ENTRE PROGRAMACIÓN LINEAL Y PROGRAMACIÓN NO LINEAL
EJERCICIO (RESUELTO POR SOLVER)
RESULTADOS
EJERCICIO APLICADO A LA MINERIA (RESUELTO POR LINGO)
RESULTADOS (RESUELTO POR LINGO)
OPTIMIZACIÓN NO RESTRINGIDA:
Los problemas de optimización no restringida no tienen
restricciones.
Sobre todos los valores x= (x1, x2,…,xn). La
condición necesar ia para que una solución específica x = x*
sea óptima cuando f(x) es una función diferenciable es
TEOREMA 1: Condición necesaria de 1° orden
Si P(X,Y,Z) es un extremo local de f, entonces Δf(X,Y,Z) = (0,0,0)
A los puntos que anulan el gradiente se le llama puntos críticos.
TEOREMA 2: Condición necesaria de 2° orden
Sea P(X,Y,Z) un punto critico de f. entonces:
1. Si f posee un mínimo local en P(X,Y,Z), entonces la forma cuadrática asociada al
Hessisiano es semidefinida positiva o definida positiva.
2. Si f posee un máximo local en P(X,Y,Z), entonces la forma cuadrática asociada al
Hessiano es semidefinida negativa o definida negativa.
TEOREMA 3: Condición necesaria de 2° orden
Sea P(X,Y,Z) un punto critico de f. entonces:
1. Si f es indefinida entonces f posee un punto de silla en P(X,Y,Z).
2. Si f es definida positiva, entonces f posee un mínimo local en P(X,Y,Z)
3. Si f es definida negativa, entonces f posee un máximo local en P(X,Y,Z)
EJEMPLO:
El gasto de una mina hace en transportar el mineral hasta la planta procesadora esta
dado por 3 factores. La distancia que se mide a través del factor “X”, el tamaño de
grano del mineral que se mide por el factor “Y” y el tipo de camión que realiza el
transporte que se mide por el factor “Z”. La relación entre estos factores y el gasto
determinado esta dado por:
f(x,y,z) = x – xy2 + y4 – 3yz + z3
Donde el gasto esta dado en millones de soles, minimiza los gastos.
(0,0,0) (1/2,1,1)
CONCLUSION: Encontrado el punto mínimo.
Decimos entonces que, el gasto mínimo de la empresa
minera se de 2.5 millones.
OPTIMIZACIÓN LINEALMENTE RESTRINGIDA:
Los problemas de optimización linealmente restringida se
caracterizan por restricciones que se ajustan por completo a
la programación lineal, de manera que todas las funciones de
restricción g(x) son lineales, pero la función objetivo es no
lineal.
El problema se simplifica mucho si sólo se tiene que tomar
en cuenta una función no lineal junto con una región
factible de programación lineal.
EJEMPLO:
Un joven ingeniero ha sintetizado un nuevo producto de voladura hecho a partir de dos
materias primas. Al combinar cantidades de las materias primas básicas “x” y “y”, la
cantidad de fertilizante que se obtiene viene dada por Q = 2x + x² + 2y + y². Para que el
producto sea efectivo la materia prima 1 (x) debe ser menor o igual a 4 litros y la materia 2
(y) menor igual que 6 litros. Se requieren 2 mil dólares por unidad de materia prima 1 (x) y
3 mil dólares por cada unidad de materia prima 2 (y) que se empleen en la fabricación del
producto. Si la compañía dispone de 18 mil dólares para la producción de materias primas.
Plantear el problema para determinar la cantidad de materia prima de forma que se
maximice la cantidad de dicho producto.
f(x,y) = 2x + x² + 2y + y²
Restricciones:
x ≤ 4
y ≤ 6 x, y ≥ 0
3x + 2y ≤ 18
CONDICIONES DE KARUSH KUHN TUCKER
Son una generalización de los multiplicadores de Lagrange para restricciones de
desigualdad.
Se introduce una variable de holgura o multiplicador de Lagrange.
Las derivadas parciales de la función f respecto a x,y, se deben igualar a 0.
Las derivadas parciales con respecto a las variables tiene que ser = 0
Se tiene que cumplir la restricción de igualdad.
Se tiene que cumplir las desigualdades.
Las dos λ tienen que ser mayor o igual a 0.
EJEMPLO:
Una compañía minera debe determinar cuantas toneladas de mineral hay que extraer en los
próximos dos años. Si la compañía extrae X1 millones de toneladas de mineral durante un
año, se podrá vender cada tonelada a 30 – X1 $. Si extrae X2 millones de toneladas durante
el segundo año, se podrá vender cada tonelada a 35 - X2 $. El costo para extraer X1
millones de toneladas en el 1er año es de X12 millones de dólares ($) y el costo para extraer
X2 millones de toneladas durante el 2do año es de X22 millones de dólares ($). Se puede
obtener como máximo un total de 20 millones de toneladas de mineral, y se puede gastar
como máximo 250 millones de dólares ($) en la extracción.
Ayuda a la empresa a maximizar sus ganancias para los próximos 2 años.
Por no cumplir con todas las Condiciones de Karush Kuhn Tucker descartamos los
puntos 2,3,4,5 y 6. Por lo tanto solo el punto 1 cumple con las condiciones.
En conclusión tenemos un punto optimo x1= 7.5 y x2 = 5.83, es decir que la
compañía minera tiene que producir 7.5 millones de toneladas en el primer año y 5.83
millones de toneladas el segundo año para maximizar sus ganancias.
EJEMPLO
Una compañía Great Westein Appliance comercializa dos modelos de hornos tostadores, el micro
tostador (x1) y el horno con auto limpieza (x2). La firma obtienes una utilidad de 28 dólares por
cada micro tostador sin importar el numero de vendidos. No obstante, las utilidades del modelo
auto limpieza se incrementan conforme se venden mas utilidades, a causa de los costos indirectos
fijos. En este modelo, la utilidad se expresa como 21x 1 + 0.25x2.
Por lo consiguiente, la función objetivo de la firma no es lineal
Min 28x1 + 21x2 + 0.25 x22
La utilidad de Great Westein esta sujeta a dos restricciones lineales: una capacidad de producción
y otra del tiempo de ventas disponible.
X1 + x2 ≤ 1000 Unidades de capacidad de producción
0.5x1 + 0.4 x2 ≤ 5000 Hora de tiempo de ventas disponibles
PROGRAMACÍÓN SEPARABLE:
La programación separable es un caso especial de programación convexa, en donde
la suposición adicional es
Todas las funciones f(x) y g(x) son funciones separables.
Una función separable es una función en la que cada término incluye una sola
variable, por lo que la función se puede separar en una suma de funciones de
variables individuales
ALGORITMOS DE PROGRAMACIÓN SEPARABLE.
1. Algoritmos de gradiente, en estos casos se modifica de alguna manera el procedimiento de
búsqueda del gradiente para evitar que la trayectoria de búsqueda penetre la frontera de
restricción.
2. Algoritmos secuenciales no restringidos, incluye los métodos de función de penalización y
de función barrera; estos algoritmos convierten el problema de optimización restringida
original en una sucesión de problemas de optimización no restringida, cuyas soluciones
óptimas convergen a la solución óptima del problema original.
3. Algoritmos de Aproximación Secuencial, incluye métodos de aproximación lineal y
aproximación cuadrática; estos algoritmos sustituyen la función objetivo no lineal por una
sucesión de aproximaciones lineales o cuadráticas. Para problemas de optimización
linealmente restringidos, estas aproximaciones permiten la aplicación repetida de los
algoritmos de programación lineal o cuadrática.
PROGRAMACIÓN GEOMÉTRICA:
Cuando se aplica programación no lineal a problemas de diseño de ingeniería, muchas veces
la función objetivo y las funciones de restricción toman la forma
En tales casos, las ci y a ty representan las constantes físicas y las x} son las variables de
diseño. Estas funciones por lo general no son ni cóncavas ni convexas, por lo que las técnicas
de programación convexa no se pueden aplicar directamente a estos problemas de
programación geo- métrica. Sin embargo, existe un caso importante en el que el problema
se puede transformar en un problema de programación convexa equivalente. Este caso es
aquel en el que todos los coeficientes c¿ en cada función son estrictamente positivos, es decir,
las funciones son polinomios positivos generalizados (ahora llamados posinomiales), y la
función objetivo se tiene que minimizar. El problema equivalente de programación convexa
con variables de decisión yx, y2,…, yn se obtiene entonces al establecer
PROGRAMACIÓN FRACCIONAL:
Suponga que la función objetivo se encuentra en la forma de una fracción, esto es, la razón o
cociente de dos funciones.
Estos problemas de programación fraccional surgen, por ejemplo, cuando se maximiza la razón
de la producción entre las horas-hombre empleadas (productividad), o la ganancia entre el capital
invertido (tasa de rendimiento), o el valor esperado dividido entre la desviación estándar de alguna
medida de desempeño para una cartera de inversiones (rendimiento/riesgo). Se han formulado
algunos procedimientos de solución especiales 1 para ciertas formas de f1(x) y f2 (x)
Cuando se puede hacer, el enfoque más directo para resolver un problema de programación
fraccional es transformarlo en un problema equivalente de algún tipo estándar que disponga de
un procedimiento eficiente. Para ilustrar esto, suponga que f(x) es de la forma de
programación fraccional lineal
Donde c y d son vectores renglón, x es un vector columna C 0 y d0 son escalares. También
suponga que las funciones de restricción gi(x) son lineales, es decir, las restricciones en forma
matricial son Ax <= b y X >= 0.
Bajo algunos supuestos débiles adicionales, el problema se puede transformar en un problema
equivalente de programación lineal si se establece:
De manera que X = y/t. Este resultado conduce a:ç
Maximizar Z = cy + ct,
Sujeta a
Ay – bt <= 0,
Dy + d0t = 1
Y
Y >= 0, t>= 0
CASO
Método Simplex: Un método basado en el proceso de eliminación de Gauss-Jordan para
resolver problemas de programación lineal.
Programación no Lineal Fraccional: En este tipo de programación, la función objetivo se
puede expresar como el cociente de dos funciones lineales de n variables, donde el
numerador debe ser cóncavo y el denominador convexo. Las restricciones de un problema
de Programación Fraccional deben ser lineales y convexas.
SOLUCIÓN:
PASO 1.
Se identifican los valores de c y d, así también, los vectores de la restricción y vector solución.
Recordando la forma de la función objetivo como:
PASO 2. Para obtener un nuevo problema lineal, se efectúa la sustitución de la siguiente manera:
PASO 3. Se obtiene un nuevo problema lineal de la forma:
PASO 4. Resolviendo por el Método Simplex.
