TEMA IV.- PROGRAMACIÓN LINEAL

TEMA IV.- PROGRAMACIÓN LINEAL

EJEMPLO DE REGIONES FACTIBLES ACOTADAS (CERRADAS)

EJEMPLO:

Representa la región definida por el siguiente sistema de inecuaciones:

0x ; 3y ; 10 yx ; xy 32

Averigua en que puntos se hace máxima y mínima la función yxyxF 34, .

Solución:

Hace máxima la función el punto (4,6).

Hace mínima la función el punto (0,3).

EJEMPLO:

Representa el recinto definido por el siguiente sistema de inecuaciones:

0x ; 0y ; 10x ; yx ; 62 xy ; 3543 yx

¿En qué punto la función yxyxF 1510, alcanza el valor máximo?

Solución:

La función alcanza el valor máximo en el punto C(1,8).

EJEMPLO:

Maximizar la función yxyxf 2, sujeto a las siguientes restricciones:

0

0

102

82

y

x

yx

yx

.

Solución:

La región factible es la siguiente:

Los vértices de la región factibles son (0,4), (0,10) y (4,2).

La función objetivo es yxyxf 2, , por lo tanto se tiene que:

8804204,0 f

20200102010,0 f

0442242,4 f

Por lo tanto esta función, con las restricciones dadas es máxima en el punto (4,2) y dicho valor

máximo es 0.

EJEMPLO:

Maximizar la función yxyxf , sujeto a las siguientes restricciones:

0

0

632

62

y

x

yx

yx

.

Solución:


Los vértices de la región factible son: A(0,0), B(0,-2), C(6/7,-18/7) y D(6,0).

Como la función objetivo es yxyxf , , se tiene que:

0000,0 f

2202,0 f

7

12

7

18

7

6

7

18,

7

6

f

6060,6 f

Con lo cual, con las restricciones dadas, el máximo valor de la función es 6 y dicho máximo se

alcanza en el punto (6,0)

EJEMPLO:


0

0

3046

0

122

y

x

yx

yx

yx

.

Solución:


Los vértices de la región factible son: A(3,3), B(3/2,21/4) y C(4,4).

Como la función objetivo es yxyxf 42, , se tiene que:

1812634323,3 f

242134

214

2

32

4

21,

2

3

f

2416844424,4 f

Por lo tanto, con las restricciones dadas, el valor máximo de la función dada es 24, y dicho

valor máximo se encuentra en todos los puntos que unen el segmento de extremos (3/2,21/4) y

(4,4) ambos puntos incluidos.

EJEMPLO DE REGIONES FACTIBLES NO ACOTADAS (NO CERRADAS)

EJEMPLO:

Dada la región del plano determinada por el sistema de inecuaciones siguiente:

0

102

632

6

x

yx

yx

yx

Determinar, si existen, los puntos donde las siguientes funciones, sujetas al conjunto de

restricciones anteriores, alcanzan sus valores máximo y mínimo.

a) yxyxf 3, ; b) yxyxf 2, , c) yxyxf 2, ; d) yxyxf 2, .

Solución:


Como se observa la región factible es no acotada (no cerrada) y los vértices de la región

factible son:

A (6,2) que es el punto de intersección de las rectas 2x-3y=6 y x+2y=10.

B (2,4) que es el punto de intersección de las rectas x+y=6 y x+2y=10.

C (0,0) que es el punto de intersección de las rectas x+y=6 y x=0.

a) Como la función objetivo es yxyxf 3, , tenemos que:

12662362,6 f

161224324,2 f

181806306,0 f

aaaf 3,

3,f

Por lo tanto tenemos que la función no tiene máximo y tiene mínimo en el punto (6,2) y dicho

mínimo vale 12.

Otra forma de ver esto es gráficamente teniendo en cuenta las rectas de nivel.

b) Como la función objetivo es yxyxf 2, , tenemos que:

2462262,6 f

6824224,2 f

121206206,0 f

aaaf 2,

2,f

