lic. gregorio bautista oblitas. existen problemas de decisión administrativos que pueden ser...

PROGRAMACIÓN LINEALLic. Gregorio Bautista Oblitas

Existen problemas de decisión administrativos que pueden ser resueltos a través de un modelo matemático llamado programación lineal. Por ejemplo:1) PRODUCCION2) MARKETING3) FINANZAS

Introducción a la Programación Lineal

Juan se dedica a la compra y venta de naranja y papaya. Todos los días temprano en la mañana visita a su proveedor de frutas en el mercado mayorista y hace las compras del día. El día anterior recibe los pedidos de sus clientes y esta suma 600 kilos de papaya y 1200 kilos de naranja. Juan lleva su camioneta para el transporte cuya capacidad de carga es de 1600 kilos. ¿Cuántos kilos de cada fruta debe comprar Juan para maximizar los beneficios?

Problema

PROBLEMAJuan lleva su camioneta para el transporte cuya capacidad de carga es de 1600 kilos. ¿Cuántos kilos de cada fruta debe comprar Juan para maximizar los beneficios?

Precio de compra al por mayor x Kg

Precio de venta al

minorista x KgUtilidad por Kg

Papaya S/. 1.30 S/. 1.60 S/. 0.30

Naranja S/. 1.00 S/. 1.20 S/. 0.20

Se tienen los siguientes precios y costos por kilo de fruta :

¿Cuántos kilos de papaya y naranja debe comprar Juan para obtener la Máxima Utilidad?

X1 = ?? X2 = ??

X1 < 600 kg X2 < 1200 kg X1 + X2 < 1600 kg

Primero se debe cargar a la camioneta con aquel que tiene mas utilidad por kilo.

Capacidad

Utilidad por kilo: S/. 0.30

X1 < 600 kg

X2 < 1200 kgX1 + X2 < 1600 kg

Se debe comprar 600 kg. de papaya y 1000 kg. de naranja, su utilidad será S/. 380.

Utilidad por kilo: S/. 0.20

MODELO DE PROGRAMACIÓN LINEAL

Un modelo de programación lineal busca el objetivo de maximizar o minimizar una función lineal, sujeta a un conjunto de restricciones lineales.

MODELO DE PROGRAMACIÓN LINEAL

Un modelo de programación lineal esta compuesto de lo siguiente:* Un conjunto de variables de decisión* Una función objetivo* Un conjunto de restricciones

1) FORMULACIÓN DEL PROBLEMA

Definición de las Variables de Decisión x1 = Cantidad, en kilos, de papaya que se debe comprar. x2 = Cantidad, en kilos, de naranja que se debe comprar.

Función Objetivo Maximizar la utilidad total de los dos

productos:Maximizar Z = 0.30 x1 + 0.20 x2

1) Formulación del Problema

RestriccionesCantidad máxima de Papaya < 600 kilos.

x1 < 600Cantidad máxima de Naranja < 1200 kilos.

x2 < 1200 Carga máxima de la camioneta < 1600

kilos.

x1 + x2 < 1600

1) Formulación del Problema

Maximizar Z = 0.30 x1 + 0.20 x2

x1 < 600

x2 < 1200

x1 + x2 < 1600

x1, x2 > 0

1) Formulación del Problema

PROCEDIMIENTO DE SOLUCIÓN GRÁFICA EN PROBLEMAS DE PL CON DOS VARIABLES

1)Establecer la formulación del problema

2) GRAFICAR RESTRICCIONESMax Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)

X1

X2

(0,0)

Cada punto en este cuadrante no negativo esta asociado con una especifica alternativa de solución.

2) GRAFICAR RESTRICCIONESMax Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)

X1

X2

(0,0)

2) GRAFICAR RESTRICCIONESMax 3 P1 + 5 P2s.a. P1 + < 4 (Planta

1) 2 P2 < 12 (Planta

2) 3 P1 + 2 P2 < 18 (Planta

3) P1, P2 > 0 (no

negatividad)

X1

X2

(0,0)

(600,0)

Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)

R1

2) GRAFICAR RESTRICCIONESMax 3 P1 + 5 P2s.a. P1 + < 4 (Planta

1) 2 P2 < 12 (Planta

2) 3 P1 + 2 P2 < 18 (Planta

3) P1, P2 > 0 (no

negatividad)

X1

X2

(0,0)

(600,0)

Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)

R1

2) GRAFICAR RESTRICCIONESMax 3 P1 + 5 P2s.a. P1 + < 4 (Planta

1) 2 P2 < 12 (Planta

2) 3 P1 + 2 P2 < 18 (Planta

3) P1, P2 > 0 (no

negatividad)

X1

X2

(0,0)

(600,0)

Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)

(0,1200)

R1

R2

2) GRAFICAR RESTRICCIONESMax 3 P1 + 5 P2s.a. P1 + < 4 (Planta

1) 2 P2 < 12 (Planta

2) 3 P1 + 2 P2 < 18 (Planta

3) P1, P2 > 0 (no

negatividad)

