Pagina 1 APUNTE DE PROGRAMACION LINEAL ASIGNATURA: MATEMATICA II - U.N.R.N. – AÑO: 2010

Muchos problemas de administración y economía están relacionados con la optimización (maximización o minimización) de una función sujeta a un sistema de igualdades o desigualdades. La función por optimizar es la función objetivo. Las funciones de ganancia y de costo son ejemplos de funciones objetivo. El sistema de igualdades o desigualdades a las que está sujeta la función objetivo reflejan las restricciones (por ejemplo, las limitaciones sobre recursos como materiales y mano de obra) impuestas a la solución (o soluciones) del problema. Los problemas de esta naturaleza se llaman problemas de programación matemática. En particular, aquellas donde la función objetivo y las restricciones se expresan como ecuaciones o desigualdades lineales se llaman problemas de programación lineal. Un problema de programación lineal Ejercicio 1: Un problema de programación lineal consta de una función objetivo lineal por maximizar o minimizar, sujeta a ciertas restricciones en la forma de igualdades o desigualdades lineales. Como ejemplo de un problema de programación lineal en que la función objetivo debe maximizarse, considere el siguiente problema de producción con dos variables: Un granjero tiene 480 hectáreas en la que se puede sembrar ya sea trigo o maíz. El calcula que tiene 800 horas de trabajo disponible durante la estación crucial del verano. Dados márgenes de utilidad y los requerimientos laborales mostrados a la derecha, ¿Cuántas hectáreas de cada uno debe plantar para maximizar su utilidad?¿Cuál es ésta utilidad máxima?

Maiz: Utilidad: $40 por ha. Trabajo: 2hs por ha. Trigo: Utilidad: $30 por ha. Trabajo: 1hs por ha.

Solución: Como primer paso para la formulación matemática de este problema, se tabula la información dada. Si llamamos X1 a las hectáreas de maíz e X2 a las hectáreas de trigo. Entonces la ganancia total Z=40 X1+30 X2 Que es la función objetivo por maximizar.

Maíz

Trigo

Elementos disponibles

Horas

2

1

800

Hectáreas

1

1

480

$40

$30

Utilidad por unidad

La cantidad total de tiempo para sembrar maíz y trigo está dada por 2X1+X2 horas que no debe exceder las 800 horas disponibles para el trabajo. Así se tiene la desigualdad: En forma análoga, la cantidad de hectáreas disponibles está dada por X1+X2, que no puede exceder las hectáreas disponibles para el trabajo, lo que conduce a la desigualdad. X1 e X2 no pueden ser negativas, de modo que X1≥0 X2≥0 En resumen, el problema en cuestión consiste en maximizar la función objetivo Z sujeta a las desigualdades. El planteo del problema es: Max Z=40 X1+30 X2 Sa: 2 X1+ X2≤800 X1+ X2≤480 X1,X2≥0 Prof: Martin Goin

Pagina 2

Si el problema consiste en Minimizar el modelo seria de la siguiente manera: Ejemplo 2: Una destilería produce dos tipos de Whisky mezclando solo dos maltas destiladas distintas, A y B. El primero tiene un 70% de Malta A y su costo es de 12 $/litro, mientras que el segundo tiene un 50% de dicha malta y su costo es de 16$/litro. Se debe utilizar como mínimo: malta A 132 litros y B 90 litros. ¿Cuántos litros de cada Whisky debe producir la destilería para minimizar sus costos? El planteo del problema es:

Min Z=12 X1+16 X2 Sa: 0,7 X1+ 0,5 X2≥132 0,3 X1+ 0,5 X2≥90 X1,X2≥0

Existen distintas formas de formular un problema de PL:

Forma Canónica o de Inecuaciones: Por ejemplo si el problema es de maximización con dos variables y tres restricciones el PL se puede formular de la siguiente manera: MAX Z=c1X1 + c2X2 SA: a11X1+a12X2≤b1 a21X1+a22X2≤b2 a31X1+a32X2≤b3 X1,X2≥0

