´ MATEMATICAS II

Grupo M

1

APELLIDOS:

NOMBRE:

Considera el problema Max. 3x + 2y + z s.a 2x2 + y 2 + z  10 x +y +z 1 x  0, z 0 1. Escribe el conjunto de oportunidades y razona si es compacto. 2. ¿Podemos asegurar que el problema tiene soluci´on ´optima? 3. Estudia si la soluci´on ( 1, 1, 1) es factible y, si lo es, si es interior o de frontera. 4. Transforma el problema para que tenga restricciones de igualdad y variables no negativas.

1. S = {(x, y, z) 2 IR3 | 2x2 + y 2 + z  10, x + y + z

1, x  0, z

S es cerrado porque est´a definido por restricciones de  y continuas (son continuas porque son polinomios).

0}.

a partir de funciones

S est´a acotado porque si (x, y, z) 2 S, entonces se cumple que 3  x  0,

4  y  4,

0  z  10.

Como S es cerrado y acotado, es compacto. (Algunos hab´eis puesto cotas falsas, como y 1, x 0, etc. Notad que de la segunda restricci´ on no se puede extraer ninguna cota.) 2. Podemos asegurar que hay soluci´on ´optima por el teorema de Weierstrass. Para ello hemos de comprobar tres cosas: (a) La funci´on objetivo es continua (porque es un polinomio). (b) El conjunto de oportunidades es compacto (lo hemos visto en la pregunta anterior). (c) El conjunto de oportunidades no es vac´ıo, porque, por ejemplo, ( 1, 1, 1) 2 S. 3. Vemos que 2( 1)2 + 12 + 1 = 3 < 10,

1 + 1 + 1 = 1,

1 < 0,

1 > 0,

luego la soluci´on dada cumple todas las restricciones y satura una de ellas (la segunda). Por lo tanto, es una soluci´on factible de frontera.

4. Introducimos las variables de holgura: Max. 3x + 2y + z s.a 2x2 + y 2 + z + s = 10 x +y +z t=1 x  0, z, s, t 0 Hacemos los cambios x = Max. s.a

x0 , y = y1

y2 :

3x0 + 2y1 2y2 + z 2x20 + (y1 y2 )2 + z + s = 10 x0 + y1 y2 + z t = 1 x0 , y1 , y2 , z, s, t 0

´ MATEMATICAS II

Grupo M

2

APELLIDOS:

NOMBRE:

¿Puedes razonar si alguno de los conjuntos siguientes es convexo? S = {(x, y, z) 2 IR3 | x

5y + 2z  5, 5x + 8y + xy + xz

2x2

y2

z2

T = {(x, y, z) 2 IR3 | x

5y + 2z  5, 5x + 8y + xy + xz

2x2

y2

z 2  3}.

3},

S = A \ B, donde A = {(x, y, z) 2 IR3 | x 5y + 2z  5}, B = {(x, y, z) 2 IR3 | 5x + 8y + xy + xz

2x2

y2

z2

3}.

El conjunto A es convexo porque es un semiespacio (ya que la funci´on que lo define es lineal). Como B est´a definido por una restricci´ on de , ser´a convexo si la funci´on 2x2

f (x, y, z) = 5x + 8y + xy + xz

y2

z2

es c´oncava. Para estudiarlo calculamos su hessiana: @f =5+y+z @x

4x,

@f =8+x @y 0

Hf = B @

|Hf | =

4 1 1

1 2 0

16 + 2 + 2 =

@f =x @z

2y,

2z,

1

1 0 C A 2

12 6= 0.

Como el determinante no es 0, basta calcular los menores principales conducentes: H1 =

4 < 0,

H12 =

2 1

1 = 3 > 0, 2

H123 =

12 < 0.

Como los menores alternan en signo empezando en negativo, el criterio de Jacobi nos da que la funci´on f es c´oncava, luego el conjunto B es convexo, y S es convexo por ser interseci´on de convexos. No podemos asegurar que T sea convexo porque, razonando como antes, tendr´ıamos que estudiar la convexidad del conjunto B = {(x, y, z) 2 IR3 | 5x + 8y + xy + xz

2x2

y2

z 2  3},

y sabemos que ser´a convexo si la funci´on que lo define es convexa, pero hemos visto que es c´oncava, luego no podemos asegurar que B sea convexo, ni T tampoco.

´ MATEMATICAS II

Grupo M

APELLIDOS:

8-3-11 Ia NOMBRE:

1. Resuelve con LINGO el problema siguiente: Max. 1000 x2 2y 2 z 2 s.a 5x + 3y + 2z  17 x + 3y + z 10 x, y, z 0 enteras 2. (0.4 ptos.) Resuelve el problema anterior por el m´etodo de ramificaci´ on y acotaci´on usando LINGO para resolver los problemas intermedios. Escribe el ´arbol correspondiente y razona por qu´e termina cada rama. En caso de que puedas ramificar varias variables, elige la menor en orden alfab´etico y, en caso de que puedas ramificar varios nodos, elige el de mejor valor de la funci´on objetivo. 3. Considera el problema siguiente: Min. x y + z s.a y 3 + 3z  10 x + y + 2z  2 x2 + z  20 x  0 y, z 0 (a) (0.5 ptos.) Enuncia el teorema de Weierstrass y estudia si se puede aplicar al problema anterior. ¿Qu´e conclusi´ on obtienes? (b) (0.1 ptos.) Estudia si la soluci´on ( 4, 1, 0) es factible y, si lo es, si es interior o de frontera. Justifica la respuesta. (c) (0.1 ptos.) Razona que el valor ´optimo de la funci´on objetivo es negativo.

4. (0.2 ptos.) Di de qu´e dos tipos puede ser un problema que no tenga soluci´on ´optima, explica en qu´e consiste cada uno de ellos y pon un ejemplo de problema que est´e en uno de los dos casos. 5. (0.5 ptos.) Comprueba si el problema siguiente satisface las hip´otesis del teorema local-global. En caso afirmativo, ¿cu´al es la conclusi´ on? Max. x + 3y + 2z s.a 2x2 + y 2 + z 2 + 2yz  10 y 0, z  0 6. (0.2 ptos.) Transforma el problema anterior para que la restricci´ on sea de igualdad y todas las variables sean no negativas.

2.

y  2 (1,2,3) F = 982 x  1 (1,2.45,1.63) F = 984.27 y

(1.36,2.36,1.52) F = 984.57

@ x @ 2

@ @ 3 (0.5,3,0.5)

F = 981.5

Infactible

De los tres nodos finales, el de arriba termina porque la soluci´on ya es entera, el segundo termina porque la soluci´on es peor que la de arriba, que ya es entera, y el tercero termina porque corresponde a un problema infactible. As´ı pues, la soluci´on ´optima es (x, y, z) = (1, 2, 3) con F = 982. 3 (a) El teorema de Weierstrass afirma que un problema de programaci´ on no lineal cuya funci´on objetivo sea continua y su conjunto de oportunidades sea compacto y no vac´ıo tiene un m´aximo y un m´ınimo global. En el problema dado, la funci´on objetivo es continua porque es un polinomio, el conjunto de oportunidades S = {(x, y, z) 2 IR3 | y 3 + 3z  10, x + y + 2z  2, x2 + z  20, x  0, y

0, z

0}

