CONCEPTOS BASICOS DE POGRAMACIÓN NO LINEAL

 

CONCEPTOS BASICOS DE POGRAMACIÓN NO LINEAL

 

Programación no lineal: 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 una función objetivo a maximizar, cuando algunas de las restricciones o la función objetivo no son lineales.

Qué es una función: una función es una cosa que hace algo. Por ejemplo, una máquina de moler café es una función que transforma los granos de café en polvo. La función (objetivo) traza, traduce el dominio de entrada (denominado región factible) en un rango de salida con dos valores finales denominados valores máximo y mínimo.

 El método Simplex: es un algoritmo de solución muy utilizado para resolver programas lineales. Es la solución algorítmica inicial para resolver problemas de Programación Lineal (PL). Este es una implementación eficiente para resolver una serie de sistemas de ecuaciones lineales. Mediante el uso de una estrategia ambiciosa mientras se salta desde un vértice factible hacia el próximo vértice adyacente, el algoritmo termina en una solución óptima.

 Un algoritmo es una serie de pasos para cumplir con una tarea determinada.

Región de Factibilidad Ilimitada: Tal y como se mencionó anteriormente, aprenda que una solución ilimitada requiere una región de factibilidad cerrada ilimitada. La situación inversa de este enunciado podría no ocurrir. Por ejemplo, el siguiente problema de PL tiene una región de factibilidad cerrada ilimitada, sin embargo, la solución es limitada. Redundancia Entre las Restricciones: Redundancia significa que algunas de las restricciones no son necesarias dado que existen otras más severas.

 

La teoría de la producción implica el análisis de un tipo específico de restricción sobre el comportamiento de la empresa, el impuesto por la tecnología, así como la investigación de los procesos de toma de decisiones de la empresa.

La tecnología es simplemente el medio (o el método) por el cual uno o más factores pueden convertirse en producción(es).

 Las funciones de producción relacionan los factores (frecuentemente denominados factores de producción, o simplemente inputs) con la producción. Se pueden representar gráficamente o matemáticamente.

 La monotonicidad simplemente significa que, si una empresa aumenta el uso de un factor, obtendrá al menos tanta producción.

 La convexidad implica que, si tenemos dos combinaciones de factores para producir una cierta cantidad de producción, la combinación de éstos producirá al menos tanta producción.

 

 

ILUSTRACIÓN GRAFICA DE PROBLEMAS DE PROGRAMACIÓN NO LINEAL

 

 

 

Cuando un problema de programación no lineal tiene sólo una o dos variables, se puede representar gráficamente de forma muy parecida a los ejercicios de programación lineal.

Una representación gráfica de este tipo proporciona una visión global de las propiedades de las soluciones óptimas de programación lineal y no lineal.

Para graficar este tipo de problemas haremos uso del software informático GeoGebra.

Ejemplo:

 

Procedimiento.

1.- Ingresar función objetivo y sus restricciones.

2.- Obtener región factible.

3.- Crear un deslizador.

 4.- Igualar función objetivo al deslizador.

5.- Igualar todas las restricciones.

6.- Intersectar la función objetivo con la función.

7.- Mover el deslizador hasta encontrar la intersección.

 

 

 

TIPOS DE PROBLEMAS DE PROGRAMACION NO LINEAL

 

Los problemas de programación no lineal se presentan de muchas formas distintas. Al con­trario del método simplex para programación lineal, no se dispone de un algoritmo que re­suelva 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 introduci­rán las clases más importantes y después se describirá cómo se pueden resolver algunos de es­tos 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.

 

OPTIMIZACIÓN CLASICA

 

