Programacion Lineal.docx

PROGRAMACION LINEAL Y NO LINEAL Programación lineal La Programación Lineal corresponde a un algoritmo a través del cual se resuelven situaciones reales en las que se pretende identificar y resolver dificultades para aumentar la productividad respecto a los recursos (principalmente los limitados y costosos), aumentando así los beneficios. El objetivo primordial de la Programación Lineal es optimizar, es decir, maximizar o minimizar funciones lineales en varias variables reales con restricciones lineales (sistemas de inecuaciones lineales), optimizando una función objetivo también lineal. Los resultados y el proceso de optimización se convierten en un respaldo cuantitativo de las decisiones frente a las situaciones planteadas. Decisiones en las que sería importante tener en cuenta diversos criterios administrativos como:    

Los hechos La experiencia La intuición La autoridad

¿Cómo resolver un problema mediante programación lineal? El primer paso para la resolución de un problema de programación lineal consiste en la identificación de los elementos básicos de un modelo matemático, estos son:

  

Función Objetivo Variables Restricciones

Figura 1

La función objetivo La función objetivo tiene una estrecha relación con la pregunta general que se desea responder. Si en un modelo resultasen distintas preguntas, la función objetivo se relacionaría con la pregunta del nivel superior, es decir, la pregunta fundamental. Así, por ejemplo, si en una situación se desean minimizar los costos, es muy probable que la pregunta de mayor nivel sea la que se relacione con aumentar la utilidad en lugar de un interrogante que busque hallar la manera de disminuir los costos.

Figura 2

Las variables de decisión Similar a la relación que existe entre objetivos específicos y objetivo general, se comportan las variables de decisión respecto a la función objetivo, puesto que estas se identifican partiendo de una serie de preguntas derivadas de la pregunta fundamental. Las variables de decisión son en teoría, factores controlables del sistema que se está modelando, y como tal, estas pueden tomar diversos valores posibles, de los cuales se precisa conocer su valor óptimo, que contribuya con la consecución del objetivo de la función general del problema. Las restricciones Cuando hablamos de las restricciones en un problema de programación lineal, nos referimos a todo aquello que limita la libertad de los valores que pueden tomar las variables de decisión. La mejor manera de hallarlas consiste en pensar en un caso hipotético en el que decidiéramos darles un valor infinito a nuestras variables de decisión, por ejemplo, ¿qué pasaría si en un problema que precisa maximizar sus utilidades en un sistema de producción de calzado decidiéramos producir una cantidad infinita de zapatos? Seguramente ahora nos surgirían múltiples interrogantes, como, por ejemplo:

    

¿Con cuánta materia prima cuento para producirlos? ¿Con cuánta mano de obra cuento para fabricarlos? ¿Pueden las instalaciones de mi empresa albergar tal cantidad de producto? ¿Podría mi fuerza de mercadeo vender todos los zapatos? ¿Puedo financiar tal empresa?

Pues bueno, entonces habríamos descubierto que nuestro sistema presenta una serie de limitantes, tanto físicas, como de contexto, de tal manera que los valores que en un momento dado podrían tomar nuestras variables de decisión se encuentran condicionados por una serie de restricciones.

Formulación matemática Una de las áreas más importantes y activas de la Optimización es la Programación Lineal. Los problemas que trata se basan en la optimización (minimización o maximización) de una función lineal conocida como función objetivo, sujeta a una serie de restricciones lineales de igualdad o desigualdad. Matricialmente, un problema de PL en notación estándar (con igualdades) se puede expresar como: max z = cx s.a Ax = b x≥0 Donde cx es la función objetivo a maximizar o minimizar. La función objetivo puede representar un problema de maximización o minimización. En un problema concreto, las restricciones pueden venir dadas en términos de igualdad o desigualdad (≥ o ≤) y las variables pueden ser no. Sin embargo, dichas variantes pueden transformarse en el problema dado en forma estándar en añadiendo variables adicionales negativas (x ≥ 0), no restringidas (x ∈ IR) o acotadas (l ≤ x ≤ u).

Transformaciones Transformar un problema a notación estándar: 1-Transformaciones sobre la función objetivo: • Transformar un problema de mínimo en un problema de máximo: max(−z) = min z