es cerrado porque est´a definido por restricciones de  y a partir de funciones que son continuas por ser polinomios, y es acotado porque todo (x, y, z) 2 S cumple 5x0

0y3

0  z  4.

Como es cerrado y acotado es compacto, y adem´as es no vac´ıo, porque, por ejemplo, (0, 0, 0) 2 S. Por lo tanto, el teorema de Weierstrass es aplicable al problema, y la conclusi´ on es que tiene un m´ınimo global. 3 (b) Vemos que 13 + 3 · 0 = 1 < 10,

4+1+2·0= 4 < 0,

1 < 2,

1 > 0,

( 4)2 + 0 = 16 < 20,

0=0

Por lo tanto, la soluci´on es factible, ya que cumple todas las restricciones, y es de frontera, porque satura una de ellas (z 0). 3 (c) La soluci´on ( 4, 1, 0) es factible, y la funci´on objetivo vale en ella f ( 4, 1, 0) = 5. La soluci´on ´optima es la mejor soluci´on factible, luego ser´a ´esta u otra mejor, en la que la funci´on objetivo ser´a menor que 5. En cualquier caso, el valor ´optimo ser´a negativo. 4 Un problema sin soluci´on ´optima puede ser infactible o no acotado. Ser´a infactible si no tiene soluciones factibles, y ser´a no acotado si toda soluci´on factible puede ser mejorada

por otra. Un ejemplo de problema infactible es Max. x + y s.a x 3 x1 5. El problema ha de cumplir que la funci´on objetivo sea c´oncava (y lo es, porque es lineal) y que el conjunto de oportunidades S = {(x, y, z) 2 IR3 | 2x2 + y 2 + z 2 + 2yz  10, y

0, z  0}

sea convexo. Para estudiar si lo es lo descomponemos como S = A \ B \ C, donde A = {(x, y, z) 2 IR3 | 2x2 + y 2 + z 2 + 2yz  10} B = {(x, y, z) 2 IR3 | y

0},

C = {(x, y, z) 2 IR3 | z  0}.

Vemos que B y C son convexos porque son semiespacios. Para que A sea convexo basta con que la funci´on f (x, y, z) = 2x2 + y 2 + z 2 + 2yz sea convexa. Estudiamos si lo es mediante la regla de Jacobi. Calculamos la hessiana de f : @f = 4x, @x

@f = 2y + 2z, @y

luego

0

@f = 2z + 2y, @z 1

4 0 0 C Hf = B @ 0 2 2 A 0 2 2

Como |Hf | = 0, hemos de calcular todos los menores principales: H1 = 4, H2 = 2, H3 = 2, H12 =

4 0 = 8, 0 2

H13 =

4 0 = 8, 0 2

H23 =

2 2 = 0, 2 2

H123 = 0. Como son todos mayores o iguales que 0, la funci´on f es convexa, el conjunto A es convexo y S es convexo por ser intersecci´ on de convexos. As´ı pues, el problema satisace las hip´otesis del teorema local-global. La conclusi´ on es que, si tiene un m´aximo local, ser´a de hecho un m´aximo global. 5. Introducimos la variable de holgura s y hacemos los cambios de variable x = x1 x2 , z = z0 : Max. x + 3y + 2z Max. x1 x2 + 3y 2z0 s.a 2x2 + y 2 + z 2 + 2yz + s = 10 ) s.a 2(x1 x2 )2 + y 2 + z02 y 0, z  0, s 0 x1 , x2 , y, z0 , s 0

2yz0 + s = 10

´ MATEMATICAS II

Grupo M

8-3-11 Ib

APELLIDOS:

NOMBRE:

1. Resuelve con LINGO el problema siguiente: Min. 2x2 + 2y 2 + z s.a 10x + 3y + 2z  23 x + 2y + 3z 13 x, y, z 0 enteras 2. (0.4 ptos.) Resuelve el problema anterior por el m´etodo de ramificaci´ on y acotaci´on usando LINGO para resolver los problemas intermedios. Escribe el ´arbol correspondiente y razona por qu´e termina cada rama. En caso de que puedas ramificar varias variables, elige la menor en orden alfab´etico y, en caso de que puedas ramificar varios nodos, elige el de mejor valor de la funci´on objetivo. 3. (0.5 ptos.) Comprueba si el problema siguiente satisface las hip´otesis del teorema local-global. En caso afirmativo ¿cu´al es la conclusi´ on? Min. x + 2y + z s.a 2xy 2x2 y 2 x 0, y  0

z2

20y

10

4. (0.2 ptos.) Transforma el problema anterior para que la restricci´ on sea de igualdad y todas las variables sean no negativas. 5. Considera el problema siguiente: Min. x + y s.a x3 + y  25 x4 + 2y 16 x2 + 3y  20 y 0 (a) (0.5 ptos.) Enuncia el teorema de Weierstrass y estudia si se puede aplicar al problema anterior. ¿Qu´e conclusi´ on obtienes? (b) (0.1 ptos.) Estudia si la soluci´on (2, 1) es factible y, si lo es, si es interior o de frontera. Justifica la respuesta. (c) (0.1 ptos.) Razona que el valor ´optimo de la funci´on objetivo es menor o igual que 3.

6. (0.2 ptos.) Di de qu´e dos tipos puede ser un problema que no tenga soluci´on ´optima, explica en qu´e consiste cada uno de ellos y pon un ejemplo de problema que est´e en uno de los dos casos.

z  4 Infactible

2.

y  0 (0,0,4.3) F = 4.3 @ z @ 5 (0,0,5) F=5 (0,0.16,4.22) F = 4.27 x0 @ y 1@ (0,1,3.6) F = 5.6 (0.08,0.16,4.19) F = 4.26 @ x 1@

(1,0.16,3.8) F = 5.9

De los cuatro nodos finales, el de m´as arriba termina porque el problema es infactible, el siguiente termina porque la soluci´on es entera, y los otros dos terminan porque corresponden a soluciones peores que la soluci´on entera que ya hemos encontrado. Por lo tanto, la soluci´on ´optima es (x, y, z) = (0, 0, 5) con F = 5. 3. Hemos de comprobar que la funci´on objetivo es convexa (y lo es, porque es lineal) y que el conjunto de oportunidades S = {(x, y, z) 2 IR3 | 2xy

2x2

y2

z2

20y

0, y  0}

10, x

sea convexo. Para estudiar si lo es lo descomponemos como S = A \ B \ C, donde A = {(x, y, z) 2 IR3 | 2xy B = {(x, y, z) 2 IR3 | x

2x2

y2

z2

20y

10}

C = {(x, y, z) 2 IR3 | y  0}.

0},

Vemos que B y C son convexos porque son semiespacios. Para que A sea convexo basta con que la funci´on f (x, y, z) = 2xy 2x2 y 2 z 2 20y sea c´oncava. Estudiamos si lo es mediante la regla de Jacobi. Calculamos la hessiana: @f = 2y @x

@f = 2x @y

4x,

0

Como |Hf | = H1 =

Hf = B @

4 2 0

2y

20,

2 2 0

0 0 C A 2

@f = @z

2z

1

8 6= 0, basta calcular los menores principales conducentes: 4 < 0,

H12 =

4 2

2 = 4 > 0, 2

H123 =

8 < 0.

