PROGRAMACIÓN LINEAL INFINITAS SOLUCIONES RICARDO TRUJILLO PÉREZ
1
PROBLEMAS DE PROGRAMACIÓN LINEAL CON INFINITAS SOLUCIONES
1. Una empresa constructora de barcos fabrica en sus dos astilleros tres tipos de barcos: A, B y C. Se compromete a entregar anualmente a cierta compañía marítima 18 barcos de tipo A, 10 del tipo B y 6 del tipo C. El primer astillero construye mensualmente 3 barcos tipo A, 2 tipo B y 1 tipo C, siendo el costo mensual de su funcionamiento de 60.000 €, y el segundo astillero construye mensualmente 2 barcos tipo A, 1 tipo B y 2 tipo C, siendo el costo mensual de su funcionamiento de 30.000 €. ¿Cuántos meses al año deberá trabajar cada astillero para que la empresa cumpla con el compromiso adquirido y consiga reducir al mínimo el costo de funcionamiento?
JUNIO 94
SOLUCIÓN
Primero agrupamos los datos en una pequeña tabla:
A B C COSTE M.
ASTILLERO I 3 u. 2 u. 1 u. 60.000 €
ASTILLERO II 2 u. 1 u. 2 u. 30.000 €
PRODUCCIÓN MÍNIMA
18 u. 10 u. 6 u.
A continuación planteamos el problema:
Sea IIastilleromesesdeNúmeroy
IastilleromesesdeNúmerox
.
Se trata de: Minimizar yxz 3060 (miles de €) sujeto a las siguientes restricciones:
A continuación representamos las rectas fronteras de los semiplanos solución para determinar la región factible. Para ello calculamos un par de puntos de cada una de ellas.
00
62
102
1823
yx
yx
yx
yx
)3,0()0,6(62
)10,0()0,5(102
)9,0()0,6(1823
yyx
yyx
yyx
PROGRAMACIÓN LINEAL INFINITAS SOLUCIONES RICARDO TRUJILLO PÉREZ
2
Seguidamente las representamos y determinamos la región factible que será la intersección de los semiplanos solución indicados por los sentidos de las flechas (ver figura).
Por último, hallamos los vértices de la región factible y evaluamos la función objetivo en cada uno de ellos. Sus vértices son los puntos:
A(0,10) B )6,2(102
1823B
yx
yx
C(6,0)
Evaluando obtenemos que: €000.300AZ €000.300BZ €000.360CZ . Así
pues, el coste mínimo se da en dos vértices consecutivos de la región factible. Por ello el problema tiene infinitas soluciones matemáticas óptimas, todos los puntos del segmento AB (la dirección de la función objetivo es paralela a dicho segmento). Para evitar soluciones con decimales que no tendrían mucho sentido en el contexto del problema, vamos a determinar los puntos del segmento AB con coordenadas enteras. Como dicho segmento está contenido en la recta de ecuación 2x + y = 10, calculamos los puntos de coordenadas enteras de dicha recta comprendidos entre A(0,10) y B(2,6). Son los puntos: A(0,10), C(1,8) y B(2,6). Así pues, tenemos tres soluciones:
0 meses de funcionamiento del astillero I y 10 meses en el II.
1 mes de funcionamiento del astillero I y 8 meses en el II.
2 meses de funcionamiento del astillero I y 6 meses en el II.
En los tres casos el coste es de 300.000 €.
PROGRAMACIÓN LINEAL INFINITAS SOLUCIONES RICARDO TRUJILLO PÉREZ
3
2. Un laboratorio prepara dos fármacos con las sustancias A y B. El primero se prepara con 2 unidades de A y 1 de B, siendo su precio de 30 € y el segundo con 1 unidad de A y 3 de B, siendo su precio de 15 €. Sabiendo que el laboratorio dispone de un total de 70 unidades de A y 60 de B, ¿cuántos fármacos de cada tipo deberá preparar con objeto de obtener el beneficio máximo? Justificar la respuesta.
JUNIO 95
SOLUCIÓN
Primero agrupamos los datos en una pequeña tabla:
FÁRMACO I FÁRMACO II DISPONIBILIDAD MÁXIMA
SUSTANCIA A 2 u. 1 u. 70 u.
SUSTANCIA B 1 u. 3 u. 60 u.
BENEFICIO 30 € 15 €
A continuación planteamos el problema:
Sea IItipofármadeNúmeroy
ItipofármadeNúmerox
cos
cos
.
Se trata de: Maximizar yxz 1530 sujeto a las siguientes restricciones:
A continuación representamos las rectas fronteras de los semiplanos solución para determinar la región factible. Para ello calculamos un par de puntos de cada una de ellas.
Seguidamente las representamos y determinamos la región factible que será la
intersección de los semiplanos solución indicados por los sentidos de las flechas (ver
figura).
00
603
702
yx
yx
yx
)20,0()0,60(603
)70,0()0,35(702
yyx
yyx
PROGRAMACIÓN LINEAL INFINITAS SOLUCIONES RICARDO TRUJILLO PÉREZ
4
Por último, hallamos los vértices de la región factible y evaluamos la función objetivo en cada uno de ellos. Sus vértices son los puntos:
A(0,0) B(0,20) C )10,30(702
603C
yx
yx
D(35,0)
Evaluando obtenemos que: €0AZ €300BZ €050.1CZ y €050.1DZ .
Así pues, el beneficio máximo se da en dos vértices consecutivos de la región factible. Por ello el problema tiene infinitas soluciones matemáticas óptimas, todos los puntos del segmento CD (la dirección de la función objetivo es paralela a dicho segmento). Para evitar soluciones con decimales que no tendrían mucho sentido en el contexto del problema, vamos a determinar los puntos del segmento CD con coordenadas enteras. Como dicho segmento está contenido en la recta de ecuación 2x + y = 70, calculamos los puntos de coordenadas enteras de dicha recta comprendidos entre C(30,10) y D(35,0). Son los puntos: (30,10), (31,8), (32,6), (33,4), (34,2) y (35,0). Así pues, tenemos seis soluciones:
30 fármacos de tipo I y 10 de tipo II.
31 fármacos de tipo I y 8 de tipo II.
32 fármacos de tipo I y 6 de tipo II.
33 fármacos de tipo I y 4 de tipo II.
34 fármacos de tipo I y 2 de tipo II.
PROGRAMACIÓN LINEAL INFINITAS SOLUCIONES RICARDO TRUJILLO PÉREZ
5
35 fármacos de tipo I y 0 de tipo II. En todos los casos el beneficio es de 1.050 €.
3. Un taller fabrica lavadoras y lavavajillas con una producción diaria máxima total de 180 unidades. El beneficio obtenido con la producción y venta de cada lavadora o lavavajillas es de 50 €. Sabiendo que por las limitaciones de la cadena de montaje no es posible fabricar diariamente más de 150 lavadoras ni más de 80 lavavajillas, se pide:
a) Determinar la producción de cada artículo a fin de obtener un beneficio máximo, teniendo en cuenta que el número de lavadoras ha de ser como mínimo el doble que el de lavavajillas, con objeto de poder atender a la demanda existente. b) ¿Cuál será el valor de dicho beneficio?
SEPTIEMBRE 96
SOLUCIÓN
Primero agrupamos los datos en una pequeña tabla:
LAVADORAS LAVAVAJILLAS
PRODUCIÓN DIARIA
MÁXIMA
180
150 80
BENEFICIOS 50 € 50 €
RESTRICCIÓN PRODUCCIÓN
Nº LAVADORAS ≥ 2· Nº LAVAVAJILLAS
A continuación planteamos el problema:
Sea aslavavajilldeNúmeroy
lavadorasdeNúmerox
.
Se trata de: Maximizar yxz 5050 sujeto a las siguientes restricciones:
180
150
022
800,
yx
x
yxyx
yyx
PROGRAMACIÓN LINEAL INFINITAS SOLUCIONES RICARDO TRUJILLO PÉREZ
6
A continuación representamos las rectas fronteras de los semiplanos solución para determinar la región factible. Para ello calculamos un par de puntos de cada una de ellas. Seguidamente las representamos y determinamos la región factible que será la intersección de los semiplanos solución indicados por los sentidos de las flechas (ver figura).
Por último, hallamos los vértices de la región factible y evaluamos la función objetivo en cada uno de ellos. Sus vértices son los puntos:
A )0,0(0
0A
yx
x
B )60,120(
180
02B
yx
yx
C )30,150(
180
150C
yx
x
D )0,150(150
0D
x
y
Evaluando obtenemos que: €0AZ €000.9BZ €000.9CZ €500.7DZ .
Así pues, el beneficio máximo se da en dos vértices consecutivos de la región factible. Por ello el problema tiene infinitas soluciones matemáticas óptimas, todos los puntos
)180,0()0,180(180
)50,100()0,0(02
yyx
yyx
PROGRAMACIÓN LINEAL INFINITAS SOLUCIONES RICARDO TRUJILLO PÉREZ
7
del segmento BC (la dirección de la función objetivo es paralela a dicho segmento). Para evitar soluciones con decimales que no tendrían mucho sentido en el contexto del problema, vamos a determinar los puntos del segmento BC con coordenadas enteras. Como dicho segmento está contenido en la recta de ecuación x + y = 180, calculamos los puntos de coordenadas enteras de dicha recta comprendidos entre B(120,60) y C(150,30). Son los puntos: (120,60), (121,59), (122,58), (123,57), (124,56), ……………(149,31) y (150,30). Así pues, tenemos treinta y una soluciones:
120 lavadoras y 60 lavavajillas.
121 lavadoras y 59 lavavajillas.
122 lavadoras y 58 lavavajillas.
……………………………………
……………………………………
149 lavadoras y 31 lavavajillas.
150 lavadoras y 30 lavavajillas. En todos los casos el beneficio es de 9.000 €.
4. Un matadero industrial sacrifica diariamente cerdos, corderos y terneros. Para ello dispone de dos líneas de trabajo. En la primera se sacrifican y despiezan cada hora 3 cerdos, 4 corderos y 1 ternero y en la segunda también cada hora 6 cerdos, 2 corderos y 1 ternero, siendo el coste por hora de la primera línea 100 € y de la segunda 200 €. Sabiendo que el mercado de la ciudad necesita cada día para su abastecimiento 30 cerdos, 20 corderos y 8 terneros, se pide: a) ¿Qué número de horas debe funcionar cada línea para abastecer cada día el mercado con un coste mínimo? b) ¿Cuál será el valor de dicho coste mínimo? Justificar las respuestas.
SEPTIEMBRE 2001 OP B
SOLUCIÓN
Primero agrupamos los datos en una pequeña tabla:
A continuación planteamos el problema:
CERDOS CORDEROS TERNERAS COSTE
LÍNEA A 3 4 1 100 €
LÍNEA B 6 2 1 200 €
ABASTECIMIENTO MÍNIMO
30 20 8
PROGRAMACIÓN LINEAL INFINITAS SOLUCIONES RICARDO TRUJILLO PÉREZ
8
SeaBlíneahorasdeNúmeroy
AlíneahorasdeNúmerox
.
Se trata de minimizar yxz 200100 sujeto a las siguientes restricciones:
A continuación representamos las rectas fronteras de los semiplanos solución para determinar la región factible. Para ello calculamos un par de puntos de cada una de ellas. Seguidamente las representamos y determinamos la región factible que será la intersección de los semiplanos solución indicados por los sentidos de las flechas (ver figura). Por último, hallamos los vértices de la región factible y evaluamos la función objetivo en cada uno de ellos. Sus vértices son los puntos:
00
8
2024
3063
yx
yx
yx
yx
)8,0()0,8(8
)10,0()0,5(2024
)5,0()0,10(3063
yyx
yyx
yyx
PROGRAMACIÓN LINEAL INFINITAS SOLUCIONES RICARDO TRUJILLO PÉREZ
9
A )10,0(2024
0A
yx
x
B )6,2(
2024
8B
yx
yx
C )2,6(
3063
8C
yx
yx
D )0,10(0
3063D
y
yx
Evaluando obtenemos que:
€000.2AZ €400.1BZ €000.1CZ €000.1DZ .
Así pues, el coste mínimo se da en dos vértices consecutivos de la región factible. Por ello el problema tiene infinitas soluciones matemáticas óptimas, todos los puntos del segmento CD (la dirección de la función objetivo es paralela a dicho segmento). Para evitar soluciones con decimales que no tendrían mucho sentido en el contexto del problema, vamos a determinar los puntos del segmento CD con coordenadas enteras. Como dicho segmento está contenido en la recta de ecuación 3x + 6y = 30, calculamos los puntos de coordenadas enteras de dicha recta comprendidos entre C(6,2) y D(10,0). Son los puntos: C(6,2), E(8,1) y D(10,0). Así pues, tenemos tres soluciones:
6 horas de funcionamiento en la línea A y 2 la B.
8 horas de funcionamiento en la línea A y 1 la B.
10 horas de funcionamiento en la línea A y 0 la B. En los tres casos el coste es de 1.000 €.
5. Una constructora dispone de 90000 𝒎𝟐 para construir viviendas en parcelas
de 300 𝒎𝟐 y de 500 𝒎𝟐 . Los beneficios obtenidos son de 18.000 euros por
cada parcela de 300𝒎𝟐 y de 30.000 euros por cada parcela de 500 𝒎𝟐.
Teniendo en cuenta que el número máximo de parcelas de 500 𝒎𝟐 es de 120
y que el número máximo de parcelas de 300 𝒎𝟐 es de 150, determinar: a) ¿Cuántas parcelas de cada tipo deberá construir para obtener unos beneficios máximos? b) ¿Cuál será el valor de dichos beneficios máximos? Justificar las respuestas.
JUNIO 2003 SOLUCIÓN
Primero agrupamos los datos en una pequeña tabla:
PROGRAMACIÓN LINEAL INFINITAS SOLUCIONES RICARDO TRUJILLO PÉREZ
10
PARCELAS DE 300 2m PARCELAS DE 500 2m
BENEFICIOS 18.000 € 30.000 €
DISPONIBILIDAD MÁXIMA
150 p 120 p
90000 2m
A continuación planteamos el problema:
Sea 2
2
500
300
mdeparcelasdeNúmeroy
mdeparcelasdeNúmerox
.
Se trata de maximizar yxz 000.30000.18 sujeto a las siguientes restricciones:
A continuación representamos las rectas fronteras de los semiplanos solución para determinar la región factible. Para ello calculamos un par de puntos de cada una de ellas.
3𝑥 + 5𝑦 = 900 → (300,0)𝑦 (0,180)
Seguidamente las representamos y determinamos la región factible que
será la intersección de los semiplanos solución indicados por los sentidos de las
flechas (ver figura).
Por último,
hallamos los vértices de la región factible y evaluamos la función objetivo en cada uno de ellos. Sus vértices son los puntos:
x
x
yx
y
0
150
90053
1200
PROGRAMACIÓN LINEAL INFINITAS SOLUCIONES RICARDO TRUJILLO PÉREZ
11
A )0,0(0
0A
y
x
B )120,0(
120
0B
y
x
C )120,100(
90053
120C
yx
y
D )90,150(150
90053D
x
yx
150
0
x
yE )0,150(E
Evaluando obtenemos que: €0AZ €000.600.3BZ €000.400.5CZ
€000.400.5DZ €000.700.2EZ .
Así pues, el beneficio máximo se da en dos vértices consecutivos de la región factible. Por ello el problema tiene infinitas soluciones matemáticas óptimas, todos los puntos del segmento CD (la dirección de la función objetivo es paralela a dicho segmento). Para evitar soluciones con decimales que no tendrían mucho sentido en el contexto del problema, vamos a determinar los puntos del segmento CD con coordenadas enteras. Como dicho segmento está contenido en la recta de ecuación 3x + 5y = 900, calculamos los puntos de coordenadas enteras de dicha recta comprendidos entre C(100,120) y D(150,90). Son los puntos: (100,120), (105,117), (110,114), (115,111), (120,108), (125,105), (130,102), (135,99), (140,96), (145,93) y (150,90). Así pues, tenemos once soluciones:
100 parcelas de 300 𝑚2 y 120 parcelas de 500 𝑚2.
105 parcelas de 300 𝑚2 y 117 parcelas de 500 𝑚2.
110 parcelas de 300 𝑚2 y 114 parcelas de 500 𝑚2.
……………………………………………………
……………………………………………………
145 parcelas de 300 𝑚2 y 93 parcelas de 500 𝑚2.
150 parcelas de 300 𝑚2 y 90 parcelas de 500 𝑚2. En todos los casos el beneficio es de 5.400.000 €.
6. Una tienda de artículos de piel necesita para su próxima campaña un
mínimo de 80 bolsos, 120 pares de zapatos y 90 cazadoras. Se abastece de los artículos en dos talleres: A y B. El taller A produce diariamente 4 bolsos, 12 pares de zapatos y 2 cazadoras con un coste diario de 360 euros. La producción diaria del taller B es de 2 bolsos, 2 pares de zapatos y 6 cazadoras siendo su coste de 180 euros cada día. Determinar, justificando la respuesta:
a) El número de días que debe trabajar cada taller para abastecer a la tienda con el mínimo coste. b) El valor de dicho coste mínimo.
SEPTIEMBRE 2007 OP B SOLUCIÓN
Primero agrupamos los datos en una pequeña tabla:
PROGRAMACIÓN LINEAL INFINITAS SOLUCIONES RICARDO TRUJILLO PÉREZ
12
A continuación planteamos el problema:
Sea Btallertrabajadosdíasy
Atallertrabajadosdíasx
.
Se trata de minimizar yxz 180360 sujeto a las siguientes restricciones:
9062
120212
8024
00
yx
yx
yx
yx
, que simplificando se reducen a:
453
606
402
00
yx
yx
yx
yx
.
A continuación representamos las rectas fronteras de los semiplanos solución para determinar la región factible. Para ello calculamos un par de puntos de cada una de ellas.
)15,0()0,45(453
)60,0()0,10(606
)40,0()0,20(402
yyx
yyx
yyx
Seguidamente las representamos y determinamos la región factible que será la intersección de los semiplanos solución indicados por los sentidos de las flechas.
BOLSOS ZAPATOS CAZADORAS COSTE
TALLER A 4 12 2 360 €
TALLER B 2 2 6 180 €
PRODUCCIÓN MÍNIMA
80 120 90
PROGRAMACIÓN LINEAL INFINITAS SOLUCIONES RICARDO TRUJILLO PÉREZ
13
Por último, hallamos los vértices de la región factible y evaluamos la función objetivo en cada uno de ellos. Sus vértices son los puntos:
B )60,0(606
0B
yx
x
C )30,5(
606
402C
yx
yx
H )10,15(
453
402H
yx
yx
F )0,45(453
0F
yx
y
Evaluando obtenemos que: €800.10BZ €200.7CZ €200.7HZ
€200.16FZ .
Así pues, el coste mínimo se da en dos vértices consecutivos de la región factible. Por ello el problema tiene infinitas soluciones matemáticas óptimas, todos los puntos del segmento CH (la dirección de la función objetivo es paralela a dicho segmento). Para evitar soluciones con decimales que no tendrían mucho sentido en el contexto del problema, vamos a determinar los puntos del segmento CH con coordenadas enteras. Como dicho segmento está contenido en la recta de ecuación 2x + y = 40, calculamos los puntos de coordenadas enteras de dicha recta comprendidos entre C(5,30) y H(15,10). Son los puntos: (5,30), (6,28), (7,26), (8,24), (9,22), (10,20), (11,18), (12,16), (13,14), (14,12) y (15,10). Así pues, tenemos once soluciones:
PROGRAMACIÓN LINEAL INFINITAS SOLUCIONES RICARDO TRUJILLO PÉREZ
14
5 días trabajados en el taller A y 30 en el B.
6 días trabajados en el taller A y 28 en el B.
7 días trabajados en el taller A y 26 en el B.
……………………………………………………
……………………………………………………
14 días trabajados en el taller A y 12 en el B.
15 días trabajados en el taller A y 10 en el B. En todos los casos el coste es de 7.200 €.