Sistema de inecuaciones o forma Canónica

Los coeficientes c se denominan coeficientes del funcional, los coeficientes a coeficientes tecnológicos, SA: sujeto a: y los b son los términos independientes. Forma estándar: MAX Z=c1X1 + c2X2 SA: a11X1+a12X2+X3 =b1 a21X1+a22X2 +X4 =b2 a31X1+a32X2 +X5=b3 X1,X2, X3,X4, X5≥0

X3, X4, X5 se llaman variables slacks y se agregan según la cantidad de restricciones

Producto Matricial:

Y

matriz A

vector X

es decir

Prof: Martin Goin

vector B

AX=B

y

c1 c2 c3 c4 c5

vector C

CX

vector X

Pagina 3 Producto Vectorial: MAX Z=c1X1 + c2X2

Ejercicio 1: Para el ejemplo del granjero formule los cuatro tipos de formas vistas anteriormente. Ejercicio 2: Para el ejemplo de la destilería formule los cuatro tipos de formas vistas anteriormente. Resolución de problemas: Para resolver el problema de PL se lo puede hacer gráficamente y analíticamente. Cuando tenemos modelos con solo dos variables básicas el problema resulta muy sencillo para resolverlo gráficamente, ya que la interpretación geométrica se produce en el plano, pero cuando tenemos mas de dos variables se lo resuelve con un método no grafico llamado Simplex. Tomando el gráficamente.

ejemplo

del

granjero

resolveremos

Primero lo que tenemos que hacer es trazar las rectas de las desigualdades (en nuestro ejemplo son 2)

Luego pintamos la región que aparece entre las rectas y los ejes cartesianos. Siempre se trabaja en el cuadrante positivo, recordemos que las variables son ≥ 0 Cada punto de la región S es candidato para resolver este problema y se conoce como solución factible. El objetivo es encontrar el o los puntos óptimos que se encuentren entre las soluciones factibles. Se lo conoce como solución optima

S

En particular los puntos candidatos para ser solución optima se encuentran en los vértices de la región. (A, B, C y D).

S Prof: Martin Goin

Pagina 4

Luego se traza la recta del funcional Z, anulando Z=0 nos queda 0=40x+30y. Si despejamos y obtenemos y(-40/30)x que pasa por el origen de coordenadas.

Por ultimo si proyectamos la recta Z paralelamente hacia arriba, iremos tocando los vértices de la región, primero pasaremos por A, luego por C y en ultimo lugar por B. Es decir que el optimo de todos los candidatos es el punto B que se encuentra mas alejado de la recta Z que pasa por el origen. El punto B es (320,160), por lo tanto la solución optima se obtiene reemplazando en la recta Z. Z= 40(320)+30(160) = 17600

Podria pasar que en otros casos la solución optima coincida con un borde, se dice entonces que tiene infinitas soluciones optimas Resolución Analítica: Para resolver este problema analíticamente, de las infinitas soluciones posibles se deberían calcular solamente aquellas que constituyan bases, y dentro de las soluciones básicas se deberían tomar solamente aquellas que sean factibles. Para empezar debemos escribir el problema de forma canónica:

Max Z=40 X1+30 X2 sa: 2 X1 + X2≤800 X1 + X2≤480 X1,X2≥0

Para llevarlo a forma estándar se agregan las variables slacks X3, X4

MAX Z=40X1 + 30X2 sa: 2X1 + X2 + X3 X1 + X2 + X4

=800 =480

X1,X2, X3,X4 ≥0

En un problema de PL con n variables (reales y slacks) y m restricciones, se define como solución básica a aquella en la que por lo menos n-m variables son nulas. En nuestro caso n=4 y m=2, por lo tanto n-m=2 son las que deberían ser nulas. A continuación mostramos una tabla para la resolución analítica de nuestro ejemplo: Variables anuladas X1 X2 X1 X3 X1 X4 X2 X3 X2 X4 X3 X4

Prof: Martin Goin

Sistema de ecuaciones

