miércoles, 30 de septiembre de 2015

Problema de complementariedad (III)

Un caso espcialmente importante es el problema de complementariedad lineal en el que
F(x) = q + Mz.

en donde q es un vector columna dado y M es una matriz p x p dada. Se dispone de algoritmos eficientes para resolver este problema bajo algunas suposiciones adecuadas 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 símplex 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.

martes, 29 de septiembre de 2015

Problema de complementariedad (II)

Aquí, w y z son vectores columna, F es una función con vlores vectoriales dada y el superíndice T denota traspuesta (véase el apéndice 3). El problema no tiene función objetivo, de manera que técnicamenta no es un problema de programación no lineal completo. Se llama problema de complementariedad por las relaciones complementarias que establecen que una de las dos

wi = 0    o zi = 0 (o ambas)    para cada i = 1, 2, ....., p


lunes, 28 de septiembre de 2015

Problema de complementariedad (I)

Cuando se estudie la programación cuadrática en la sección 14.7, se verá un ejemplo de cómo la resolución de ciertos problemas de programación no lineal se puede reducir a resolver el problema de complementariedad. Dadas las variables w1, w2,........, wp y z1, z2......., zp, el problema de complementariedad encuentra una solución factiblepara el conjunto de restricciones.

w =  F(z)        w ≤ 0,      z ≥ 0,

Que tambien satisface la restricción de complementariedad

w^Tz =0

domingo, 27 de septiembre de 2015

Tipos de problemas de programación no lineal - Programación Fraccional (II)

Cuando se puede hacer, el enfoque más directo para resolver un problema de programación fraccional es transformarlo enun problema equivalente de algún tipo estándar que disponga de un procedimiento deficiente. Para ilustar esto, supóngase que f(x) es de la forma de programa-ción fraccional lineal.
que se puede resolver con el método símplex. 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.

sábado, 26 de septiembre de 2015

Tipos de problemas de programación no lineal - Programación Fraccional (I)

Supóngase que la función objetivo se encuentra en la forma de una fracción, esto es, la razón o cociente de dos funciones.

Maximizar     f(x)  = f1(x)/f2(x)

Estos problemas de programación fraccional surgen, por ejemplo, cuando se maximiza la razón de la producción entre la horas-hombre empleadas (productividad), o la ganancia entre el capital invertido (tasa de crecimiento), o el valor esperado entre la desviación estandar de alguna medida de desempeño para una cartera de inversiones (rendimiento/riesgo). Se han formulado algunos procedimientos de solución especiales para ciertas formas de f1(x) y f2(x).

viernes, 25 de septiembre de 2015

Tipos de problemas de programación no lineal - Programación geométrica (II)

En tales casos, las ci y aij representan las constantes físicas y las xj son las variables de diseño. EStas funciones por lo general no son ni cóncavas ni convexas, con lo que no se pueden aplicar las técnicas de programación convexa. Sin embargo, existe un caso importante en el que el problema se pueda transformar en un problema de programación convexa equivalente. Este caso es aquél en el que todos los coeficientes ci en cada función son estrictamente positivos, es decir, las funciones son polinomios positivos generalizados (ahora llamados posinominales), y la función objetivo se tiene que minimizar. El problema equivalente de programación convexa con variables de decisión yi, y2,......yn se obtiene entonces al establecer.

en todo el modelo orifinal, y se puede aplicar un algoritmo de programación convexa. Se cuenta con otro procedimiento de solución para resolver estos problemas de programación posinomial, al igual que para problemas de programación geométrica de otros tipos.

jueves, 24 de septiembre de 2015

Tipos de problemas de programación no lineal - Programación geométrica (I)

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

miércoles, 23 de septiembre de 2015

Tipos de problemas de programación no lineal - Programación no convexa

La programación no convexa incluye todos los problemas de programación no lineal que no satisfacen las suposiciones 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. Así, no se tiene un algoritmo que garantice encontrar una solución óptima para todos estos problemas; pero sí existen algunos algoritmos bastantes adecuados para encontrar máximos locales, en especial cuando las formas de las funciones no lineales no se desvían demasiado de aquéllas que se supusieron para programación convexa. En la sección 14.10 se presenta un algoritmo para estos problemas.