2-Transformaciones sobre las restricciones: • Transformar una restricción con rhs negativo: sí existe i tal que bi < 0, entonces basta multiplicar por (−1) la restricción. • Transformar desigualdades ≤ en igualdades: sí aparece una restricción del tipo ai1x1 + ai2x2 + . . . + ainxn ≤ bi, entonces definimos una nueva variable de holgura xn+1 ≥ 0 con costo nulo, cn+1 = 0, de manera que reemplazamos la desigualdad por la siguiente igualdad de forma equivalente: ai1x1 + ai2x2 + . . . + ainxn + xn+1 = bi. • Transformar desigualdades ≥ en igualdades: sí aparece una restricción del tipo ai1x1 + ai2x2 + . . . + ainxn ≥ bi, entonces definimos una nueva variable de superavit xn+1 ≥ 0 con costo nulo, cn+1 = 0, de manera que reemplazamos la desigualdad por la siguiente igualdad de forma equivalente: ai1x1 + ai2x2 + . . . + ainxn − xn+1 = bi

3-Transformaciones sobre las variables: • Transformar una variable no positiva en una variable no negativa: sí existe j tal que xj ≤ 0, entonces la reemplazamos por una nueva variable no negativa x˜j = −xj, x˜j ≥ 0. • Transformar una variable no restringida en dos variables no negativas: sí existe j tal que xj ∈ IR (no restringida), entonces la reemplazamos por la diferencia entre dos variables no negativas: xj = x+j – x−j, x+j ≥ 0, x−j ≥ 0. • Transformar una variable acotada inferiormente en una variable no negativa: sí existe j tal que xj ≥ lj, entonces la reemplazamos por una nueva variable no negativa x˜j = xj – lj, x˜j ≥ 0.

• Transformar una variable acotada superiormente en una variable no negativa:

sí existe j tal que xj ≤ uj, entonces la reemplazamos por una nueva variable no negativa x˜j = uj − xj, x˜j ≥ 0.

Clasificación Los problemas de optimización pueden clasificarse, según el carácter de las variables, en:

Problemas lineales generales, si todas sus variables de decisión son continuas, es decir, toman valores en el espacio de números reales IR. Se denominarán simplemente problemas lineales y se denotarán por PL.

Problemas enteros, si todas sus variables de decisión son enteras, es decir, toman valores en el espacio de números enteros Z. También se conocen como problemas enteros puros lineales, y se denotan por PE. En particular, se tiene un problema entero 0–1, si todas sus variables son binarias, es decir, toman valores en el conjunto {0, 1}.

Problemas mixtos, si tienen variables de decisión tanto continuas como enteras. También se conocen como problemas enteros mixtos lineales, y se denotaran por PM. En particular, un problema mixto 0–1 es aquel que contiene tanto variables continuas como variables binarias.

Método simplex El método Simplex es un algoritmo para la resolución de PL. Consiste en un proceso algebraico en el que cada iteración calcula una solución factible. Mediante un criterio de parada en el que se chequea la optimalidad de la solución, se encuentra la solución óptima. El método simplex se basa en tres propiedades claves de las soluciones factibles de punto-extremo, bajo el supuesto de que el problema tiene solución factible y acotada: 1-Si hay exactamente una ´única solución ´optima, debe ser una solución factible de punto-extremo. Si hay soluciones ´optimas múltiples, entonces al menos dos deben ser soluciones de punto extremo adyacentes 2- Hay un número finito de soluciones factibles de punto-extremo. 3-Si una solución factible de punto-extremo es igual o mejor (en términos de z) que todas sus soluciones factibles adyacentes, entonces es igual o mejor que todas las soluciones factibles de punto extremo, es decir, es solución óptima.

La propiedad 1 implica que la búsqueda se reduce a un número finito de soluciones y la propiedad 3 da la clave para la prueba de optimalidad. El método explota estas tres propiedades examinando solo una cantidad relativamente pequeña de soluciones factibles punto-extremo y parando tan pronto como la prueba de optimalidad se satisfaga. En cada iteración se mueve de manera eficiente de un punto extremo a otro adyacente mejor. El procedimiento puede resumirse en el esquema algorítmico de la Figura

Figura 3