Solución X3 = 800 X4 = 480 X2 = 800 X4 = -320 X2 = 480 X3 = 320 X1 = 400 X4 = 80 X1 = 480 X3 = -160 X1 = 320 X2 = 160

Valor del funcional

Punto en la grafica

Z=0

D

NO FACTIBLE

FUERA DEL RECINTO

Z = 14400

A

Z = 16000

C

NO FACTIBLE

FUERA DEL RECINTO

Z = 17600

B

Pagina 5 Claramente, como se muestra en la tabla, la solución optima es 17600 (vértice B) con X1=320 y X2=160. Para el caso de minimización, la grafica se resuelve de la siguiente manera: Supongamos otro ejemplo: Un nutricionista asesora a un individuo que sufre una deficiencia de hierro y vitamina B, y le indica que debe ingerir al menos 2400 mg de vitamina B-1 (tiamina) y 1500 mg de vitamina B-2 (riboflavina) durante cierto período de tiempo. Existen dos píldoras de vitaminas disponibles, la marca A y la marca B. Cada píldora de la marca A contiene 40 mg de hierro, 10 mg de vitamina B-1, 5 mg de vitamina B-2 y cuesta 6 centavos. Cada píldora de la marca B contiene 10 mg de hierro, 15 mg de vitamina B-1 y de vitamina B-2, y cuesta 8 centavos (tabla 2). ¿Cuáles combinaciones de píldoras debe comprar el paciente para cubrir sus requerimientos de hierro y vitamina al menor costo? Marca A

Marca B

Requerimientos mínimos

Hierro

40 mg

10 mg

2400 mg

Vitamina B-1

10 mg

15 mg

2100 mg

Vitamina B-2

5 mg

15 mg

1500 mg

Costo por píldora (US$)

0,06

0,08

Entonces el modelo de PL será: Min Z=6 X1+8 X2 sa: 40X1 + 10X2 ≥ 2400 10X1 + 15X2 ≥ 2100 5X1 + 15X2 ≥ 1500

S

X1,X2≥0 En particular los puntos candidatos para ser solución optima se encuentran en los vértices de la región. (A, B, C y D). Si proyectamos la recta Z hacia arriba de manera paralela el primer punto que tocaríamos de la región será B, es decir que es el optimo. El punto B es (30,120) por lo tanto el Z = 6(30)+8(120) Z = 1140 Ejercicio 3: Hallar la solución del ejercicio del nutricionista de modo analítico. Ejercicio 4: Hallar la solución del ejercicio de la destilería de modo analítico.

Casos especiales en la solución: No siempre obtenemos la solución optima (única), también se puede obtener solución alternativa (mas de una solución), esto ocurre cuando la recta Z (funcional) coincide con dos vértices. Por ejemplo: Al Problema del granjero le hacemos una modificación en el funcional:

Max Z=30 X1+30 X2 sa: 2 X1 + X2≤800 X1 + X2≤480 X1,X2≥0

Prof: Martin Goin

Para llevarlo a forma estándar se agregan las variables slacks X3, X4

Max Z=30 X1+30 X2 sa: 2 X1 + X2 + X3 =800 X1 + X2 + X4 =480

X1,X2, X3,X4 ≥0

Pagina 6 La tabla con la solución analítica quedaría de la siguiente manera: Variables anuladas X1 X2 X1 X3 X1 X4 X2 X3 X2 X4 X3 X4

Sistema de ecuaciones

Solución X3 = 800 X4 = 480 X2 = 800 X4 = -320 X2 = 480 X3 = 320 X1 = 400 X4 = 80 X1 = 480 X3 = -160 X1 = 320 X2 = 160

Valor del funcional

Punto en la grafica

Z=0

D

NO FACTIBLE

FUERA DEL RECINTO

Z = 14400

A

Z = 12000

C

NO FACTIBLE

FUERA DEL RECINTO

Z = 14400

B

Es decir que la solución es alternativa, porque Z=14400 se da en dos de los vértices B y A. Entonces podemos concluir que la solución esta en la recta y = 480 – X. Ejercicio 5: Hallar la solución de este último ejercicio gráficamente.

