Álgebra matricial y optimización ma130 · formule el problema de determinar el número de...
TRANSCRIPT
Programación Lineal Ma130 - p. 1/27
Álgebra Matricial y OptimizaciónMa130
Programación LinealDepartamento de Matemáticas
ITESM
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 2/27
Introducción
En esta lectura daremos una introducción a lamodelación de problemas mediante programaciónlineal; pondremos énfasis en las etapas quecomponen la modelación.
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 3/27
Ejemplo 1
La compañía de pinturas Manchita produce trestipos de pintura adicionando a una pintura basecuatro productos o aditivos químicos (Q1 a Q4). Setiene abundante pintura base disponible y cuyocosto ya fue cubierto. La compañía deseadeterminar la cantidad de toneladas de cada tipode pintura que debe producir de manera quemaximice la ganancia total. Las únicasrestricciones se deben a la disponibilidad de losaditivos químicos requeridos. Las gananciasobtenidas por las toneladas de pintura producidaaparecen en la tabla siguiente.
Programación Lineal Ma130 - p. 4/27
Kg. de químico requerido por tonelada de
Aditivo Pintura interior Pintura exterior Pintura especial disponible
Q1 1 2 2 2 kg
Q2 2 1 1 1 kg
Q3 1 5 1 3 kg
Q4 0 0 1 0.8 kg
Ganancia por tonelada 15,000 25,000 19,000
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 5/27
Soluci onEn la metodología de solución a los problemas deinvestigación de operaciones, el primer pasoconsiste en establecer las acciones a tomar por laempresa para alcanzar sus objetivos. En estecaso, la compañía tiene como meta determinar elplan productivo de máxima ganancia. En estecaso, tal plan se determina indicando el número detoneladas de cada pintura que debe producir. Estodefine lo que se conoce como las variables dedecisi on :■ x = número de toneladas de pintura interior■ y = número de toneladas de pintura exterior■ z = número de toneladas de pintura especial
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 6/27
El siguiente paso es determinar la funci on objetivo .Ésta debe ir acorde con la meta de la empresa ydebe estar en función de las variables de decisión:La compañía desea maximizar la ganancia. Unelemento clave en los modelos de programaciónlineal es el supuesto de aditividad : La gananciatotal de la compañía es la suma de las gananciaspor separado de la venta de cada uno de losproductos. Esto descartaría momentáneamentesituaciones donde las ganancias estáncondicionadas ante ventas combinadas deproductos. Otro supuesto importante es el deproporcionalidad : La contribución de cada productoes directamente proporcional a la cantidad deproducto.
Programación Lineal Ma130 - p. 7/27
En nuestro ejemplo:
Ganancia total = Ganan. por P. Int. + Ganan. por P. Ext. + Ganan. por
= 15, 000dólareston · x+
25, 000dólareston · y+
19, 000dólareston · z
El objetivo queda
Maxw = 15 x+ 25 y + 19 z (en miles de dólares)
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 8/27
El siguiente paso es determinar las restriccionesque son condicionamientos a los valores quepueden tomar las variables de decisión. Estoscondicionamientos son muy diversos y podríanestar asociados a los recursos de la empresa, alas demandas del mercado o bien controles decalidad, por citar algunos ejemplos. En nuestroejemplo los recursos disponibles referentes a losaditivos químicos son los que condicionan el planproductivo.
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 9/27
Nuevamente, como en la función objetivo, las dossuposiciones de aditividad y proporcionalidad sonuna exigencia en los modelos de programaciónlineal: para cada aditivo,■ el total consumido es la suma de lo consumido
por separado en cada producto y■ el total consumido por cada producto es
directamente proporcional a la cantidad deproducto
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 10/27
Aplicados a nuestro ejemplo las restriccionesquedan:■ Aditivo 1:
1kgton
x+ 2kgton
y + 2kgton
z ≤ 2 kg
■ Aditivo 2:
2kgton
x+ 1kgton
y + 1kgton
z ≤ 2 kg
■ Aditivo 3:
1kgton
x+ 5kgton
y + 1kgton
z ≤ 3 kg
■ Aditivo 4:
0kgton
x+ 0kgton
y + 1kgton
z ≤ 0.8 kg
Si regresamos a la naturaleza de nuestro
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 11/27
Resumiendo: en términos puramentematemáticos, el problema de la empresa consisteen determinar x, y y z que:
Max f(x, y, z) = 15 x+ 25 y + 19 z
Sujeto a:
x + 2 y + 2 z ≤ 2
2 x + y + z ≤ 2
x + 5 y + z ≤ 3
z ≤ 0.8
con x, y, z ≥ 0
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 12/27
Ejemplo 2
Una compañía fabrica dos tipos de productos, el tipo A y el tipo B.Un producto A se vende en $27 y requiere materia prima por uncosto de $10. El costo de mano de obra de cada producto A es de$14. Por otro lado, un producto B se vende en $21 y requieremateria prima por un costo de $9. El costo de mano de obra decada producto B es de $10. La manufactura de los productos A y B
requiere dos tipos de labor: carpintería y acabado. Cada productoA requiere 2 horas de acabado y 1 de carpintería, mientras que unproducto B requiere 1 hora de acabado y 1 hora de carpintería.Cada semana la campañía dispone de 100 horas para acabado y80 horas para carpintería. Mientras que la demanda de productosB es ilimitada, se estima que la compañía vende a lo más 40productos A por semana. La compañía desea hacer un plan deproducción semanal que maximice la ganancia semanal.
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 13/27
Soluci onSigamos los pasos de la metodología planteadaen el problema anterior.1 Variables de decisi on
■ x = Cuántos productos A por semana deben producirse y
■ y = cuántos productos B por semana deben producirse.
2 Funci on Objetivo
Ganancia = Venta − Costo = Venta − CostoMateria Prima − CostoMano Obra= (27 · x+ 21 · y)− (10 · x+ 9 · y)− (14 · x+ 10 · y)
= 3x+ 2 y dólares
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 14/27
3 Restricciones■ (Recurso) Horas de carpintería:
2 horasartículo · x+ 1 hora
artículo · y ≤ 100 horas
■ (Recurso) Acabado:
1 horaartículo · x+ 1 hora
artículo · y ≤ 80 horas
■ (Condiciones de Mercado) Demanda:x ≤ 40 artículos
■ Naturales: x, y ≥ 0 y x y y enteros.
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 15/27
Resumiendo, el problema matemático queda:
Max f(x, y) = 3 x+ 2 y
sujeto a2 x + y ≤ 100
x + y ≤ 80
x ≤ 40
con x y y ≥ 0 y ambos enteros.
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 16/27
Ejemplo 3
Una oficina postal requiere un cierto númeromínimo de empleados de tiempo completodependiendo del día de la semana. La siguientetabla muestra los requisitos. La unión detrabajadores establece que un trabajador detiempo completo debe trabajar 5 días consecutivosy descansar los siguientes 2. Formule el problemade determinar el número de empleados de tiempocompleto mínimo que debe tener la oficina postal.
Día Empleados de tiempo completo requeridos
Día1 = Lunes 17
Día2 = Martes 13
Día3 = Miércoles 15
Día4 = Jueves 14
Día5 = Viernes 16
Día6 = Sábado 16
Día7 = Domingo 11
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 17/27
Soluci onVariables de decisi onUna primera tentación es definir una variable dedecisión como el total de empleados, pero desdeel punto de vista del departamento de personal elproblema no se resuelve conociendo el total deempleados contratados sino con la especificaciónde rol de trabajos; es decir, cuántos inician qué díade la semana. Entonces observamos que esa esla clave para definir las variables de decisión:■ xi= el número de empleados que inicial su
semana laboral el día i (1=lunes, 2=martes, etc)Note que entonces el total de empleadoscontratados es la suma de los xi.
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 18/27
Funci on objetivo
El objetivo de la empresa es claro: minimizar eltotal de empleados contratados:
Min z =7∑
i=1
xi
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 19/27
Restricciones
Nuestras restricciones se relacionan con cumplir con laoperatividad de la oficina postal en cada día de la semana:debemos garantizar que en cada día de la semana el número deempleados que estén laborando (no sólo los que inician su semanalaboral tal día) son al menos los requeridos. Por ejemplo, contemosel total de empleados que están laborando el día lunes. Seguroestán todos los que inician su semana el lunes (x1) (ellosdescansan sábado y domingo), pero también están todos los que lainiciaron el domingo (x7) (ellos descansan viernes y sábado), todoslos que la iniciaron el sábado (x6) (ellos descansan jueves yviernes), todos los que la iniciaron el viernes (x5) (ellos descansanmiércoles y jueves), y todos los que la iniciaron el jueves (x4) (ellosdescansan martes y miércoles). Todos los que incian en martesdescansan domingo y lunes, y los que inician en miércolesdescansan lunes y martes. Resumiendo
total de trabajadores en lunes = x1 + x4 + x5 + x6 + x7 ≥ 17
Programación Lineal Ma130 - p. 20/27
Siguiendo un análisis semejante para cada uno de los días restantes concluimosque se requiere:
total de trabajadores en martes = x1 + x2 + x5 + x6 + x7 ≥ 13
total de trabajadores en miércoles = x1 + x2 + x3 + x6 + x7 ≥ 15
total de trabajadores en jueves = x1 + x2 + x3 + x4 + x7 ≥ 14
total de trabajadores en viernes = x1 + x2 + x3 + x4 + x5 ≥ 16
total de trabajadores en sábado = x2 + x3 + x4 + x5 + x6 ≥ 16
y
total de trabajadores en domingo = x3 + x4 + x5 + x6 + x7 ≥ 11
Además, los valores de las variables xi deben ser enteros.
Programación Lineal Ma130 - p. 21/27
En términos puramente matemáticos el problema consiste en
Min z =7∑
i
xi
sujeto a
x1 + x4 + x5 + x6 + x7 ≥ 17
x1 + x2 + x5 + x6 + x7 ≥ 13
x1 + x2 + x3 + x6 + x7 ≥ 15
x1 + x2 + x3 + x4 + x7 ≥ 14
x1 + x2 + x3 + x4 + x5 ≥ 16
x2 + x3 + x4 + x5 + x6 ≥ 16
x3 + x4 + x5 + x6 + x7 ≥ 11
con xi ≥ 0 y xi entero para i = 1, 2, . . . , 7.
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 22/27
Ejemplo 3
Sunco Oil produce tres tipos de gasolinas (G1, G2 y G3). Cada tipo
es producido combinando tres tipos de crudo (C1, C2 y C3). Las
ventas en dolares por barril de gasolina son: G1 en 70, G2 en 60 y
G3 en 50. Los costos en dolares por barril de crudo son: C1 en 45,
C2 en 35 y C3 en 25. Sunco puede comprar hasta 5000 barriles de
cada tipo de crudo al día. Los tres tipos de gasolina difieren en
octanaje y en porcentaje de azufre. Para producir G1 la
combinación de crudos debe tener en promedio un octanaje
almenos de 10 y contener no más de 1 % de azufre. Para producir
G2, el octanaje promedio es de al menos 8 y contener no más de
2 % de azufre. Para producir G3, el octanaje promedio es de al
menos de 6 y contener no más de 1 % de azufre. C1 posee un
octanaje de 12 y 0.5 % azufre, C2 posee un octanaje de 6 y 2.0 %
de azufre, y C3 posee un octanaje de 8 y 3.0 % de azufre. El costo
de transformación de un barril de crudo en uno de gasolina es de 4
dolares. Sunco puede producir a lo más 14,000 barriles de gasolina
al día.
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 23/27
Los clientes de Sunco requieren 3,000 barriles de G1, 2,000 barrilesde G2, y 1,000 barriles de G3 por día. Sunco considera unaobligación satisfacer estos requerimientos. Es un hecho que lapublicidad estimula la demanda de sus productos. Cada dolargastado en la publicidad de uno de sus productos aumenta lademanda diaria en 10 barriles. Formule un modelo de PL quepermita a Sunco maximizar sus ganancias diarias.
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 24/27
Soluci on
Variables de decisi on
Notemos que por un lado estamos interesados en saber cuántos
barriles de cada gasolina se deben producir, y por otro estamos
interesados en cuántos barriles de cada tipo crudo comprar. Sin
embargo, aún con estos datos el departamento encargado de la
producción debe decidir cómo se deben mezclar los crudos para
producir cada tipo de gasolina. Es decir, que las cantidades totales
de gasolina y de crudo no resuelven el problema de la producción.
Lo que sí resuelve el problema de la producción es decidir
exactamente cómo deben mezclarse los curdos comprados para
producir cada tipo de gasolina.
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 25/27
Así las variables de decisión deben ser
xi,j = cantidad de barriles del crudo i utilizados para producir gasolina j
Esto por un lado. Pero otra parte pendiente son las decisiones quedebe tomarse en publicidad. Y para ello debemos precisar cuántosdólares se debe invertir en la publicidad de cada tipo de gasolina:
yj = total de dólares aplicados en la publicidad de la gasolina j
Observemos que estas variables de decisión permiten determinarel total de barriles de cada tipo de crudo que debe comprarse y eltotal de barriles de cada tipo de gasolina se produce:■
∑3
i=1xi,j es el total de barriles de gasolina j a producir.
■∑
3
j=1xi,j es el total de barriles de crudo i en la producción.
■∑
3
i=1
∑3
j=1xi,j es el total de barriles de crudo a procesar (que
será el total de barriles de gasolina a producir).
Programación Lineal Ma130 - p. 26/27
Funci on objetivo
El objetivo de la empresa en maximizar las ganancias. Las ganancias serán lasventas menos los costos. Los costos en los que se incurre son los referentes a lamateria prima, a la transformación y a la publicidad.■ CT = Costo de transformación:
CT = 4 dólares/barril · (3∑
i=1
3∑
j=1
xi,j)
■ CMP = Costo de materia prima:
CMP = 45dólaresbarril
·
3∑
j=1
x1,j + 35dólaresbarril
·
3∑
j=1
x2,j + 25dólaresbarril
·
3∑
j=1
x3,j
■ V = Venta de crudo:
V = 70dólaresbarril
·
3∑
i=1
xi,1 + 60dólaresbarril
·
3∑
i=1
xi,1 + 50dólaresbarril
·
3∑
i=1
xi,1
■ P = Costo de publicidad:
P = y + y + y =
3∑y
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 27/27
Restricciones
En este problema las restricciones son de diferente tipo:■ La compañía tiene una capacidad instalada que no puede
exceder:3∑
i=1
3∑
j=1
xi,j ≤ 14, 000
■ Las compañías que proveen crudo tienen limitaciones; 5 milbarriles de cada curo están disponibles a lo más:
3∑
j=1
xi,j ≤ 5, 000 para i = 1, 2, 3
IntroEj 1Ej 2Ej 3Ej 4
Programación Lineal Ma130 - p. 28/27
■ Para cada gasolina, la totalidad de gasolina producida equiparala demanda. Y por otro lado, la demanda será el resultado de lademanda natural más la inducida por publicidad:
3∑
i=1
xi,1 = 3, 000 + 10 y1
3∑
i=1
xi,2 = 2, 000 + 10 y2
3∑
i=1
xi,3 = 1, 000 + 10 y3
■ Cada gasolina producida tiene ciertos criterios de calidad acuidar: el porcentaje de azufre y el octanaje. Supongamos que secumple el principio de aditividad y el de proporcionalidad tantopara el octanaje como para el porcentaje de azufre. Así para lagasolina 1:◆ Azufre: en cada tipo de gasolina no se debe exceder el 1 %.
El total de gasolina 1:∑
3
i=1xi,1
Aporte de azufre por cada tipo de crudo: C1: 0.5 %, C2: 2.0 %