programación lineal

PROGRAMACIÓN LINEAL

DantzigKantorovich

Koopmans

© Inmaculada Leiva Tapia

I.E.S.Alborán

2

INECUACIONES LINEALES

CON 2 INCÓGNITAS

1.

3

Ejemplo 1:Resolver la inecuación lineal 3x + 2y > 1

x y

-1 2

1 -1

4

Tomamos el punto O(0,0) y sustituimos sus coordenadas

en la ecuación de la recta:3 . 0 + 2 . 0 = 0


3.0+2.0 = 0 no es >1.Por tanto

O(0,0) no estáen el

semiplano3x + 2y > 1

5

3x + 2y > 1


O(0,0) es exterior

al semiplano 3x + 2y > 1

6



Ejemplo 2:Resolver la inecuación lineal 3x+2y<1

3.0+2.0 = 0 sí es < 1.Por tanto

O(0,0) sí estáen el

semiplano3x + 2y < 1

7



3x + 2y < 1

Ejemplo 2:Resolver la inecuación lineal 3x+2y<1

O(0,0) es interior

al semiplano 3x + 2y < 1

8

Resolver la inecuación: 3x+2y > 1

Sus soluciones forman un semiplano.Para determinarlo:

Se representa la recta 3x+2y=1.

Se toma un punto que no esté en la recta,por ej.,el origen (0,0) y se sustituye en la inecuación.

Si la cumple,se toma el semiplano que contiene al (0,0);y si no,el otro semiplano.

INECUACIONES LINEALES CON 2 INCÓGNITAS

3.0 + 2.0 < 1(0,0) es exterior

RESUMEN

9

SISTEMAS DE INECUACIONES

LINEALES CON 2 INCÓGNITAS

2.

10

SISTEMAS DE INECUACIONES LINEALES CON 2 INCÓGNITAS

● Cada inecuación determina un semiplano.

● La solución del sistema será la intersección ( puntos comunes) de todos los semiplanos.Es siempre una región convexa.

Ejercicio:

Resuelve el sistema de inecuaciones

3x + 2y ≥ 1

x – y ≤ 2

x + 4y ≤ 7

11

Ejercicio:


3x + 2y ≥ 1

x – y ≤ 2

x + 4y ≤ 7

● Cada inecuación determina un semiplano.

● La solución del sistema será la intersección ( puntos comunes) de todos los semiplanos.Es siempre una región convexa.

x y

1 -12 03 1

x y

1 -13 -40 1/2

g : 3x + 2y =1 h : x – y = 2 i : x + 4y = 7

x y

3 17 0-1 2

Para representar cada rectax y

13

3x + 2y ≥ 1

14

x – y ≤ 2

15

x + 4y ≤ 7

16

x + 4y ≤ 7

3x + 2y ≥ 1

x – y ≤ 2

17

3x +2y ≥ 1

x + 4y ≤ 7x - y ≤ 2

19

Región devalidez

(soluciones factibles)

Los vértices se obtienen

como intersecciónde pares de rectas

A = g ∩ i : 3x +2y = 1 x + 4y = 7

B = h ∩ i :x – y = 2

x + 4y = 7

C = h ∩ g :x – y = 2

3x + 2y =1

20

PROGRAMACIÓN LINEAL

3.

21

PROGRAMACION LINEAL

La programación lineal es un

método para obtener la opción

más conveniente, u opción

óptima ,en situaciones en las

que la función que se quiere

optimizar( hacer máxima o

mínima) depende de unas

variables sujetas a ciertas

restricciones.

Ejercicio:


3x + 2y ≥ 1

x – y ≤ 2

x + 4y ≤ 7

y maximiza con esas restricciones la función objetivo

F(x,y) = x + 5y

22

Ejercicio:


3x + 2y ≥ 1

x – y ≤ 2

x + 4y ≤ 7

y maximiza con esas restricciones la función objetivo

F(x,y) = x + 5y

Practica con Geogebra

23

Direcciónde la

función objetivo

24

Función objetivomaximizada en el vértice A (-1,2) :

F(-1,2) = -1 + 5 . 2 = 9

25

PROGRAMACION LINEALPartiendo de

hay que

y que está sujeta a

FUNCION OBJETIVO:Función que se debe optimizar

(maximizar o minimizar) Beneficios Costes Tiempo ........

RESTRICCIONES:Condiciones que tenemos

Dinero disponible Capacidad de almacenamiento Material a usar .......

BUSCAR SOLUCIÓN ÓPTIMA:Queremos conseguir

Beneficios máximosCostes mínimos Tiempo mínimo ........