Como alternan en signo empezando en negativo, la funci´on f es c´oncava, luego el conjunto A es convexo, luego S es convexo por ser intersecci´ on de convexos. As´ı pues, el problema satisface las hip´otesis del teorema local-global. La conclusi´ on es que si tiene un m´ınimo local, ser´a de hecho un m´ınimo global. 4. Introducimos la variable de holgura s y hacemos los cambios de variable y = z = z1 z2 : Min. x + 2y + z s.a 2xy 2x2 y 2 z 2 20y s = 10 x 0, y  0, s 0

y0 ,

Min. x 2y0 + z1 z2 s.a 2xy0 2x2 y02 (z1 ) x, y0 , z1 , z2 , s 0.

z2 )2

20y0

s = 10

5. (a) El teorema de Weierstrass afirma que un problema de programaci´ on no lineal cuya funci´on objetivo sea continua y su conjunto de oportunidades sea compacto y no vac´ıo tiene un m´aximo y un m´ınimo global. En el problema dado, la funci´on objetivo es continua porque es un polinomio, el conjunto de oportunidades S = {(x, y) 2 IR3 | x3 + y  25 x4 + 2y

16, x2 + 3y  20, y

0}

es cerrado porque est´a definido por restricciones de  y a partir de funciones que son continuas por ser polinomios, y es acotado porque todo (x, y) 2 S cumple 5  x  5,

0  y  7.

Como es cerrado y acotado es compacto, y adem´as es no vac´ıo, porque, por ejemplo, (2, 1) 2 S. Por lo tanto, el teorema de Weierstrass se puede aplicar al problema, y la conclusi´ on es que ´este tiene un m´ınimo global. 3. (b) Se cumple que 23 + 1 = 9 < 25,

24 + 2 · 1 = 17 > 16,

22 + 3 · 1 = 7 < 20,

1 > 0,

luego (2, 1) es una soluci´on factible, porque cumple todas las restricciones, y es interior, porque no satura ninguna de ellas. 3. (c) La soluci´on (2, 1) es factible, y en ella la funci´on objetivo vale f (2, 1) = 3. La soluci´on ´optima es la mejor soluci´on factible, luego ser´a ´esta (con funci´on objetivo igual a 3), u otra mejor (en la que la funci´on objetivo ser´a menor que 3). En cualquier caso, el valor ´optimo de la funci´on objetivo ser´a  3.

6. Un problema sin soluci´on ´optima puede ser infactible o no acotado. Ser´a infactible si no tiene soluciones factibles, y ser´a no acotado si toda soluci´on factible puede ser mejorada por otra. Un ejemplo de problema no acotado es Max. x + y s.a x 3

´ MATEMATICAS II

Grupo M

10-3-11 Ia

APELLIDOS:

NOMBRE:

1. Resuelve con LINGO el problema siguiente: Min. 100 7x + 9y + 5z s.a 3x2 + 2xy + 3y 2 + z 2  80 x + 4y + 5z 7 x, y, z 0 enteras 2. (0.4 ptos.) Resuelve el problema anterior por el m´etodo de ramificaci´ on y acotaci´on usando LINGO para resolver los problemas intermedios. Escribe el ´arbol correspondiente y razona por qu´e termina cada rama. En caso de que puedas ramificar varias variables, elige la menor en orden alfab´etico y, en caso de que puedas ramificar varios nodos, elige el de mejor valor de la funci´on objetivo. 3. (0.5 ptos.) Razona si el teorema local-global se puede aplicar o no a los problemas siguientes: Min. 3x y + z s.a 50x + xy xz + 2yz x + y + 3z = 10

2

2x

y

2

z

2

10

Min. 50x + xy xz + 2yz s.a x + y + 3z  10 3x y + z 4 x, y, z 0

2x2

En caso de que se pueda aplicar, ¿nos asegura esto que el problema tenga ´optimo global? 4. (0.1 ptos.) Para cada problema de la pregunta anterior, razona si (2, 1, 0) es o no una soluci´on factible. En caso de que sea factible razona si es interior o de frontera. 5. Considera el problema siguiente: Max. 3x + 2y + 5z s.a x2 + y 3 + z 4  10 x+y+z 1 y 0, z  0

(a) (0.5 ptos.) Enumera las condiciones que ha de cumplir para que se le pueda aplicar el teorema de Weierstrass y comprueba si se cumplen para el problema dado. Si es as´ı, ¿qu´e podemos afirmar sobre el mismo? (b) (0.1 ptos.) Sabiendo que el valor ´optimo de la funci´on objetivo es 11.04, en caso de a˜ nadir como nueva restricci´ on x + z 3, ¿el nuevo valor ´optimo podr´ıa ser 11.05? (c) (0.2 ptos.) Transforma el problema para que tenga restricciones de igualdad y variables no negativas. 6. (0.2 ptos.) Di lo que es un problema infactible y lo que es un problema no acotado. A˜ nade una restricci´ on al problema de la pregunta anterior para que pase a ser de uno de estos dos tipos (di de cu´al).

y2

z2

x  4 (4,0.75,0) F = 78.7

2.

z  0 (4.9,0.5,0) F = 69.75 @ x 5@ Infactible (5,0,0.4) F = 67 x5 @ z 1@ (5,0,1) F=70 (5.15,0,0.3) F = 65.7 @ x 6@ Infactible

De los cuatro nodos finales, el de m´as arriba termina porque es peor que el tercero, en el que la soluci´on ya es entera, el segundo y el cuarto terminan porque corresponden a problemas infactibles, y el tercero termina porque la soluci´on es entera. Por lo tanto, la soluci´on ´optima es (x, y, z) = (5, 0, 1) con F = 70. 3. Para el primer problema: la funci´on objetivo ha de ser convexa, y lo es porque es lineal, y el conjunto de oportunidades S = {(x, y, z) 2 IR3 | 50x + xy

xz + 2yz

2x2

y2

z2

10, x + y + 3z = 10}

ha de ser convexo. Para estudiar si lo es lo descomponemos como S = A \ B, donde A = {(x, y, z) 2 IR3 | 50x + xy

2x2

xz + 2yz

y2

z2

10},

B = {(x, y, z) 2 IR3 | x + y + 3z = 10}. Vemos que B es convexo porque es un semiespacio. Para que A sea convexo basta con que la funci´on f (x, y, z) = 50x + xy xz + 2yz 2x2 y 2 z 2 sea c´oncava. Estudiamos si lo es mediante la regla de Jacobi. Calculamos la hessiana: @f = 50 + y @x

z

@f = x + 2z @y

4x,

0

4 1 1

Hf = B @

1 2 2

@f = @z

2y,

x + 2y

2z

1

1 2 C A 2

Como |Hf | = 0, hemos de calcular todos los menores principales: H1 = H12 =

4 1

1 =7 2

4  0, 0,

H13 =

H2 = 4 1

2  0, 1 =7 2

H3 = 0,

2  0,

H23 =

2 2

2 =0 2

0,

H123 = 0  0 Como los menores de cada orden alternan en signo empezando en negativo, la funci´on f es c´oncava, luego el conjunto A es convexo, luego S es convexo por ser intersecci´ on de convexos. Ahora vemos que al segundo problema no se le puede aplicar el teorema local-global, pues la funci´on objetivo tendr´ıa que ser convexa, y acabamos de ver que es c´oncava.

