problemas de programaciÓn lineal con infinitas …

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


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 €.


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


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 €


Sea IItipofármadeNúmeroy

ItipofármadeNúmerox

cos

cos

.

Se trata de: Maximizar yxz 1530 sujeto a las siguientes restricciones:


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


4


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.






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


LAVADORAS LAVAVAJILLAS

PRODUCIÓN DIARIA

MÁXIMA

180

150 80

BENEFICIOS 50 € 50 €

RESTRICCIÓN PRODUCCIÓN

Nº LAVADORAS ≥ 2· Nº LAVAVAJILLAS


Sea aslavavajilldeNúmeroy

lavadorasdeNúmerox

.

Se trata de: Maximizar yxz 5050 sujeto a las siguientes restricciones:

180

150

022

800,

yx

x

yxyx

yyx


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).


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


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.



……………………………………

……………………………………


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



CERDOS CORDEROS TERNERAS COSTE

LÍNEA A 3 4 1 100 €

LÍNEA B 6 2 1 200 €

ABASTECIMIENTO MÍNIMO

30 20 8


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


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



10

PARCELAS DE 300 2m PARCELAS DE 500 2m

BENEFICIOS 18.000 € 30.000 €

DISPONIBILIDAD MÁXIMA

150 p 120 p

90000 2m


Sea 2

2

500

300

mdeparcelasdeNúmeroy

mdeparcelasdeNúmerox

.

Se trata de maximizar yxz 000.30000.18 sujeto a las siguientes restricciones:


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


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.



……………………………………………………

……………………………………………………


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



12


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

.


)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


13


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:


14

5 días trabajados en el taller A y 30 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 €.

problemas de programaciÓn lineal con infinitas …

Documents