La teoría de optimización clásica o programación matemática está constituida por un conjunto de resultados y métodos analíticos y numéricos enfocados a encontrar e identificar al mejor candidato de entre una colección de alternativas, sin tener que enumerar y evaluar explícitamente todas esas alternativas. Un problema de optimización es, en general, un problema de decisión. Con el fin de ilustrar de forma adecuada la estructura y composición de un problema de optimización, introduciremos a continuación un sencillo ejemplo. Ejemplo 1.1 (Construcción de una caja con volumen máximo) Supongamos que queremos determinar las dimensiones de una caja rectangular de forma que contenga el mayor volumen posible, pero utilizando para ello una cantidad fija de material. El problema en forma abstracta se podría plantear en los siguientes términos Maximizar Volumen de la caja sujeto a Área lateral fija Con el fin de resolver este problema habrá que modelizarlo matemáticamente, es decir tendremos que expresarlo en términos matemáticos. El primer paso para modelizar un problema de optimización es identificar y definir las variables que están implicadas en dicho problema, en este caso y puesto que estamos tratando de determinar el tamaño de una caja rectangular, la opción más clara es considerar como variables sus tres dimensiones rectangulares usuales (ancho, largo, alto) y que representamos con x, y, z. Con estas variables, la función para la que tenemos que encontrar el mejor valor será el volumen de la caja que puede expresarse como V (x; y; z) = xyz A continuación debemos tener en cuenta las limitaciones existentes sobre el material. Como este material se utiliza para construir las paredes de la caja, necesitaremos considerar el área lateral de la misma, y si la caja tiene tapa, dicha área será A (x; y; z)= 2(xy + yz + zx) Por último, teniendo en cuenta que las dimensiones de la caja no pueden ser negativas el problema puede expresarse matemáticamente como Maximizar xyz sujeto a 2 (xy + yz + zx) = A x; y; z ≥ 0

 

 

PUNTOS DE INFLEXION

 

Se define un punto de inflexión como el punto en que la función pasa de ser convexa a cóncava o de cóncava a convexa.

En la siguiente gráfica podemos ver que cuando x = 0, la gráfica pasa de ser cóncava a ser convexa, por lo que podemos decir que el punto de inflexión esta en X = 0.

 

Una característica de los puntos de inflexión es que son los puntos donde la función derivada tiene máximos y mínimos. Si nos fijamos, cuando nos acercamos a un punto de inflexión la función cada vez crece más (o decrece menos), pero al sobrepasar el punto de inflexión la función empieza a crecer menos (o decrecer menos). Esto significa que justamente donde haya un punto de inflexión la derivada tendrá un máximo o un mínimo. Consecuentemente encontraremos los puntos de inflexión buscando ceros de la segunda derivada.

Vamos a ilustrar el proceso con un ejemplo para así dar una explicación simple y clara:

Consideraremos la función F(x) = x³ - 3x (es la función representada en la anterior gráfica).

MAXIMOS Y MINIMOS

 

Mínimo (fuerte): Un punto extremo X0 de una función f(X0) define un mínimo de la función si f(X0+h) > f(X0), donde X0 es cualquier punto de la función y h en valor absoluto es suficientemente pequeña. Máximo (fuerte): Un punto extremo X0 de una función f(X0) define un máximo de la función si f(X0+h) < f(X0), donde X0 es cualquier punto de la función y h en valor absoluto es suficientemente pequeña.

Una función puede contener varios máximos y mínimos, identificados por los puntos extremos de la función. En la figura 1 se puede observar esto, los puntos x1, x3 y x6 son máximos, de la figura notamos que f(x6) es el mayor que f(x1) y f(x3), a este punto se le conoce como máximo global de la función y a los restantes como máximos locales. Lo mismo se puede ver para los mínimos, en los que también existe un mínimo global f(x2) y un mínimo local f(x4). Como es de lógico, solo puede existir un solo global y posiblemente varios locales.

Una condición necesaria pero no suficiente para que X0 sea un punto extremo, es que, para una función con más de una variable, el gradiente Ñ f(X0) = 0. Si es cierto esto entonces X0 será conocido como punto estacionario. Una condición suficiente para que un punto estacionario sea extremo es que la matriz Hessiana H obtenida en X0 del sistema de ecuaciones sea positiva cuando X0 es un punto extremo de mínimo. Y negativa cuando X0 es un punto extremo de máximo. Un máximo débil implica un numero finito de máximos alternativos (ver figura 1) y se define como X0 es un máximo débil, si f (X0 + h) <= f(X0). Un análisis similar es para los mínimos débiles. Un punto de inflexión se encuentra cuando la evaluación del gradiente da cero y no es un extremo, esto es, se debe de cumplir la condición de la matriz Hessiana.