ejercicios programación lineal PDF

Preview

Summary

ejercicios resuelto de programacion lineal....

Description

FACULTAD DE CIENCIAS ECONÓMICAS Y EMPRESARIALES GRADO DE ECONOMÍA PROGRAMACIÓN MATEMÁTICA RELACIÓN DE PROBLEMAS resueltos. LECCIÓN 1. Epígrafes 3-4

PROBLEMA 1 Dado el problema de programación matemática: Optimizar x2 + y2 s. a (x - 1)2 + 4y2  4 (x + 1)2 + 4y2  4 resuelva las siguientes cuestiones: a) ¿Es cerrado el conjunto de oportunidades? ¿y convexo? b) Resuelva gráficamente el problema planteado indicando los máximos y los mínimos del mismo. c) ¿Son los óptimos locales encontrados globales?

Solución: a) Puesto que el dominio de la función objetivo es todo 2, el conjunto de oportunidades está formado por aquellos puntos que verifican las dos restricciones del problema. Como ambas inecuaciones incluyen la igualdad, el conjunto de oportunidades contiene a su frontera y es, por tanto, cerrado. Por otra parte, para estudiar su convexidad, podemos hacerlo analizando el carácter de la función que define cada una de las restricciones. Si calculamos sus correspondientes matrices hessianas, resultan definidas positivas, por lo que ambas funciones son convexas, y como las dos desigualdades son de menor o igual, podemos decir que el conjunto de oportunidades es convexo. Este hecho también podemos contrastarlo con la gráfica que aparece al final de este fichero. La primera restricción es el conjunto de puntos que están dentro y sobre la elipse cuyo centro es el punto (1,0) y corta al eje de abscisa en (-1,0) y (3,0). Análogamente, la segunda restricción es el recinto delimitado por una elipse con centro en el (-1,0) y corta al eje de abscisa en (1,0),(-3,0). Cada uno de estos conjuntos es un conjunto convexo y, en consecuencia, la intersección de ambos (conjunto de oportunidades) también lo es, que es la zona pintada de verde en la gráfica. b) Para resolver el problema gráficamente, hemos de pintar algunas curvas de nivel de la función objetivo y determinar la dirección de preferencia. La curva de nivel k se obtiene igualando la función objetivo a dicha constante k: x2  y2  k que es una circunferencia centrada en el punto (0,0) y de radio k (con lo cual no tiene sentido, en este problema, que la constante k sea negativa). Si hacemos k = 0, obtenemos el centro, es decir, el punto (0,0), que es admisible,y si le vamos dando valores superiores a dicha constante, obtenemos circunferencias concéntricas que van creciendo conforme el radio es mayor. Con lo cual, la función crece hacia fuera. Este hecho podemos contrastarlo calculando el gradiente de la función objetivo:

 2x  f ( x , y )    2y  Como no es constante, sustituimos en un punto cualquiera que no anule el gradiente, por ejemplo, en el (1,0) y resulta:  2  f (1,0)    0  Este vector es perpendicular a la tangente correspondiente a la curva de nivel que pasa por el punto (1,0), indicándonos que, efectivamente, la función crece cuando pasamos de una circunferencia a otra de radio superior. En consecuencia, el mínimo del problema se encuentra en el punto admisible (0,0), donde se alcanza el valor más pequeño de la función objetivo (f(0,0) = 0). Por otra parte, el máximo será el último punto en el cual una curva de nivel toca al conjunto de oportunidades, y ello se produce, de acuerdo con la gráfica, en los puntos (1,0) y (-1,0), por los cuales pasa la misma curva de nivel k =1. Por tanto, en ambos puntos el valor de la función objetivo se hace máximo e igual a 1 (f(1,0) = f(1,0) = 1). Pero, si observamos detenidamente la gráfica, podemos apreciar que también hay máximos en los puntos de corte de las dos elipses: ( x  1) 2  4 y 2  4  3  3     0, ,  0,  2 2 2  ( x  1)  4 y  4  2   Por ambos puntos, pasa la misma curva de nivel, la circunferencia: 3 x2  y2  4 cuya curvatura, en las proximidades de esos puntos de corte, queda por encima del conjunto de oportunidades. c) Para determinar si los óptimos son globales aplicamos el teorema Local-Global, el cual proporciona condiciones suficientes para que un mínimo (máximo) local sea global. Si el conjunto de oportunidades es convexo y la función objetivo es continua y convexa (cóncava), entonces todo mínimo (máximo) local es global. En nuestro caso, ya hemos visto que el conjunto de oportunidades es convexo. Por otra parte, la función objetivo es continua por ser una función polinómica y convexa (su matriz hessiana es definida positiva), luego, podemos concluir que todo mínimo local es global, pero para máximo no lo podemos asegurar. Podemos entonces aplicar el teorema de Weierstrass, que nos ofrece condiciones suficientes para la existencia de óptimos globales. Este teorema requiere que la función objetivo sea continua, y que el conjunto de oportunidades sea no vacío y compacto (cerrado y acotado). En este problema, el conjunto de oportunidades es no vacío (hay puntos en él), cerrado, puesto que incluye a su frontera (las inecuaciones contienen la igualdad) y acotado, puesto que lo podemos encerrar en una bola de radio finito. Además, la función objetivo es continua. En consecuencia, podemos afirmar que existe, al menos, un mínimo global (el punto (0,0)) y un máximo global. Los máximos globales serán los puntos (1,0) y (-1,0) ya que en estos el valor de la función es superior al alcanzado en los otros dos máximos.

