Problemas de Formulacion de Modelos de Programacion Lineal

8/12/2019 Problemas de Formulacion de Modelos de Programacion Lineal

1/95

Coleccion de problemas de formulacion de modelos de

Programacion Lineal

Alvaro Garca Sanchez, Miguel Ortega Mier

3 de marzo de 2013

5


2/95

Indice

1. 7

1.1. Enunciado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2. Resolucion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2. 13


3. 19


4. 22


5. 24

5.1. Enunciado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

6. 25


7. 28


8. 31


9. 33


10. 37


11. 42


12. 46

12.1. Enunciado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

12.2. Resolucion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

13. 48


1


3/95

14. 52


15.Ejercicio 54


16.Ejercicio 55


17.Ejercicio 56


18.Ejercicio 57


19.Ejercicio 58


20.Ejercicio 59


21.Ejercicio MME-1213-ENE-2 61


22.Ejercicio 62

22.1. Enunciado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

22.2. Resolucion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

23.Ejercicio 65


24.Ejercicio 66


25.Ejercicio 68

25.1. Enunciado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

26.Ejercicio 6926.1. Enunciado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6926.2. Resolucion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

27.Ejercicio 70


2


4/95

28.Ejercicio 72


29.Ejercicio MME-1213-ENE-3 74


30.Ejercicio 75


31.Ejercicio 76


32.Ejercicio 78


33.Ejercicio 80


34.Ejercicio 82


35.Ejercicio 83


36.Ejercicio 85

36.1. Enunciado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

36.2. Resolucion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

37.Ejercicio 87


38.Ejercicio 88

38.1. Enunciado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8838.2. Resolucion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8838.3. Enunciado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9038.4. Resolucion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9038.5. Enunciado MME-1213-ENE-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9138.6. Resolucion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

39.Ejercicio 92


3


5/95

40.Ejercicio 93


4


6/95

INDICE 6Indice


7/95

1 71.

1.1. Enunciado

Un fabricante de refrescos F Rproduce tres modalidades (A, B yC), cada una en su propio formato:de 3 litros, 2 litros y 1 litro, respectivamente. Este fabricante esta comprometido a entregar a un grandistribuidorGD(su unico cliente) exactamente 20000 litros diarios de refrescos. Dispone de 25000 gramos

diarios de un saborizante del que cada modalidad consume por botella: la botella de 3 litros, 2 gramos; lade 2 litros, 3 g; y la de un litro, 4 g. Conocidos los datos economicos de A, B y C, y siendo xj los miles debotellas de la modalidadj a envasar diariamente, F Rha planteado el siguiente modelo de programacionlineal (c y b estan expresados en miles):

max z = 5x1+ 6x2+ 8x3

s.a.

2x1+ 3x2+ 4x3 25

3x1+ 2x2+ 1x3= 20

x1, x2, x3 0

(1)

1. Obtener el plan optimo de envasado de F R.

2. Determinar el significado de los multiplicadores del simplex de las dos restricciones.

3. AF Rle preocupa la posibilidad de que su proveedor de tapones (iguales para las tres modalidades)restrinja su suministro a un maximo de 6000 tapones diarios. Como ejercicio de postoptimizacion,introducir esta nueva restriccion y determinar su repercusion.

4. Mediante el correspondiente analisis de sensibilidad, determinar la repercusion en elmixde envasadode posibles cambios en los precios de venta de las dos modalidades de menor capacidad,B yC (x2y x3).

5. Determinar la validez del mix de produccion ante posibles variaciones en la demanda total derefrescos, que se traduciran en un mayor o menor volumen a entregar diariamente a GD, utilizandoel analisis de sensibilidad.

6. El formato de 3 litros (modalidad A, x1) puede estar especialmente afectado por los cambios enlos mercados de refrescos y materias primas. Mediante la programacion parametrica, analizar elconjunto de diferentes planes de envasado y sus resultados en funcion de cualquier valor no negativode la contribucion unitaria al beneficio del producto A.

7. El gran distribuidor GD exige que las entregas diarias sean multiplos exactos de mil para cadamodalidad. A partir de la resolucion del apartado a) de la pregunta anterior, plantear un planosecante de correspondiente al algoritmo de Gomory y, sin realizar ninguna iteracion, introducir larestrccion correspondiente en la tabla de la solucion optima hasta el momento.

1.2. Resolucion

max z = 5x1+ 6x2+ 8x3

s.a.

2x1+ 3x2+ 4x3 25

3x1+ 2x2+ 1x3= 20

x1, x2, x3 0

(2)


8/95

1 8El problema se puede reformular de la siguiente manera, convirtiendo las desigualdades en igualdades(identido al problema anterior en terminos del sistema que representa):

max z = 5x1+ 6x2+ 8x3

s.a.

2x1+ 3x2+ 4x3+ h1 = 25

3x1+ 2x2+ 1x3 = 20

x1, x2, x3 0

(3)

No existe solucion basica factible inmediata, por lo que es necesario utilizar el metodo de las dos faseso de la Mgrande. En el primer caso, se construye el siguiente problema auxiliar P:

max z = a

s.a.

2x1+ 3x2+ 4x3+ h1 = 25

3x1+ 2x2+ 1x3+ a= 20

x1, x2, x3, a 0

(4)

Apartado 1. Para el problemaP es posible encontrar una solucion basica factible de partida con lasactividades basicash1 ya, con valoresh1 = 20 ya = 20. Al aplicar el metodo del Simplex, en su variantede la matriz completa, para esa solucion basica se obtiene la siguiente tabla:

x1 x2 x3 h1 a20 3 2 1 0 0 (VB fase 1)0 5 6 8 0 0 (VB fase 2)

h1 25 2 3 4 1 0a 20 3 2 1 0 1

Introduciendo en la basex1 y sacando a, se obtiene:

x1 x2 x3 h1 a0 0 0 0 0 -1 (VB fase 1)

-100/3 0 8/3 19/3 0 -5/3 (VB fase 2)h1 35/3 0 5/3 10/3 1 -2/3x1 20/3 1 2/3 1/3 0 1/3

La tabla anterior corresponde a una solucion del problemaP dondea = 0, por lo que es una solucionbasica factible del problema original, pero no optima, porque no cumple VB 0. Introduciendo en labasex3 y sacando h1, se obtiene:

x1 x2 x3 h1 a0 0 0 0 0 -1 (VB fase 1)

-111/2 0 -1/2 0 -19/10 -2/5 (VB fase 2)x3 7/2 0 1/2 1 3/10 -1/5

x1 11/2 1 1/2 0 -1/10 2/5

La tabla anterior corresponde a la solucion optima del problema original (VB 0). El programa deproduccion optimo consiste en:

Producir 5500 refrescos de 1/3l, ningun refresco de 1/2l y 3500 de 1l.

Se consumen todo el material disponible para producir las botellas (h1 = 0)


9/95

1 9Apartado 2. Los multiplicadores del simplex (B =cBB1) se pueden calcular, a partir de la tabla,de la siguiente manera:

B1 = VBh1

= 19/10

B2 = VBa = 2/5

La interpretacion de los mismos es la siguiente:

B1 = 19/10. Si b1 = 1 z = 19/10. La empresa estara dispuesta a pagar hasta 1900 unidadesmonetarias para disponer de 1 kg mas diariamente. Igualmente, estara dispuesta a vender 1 kg sirecibiera por ello cualquier cantidad superior a 1900 unidades monetarias.

B2 = 2/5. Si b1 = 1 z = 2/5. La empresa podria obtener un beneficio mayor (4/5) si elcompromiso fuera entrgar 21000 botellas y no 20000, por lo que este compromiso esta actuandocomo una limitacion.F Restara dispuesta a renegociar el compromiso para pasar a 21000 botellas,siempre y cuando esto no representara un coste para ella superior a 400 unidades monetarias.

Apartado 3. En terminos del planteamiento del modelo, la posibilidad descrita se traducira en lasiguiente restriccion:

x1+ x2+ x3 6 x1+ x2+ x3+ h3 = 6

Tras introducir la nueva restriccion y modificarla convenientemente para que x1, x3 y h3 sean lasvariables basicas, se obtiene la solucion correspondiente a la siguiente tabla, que es una soluci on quecumple el criterio de optimalidad pero no es factible. Aplicando Lemke (sacando h3 e introduciendo h1)se obtiene la siguiente tabla.

x1 x2 x3 h1 h3-111/2 0 -1/2 0 -19/10 0

x3 7/2 0 1/2 1 3/10 0x1 11/2 1 1/2 0 -1/10 0

6 1 1 1 0 11/2 0 1/2 1 1/10 1

h3 -3 0 0 0 -1/5 1-111/2 0 -1/2 0 -19/10 0

x3 7/2 0 1/2 1 3/10 0x1 11/2 1 1/2 0 -1/10 0h3 -3 0 0 0 -1/5 1

-27 0 -1/2 0 0 -19/2x3 -1 0 1/2 1 0 3/2x1 7 1 1/2 0 0 -1/2h1 15 0 0 0 1 -5

La ultima tabla corresponde a una solucion no factible (x3 0) y no existe ninguna tasa de sustitucionde esa variable con respecto a las no basicas que sea negativa. Al introducir la nueva restriccion el problemano tiene solucion factible. Si el proveedor de tapones hiciera como se dice, no sera posible obtener unprograma de produccion que cumpliera con todas las restricciones.

Apartado 4. El rango de valores para c2 y c3 dentro del cual la composicion del mixde producciones el mismo que el obtenido se obtiene calculando los nuevos criterios del Simplex en funci on de dichosvariables.

En el caso de c2, como x2 no es una variable basica, si c2 se modifica, solo se modifica VB2 . En

particular:

VB2 =c2 cBB1A2 = c2

B

32

=c2 13/2 (5)


10/95

1 10El mixsigue siendo el mismo si c2 13/2 0, es decir, si c2 13/2El el caso de que cambiec3, comox3 es una variable basica, cambian los criterios del Simplex de todas

las variables (menos los de las basicas, que son 0). En particular:

VB =c cBB1A= c cBp=