26

En los problemas de programación lineal con dos variables tenemos:

Una función objetivo F(x,y) lineal que hay que optimizar. Puede representarse mediante una recta móvil.

Varias restricciones,dadas mediante inecuaciones lineales.Cada una de ellas tiene como solución un semiplano.

Todas las restricciones juntas dan lugar a una región poligonal convexa (región de validez) que puede ser finita o infinita.

Las soluciones factibles son los puntos de la región de validez,y cumplen todas las restricciones a la vez.

27

Para optimizar la función objetivo,se mueve la recta que la representa, paralelamente a sí misma,hasta encontrar el punto donde alcanza el máximo o mínimo (solución óptima).

Para determinar los vértices de la región de validez,se resuelvenlos sistemas formados por los pares de rectas que determinanlos lados de dicha región.

La solución óptima se encuentra siempre en la periferia de la región de validez y puede ser: única ( vértice), infinitas ( lado ) o no existir.

En los problemas de programación lineal con dos variables tenemos:

28

4.

EJERCICIOS

29

EJERCICIO 1:

Con 80 Kg de acero y 120 kg de aluminio,se quieren fabricar bicicletas de montaña y de paseo que se venderán a 200 y 150 €, respectivamente.

Para la de montaña se necesitan 1 kg de acero y 3 kg de aluminio, mientras que para la de paseo se requieren 2 kg de cada metal.

¿Cuántas bicicletas de cada clase se deben fabricar para obtener el máximo beneficio?¿A cuánto ascenderá este beneficio ?

Restricciones:

x = bicicletas de montañay = bicicletas de paseox ≥ 0y ≥ 0acero: x + 2y ≤ 80aluminio: 3x + 2y ≤ 120

Beneficio a maximizar:

F(x,y) = 200x+150y

Practica con Geogebra

31

x + 2y ≤ 80

32

3x + 2y ≤ 120

34

Región de validez:

formada por todas las soluciones factibles

35

Dirección de la

Función objetivo

Restricciones:x=bicicletas de montañay=bicicletas de paseox ≥ 0y ≥ 0acero: x + 2y ≤ 80aluminio: 3x + 2y ≤ 120Beneficio a maximizar:F(x,y) = 200x+150y

36

Restricciones:x=bicicletas de montañay=bicicletas de paseox≥0y≥0acero: x+2y ≤ 80aluminio: 3x+2y ≤ 120Beneficio a maximizar:F(x,y) = 200x+150y

Función objetivo ya maximizada en el vértice C(20,30):

F(20,30) =200 . 20 + 150 . 30 = 8500 €

37

Si no se aprecia claramente cuál es el vértice que corresponde a la solución óptima, evaluamos la función objetivo en los vértices de la región de validez en que haya duda (en este caso B, C y D):

en B(40,0) : 200 . 40 + 150 . 0 = 8000 €en C(20,30): 200 . 20 + 150 . 30 = 8500 €en D(0,40) : 200 . 0 + 150 . 40 = 6000 €

así vemos que el máximo de beneficios es para 20 bicicletas de montaña y 30 de paseo.

Restricciones:x=bicicletas de montañay=bicicletas de paseox≥0y≥0acero: x+2y ≤ 80aluminio: 3x+2y ≤ 120Beneficio a maximizar:F(x,y) = 200x+150y

38

EJERCICIO 2:

Halla los valores de x e y que hacen máxima la función

z = 8x + 5y

sujeta a las siguientes restricciones:

x + y ≤ 73x + y ≤ 12x ≤ 3x ≥ 0y ≥ 0

Practica con GeoGebra

41

x + y ≤ 7

42

3x + y ≤ 12

43

0 ≤ x ≤ 3

45

Región de

validez

46

Dirección de la

funciónobjetivo

47

Función objetivo ya maximizada en el vértice D(2,5;4,5):

F(2,5;4,5) = 8. 2,5 + 5. 4,5 = 42,5

48

EJERCICIO 3:

Halla los valores de x e y que hacen máxima la función

z = 8x + 5y

sujeta a las siguientes restricciones:

x + y ≤ 73x + y ≤ 12x ≤ 3x ≥ 0y ≥ 0

x , y deben ser números naturales.


50

Puntos factiblesson sólo los de

coordenadasnaturales

51

Dirección de la

funciónobjetivo

52

Función objetivo ya maximizada en C(2,5):

F(2,5) = 8 . 2 + 5 . 5 = 41

53

EJERCICIO 4:

Un club de jubilados quiere organizar un viaje para 200 socios.