X1

X2

(0,0)

(600,0)

Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)

(0,1200)

R1

R2

2) GRAFICAR RESTRICCIONESMax 3 P1 + 5 P2s.a. P1 + < 4 (Planta

1) 2 P2 < 12 (Planta

2) 3 P1 + 2 P2 < 18 (Planta

3) P1, P2 > 0 (no

negatividad)

X1

X2

(0,0)

(600,0)

Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)

(0,1200) R2

R1

2) GRAFICAR RESTRICCIONESMax 3 P1 + 5 P2s.a. P1 + < 4 (Planta

1) 2 P2 < 12 (Planta

2) 3 P1 + 2 P2 < 18 (Planta

3) P1, P2 > 0 (no

negatividad)

X1

X2

(0,0)

(600,0)

Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)

(0,1200)

R3

R2

R1

(1600,0)

(0,1600)

2) GRAFICAR RESTRICCIONESMax 3 P1 + 5 P2s.a. P1 + < 4 (Planta

1) 2 P2 < 12 (Planta

2) 3 P1 + 2 P2 < 18 (Planta

3) P1, P2 > 0 (no

negatividad)

X1

X2

(0,0)

(600,0)

Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)

(0,1200)

R3

R2

R1

(1600,0)

(0,1600)

(400,1200)

(600,1000)

PROCEDIMIENTO DE SOLUCIÓN GRÁFICA EN PROBLEMAS DE PL CON DOS VARIABLES

1)Establecer la formulación del problema2)Graficar en el plano cartesiano (X,Y) las

restricciones del tipo >, < ó =, como si fueran rectas.

3)Ubicar el espacio de la solución factible (región factible), el cual está dado por el área común a todas las restricciones.

3) UBICAR REGIÓN FACTIBLEMax 3 P1 + 5 P2s.a. P1 + < 4 (Planta

1) 2 P2 < 12 (Planta

2) 3 P1 + 2 P2 < 18 (Planta

3) P1, P2 > 0 (no

negatividad)

X1

X2

(0,0)

(600,0)

Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)

(0,1200)

R3

R2

R1

(400,1200)

(600,1000)Región factible es el conjunto de puntos que satisface todas las restricciones simultáneamente. Existen infinitos puntos factibles (soluciones).

3) UBICAR REGIÓN FACTIBLE

X1

X2

(0,0)

(600,0)

Max Z = 0.30 X1 + 0.20 X2s.a. X1 < 600 (Papaya) X2 < 1200 (Naranja) X1 + X2 < 1600 (Camioneta) X1, X2 > 0 (no negatividad)

(0,1200) (400,1200)

(600,1000)

A B

C

DE

Se llaman puntos extremos a los vértices de la región de factibilidad.

Los valores que optimizan la función objetivo siempre se encuentran en uno de los puntos extremos.

PROCEDIMIENTO DE SOLUCIÓN GRÁFICA EN PROBLEMAS DE PL CON DOS VARIABLES

1)Establecer la formulación del problema2)Graficar en el plano cartesiano (X,Y) las

restricciones del tipo >, < ó =, como si fueran rectas.3)Ubicar el espacio de la solución factible (región

factible), el cual está dado por el área común a todas las restricciones.

4)Obtener la solución óptima.

4) OBTENER SOLUCIÓN OPTIMA

X1

X2

(0,0)

(600,0)

Max Z = 0.30 X1 + 0.20 X2En la región factible

(0,1200) (400,1200)

(600,1000)

A B

C

DE

0.30

0.20

Pendiente de la función objetivo

Se debe dibujar el contorno de la función objetivo (línea iso-beneficio) mediante rectas paralelas, en cada vértice, según la relación: X2 = – 1.5 X1 + K

4) OBTENER SOLUCIÓN OPTIMA

X1

X2

(0,0)

(600,0)

Max Z = 0.30 X1 + 0.20 X2En la región factible

(0,1200) (400,1200)

(600,1000)

A B

C

DE

Z1 = 0.30 (0) + 0.20 (0) = 0

Pendiente de la función objetivo

Z1

0.30

0.20

4) OBTENER SOLUCIÓN OPTIMA

X1

X2

(0,0)

(600,0)

Max Z = 0.30 X1 + 0.20 X2En la región factible

(0,1200) (400,1200)

(600,1000)

A B

C

DE

Z1 = 0.30 (0) + 0.20 (0) = 0

Z2 = 0.30 (600) + 0.20 (0) = 180

Pendiente de la función objetivo

Z1

0.30

0.20

Z2

4) OBTENER SOLUCIÓN OPTIMA

X1

X2

(0,0)

(600,0)

Max Z = 0.30 X1 + 0.20 X2En la región factible

(0,1200) (400,1200)

(600,1000)

A B

C

DE

Z1 = 0.30 (0) + 0.20 (0) = 0

Z2 = 0.30 (600) + 0.20 (0) = 180

Z3 = 0.30 (0) + 0.20 (1200) = 240