Por lo tanto tenemos que la función no tiene mínimo y tiene máximo en el punto (6,2) y dicho

máximo vale 2.


c) Como la función objetivo es yxyxf 2, , tenemos que:

102122622,6 f

0444224,2 f

6606026,0 f

aaf 2,

2,f

Por lo tanto tenemos que la función no tiene mínimo ni máximo.


d) Como la función objetivo es yxyxf 2, , tenemos que:

10462262,6 f

10824224,2 f

121206206,0 f

aaaf 2,

2,f

Por lo tanto tenemos que la función no tiene máximo y tiene infinitos mínimos que son los

puntos (2,4), (6,2) y los infinitos puntos del segmento que une los puntos (2,4) y (6,2).


EJEMPLO:

Dada la región del plano determinada por el sistema de inecuaciones siguiente:

0

182

122

x

yx

yx

yx

Determinar, si existen, los puntos donde las siguientes funciones, sujetas al conjunto de

restricciones anteriores, alcanzan sus valores máximo y mínimo.

a) yxyxf 32, ; b) yxyxf 3, , c) yxyxf 3, ; d) yxyxf 2, .

Solución:


Como se observa la región factible es no acotada (no cerrada) y los vértices de la región

factible son:

A (0,0) que es el punto de intersección de las rectas y=x y x=0.

B (4,4) que es el punto de intersección de las rectas y=x y x+2y=12.

C (8,2) que es el punto de intersección de las rectas x+2y=12 y 2x+y=18.

a) Como la función objetivo es yxyxf 32, , tenemos que:

00003020,0 f

2012843424,4 f

2261623822,8 f

aaaf 232,

32,f

Por lo tanto tenemos que la función no tiene mínimo y tiene máximo en el punto (8,2) y dicho

máximo vale 22.


b) Como la función objetivo es yxyxf 3, , tenemos que:

0000300,0 f

81244344,4 f

2662382,8 f

aaaf 3,

3,f

Por lo tanto tenemos que la función no tiene máximo y tiene mínimo en el punto (4,4) y dicho

mínimo vale -8.


c) Como la función objetivo es yxyxf 3, , tenemos que:

0000030,0 f

164124434,4 f

262242832,8 f

aaaf 33,

3,f

Por lo tanto tenemos que la función no tiene mínimo ni máximo.


d) Como la función objetivo es yxyxf 2, , tenemos que:

0000200,0 f

12844244,4 f

12482282,8 f

aaaf 2,

2,f

Por lo tanto tenemos que la función no tiene mínimo y tiene infinitos máximos que son los

puntos (4,4), (8,2) y los infinitos puntos del segmento que une los puntos (4,4) y (8,2).


EJEMPLO:


42

82

63

yx

yx

yx

.

Solución:


Los vértices de la región factible son A(0,2) y B(4,0).

Como la función objetivo es yxyxf 63, , se tiene que:

1212026032,0 f

1201206430,4 f

Por lo tanto, con las restricciones dadas, el máximo valor que toma la función es 12 y dicho

valor máximo se produce en todos los puntos del segmento (0,2) y (4,0), ambos puntos

incluidos.

EJEMPLO:


0

0

4

255

y

x

yx

yx

.

Solución:


Como la región factible no existe ya que no hay ningún punto que verifique todas las

restricciones no podemos hallar el máximo de esta función con estas restricciones.

EJEMPLO:


0

0

4

82

123

y

x

yx

yx

yx

.

Solución:

Como la región factible no está acotada superiormente, entonces esta función no alcanza el

máximo ya que, con estas restricciones, su máximo sería infinito.

PROBLEMAS DE PROGRAMACIÓN LINEAL.-

EJEMPLO:

Disponemos de 90.000 metros cuadrados para construir parcelas de 3.000 y 5.000 metros

cuadrados, tipos A y B respectivamente. Los beneficios son de 10.000 € por cada parcela A y

de 20.000 € por cada parcela B. El número máximo de parcelas B es de 120, y el de parcelas A,

150.