5 6 c3 0

c3 5 0 1/2 1 3/10

1 1/2 0 1/10

=

= 5 6 c3 0 5 c3+52 c3 3c3510 = 0 7 c3 0 3c3510 (6)

Es decir, el mixes el mismo si se cumple simultaneamente:

7 c3 03c3510

0

c3 7c3 5/3

c3 7 (7)

El mix es el mismo, siempre y cuando la contribucion unitaria al beneficio de cada botella de litro seaigual o superior a 7 unidades monetarias.

Apartado 5. La demanda de refrescos quedar reflejada en la segunda restriccion. Si cambia b2, lasolucion podra dejar de ser factible y, por lo tanto, dejar de ser optima.

uB

=B1

b= 3/10 1/51/10 2/5 25b2 = 752b2

1025+4b2

10 0 b2 75/2b2 25/4 (8)

Es decir, el mixes el mismo se 25/4 b2 75/2, es decir, si la demanda supera los 6250 botellas ysi no supera los 37500.

Apartado 6.

T0 x1 x2 x3 h1-111/2 0 -1/2 0 -19/10

x3 7/2 0 1/2 1 3/10x1 11/2 1 1/2 0 -1/10

Seac1 = , con 0 . Si = 5, T ,0 es la tabla correspondiente a la solucion optima.

Si modifica su valor, se modificara el vector de criterios del Simplex V

B

(). Siempre y cuandoVB() 0 las actividades basicas seranx1 yx3, con los niveles de realizacion de la tabla T0. El criteriodel SimplexVB() es:

VB() = c cBB1A= c cBp=

6 8 0

8 0 1/2 1 3/10

1 1/2 0 1/10

=

0 42

0 2410

(9)Las variables basicas son x1 y x3 siempre y cuando VB(). Es decir:

4 0 24 0

4 24 (10)

Si 4 24, la tabla corresondiente a la solucion optima es T0():

T0() x1 x2 x3 h128 11/2 0 4

2 0 24

10

x3 7/2 0 1/2 1 3/10x1 11/2 1 1/2 0 -1/10


11/95

1 11Si = 4, la tabla se convierte en T1, correspondiente a un optimo multiple. Introduciendo x2 ysacandox3 se obtiene una nueva solucion a la que le corresponde la tabla T2

T1 x1 x2 x3 h1-50 0 0 0 -2

x3 7/2 0 1/2 1 3/10x1 11/2 1 1/2 0 -1/10

T2 x1 x2 x3 h1-50 0 0 0 -2

x2 7 0 1 2 3/5x1 2 1 0 -1 -2/5

Si modifica su valor, se modificara el vector de criterios del Simplex VB(). Siempre y cuandoVB() 0 las actividades basicas seranx1 yx2, con los niveles de realizacion de la tabla T2. El criteriodel SimplexVB() es:


6 8 0

6 0 1 2 3/5

1 0 1 2/5

=

0 0 4 2185 (11)

El criterio del Simplex de la tabla T2 nunca se anula para valores de tales que 0 4Volviendo a la tabla T0(), si = 24, la tabla se convierte en la tabla T3, correspondiente a un

optimo multiple. Introduciendoh1 sacandox3 se obtiene la tablaT4 correspondiente a la solucion optimaalternativa:

T3 x1 x2 x3 h1160 0 -10 0 0

x3 7/2 0 1/2 1 3/10x1 11/2 1 1/2 0 -1/10T4 x1 x2 x3 h1

160 0 -10 0 0

h3 35/3 0 5/3 10/3 1x1 20/3 1 2/3 1/3 0

De nuevo, Si modifica su valor, se modificara el vector de criterios del Simplex VB(). Siempre ycuandoVB() 0 las actividades basicas seranx1 y h1, con los niveles de realizacion de la tabla T4. Elcriterio del Simplex VB() es:


6 8 0

0 0 5/3 10/3 1

1 2/3 1/3 0

=

0 623

243

0) (12)

El criterio del Sipmlex no se hace positivo para ningun valor de tal que >24En resumen:

Variables basicas: x1 = 2 yx2 = 7 si 0 4 conz = 42 + 2

Variables basicas: x1 = 11/2 y x3 = 7/2 si 4 24 conz = 28 + 11/2

Variables basicas: x1 = 20/3 y h1 = 35/3 si 24 con z = 20/3


12/95

1 12Apartado 6. Los dos posibles plano de Gomory de la forma:f0+

fixi 0 seran, en este caso,dos, uno por cada variable:

1/2 + 1/2x2+ 3/10h1 0 1/2x2+ 3/10h1 h3= 1/2

1/2 + 1/2x2+ 9/10h1 0 1/2x2+ 9/10h1 h4= 1/2

Si se introduce y modifica el primer plano secante, la tabla resultante sera la siguiente:

x1 x2 x3 h1 h3-111/2 0 -1/2 0 -19/10 0

x3 7/2 0 1/2 1 3/10 0x1 11/2 1 1/2 0 -1/10 0

1/2 0 1/2 0 3/10 -1h3 -1/2 0 1/2 0 -3/10 1

La tabla final es la siguiente, correspondiente a una solucion no factible que cumple el criterio deoptimalidad, por lo que se podra aplicar el metodo de Lemke.

x1 x2 x3 h1 h3-111/2 0 -1/2 0 -19/10 0

x3 7/2 0 1/2 1 3/10 0x1 11/2 1 1/2 0 -1/10 0h3 -1/2 0 1/2 0 -3/10 1


13/95

2 132.

2.1. Enunciado

Un fabricante de refrescos F Rproduce tres modalidades (A, B yC), cada una en su propio formato:de 3 litros, 2 litros y 1 litro, respectivamente. Este fabricante esta comprometido a entregar a un grandistribuidorGD(su unico cliente) exactamente 20000 litros diarios de refrescos. Dispone de 25000 gramos

diarios de un saborizante del que cada modalidad consume por botella: la botella de 3 litros, 2 gramos; lade 2 litros, 3 g; y la de un litro, 4 g. Conocidos los datos economicos de A, B y C, y siendo xj los miles debotellas de la modalidadj a envasar diariamente, F Rha planteado el siguiente modelo de programacionlineal (c y b estan expresados en miles):

max z = 5x1+ 6x2+ 8x3

s.a.

2x1+ 3x2+ 4x3 25

3x1+ 2x2+ 1x3= 20

x1, x2, x3 0

(13)

1. Obtener el plan optimo de envasado de F R.

2. Determinar el significado de los multiplicadores del simplex de las dos restricciones.

3. AF Rle preocupa la posibilidad de que su proveedor de tapones (iguales para las tres modalidades)restrinja su suministro a un maximo de 6000 tapones diarios. Como ejercicio de postoptimizacion,introducir esta nueva restriccion y determinar su repercusion.

4. Mediante el correspondiente analisis de sensibilidad, determinar la repercusion en elmixde envasadode posibles cambios en los precios de venta de las dos modalidades de menor capacidad,B yC (x2y x3).

5. Determinar la validez del mix de produccion ante posibles variaciones en la demanda total derefrescos, que se traduciran en un mayor o menor volumen a entregar diariamente a GD, utilizandoel analisis de sensibilidad.

6. El formato de 3 litros (modalidad A, x1) puede estar especialmente afectado por los cambios enlos mercados de refrescos y materias primas. Mediante la programacion parametrica, analizar elconjunto de diferentes planes de envasado y sus resultados en funcion de cualquier valor no negativode la contribucion unitaria al beneficio del producto A.

7. El gran distribuidor GD exige que las entregas diarias sean multiplos exactos de mil para cadamodalidad. A partir de la resolucion del apartado a) de la pregunta anterior, plantear un planosecante de correspondiente al algoritmo de Gomory y, sin realizar ninguna iteracion, introducir larestrccion correspondiente en la tabla de la solucion optima hasta el momento.

2.2. Resolucion

max z = 5x1+ 6x2+ 8x3

s.a.

2x1+ 3x2+ 4x3 25

3x1+ 2x2+ 1x3= 20

x1, x2, x3 0

(14)


14/95

2 14El problema se puede reformular de la siguiente manera, convirtiendo las desigualdades en igualdades(identido al problema anterior en terminos del sistema que representa):

max z = 5x1+ 6x2+ 8x3

s.a.

2x1+ 3x2+ 4x3+ h1 = 25

3x1+ 2x2+ 1x3 = 20

x1, x2, x3 0

(15)

No existe solucion basica factible inmediata, por lo que es necesario utilizar el metodo de las dos faseso de la Mgrande. En el primer caso, se construye el siguiente problema auxiliar P:

max z = a

s.a.

2x1+ 3x2+ 4x3+ h1 = 25

3x1+ 2x2+ 1x3+ a= 20

x1, x2, x3, a 0

(16)

Apartado 1. Para el problemaP es posible encontrar una solucion basica factible de partida con lasactividades basicash1 ya, con valoresh1 = 20 ya = 20. Al aplicar el metodo del Simplex, en su variantede la matriz completa, para esa solucion basica se obtiene la siguiente tabla:

x1 x2 x3 h1 a20 3 2 1 0 0 (VB fase 1)0 5 6 8 0 0 (VB fase 2)

h1 25 2 3 4 1 0a 20 3 2 1 0 1

Introduciendo en la basex1 y sacando a, se obtiene:

x1 x2 x3 h1 a0 0 0 0 0 -1 (VB fase 1)

-100/3 0 8/3 19/3 0 -5/3 (VB fase 2)h1 35/3 0 5/3 10/3 1 -2/3x1 20/3 1 2/3 1/3 0 1/3

La tabla anterior corresponde a una solucion del problemaP dondea = 0, por lo que es una solucionbasica factible del problema original, pero no optima, porque no cumple VB 0. Introduciendo en labasex3 y sacando h1, se obtiene:

x1 x2 x3 h1 a0 0 0 0 0 -1 (VB fase 1)

-111/2 0 -1/2 0 -19/10 -2/5 (VB fase 2)x3 7/2 0 1/2 1 3/10 -1/5

x1 11/2 1 1/2 0 -1/10 2/5

