6 Curso 2004/05
Capı́tulo 2: Programación Lineal.
1. Dibuja en el plano la región que delimitan las restricciones siguientes:
x2 ≥ 0, 0 ≤ x1 ≤ 3, −x1 + x2 ≤ 1, x1 + x2 ≤ 4.
Para cada una de las funciones objetivo que siguen, encuentra en qué punto o puntos
se alcanza su valor máximo:
f1 = 2x1 + x2 , f2 = x1 + x2 , f3 = x1 + 2x2 .
2. Resuelve gráficamente los siguientes problemas:
a)
máx 2x1 + 6x2
s.a. −x1 + x2 ≤ 1,
2x1 + x2 ≤ 2,
x1 , x2 ≥ 0,
b)
máx −3x1 + 2x2
s.a. x1 + x2 ≤ 5,
0 ≤ x1 ≤ 4,
1 ≤ x2 ≤ 6.
3. Resolver
máx 4x1 + 2x2
(x1 ,x2 )∈Ω
siendo
Ω = (x1 , x2 ) ∈ R2 : x1 − 2x2 ≥ 2, x1 + 2x2 = 8, x1 − x2 ≤ 11, x1 ≥ 0
4. Estudiar para los distintos valores de k si el PPL
opt(x1 ,x2 )∈Ω x1 + kx2 ,
siendo
Ω = (x1 , x2 ) ∈ R2 : 3x1 + 2x2 ≥ 6, x1 + 6x2 ≥ 8, x1 , x2 ≥ 0 ,
tiene solución. En caso afirmativo decir si dicha solución es o no única (opt implica el
estudio del máximo y del mı́nimo).
5. Resolver el PPL
máx 2x1 + 3x2 + x3
(x1 ,x2, x3 )∈Ω
siendo Ω el subconjunto de R3 definido por las restricciones:
x1 + x2 + 2x3 ≤ 200, 3x1 + 2x2 + x3 ≤ 500, x1 + 2x2 + 3x3 ≤ 300,
x1 , x2 , x3 ≥ 0.
Capı́tulo 2: Programación Lineal. 7
6. Resolver
máx {3x1 + 2x2 − 2x3 }
(x1 ,x2 ,x3 )∈Ω
siendo
Ω = (x1 , x2 , x3 ) ∈ R3 : 4x1 + 2x2 + 2x3 ≤ 20, 2x1 + 2x2 + 4x3 ≥ 6, x1 , x2 ≥ 0 .
7. Encontrar el máximo de la función 240x1 + 104x2 + 60x3 + 19x4 sobre el conjunto
definido por las restricciones:
20x1 + 9x2 + 6x3 + x4 ≤ 20, 10x1 + 4x2 + 2x3 + x4 ≤ 10, x1 , x2 , x3 , x4 ≥ 0.
8. Se considera el problema
máx 1,1x1 + 1,2x2 + x3
sujeto a las restricciones:
2x1 + 2x2 + 2x3 ≤ 10, x1 + 3x2 + x3 ≤ 10 4x1 + x2 + x3 ≤ 10,
3x1 + x2 + 3x3 ≤ 10, x1 + 2x2 + 3x3 ≤ 10, 3x1 + 2x2 + x3 ≤ 10,
x1 , x2 , x3 ≥ 0.
Plantear y resolver su problema dual.
9. Determinar el valor máximo de la función coste 18x1 +4x2 +6x3 en el conjunto definido
por las restricciones:
3x1 + x2 ≤ −3, 2x1 + x3 ≤ −5, x1 , x2 , x3 ≤ 0.
10. En el transcurso de la resolución de un problema de programación lineal mediante el
método simplex se llega a la siguiente tabla:
c -3 -2 0 0 0
cB base x1 x2 x3 x4 x5 b
-3 x1 1 0 1 0 0 4
0 x4 0 0 5 1 -3 5
-2 x2 0 1 -2 0 1 2
z j − cj
Obtener la solución y el valor óptimo mediante iteración del método simplex.
11. Una empresa que produce banjos, guitarras y mandolinas utiliza madera, mano de
obra y metal en su construcción. Las cantidades de cada recurso que se precisan para
realizar una unidad de cada instrumento musical se muestran en la tabla siguiente:
Banjo Guitarra Mandolina
Madera 1 2 1
Mano de obra 1 2 2
metal 1 1 1
8 Curso 2004/05
La empresa dispone de 50 unidades de madera, 60 unidades de trabajo y 55 de metal,
y vende los banjos a 200¿, las guitarras a 175¿ y las mandolinas a 125¿. Se trata de
encontrar la cantidad a producir de cada instrumento para maximizar los beneficios
de la empresa. Para ello se pide:
a) Formular el problema como un PPL y encontrar la producción que maximiza los
beneficios.
b) Formular el dual de este problema y explicar su interpretación económica. Resolver
el problema dual, utilizando para ello la solución del problema primal. ¿Qué can-
tidad estarı́a dispuesta a pagar la empresa por una unidad adicional de madera?
¿Y de trabajo? ¿Y de metal?
12. Una pequeña central eléctrica consta de dos generadores. El primero proporciona unos
beneficios de 3¿/MWh con una potencia máxima de salida de 4 MWh, mientras que
el segundo genera unos beneficios de 5¿/MWh con una potencia máxima de 6 MWh.
Además el sistema debe ajustarse en todo momento de modo que la restricción requeri-
da por el sistema de refrigeración se cumpla: tres veces la potencia de salida del primer
generador más el doble de la del segundo no puede exceder en ningún caso 18 MWh.
¿Cuál es la potencia óptima de salida de cada generador que maximiza los beneficios?
13. Un constructor de cable eléctrico de alta calidad fabrica el cable a partir de dos tipos
de aleaciones metálicas, A y B. La primera contiene un 80 % de cobre y un 20 % de
aluminio, mientras que las segunda tiene un 68 % de cobre y un 32 % de aluminio. El
coste de la aleación A es de 80¿/Kg y el de B es de 60¿/Kg. ¿Qué cantidades de
aleaciones A y B tendrá que emplear el constructor para obtener 1 Kg. de cable que
no contenga más de un 25 % de aluminio y cuyo coste sea mı́nimo?
14. La producción de dos partes, A y B, de una determinada máquina requieren operar
en ellas mediante cinco procesos distintos L, S, D, M y G. Los tiempos que requieren
cada uno de estos procesos sobre cada parte vienen especificados en la tabla siguiente
(datos en horas por unidad)
Parte L S D M G
A 0.6 0.4 0.1 0.5 0.2
B 0.9 0.1 0.2 0.3 0.3
El número de procesos de cada clase disponible son: L, 10; S, 3; D, 4; M, 6; G, 5. Cada
uno de ellos puede usarse durante 8 horas diarias, 30 dı́as al mes. Se pide
a) Determinar el plan de producción para maximizar el número total de partes A y
B en un mes.
Capı́tulo 2: Programación Lineal. 9
b) Si el número de partes A debe ser igual al de B, ¿cuál serı́a el mejor plan de
producción?
15. Un inversor es propietario de 75 participaciones de la sociedad A, 100 participaciones
de B y 25 de C, cuyos precios actuales por participación son, 20¿, 2¿ y 100¿ respecti-
vamente. Supongamos que se puede predecir los dividendos que se pagarán al final del
perı́odo que empieza ahora, y los precios que tendrán las participaciones de acuerdo a
los siguientes datos: la sociedad A pagará 5¿ por participación, con un nuevo precio
de 18¿; la sociedad B no pagará dividendos y su nuevo precio será de 3¿, y la sociedad
C pagará 2¿ en dividentos y tendrá un precio de 102¿ al final del perı́odo. Se sabe
además que
no se dispone de dinero adicional para invertir,
para contrarrestar la inflación, el valor total al final del perı́odo debe ser como
mı́nimo un 5 % mayor que el valor actual,
se prefiere una cartera equilibrada en el sentido de que el precio de cada valor
actual después del ajuste represente al menos el 25 % del precio total actual de la
cartera,
el número de participaciones no puede ser negativo.
Se trata de decidir qué opción tomar con la presente cartera de valores para, lógica-
mente, maximizar los beneficios.