CONJUNTO DE OPORTUNIDADES

CURVAS DE NIVEL

PROBLEMA 2 Dado el problema de programación matemática: Optimizar (x - 1)2 + (y - 3)2 s. a x+y3 x - y2  - 2 x  0 y  0 resuelva las siguientes cuestiones: a) ¿Es cerrado el conjunto de oportunidades? ¿y convexo? b) Resuelva gráficamente el problema planteado indicando los máximos y los mínimos del mismo. c) ¿Son los óptimos locales encontrados globales? Determine las restricciones activas. Solución: a) Al observar todas las restricciones del problema y ver que todas contienen la igualdad podemos concluir que el conjunto es cerrado, puesto que contiene a su frontera. En cambio, para ver si es convexo pasamos a pintarlo, puesto que nos basaremos en la gráfica, la cual aparece al final de este fichero. Teniendo en cuenta que nosotros pintamos sólo igualdades, la primera restricción viene delimitada por una recta, cuyos puntos de corte con los ejes son (3, 0) y (0, 3). La segunda da lugar a una parábola, cuyo vértice se encuentra en el punto (-2, 0) y cuya apertura se produce hacia el lado derecho de la gráfica. Por último, las dos últimas restricciones corresponden al primer cuadrante, donde las dos variables toman valores positivos.

La intersección de todas las restricciones da lugar al conjunto de oportunidades, correspondiendo a la zona pintada en verde en la gráfica. Podemos ver que dicho conjunto es convexo puesto que si cogemos dos puntos cualesquiera de dicho conjunto, el segmento que los une siempre va a estar dentro de dicho conjunto. b) Para resolver el problema, una vez pintado el conjunto de oportunidades, nos queda por pintar las curvas de nivel e indicar la dirección de preferencia, encontrándose el mínimo (o mínimos) global(es) del problema en aquel punto donde las curvas de nivel toquen por primera vez al conjunto de oportunidades y el máximo (o máximos) global(es) en aquel punto donde toquen al conjunto por última vez. Si observamos la función objetivo vemos que las curvas de nivel adoptarían la siguiente expresión:

(x - 1)2 + (y - 3)2 =  luego corresponderían a circunferencias centradas en el punto (1, 3) y cuyo radio iría aumentado desde el valor cero. Así, la primera curva sería el punto (1, 3), yendo las demás hacia fuera al ir aumentando el radio de las mismas, como puede verse en la gráfica. Por tanto, la primera vez que tocan las curvas al conjunto de oportunidades sería en el punto de corte superior de la recta con la parábola. Para obtener las coordenadas del mismo resolvemos el sistema: x + y =3 x - y2 = - 2

  1  21  1  21   , correspondiendo entonces el mínimo al punto  3  .  2 2   En cuanto al máximo del problema, vemos cómo la última vez que tocan las curvas de nivel al conjunto de oportunidades lo hacen en el punto (3, 0), punto de corte de la recta con el eje de abscisas, por lo tanto ese sería el máximo del problema. (Obsérvese que el punto (0,0) sería un máximo local). c) Para poder asegurar que nuestro optimo local es global, podemos seguir varios caminos: El primero, es el método gráfico, que es el antes citado, referente a la primera y última vez que las curvas de nivel tocan el conjunto de oportunidades. El segundo es utilizando el Teorema de Weierstrass, pues si este se verifica, el menor (mayor) de los minimos (máximos) locales es el mínimo (máximo) global Para utilizar este procedimiento debemos de asegurarnos de haber obtenido todos los locales. El tercero, es utilizando el Teorema Local Global. El teorema de Weierstrass nos asegura que si la función objetivo es continua y el conjunto de oportunidades es compacto (cerrado y acotado) y no vacío el problema posee un máximo y un mínimo global. En nuestro ejemplo, la función objetivo es continua porque es polinómica, y el conjunto de oportunidades es cerrado porque, como ya hemos dicho anteriormente, contiene a su frontera y es acotado, porque se puede encerrar en una bola de radio finito. Además es no vacío luego, se cumplen las condiciones de este teorema por lo que existen un mínimo global y un máximo global. Utilizando este teorema tenemos que como existe un unico mínimo local, es global (puesto que seguro existe un minimo global según Weierstrass). Respecto del máximo global, como existen dos máximos locales, el mayor de ellos es el máximo global. También podemos aplicar el teorema Local-Global, pero este sólo se verifica para mínimo, pues la función es convexa y el conjunto convexo, luego podríamos asegurar que todo mínimo local es global. En cuanto a las restricciones activas en los óptimos, vemos cómo el mínimo verifica con igualdad la primera y la segunda restricción (de hecho sus coordenadas las hemos sacado del sistema formado por esas dos primeras restricciones tomadas con igualdad), mientras que para el máximo las restricciones activas serían la primera y la cuarta.

CONJUNTO DE OPORTUNIDADES

CURVAS DE NIVEL

PROBLEMA 3 Dado el problema de programación matemática: y - (x - 1)2

Optimizar s. a

x+2y8 4 x + 9 y2  36 x0 y0 2

a) Resuelva gráficamente el problema planteado b) ¿Podemos asegurar la existencia de soluciones? c) ¿Se puede asegurar que los óptimos obtenidos son globales? d) Indique las restricciones activas en los óptimos. Solución: a) El conjunto de oportunidades está formado por los puntos que verifican todas las restricciones del problema, dado que el dominio de la función objetivo es 2. La primera restricción es un semiespacio, que corta a los ejes en los puntos (0,4) y (8,0), mientras que la segunda restricción es el recinto exterior delimitado por la elipse cuyos cortes con los ejes son (3,0), (-3,0), (0,2) y (0,-2). Las dos últimas restricciones nos sitúan en el primer cuadrante. La zona delimitada por todas ellas aparece coloreada en verde en la primera gráfica que hay al final de este fichero. En la otra gráfica se incorporan las curvas de nivel, que son parábolas de la forma: y  (x  1)2  k