La tabla anterior corresponde a la solucion optima del problema original (VB 0). El programa deproduccion optimo consiste en:

Producir 5500 refrescos de 1/3l, ningun refresco de 1/2l y 3500 de 1l.

Se consumen todo el material disponible para producir las botellas (h1 = 0)


15/95

2 15Apartado 2. Los multiplicadores del simplex (B =cBB1) se pueden calcular, a partir de la tabla,de la siguiente manera:

B1 = VBh1

= 19/10

B2 = VBa = 2/5

La interpretacion de los mismos es la siguiente:

B1 = 19/10. Si b1 = 1 z = 19/10. La empresa estara dispuesta a pagar hasta 1900 unidadesmonetarias para disponer de 1 kg mas diariamente. Igualmente, estara dispuesta a vender 1 kg sirecibiera por ello cualquier cantidad superior a 1900 unidades monetarias.

B2 = 2/5. Si b1 = 1 z = 2/5. La empresa podria obtener un beneficio mayor (4/5) si elcompromiso fuera entrgar 21000 botellas y no 20000, por lo que este compromiso esta actuandocomo una limitacion.F Restara dispuesta a renegociar el compromiso para pasar a 21000 botellas,siempre y cuando esto no representara un coste para ella superior a 400 unidades monetarias.

Apartado 3. En terminos del planteamiento del modelo, la posibilidad descrita se traducira en lasiguiente restriccion:

x1+ x2+ x3 6 x1+ x2+ x3+ h3 = 6

Tras introducir la nueva restriccion y modificarla convenientemente para que x1, x3 y h3 sean lasvariables basicas, se obtiene la solucion correspondiente a la siguiente tabla, que es una soluci on quecumple el criterio de optimalidad pero no es factible. Aplicando Lemke (sacando h3 e introduciendo h1)se obtiene la siguiente tabla.

x1 x2 x3 h1 h3-111/2 0 -1/2 0 -19/10 0

x3 7/2 0 1/2 1 3/10 0x1 11/2 1 1/2 0 -1/10 0

6 1 1 1 0 11/2 0 1/2 1 1/10 1

h3 -3 0 0 0 -1/5 1-111/2 0 -1/2 0 -19/10 0

x3 7/2 0 1/2 1 3/10 0x1 11/2 1 1/2 0 -1/10 0h3 -3 0 0 0 -1/5 1

-27 0 -1/2 0 0 -19/2x3 -1 0 1/2 1 0 3/2x1 7 1 1/2 0 0 -1/2h1 15 0 0 0 1 -5

La ultima tabla corresponde a una solucion no factible (x3 0) y no existe ninguna tasa de sustitucionde esa variable con respecto a las no basicas que sea negativa. Al introducir la nueva restriccion el problemano tiene solucion factible. Si el proveedor de tapones hiciera como se dice, no sera posible obtener unprograma de produccion que cumpliera con todas las restricciones.

Apartado 4. El rango de valores para c2 y c3 dentro del cual la composicion del mixde producciones el mismo que el obtenido se obtiene calculando los nuevos criterios del Simplex en funci on de dichosvariables.

En el caso de c2, como x2 no es una variable basica, si c2 se modifica, solo se modifica VB2 . En

particular:

VB2 =c2 cBB1A2 = c2

B

32

=c2 13/2 (17)


16/95

2 16El mixsigue siendo el mismo si c2 13/2 0, es decir, si c2 13/2El el caso de que cambiec3, comox3 es una variable basica, cambian los criterios del Simplex de todas

las variables (menos los de las basicas, que son 0). En particular:

VB =c cBB1A= c cBp=

5 6 c3 0

c3 5 0 1/2 1 3/10

1 1/2 0 1/10

=

= 5 6 c3 0 5 c3+52 c3 3c3510 = 0 7 c3 0 3c3510 (18)

Es decir, el mixes el mismo si se cumple simultaneamente:

7 c3 03c3510

0

c3 7c3 5/3

c3 7 (19)

El mix es el mismo, siempre y cuando la contribucion unitaria al beneficio de cada botella de litro seaigual o superior a 7 unidades monetarias.

Apartado 5. La demanda de refrescos quedar reflejada en la segunda restriccion. Si cambia b2, lasolucion podra dejar de ser factible y, por lo tanto, dejar de ser optima.

uB

=B1

b= 3/10 1/51/10 2/5 25b2 = 752b2

1025+4b2

10 0 b2 75/2b2 25/4 (20)

Es decir, el mixes el mismo se 25/4 b2 75/2, es decir, si la demanda supera los 6250 botellas ysi no supera los 37500.

Apartado 6.

T0 x1 x2 x3 h1-111/2 0 -1/2 0 -19/10

x3 7/2 0 1/2 1 3/10x1 11/2 1 1/2 0 -1/10

Seac1 = , con 0 . Si = 5, T ,0 es la tabla correspondiente a la solucion optima.

Si modifica su valor, se modificara el vector de criterios del Simplex V

B

(). Siempre y cuandoVB() 0 las actividades basicas seranx1 yx3, con los niveles de realizacion de la tabla T0. El criteriodel SimplexVB() es:

VB() =c cBB1A= c cBp=

6 8 0

8 0 1/2 1 3/10

1 1/2 0 1/10

=

0 42

0 2410

(21)Las variables basicas son x1 y x3 siempre y cuando VB(). Es decir:

4 0 24 0

4 24 (22)

Si 4 24, la tabla corresondiente a la solucion optima es T0():

T0() x1 x2 x3 h128 11/2 0 4

2 0 24

10

x3 7/2 0 1/2 1 3/10x1 11/2 1 1/2 0 -1/10


17/95

2 17Si = 4, la tabla se convierte en T1, correspondiente a un optimo multiple. Introduciendo x2 ysacandox3 se obtiene una nueva solucion a la que le corresponde la tabla T2

T1 x1 x2 x3 h1-50 0 0 0 -2

x3 7/2 0 1/2 1 3/10x1 11/2 1 1/2 0 -1/10

T2 x1 x2 x3 h1-50 0 0 0 -2

x2 7 0 1 2 3/5x1 2 1 0 -1 -2/5

Si modifica su valor, se modificara el vector de criterios del Simplex VB(). Siempre y cuandoVB() 0 las actividades basicas seranx1 yx2, con los niveles de realizacion de la tabla T2. El criteriodel SimplexVB() es:


6 8 0

6 0 1 2 3/5

1 0 1 2/5

=

0 0 4 2185 (23)

El criterio del Simplex de la tabla T2 nunca se anula para valores de tales que 0 4Volviendo a la tabla T0(), si = 24, la tabla se convierte en la tabla T3, correspondiente a un

optimo multiple. Introduciendoh1 sacandox3 se obtiene la tablaT4 correspondiente a la solucion optimaalternativa:

T3 x1 x2 x3 h1160 0 -10 0 0

x3 7/2 0 1/2 1 3/10x1 11/2 1 1/2 0 -1/10T4 x1 x2 x3 h1

160 0 -10 0 0

h3 35/3 0 5/3 10/3 1x1 20/3 1 2/3 1/3 0

De nuevo, Si modifica su valor, se modificara el vector de criterios del Simplex VB(). Siempre ycuandoVB() 0 las actividades basicas seranx1 y h1, con los niveles de realizacion de la tabla T4. Elcriterio del Simplex VB() es:


6 8 0

0 0 5/3 10/3 1

1 2/3 1/3 0

=

0 623

243

0) (24)

El criterio del Sipmlex no se hace positivo para ningun valor de tal que >24En resumen:

Variables basicas: x1 = 2 yx2 = 7 si 0 4 conz = 42 + 2

Variables basicas: x1 = 11/2 y x3 = 7/2 si 4 24 conz = 28 + 11/2

Variables basicas: x1 = 20/3 y h1 = 35/3 si 24 con z = 20/3


18/95

2 18Apartado 6. Los dos posibles plano de Gomory de la forma:f0+

fixi 0 seran, en este caso,dos, uno por cada variable:

1/2 + 1/2x2+ 3/10h1 0 1/2x2+ 3/10h1 h3= 1/2

1/2 + 1/2x2+ 9/10h1 0 1/2x2+ 9/10h1 h4= 1/2

Si se introduce y modifica el primer plano secante, la tabla resultante sera la siguiente:

x1 x2 x3 h1 h3-111/2 0 -1/2 0 -19/10 0

x3 7/2 0 1/2 1 3/10 0x1 11/2 1 1/2 0 -1/10 0

1/2 0 1/2 0 3/10 -1h3 -1/2 0 1/2 0 -3/10 1

La tabla final es la siguiente, correspondiente a una solucion no factible que cumple el criterio deoptimalidad, por lo que se podra aplicar el metodo de Lemke.

x1 x2 x3 h1 h3-111/2 0 -1/2 0 -19/10 0

x3 7/2 0 1/2 1 3/10 0x1 11/2 1 1/2 0 -1/10 0h3 -1/2 0 1/2 0 -3/10 1


19/95

3 193.

3.1. Enunciado

La empresa San Guemil fabrica dos tipos de cerveza, una lager y una pilsen, para lo cual necesitadisponer de malta, lupulo y levadura.

Cada metro cubico de lager requiere 50 kg de malta, 20 de lupulo y 2 de levadura. Cada metro cubico

de pilsen necesita 60 kg de malta, 25 de lupulo y 2 de levadura. El beneficio que obtiene la empresa concada metro cubico de lager es de 140 um, mientras que con cada metro c ubico de pilsen obtiene 150 um.San Guemil dipone de una tonelada de malta por semana, 250 kg de lupulo y 22 kg de levadura tambienpor semana.

El modelo de programacion lineal que permite obtener la produccion optima para cada semana quedadescrito por:

max z = 140x1+ 150x2

s.a.:

50x1+ 60x2 1000

20x1+ 25x2 250

2x1+ 2x2 22

x1, x2 0

(25)

dondex1 yx2 representan, respectivamente, los volumenes de produccion semanales (enm3) de lagery de pilsen.

La tabla del simplex correspondiente a la solucion optima del modelo anterior y, por lo tanto, al plande produccion optimo de San Guemil, es:

x1 x2 h1 h2 h3-1600 0 0 0 -2 -50

h1 390 0 0 1 -2 -5x2 6 0 1 0 1/5 -2x1 5 1 0 0 -1/5 5/2

donde h1, h2 y h3 son, respectivamente, las holguras correspondientes a las tres restricciones del

modelo lineal.Se pide:

1. Indicar que uso se hace de cada una de las tres materias primas, as como cual es el precio maximoque estara dispuesta a pagar San Guemil por disponer de 1 kg mas a la semana de cada una de lastres materias primas.

2. Indicar, para el caso del lupulo, cuantos kg adicionales estara dispuesta a adquirir y cuantos kg desu disponibilidad de lupulo estara dispuesta a vender semanalmente tomando como referencia elprecio indicado en el apartado anterior.

3. San Guemil esta valorando la posibilidad de producir un nuevo tipo de cerveza, que tiene una doblefermentacion. Esta nueva cerveza consume, por cada metro cubico producido, 70 kg de malta, 30de lupulo y 4 kg de levadura. Indicar el beneficio unitario mnimo que hara rentable la produccion

y comercializacion de esta nueva cerveza.

4. San Guemil ha firmado un contrato de suministro con sus actuales clientes, por el cual se compro-mete a servir, conjuntamente entre lager y pilsen, un mnimo de 40m3 al mes (considerese que unmes tiene cuatro semanas). Indicar cual es el nuevo plan de produccion optimo.

5. Si una determinada semana se decide reservar 10 kg de lupulo sin utilizar (h2 = 10), como semodifica el plan optimo de produccion? como se modifica el valor de la funcion objetivo?


20/95

3 203.2. Resolucion

Apartado 1. La utilizacion que se hace de los recursos es la siguiente:

de los 1000 kg de malta, queda 390 sin utilizar;

se consumen por completo los 250 kg de lupulo;

se consumen por completo los 22 kg de levadura;El valor de una unidad adicional de cada recurso viene dado por el precio sombra de la restriccion

corresonpondiente. El vector de multiplicadores del simplex (precios sombra) es Bi = VBhi

, debido a

que todas las restricciones son de tipo menor o igual, por lo que B = (0, 2, 50). Por lo tanto:

San Guemil no esta dispuesta a pagar nada por adquirir un kg adicional de malta (y estara dispuestoa vender un kg de malta a cualquier precio);

San Guemil esta dispuesta a comprar un kg adicional de lupulo si el precio de ese kg es inferior a2 um (estara dispuesta a vender un kg a un precio superior a 2 um);

igualmente, estara dispuesta a comprar un kg adicional de levadura a un precio inferior a 50 um/kg(y a vender uno de sus 22 kg disponibles a un precio superior a 50 um/kg);

Apartado 2. Al adquirir lupulo adicional a los 250 kg se modifica el vector de disponibilidad de losrecursosb = (1000, 250, 22)T. Por un lado:

el precio sombra de ese recurso (segunda componente de B =cBB1) cambiara si cambia la base(B);

la base se modifica, porque, al modificarse b, la solucion basica hasta ahora optima puede dejar deser factible (uB =B1b).

El rango de valores dentro del cual el precio al cual San Guemil est a dispuesta a comprar un kg delupulo adicional a un maximo de 6um/kg es aquel para el cual uB 0:

uB =B1b= 1 2 50 1/5 2

0 1/5 5/2

1000b222

1000 2b2 110 0b25

+ 44 0 b2

5 + 55 0

b2 440b2 220b2 275

220 b2 275

(26)

Por lo tanto, San Guemil esta dispuesta a comprar hasta 25 kg de lupulo a un precio inferior a 2um/kg (75 = 275-250) o a vender hasta 30 kg a un precio superior a 2 um/kg (30=250-220).

Apartado 3. La nueva variedad resultara un producto rentable si el criterio del simplex de la variablecorrespondiente (x3) es positivo. Es decir:

VB3 =c3 cBB1A3 = c3

BA3 = c3 (0, 2, 50)

7030

4

=c3 260 0 c3 260 (27)

Por lo que si el precio es superior a los 260 um/m3, sera interesante su produccion y comercializacion.

Apartado 4. San Guemil esta produciendo en la actualidad 11 m3, por lo que en la actualidad yaesta cumpiendo el compromiso de producir al menos 10 m3. La restriccion que tendra la forma x1+x2 10no modifica el plan optimo de produccion, de manera que el plan optimo de produccion sera el mismo.


21/95

3 21Apartado 5. Reservar una cantidad de lupulo de 10 kg es equivalente a que h2 = 10. Cuando unavariable no basica entra a formar parte de la solucion, las tasas de sustitucion de esa variable con respectoa las basicas indican como se modifican los valores de estas al entrar aquella.

Las tasas de sustitucion deh3 sonph3 = (2, 15

, 15

, 0)T, por lo que:

h1 aumenta en 10 2 = 20, con lo que sobran 20 kg mas de malta

x2 disminuye en 10 1

5

= 2, con lo que se produce 2m3 menos de pilsen, es decir, se produciran 4m3 semanales;

x1 aumenta en 10 1

5= 2, con lo que se producen 2 m3 mas de lager, es decir, se produciran 7 m3

semanales.

Por su parte, la funcion ob jetivo se modificara de la siguiente manera: z = 10 VBh2 = 10 (2),es decir, el beneficio ser a de 1580 um semanales.


22/95

4 224.

4.1. Enunciado

1Un avicultor AV ha determinado que sus necesidades semanales de acido ascorbico (AA) y-caroteno

(C) como suplemento al pienso comun son, como mnimo, de 15 y 3 kilogramos respectivamente. En

su mercado local dispone de tres complejos suplementarios, de distinto precio y que contienen amboscomponentes en distintas proporciones. Siendo x1, x2 y x3 los kg semanales que comprara AV de cadauno de los tres complejos suplementarios CS1, CS2 y CS3, AV ha planteado el siguiente modelo deprogramacion lineal:

min z = 70x1+ 20x2+ 50x3

s.a.:

40x1+ 60x2+ 40x3 15000

30x1+ 60x2+ 40x3 3000

x1, x2, x3 0

(28)

1. Explicar el significado de cada uno de los coeficientes que aparecen en el modelo.

2. Obtener el plan optimo de compra de complejos suplementarios al precio normal y describir lainformacion que suministra la matriz completa para esta solucion.

3. Si surge un nuevo proveedor que ofrece un complejo suplementario CSN a 80 /Kg que contiene30 gramos de AA por kilogramo cuantoC por Kg debera contener como mnimo C SNpara quele interesara a AV?

4. Realizar el analisis de sensibilidad de la solucion optima obtenida en2respecto a los precios de loscomplejos suplementariosC S1, C S2 yC S3.

4.2. Resolucion

Apartado 1 Los coeficientes de la funcion objetivo (70, 20, 50) son los precios por kg de CS1, CS2 yCS3. Los terminos independientes de las restricciones (15000, 3000)T son los requisitos mnimos de AA

y C medidos en gramos. Los coeficientes tecnicos indican los gramos de AA o de C contenidos en unkilogramo de cada uno de los complejos suplementarios.

Apartado 2 La estructura del modelo se ajusta a la requerida para aplicar el metodo de Lemke. optima:

-z x1 x2 x3 xh1 xh20 -70 -20 -50 0 0

xh1 -15000 -40 -60 -40 1 0xh2 -3000 -30 -60 -40 0 1

5000 -170/3 0 -110/3 -1/3 0x2 250 2/3 1 2/3 -1/60 0

xh2 12000 10 0 0 -1 1

Solucion optima: AV comprara 250 kg/semana de CS2 con un coste de 5000 /semana. De estaforma cumplira estrictamente el mnimo de AA y de C suministrara a sus gallinas 12000 gramos (12kg) mas semanalmente de lo estrictamente necesario. Para que le interesara comprar CS1 o CS2, el preciodel suplemento debera ba jar 170/3 /kg (57 /kg) y 110/3 /kg (37 /kg), respectivamente, pasandoen ambos casos a 40/3 /kg (13 /kg). Una disminucion de los requisitos de C no tendra repercusioneconomica para AV (los cumple con holgura). Sin embargo, el valor de oportunidad de un gramo de AA es1/3 , lo que significa que por cada kilogramo que disminuyeran o aumentaran las necesidades semanalesde AA en la granja, AV disminuira o aumentara sus costes en 333 .


23/95

4 23Apartado 3 Como se acaba de ver, el contenido en C de un nuevo CS le es indiferente, ya queeste requisito esta cumplido de sobra. Por lo tanto, el interes CSN radica en si su precio de 80 /kgesta compensado por su contenido en AA medido mediante el valor de oportunidad, es decir, para queVBN = cN

BAN = cN B1 aN1 0, debe suceder que cN B1 aN1. Como lo que aporta CSN en

terminos de AA es B1 aN1 = 30/3 = 10 /kg y su precio es 80 /kg VBN = 70 y no interesa CSN

sea cual fuera su contenido en C.

Apartado 4 Para c1yc3ya se ha visto en el apartado b) que el intervalo correspondiente ser a [40/3, )en ambos casos. Como C S2 esta en la base de la solucion optima, si se expresa V

B para esta en funciondec2, resultara:

x1 x2 x3 xh1 xh25000 -70+2c2/3 0 -50+2c2/3 -c2/60 0

x2 250 2/3 1 2/3 -1/60 0xh2 12000 10 0 0 -1 1

Para que no exista un VBj >0 debe darse que: c2 105, c2 75 y c2 0 c2 [0, 75] ya que si elprecio deC S2 sube de 75 /kg AV pasara a comprar C S3.


24/95

5 245.

5.1. Enunciado

Dado el siguiente modelo de programacion lineal (MP):

max z = 5x1+ 2x2 9x3

s.a.:

x1+ x2 x3 6

x1 + 3x3= 12

x1, x2, x3 0

(29)