Determinar cuántas parcelas de cada tipo necesitamos para obtener beneficios máximos.

Solución:

Sea x el número de parcelas, que necesitamos, de tipo A.

Sea y el número de parcelas, que necesitamos, de tipo B.

La función objetivo, que queremos maximizar, es yxyxB 000.20000.10, .

Las restricciones son las siguientes:

0

0

150

120

000.90000.5000.3

y

x

x

y

yx

0

0

150

120

9053

y

x

x

y

yx


Los vértices de la región factible son (0,0), (0,18) y (30,0).

Como la función objetivo es yxyxB 000.20000.10, , entonces se tiene que:

0000000.200000.100,0 B

000.360000.360018000.200000.1018,0 B

000.3000000.3000000.2030000.100,30 B

Por lo tanto para que los beneficios sean máximos necesitamos 18 parcelas de tipo B y

ninguna parcela de tipo A y dichos beneficios máximos serán de 360.000 €.

EJEMPLO:

Vamos a invertir en dos productos financieros A y B. La inversión en A será, al menos de

3.000 € y no se invertirá en A más del doble que en B. El producto A proporciona un beneficio

del 10% y B del 5%.

Si disponemos de un máximo de 12.000 €, ¿cuánto se debe invertir en cada producto para

maximizar el beneficio?

Solución:

Sean x los euros que vamos a invertir en el producto financiero A.

Sean y los euros que vamos a invertir en el producto financiero B.

La función objetivo, que queremos maximizar, es yxyxB 05,01,0, .

Las restricciones son las siguientes:

0

000.12

2

000.3

y

yx

yx

x



Como0 la función objetivo es yxyxB 05,01,0, , entonces se tiene que:

37575300150005,030001,01500,3000 B

750450300900005,030001,09000,3000 B

1000200800400005,080001,04000,8000 B

Para que los beneficios sean máximos hay que invertir 8.000 € en el producto A y 4.000 € en el

producto B y dicho beneficio máximo será de 1.000 €.

EJEMPLO:

Se fabrican dos tipos de aparatos A y B en los talleres X e Y. En cada uno de los talleres se

trabajan 100 horas a la semana. Cada aparato A requiere 3 horas del taller X y 1 hora del

taller Y, y cada aparato de B, 1 y 2 horas, respectivamente. Cada aparato A se vende a 100 € y

cada aparato B a 150 €. Calcula el número de aparatos de cada tipo que hay que producir

para que la facturación sea máxima.

Solución:

Sean x el número de aparatos del tipo A que hay que producir.

Sean y el número de aparatos del tipo B que hay que producir.

La función objetivo, que hay que maximizar, es yxyxF 150100, .

Las restricciones son:

0

0

1002

1003

y

x

yx

yx


Los vértices de la región factible son (0,0), (0,50), (20,40) y (100/3,0)

Como la función objetivo es yxyxF 150100, , se tiene que:

000015001000,0 F

75007500050150010050,0 F

800060002000401502010040,20 F

3

100000

3

100000150

3

1001000,

3

100

F

Para que la facturación sea máxima hay que producir 20 aparatos del tipo A y 40 aparatos del

tipo B Y dicha facturación máxima será de 8.000 €.

EJEMPLO:

Tenemos 120 refrescos de naranja y 180 de limón. Se venden en paquetes de dos tipos: los

paquetes de tipo A contienen 3 refrescos de naranja y 3 de limón, y los del tipo B contienen 2

refrescos de naranja y 4 de limón. El beneficio es de 6 € por cada paquete de tipo A y de 5 €

por cada paquete de tipo B. Hallar cuántos paquetes de cada tipo hay que vender para

maximizar los beneficios.

Solución:

Sean x el número de paquetes del tipo A que hay que vender.

Sean y el número de paquetes del tipo A que hay que vender.

La función objetivo, que queremos que sea máxima, nos viene dada por yxyxB 56, .


0

0

18043

12023

y

x

yx

yx

La región factible es:

Los vértices de la región factible son (0,0), (0,45), (20,30) y (40,0).