las cuales tienen como vértice el punto (1, k) y están abiertas hacia arriba. A medida que le vamos dando mayores valores a k, obtenemos parábolas que están por encima. Luego, la dirección de máximo crecimiento es hacia arriba. De hecho, el gradiente de la función es:   2( x 1)   f (x , y )   1   Como no es constante, sustituimos en un punto cualquiera que no anule el gradiente, por ejemplo, en el (1, 0) y resulta:  0  f (1,0)    1  indicándonos que, efectivamente, la función crece cuando pasamos de una parábola a otra que está por encima. Luego, la primera vez que estas curvas tocan al conjunto de oportunidades lo hacen en el punto de corte de la recta (frontera de la primera restricción) con el eje de abscisa, esto es, en el punto (8,0) se alcanza un mínimo, y en él la función objetivo vale -49 (f(8,0) = -49). Por otra parte, el máximo está situado en la última parábola que toca al conjunto de oportunidades, sobre la recta (frontera de la primera restricción). b) Supongamos que no hemos resuelto el problema y queremos analizar si tiene solución o no. Para ello analicemos si podemos aplicar el teorema de Weierstrass. El conjunto de oportunidades es no vacío, puesto que hay puntos en él y cerrado, ya que todas las inecuaciones contienen la igualdad. También es acotado, puesto que podemos encerrarlo en una bola de radio finito. En cuanto a la función objetivo, se trata de una función continua por ser polinómica. En consecuencia, podemos decir que el problema tiene un máximo y un mínimo global, en el interior o en la frontera, es decir, hay solución. c) Para analizar la globalidad de los óptimos, veamos si podemos aplicar el teorema LocalGlobal. Observando la gráfica podemos concluir que el conjunto no es convexo, ya que si tomamos los puntos (0,2) y (3,0) que pertenecen al conjunto de oportunidades, el segmento que los une no está contenido en dicho conjunto. Luego no podemos aplicar el teorema, pero ello no quiere decir que los óptimos obtenidos en el apartado a) no puedan ser globales, puesto que este teorema da condiciones suficientes. No obstante, puesto que en el apartado anterior hemos comprobado que se verificaba el teorema de Weiertrass, los óptimos que hemos obtenido han de ser los que nos aseguraba este teorema y en consecuencia, podemos concluir que son globales. También podemos afirmar que el mínimo obtenido en el apartado a) es global a partir de la gráfica, puesto que no hay otro punto en el conjunto de oportunidades donde se alcance un valor más pequeño que en el punto (8,0). Análogamente, para el máximo. d) En el punto (8,0), mínimo global de nuestro problema, las restricciones activas son la primera y la tercera. En el máximo global, sólo la primera restricción es activa.

CONJUNTO DE OPORTUNIDADES

CURVAS DE NIVEL

PROBLEMA 4 Dado el problema: Optimizar (x + 2) 2 + y 2 s. a 9 (x + 2)2 + 4 (y - 3)2  36 x  -2 -3 < y  3 a) Resolverlo gráficamente. b) ¿Podemos asegurar la existencia de soluciones? c) ¿Se pueden asegurar que los óptimos obtenidos son globales? d) Señálense las restricciones activas e inactivas en los óptimos. Solución: a) Para resolver este tipo de problemas necesitamos tres elementos: el conjunto de oportunidades, el mapa de curvas de nivel y la dirección de máximo crecimiento de la función objetivo.

El conjunto de oportunidades: Puesto que el dominio o conjunto de definición de la función objetivo es todo 2, el conjunto de puntos admisibles del problema será el determinado por las restricciones: X = { ( x , y) 2 / 9 (x + 2)2 + 4 (y - 3)2  36; x  -2; y  3; -3 < y } La primera restricción viene delimitada por una elipse, 9 (x + 2)2 + 4 (y - 3)2  36  9 (x + 2)2/36 +4 (y - 3)2 /36 =1  (x + 2)2/4 + (y - 3)2 /9 =1 de centro (-2, 3); semieje de abscisa rx = 2; semieje en ordenadas ry = 3. Así, la restricción 9 (x + 2)2 + 4 (y - 3)2  36 define la parte de dentro de la elipse. La segunda y tercera son semiespacios cerrados y la última un semiespacio abierto. La intersección de todas da lugar a la zona pintada en verde en la figura 1. Mapas de curvas de nivel: Las curvas de nivel de la función objetivo son circunferencias centradas en el punto (-2, 0) y radio k ( obsérvese que, por este motivo, no tiene sentido, en este problema, que la constante k sea negativa): (x + 2) 2 + y 2 = k2 Le damos valores a la constante k = 0, 1, 3, 13 ,..., y así obtenemos el mapa de curvas de nivel que dibujamos sobre el conjunto de oportunidades en la figura 2.

Figura 1.- Conjunto de oportunidades.

Figura 2.- Curvas de nivel. Dirección de máximo crecimiento: Calculemos el vector gradiente de la función objetivo  2( x  2)  F ( x , y )     2y  Como podemos observar nos da un vector de componentes no constantes, por tanto, tendremos que sustituir uno o varios puntos cualesquiera donde no se anule dicho gradiente; por ejemplo:

F (-2,1) = (0, 2)t donde la dirección dada por el vector (0, 2) dibujada a partir del punto (-2,1) es perpendicular a la tangente correspondiente a la curva de nivel que pasa por el punto (-2,1). Se observa que, al seguir la dirección de dicho gradiente, se pasa a una curva de nivel exterior. Por tanto, la función crece hacia fuera.

Además, hay que tener en cuenta que las curvas de nivel son circunferencias concéntricas, y éstas tienen su máximo crecimiento cuanto mayor sea el radio. Si nos fijamos en la figura 2, el conjunto de oportunidades se encuentra a la derecha del centro de las circunferencias, razón por la que el primer punto de X que es intersecado por una curva de nivel, el (-2, 0), es un mínimo, mientras que el último punto de X en tener una intersección no vacía con una curva de nivel es el punto de corte de la recta y = 3 con la elipse 9 (x + 2)2 + 4 (y - 3)2 = 36. Resolviendo el sistema, obtenemos que las coordenadas del máximo del problema son (0, 3). b) ¿Podemos asegurar la existencia de soluciones?

Desde el apartado anterior, podemos contestar a esta cuestión que sí, pero supongamos que no lo hemos resuelto gráficamente. Entonces, existe un teorema, el de Weierstrass, que establece las condiciones suficientes para poder asegurar si un problema posee solución. Dicho teorema afirma que si la función objetivo es continua y, si el conjunto de oportunidades X es compacto (o sea, cerrado y acotado) y no vacío, entonces podemos asegurar la existencia de, al menos, un máximo y mínimo globales para el problema. En nuestro caso: -La función objetivo es continua, por ser polinómica. -¿Es el conjunto X cerrado y acotado?: en la figura 1 se puede observar que el conjunto X es cerrado porque contiene a su frontera. Nótese que, necesitamos dibujar el conjunto, ya que a pesar de haber una restricción que no tiene el signo de igualdad, y > -3, el conjunto sí es cerrado. Respecto a si es acotado, en este ejercicio podemos asegurar que sí lo es sin necesidad de dibujar X; ya que la restricción 9 (x + 2)2 + 4 (y - 3)2  36 define la parte de dentro de una elipse, la cual siempre es acotada. Además, si una restricción determina un conjunto acotado, obviamente, al intersecarlo con más restricciones, con mayor motivo seguirá siendo acotado. No obstante, lo podemos comprobar mediante la figura 1 y además vemos que no es vacío. Al verificar que se cumplen todas las hipótesis del teorema de Weierstrass, podemos afirmar la existencia de, al menos, un máximo y un mínimo globales. c) ¿Se pueden asegurar que los óptimos obtenidos son globales?

En el apartado anterior hemos visto que los puntos obtenidos son globales. Pero supongamos que no hemos aplicado Weiertrass o que no se verificase. Entonces utilizaremos el teorema LocalGlobal, el cual va a darnos condiciones suficientes para que un óptimo local obtenido sea global. El teorema afirma que si la función objetivo F(x, y) es continua en X, siendo éste un conjunto convexo. Entonces, si F(x, y) es convexa en dicho conjunto, todo mínimo local es global; de igual forma, si F(x, y) es cóncava en dicho conjunto, todo máximo local es global. ¿Es convexo X?: al estar definido nuestro problema en el espacio vectorial 2, podemos comprobar la definición de conjunto convexo en la figura 1, dibujando un segmento que una dos puntos de X que, al estar contenido en dicho conjunto, podemos asegurar que el conjunto de oportunidades es convexo. En cuanto a la función objetivo, F(x, y) = (x + 2) 2 + y 2 es continua ya que es polinómica. Para comprobar si es cóncava o convexa, aplicamos el criterio basado en el estudio de su matriz hessiana:  2 0 H F(x, y) =    0 2 Al ser esta matriz definida positiva, la función es convexa estricta, por lo se puede asegurar que todo mínimo local es global. Respecto a los máximo, no podemos afirmar nada. Aunque sabemos que son globales por Weierstrass.

d) Señálense las restricciones activas e inactivas en los óptimos.

En el mínimo, (-2, 0), son activas la elipse y el semiespacio x  -2; en el punto máximo (0, 3) lo son la elipse y el semiespacio y  3. Cabe destacar que si suprimimos...