Pendiente de la función objetivo

Z1

0.30

0.20

Z2

Z3

4) OBTENER SOLUCIÓN OPTIMA

X1

X2

(0,0)

(600,0)

Max Z = 0.30 X1 + 0.20 X2En la región factible

(0,1200) (400,1200)

(600,1000)

A B

C

DE

Z1 = 0.30 (0) + 0.20 (0) = 0

Z2 = 0.30 (600) + 0.20 (0) = 180

Z3 = 0.30 (0) + 0.20 (1200) = 240

Z4 = 0.30 (400) + 0.20 (1200) = 360

Pendiente de la función objetivo

Z1

0.30

0.20

Z2

Z3

Z4

4) OBTENER SOLUCIÓN OPTIMA

X1

X2

(0,0)

(600,0)

Max Z = 0.30 X1 + 0.20 X2En la región factible

(0,1200) (400,1200)

(600,1000)

A B

C

DE

Z1 = 0.30 (0) + 0.20 (0) = 0

Z2 = 0.30 (600) + 0.20 (0) = 180

Z3 = 0.30 (0) + 0.20 (1200) = 240

Z4 = 0.30 (400) + 0.20 (1200) = 360

Z5 = 0.30 (600) + 0.20 (1000) = 380

Z1

Z2

Z3

Z4

Z5

4) OBTENER SOLUCIÓN OPTIMA

X1

X2

Max Z = 0.30 X1 + 0.20 X2En la región factible

(600,1000)

A B

C

DE

Z1 = 0.30 (0) + 0.20 (0) = 0

Z2 = 0.30 (600) + 0.20 (0) = 180

Z3 = 0.30 (0) + 0.20 (1200) = 240

Z4 = 0.30 (400) + 0.20 (1200) = 360

Z5 = 0.30 (600) + 0.20 (1000) = 380

Solución óptima: Se encuentra en el punto C de las restricciones activas (R1 y R3)

R1

R3

R2

PROGRAMA LINEAL SIN SOLUCIÓN OPTIMALa función objetivo es no acotado: Ocurre cuando el objetivo puede crecer infinitamente (maximización)

No factible: Ocurre cuando en el modelo no hay ningún punto de factible

MODELO GENERAL DE PROGRAMACIÓN LINEAL

Maximizar (o Minimizar) Z = C1 X1 + C2 X2 +....+ Cn XnSujeto a:

a11 X1 + a12 X2 + a13 X3 +....+ a1n Xn < b1

:

ak1 X1 + ak2 X2 + ak3 X3 +....+ akn Xn > bk

:

am1 X1 + am2 X2 + am3 X3 +....+ amn Xn = bm

X1, X2, X3,...., Xn > 0

Se define las variables de decisión: X1, X2, X3,...., Xn

PROBLEMA 01

Un herrero con 80 kgs. de acero y 120 kgs. de aluminio quiere hacer bicicletas de paseo y de montaña, cuya utilidad son, respectivamente a S/.60 y S/.40 cada una. Para la de paseo empleará 1 kg. de acero y 3 kg. de aluminio, y para la de montaña 2 kg. de ambos metales. Como máximo se puede vender 30 bicicletas de paseo. ¿Cuántas bicicletas de paseo y de montaña venderá?

Para satisfacer las demandas de sus distribuidores, una fabrica de jeans debe producir, no menos de 300 y no mas de 600 jeans azules, y no menos de 100 y no mas de 300 jeans negros por día. Además, para mantener una buena calidad, no debe producir en total más de 800 jeans por dia, si se sabe que se obtiene una ganancia de S/. 35 por cada jeans azul y de S/. 25 por cada jean negro. ¿Cuál debe ser la producción diaria de cada tipo de jean para maximizar la ganancia?

PROBLEMA 02

Una empresa embotelladora fabrica dos tipos de bebidos: de naranja y de cola. Para elaborar la bebida de naranja se requiere 3 horas de uso de la máquina A y 1 hora de la maquina B, mientras que para elaborar la bebida de cola se requiere 2 horas de uso de la máquina A y 2 horas de la maquina B. La ganancia por bebida de naranja es S/. 0.70 y por las de cola es S/. 0.50. Calcula la máxima guanacia que se puede obtener si la maquina A puede trabajar 72 horas semanales y la maquina B, 84 horas semanales.

PROBLEMA 03

Una hacienda dispone de 100 hectáreas para sembrar maíz y algodón. La semilla del maíz cuesta S/. 40 por hectárea y la de algodón S/. 60 por hectárea. Los costos totales por mano de obra para la siembra son S/. 200 y S/. 100 por hectárea, respectivamente. Se espera obtener una ganancia de S/. 1500 por hectárea cosechada de algodón. Si no se puede invertir mas de S/. 4800 en semillas ni mas de S/. 14 000 en mano de obra, ¿Cuántas hectáreas de cada cultivo convienen sembrar para obtener la máxima ganacia?

PROBLEMA 04