1. Que afirma el Teorema Fundamental de la Programacion Lineal?Que implicaciones tiene en termi-nos de la busqueda de la solucion optima de un problema de Programacion Lineal? Para el problema(MP), indicar tres soluciones: una solucion no basica factible, una solucion basica factible y unasolucion basica no factible.

2. Plantear y resolver graficamente el problema dual de MP.

3. Por aplicacion del teorema de las holguras complementarias, determinar a partir de 2) la composicionde la solucion optima de MP as como su correspondiente vector de criterios del simplex.

4. Explicar el significado de cada uno de los componentes del vector de criterios del simplex de lasolucion optima de MP obtenido en 3).

Postoptimizacion

5. Explicar la repercusion que podra tener para MP y para su dual la consideracion de una nuevarestriccion en MP (no es necesario mostrar ningun ejemplo numerico)

6. Ante la posibilidad de introducir en una nueva variable de accion xN en MP con los siguientesdatos:cN= 8 ,a1N= 1 ,a2N= 4 , analogamente a lo realizado en 2) y en 3), analizar graficamentesu repercusion en el modelo dual y su interes para MP.


25/95

6 256.

6.1. Enunciado

MME 1011 ENEUna empresa produce y comercializa tres tipos de productos, P1, P2 y P3, que sirve en pales, que

pueden o no estar completos (se puede entregar un pale a medio completar, medio pale, un cuarto de

pale, etc.) Por cada pale de estos productos, obtiene unos ingresos netos de 4, 12 y 2 unidades monetarias,respectivamente. Existe una instalacion de la que se dispone de un total de 6 das de traba jo a la semana.Producir un pale de P1 lleva 3 das, uno de P2 lleva 6 das y montar uno de P3 lleva 2 das. Ademas,existe un compromiso de entregar al menos el contenido conjunto equivalente a dos pales.

El siguiente modelo de programacion lineal permite obtener el plan de produccion optimo.

max z = 4x1+ 12x2+ 2x3

s.a.:

3x1+ 6x2+ 2x3 6

x1+ x2+ x3 2

x1, x2, x3 0

(30)

Dondexi representa el numero de pales producidos y servidos semanalmente dePi, coni = 1, 2, 3. Elproblema tambien se puede formular como:

max z = 4x1+ 12x2+ 2x3

s.a.:

3x1+ 6x2+ 2x3+ h1 = 6

x1+ x2+ x3 h2 = 2

x1, x2, x3, h1, h2 0

(31)

Una solucion posible es aquella a la que le corresponde la siguiente tabla, obtenida con la aplicaci ondel metodo del simplex en su variante de la matriz completa.

x1 x2 x3 h2 h1

-8 0 2 0 -2 -2x1 2 1 4 0 2 1x3 0 0 -3 1 -3 -1

Se pide:

1. Explicar el significado de las variablesh1 yh2.

2. Indicar si la solucion a la que se refiere la tabla dada es optima y justificar por que.

3. Para la solucion optima del problema (sea la correspondiente a la tabla dada u otra obtenida apartir de ella) interpretar y explicar el programa de produccion obtenido, la utilizacion que se hacede la instalacion y el cumplimiento del compromiso comercial.

Para la solucion optima (cada uno de los siguientes apartados son independientes entre s):

4. En que condiciones esta dispuesta la empresa a renegociar su compromiso de entregar un mnimode 2 pales.

5. Se ha realizado un estudio de mercado, y se sabe que no se pueden vender m as de 1 pale de P3 ala semana. Obtener el nuevo programa de produccion optimo con esa informacion.

6. Identificar el rango de valores para el ingreso por pale neto dentro del cual resulta interesanteproducir y vender el producto P2.


26/95

6 266.2. Resolucion

Apartado 1.

h1 representa el numero de das, de los 6 disponibles, que no se emplean en la produccion de pales.Es capacidad no utilizada.

h2 representa el numero de pales que se sirven por encima del compromiso de los dos pales adqui-

ridos.

Apartado 2. La solucion correspondiente a la tabla dada no es la solucion optima, porque la variablex2tiene criterio del simplex positivo (VB2 = 2), de manera que la introducion de esta variable (producciony venta deP2) reportara un valor de la funcion objetivo mayor que 8.

Apartado 3. En primer lugar, hay que obtener la solucion optima del problema. A partir de la tabladada, aplicando el metodo del Simplex, se introduce la variablex2 y se suprime la variablex1.

x1 x2 x3 h2 h1-8 0 2 0 -2 -2

x1 2 1 4 0 2 1x3 0 0 -3 1 -3 -1

-9 -1/2 0 0 -3 -5/2x2 1/2 1/4 1 0 1/2 1/4x3 3/2 3/4 0 1 -3 /2 -1/4

La tabla obtenida corresponde a la solucion optima. El plan de produccion consiste en:

no producir nada de producto P1,

producir medio pale de producto P2,

producir un pale y medio de producto P3,

utilizar por completo los seis das de capacidad de produccion y

cumplir el compromiso comercial entregando el mnimo de producto pactado (dos pales),

con un beneficio semanal de 9 unidades monetarias.

Apartado 4. El precio sombra de la restriccion correspondiente al compromiso comercial (de tipo )esB2 =V

Bh2

= 3. De manera que zj |b2=1 = 3, por lo que:

la empresa estara dispuesta a asumir un compromiso de entrega superior a 2, siempre que recibieraalgun tipo de compensacion superior a 3 u.m. por cada pale adicional que se comprometiera aentregar por encima de esos dos.

la empresa estara dispuesta a ofrecer algun tipo de compensacion por relajar el compromiso deentrega, sin superar 3 u.m. por la relajacion del compromiso en un pale.