Programación no lineal Como respuesta a dos de las críticas más frecuentes de la PL, a saber, la destructividad de la hipótesis de linealidad y la dificultad de definir una única función objetivo surge la Programación no lineal (PNL) y la Teoría de la Decisión Multicriterio (que no abordaremos en este capítulo). Efectivamente, un supuesto importante en PL es que todas sus funciones (objetivo y restricciones) son lineales. Aunque, en esencia, este supuesto se cumple en el caso de muchos problemas prácticos, con frecuencia no es así. Por lo que es necesario abordarlo desde la Programación No Lineal (PNL). De manera general, un problema de PNL consiste en encontrar x = (x1, x2, . . ., xn) tal que max f(x) s.a gi(x) ≤ bi, ∀i = 1, 2, . . ., m x≥0 donde f(x) y gi(x) son funciones dadas de n variables de decisión. Existen muchos tipos de problemas de PNL, en función de las características de estas funciones, por lo que se emplean varios algoritmos para resolver los distintos tipos. Para ciertos casos donde las funciones tienen formas sencillas, los problemas pueden resolverse de manera relativamente eficiente. En algunos otros casos, incluso la solución de pequeños problemas representa un verdadero reto. Cuando un problema de PNL tiene solo una o dos variables, se puede representar en forma gráfica. Si las funciones no son lineales, dibujaremos curvas en lugar de rectas, por lo que función objetivo y región factible dejaran de tener el aspecto que adquieren en la PL. La solución no tiene por qué estar en un vértice de la región factible, ni siquiera tiene porque encontrarse en la frontera de esta. Por lo que la desaparece ahora la gran simplificación que se utiliza en PL, que permite limitar la búsqueda de solución ´optima a las soluciones en los vértices. Además, en PNL un máximo local no es necesariamente un máximo global y en general, los algoritmos de PNL no pueden distinguir cuando se encuentra en un ´optimo local o en uno global. Por tanto, es crucial conocer las condiciones en las que se garantiza que un máximo local es un máximo global en la región factible. Recuerde que en Análisis Maten ático, cuando se maximiza una función ordinaria (doblemente diferenciable) de una sola variable f(x) sin restricciones, esta garantía está dada cuando.

Es decir, cuando la función es cóncava hacia abajo, o simplemente cóncava.

Tipos de problemas de programación 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. -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. Ejemplos de problemas de PNL:         

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 no restringida: problema sin restricciones, es decir, el problema se reduce a maxf(x). Si f(x) es diferenciable, la condición necesaria para que x = x∗ sea óptima es

La condición suficiente es que f(x) sea cóncava. Optimización restringida linealmente: si todas las funciones de restricciones son lineales pero la función objetivo es no lineal. Se han desarrollado extensiones del método simplex. Un caso particular, con m = 0 es aquel en que hay variables no negativas. Por ejemplo, max f(x) s.a xj ≥ 0

Entonces la condición necesaria cambiaría a:

Programación cuadrática: problema restringido linealmente con función objetivo cuadrática (contiene cuadrados de variables o/y productos de variables)

Se han desarrollado muchos algoritmos para f(x) cóncava, esta formulación surge de manera natural en muchas aplicaciones.

Programación convexa: abarca una amplia clase de problemas, entre los cuales, como casos especiales, se puede mencionar todos los tipos anteriores cuando f(x) es una función cóncava que debe maximizarse. Los supuestos son: (i) f(x) es cóncava y (ii) cada gi(x) es convexa. Estos supuestos aseguran que un máximo local es global.

Programación separable: es un caso especial de programación convexa, en donde el supuesto adicional es: todas las funciones f(x) y gi(x) son separables. Una función separable es una función en la que cada termino incluye una sola variable, por lo que la función se puede separar en una suma de funciones de variables individuales. Por ejemplo, si f(x) es una función separable, se puede expresar como:

Donde cada fj (xj) incluye solo los términos con xj. Como en el ejemplo que se muestra a continuación: f(x1, x2) = 54x1 − 9x21 + 78x2 − 13x22 es una función separable porque puede ser expresada como f(x1, x2) = f1(x1) + f2(x2) de la siguiente forma: f1(x1) = 54x1 − 9x21 y f2(x2) = 78x2 − 13x22 son cada una funciones de una sola variable. Es importante distinguir estos problemas de otros de programación convexa, pues cualquier problema de programación separable se puede aproximar muy de cerca mediante uno de programación lineal y, entonces, se puede aplicar el eficiente método simplex.