Como la función objetivo, que queremos maximizar, es yxyxB 56, , se tiene que:

00005060,0 B

22522504550645,0 B

27015012030520630,20 B

2400240054060,40 B

Para que los beneficios sean máximos hay que vender 20 paquetes del tipo A y 30 paquetes del

tipo B y dichos beneficios máximos serán de 270 €.

EJEMPLO:

Una fábrica elabora dos tipos de productos A y B. El tipo A necesita 2 obreros trabajando un

total de 20 horas y se obtiene un beneficio de 1.500 € por unidad. El tipo B necesita 3 obreros

con un total de 10 horas y el beneficio es de 1.000 € por unidad. Si disponemos de 60 obreros y

480 horas de trabajo, determina la cantidad de unidades de A y de B que se deben fabricar

para maximizar el beneficio.

Solución:

Sean x el número de unidades del producto A que hay que fabricar.

Sean y el número de unidades del producto B que hay que fabricar.

La función objetico, que queremos maximizar, es yxyxB 10001500, .


0

0

4801020

6032

y

x

yx

yx

0

0

482

6032

y

x

yx

yx



Como la función objetivo, que queremos maximizar, es yxyxB 10001500, , se tiene que:

00001000015000,0 B

200002000002010000150020,0 B

37500600031500610002115006,21 B

36000036000010002415000,24 B

Para maximizar los beneficios debemos de fabricar 21 unidades del producto A y 6 unidades

del producto B y dichos beneficios máximos serán de 37.500 €.

EJEMPLO:

Una fábrica de conservas tiene 800 kg de guisantes para conservar en dos tipos de latas. La

lata pequeña contiene 200 gramos y aporta un beneficio de 10 céntimos por lata. La lata

grande contiene 500 gramos y un beneficio de 30 céntimos. Si en el almacén solo disponemos

de 2.000 latas de tamaño pequeño y 1.000 grandes, determina la cantidad de latas de cada

tamañoque tenemos que producir para maximizar el beneficio.

Solución:

Sean x el número de latas pequeñas que hay que producir.

Sean y el número de latas grandes que hay que producir.

La función objetivo, que queremos maximizar, es yxyxB 3,01,0, .


0

0

1000

2000

8005,02,0

y

x

y

x

yx

0

0

1000

2000

800052

y

x

y

x

yx


Los vértices de la región factible son (0,0), (0,1000), (1500,1000), (2000,800) y (2000,0).

Como la función objetivo, que queremos maximizar, es yxyxB 3,01,0, , se tiene que:

00003,001.00,0 B

300300010003,001.01000,0 B

45030015010003,015001.01000,1500 B

4402402008003,020001.0800,2000 B

200020003,020001.00,2000 B

Para maximizar los beneficios debemos producir 1.500 latas pequeñas y 1.000 latas grandes y

dichos beneficios máximos serán de 450 €.

EJEMPLO:

Un deportista necesita diariamente consumir 36 gramos de una sustancia M, 24 gramos de N

y 8 gramos de P. En la farmacia ha encontrado dos tipos de cápsulas que contienen estas

sustancias. Las cápsulas A tienen 6 gramos de M, 2 gramos de N y 18 gramos de P, y cuestan 3

céntimos por cápsula. Las cápsulas B tienen 3 gramos de M, 4 gramos de N y 18 gramos de P,

y cuestan 4,5 céntimos por cápsula. ¿Cuántas cápsulas de cada tipo necesita para que el coste

sea mínimo?

Solución:

Sean x el número de cápsulas del tipo A que necesita.

Sean y el número de cápsulas del tipo B que necesita.

La función objetivo, que queremos minimizar, es yxyxC 5,43, .


0

0

81818

2442

3636

y

x

yx

yx

yx

0

0

499

122

122

y

x

yx

yx

yx



La función objetivo que tenemos que minimizar es yxyxC 5,43, , por lo tanto:

54540125,40312,0 C

30181245,4434,4 C

3603605,41230,12 C