Apartado 5. La informacion adicional da lugar a la aparicion de una nueva restriccion:x3 1. Comola produccion de P3 obtenida anteriormente es de 1.5 pales, dicha solucion no es factible y es necesarioobtener la nueva solucion. Introducciendo la nueva restriccion (que se puede formular como x3+ h3 = 1y aplicando el metodo de Lemke, se obtiene lo siguiente:


27/95

6 27x1 x2 x3 h2 h1 h3-9 -1/2 0 0 -3 -5/2 0

x2 1/2 1/4 1 0 1/2 1/4 0x3 3/2 3/4 0 1 -3 /2 -1/4 0

1 0 0 1 0 0 1-26/3 0 0 0 -4 8/3 -2/3

x2 1/3 0 1 0 1 1/3 1/3

x3 1 0 0 1 0 0 1x1 2/3 1 0 0 -2 -1/3 -4/3

La tabla obtenida corresponde a la nueva solucion optima, cuyo plan de produccion consiste en:

producir 2/3 de pale de producto P1,

producir 1/3 de pale de producto P2,

producir un pale de producto P3,

utilizar por completo los seis das de capacidad de produccion y

cumplir el compromiso comercial entregando el mnimo de producto pactado (dos pales),

con un beneficio semanal de 26/3 unidades monetarias, menor que el que se obtena antes de larestriccion comercial.

Apartado 6. Resulta interesante producir y venderP2 mientras VB 0, ya que x2 es una variable

basica en la solucion optima

VB =c cBB1A=

4 c2 2 0 0

c2 2 1/4 1 0 1/2 1/4

3/4 0 1 3/2 1/4

0

10c24

0 0 6c22

2c24

0 10 c2

(32)

Para cualquier precio de venta superior a 10 u.m. por pale resulta interesante producir y vender

producto P2


28/95

7 287.

7.1. Enunciado

Dado el problema de programacion lineal

maxz = x1+ x2 5x3+ 14x4

s.a

3x1+ 4x2+ 5x3+ 6x4 24

x1+ x2 2x3+ 2x4 12

x1, x2, x3, x4 0

(33)

su solucion optima queda caracterizada por: xo =

x4h2

, uo =

44

y B1 =

1

6 0

1

3 1

.

Se pide:

1. Para la solucion optima, obtener el cuadro correspondiente a la aplicacion del metodo del Simplexen su variante de la matriz completa.

2. Indicar la nueva solucion si la disponibilidad del recurso de la segunda restriccion disminuye en 8unidades.

3. Indicar, partiendo del problema original, como se modificara la solucion si el coeficiente de x4pasara de tomar un valor 14 a un valor 5.

4. Explicar el significado de VB3 , interpretado como c3 cBpB3, explicando con detalle su significado

con los valores numericos que permiten calcularVB3 .

5. Formular el problema dual e indicar cual es su solucion optima a partir de la aplicacion de losteoremas de la dualidad. No se valorara la resolucion del apartado por otros metodos diferentes delsolicitado.

7.2. Resolucion

Apartado 1. Lo que falta para poder construir la tabla son las tasas de sustitucion,pB =B1A, y elvector de criterios del simplex,VB =c cBB1A.

pB =B1A=

1

6 0

1

3 1

3 4 5 6 1 01 1 2 2 0 1

=

1/2 2/3 5/6 1 1/6 0

2 1/3 10/3 0 1/3 1

(34)

VB =c cBB1A= c cBpB = 1 7 5 14 0 0

14 0 1/2 2/3 5/6 1 1/6 0

2 1/3 10/3 0 1/3 1

=

8 25/3 50/3 0 7/3 0 (35)

Y, por lo tanto, la tabla es:

x1 x2 x3 x4 h1 h2-56 -8 -25/3 -50/3 0 -7/3 0

x4 4 1/2 2/3 5/6 1 1/6 0h2 4 -2 -1/3 -11/3 0 -1/3 1


29/95

7 29Apartado 2. El nuevo problema tendra b2 = 4, por lo que uB =B1bcambiara de valor.

B1b=

1

6 0

1

3 1

24

4

=

44

(36)

La solucion deja de ser factible y cumplira VB 0 y uB 0. Hay que aplicar el metodo de Lemke.Eliminandoh2 de la base e introduciendo x1 se obtiene:

x1 x2 x3 x4 h1 h2-40 0 -7 -2 0 -1 -4x4 3 0 * * 1 * *x1 2 1 * * 0 * *

Con lo que la nueva solucion es x4 = 3, x1 = 2 y el resto de variables no b asicas, e iguales a 0 y conun valor de la funcion objetivoz = 40.

Apartado 3. El nuevo problema tendra c4 = 5, por lo que VB cambiara de valor.

VB =c cBcB1A= c cB cpB =

1 1 5 5 0 0 5 0 1/2 2/3 5/6 1 1/6 0

2 1/3 11/3 0 1/3 1 = 7/2 7/3 55/6 0 5/6 0

(37)

Luego la solucion sera igualmente factible y optima. Con lo que x4 = 4, h2 = 0. S cambiara el valorde la funcion objetivo,z = 20

Apartado 4. VB3 =c3 cBpB3 = 50/3 representa la diferencia entre:

c3 = 5 la contribucion unitaria al beneficio por cada unidad realizada dex3(en este caso representauna perdida) y

la modificacion de la funcion objetivo por la modificacion de las variables basicas que representa larealizacion de una unidad dex3, 35/3,que se calcula como

la contribucion unitaria de las variables basicas, c

B

, multiplicada por la modificacion de las variables basicas que representa la realizacion de una unidad de x3,pB3.

En este caso, al realizar una unidad de x3 la funcion objetivo disminuira en 5 y la modificacion delas variables basicas hara que la funcion objetivo disminuyera en 35/3, con lo que no resulta interesantela realizacion de esa actividad.

Apartado 5. El problema dual es:

mins = 24y1+ 12y2

s.a

3y1 y2 1

4y1+ y2 15y1 2y2 5

6y1+ 2y2 14

y1, y2 0

(38)

Y su solucion optima es, por aplicacion del teorema fundamental de la dualidad:yo =B = (7/3, 0)Y por aplicacion del teorema de las holguras complementarias:


30/95

7 30Para la primera variable de hogura:y3= V1 = 8

y4 = V2 = 25/3

y5 = V3 = 49/3

y6 = V4 = 0

Con un un valor de la funcion objetivos =z = 56


31/95

8 318.

8.1. Enunciado

Se pide responder a las siguientes preguntas de tipo test.NOTA: redactar la respuesta incluyendo la frase completa en las hojas entregadas para calificar

con el encabezado y con la opcion elegida como correcta. Por ejemplo, una posible respuesta, sera

Al resolver un problema mediante le metodo de las dos fases, una restriccion del tipo jaijxj = bi,en el problema auxiliar asociado se transforma en jaijxj +hi ai = bi. No es necesario indicar elsubapartado (porque todos son diferentes)

Solo una respuesta de cada apartado es correcta. Para cada apartado, una respuesta correcta sumaun punto, una respuesta incorrecta resta un cuarto de punto.

1. Al resolver un problema mediante el metodo de las dos fases, una restriccion del tipo

jaijxj =bi,en el problema auxiliar asociado

Se transforma en

jaijxj+ hi ai= bi.

Se transforma en

jaijxj hi+ ai= bi.

Se transforma en

jaijxj+ ai = bi.

Ninguna de las anteriores es correcta.

2. Al resolver un problema mediante el metodo de las dos fases:

Si la solucion optima del problema auxiliar contiene alguna variable artificial en la base, elproblema original no tiene solucion factible.

Si la solucion optima del problema auxiliar tiene funcion objetivo igual a cero, el problemaoriginal s tiene solucion factible.

Tras obtener la solucion optima del problema auxiliar, basta con recalcularVB yz para poderreutilizar la tabla de dicha solucion y obtener una tabla correspondiente una solucion factibledel problema original .


3. Dado un problema de programacion lineal de maximizacion P, cuya solucion optima esx:

Al introducir una nueva restriccion, la solucion x puede dejar cumplir el criterio de optima-lidad.

Al introducir una nueva actividad, la solucionx puede dejar de ser factible.

Si se disminuye la contribucion unitaria al beneficio de una actividad no basica, la x podradejar de ser la solucion optima.


8.2. Resolucion

1. Al resolver un problema mediante le metodo de las dos fases, una restriccion del tipojaijxj =bi,en el problema auxiliar asociado

INCORRECTA: se transforma en

jaijxj+ hi ai= bi

INCORRECTA: se transforma en

jaijxj hi+ ai= bi

CORRECTA: se transforma en

jaijxj+ ai= bi

INCORRECTA: ninguna de las anteriores es correcta


32/95

8 322. Al resolver un problema mediante el metodo de las dos fases

INCORRECTA: si la solucion optima del problema auxiliar contiene alguna variable artificialen la base, el problema original no tiene soluci on factible

CORRECTA: si la solucion optima del problema auxiliar tiene funcion objetivo igual a cero,el problema original s tiene solucion factible

INCORRECTA: tras obtener la solucion optima del problema auxiliar, basta con recalcularVB y z para poder reutilizar la tabla de dicha solucion y obtener una tabla correspondientela solucion optima del problema original

INCORRECTA: ninguna de las anteriores es correcta

3. Dado un problema de programacion lineal P, cuya solucion optima es x

INCORRECTA: al introducir una nueva restriccion, la solucion x puede dejar cumplir elcriterio de optimalidad

INCORRECTA: al introducir una nueva actividad, la solucionx puede dejar de ser factible

INCORRECTA: si se disminuye la contribucion unitaria al beneficio de una actividad nobasica, la x podra dejar de ser la solucion optima

CORRECTA: ninguna de las anteriores es correcta


33/95

9 339.

9.1. Enunciado

La empresa dynamix fabrica tres estilos diferentes de mesas. A,B y C. Cada modelo de mesa requierede una cierta cantidad de tiempo para el corte de las piezas, su montaje y el correspondiente proceso depintura. La empresa puede vender todas las unidades que fabrica. Es mas, el modeloB tambien se puede

vender sin pintar. Los datos tecnico-economicos se muestran a continuacion.

Tiempo Tiempo Tiempo Contrib.Modelo corte (h) montaje (h) pintura (h) unitaria (euros)Modelo 1: mesa A pintada 1 2 4 35Modelo 2: mesa B pintada 2 4 4 40Modelo 3: mesa B sin pintar 2 4 0 20Modelo 4: mesa Cpintada 3 7 5 50

Capacidad (h/mes) 200 300 240

El siguiente modelo de programacion lineal permite obtener el plan de produccion mensual optimo.

maxz = 35x1+ 40x2+ 20x3+ 50x4

s.a

x1+ 2x2+ 2x3+ 3x4 200

2x1+ 4x2+ 4x3+ 7x4 300

4x1+ 4x2+ 5x4 240

x1, x2, x3, x4 0

(39)

Dondexi, i= 1, 2, 3 representa las unidades de modelo i producidas y vendidas mensualmente y x5,x6 y x7 son las variables de holgura necesarias para convertir las restricciones 1, 2 y 3, respectivamente,en igualdades.

Se sabe que las variables basicas de la solucion optima son x5, x3 y x1 y que la matriz inversa de la

base, para el orden de variables basicas anterior, correspondiente a dicha solucion es

B1 =

1 12 00 1

4 1

8

0 0 14

.Se pide:

1. Definir el plan de produccion optimo y el uso asociado de los recursos.

2. Dado el exito de los modelos de mesa sin pintar, la empresa esta valorando la posiblidad de fabricar elmodeloCsin pintar (que se diferencian de las mesas pintadas solo en el proceso de pintado). Estimaque la contribucion unitaria al beneficio de ese modelo sera de 42 euros por unidad. Justificar elinter es de la fabricaccion y venta de mesasCsin pintar y, en caso de haber un nuevo plan optimo

de produccion, describir cual sera.

3. Realizar un analisis de sensibilidad para la capacidad del taller de montaje.

4. Un estudio preliminar de metodos y tiempos permite afirmar que el tiempo de pintado de las mesasB podra reducirse. En particular, atendiendo a diferentes mejoras se podra reducir el valor peronunca podra ba jar de 2 horas. Se pide indicar cual es el beneficio obtenido en funcion de las horasde reduccion , que puede tomar cualquier valore entre 0 y 2.


34/95

9 349.2. Resolucion

Apartado 1. El vector de realizacion de las actividades basicas se obtiene como uB = B1b. En estecaso:

uB = 1 1

2 0

0 14

18

0 0 14

200300240

= 504560

(40)Es decir, x5 = 50,x3 = 45, x1 = 60 y el resto de variable son nulas, lo cual significa que:

se fabrican 60 mesas de tipo A y 45 de tipo B sin pintar,

no se fabrica nada del resto de modelos y

se emplean todas las horas disponibles de montaje y pintura y

sobran 50 horas de taller de corte,

con un beneficio de 3000 euros.

Apartado 2. Para valorar el interes de fabricar un nuevo modelo sera necesario introducir una nuevavariable,x8: numero de mesas de tipo Csin pintar. Con A8 = ( 3 7 0 )T, c8 = 42.

Sera interesante fabricar el nuevo modelo si VB8 0.

VB8 =c7 cBB1A8 = 42

0 20 35

1 12 00 14

18

0 0 14

3 7 0 = 7 (41)

Por lo que s sera interesante su produccion y venta, ya que con cada unidad producida y vendida elbeneficio se incrementara en 8 euros.

La tabla correspondiente a la solucion optima sin introducir la produccion del nuevo modelo sera lasiguiente, a partir de la cual, se podra iterar para obtener el nuevo plan de produccion.

x1 x2 x3 x4 x5 x6 x7 x8-3000 0 -5 0 -65/4 0 -5 -25/4 7

x5 50 0 0 0 -1/2 1 -1/2 0 -1/2x3 45 0 1/2 1 9/8 0 1/4 -1/8 7/4x1 60 1 1 0 5/4 0 0 1/4 0

-3180 0 -7 -4 -83/4 0 -6 -23/4 0x5 62.87 0 1 0x8 25.71 0 0 1x1 60 1 0 0

Con lo que el nuevo plan optimo consiste en:

producir, por termino medio, 60 mesasA y 25.71 de tipo C sin pintar

no producir nada del resto de modelos,

empleando todas las horas de todos los talleres, salvo en el de corte, que sobraran 62.87.


35/95

9 35Apartado 3. Las variables basicas de la solucion del apartado 1 son las correspondientes a la soluci onoptima mientras que uB =B1b tenga todos sus valores no negativos.

uB =

1 1

2 0

0 14

18

0 0

1

4

200b2

240

=

200 b2

2b24

30

60

0 (42)

Es decir 0 b2 400. Mientras la disponibilidad de las horas de montaje sea superior a 120 e inferiora 400, la solucion optima tiene las mismas soluciones basicas, lo que significa que el mix de prouduccionno cambia. S cambia la funcion objetivo que aumenta o disminuye en 2 = 25/4 con cada aumento odisminucion de una hora de taller con respecto a las disponibles.

Apartado 4. Como se admite que el tiempo de pintura puede reducirse en cualquier valor superiorcero e inferior a dos, en terminos del modelo, esto significa que los coeficientes tecnicos de la actividad 2

dependen de un parametro. En concreto,A2 =

2 4 4 T

Es necesario evaluar como se modificala solucion optima del problema en funcion de los valores del parametro.

Para la solucion optima de partida = 0 y x2 es no basica. Puede ocurrir que al variar el valor de resulte rentable realizar dicha actividad. Para ello es necesario evaluar el critero del simplex para dicha

variable en funcion del parametro:

VB2 =c2 BA2 = 40

0 5 25/4

244

= 20 + 25

4 (43)

Al modificarA2, cambian tanto VB2 como pB2 =B

1A2.

pB2 =

1 12

00 1

4 1

8

0 0 14

24

4

=

04+8

44

0 (44)

Es decir, mientras 4/5 la solucion inicial sigue siendo optima. En caso de que 4/5, la intro-

duccion dex2 mejorara el valor de la funcion objetivo. Para = 0, se tiene que pB2 =

0 3/5 4/5

TLa tabla correspondiente a ese caso sera la siguiente, correspondiente a un optimo multiple.

x1 x2 x3 x4 x5 x6 x7-3000 0 0 0 -65/4 0 -5 -25/4

x5 50 0 0 0 -1/2 1 -1/2 0x3 45 0 3/5 1 9/8 0 1/4 -1/8x1 60 1 4/5 0 5/4 0 0 1/4

-3000 0 0 0 -65/4 0 -5 -25/4x5 50 0 0 0 -1/2 1 -1/2 0x2 75 0 1 5/3 15/16 0 5/12 5/24x1 0 1 0 -4/4 -1/4 0 -1/3 25/6

La segunda tabla se obtiene introduciendo x2 y eliminandox1 de la base. Para valores de superioresa 4/5, las actividades basicas son x5,x2 y x1.

Al entrarx2 en la base, la nueva solucion base es:


36/95

9 36

B=

1 2 10 4 2

0 4 4

(45)

Y, a patir de su inversa, es posible calcular los nuevos criterios del simplex. Se puede comprobar quepara 4/5 2 el criterio del simplex de las nuevas variables no basicas sigue siendo no negativo.

En resumen:si la reduccion del tiempo de pintado es de entre 0 y 0.8 horas, el plan de produccion es el mismodel apartado 1;

si la reduccion del tiempo de pintado esta entre 0.8 y 2 horas, el mix de produccion cambia y seproduciran mesas de tipo A y B , en diferente cantidad segun la reduccion del tiempo de pintura.


37/95

10 3710.

10.1. Enunciado

El fabricante de bicicletas UPM Bikes produce bicicletas, triciclos y tandems. La produccion semanaldepende, esencialmente, de la disponibilidad de ruedas y de manillares y de las tareas de montaje. Elaprovisionamiento del resto de piezas y el resto de tareas no representan una limitacion para la empresa.

A la semana, UPM bikes dispone de un maximo de 100 ruedas y de 50 manillares.Por otro lado, el montaje de una bicicleta requiere una hora, mientras que el montaje de un triciclo ode un tandem requiere dos horas y existen dos operarios para realizar el montaje, cada uno de los cualestrabaja 40 horas semanales.

Ademas, UPM Bikes ha asumido un compromiso comercial y debe entregar un mnimo de 10 bicicletassemanalmente a uno de sus clientes.

Por ultimo, el beneficio unitario que proporcionan estos productos son de 300 cada bicicleta, 400 cada triciclo y 500 cada tandem.

Si x1, x2 y x3 representan las unidades de bicicletas, triciclos y t andems producidos semanalmente,el siguiente modelo de programacion permite obtener el plan de produccion optimo.

max z = 300x1+ 400x2+ 500x3

s.a.:

2x1+ 3x2+ 2x3+ h1 = 100

x1+ x2+ 2x3+ h2 = 50

x1+ 2x2+ 2x3+ h3 = 80

x1 h4 = 10

x1, x2, x3, h1, h2, h3, h4 0

(46)

Se admite que aunque las variables podran ser enteras, con el problema lineal se calculan los valoresmedios de produccion a lo largo de las diferentes semanas en las que se repite el plan de producci on.

La siguiente tabla corresponde a una solucion del problema correspondiente a su vez al plan deproduccion.

x1 x2 x3 h1 h2 h3 h4

-13000 0 150 0 0 -250 0 50h1 40 0 2 0 1 -1 0 1x3 20 0 1/2 1 0 1/2 0 1/2h3 30 0 1 0 0 -1 1 0x1 10 1 0 0 0 0 0 -1

Se pide:

1. Obtener el plan de produccion optimo y explicar el uso que se hace de los recursos

Para la solucion optima (cada uno de los siguientes apartados son independientes entre s):

2. Identificar la inversa de la base correspondiente a la solucion optima encontrada.

3. Discutir el interes por subcontratar horas adicionales para el montaje de productos.

4. Realizar el analisis de sensibilidad de la solucion obtenida con respecto al numero de manillaresdisponibles.

5. Indicar de que manera estara interesada UPM Bikes en renegociar su compromiso comercial

6. El precio de los tandems es bastante variable a lo largo del tiempo. Obtener mediante programa-cion parametrica el programa de produccion optimo para todos los posibles valores positivos de lacontribucion unitaria al beneficio de dicho producto iguales o superiores a 350 .


38/95

10 3810.2. Resolucion

REVISAR ERRATAS ULTIMO APARTADO

Apartado 1. Se aplica el metodo del Simplex partiendo de la tabla dada:

x1 x2 x3 h1 h2 h3 h4

-13000 0 150 0 0 -250 0 50h1 40 0 2 0 1 -1 0 1x3 20 0 1/2 1 0 1/2 0 1/2h3 30 0 1 0 0 -1 1 0x1 10 1 0 0 0 0 0 -1

-16000 0 0 0 -75 -175 0 -25x2 20 0 1 0 1/2 -1/2 0 1/2x3 10 0 0 1 -1/4 3/4 0 1/4h3 10 0 0 0 -1/2 -1/2 1 -1/2x1 10 1 0 0 0 0 0 -1

El programa de produccion optimo consiste en producir:

10 bicicletas

20 triciclos

10 tandems

Se usan todos los manillares y todas las ruedas y sobran diez horas de operarios de montaje.

Apartado 2. La inversa de la base esta donde originalmente habra estado la identidad. Las columnas1, 2 y 3 de la identidad estaban en la tabla inicial en las columnas correspondientes a h1,h2 yh3. Por suparte, la columna de h4, en la tabla incial, contea a la cuarta columna de la matriz identidad, por lo quela inversa de la base es la siguiete:

B1 =

1/2 1/2 0 1/21/4 3/4 0 1/41/2 1/2 1 1/2

0 0 0 1

(47)

Apartado 3. Sobran 10 horas de montaje por lo que no interesa contratar horas adicionales de montaje,y as queda de manifiesto dado el valor del precio sombra de la tercera restriccion3= VBh3 = 0.

Apartado 4. Las variables basicas de la solucion obtenida seran las de la solucion optima al modificarb2 si la solucion basica correspondiente sigue siendo factible.

uB =B

1b= 1/2 1/2 0 1/2

1/4 3/4 0 1/41/2 1/2 1 1/2

0 0 0 1

100b28010

= b2 90

b2 110/3b2 7010 0

(48)Mientras la disponibilidad de manillares este entre 37 y 70 a la semana, la composicion del plan de

produccion optimo no cambia (aunque s la cantidad de piezas producidas).


39/95

10 39Apartado 5. El compromiso comercial de UPM bikes aparece reflejado en la cuarta restriccion. El preciosombra de la misma es 4 =V

Bh4

=25, lo cual significa que si el compromiso comercial aumentase, enuna unidad, el beneficio semanal se reducira en 25 . Por lo tanto, UPM Bikes estara dispuesta a:

asumir un compromiso comercial mas restrictivo y entregar mas de 10 bicis, si recibe una compen-sacion por cada una de ellas superior a 25 .

relajar su compromiso comercial en la entrega de bicicletas, siempre y cuando la reduccion nosupusiera un coste adicional superior a 25 .

Apartado 6. Se trata de estudiar la solucion optima cuando el vector de contribuciones unitarias albeneficio es c = (300, 400, 500+ , 0, 0, 0, 0), con 150 .

La solucion obtenida en el apartado 1 es valida para = 0 y, en general, el valor de VB en funcionde es:

uB() =c() cB()B1A=

300 400 500 + 0 0 0 0

400 500 + 0 300

0 1 0 1/2 1/2 0 1/20 0 1 1/4 3/4 0 1/40 0 0 1/2 1/2 1 1/2

1 0 0 0 0 0 1

=

0 0 0 300

4 3+700

4 0 100

4

(49)

= 0 x1 x2 x3 h1 h2 h3 h40 0 0 300

4 3+700

4 0 100

4

x2 20 0 1 0 1/2 -1/2 0 1/2x3 10 0 0 1 -1/4 3/4 0 1/4h3 10 0 0 0 -1/2 -1/2 1 -1/2x1 10 1 0 0 0 0 0 -1

La solucion es la solucion optima si se cumple simultaneamente

300 0

3 700 0

100 0

(50)

Es decir, mientras 100 300 la base no se modifica.Si = 100 (el beneficio por cada tandem es de 400 ), la tabla se convierte en la siguiente (optimo

multiple) y se puede introducir la variable h4:

x1 x2 x3 h1 h2 h3 h40 0 0 -100 -100 0 0

x2 20 0 1 0 1/2 -1/2 0 1/2x3 10 0 0 1 -1/4 3/4 0 1/4

h3 10 0 0 0 -1/2 -1/2 1 -1/2x1 10 1 0 0 0 0 0 -10 0 0 -100 -100 0 0

h4 40 0 2 0 1 -1 0 1x3 0 0 -1/2 1 -1/2 1 0 0h3 30 0 1 0 0 -1 1 0x1 50 1 2 0 1 -1 0 0


40/95

10 40La solucion obtenida es valida para = 100 y, en general, el valor de VB en funcion de es:

uB() =c() cB()B1A=

300 400 500 + 0 0 0 0

0 500 + 0 300

0 2 0 1 1 0 10 1/2 1 1/2 1 0 00 1 0 0 1 1 0

1 2 0 1 1 0 0

=

0 +100

2 0 100

2 + 200 0 0

(51)

x1 x2 x3 h1 h2 h3 h40 +100

2 0 100

2 + 200 0 0

h4 40 0 2 0 1 -1 0 1x3 0 0 -1/2 1 -1/2 1 0 0h3 30 0 1 0 0 -1 1 0x1 50 1 2 0 1 -1 0 0

La solucion es la solucion optima si se cumple simultaneamente

+ 100 0

100 0

200 0

(52)

Esto se cumple para cualquier valor de con 150 100Si = 300 (el beneficio por cada tandem es de 800 ), la tabla se convierte en la siguiente (optimo

multiple) y se puede introducir la variable h1:

x1 x2 x3 h1 h2 h3 h40 0 0 0 -400 0 -100

x2 20 0 1 0 1/2 -1/2 0 1/2

x3 10 0 0 1 -1/4 3/4 0 1/4h3 10 0 0 0 -1/2 -1/2 1 -1/2x1 10 1 0 0 0 0 0 -1

0 0 0 0 -400 0 -100h1 40 0 2 0 1 -1 0 1x3 20 0 1/2 1 0 1/2 0 1/2h3 30 0 1 0 0 -1 1 0x1 10 1 0 0 0 0 0 -1

La solucion obtenida es valida para = 300 y, en general, el valor de VB en funcion de es:

uB() =c() cB()B1A=

300 400 500 + 0 0 0 0

0 500 + 0 300 0 2 0 1 1 0 10 1/2 1 0 1/2 0 1/20 1 0 0 1 1 0

1 0 0 0 0 0 1

=

0 3002

0 0 5002

0 100

(53)


41/95

10 41La solucion es la solucion optima si se cumple simultaneamente

300 0

500 0

100 0

(54)

Esto se cumple para cualquier valor de con

En resumen:

si 350 c3 450, se deben producir 50 bicicletas;

si 450 c3 800, se deben producir 10 bicicletas, 20 triciclos y 10 tandems;

si 800 c3 , se deben producir 10 bicicletas y 20 tandems.


42/95

11 4211.

11.1. Enunciado

David, Diana y Lidia son los unicos socios y empleados de una compana que produce relojes. Davidy Diana pueden trabajar un maximo de 40 horas por semana (cada uno de ellos), mientras que Lidia solopuede trabajar hasta 22 horas semanales.

La empresa hace dos tipos de relojes: rejores de pie y relojes de pared. Para hacer un reloj, David(ingeniero mecanico) ensambla las partes internas y Diana (ebanista) produce las cajas de madera ela-boradas a mano. Lidia es responsable de recibir pedidos y enviar los relojes. El tiempo que se requierepara cada tarea se muestra en la siguiente tabla.

Tarea Reloj de pie Reloj de pared

Montar mecanismo 6 horas 4 horasTallar la cubierta de madera 8 horas 4 horasEnvo 3 horas 3 horas

Cada reloj de pie construido y enviado deja una ganancia de 300 , mientras que cada reloj de paredproporciona una ganancia de 200 .

Los tres socios desean determinar cuantos relojes de cada tipo deben producir por semana para

maximizar la ganancia total.Se pide:

1. Formular un modelo de programacion lineal para los socios de esta empresa.

2. Resolver el modelo anterior e indicar el plan de produccion optimo y la ocupacion de los socios. Sepide interpretar y explicar correctamente los resultados obtenidos.

3. Existe acuerdo entre los socios por el que aquel que pudiera hacer que el beneficio aumentara maspor cada hora adicional traba jada, aumentara su disponibilidad horaria para la empresa. Identificarque socio aportara mayor incremento del beneficio por hora adicional traba jada y el numero dehoras que podra aumentar su disponibilidad proporcionando ese incremento.

4. Existe la posiblidad de vender solo las cajas de los relojes de pared, sin incluir ningun mecanismo.

Identificar cual es el beneficio unitario obtenido por caja que hara rentable su produccion y venta.Se estima que para este producto el tiempo de preparacion de envos es el mismo que para el restode productos.

5. Identificar el rango de valores para el margen por reloj de pared dentro del cual resulta interesanteproducir y vender dicho producto.

6. Se ha adquirido un compromiso comercial consistente en entregar al menos 9 relojes de pie cada tressemanas a un cliente. Caracterizar el efecto que tiene este compromiso sobre el plan de producciony comentar en que condiciones dicho compromiso puede ser interesante para la empresa.

11.2. Resolucion

Apartado 1. Se define x1 y x2 como el numero de relojes de pie y de pared producidos y enviadossemanalmente, respectivamente. El modelo de programacion lineal que permite maximizar la ganancia esel siguiente:


43/95

11 43

max z = 300x1+ 200x2

s.a.:

6x1+ 4x2 40

8x1+ 4x2 40

3x1+ 3x2 22x1, x2 0

(55)

Apartado 2. El modelo se puede reformular con las restricciones en forma de igualdad

max z = 300x1+ 200x2

s.a.:

6x1+ 4x2+ h1 = 40

8x1+ 4x2+ h2 = 40

3x1+ 3x2+ h3 = 22

x1, x2, h1, h2, h3 0

(56)

Donde h1, h2, h3 representan, respectivamente, el numero de las horas dispnibles que no trabajancada semana, respectivamente, David, Diana y Lidia. Aplicando el metodo del simplex se puede resolverel problema.

x1 x2 h1 h2 h30 300 200 0 0 0

h1 40 6 4 1 0 0h2 40 8 4 0 1 0h3 22 3 3 0 0 1

-1500 0 50 0 -75/2 0h1 10 0 1 1 3/4 0x1 5 1 1/2 0 1/8 0

h3 7 0 3/2 0 -3/8 1-5200/3 0 0 0 -25 -100/3

h1 16/3 0 0 1 -1/2 -2/3x1 8/3 1 0 0 1/4 -1/3x2 14/3 0 1 0 -1/4 2/3

El plan de produccion optimo consiste en producir, cada tres semanas, 8 relojes de pie, 14 relojes depared, para lo cual David debe trabajar 34.67 horas a la semana, Diana 40 horas y Lidia 22 horas, conun beneficio total de 1733.33 por semana.

Apartado 3. El incremento de la funcion objetivo obtenido al disponer de una hora adicional de cadauna de las tareas de la empresa viene dada por el precio sombra de las tres restricciones correspondientes.

1 = VBh1

= 0

2 = VBh2

= 25

3 = VBh3

= 33.33

(57)

Es decir, cada hora adicional de Lidia, permitira mejorar el beneficio en 33.33 .


44/95

11 44Para calcular el numero de horas que se debera ampliar el horario de Lidia obteniendo una mejora de33.33 por cada hora adicional, es necesario calcular para que valor de b3 la solucion deja de ser factible.

uB =B1b=

1 1/2 2/30 1/4 1/3

0 1/4 2/3

4040

b3

=

602b33

30b33

2b3303

(58)

Mientras 15 b3 30 se mantiene la solucion basica obtenida y, con ella, los precios sombra.Con el acuerdo pactado, Lidia debera trabajar 8 horas adicionales con un incremento total del bene-

ficio de 8 33.33 = 266.66 .

Apartado 4. Lo que se propone representa una nueva actividad x3, cuyos coeficientes tecnicos sonAT = (0, 4, 3). Se pide caracterizarc3 para que interese realizar esta actividad, es decir, si VB3 0

VB3 =c3 cB cBB1A3 = c3 c

B BA3 =

c3 0 25 100/3

04

3

=c3 200(59)

Siempre y cuando el beneficio unitario obtenido por la venta de las cajas de relojes de pared seasuperior a 200 es interesante su produccion y venta.

Apartado 5. En terminos del modelo, se pide un analisis de sensiilidad dec2, es decir, para que rangode valores de c2 la solucion siga siendo optima.

VB =c cB cBB1A=

300 200 0 0 0

0 300 c2 0 0 1 1/2 2/31 0 0 1/4 1/3

0 1 0 1/4 2/3

=

300 c2 0 0 0

0 0 0 300c2

4

300+2c23

0 150 c2 300

(60)

Es decir, el plan de produccion es optimo siempre y cuando el precio de los relojes de pared sea igualo superior a 100 e igual o inferior a 300 .

Apartado 6. El nuevo compromiso se traduce en una nueva restriccion: x1 3. La solucion optimaobtenida no cumple esta restriccion, por lo que es necesario iterar para obtener la nueva solucion.

La restriccion, de haberse introducido en la tabla del problema original, habra tenido la formax2 h4= 3

x1 x2 h1 h2 h3 h4-5200/3 0 0 0 -25 -100/3 0

h1 16/3 0 0 1 -1/2 -2/3 0

x1 8/3 1 0 0 1/4 -1/3 0x2 14/3 0 1 0 -1/4 2/3 03 1 0 0 0 0 -1

1/3 0 1 0 -1/4 1/3 -1h4 -1/3 0 -1 0 1/4 -1/3 1

La tabla una vez incorada la nueva restriccion y con h4 como variable basica es la siguiente, a partirde la cual se puede iterar aplicando el metodo de Lemke.

8/12/2019 Problemas de Formulac

Documents

Problemas de Formulacion de Modelos de Programacion Lineal