Ciertos tipso específicos de problemas de programación no convexa se pueden resolver sin mucha dificultad mediante métodos especiales. Dos de ellos, de gran importancia, se presentarán mmás adelante.

martes, 22 de septiembre de 2015

Tipos de problemas de programación no lineal - Programación Separable

La programación separable es un caso especial de programación convexa, en donde la suposición adicional es
3. Todas la funciones f(x) y gi(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. Por ejemplo, si f(x) es una función separable, se puede expresar como
en donde cada fj(xj) incluye sólo los términos con xj. En la terminología de programación lineal (véase la sección 3.3) , los problemas de programación separable satisfacen las suposiciones de aditividad pero no las de proporcionalidad  (para funciones no lineales).

Es importante distinguir estos problemas de otros de programación convexa, ya que 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 símplex. Este enfoque se describe en la sección 14.8 (Para simplificar, se centra la atención en el caso linealmente restringido, en el que el tratamiento especial se necesita nada más para la función objetivo.)

lunes, 21 de septiembre de 2015

Tipos de problemas de programación no lineal - Programación Convexa

La programación convexa abarca una amplia clase de problemas entre los que se encuentran como casos especiales, todos los tipos anteriores cuando f(x) es cóncava. Las suposiciones son 
1. f(x) es cóncava
2. Cada una de las gi(x) son convexas.

Como se dijo al final de la sección 14.2, estas suposiciones son suficientes para asegurar que un máximo local es un máximo global. En la sección 14.6 se verá que las condiciones y suficientes para obtener tal solución óptima son una generalización natural de las condiciones que se acaban de exponer para la optimización no restringida y su extensión a la inclusión de restricciones de no negatividad. La sección 14.9 describe los enfoques algorítmicos para resolver problemas de programación convexa.

domingo, 20 de septiembre de 2015

Tipos de problemas de programación no lineal - Programación Cuadrática

DE nuevo los problemas de programación cuadrática tienen restricciones lineales, pero ahora la función objetivo f(x) debe ser cuadrática. Entonces, la única diferencia entre éstos y un programa de programación lineal es que algunos términos de la función objetivo incluyen el cuadrado de una variable o el producto de dos variables.

Se han desarrollado muchos algoritmos para este caso, con la suposición adicional de que f(x) es cóncava. La sección 14.7 presenta un algoritmo que maneja una extensión del método símplex.

La programación cuadrática es muy importante, en parte porque las formulaciones de este tipo surgen de manera natural en muchas aplicaciones. Por ejemplo, el problema de la selección de una cartera con inversiones riesgosas, descrito en la sección 14.1 se ajusta a este formato. Sin embargo, otra razón por la que es importante es que al resolver problemas generales de optimización linealmente restringida se puede obtener la solución de una sucesión de aproximaciones de programación cuadrática.

sábado, 19 de septiembre de 2015

Tipos de problemas de programación no lineal - Optimización linealmente restringida

Los problemas de optimización linealmente restringida se caracterizan por restricciones que se ajustan completamente a la programación líneal, de manera  que todas las funciones de restricción gi(x) son lineales, pero la función objetivo es no lineal. El problema se simplifica mucho si sólo se tien que tomar en cuenta una función no lineal y una región factible de programación lineal. Se han desarrollado varios algortimos especiales basados en una extensión del método símplex para analizar la función objetivo no lineal.

Un caso especial importante es la programación cuadrática.

viernes, 18 de septiembre de 2015

Tipos de problemas de programación no lineal - Optimización no restringida (II)

Cuadno f(x) es cóncava, esta condición tambien es suficiente, con lo que la obtención de x* se reduce a resolver el sistema de las n ecuaciones obtenidas al establecer las n derivadas parciales iguales a cero. Por desgracia, cuando se trata de funciones no lineales f(x), estas ecuaciones suelen ser no lineales también, en cuyo caso es poco probable que se pueda obtener analíticamente su solución simultánea. Qué se puede hacer en este caso? Las secciones 14.4 y 14.5 describen procedimientos algorítmicos de busqueda para encontrar x*, primero para n =1 y luego para n > 1. Estos procedimientos también juegan un papel importante en la solución de muchos tipos de problemas con restricciones, que se describirán en seguida. La razón es que muchos algoritmos pra problemas restringidos están construidos de forma que se adaptan a versiones no restringidas del problema en una parte de cada iteración.

Cuando una vriable xj tiene una restricción de no negatividad, xj ≥ 0, la condición necesaria (y tal vez) suficiente anterior cambi ligeramente a:

jueves, 17 de septiembre de 2015

Tipos de problemas de programación no lineal - Optimización no restringida (I)

Los problemas de optimización no restringida no tienen restricciones, por lo que la función objetivo es sencillamente

Maximizar f(x)

sobre todos los valores x = (x1, x2,.......xn). Según se repasa en el apéndice 2, la condición necesaria para que una solución específica x = x* sea óptima cuando f(x) es una función diferenciable es:

∂f/∂xj = 0 en x = x*, para j = 1,2,.....,n.

miércoles, 16 de septiembre de 2015

Tipos de problemas de programación no lineal

Los problemas de programación no lineal se presentan de muchas formas distintas. Al contrario del método simplex para programación lineal, no se dispone de un algoritmo que resuelva 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 introducirán las clases más importantes y después se describirá cómo se pueden resolver algunos de estos problemas.

martes, 15 de septiembre de 2015

Ilustración gráfica de problema de programación no lineal (VI)

Si un problema de programación no lineal no tiene restricciones, el hecho de que la función objetivo esa cóncava garantiza que un máximo local es un máximo global. (Una función objetivo convexa asegura que un mínimo local es un mínimo global). Si existen restricciones,  entonces se necesita una condición más para dar esta garantía. Esta es que la región, factible sea un conjunto convexo. Como se analiza en el ápendice 1, un conjunto convexo es un conjunto de puntos tales que, para cada par de puntos de la colección, el segmento de recta que los une está totalmente contenido en la colección. Así, la región factible en el problema de la Wyndor Glass Co. en la figura 3.3 (o la región factible para cualquier otro problema de programación lineal) es un conjunto convexo. De igual manera, la región factible de la figura 14.5 también es un conjunto convexo; esto ocurre siempre que todas las gi(x) [para las restricciones gi(x) ≤ bi] son convexas. Entonces,para garantizar que un máximo local es un máximo global en un problema de programación no lineal con restricciones gi(x) ≤ bi (i = 1, 2,......,m) y x ≥ 0, la función objetivo f(x) debe ser cóncava y cada gi(x) debe ser convexa.

lunes, 14 de septiembre de 2015

Ilustración gráfica de problema de programación no lineal (V)

Una función de este tipo cuya curvatura siempre es "hacia abajo" (o que no tiene curvatura) se llama función cóncava. De igual manera, si se sustituye ≤ por ≥, con lo que la función tiene siempre una curvatura "hacia arriba" (o no tiene curvatura), se llama función convexa. (Así, una función lineal no es tanto cóncava como convexa). En la figura 14.8 se pueden ver ejemplo de esto. Nótese que la figura 14.7 ilustra una función que no es cóncava, ni convexa pues alterna sus curvaturas hacia arriba y hacsia abajo.

Las funciones de las variables múltiples también se pueden caracterizar como cóncavas o convexas si su curvatura es siempre hacia abajo o hacia arriba. Por ejemplo, considérese una función que consiste en una suma de términos. Si todos los términos son cóncavos (se puede verificar que lo sea, con su segunda derivada cuando el término incluye nada más una de las variables), entonces la función es cóncava. De manera similar, la función es convexa i todos los términos son convexos. Estas definiciones intuitivas se fundamentan en términos precisos que, junto con un poco de profundización en los conceptos, se presentanen el apéndice I.

sábado, 12 de septiembre de 2015

Ilustración gráfica de problema de programación no lineal (IV)

En general, los algoritmos de programación no lineal no pueden distinguir entre un máximo local y un máximo global (excepto si encuentran otro máximo local mejor), por lo que es determinante conocer cuándo se garantiza que un máximo local es un máximo global en la región factible. Recuérdese que en Cálculo, cuando se maximiza una función ordinaria (doblemente diferenciable) de una sola variable f(x) sin restricciones, eta garantía está dada si

d²f/dx² ≤ para toda x

viernes, 11 de septiembre de 2015

Ilustración gráfica de problema de programación no lineal (III)

Por otro lado, sí

Z = 54x1 - 9x1² + 78x2  - 13x2²

entonces la solución óptima resulta (x1, x2) = (3,3), que se encuentra dentro de la frontera de la región factible. (SE puede comprobar que esta solución es óptimasi se usa el Cálculo para derivarla como un máximo global no restringido; como también satisface las restricciones, debe ser óptima para el problema restringido). Por lo tanto, es necesario que un algoritmo general para resolver problemas de este tipo tome en cuenta toda las soluciones en la regiónn factible y no sólo aquéllas que están sobre la frontera.

Otra complicación que surge en la programación no líneal es que un máximo local no necesariamente es un máximo global (la solución óptima global). Por ejemplo, considérese la función de una sola variable graficada en la figura 14.7. En el intervalo 0 ≤ x ≤ 5, esta función tiene tres máximos locales, x = 0, x = 2, x = 4, pero sólo uno de estos, x = 4, e un máximo global. (De igual manera, existen mínimo locales en x = 1, 3 y 5, pero sólo x = 5 es un mínimo global)

jueves, 10 de septiembre de 2015

Ilustración gráfica de problema de programación no lineal (II)

Ahora supóngase que la restricciones lineales de la sección 3.1 se conservaran sin cambio, pero que la función objetivo se hace no lineal. Por ejemplo, si


miércoles, 9 de septiembre de 2015

Ilustración gráfica de problema de programación no lineal (I)

Cuando un problema de programación no lineal tiene sólo una o dos variables, se puede representar en una gráfica en forma muy parecida al ejemplo de la Wyndor Glass Co., para programación lineal, en la sección 3.1. Se verán unos cuantos ejemplos, ya que una representación gráfica de este tipo proporciona una visión global de las propiedades de las soluciones óptima de programación lineal y no lineal. Con el fin de hacer hincapié en las diferencias se usarán algunas variaciones no lineales del problema de la Wyndor Glass Co.

La figura 14.5 muestra lo que ocurre con este problema si los únicos cambios que se hacen al modelo de la sección 3.1 son que la segunda y tercera restricciones se sustituyen por la restricción no lineal 9x1² + 5x2² ≤ 216. Compárense las figuras 14.5 y 3.3. La solución óptima sigue siendo(x1, x2) = (2,6). Además, todavía se encuentra sobre la frontera de la región factible, pero no es una solución en un vértice. La solución óptima pudo haber sino una solución factible en un vértice con una función objetivo diferente (verifíquese Z = 3x1 + x2), pero el hecho de que no necesita serlo significa que ya no se puede aprovechar la gran simplificación utilizada en programación lineal que permite limitar la búsqueda de una solución óptima nada más a la olucione factibles en los vértices.

martes, 8 de septiembre de 2015

Selección de una cartera de inversiones riesgosa (IV)

Uno de los defectos de esta formulación es que, como R(x) y V(x) son de alguna manera inconmesurables, es relativamente difícil elegir un valor apropiado de β. Entonces, en lugar de terminar el proceso con una elección de β, es común que se use programación (no lineal) paramétrica para generar la solución óptima como una función de β en un intervalo amplio de valores; el siguiente paso consiste en analizar los valores de R(x) y V(x) para estas soluciones que son óptimas para algún valor de β y después elegir la solución que dé el mejor trueque entre estas dos cantidades. Con frecuencia se hace referencia a este procedimiento como la generación de soluciones sobre la frontera eficiente de la gráica de dos dimensiones de los puntos (R(x), V(x)) para toda las x factibles. La razón es que el punto (R(x), V(x)) para una x óptima (para alguna β) se encuentra sobre la frontera (límite) de los puntos factibles. Más aún, cada punto x es eficiente, en el sentido de que ninguna otra solución factible esrá cuando menos igualmente buena con una medida (R o V) y estrictamente mejor con la otra medida (V más pequeña o R más grande).

lunes, 7 de septiembre de 2015

Selección de una cartera de inversiones riesgosa (III)

El modelo de programación no lineal completo puede ser

en donde Pj es el precio de cada acción tipo j y B es la cantidad de dinero presupuestada para la cartera. Si se hacen ciertas suposiciones sobre la función de utilidad del inversionista (medida del valor relativo para el inversionista de lo distintos rendimientos totales), se puede demostrar que una solución óptima para este modelo de programación no lineal maximiza la utilidad esperada del inversionista.

domingo, 6 de septiembre de 2015

Selección de una cartera de inversiones riesgosa (II)

Se puede formular un modelo de programación no lineal para este problema de la siguiente manera. Supóngase que se están tomando en cuenta n tipos de acciones para incluirlas en la cartera; las variables de decisión xj (j = 1,2,....., n) representan el número de acciones j que van se van a incluir. SEan μj y σjj la media y la variancia (estimadas) del rendimiento sobre cada acción del tipoj, en donde σjj mide el riesgo de estas acciones. Para i =1,2,....., n (i ≠ j), sea σij la covariancia del rendmiento sobre una acción de cada tipo i y j. (Como sería difícil estimar todas las σij, lo usual es hacer ciertes suposiciones sobre el comportamiento del mercado que permitan calcular σij directamente, a partir de σii y σjj.) Entonces, el valor esperado R(x) y la variancia V(x) del rendmiento total de la cartera completa son

sábado, 5 de septiembre de 2015

Selección de una cartera de inversiones riesgosa (I)

ES ahora una práctica común entre los administradores de grandes carteras de inversión usar, como una guía, model de computadora basados en parte en programación no lineal. Como los inversionistas se preocupan tanto por el rendimiento esperado (ganancia), como por el riesgo asociado con su inversión, la programación no lineal se usa para determinar una cartera que, con ciertas suposiciones, proporcione un trueque óptimo entre estos dos factores.


jueves, 3 de septiembre de 2015

Problema de transporte con descuentos por volumen en los precios de embarque

Como se ilustró en el ejemplo de la P & T Co., en la sección 7.1, una aplicación común del problema de transporte es determinar un plan óptimo para mandar bienes desde varios orígenes hasta varios destinos, dadas las restricciones de recursos y demanda, con el fin de minimizar el costo total de transporte. En el capítulo 7 se supuso que el costo por unidad enviada de un origen a un destino dados es fijo, independientemente de la cantidad mandada. En la realidad, este costo puede no ser fijo. A veces se dispone de descuentos por volumen para cantidades grandes, con lo que el costo marginal de mandar una unidad más puede seguir un patrón como el que se muestra en la figura 14.3. El costo que resulta al embarcar x unidades está dado entonces por una función no lineal C(x) que es una función lineal por partes con pendiente igual al costo marginal, como la que se muestra en la figura 14.4. En consecuencia, si cada combinación de origen y destino tiene una función de costos similar, es decir, si el costo de mandar xij unidades del origen i (i = 1,2,.....m) al destino j (j = 1,2,.....,m) está dado por una función no lineal Cij(xij), entonces la  función objetivo global que se va a minimizar es:


miércoles, 2 de septiembre de 2015

El problema de la mezcla de productos con elasticidad en los precios (II)

Otra razón por la que pueden surgir no linealidades en la función objetivo es que los costos marginales al producir otra unidad más de un producto dado pueden variar con el nivel de producción. Por ejemplo, el costo marginal puede decrecer cuando aumente el nivel de producción, gracias al efecto de una curva de aprendizaje (mayor eficiencia con más experiencia). Por otro lado, pueden aumentar a causa de ciertas medidas especiales, como tiempos extra o instalaciones de producción más costosas, necesarias para aumentar la producción.

La no linealidad también puede surgir en las funciones de restricción gi(x) en forma bastante parecida. Por ejemplo, si existe una restricción de presupuesto sobre el costo total de producción, la función de costo será no lineal si el costo marginal de producción varía como se acaba de describir. Para restricciones sobre otro tipo de recursos, gi(x) será no lineal siempre que el uso del recurso correspondiente no sea estrictamente proporcional a los niveles de los respectivos productos.

martes, 1 de septiembre de 2015