Contratan una agencia que dispone de 4 microbuses de 25 plazas y 5 autobuses de 50, pero solamente dispone de 6 conductores.

El alquiler de los autobuses es de 160 € por día y el de los microbuses de 70 € por día.

¿Cómo deben hacer para que el coste del viaje sea el menor posible?¿Cuál será dicho coste?


Restricciones:

x = nº microbusesy = nº autobuses0 ≤ x ≤ 40 ≤ y ≤ 5x + y ≤ 6(25x + 50y ≥ 200) → x + 2y ≥ 8

Coste a minimizar:

F(x,y) = 7x + 16y (en decenas de euros)

55

x + y ≤ 6

56

x + 2y ≥ 8

57

0 ≤ x ≤ 4

58

0 ≤ y ≤ 5

59

Región de validez

60

Dirección función objetivo

61

Función objetivo minimizada en

B(4,2):70.4 + 160.2 = 600 €

62

EJERCICIO 5:

Un estudiante reparte propaganda en su tiempo libre.La empresa A le paga 0,05 € por impreso repartido y la empresa B, con folletos más grandes, le paga 0,07 € por impreso.

El estudiante lleva dos bolsas: una para los impresos de tipo A, en la que le caben 120, y otra para los de tipo B, en la que sólo caben 100.

Ha calculado que cada día puede repartir 150 impresos como máximo.

¿Cuántos impresos habrá de repartir de cada clase para que su beneficio diario sea máximo?

Restricciones:

(x = nº folletos de empresa A)(y = nº folletos de empresa B) 0 ≤ x ≤ 120 0 ≤ y ≤ 100 x + y ≤ 150


F(x,y) = 5x +7y( en céntimos de € )


71

EJERCICIO 6:

Una industria vinícola produce vino y vinagre.

El doble de la producción de vino es siempre menor o igual que la de vinagre más cuatro unidades.

Además,el triple de la producción de vinagre más cuatro veces la producción de vino es siempre menor o igual que 18 unidades.

Halla el número de unidades de cada producto que se deben producir para alcanzar un beneficio máximo,sabiendo que cada unidad de vino deja beneficio de 8 €,y cada unidad de vinagre 2 €.

Restricciones:

x = nº unidades de vinoy = nº unidades de vinagrex ≥ 0,y ≥ 02x - y ≤ 44x + 3y ≤ 18


F(x,y) = 8x +2y


80

EJERCICIO 7:

Un autobús Madrid-París ofrece plazas para fumadores al precio de 100 €, y para no fumadores al precio de 60 €.

Al no fumador se le permite llevar 50 kg de peso y al fumador sólo 20 kg.

Si el autobús tiene 90 plazas y admite un equipaje de hasta 3000 kg,¿cuál debe ser la oferta de la compañía si se quiere obtener el máximo beneficio?

Restricciones:

x = nº plazas de fumadoresy = nº plazas de no fumadoresx ≥ 0, y ≥ 0x + y ≤ 902x + 5y ≤ 300

Función objetivo a maximizar:

F(x,y) = 100x + 60y


87

EJERCICIO 8:

Para cubrir un determinado trayecto, una compañía aérea tiene dos aviones: A y B.

Entre ambos deben hacer, al menos, 60 vuelos, pero no más de 200;además el avión A no puede sobrepasar los 120 vuelos, ni el B puede volar más veces que el A.

Si en cada vuelo A consume 900 l. de combustible y B consume 700 l., ¿cuántos vuelos debe hacer cada avión para que el consumo total sea mínimo?

Restricciones:

(x=nº vuelos A)(y=nº vuelos B) 0 ≤ x ≤ 120 y ≥ 0 60 ≤ x+y ≤ 200 y ≤ x

Consumo a minimizar:

F(x,y) = 900x+ 700y


96

EJERCICIO 9:

Una persona quiere invertir 100 000 € en dos tipos de acciones A y B.

Las de tipo A tienen más riesgo,pero producen un beneficio del 10 %.

Las de tipo B son más seguras,pero producen sólo el 7 % nominal.

Decide invertir como máximo 60 000 € en la compra de acciones A y al menos 20 000 € en la compra de acciones B.

Además quiere que lo invertido en A sea por lo menos igual a lo invertido en B.

¿Cómo debe invertir los 100 000 € para que el beneficio anual sea máximo?

Restricciones:

x = nº acciones Ay = nº acciones B(en decenas de miles de €)

0 ≤ x ≤ 6 y ≥ 2x - y ≥ 0x + y ≤ 10


F(x,y) = 0.10x + 0.07y


programación lineal

Education