1. No category

Programación Matemática.
1
Análisis de sensibilidad.
1. Dado el programa lineal
maximizar
sujeta a
f (x) = 4x1 + 6x2 + 3x3
3x1 + 3x2 + x3 ≤ 30
2x1 + 2x2 + 3x3 ≤ 40
xi ≥ 0.
a) Resolverlo por el método sı́mplex.
b) Añadir la restricción 6x1 + 5x3 ≤ 60 y dar la solución óptima.
c) Cambiar la primera desigualdad por igualdad y conservar la restricción del apartado anterior.
d ) Sustituir la condición de no negatividad para x1 y x2 por x1 ≥ −1 y x2 ≥ −2.
e) Suponer que x3 no está restringida en signo.
2. La tabla siguiente es óptima para el problema de PL maximizar f (x) = cx, x ∈ {x/Ax = b, x ≥ 0}.
Básicas f
x1
0
x2
0
f (x)
1
x1
1
0
0
x2
0
1
0
x3
1
1
4
x4 x5
3 −1
−1 2
3
4
Solución
1
2
8
donde la base inicial es x4 , x5 con B = [a4 a5 ] = I.
a) ¿Cuánto puede aumentar c3 para que la solución siga siendo óptima? Hallar la solución óptima si
c3 = 6.
b) Intervalo de variación de c2 para que no varı́e la solución óptima. Hallar la solución óptima para
c2 = 1.
c) Intervalo de variación de c1 para que no varı́e la solución óptima.
d ) Mayor y menor valor de λ para que no varı́e la solución óptima cuando c se sustituye por c0 =
c + λc∗ , siendo c∗ = (0, 0, 1, −1, 2) y λ ∈ R.
e) Intervalo de variación de b2 para que (x1 , x2 ) sigan siendo básicas (no es necesario calcular el valor
de b2 )
f ) Hallar la solución óptima por el método sı́mplex dual si b2 aumenta dos unidades.
g) Intervalo de variación de λ para que x1 , x2 siga siendo base óptima si b se sustituye por b0 = b+λb∗ ,
con b∗ = (1, −1) y λ ∈ R.
h) Hallar la solución óptima si se añade la restricción x1 + x3 ≥ 2.
3. Una compañı́a se dedica a la fabricación de tres tipos de artı́culos A, B y C a fin de maximizar el
beneficio total a través del siguiente PL
maximizar f (x) = 3x1 + x2 + 5x3
sujeta a
6x1 + 3x2 + 5x3 ≤ 45 (mano de obra)
3x1 + 4x2 + 5x3 ≤ 30 (material)
xi ≥ 0.
donde xi representa el número de unidades del artı́culo i. La tabla óptima es
Básicas f
x1
0
x3
0
f (x)
1
x1
1
0
0
x2
−1/3
1
3
x3
0
1
0
x4
1/3
−1/5
0
x5
Solución
−1/3
5
2/5
3
1
30
Programación Matemática.
2
a) Intervalo para el beneficio unitario de A, c1 , que no varı́e la solución óptima. Determinar la solución
óptima si c1 = 2.
b) Se pueden obtener 15 unidades de material con un coste adicional de 10 unidades ¿resulta beneficioso llevar a cabo esa opción?
c) Hallar la solución óptima si la disponibilidad de material es de 60 unidades.
d ) Si las unidades de material necesarias para fabricar una unidad de B se reducen a 2 ¿afecta este
hecho a la solución óptima?
e) Si se añade una restricción de control 2x1 +x2 +3x3 ≤ 20 ¿quedan afectadas las soluciones óptimas
primal y dual originales?
4. Considerar el siguiente problema de programación lineal
minimizar f (x) = 3x1 + (4 + 8λ)x2 + 7x3 − x4 + (1 − 3λ)x5
sujeta a
5x1 − 4x2 + 14x3 − 2x4 + x5 = 20
x1 − x2 + 5x3 − x4 + x5 = 8
xi ≥ 0.
¿Para qué valores de λ es óptima la base (x2 , x3 )? Determinar las soluciones óptimas para λ ≥ 1.
5. Sea el problema de programación lineal siguiente
minimizar f (x) = x1 + x2 + 7x3 + 3x4 + x5 + 2x6 + x7
sujeta a
x1 + 2x2 − x3 − x4 + x5 + 2x6 + x7 = 16
x2 − 3x4 − x5 + 3x6 − x7 = 2
−x1 − 3x3 + 3x4 + x5 − x7 = −4
xi ≥ 0.
La variable x7 representa la cantidad de un determinado artı́culo; se rumorea que el gobierno legislará que la compañı́a sólo podrá fabricar un número determinado de unidades de este artı́culo. Ante
esta posibilidad, conviene hallar la solución para cualquier valor no negativo de x7 .
6. Análisis paramétrico de los siguientes problemas de programación lineal
a)
minimizar f (x) = x1 + 2x2 − x3 − 4x4 − x5 + 2x6 + x7
sujeta a
x1 + x2 + x3 + x5 = 9 − 2λ
x2 + x3 + x4 − x5 + 2x6 − x7 = 4 − λ
x1 + x2 + 2x3 + 2x4 + 2x5 + x6 + x7 = 5 − λ
xi ≥ 0.
b)
minimizar f (x) = 2x1 + 3x2 + 4x3 + 5x4
sujeta a
2x1 − x2 + x3 − x4 ≤ 2 − λ
x1 + 2x2 + x3 − x4 ≤ 10 − 2λ
x1 + x2 − 2x3 − x4 ≤ 3 + λ
xi ≥ 0.
Programación Matemática.
3
7. Análisis paramétrico del siguiente problema de programación lineal
minimizar f (x) = x1 + λx2 + µx3 + x4 + x5 + x6 + x7 + λx8 + µx9
sujeta a
x1 − x4 − 2x6 + 4x7 + 2x8 + x9 = 4
x2 + 2x4 − 2x5 + x6 + 2x7 + 4x8 = 2
x3 + x5 + x6 + x7 + 2x9 = 1
xi ≥ 0.
8. Un veterinario aconseja a un granjero dedicado a la crı́a de pollos una dieta mı́nima para la alimentación
de las aves compuesta de 3 unidades de hierro y 4 de vitaminas. El granjero sabe que cada kilo de
maı́z proporciona 2.5 unidades de hierro y 1 de vitaminas, cada kilo de harina de pescado contiene 3
unidades de vitaminas y cada kilo de cierto pienso sintético 1 unidad de hierro y 2 de vitaminas.
El granjero se pregunta por la composición de la dieta óptima que minimice el costo de la alimentación,
sabiendo que los precios del maı́z, harina de pescado y pienso sintético son de 0.12, 0.18 y 0.096 unidades
monetarias, respectivamente.
Comprobar si la solución sigue siendo válida en los siguientes casos:
a) El precio del kilo de maı́z pasa de 0.12 a 0.15 unidades monetarias.
b) El precio del kilo de harina de pescado se reduce a 0.12.
c) El precio del kilo de pienso sube hasta las 0.12 unidades monetarias.
d ) Aparece otro tipo de alimento cuyo precio es de 0.15 unidades monetarias y cuya composición es
2 unidadess de hierro y 2 de vitaminas.
e) Se hace necesario introducir un nuevo componente alimenticio de manera que las aves consuman
por lo menos una unidad. En cada kilo de los alimentos (maı́z, harina de pescado y pienso) se
encuentra una unidad del nuevo componente.
f ) La cantidad mı́nima de hierro se amplı́a a 5 unidades.
g) Las aves precisan consumir por lo menos 5 unidades de vitaminas.
h) Se presenta una variedad de maı́z que en cada kilo contiene 3 unidades de hierro y 1 de vitaminas
y que sigue costando 0.12 unidades por kg.
9. La empresa A se dedica al montaje de motocicletas de 500, 250, 125 y 50 cm3 de cilindrada unitaria. Posee una planta que está estructurada en cuatro departamentos: fabricación de chasis, pintura,
montaje y el departamento de control de calidad.
Las horas de mano de obra que necesita cada uno de los modelos de motocicletas en los diferentes
departamentos son los siguientes:
Mod.
Mod.
Mod.
Mod.
500
250
125
50
Chasis
8
6
4
2
Pintura
6
3
2
1
Montaje
8
8
6
4
Control de calidad
4
2
2
2
La distribución de los trabajadores es la siguiente:
El departamento de fabricación de chasis dispone de 25 trabajadores, el de pintura de 18, el de montaje
de 30 y el de calidad de 10. Todos los trabajadores realizan una jornada laboral de 8 horas.
Si el margen de beneficio de cada uno de los modelos es de 1200, 840, 480 y 240 u.m., respectivamente,
a) ¿cuál ha de ser la combinación óptima de motocicletas a producir para que el beneficio sea máximo?
Programación Matemática.
4
b) ¿Cuánto se estarı́a dispuesto a pagar por disponer de un operario más en sólo uno de los departamentos?
c) Obtener la solución óptima en los siguientes casos.
1) Se contrata un nuevo operario para la sección de verificación.
2) Se consigue reducir el número de horas empleadas en la construcción del chasis de las motocicletas de 125 cm3 pasando de 4 horas a 3.
3) En un nuevo avance tecnológico, la sección de construcción de chasis reduce el tiempo de
fabricación unitario de las motocicletas de 125 cm3 de 4 a 2 horas.
4) ¿Interesarı́a fabricar motocicletas de 125 cm3 si su beneficio unitario fuese de 540 unidades
monetarias?
5) El departamento de ventas informa que las motocicletas de 250 cm3 son invendibles al precio
actual y que para poder competir con las marcas rivales el precio deberı́a descender ¿en
qué cantidad? ¿cuál serı́a el beneficio neto unitario en ese caso?
10. Una compañı́a desea determinar el número de unidades mensuales de los productos P1 , P2 y P3 que
debe producir para maximizar sus beneficios totales. Para la elaboración de una unidad de cada uno de
los productos se precisa de dos recursos R1 y R2 . La cantidad de cada recurso disponible, la cantidad
de recurso que precisa cada unidad de producto y, el beneficio por unidad de producto se dan en la
siguiente tabla:
R1
R2
Beneficio/unidad
P1
0
2
2
P2
1
1
2
P3
2
1
4
Cantidad máxima
disponible
230
360
Además, por necesidades de mercado, la producción mensual conjunta de P1 y P2 debe ser de al menos
160 unidades.
a) Determinar qué cantidad de cada producto debe fabricarse con objeto de maximizar el beneficio.
b) ¿Cuánto puede variar la ganancia por unidad de producto P1 sin que se modifique la solución
óptima?
c) Diversos problemas en el suministro de R1 han reducido su disponibilidad a 50, ¿cuál es la nueva
solución óptima?
d ) Se está pensando una posible modificación de P2 que permitirı́a un aumento en su beneficio por
unidad, pasarı́a a ser de 3, pero que provocarı́a un cambio en la cantidad de cada uno de los
recursos consumidos, que serı́an ahora 1 y 2, respectivamente ¿Resultarı́a rentable llevar a cabo
las modificaciones?
e) ¿Cómo se modificarı́a la solución óptima si la cantidad de P1 no pudiera superar las 100 unidades?
f ) Cabe la posibilidad de fabricar un nuevo producto P4 , cuyo beneficio por unidad serı́a de 5, y
cuyo consumo de R1 y R2 serı́a de 4 y 1 unidades, respectivamente ¿Merece la pena fabricarlo?
11. Cierta empresa produce cuatro artı́culos diferentes utilizando los materiales A y B. Dada la distancia
entre el almacén proveedor y la empresa, el proveedor establece como condición para servir los materiales
que el consumo mı́nimo mensual de A y B debe ser de 5.600 y de 8.700 unidades.
La estructura del proceso productivo es la siguiente:
Material A
Material B
Producto 1
200
300
Producto 2
150
250
Producto 3
100
180
Producto 4
45
82
Programación Matemática.
5
El coste mı́nimo unitario es, respectivamente, de 90, 80, 50, 24.
¿Cuál debe ser la distribución de la producción para que los costes sean mı́nimos?
Realizar el análisis de postoptimación en los siguientes casos.
a) c1 = 85.
b) c2 = 90.
c) c3 = 45.
d ) c4 = 30.
e) Introducir una nueva variable x5 con coeficiente c5 = 75 y asociada al vector (200, 150).
f ) Introducir una nueva restricción: 100x1 + 80x2 + 70x3 + 40x4 ≥ 2500.
g) b1 = 5,000.
h) b2 = 9,000.
i ) a21 = 100.
12. Considérese una fábrica de cerveza que produce dos tipos distintos, negra (N) y rubia (R). Para su
obtención son necesarios, además de agua para la cual no hay limitación de disponibilidad, lúpulo,
malta y levadura.
La siguiente tabla muestra las unidades necesarias de cada uno de estos recursos escasos para producir
un litro de cada una de las respectivas cervezas, las unidades disponibles de cada recurso y el beneficio
por litro de cerveza producida.
El problema del fabricante consiste en decidir cuánto debe fabricar de cada cerveza para que el beneficio
sea máximo.
Recursos
Lúpulo
Malta
Levadura
Beneficio
Negra
1
3
3
5
Rubia
2
1
2
4
Disponibilidad
14
15
18
a) Hallar la estrategia óptima del fabricante.
b) Para ser competitivo, el fabricante debe bajar el precio de la cerveza negra. De esta forma el
beneficio por litro pasa a ser de 4 unidades monetarias. ¿Cuál es la solución óptima en esta nueva
situación?
c) Hay huelga de transportes y eso impide la llegada de malta a la fábrica. El fabricante tiene 8
unidades de malta de reserva. ¿Cuál debe ser ahora su polı́tica de fabricación?
d ) Se estropean las tuberı́as y el agua no se puede utilizar. El fabricante debe utilizar el agua de
una fuente cercana, pero para no pagar impuestos sólo puede coger 16 litros. Si la cerveza negra
necesita 1 unidad de agua y la rubia necesita 3 unidades, por litro, ¿cuál es la nueva solución?
e) Estudiar para qué valores de λ positivos la estrategia de producción se mantiene si el vector de
beneficios es ahora (5, 4) + λ(3, −4).
f ) Estudiar la variación de la solución para los valores positivos de λ si el vector de restricciones es
ahora (14, 15, 18) + λ(−1, 0, −3).
13. Una compañı́a desea determinar el número de unidades mensuales de los productos P1 , P2 y P3 que
debe producir para maximizar sus beneficios totales. Para la elaboración de una unidad de cada uno de
los productos se precisa de dos recursos R1 y R2 . La cantidad de cada recurso disponible, la cantidad
de recurso que precisa cada unidad de producto y, el beneficio por cada unidad de producto se dan en
la siguiente tabla:
Programación Matemática.
R1
R2
Beneficio/unidad
P1
0
2
2
6
P2
1
1
2
P3
2
1
4
Cantidad máxima
disponible
230
360
Además, por necesidades de mercado, la producción mensual conjunta de P1 y P2 debe ser de al menos
160 unidades.
a) Determinar qué cantidad de cada producto debe fabricarse con objeto de maximizar el beneficio.
b) ¿Cuánto puede variar la ganancia por unidad de producto P1 sin que se modifique la solución
óptima?
c) Diversos problemas en el suministro de R1 han reducido su disponibilidad a 50, ¿cuál es la nueva
solución óptima?
d ) Se está pensando una posible modificación de P2 que permitirı́a un aumento en su beneficio por
unidad, pasarı́a a ser de 3, pero que provocarı́a un cambio en la cantidad de cada uno de los
recursos consumidos, que serı́an ahora 1 y 2, respectivamente. ¿Resultarı́a rentable llevar a cabo
las modificaciones?
e) ¿Cómo se modificarı́a la solución óptima si la cantidad de P1 no pudiera superar las 100 unidades?
f ) Cabe la posibilidad de fabricar un nuevo producto P4 , cuyo beneficio por unidad serı́a de 5, y
cuyo consumo de R1 y R2 serı́a de 4 y 1 unidades, respectivamente ¿Merece la pena fabricarlo?
g) ¿Cuánto estarı́a dispuesta a pagar por disponer de una unidad más del recurso R2 ?
14. La siguiente formulación matemática describe el problema que tiene un fabricante al asignar tres
recursos a la producción anual de tres artı́culos. Denotamos por x1 , x2 y x3 las cantidades que se
producirán de cada uno de los artı́culos. La función objetivo refleja la contribución a la ganancia de
estos artı́culos.
Maximizar
f (x1 , x2 , x3 ) = 10x1 + 15x2 + 5x3
sujeta a
2x1 + x2 ≤ 6000
3x1 + 3x2 + x3 ≤ 9000
x1 + 2x2 + 2x3 ≤ 4000
x1 , x2 , x3 ≥ 0.
a) Verificar, usando el teorema de la holgura complementaria, que en la solución óptima las variables
básicas son x1 , x2 y la holgura de la primera restricción.
b) Construir la tabla simplex correspondiente a dicha solución sin resolver el problema por el simplex,
sólo usando la expresión matricial de una tabla del simplex.
c) El departamento de I+D propone la elaboración de un nuevo artı́culo cuyos coeficientes de producción en las restricciones son (2, 1, 0)T . Si la contribución a la ganancia por unidad de este nuevo
artı́culo es de 12$ ¿debe fabricarse este artı́culo? En caso afirmativo ¿cuál es la nueva solución
óptima?
d ) ¿Cuál es la contribución mı́nima a la ganancia que debe esperarse antes de que la producción de
este nuevo artı́culo incremente, de hecho, el valor de la función objetivo?