Programación no convexa: incluye todos los problemas de PNL que no satisfacen los supuestos de programación convexa. En este caso, aun cuando se tenga ´éxito en encontrar un máximo local, no hay garantía de que sea también un máximo global. Por lo tanto, no se cuenta con un algoritmo que garantice encontrar una solución óptima para todos estos problemas; sin embargo, existen algunos algoritmos bastante adecuados para encontrar máximos locales, en especial cuando las formas de las funciones no lineales no se desvían demasiado de aquellas que se supuso para programación convexa. Ciertos tipos específicos de problemas de programación no convexa se pueden resolver sin mucha dificultad métodos especiales. Programación geométrica: cuando se aplica PNL a problemas de diseño de ingeniería, muchas veces la función objetivo y las funciones de restricción toman la forma:

Donde

En tales casos, ck y akj con frecuencia representan las constantes físicas, mientras que las xj 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 en forma directa a estos problemas de programación geomé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 ck de cada función son estrictamente positivos, es decir, las funciones son polinomios positivos generalizados (ahora llamados polinomios), y la función objetivo se tiene que minimizar. El problema equivalente de programación convexa con variables de decisión y1, y2, . . ., yn se obtiene al establecer xj = eyj, j = 1, 2, . . ., n En todo el modelo original, de modo que ya se puede aplicar un algoritmo de programación convexa. Se ha desarrollado otro procedimiento de solución para resolver estos problemas de programación polinomial, al igual que para problemas de programación geométrica de otros tipos.

Programación fraccional: si la función objetivo se encuentra en la forma de una fracción, esto es, como 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-persona 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 de una cartera de inversiones (rendimiento /riesgo). Se han formulado algunos procedimientos de solución especiales para ciertas formas de f1(x) y f2(x). Cuando es posible, 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 este enfoque, suponga que f(x) es de la forma de programación fraccional lineal.

Donde c y d son vectores fila, x es un vector columna y 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

Este resultado conduce a

Que se puede resolver con el método simplex. En términos generales, se puede usar el mismo tipo de transformación para convertir un problema de programación fraccional con f1(x) cóncava, f2(x) convexa y gi(x) convexas, en un problema equivalente de programación convexa.

Problema de complementariedad: Dadas las variables w1, w2, . . ., wp y z1, z2, . . ., zp, el problema de complementariedad encuentra una solución factible para el conjunto de restricciones w = F(z), w ≥ 0, z ≥ 0

Que también satisface la llamada restricción de complementariedad, wtz = 0. Aquí, w y z son vectores columna, F es una función vectorial y el superíndice t denota la transpuesta. El problema no tiene función objetivo, de manera que, desde un punto de vista técnico, no es un problema de programación no lineal completo. Se llama problema de complementariedad por las relaciones complementarias que establecen las también conocidas como variables complementarias que wi = 0 ´o zi = 0 i = 1, 2, . . ., p. Un caso en especial importante es el problema de complementariedad lineal, donde F(z) = q + Mz, Donde q es un vector columna dado y M es una matriz dada de orden p × p. Se dispone de algoritmos eficientes para resolver este problema bajo algunos supuestos adecuados sobre las propiedades de la matriz M. Uno de estos requiere pivotear de una solución básica factible a la siguiente, en forma muy parecida a la del método simplex para programación lineal. Además de tener aplicaciones en programación no lineal, los problemas de complementariedad se utilizan en teoría de juegos, problemas de equilibrio económico y problemas de equilibrio en ingeniería.

Aplicaciones de la programación lineal y no lineal Son métodos eficientes para determinar una decisión óptima entre un gran número de decisiones posibles Es impresionante el número y la diversidad de problemas en los que se puede aplicar gracias a sus diferentes características tales como: Proporcionalidad: las variables y la función objetivo deben ser lineales (para PL). Aditividad: Es necesario que cada variable sea aditiva respecto a la variable objetivo. Divisibilidad: las soluciones no deben ser necesariamente números enteros. Optimalidad: La solución óptima (máximo o mínimo) debe ocurrir en uno de los vértices del conjunto de soluciones factibles.

Figura 4

Casos de estudio Programación lineal Método simplex

Nota: las casillas en rojo representan al elemento pivote.

Conclusión: con x1 = 15 y x2 = 25 se obtiene un máximo de 2100 unidades monetarias. Comprobando: z = 40(15) + 60(25) = 2100

Programación no lineal Método simplex mejorado o de las 2 fases

Conclusión: con x1 = 3/5 y x2 = 6/5 se minimiza hasta 3 unidades monetarias

Bibliografía Cuellar, R. C. (1996). Programacion lineal. Universidad Autonoma de Nuevo Leon, 132. Maestre, M. M. (-). Técnicas Cíasicas de Optimización. Facultad de Ciencia y Tecnología, 82.