Prof: Martin Goin

Pagina 7 TRABAJO PRACTICO Nº 6: PROGRAMACION LINEAL ASIGNATURA: MATEMATICA II - U.N.R.N. – AÑO: 2010

Ejercicio 1: Resolver Gráficamente y Analíticamente los siguientes Programas Lineales

b) Max z = x1 + 2x2 sa: x1 + x 2 ≤ 4

a) Max z = x1 + x 2 sa: x1 + x 2 ≤ 4 x1 + 5 x 2 ≤ 1

x1 + 2 x 2 ≤ 2

x2 ≤ 2

x1 , x 2 ≥ 0

x1 , x 2 ≥ 0

c) Min z = x1 + x 2 sa: x1 + 2 x 2 ≥ 2

d) Max z = 9 x1 + 2 x2 sa: 4 x1 + 5 x 2 ≤ 2 − 5 x1 + 10 x 2 ≤ 1

3 x1 − x 2 ≥ 1 x1 , x 2 ≥ 0 Ejercicio 2: a)

sol: 2

sol: recta X2=4-X1

sol: 1.285714

x1 , x 2 ≥ 0

sol: 4.5

Resolver gráficamente y analíticamente el ejercicio 1 d) cambiando el funcional Z por 16X1 + 20X2 Sol: recta X2=(2-4X1)/5

b)

Resolver gráficamente y analíticamente el ejercicio 1 d) cambiando el funcional Z por X1 - 2X2 Sol: recta X2=-(1-10X1)/5

Ejercicio 3: Plantear y resolver el siguiente problema de minimización: Una empresa produce sacos para la preparación de cemento usando los ingredientes A y B. Cada kilo de ingrediente A cuesta $ 6 y contiene 4 unidades de arena fina, 3 de arena gruesa y 6 de pedregullo. Por su parte cada kilo de ingrediente del B cuesta $7 y contiene 3 unidades de arena fina, 5 de gruesa y 2 de pedregullo. Cada saco debe contener por lo menos 11 unidades de arena fina, 10 de gruesa y 9 de pedregullo. Sol: $ 18.09 Ejercicio 4: Plantear y resolver el siguiente problema de maximización: Estudiantes de Turismo necesitan ganar dinero y deciden pedir trabajo en una agencia para realizar encuestas, la misma contrata a dos tipos de equipos de jóvenes: Tipo A: parejas (un chico y una chica) y Tipo B: cuatro jóvenes (3 chicas y un chico). Los estudiantes interesados están conformados. ¿Como deberán distribuirse para sacar el mayor provecho económico, sabiendo que disponemos de 10 chicos y 20 chicas? Sol: $ 4000 Ejercicio 5: Disponemos de 210.000 euros para invertir en bolsa. Nos recomiendan dos tipos de acciones. Las del tipo A, que rinden el 10% y las del tipo B, que rinden el 8%. Decidimos invertir un máximo de 130.000 euros en las del tipo A y como mínimo 60.000 en las del tipo B. Además queremos que la inversión en las del tipo A sea menor que el doble de la inversión en B. ¿Cuál tiene que ser la distribución de la inversión para obtener el máximo interés anual? Resolverlo Graficamente únicamente. Sol: € 20700

Ejercicio 6: En una pastelería se hacen dos tipos de tartas: Vienesa y Real. Cada tarta Vienesa necesita un cuarto de relleno por cada Kg. de bizcocho y produce un beneficio de 250 Pts, mientras que una tarta Real necesita medio Kg. de relleno por cada Kg. de bizcocho y produce 400 Ptas. de beneficio. En la pastelería se pueden hacer diariamente hasta 150 Kg. de bizcocho y 50 Kg. de relleno, aunque por problemas de maquinaria no pueden hacer mas de 125 tartas de cada tipo. ¿Cuántas tartas Vienesas y cuantas Reales deben vender al día para que sea máximo el beneficio? Resolver gráficamente únicamente. Sol: $ 45000

Prof: Martin Goin