UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD ESCUELA DE CIENCIAS BSICAS, TECNOLOGA E INGENIERA

PROGRAMACIN NO LINEAL

Conceptos generales

INTRODUCCIN Una suposicin importante de programacin lineal es que todas sus funciones Funcin objetivo y funciones de restriccin son lineales. Aunque, en esencia, esta suposicin se cumple para muchos problemas prcticos, es frecuente que no sea as. De hecho, muchos economistas han encontrado que cierto grado de no linealidad es la regla, y no la excepcin, en los problemas de planeacin econmica, por lo cual, muchas veces es necesario manejar problemas de programacin no lineal de una manera general, el problema de programacin no lineal consiste en encontrar x = ( x1,x2,....xn ) para maximizar f(x), sujeta a: g(x) bi, para i= 1, 2,3....m y x 0 en donde f(x) y las g(x) son funciones dadas de n variables de decisin. No se dispone de un algoritmo que resuelva todos los problemas especficos que se ajustan a este formato. Sin embargo, se han hecho grandes logros en lo que se refiere a algunos casos especiales, haciendo algunas suposiciones sobre las funciones, y la investigacin sigue muy activa. En este caso se destaca el estudio de optimizacin en una variable sin restricciones de la forma: Optimizar z = f(x) Donde f es funcin no lineal de x y la optimizacin se realiza en (-, ). Si la bsqueda se circunscribe a un sub. Intervalo finito [a, b] el problema es de optimizacin no lineal restringida y se transforma a optimizar z = f(x) con la condicin a x b. Optimizacin no lineal multivariable Es el caso anlogo al anterior, pero en el caso en que la funcin f es de ms de una variable, es decir: Optimizar z = f(X) donde X = [x1, x2, ..., xn]T Si existen las restricciones Gi(X) = 0 Es un problema no lineal multivariable restringido. Ejemplo Una Compaa desea construir una planta que recibir suministros desde tres ciudades A, B, C, tomando como origen la ciudad A, B tiene coordenadas (300 km. al Este,400 Km. al Norte), y C tiene coordenadas (700 Km. al Este, 300 Km. al norte) respecto de A. La posicin de la planta debe estar en un punto tal que la distancia a los puntos A, B y C sea la mnima. sean x1 y x2 las coordenadas desconocidas de la planta respecto de A. Utilizando la frmula de la distancia, debe minimizarse la suma de las distancias

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD ESCUELA DE CIENCIAS BSICAS, TECNOLOGA E INGENIERA

No hay restricciones en cuanto a las coordenadas de la planta ni condiciones de no negatividad, puesto que un valor negativo de x1 significa que la planta se localiza al Oeste del punto A. La ecuacin es un programa matemtico no lineal in restricciones. Veamos ahora algunos casos de programacin no lineal comunes de encontrar:

PROGRAMACIN CUADRTICA

Es un caso particular de programacin matemtica no lineal. Un programa Matemtico en el cual cada restriccin gi es lineal pero el objetivo es cuadrtico se Conoce como programa cuadrtico, es decir f(x1,x2,..,xn) = S i=1,nS j=1,n cijxixj + S i=1,ndixi Ejemplo Minimizar z = x12+X22 Con las condiciones x1 - x2 = 3 X2 3 Donde ambas restricciones son lineales, con n = 2 (dos variables) c11 = 1; c12 = c21 = 0; c22 = 1 y d1 = d2 = 0.

MULTIPLICADORES DE LAGRANGE -CONDICIONES KUNH TUCKER

MULTIPLICADORES DE LAGRANGE.

Se pueden utilizar los multiplicadores de Lagrange para resolver los problemas no lineales en los cuales las restricciones son igualdades. Consideramos los del tipo siguiente: max(o min) z= f(x1,x2,.....xn..) s.a g1( x1,x2,.....xn..)= b1 g2( x1,x2,.....xn..)= b2 gm( x1,x2,.....xn..)= bm para resolverlo, asociamos un multiplicadorL1 con la i-esima restriccin y frmamos el lagrangiano.

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD ESCUELA DE CIENCIAS BSICAS, TECNOLOGA E INGENIERA

TCNICA DEL GRADIENTE

TCNICAS DE GRADIENTE.

En este punto se desarrolla un mtodo para optimizar funciones continuas que son dos veces diferenciables. La idea general es generar puntos sucesivos comenzando en un punto inicial dado, en la direccin del aumento ms rpido maximizacin) de la funcin. Est tcnica se conoce como mtodo del gradiente porque el gradiente de la funcin en un punto es lo que indica la tasa ms rpida de aumento.