En el caso del primer problema, en el que s´ı que se puede aplicar el teorema, esto no nos asegura que tenga ´optimo global, sino u ´nicamente que, en caso de tener un ´optimo local, ser´a de hecho un ´optimo global. 4. La soluci´on (2, 1, 0) es infactible para el primer problema, pues no cumple la segunda restricci´ on: 2 + 1 + 3 · 0 = 3 6= 10. Para el segundo tenemos que 2 + 1 + 3 · 0 = 3 < 10,

3·2

1 + 0 = 5 > 4,

2 > 0,

1 > 0,

0 = 0,

luego se trata de una soluci´on factible (porque cumple todas las restricciones) y de frontera (porque satura una de ellas, z 0). 5. (a) El problema ha de cumplir: 1. La funci´on objetivo ha de ser continua, y en este caso lo es porque es un polinomio. 2. El conjunto de oportunidades: S = {(x, y, z) 2 IR3 | x2 + y 3 + z 4  10, x + y + z

1, y

0, z  0}

ha de ser compacto, es decir, cerrado y acotado. En este caso es cerrado porque est´a definido por restricciones de funciones que son continuas porque son polinomios.

y  a partir de

Tambi´en es acotado, pues todo (x, y, z) 2 S cumple: 4  x  4,

0  y  3,

2z0

3. El conjunto de oportunidades ha de ser no vac´ıo, y esto se cumple porque, por ejemplo, (0, 1, 0) 2 S. As´ı pues, el problema cumple las hip´otesis del teorema de Weierstrass, y la conclusi´ on es que tiene un m´aximo global. 5. (b) Al a˜ nadir una restricci´ on, la nueva soluci´on ´optima ser´a igual o peor que la soluci´on del problema original, luego no puede ser 11.05, que ser´ıa un valor mejor, ya que el problema es de maximizar. 5. (c) Introducimos variables de holgura s y t y hacemos los cambios de variable x = x1 x2 , z = z0 : Max. 3x + 2y + 5z Max. 3x1 3x2 + 2y 5z0 s.a x2 + y 3 + z 4 + s = 10 s.a (x1 x2 )2 + y 3 + z04 + s = 10 ) x+y+z t=1 x1 x2 + y z0 t = 1 y 0, z  0, s, t 0 x1 , x2 , y, z0 , s, t 0 6. Un problema es infactible si no tiene soluciones factibles. Un problema es no acotado si toda soluci´on factible puede ser mejorada por otra. Si al problema anterior a˜ nadimos la restricci´ on z 1 se vuelve infactible, pues ninguna soluci´on puede cumplir a la vez las restricciones z  0 y z 1.

´ MATEMATICAS II

Grupo M

APELLIDOS:

10-3-11 Ib NOMBRE:

1. Resuelve con LINGO el problema siguiente: Max. xy 2 z + 2x s.a x + 3y + z  20 2x + 5y + 3z 39 x, y, z 0 enteras 2. (0.4 ptos.) Resuelve el problema anterior por el m´etodo de ramificaci´ on y acotaci´on usando LINGO para resolver los problemas intermedios. Escribe el ´arbol correspondiente y razona por qu´e termina cada rama. En caso de que puedas ramificar varias variables, elige la menor en orden alfab´etico y, en caso de que puedas ramificar varios nodos, elige el de mejor valor de la funci´on objetivo. 3. (0.5 ptos.) Enuncia el teorema local-global y razona si se puede aplicar al problema siguiente: Min. x2 + y 2 + z 2 s.a 5xy x2 3y 2 2z 2 5 z  10 x 0, y  0 4. (0.2 ptos.) Transforma el problema de la pregunta anterior para que tenga restricciones de igualdad y variables no negativas. 5. Considera los problemas siguientes: Max. x + y 2 + z s.a x2 + 2y  10 z 4  20 y 0

Min. x + y 2 + z s.a x3 + 2y  10 z 4  20 y, z 0

(a) (0.3 ptos.) Escribe sus conjuntos de oportunidades y razona si son compactos. (b) (0.2 ptos.) Razona que al menos uno de los problemas tiene ´optimo global. (c) (0.1 ptos.) Razona si la soluci´on ( 1 000, 1, 1) es factible o infactible para cada uno de los problemas y, en caso de que sea factible, si es interior o de frontera. (d) (0.2 ptos.) Explica lo que es un problema infactible y un problema no acotado. ¿Alguno de los dos problemas del enunciado es de uno de estos tipos? 6. (0.1 ptos.) Si (1, 2, 1) y (0, 2, 3) son soluciones factibles de un problema de maximizar y el valor en ellas de la funci´on objetivo es f (1, 2, 1) = 10, f (0, 2, 3) = 15, ¿pueden ser las dos ´optimos globales del problema? ¿Qu´e podemos decir sobre el valor ´optimo de la funci´on objetivo?

y  3 (5,3,6) F = 280

2. (5.13,3.3,4.9) F = 287.91

x  5 (5,3,3.5) F = 287.77 @ y 4@ (4,4,3.9) F = 264 @ x @ 6

y3

(6,3,5) F = 282

(6,3.1,4.6) F = 283.01 @ y

4@ Infactible

De los cuatro nodos finales, el primero y el tercero (contados desde arriba) terminan porque corresponden a soluciones enteras, el segundo termina porque es peor que el primero, que corresponde a una soluci´on entera, y el cuarto porque el problema es infactible. Por lo tanto, la soluci´on ´optima es la mejor de las dos soluciones enteras encontradas: (x, y, z) = (6, 3, 5) con F = 282. 3. El teorema local-global afirma que si, en un problema de programaci´ on no lineal con conjunto de oportunidades convexo, si la funci´on objetivo es c´oncava todos los m´aximos locales son globales, mientras que si la funci´on objetivo es convexa, todos los m´ınimos locales son globales. En el problema dado, la funci´on objetivo ha de ser convexa. Para estudiar si lo es, calculamos su hessiana: @f = 2x, @x

@f = 2y, @y

@f = 2z, @z

0

1

2 0 0 B Hf = @ 0 2 0 C A 0 0 2

Como es diagonal y la diagonal es positiva, la funci´on objetivo es convexa. El conjunto de oportunidades es S = {(x, y, z) 2 IR3 | 5xy

x2

3y 2

2z 2

5, z  10, x

0, y  0}.

Para ver si es convexo lo descomponemos como S = A \ B \ C \ D, donde A = {(x, y, z) 2 IR3 | 5xy

x2

3y 2

C = {(x, y, z) 2 IR3 | x

2z 2 0},

5},

B = {(x, y, z) 2 IR3 | z  10},

D = {(x, y, z) 2 IR3 | y  0}.

Vemos que B, C y D son convexos porque son semiespacios. Para que A sea convexo basta con que la funci´on g(x, y, z) = 5xy x2 3y 2 2z 2 sea c´oncava. Para estudiar si lo es calculamos su hessiana: @g = 5y @x

2x,

@g = 5x @y

6y,

@g = @z

4z

0

Hg = B @

2 5 0

5 6 0

1

0 0 C A 4

Como |Hg| = 52 6= 0, basta calcular los menores principales conducentes: H1 =

2,

H12 =

2 5

5 = 6

13,

H123 = 52.