Para que el coste sea mínimo se necesita 4 cápsulas del tipo A y 4 cápsulas del tipo B y dicho

coste mínimo será de 30 céntimos de euro.

EJEMPLO:

Los animales de una granja deben tomar, al menos, 60 miligramos de vitamina A y, al menos,

90 miligramos de vitamina B. Existen dos compuestos con estas vitaminas. El compuesto X

contiene 10 miligramos de vitamina A y 15 miligramos de B, y cada dosis cuesta 0,50 €., El

compuesto Y contiene 10 miligramos de cada vitamina, y cada dosis cuesta 0,30 €. Además, se

recomienda no tomar más de 8 dosis diarias. Calcula qué dosis tiene que tomar para que el

coste sea mínimo.

Solución:

Sean x el número de dosis del compuesto X que tienen que tomar.

Sean y el número de dosis del compuesto Y que tienen que tomar.

La función objetivo, que queremos minimizar, es yxyxC 3,05,0, .


0

0

8

901015

601010

y

x

yx

yx

yx

0

0

8

1823

6

y

x

yx

yx

yx



Como la función objetivo, que queremos minimizar, es yxyxC 3,05,0, , se tiene que:

30303,065,00,6 C

8,28,1163,025,06,2 C

40403,085,00,8 C

Para que el coste sea mínimo tienen que tomar 2 dosis del compuesto X y 6 dosis del

compuesto Y y dicho coste mínimo será de 2,8 €.

EJEMPLO:

Una empresa se dedica a elaborar lotes de productos que se venden en los supermercados. En

estos momentos están empaquetando dos lotes diferentes. El lote del tipo A tiene 1 queso y dos

botellas de vino, y su transporte cuesta 0,90 €. El lote B tiene 3 quesos y 1 botella de vino, y

cuesta 1,50 € transportarlo. La empresa dispone de 200 quesos y 100 botellas de vino, y

necesita elaborar, al menos, 10 lotes de tipo A y 25 de tipo B. ¿Cuántos lotes de cada clase han

de elaborar para que los gastos en transporte sean mínimos?

Solución:

Sean x los lotes que se han de elaborar del tipo A.

Sean y los lotes que se han de elaborar del tipo B.

La función objetivo, que queremos minimizar, es yxyxG 5,19,0, .


25

10

1002

2003

y

x

yx

yx


Los vértices de la región factible son (10,25), (10,190/3), (20,60) y (75/2,25).

La función objetivo, que queremos minimizar, es yxyxG 5,19,0, , por lo tanto:

5,465,379255,1109,025,10 G

1049593

1905,1109,0

3

190,10

G

1089018605,1209,060,20 G

25,715,3775,33255,12

759,025,

2

75

G

Para que los gastos en transporte sean mínimos se han de elaborar 10 lotes del tipo A y 25

lotes del tipo B y dicho gasto mínimo será de 46,5 €.

EJEMPLO:

La tabla siguiente nos muestra la composición de los artículos, A y B, por los elementos M1,

M2 y M3.

A B

M1 2 1

M2 3 2

M3 1 2

Necesitamos, al menos, 45 unidades de M1, 71 de M2 y 25 de M3, y los costes de traslado de A

y B son 50 € y 60 €, respectivamente.

Determinar los artículos que hay que elaborar para que los costes del traslado sean mínimos.

Solución:

Sea x el número de artículos A que hay que elaborar.

Sea y el número de artículos B que hay que elaborar.

La función objetivo, que queremos minimizar, es yxyxC 6050, .


0

0

252

7123

452

y

x

yx

yx

yx



Como la función objetivo, que tenemos que minimizar, es yxyxC 6050, , se tiene que:

270027000456005045,0 C

137042095076019507,19 C

121060115016023501,23 C

12500125006025500,25 C

Para que los costes sean mínimos hay que elaborar 23 artículos A y 1 articulo B, siendo así los

costes mínimos de 1.210 €.

Documents

TEMA IV.- PROGRAMACIÓN LINEAL