MTODO DE NEWTON- RAPHSON

EL MTODO DE NEWTON-RAPHSON.

Una desventaja de utilizar la condicin necesaria f(x)= 0 para determinar puntos estacionarios es la dificultad de resolver numricamente las ecuaciones simultneas resultantes. El mtodo de Newton-Raphson es un procedimiento iterativo para resolver ecuaciones simultneas no lineales. Aunque el mtodo se presenta en este contexto, realmente es parte de los mtodos conocidos como mtodos de gradiente para optimizar numricamente funciones no restringidas, irrestrictas. fi (X) =0, i=1, 2, ..., m seXk un punto dado. Entonces por el desarrollo de Taylor fi(X)= fi (Xk ) + fi(Xk) (X-Xk) , i= 1, 2, ...., m Por consiguiente, las condiciones originales pueden aproximarse por fi (Xk) + fi (Xk) (X-Xk) = 0 , i= 1, 2, ...., m Estas ecuaciones pueden escribirse en notacin matricial como Ak + Bk (X - Xk) = 0 Bajo la hiptesis de que todas las fi(X) son independientes Bk necesariamente es no singular. Por consiguiente, la ltima ecuacin proporciona X = Xk -Bk-1Ak La idea del mtodo es comenzar desde un punto inicial X0. Utilizando la ecuacin anterior, siempre puede determinarse un nuevo punto Xk+1a partir de Xk. El procedimiento finaliza con Xm como la solucin cuando Xm = Xm-1 .

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD ESCUELA DE CIENCIAS BSICAS, TECNOLOGA E INGENIERA

ACTIVIDADES DE AUTOEVALUACIN

TALLER En los siguientes ejercicios identifique y describa los siguientes aspectos del escenario de colas: a. Los clientes y los servidores b. La poblacin de clientes y su tamao c. El proceso de llegada y los parmetros adecuados para la distribucin de llegadas d. El proceso y la disciplina de colas e. Proceso de servicios y los parmetros adecuados para la distribucin tiempo - servicio 1. La divisin de mantenimiento de las Empresas Pblicas de Neiva est tratando de decidir cuntos reparadores necesita tener para proporcionar un nivel aceptable de servicios a sus clientes. Las quejas llegan a un centro de servicios de acuerdo con una distribucin exponencial, con una tasa promedio de 20 llamadas al da. El tiempo que tarda un tcnico reparador en llegar al lugar donde se le llam, resolver el problema y regresar tambin sigue una distribucin exponencial, con un promedio de 3 horas y 30 minutos. 2. El gerente del Supermercado La Sexta desea determinar el nmero mnimo de cajeros que necesita para atender a los clientes que llegan a la hora del almuerzo. El tiempo promedio entre la llegada de dos clientes es de 2 minutos, pero el tiempo real entre llegadas sigue una distribucin exponencial. Cada cajero puede atender un promedio de 12 clientes por hora, pero el tiempo de atencin a cada cliente vara de acuerdo a una distribucin exponencial. 3. El portaaviones de Aires tiene un complemento de 80 aviones. Despus de operaciones de rutina, los aeroplanos son llevados de la cubierta de vuelo a una cubierta inferior, dos a la vez. El recorrido en elevador de una cubierta a otra dura 20 segundos y se necesitan diez segundos para cargar y descargar una aeronave del elevador. Los elevadores llegan al elevador de la cubierta de vuelo cada 30 segundos.

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD ESCUELA DE CIENCIAS BSICAS, TECNOLOGA E INGENIERA

FUENTES DOCUMENTALES

BIBLIOGRAFA

lvarez A. Jorge Investigacin de Operaciones. Programacin Lineal. Editorial. U.N.I.Lima 1995.

Prawda W. Juan Mtodos y Modelos de Investigacin de Operaciones. Tomo I: Modelos Deterministicos. Editorial Limusa. Quinta Edicin. Mxico 2001.

TahaHamdy A. Investigacin de Operaciones. Una Introduccin. Editorial Prentice Hall. Sptima Edicin. Mxico 2000.

Instituto Tecnolgico de Introduccin a la Investigacin de Operaciones. Sonora, Mxico. Abril 2007

Programa Nacional de TIC, Captulo 8: Programacin Lineal. Ministerio de Educacin y Ciencia, Espaa. Set. 2007

Dr. Ing. Franco Bellini M, Curso de Investigacin de Operaciones. Universidad Santa Maria. Caracas Venezuela. Ago.2005