Para que g fuera c´oncava, los signos habr´ıan tenido que ser H1 < 0, H12 > 0, H123 < 0. Como no es as´ı, la funci´on g no es c´oncava, y no podemos asegurar que el conjunto A sea convexo, ni S tampco. As´ı pues, no podemos aplicar el teorema local-global al problema. 4. Introducimos variables de holgura s, t y hacemos los cambios de variable y = z = z1 z2 : Min. x2 + y 2 + z 2 s.a 5xy x2 3y 2 2z 2 z + t = 10 x 0, y  0, s, t 0

Min. x2 + y02 + (z1 z2 )2 s=5 s.a 5xy0 x2 3y02 2(z1 ) z1 z2 + t = 10 x, y0 , z1 , z2 , s, t 0

z2 )2

y0 ,

s=5

5. (a) Para el primer problema: S = {(x, y, z) 2 IR3 | x2 + 2y  10, z 4  20, y 0}. El conjunto es cerrado porque est´a definido por restricciones de  y a partir de funciones que son continuas porque son polinomios. Adem´as est´a acotado porque todo (x, y, z) 2 S cumple: 4  x  4,

0  y  5,

3  z  3.

Como S es cerrado y acotado, es compacto. Para el segundo problema: T = {(x, y, z) 2 IR3 | x3 + 2y  10, z 4  20, y 0, z 0} no est´a acotado, porque la variable x no tiene cota inferior. Todas las restricciones se pueden cumplir con cualquier valor negativo de x. Por lo tanto, T no es compacto. 5.(b) El primero de los dos problemas tiene ´optimo global, porque satisface las hip´otesis del teorema de Weierstrass: la funci´on objetivo es continua (porque es un polinomio), el conjunto de oportunidades es compacto (lo hemos visto en la pregunta anterior) y es no vac´ıo, pues (0, 0, 0) 2 S.

5.(c) La soluci´on ( 1 000, 1, 1) es infactible para el primer problema, pues no cumple la primera restricci´ on. Para el segundo tenemos que ( 1 000)3 + 2 · 1 =

999999998 < 10,

14 = 1 < 20,

1 > 0,

0=0

luego se trata de una soluci´on factible (porque cumple todas las restricciones, y es de frontera porque satura una de ellas (z 0). 5.(d) Un problema infactible es un problema sin soluciones factibles, mientras que un problema es no acotado si toda soluci´on factible puede ser mejorada por otra.

El primero de los dos problemas tiene soluci´on ´optima (apartado b), luego no es de ninguno de los dos tipos. Por el contrario, el segundo problema es no acotado, pues las soluciones ( 10, 1, 1),

( 100, 1, 1),

( 1 000, 1, 1),

( 10 000, 1, 1), . . .

son todas factibles y cada una de ellas es mejor que la anterior. 6. Las dos soluciones no pueden ser ´optimos globales, pues la primera es peor que la segunda, luego no puede ser la mejor de todas las soluciones factibles. La segunda podr´ıa ser ´optima y, si no lo es, ser´a porque hay otra mejor, en la que la funci´on objetivo valdr´a m´as de 15. Por lo tanto, lo que podemos decir sobre el valor ´optimo de la funci´on objetivo es que ser´a mayor o igual que 15.

´ MATEMATICAS II

Grupo M

3

APELLIDOS:

NOMBRE:

Considera el problema Min. 2x + 5y s.a 2y 3 3x + 5y  17 4x + 7y = 14 x, y 0 1. Estudia si la soluci´on (x, y, s, t) = (0, 2, 1, 7) es factible b´asica. 2. Estudia si existe una soluci´on factible b´asica con variables b´asicas (x, y, s). En primer lugar hay que escribir el problema en forma est´andar: Min. 2x + 5y s.a 2y s = 3 3x + 5y + t = 17 4x + 7y = 14 x, y, s, t 0 La matriz ampliada es:

0

0 2 B ¯ A=@ 3 5 4 7

1

1 0 3 0 1 17 C A 0 0 14

1. La soluci´on cumple las restricciones de igualdad: 2·2

1 = 3,

3 · 0 + 5 · 2 + 7 = 17,

4 · 0 + 7 · 2 = 14

Tiene que haber tres variables b´asicas (tantas como restricciones) y una no b´asica y, en efecto, la soluci´on dada tiene un cero, luego podemos tomar como variables b´asicas y, s, t y como variable no b´asica x. El determinante de la matriz b´asica es 2 5 7

1 0 0 1 = 0 0

7 6= 0.

Estas tres condiciones garantizan que la soluci´on es b´asica y, como adem´as sus variables son no negativas, es una soluci´on factible b´asica.

2. La soluci´on buscada tendr´a t = 0 (porque es la variable no b´asica) y las variables b´asicas vendr´an dadas por x¯B = B 1¯b. La matriz b´asica es 0

1

0 2 B=B @ 3 5 4 7 Se cumple que |B| =

1. La matriz adjunta es

0

˜= B

5 0 7 0

B B B B B B B B B B B @

1 0 C A 0

3 0 4 0

3 5 4 7

2 7

1 0

0 4

1 0

0 2 4 7

2 5

1 0

0 3

1 0

0 2 3 5

1 C C C C C C C C C C C A

0

0 7 5

=B @

0 4 3

1

1 8 C A 6

Por lo tanto: 0

0 B t ˜ B =@ 0 1

7 4 8

1

5 3 C A, 6

B

1

0

0 0 1

=B @

7 4 8

1

5 3 C A. 6

Las variables b´asicas son: 0

1

0

x B C B @ y A=@ s

0 0 1

7 4 8

10

1

0

5 3 B C B 3 C A @ 17 A = @ 6 14

1

49 26 C A 55

La soluci´on b´asica es (x, y, s, t) = (49, 26, 55, 0). Como no es factible, no hay soluci´on factible b´asica con variables b´asicas (x, y, s).

´ MATEMATICAS II

Grupo M

21-3-11 L1

APELLIDOS:

NOMBRE:

Una empresa debe atender lo m´as r´apidamente posible una demanda de 800 unidades de un producto A y 600 unidades de otro producto B, y para elaborarlos dispone de tres f´abricas F1 , F2 y F3 , la tercera de las cuales puede elaborar cualquier cantidad del producto B, pero no est´a preparada para elaborar el producto A. El problema siguiente determina las cantidades que le conviene elaborar en cada f´abrica de cada producto para minimizar el tiempo requerido garantizando un beneficio m´ınimo de 5 900 C. Min. 5X1A + 14X1B + 7X2A + 6X2B + 7X3B s.a X1A + X1B  700 X2A + X2B  600 X1A + X2A 800 X1B + X2B + x3B 600 3X1A + 12X1B + 9X2A + 5X2B + 3X3B 5 900 X1A , X1B , X2A , X2B , X3B 0 Variable Value X1A 675.0000 X1B 0.000000 X2A 125.0000 X2B 475.0000 X3B 125.0000 Row TIEMPO CAPACIDAD_1 CAPACIDAD_2 PRODUCCION_A PRODUCCION_B BENEFICIO

Tiempo (en minutos) Producci´on F1  capacidad Producci´on F2  capacidad Producci´on A compromiso Producci´on B compromiso Beneficio obtenido exigido Reduced Cost 0.000000 0.2500000 0.000000 0.000000 ?

Slack or Surplus 7975.000 25.00000 0.000000 0.000000 0.000000 0.000000

Dual Price -1.000000 0.000000 2.500000 -2.750000 -4.750000 -0.7500000

Objective Coefficient Ranges:

Variable X1A X1B X2A X2B X3B

Row CAPACIDAD_1 CAPACIDAD_2 PRODUCCION_A PRODUCCION_B BENEFICIO

Current Coefficient 5.000000 14.00000 7.000000 6.000000 7.000000

Allowable Increase 3.000000 INFINITY 0.1111111 1.666667 0.7692308E-01

Righthand Side Ranges: Current Allowable RHS Increase 700.0000 INFINITY 600.0000 50.00000 800.0000 14.28571 600.0000 33.33333 5900.000 1900.000

Allowable Decrease 0.1111111 0.2500000 3.000000 0.1111111 1.666667

Allowable Decrease 25.00000 316.6667 385.7143 500.0000 100.0000

´ MATEMATICAS II

Grupo M

APELLIDOS:

21-3-11 L1 NOMBRE:

Responde a las preguntas siguientes particularizando las respuestas al ejemplo concreto, evitando en tu conclusi´ on final expresiones generales como “funci´on objetivo”, “variable de holgura”, etc. Excepto para las preguntas 3, 4, 7, 9, escribe el n´ umero de cada pregunta que respondas al lado del dato o los datos de la soluci´on de lingo en que se basa tu respuesta. 1. (0.1 ptos.) ¿Qu´e cantidades de cada producto conviene producir en la f´abrica F1 ? 2. (0.1 ptos.) ¿Cu´antos minutos requerir´ a la producci´on total? ¿A cu´antas horas equivalen? 3. (0.1 ptos.) Indica cu´ales son las variables b´asicas y cu´ales las no b´asicas de la soluci´on ´optima. 4. (0.1 ptos.) Interpreta el valor 25 que aparece en la l´ınea: Row CAPACIDAD_1

Slack or Surplus 25.00000

Dual Price 0.000000

5. (0.2 ptos.) Si la empresa quisiera exigir un beneficio m´ınimo de 6 000 C, ¿aumentar´ıa o disminuir´ıa el tiempo necesario para la producci´on? ¿En cu´anto? 6. (0.1 ptos.) Interpreta el coste reducido de la variable X1B. 7. (0.1 ptos.) En la soluci´on falta el coste reducido de la variable X3B. Indica su interpretaci´ on. ¿Puedes deducir cu´anto vale? 8. (0.1 ptos.) Si la empresa tuviera que aceptar un compromiso de 10 unidades adicionales, ¿c´omo podr´ıa atenderlo m´as r´apidamente, si fuera del producto A o del producto B? 9. (0.1 ptos.) Explica por qu´e es falsa la afirmaci´ on siguiente y corr´ıgela: “Como no estamos empleando toda la capacidad de la f´ abrica F1 , el precio dual de su restricci´ on de capacidad es 0, lo que significa que podemos aumentar la cantidad producida en dicha f´ abrica sin alterar por ello el tiempo total empleado.” 10. (0.2 ptos.) Si la empresa pudiera reducir a 5 minutos el tiempo necesario para producir en F2 una unidad del producto A, ¿le convendr´ıa replantearse las cantidades que debe de producir en cada f´abrica? 11. (0.2 ptos.) Si el compromiso de producto B fuera de 500 unidades en lugar de 600, ¿seguir´ıa siendo necesaria toda la capacidad de la f´abrica F2 o quedar´ıa parte sin aprovechar? 12. (0.1 ptos.) ¿Qu´e beneficio podr´ıa obtener la empresa si pudiera aumentar en 40 unidades la capacidad de la f´abrica F2 ?

1. Conviene producir 675 unidades del producto A y ninguna del producto B. 2. Requiere 7 975 minutos, que equivalen a 7 975/60 = 133 horas. 3. Como hay cinco restricciones, tiene que haber 5 variables b´asicas, que son x1A , x2A , x2B , x3B , s1 (donde s1 es la variable del holgura de la primera restricci´ on). Las variables no b´asicas son x1B , s2 , s3 , s4 , s5 . 4. Significa que, aunque la f´abrica 1 puede producir hasta 700 unidades de producto, conviene producir 25 unidades menos de esta capacidad m´axima. 5. Miramos el precio dual de la quinta restricci´ on, que es 0.75, lo que nos dice que si el beneficio exigido pasa de 5 900 a 6 000, es decir, si aumenta en 100, el tiempo requerido mejorar´ a en 0.75 ⇥ 100 = 75, es decir, empeorar´a (aumentar´a) en 75 minutos. 6. No conviene producir el producto B en la f´abrica 1, pero si necesit´ aramos producir una unidad de dicho producto en dicha f´abrica, el tiempo requerido aumentar´ıa en 0.25 minutos. 7. Dicho coste reducido es lo que aumentar´ıa el tiempo requerido si cambi´aramos la restricci´ on x1B 0 por x1B 1, es decir, si nos vi´eramos obligados a producir al menos una unidad del producto B en la f´abrica 1, y el resultado es 0, puesto que ya estamos produciendo 125 unidades de dicho producto en dicha f´abrica, luego si estuvi´eramos obligados a producir una unidad no necesitar´ıamos cambiar la soluci´on, luego el tiempo empleado ser´ıa el mismo. 8. Miramos los precios duales de las restricciones tercera y cuarta: el primero es 2.75, que nos dice que si aument´aramos la producci´on de A en 10 unidades, el tiempo requerido aumentar´ıa en 27.5 minutos, mientras que si el aumento fuera del producto B el aumento de tiempo ser´ıa (seg´ un el otro precio dual) de 47.5 minutos. Por lo tanto, ser´ıa preferible aumentar la producci´on de A. 9. La afirmaci´ on es falsa porque el precio dual nulo nos dice que el tiempo empleado no cambiar´a si aumentamos la capacidad de la f´abrica, no la cantidad producida en ella. No es lo mismo: en este caso, la capacidad es de 700 unidades, mientras que la producci´on es de 625 unidades. Es el 700 y no el 625 lo que podemos alterar sin que var´ıe el tiempo. 10. El intervalo de sensibilidad del coeficiente de x2A en la funci´on objetivo es [4, 7.11]. Como 5 minutos est´a dentro del intervalo, la soluci´on ´optima no cambiar´a, luego no convendr´a replantearse la producci´on. 11. El intervalo de sensibilidad de la cuarta restricci´ on permite un descenso de hasta 500 unidades, luego un descenso de 100 queda dentro del intervalo, lo que implica que las variables no b´asicas seguir´an siendo las mismas. Como la variable de holgura

de la restricci´ on de capacidad de F2 es cero, seguir´a siendo cero, lo que significa que seguiremos empleando toda la capacidad. 12. El intervalo de sensibilidad de la capacidad de la f´abrica F2 permite un aumento de hasta 50 unidades, luego un aumento de 40 queda dentro del intervalo. Por lo tanto, las variables no b´asicas ser´an las mismas y, en particular, como la variable de holgura de la restricci´ on de beneficio es cero, seguir´a siendo cero, luego el beneficio seguir´a siendo el mismo: 5 900 C.

´ MATEMATICAS II

Grupo M

4-4-11 II

APELLIDOS:

NOMBRE:

1. Considera el problema Max. x y + z s.a 3x + y + z 3 x + 2y + 2z = 8 x + 3y + z  6 x, z 0, y  0 (a) Sin realizar ninguna iteraci´ on, construye la tabla del s´ımplex correspondiente a la soluci´on (4, 0, 2). (b) Resuelve el problema mediante el algoritmo del s´ımplex partiendo de dicha tabla. Razona todos los pasos y la conclusi´ on final (qu´e variable entra y por qu´e, qu´e variable sale y por qu´e, etc.) 2. Considera el problema Max. x + 3y + z + w s.a x + 2y + 2z + w = 8 x + 2y 2z = 6 2x + 2y + z  8 x, y, z, w 0 (a) Resu´elvelo por el m´etodo de las penalizaciones. (b) Razona que tiene soluci´on ´optima y si es de v´ertice, de arista finita o de arista infinita. (c) Estudia si la soluci´on (x, y, z, w) = (0, 3.5, 0.5, 0) es factible b´asica. (d) Razona que la soluci´on anterior es ´optima sin hacer ning´ un c´alculo que no puedas hacer mentalmente. 3. La figura siguiente representa el conjunto de oportunidades de un problema de programaci´ on lineal (hay que entender que se extiende indefinidamente hacia la derecha): E

B

A

C

D

(a) ¿Tiene el problema soluciones factibles b´asicas?, ¿cu´antas? (b) Razona si el problema podr´ıa ser infactible. ¿Y no acotado? (c) De los cinco puntos se˜ nalados, ¿Podr´ıa alguno ser una soluci´on ´optima? ¿Por qu´e? (d) Sea f la funci´on objetivo del problema y supongamos que f (A) = f (B) = 6,

f (C) = f (D) = 7,

f (E) = 8,

(pero no sabemos si el objetivo es maximizar o minimizar). ¿Puede tener el problema soluci´on ´optima de v´ertice? ¿Y de arista finita? ¿Y de arista infinita?

1. El problema en forma est´andar es Max. x + y0 + z s.a 3x y0 + z s = 3 x 2y0 + 2z = 8 x 3y0 + z + t = 6 x, y0 , z, s, t 0

0

3 A=B @ 1 1

1

1 1 2 2 3 1

1 0 3 0 0 8 C A 0 1 6

(a) Sustituyendo en las restricciones calculamos las variables de holgura: (x, y0 , z, s, t) = (4, 0, 2, 11, 0), luego las variables b´asicas son x, z, s. La matriz b´asica es 0

3 1 B=B @ 1 2 1 1

1

1 0 C A 0 B

0

B 1A = B @

0 0 1

1 1 2

1

10

0

0 0 1

1 y0 4 1 10 3 4

1 1 2

0 1 2 1

2 1 C A 5

1

1 1 2 2 3 1

0

1 0 3 1 C B 0 0 8 A=@ 0 0 1 6 0

Por lo tanto, la tabla del s´ımplex es: 1 x 1 x 1 1 z 0 0 s 0 1 0

˜=B B @

|B| = 1,

1 ˜t B = B =@ 1

2 3 CB 1 A@ 1 5 1

0

1 z 0 1 0 1 0

0 s 0 0 1 0 0

0 1 1

1

1 2 C A 5

4 0 0 1 1 0 10 0 1

0 t 2 4 1 2 5 11 1 1 6

(b) Como el problema es de maximizar, entra la variable y0 , porque es la u ´nica con marginal positivo, y sale la variable z porque es la u ´nica con yij positivo. 1 1 x y0 1 x 1 0 1 y0 0 1 0 s 0 0 1 1 0 0

1 z 4 1 10 5 4

0 s 0 0 1 0 0

1

2 4 1 2 C A 5 11

0 t 2 12 1 2 5 31 3 3 14

Ahora puede entrar la variable t, porque tiene marginal positivo, pero no sale ninguna variable, porque todos los yij son negativos. Por consiguiente, el problema es no acotado.

2. (a) El problema en forma est´andar es Max. x + 3y + z + w s.a x + 2y + 2z + w = 8 x + 2y 2z = 6 2x + 2y + z + s = 8 x, y, z, w, s 0 1 x 1 1 2

3 y 1 w 2 M A 2 0 s 2 1 M 2 2M M 1 + 2M

x 1 B A = @1 2 0

y 2 2 2

1 1 z w 2 1 2 0 1 0 2 + 2M 1 1 2M 0

z w A s 1 2 1 0 0 8 2 0 1 0 6C A 1 0 0 1 8 M A 0 1 0 M 0

0 s 0 8 0 6 1 8 0 0 8 6M

Entra la variable y porque tiene el marginal m´as positivo y sale la variable A porque es la que tarda menos en llegar a cero: 8/2 = 4, 6/2 = 3, 8/2 = 4.

1 w 3 y 0 s

1 x 0 1/2 1 3/2 1/2

3 y 0 1 0 3 0

1 1 z w 4 1 1 0 3 0 1 1 0 0

M A 1 1/2 1 1/2 M 1/2

0 s 0 2 0 3 1 2 0 0 11

Ya no puede entrar ninguna variable porque todos los marginales son negativos, luego la tabla es ´optima y corresponde a la soluci´on (x, y, z, w) = (0, 3, 0, 2). (b) El problema tiene soluci´on ´optima porque la variable artificial ha terminado con el valor 0. Adem´as la soluci´on es de arista finita, pues la variable z es no b´asica y tiene marginal 0, luego puede entrar sin alterar la funci´on objetivo, y sale la variable s, por lo que la arista es finita. (c) Sustituyendo en la tercera restricci´ on calculamos la variable de holgura: (x, y, z, w, s) = (0, 3.5, 0.5, 0, 0.5). • Comprobamos que cumple las restricciones de igualdad: 0+2·3.5+2·0.5+0 = 8,

0+2·3.5 2·0.5 = 6,

2·0+2·3.5+0.5+0.5 = 8.

• Como hay tres restricciones, ha de haber tres variables b´asicas, luego dos no b´asicas, luego la soluci´on ha de tener dos ceros, y los tiene. Las variables b´asicas son y, z, s.

• El determinante de la matriz b´asica es 2 2 2

2 0 2 0 = 1 1

8 6= 0.

Estas tres propiedades implican que la soluci´on es b´asica, y como sus variables son no negativas, es factible b´asica. (d) Basta observar que el valor de la funci´on objetivo en la soluci´on dada es F (0, 3.5, 0.5, 0) = 0 + 3 · 3.5 + 0.5 = 11 y en el apartado (a) hemos visto que el valor ´optimo de la funci´on objetivo es 11. Por lo tanto, la soluci´on dada es igual de buena que la soluci´on ´optima que hemos encontrado, luego tambi´en es ´optima. (Es el otro extremo de la arista finita de soluciones ´optimas.) 3. (a) Las soluciones factibles b´asicas son los v´ertices del conjunto de oportunidades. Este problema tiene dos: los puntos A y B. (b) El problema no puede ser infactible porque todos los puntos sombreados son soluciones factibles. Si la funci´on objetivo mejora hacia la derecha, el problema ser´a no acotado, pero tambi´en podr´ıa mejorar hacia la izquierda, y entonces el problema tendr´a soluci´on ´optima. No podemos, pues, asegurar que sea no acotado. (c) En un problema de programaci´ on lineal, las soluciones ´optimas son siempre de frontera, luego el punto C no pudese ser soluci´on ´optima, los dem´as s´ı. (d) Como la funci´on objetivo vale lo mismo en los dos v´ertices, no puede haber soluci´on de v´ertice, porque si uno es ´optimo el otro tambi´en lo es, luego la soluci´on es de arista finita. El problema s´ı que puede tener soluci´on ´optima de arista finita. Esto sucede si toda la arista AB est´a formada por soluciones ´optimas. Por ejemplo, si la funci´on objetivo es minimizar x. El conjunto de oportunidades tiene dos aristas infinitas, pero ninguna de ellas puede ser una arista de soluciones ´optimas, porque en ella la funci´on objetivo toma valores distintos en puntos distintos. Para que fuera una arista de soluciones ´optimas, la funci´on objetivo tendr´ıa que tomar el mismo valor (´optimo) en todos los puntos de la arista. As´ı pues, no puede haber soluci´on ´optima de arista infinita.

´ MATEMATICAS II

Grupo M

9-5-11 III

APELLIDOS:

NOMBRE:

1. Considera el problema siguiente, cuya tabla ´optima (una vez puesto en forma est´andar) es la que se indica. Min. 2x + 5y + z s.a x + y 10 3x + z = 20 x  0, y, z 0

2 x0 1 z

2 x0 1 0 2 0

5 y 1 3 1 4

1 z 0 1 1 0

0 s 1 10 3 50 1 1 30

(a) (0.05 ptos) Ponlo en forma est´andar y escribe la matriz t´ecnica del problema resultante. (b) (0.2 ptos) Escribe el problema dual (del dado, no del problema en forma est´andar) (c) (0.2 ptos) Calcula la soluci´on ´optima del dual a partir de la tabla ´optima del primal. 2. El problema siguiente maximiza el beneficio de una empresa sujeto a una restricci´ on presupuestaria teniendo en cuenta que la capacidad de producci´on total est´a limitada a 40 unidades. Max. 2x + 3y + 2z beneficio s.a 3x + 2y + 4z  100 coste  presupuesto x + y + z  40 producci´on  capacidad x, y, z 0

0 s 3 y

2 x 1 1 3 1

3 y 0 1 3 0

2 z 2 1 3 1

0 s 1 0 0 0

0 t 2 20 1 40 3 3 120

µ s0 2 0 0 1 0 1 2 1 0

t0 1 1 1

u0 1 0 0

La tabla de la izquierda corresponde a la soluci´on ´optima del problema. (a) (0.05 ptos) Deduce de la tabla cu´al es la soluci´on ´optima del problema dado y el beneficio m´aximo. (b) (0.1 ptos) Escribe el problema dual. (c) (0.2 ptos) Calcula la soluci´on ´optima del dual a partir de la tabla ´optima del primal, incluyendo los valores de las variables de holgura.

(d) (0.1 ptos) Completa la tabla ´optima del dual. (Ten cuidado con el orden en que pones las variables en la parte izquierda.) (e) (0.1 ptos) ¿C´omo afectar´ıa a los beneficios de la empresa que una aver´ıa en una m´aquina redujera la capacidad de producci´on a 35 unidades? Razona la respuesta sin calcular la nueva soluci´on ´optima. (f) (0.3 ptos) Calcula e interpreta el intervalo de sensibilidad del beneficio unitario del segundo producto. (g) (0.3 ptos) Calcula e interpreta el intervalo de sensibilidad de la capacidad de producci´on. (h) (0.4 ptos) Calcula la nueva soluci´on ´optima si la empresa pudiera aumentar su capacidad de producci´on hasta 60 unidades en total.

1 (a) Min. s.a

2x0 + 5y + z x0 + y s = 10 3x0 + z = 20 x0 , y, z, s 0

A=

1 1 0 3 0 1

1 10 0 20

!

(b), (c) Max. 10 + 20µ s.a + 3µ 2 5 µ1 0

( , µ) = ( 2, 1)

1 0 3 1

!

= (1, 1)

(La matriz B 1 se obtiene de las columnas de y, z de la tabla ´optima, ya que la matriz t´ecnica tiene la matriz identidad en dichas columnas.) 2 (a) (x, y, z) = (0, 40, 0), B = 120. (b) Min. 100 + 40µ s.a 3 + µ 2 2 +µ 3 4 +µ 2 , µ 0. (c) La correspondencia entre variables es $ s, µ $ t, s0 $ x, t0 $ y, u0 $ z, de modo que, mirando los marginales de la tabla: ( , µ, s0 , t0 , u0 ) = (0, 3, 1, 0, 1).

(d) 100 40 0 µ s0 0 0 u 2 0 0 0 0 s 1 0 1 40 µ 2 1 0 80 40 0 20 0 0

0 t0 1 1 1 40 40

0 u0 1 1 0 1 0 3 0 0 120

(e) La variable dual µ = 3 se interpreta como que por cada unidad que aumente la capacidad de producci´on, el beneficio aumenta 3 unidades. Ante una disminuci´on de 5 unidades, el incremento de beneficio ser´a de 3 · ( 5) = 15 unidades, es decir, el beneficio disminuir´a 15 unidades. (f) 2 x 1 1 c2

0 s c2 y 2

c2

c2 y 0 1 c2 0 2

2 z 2 1 c2 c2

0 s 1 0 0 0

0 t 2 20 1 40 c2 c2 120

Para que la tabla siga siendo ´optima ha de ser 2 c2  0, c2  0, luego c2 2, c2 0 y, por lo tanto, el intervalo de sensibilidad es [2, +1[. Su interpretaci´ on es que mientras el beneficio unitario del segundo producto no sea inferior a 2 la soluci´on ´optima seguir´a siendo la misma. (g) La matriz B

1

est´a en la tabla ´optima en las columnas de s y t. Calculamos 1¯

B b=

1 0

2 1

!

100 b2

!

=

100

2b2 b2

!

Para que la tabla siga siendo factible ha de ser 100 2b2 0 y b2 0, luego b2  50 y el intervalo de sensibilidad es [0, 50]. Su interpretaci´ on es que mientras la capacidad de producci´on no supere las 50 unidades las variables b´asicas de la soluci´on ´optima ser´an las mismas, lo que se traduce en que se seguir´a sin producir los productos x, z y se seguir´a agotando el presupuesto. (h) Como la nueva capacidad est´a fuera del intervalo de sensibilidad, la nueva tabla ya no ser´a factible, por lo que tendremos que postoptimizar con el dual: 100 60 0 µ s0 0 0 u 2 0 0 0 s0 1 0 1 60 µ 2 1 0 120 60 0 20 0 0

0 t0 1 1 1 60 60

0 u0 1 1 0 1 0 3 0 0 120

La tabla ya no es ´optima. Entra la variable , porque tiene marginal negativo en un problema de minimizar, y sale la variable µ, pues es la u ´nica con yij > 0. 100 0 u0 0 s0 100

60 0 µ s0 0 1 0 0 1/2 1 1 1/2 0 100 50 0 0 10 0

0 t0 2 3/2 1/2 50 50

0 u0 1 4 0 5/2 0 3/2 0 0 150

La tabla ya es ´optima y la nueva soluci´on del primal es (x, y, z) = (0, 50, 0) con un beneficio m´aximo de 150.