Fundamentos de Investigaci´on de Operaciones Formulaci´on de Modelos de Programac´on Lineal 17 de julio de 2004

La Programaci´ on Lineal (LP) es una herramienta para resolver problemas de optimizaci´ on que se caracterizan por tener como funci´ on objetivo y restricciones combinaciones lineales de las variables de decisi´ on. La principal ventaja radica en que existe un algoritmo eficiente (SIMPLEX) para resolver este tipo de modelos.

1.

Conceptos B´ asicos Consideremos el siguiente ejemplo para describir los t´erminos presentes en todo problema de LP.

Ejemplo 1. Una muebler´ıa produce mesas y sillas de madera. Cada mesa es vendida en $27000 y requiere $10000 en materiales, adem´ as, el costo de unitario por mano de obra se estima en $14000. En el caso de las sillas, su precio de venta es de $21000 y los costos son de $9000 y $10000, en materiales y mano de obra respectivamente. La fabricaci´ on de cada producto requiere de dos tipos de labores: carpinter´ıa y terminaciones. Una mesa requiere de 1 hora de carpinter´ıa y 2 horas de terminaciones. Una silla requiere de 1 hora de carpinter´ıa y 1 hora de terminaciones. Cada semana, la muebler´ıa puede obtener todos los materiales que desee, sin embargo, se pueden dedicar hasta 100 horas a las terminaciones y hasta 80 horas a la carpinter´ıa. La demanda por mesas no est´ a limitada, mientras que la demanda semanal m´ axima por sillas es de 40. La muebler´ıa desea maximizar sus utilidades (ingresos - costos). Formule un modelo matem´ atico que permita maximizar las utilidades.

1.1.

Variables de Decisi´ on

Se debe comenzar definiendo las variables de decisi´ on relevantes. En un modelo de programaci´on lineal las variables de decisi´on deben ser capaces de describir completamente las decisiones que puedan ser tomadas y todas las variantes que existan. Antes de definir las variables de decisi´on es importante definir las unidades involucradas en el problema. En este caso, se habla de unidades de sillas y mesas, de horas de trabajo por unidad y de demanda semanal. De acuerdo a ello, una buena opci´on para definir las variables de decisi´on consiste en asociar las variables al n´ umero de unidades de sillas y mesas a producir por semana. Por lo tanto, podemos definir: x1 = n´ umero de mesas producidas por semana. (1.1) x2 = n´ umero de sillas producidas por semana.

1

F.I.O. Segundo Semestre 2004

1.2.

Programaci´ on Lineal

Funci´ on Objetivo

En un problema de LP, se debe tomar la decisi´on de maximizar (usualmente las utilidades) o de minimizar (usualmente los costos) cierta funci´on de las variables de decisi´on. La funci´on a maximizar o minimizar se denomina funci´ on objetivo. Antes de formular el modelo matem´atico conviene resumir los datos del problema (Tabla 1.1). hVentai $ un. 27000 21000 –

Mesa Silla Disponibilidad

Materiales i h $ un. 10000 9000 –

Mano h de iObra $ un. 14000 10000 –

Carpinter´ i ıa h hr. un. 1 1 80

Terminaciones i h hr. un. 2 1 100

Dda. M´axima £ un. ¤ sem. – 40 –

Tabla 1.1: Resumen Ejemplo 1 En el ejemplo, los costos e ingresos no dependen del valor de x1 o de x2 , por lo tanto basta concentrarse en maximizar la diferencia entre: µ ¶ µ ¶ µ ¶ ingresos costos de costos por − − (1.2) semanales materiales mano de obra Luego, se debe expresar los t´erminos anteriores en funci´on de las variables de decisi´on x 1 y x2 . Supondremos que todas las sillas y mesas fabricadas son vendidas (respentando las condiciones de mercado del enunciado). As´ı: µ ¶ µ ¶ µ ¶ ingresos ingresos ingresos = + semanales por mesas por sillas = =

³

$ mesa

´¡

´³ ´ ³ mesas ¢ + $ sillas semana semana silla

27000x1

+

(1.3)

21000x2

Similarmente: ¶ costos por = 10000x1 + 9000x2 µ materiales ¶ costos por = 14000x1 + 10000x2 mano de obra µ

(1.4)

Por lo tanto la funci´on a maximizar queda (en miles): (27x1 + 21x2 ) − (10x1 + 9x2 ) − (14x1 + 10x2 ) = 3x1 + 2x2

(1.5)

Otra opci´on para construir la funci´on objetivo consiste en calcular previamente los ingresos netos o utilidades de cada uno de los productos de la muebler´ıa. As´ı: utilidad por mesa = 27 − 10 − 14 = 3 utilidad por silla = 21 − 9 − 10 = 2

(1.6)

As´ı, el objetivo de la muebler´ıa es escoger los valores de x1 y x2 tal que se maximize 3x1 + 2x2 . Denotando por z el valor de la funci´on objetivo para cualquier LP, la funci´on objetivo de la muebler´ıa es: 2

F.I.O. Segundo Semestre 2004

Programaci´ on Lineal

Maximizar z = 3x1 + 2x2

(1.7)

El coeficiente que acompa˜ na a cada variable en la funci´on objetivo se denomina coeficiente en la funci´ on objetivo de la variable y refleja el aporte unitario de dicha variable a la funci´on objetivo.

1.3.

Restricciones

En la medida que las variables x1 y x2 crecen, la funci´on objetivo aumenta su valor. Por lo tanto si se pudiera escoger arbitrariamente el valor de x1 y x2 , la muebler´ıa podr´ıa hacer crecer arbitrariamente el valor de sus utilidades. Evidentemente, en la pr´actica esto no es posible. En este ejemplo, el valor de las variables est´a limitado por las siguientes tres restricciones: Restricci´ on 1 : m´aximo 100 horas semanales para terminaciones Restricci´ on 2 : m´aximo 80 horas semanales para carpinter´ıa Restricci´ on 3 : producci´on m´axima de 40 sillas semanales Se asume que la cantidad disponible de material es ilimitada. Luego, el pr´oximo paso consiste en formular matem´aticamente las restricciones anteriores en funci´on de las variables de decisi´on. Para formular la primera restricci´on en funci´on de las variables x1 y x2 observamos que: ´ ³ ´¡ ³ mesas ¢ terminaciones terminaciones = semana semana mesa ³ ´ ´³ sillas (1.8) + terminaciones semana silla = 2x1 + 1x2 Por lo tanto la primera restricci´on queda:

2x1 + x2 ≤ 100

Es importante notar que todos los valores en la expresi´on anterior son por semana, ya que las variables de decisi´on se han escogido con esa referencia. An´alogamente la segunda restricci´on queda:

x1 + x2 ≤ 80

Finalmente, la tercera restricci´on s´olo limita el valor de x2 :

x2 ≤ 40

El valor que aparece a la derecha del signo de la desigualdad en cada restricci´on se denomina the constraint’s right-hand side (rhs) o coeficiente del lado derecho de la restricci´on. Usualmente, representa la cantidad disponible de cierto recurso.

1.4.

Restricci´ on de Signo

Para completar la formulaci´on del modelo es importante definir si existe alguna restricci´on de signo para cada variable de decisi´on. Si una variable de decisi´on xi debe cumplir condiciones de no-negatividad, debemos agregar la restricci´on xi ≥ 0. Si la variable de decisi´on xi puede asumir valores positivos y negativos se dice que la variable xi no tiene restricci´ on de signo (srs). En este ejemplo, ambas variables de decisi´on se refieren a cantidades a producir, por lo tanto son no-negativas, luego: x1 ≥ 0 y x2 ≥ 0. Sin embargo, en otros ejemplos las varibles pueden ser srs, por ejemplo en el caso de que xi se refiere al saldo de alguna cuenta.

3

F.I.O. Segundo Semestre 2004

Programaci´ on Lineal

Combinando todas las expresiones anteriores, es posible completar el modelo matem´atico para este problema de optimizaci´on: Max

z = 3x1 + 2x2 (Funci´on Objetivo)

sujeto a (st) 2x1 + x2 x1 + x 2 x2 x1 x2

≤ ≤ ≤ ≥ ≥

100 80 40 0 0

(Restricci´on (Restricci´on (Restricci´on (Restricci´on (Restricci´on

de de de de de

terminaciones) carpinter´ıa) demanda m´axima) signo) signo)

(1.9)

Se deja como ejercicio al lector determinar las modificaciones sobre el modelo anterior si: El excedente de horas de terminaciones puede ser empleado para carpinter´ıa y viceversa. La misma hip´otesis del punto anterior pero suponiendo que cada hora de terminaciones equivale a dos horas de carpinter´ıa. La producci´on de mesas no puede exceder al 40 % del total de unidades producidas de mesas y sillas.

2.

Generalizaci´ on Repasemos en primer lugar algunos conceptos de linealidad de funciones y desigualdades.

Definici´ on 1 Una funci´ on f (x1 , x2 , · · · , xn ) de x1 , x2 , · · · , xn es una funci´ on lineal s´ı y s´ olo s´ı para un conjunto de constantes c1 , c2 , · · · , cn , se tiene: f (x1 , x2 , · · · , xn ) = c1 x1 + c2 x2 + · · · + cn xn Definici´ on 2 Para cualquier funci´ on f (x1 , x2 , · · · , xn ) y cualquier n´ umero b las desigualdades: f (x1 , x2 , · · · , xn ) ≤ b f (x1 , x2 , · · · , xn ) ≥ b son desigualdades lineales. Definici´ on 3 Un problema de programaci´ on lineal (LP) es un problema de optimizaci´ on para el cual debemos tener presente lo siguiente: 1.

Se maximiza (o minimiza) una funci´ on lineal de las variables de decisi´ on. La funci´ on que es maximizada o minimizada se denomina funci´ on objetivo.

2.

Los valores de las variables de decisi´ on deben satisfacer un conjunto de restricciones. Cada restricci´ on debe ser una ecuaci´ on o desigualdad lineal.

3.

Existe una restricci´ on de signo asociada a cada variable. Para toda variable x i , la res- tricci´ on de signo especifica si xi debe ser no-negativa (xi ≥ 0)o bien sin restricci´ on de signo (srs).

De acuerdo a las definiciones anteriores, el ejemplo estudiado corresponde efectivamente a un LP, pues tanto la funci´on objetivo como las restricciones son funciones lineales de x 1 y x2 . El problema estudiado corresponde a un problema t´ıpico de decisi´on donde se debe obtener el programa de producci´on que maximiza las utilidades sujeto a recursos limitados.

4

F.I.O. Segundo Semestre 2004

3.

Programaci´ on Lineal

Consecuencias y Supuestos

El hecho que la funci´on objetivo de un PL sea una funci´on lineal de las variables de decisi´on tiene dos implicancias: 1. La contribuci´on a la funci´on objetivo de cada variable es proporcional al valor de la variable de decisi´on. 2. La contribuci´on a la funci´on objetivo para toda variable es independiente de los valores de las otras variables de decisi´on. An´alogamente, el hecho de que cada restricci´on sea una ecuaci´on o desigualdad lineal tambi´en tiene dos implicancias: 1. La contribuci´on de cada variable al coeficiente del lado izquierdo de cada restricci´on es proporcional al valor de la variable. 2. La contribuci´on de cada variable al coeficiente del lado izquierdo de cada restricci´on es independiente de los valores de las otras variables. Las primeras implicancias de la listas anteriores constituyen el Supuesto de Proporci´ on en LP. Las segundas implicancias de las listas anteriores constituyen el Supuesto de Adici´ on en LP. Para que un modelo de LP corresponda a una representaci´on adecuada de la realidad, las variables de decisi´on deben satisfacer los dos supuestos anteriores. Adicionalmente, se agregan dos supuestos: el supuesto de Divisibilidad y el de Certeza. El Supuesto de Divisibilidad requiere que cada variable de decisi´on pueda tomar valores fraccionarios. En el ejemplo anterior, el supuesto se traduce en que es aceptable producir 2.4 sillas ´o 1.6 mesas. Evidentemente, el supuesto de divisibilidad no se satisface en el ejemplo. En este caso se puede proceder a formular el modelo como un problema de programaci´ on lineal entera (ILP), problema en el cual una o m´as variables deben ser enteras. Este tipo de problema se estudiar´a m´as adelante. Cuando no se satisface el supuesto de divisibilidad, una posibilidad es redondear la soluci´on obtenida a un valor entero, sin embargo no existen garant´ıas que dicha soluci´on sea la mejor. El Supuesto de Certeza exige que cada par´ametro: coeficientes de la funci´on objetivo, coeficientes del lado derecho, etc. sean conocido con certeza, es decir, no se acepta incertidumbre en sus valores. Es claro que es muy dif´ıcil que un problema cumpla exactamente con todos los supuestos. Sin embargo, un modelo puede ser u ´til aunque difiera de la realidad si se es consistente con los requerimientos m´as estrictos del problema y se tienen presente las limitaciones al interpretar los resultados.

4.

´ Regiones Factibles y Soluciones Optimas

Dos de los conceptos m´as fundamentales en LP son el de regi´on factible y de soluci´on ´optima de un problema. Llamaremos punto a la especificaci´on de un valor para cada variable de decisi´on. Definici´ on 4 La regi´ on factible para un LP es el conjunto de puntos que satisfacen todas las restricciones (incluidas las de signo) de un problema de LP.

5

F.I.O. Segundo Semestre 2004

Programaci´ on Lineal

Definici´ on 5 En el caso de un problema de maximizaci´ on, una soluci´ on ´ optima del LP es un punto de la regi´ on factible que est´ a asociado al mayor valor posible de la funci´ on objetivo. Similarmente, para un problema de minimizaci´ on, una soluci´ on o ´ptima es un punto que est´ a asociado al menor valor posible de la funci´ on objetivo. La mayor´ıa de los problemas de LP tienen s´olo una soluci´on ´optima. Sin embargo, existen muchos problemas de LP que no poseen soluci´on ´optima o bien poseen varios o infinitos valores ´optimos.

5.

Algunos Ejemplos

5.1.

Problema de la Dieta

Una dieta diaria satisfactoria debe contener al menos 2000 [kCal], 55 [g] de prote´ınas y 800 [mg] de Calcio. Se pide formular un modelo que permita determinar una dieta satisfactoria de m´ınimo costo a partir de los alimentos indicados en el Tabla 5.1. h i £ ¤ Alimento Porci´on Energ´ıa [kCal] Prote´ınas [g] Calcio [mg] Precio u$ L´ımite d´uıa Avena Pollo Huevos Leche Pastel Cerdo

28 100 2 237 170 260

110 205 160 160 420 260

4 32 13 8 4 14

2 12 54 285 22 80

3 24 13 9 20 29

4 3 2 8 2 2

Tabla 5.1: Alimentos disponibles Modelo: En este caso resulta natural definir como variable de decisi´on xi la cantidad de alimento tipo ”i”(i = 1 . . . 6) a consumir. Como cada alimento tiene un costo, basta ponderar cada variable de decisi´on por su respectivo coeficiente y construir la funci´on objetivo a minimizar. Las restricciones obedecen a los l´ımites diarios de consumo por alimento y a las condiciones de energ´ıa, prote´ınas y calcio que debe cumplir la dieta. Por lo tanto, el modelo queda: Min z = 3x1 + 24x2 + 13x3 + 9x4 + 20x5 + 29x6 st 110x1 + 205x2 + 160x3 + 160x4 + 420x5 + 260x6 4x1 + 32x2 + 13x3 + 8x4 + 4x5 + 14x6 2x1 + 12x2 + 54x3 + 285x4 + 22x5 + 80x6 x1 x2 x3 x4 x5 x6 xi

6

(Funci´on Objetivo) ≥ ≥ ≥ ≤ ≤ ≤ ≤ ≤ ≤ ≥

2000 55 800 4 3 2 8 2 2 0 ∀i

(Energ´ıa m´ınima) (Proteinas m´ınimas) (Calcio m´ınimo) (Porci´on l´ımite) (Porci´on l´ımite) (Porci´on l´ımite) (Porci´on l´ımite) (Porci´on l´ımite) (Porci´on l´ımite) (Restricci´on de signo)

F.I.O. Segundo Semestre 2004

5.2.

Programaci´ on Lineal

Problema de Planificaci´ on de Personal

Las enfermeras de un hospital llegan cada 4 horas y trabajan en turnos de 8 horas continuas. La administraci´on ha decidido definir 6 cambios de turno al d´ıa para minimizar las distracciones y los problemas de comunicaci´on que ocurren en los cambios de turno. El hospital ha realizado un an´alisis del trabajo requerido durante cada uno de los seis bloques horarios del d´ıa. Las caracter´ısticas de cada bloque se muestran en el Tabla 5.2. Hora del D´ıa 2 AM - 6 AM 6 AM - 10 AM 10 AM - 2 PM 2 PM - 6 PM 6 PM - 10 PM 10 PM - 2 AM

Per´ıodo 1 2 3 4 5 6

N´ umero m´ınimo de enfermeras 25 60 50 35 55 40

Tabla 5.2: Caracter´ısticas de cada Bloque Horario. Las enfermeras que empiezan a trabajar en los per´ıodos 2, 3 y 4 ganan US$40 al d´ıa, y aquellas que comienzan en los per´ıodos 1, 5 y 6 ganan US$50 al d´ıa. ¿Cu´al es la planificaci´on de los turnos de las enfermeras que minimizan los costos por salarios? Modelo: En este caso podemos identificar como variable de decisi´on el n´ umero de enfermeras N i que comienza a trabajar en el turno ”i”(i = 1 . . . 6). De esta forma, la funci´on objetivo queda: z = 50N1 + 40N2 + 40N3 + 40N4 + 50N5 + 50N6 Evidentemente, la funci´on anterior debe ser minimizada. Para construir las restricciones es conveniente recurrir a una representaci´on gr´afica de los turnos (Figura 5.1).

1 N1

2 N2

Turno 3 4 N3

5

N4

N5

6

N6

Figura 5.1: Esquema de los turnos De la gr´afica anterior se observa que en cada bloque trabajan las enfermeras que comenzaron su turno en dicho bloque, pero tambi´en las que empezaron su turno en el bloque anterior. Por lo tanto, las restricciones de personal m´ınimo por turno quedan: N1 + N 2 N2 + N 3 N3 + N 4 N4 + N 5 N5 + N 6 N6 + N 1 7

≥ ≥ ≥ ≥ ≥ ≥

60 50 35 55 40 25

F.I.O. Segundo Semestre 2004

Programaci´ on Lineal

Finalmente, el modelo se completa con las restricciones de signo: Ni ≥ ∀ i

5.3.

Problema de Planificaci´ on de Producci´ on

La empresa Sil Computer necesita satisfacer la demanda de computadores por parte de sus clientes (grandes corporaciones e instituciones educacionales) para los pr´oximos 4 trimestres. Actualmente, Sil Computer tiene 5000 computadores en inventario. La demanda esperada para los pr´oximos trimestres son 7000, 15000, 10000 y 8000. Sil Computer tiene el material y la capacidad de producir hasta 10000 computadores cada trimestre, a un costo de US$ 2000 por computador. Empleando personal de sobretiempo se puede producir hasta 2500 computadores m´as a un costo individual de US$ 2200. Los computadores producidos en un trimestre pueden ser usados para satisfacer la demanda de ese per´ıodo, o bien quedar en inventario para ser usados posteriormente. Cada computador en inventario tiene un costo adicional de US$100 por per´ıodo para reflejar los costos de almacenaje. ¿Como puede satisfacer Sil Computer su demanda a costo m´ınimo? Modelo: En este caso la decisi´on a tomar corresponde a la producci´on de computadores por trimestre. Como se puede fabricar computadores en horario normal y en sobretiempo es conveniente separar ambos tipos de producci´on en variables distintas. Adem´as, se debe decidir en cada per´ıodo cuantas unidades guardar en inventario. Definamos las siguientes variables (∀ t = 1 . . . 4): xt = producci´on en el per´ıodo t en horario normal yt = producci´on en el per´ıodo t en sobretiempo it = inventario al final del per´ıodo t De acuerdo a las variables definidas podemos formular el modelo completo considerando el balance trimestral entre lo producido, lo proveniente del per´ıodo anterior en inventario y la demanda del trimestre respectivo. Min z = 2000(x1 + x2 + x3 + x4 ) + 2200(y1 + y2 + y3 + y4 ) + 100(i1 + i2 + i3 ) st 5000 + x1 + y1 = 7000 + i1 i1 + x 2 + y2 = 15000 + i2 i2 + x 3 + y3 = 10000 + i3 i3 + x 4 + y4 = 8000 xt ≤ 10000 ∀t yt ≤ 2500 ∀t x t , yt , i t ≥ 0 ∀t Para la formulaci´on anterior se ha supuesto que cada computador es completamente fabricado en horario normal o en sobretiempo y que las variables pueden ser no enteras. Evidentemente este supuesto puede no ser correcto en la situaci´on real, pero constituye una buena aproximaci´on del problema. Revisando la formulaci´on propuesta, se observa que no existe la variable i 4 ¿ Porqu´e no se incluye en el modelo ? ¿ Qu´e pasar´ıa si se incorporara ?

8

F.I.O. Segundo Semestre 2004

5.4.

Programaci´ on Lineal

Problema de Transporte

Supongamos un problema de transporte de alg´ un producto desde n or´ıgenes hacia m destinos. En cada origen hay una existencia de productos ei (i = 1 . . . n). En cada destino hay una demanda por dj unidades (j = 1 . . . m). El costo unitario de env´ıo desde cada origen i hacia cada destino j es de c ij . Formule un modelo de programaci´on lineal que permita definir la distribuci´on del producto de modo de minimizar los costos de transporte. Modelo: La decisi´on consiste simplemente en determinar el n´ umero de productos que son transportados desde cada origen hacia cada destino. Luego, se emplear´an las siguientes variables: xij

= cantidad enviada desde origen i a destino j

De acuerdo a las variables definidas, la funci´on objetivo queda: M in

n X m X

cij xij

i=1 j=1

Las restricciones corresponden a la capacidad m´axima en cada origen y a la demanda en cada destino. Adem´as, como las variables representan cantidades, deben ser positivas. Pm xij ≤ ei ∀ i = 1 . . . n (disponibilidad) Pj=1 n i=1 xij ≥ dj ∀ j = 1 . . . m (demanda) xij ≥ 0 ∀i×j (restricci´on de signo) El problema anterior se dice balanceado si se satisface que: n X

ei =

m X

dj

j=1

i=1

El problema anterior admite m´ ultiples variaciones como la incorporaci´on de l´ımites a la capacidad de cada ruta, incorporaci´on de costos fijos, puntos de transbordo, rutas alternativas entre otras posibilidades. Este tipo de problema es muy vers´atil y puede ser aplicado a muchas situaciones que no necesariamente se refieren a transporte, adem´as posee su propio algoritmo de resoluci´on. ¿ C´omo cambiar´ıa la formulaci´on si se incorporaran k puntos de transbordo, es decir, puntos intermedios sin demanda ni oferta, pero que pueden servir como rutas alternativas para disminuir costos de env´ıo desde un origen i a alg´ un destino j ?

5.5.

Problema de Mezcla

Una refiner´ıa de petr´oleos produce dos tipos de gasolina sin plomo: regular y extra, los cuales vende a su cadena de estaciones de servicio en US$12 y US$14 por barril, respectivamente. Ambos tipos se preparan del inventario de petr´oleo nacional refinado y de petr´oleo importado refinado que tiene la refiner´ıa y deben cumplir las especificaciones que se presentan en el Tabla 5.3. Las caracter´ısticas del inventario de petr´oleos refinados se muestran en el Tabla 5.4. Formule un modelo de programaci´on lineal que permita maximizar la ganancia semanal de la refiner´ıa.

9

F.I.O. Segundo Semestre 2004

Regular Extra

Programaci´ on Lineal

Presi´on m´axima de vapor 23 23

Octanaje m´ınimo 88 93

Demanda m´axima [barril/semana] 100.000 20.000

Entregas m´ınimas [barril/semana] 50.000 5.000

Tabla 5.3: Especificaciones de las gasolinas

Nacional Importado

Presi´on de vapor 25 15

Octanaje 87 98

Inventario [barril] 40.000 60.000

Costo [US$/barril] 8 15

Tabla 5.4: Caracter´ısticas de los petr´oleos Modelo: Para poder formular un modelo para el problema supondremos que no existen p´erdidas en el proceso de refinamiento y que tanto el octanaje como la presi´on de vapor se pueden mezclar linealmente. De acuerdo al supuesto anterior debemos definir variables que nos permitan controlar que proporci´on de cada tipo de petr´oleo se emplear´a para fabricar cada tipo de gasolina, as´ı: xij

= cantidad de petr´oleo refinado tipo i (i = 1, 2) para fabricar gasolina j (j = 1, 2)

Donde petr´oleo refinado tipo 1 corresponde a Nacional y tipo 2 a Importado, gasolina 1 equivale a Regular y gasolina 2 a Extra. Consideremos las variables anteriores en barriles, de modo de emplear las proporciones entregadas en el enunciado. Como se conoce el precio de venta de cada gasolina y el costo de cada petr´oleo, la funci´on objetivo se reduce a maximizar la diferencia entre ingresos y costos, es decir, las utilidades. M ax

12(x11 + x21 ) + 14(x12 + x22 ) − 8(x11 + x12 ) − 15(x21 + x22 )

A continuaci´on construimos las restricciones. Las restricciones respecto de inventario disponible y demanda de cada tipo de gasolina se explican por s´ı solas: x11 + x12 x21 + x22 x11 + x21 x11 + x21 x12 + x22 x12 + x22

≤ ≤ ≥ ≤ ≥ ≤

40000 60000 50000 100000 5000 20000

(Inventario petr´oleo tipo 1) (Inventario petr´oleo tipo 2) (Demanda m´ınima de gasolina tipo 1) (Demanda m´axima de gasolina tipo 1) (Demanda m´ınima de gasolina tipo 2) (Demanda m´axima de gasolina tipo 2)

Las restricciones de presi´on de vapor y de octanaje m´ınimo deben ser normalizadas respecto de la

10

F.I.O. Segundo Semestre 2004

Programaci´ on Lineal

cantidad total fabricada, que no es necesariamente la cantidad m´axima o m´ınima posible de fabricar. 25x11 +15x21 x11 +x21 25x12 +15x22 x12 +x22 87x11 +98x21 x11 +x21 87x12 +98x22 x12 +x22

≤ ≤ ≥ ≥

23 23 88 88

(Presi´on de vapor m´axima gasolina tipo 1) (Presi´on de vapor m´axima gasolina tipo 2) (Octanaje m´ınimo gasolina tipo 1) (Octanaje m´ınimo gasolina tipo 2)

Finalmente, el modelo queda completo con las condiciones de signo: xij

5.6.

≥ 0 ∀i×j

Problema de Producci´ on y Asignaci´ on de Personal

Un peque˜ no taller arma dispositivos mec´anicos, ya sea como un producto terminado que entrega al mercado, o como un proceso intermedio para entregar a una gran f´abrica. Trabajan 3 personas en jornadas de 40 horas semanales. Dos de estos obreros no calificados reciben $0,4 por hora, y el tercero, un obrero calificado recibe $0,6 por hora. Los tres est´an dispuestos a trabajar hasta 10 horas adicionales a la semana con un salario 50 % superior durante este per´ıodo. Los costos fijos semanales son de $800. Los gastos de operaci´on variable son de $1,0 por hora de trabajo de obrero no calificado y $2,4 por hora de obrero calificado. Los dispositivos mec´anicos sin acabar son vendidos a la planta a $6,5 cada uno. El taller tiene un contrato bajo el cual debe entregar 100 de estos dispositivos semanalmente a la empresa. El due˜ no del taller tiene como pol´ıtica el producir no m´as de 50 dispositivos a la semana por sobre el contrato. Los dispositivos terminados se venden a $15 cada uno sin restricciones de mercado. Se requieren 0,5 horas de obrero no calificado y 0,25 horas de obrero calificado para producir un dispositivo sin acabar listo para entregar a la otra empresa. Uno de estos dispositivos puede ensamblarse y dejarlo terminado agreg´andole 0,5 horas de trabajador calificado. Un dispositivo listo para entregar al mercado se puede producir con 0,6 horas de obrero no calificado y 0,5 horas de obrero calificado. Plantear el modelo de Programaci´on Lineal que permita responder la consulta: ¿ C´omo y cu´anto producir para cumpir el contrato de modo de maximizar las utilidades ? Modelo: En este caso, es posible establecer tres tipo de productos: intermedio (i = 1), intermedio que se acaba (i = 2) y acabado (i = 3). Por lo tanto, se puede definir las siguientes variables: xi = cantidad de productos tipo i fabricados

i = 1, . . . 3

De acuerdo al enunciado, los dos obreros no calificados y el obrero calificado trabajan 40 horas semanales fijas, por lo tanto, s´olo es necesario cuantificar como variables las horas extraordinarias de trabajo. zj = horas extraordinarias de los trabajadores tipo j j = 1, 2 Donde tipo 1 corresponde a obreros no calificados y tipo 2 a obreros calificados.

11

F.I.O. Segundo Semestre 2004

Programaci´ on Lineal

Como existe informaci´on de costos de producci´on y de precio de venta para razonable plantear el problema como uno de maximizaci´on de utilidades. Luego, debemos expresar la diferencia entre ingresos (I) y costos (C) como funci´on de las variables de decisi´on: I

= 6,5 × x1 + 15 (x2 + x3 )

C = 2 × 40 × 0,4 + 0,6 × z1 + 1 × 40 × 0,6 + 0,9 × z2 + | {z } | {z } sueldos o.n.c. sueldos o.c. 1 × (2 × 40 + z1 ) + 2,4 (1 × 40 + z2 ) + 800 |{z} {z } | costos fijos gastos de operaci´on variables

Luego, la funci´on objetivo queda: Z =I −C

M ax

De acuerdo al enunciado, existen l´ımite inferior y superior para la demanda de productos intermedios: x1 ≥ 100 x1 ≤ 150 Las otras restricciones tienen que ver con la disponibilidad de mano de obra para producci´on: 0,5 (x1 + x2 ) + 0,6 × x3 z1 0,25 × x1 + 0,75 × x2 + 0,5 × x3 z2

≤ ≤ ≤ ≤

80 + z1 20 40 + z2 10

Finalmente, se deben incorporar la restricciones de signo: x i , zj

5.7.

≥ 0

∀ i, j

Ejemplos adicionales

1. Una determinada aerol´ınea, con centro en Santiago, est´a dise˜ nando un nuevo sistema de atenci´on a pasajeros que realicen viajes a cuatro destinos espec´ıficos: Antofagasta, Temuco, Puerto Montt y Punta Arenas. Para eso consta de tres tipos de aviones, los que difieren en capacidad, rendimiento y costos, seg´ un se muestra en el Tabla 5.5. Hist´oricamente para esta ´epoca se tiene Tipo de Avi´on 1 2 3

Costo de Operaci´on por viaje en la ruta: Antofagasta Temuco Puerto Montt Punta Arenas 1000 1100 1200 1500 800 900 1000 1000 600 800 800 900 Tabla 5.5: Costos de operaci´on por viaje

una demanda m´ınima diaria de 90 pasajeros a Antofagasta, 100 a Temuco, 200 a Puerto Montt y de 120 pasajeros a Punta Arenas. Adem´as, lo que la aerol´ınea recibe por pasajero a cada lugar es de 40 si el destino es Antofagasta, 40 si el destino es Temuco, 45 si el destino es Puerto Montt y 70 si se viaja a Punta Arenas. Los datos tanto de operaci´on y de disponibilidad que actualmente tiene la aerol´ınea se muestran en el Tabla 5.6. Finalmente, se ha dispuesto (de preferencia, pero no obligatoriamente) atender 12

F.I.O. Segundo Semestre 2004

Programaci´ on Lineal

Tipo de Avi´on 1 2 3

Capacidad (pasajeros) 50 30 20

N´ umero de Aviones 5 8 10

Tabla 5.6: Capacidad y disponibilidad de aviones Tipo de Avi´on 1 2 3

N´ umero m´aximo de viajes diarios a: Antofagasta Temuco Puerto Montt Punta Arenas 3 2 2 1 4 3 3 2 5 5 4 2 Tabla 5.7: Costos de operaci´on por viaje

m´as de una ruta por cada tipo de avi´on, ante lo cual se han planteado condiciones al dise˜ no del sistema de pasajeros (Tabla 5.7). Determinar el modelo de programaci´on lineal que permita optimizar la asignaci´on de los aviones a las distintas rutas. Modelo: Para plantear el problema, se debe definir variables de decisi´on que sean capaces de reflejar el tipo de avi´on (i = 1, . . . 3) y el destino (j = 1, . . . 4) al que es asignada. Luego, se define: xij

= n´ umero de aviones de tipo i asignados al destino j

En este problema, no se conoce el valor exacto de la demanda por pasajes ya que s´olo se conoce el valor m´ınimo de la demanda por pasajes. Por lo tanto, se puede formular la funci´on objetivo de dos formas: como un un problema de maximizaci´on de las utilidades obtenidas de la diferencia entre el ingreso m´ınimo asociado a la demanda m´ınima conocida y el costo de asignaci´on de los aviones (ingresos constantes), o bien simplemente como un problema de minimizaci´on de costos de asiganci´on. Intuitivamente es claro que maximizar una constante menos unas funci´on frente a minimizar la misma funci´on es equivalente, por lo que cualquiera de las dos formulaciones conduce a la misma soluci´on. Luego, la funci´on objetivo queda: 4 3 X X

Min

cij × xij

i=1 j=1

Donde los coeficientes cij corresponden a los datos del Tabla 5.5. Luego, se procede a plantear las restricciones. En primer lugar se debe garantizar poder satisfacer la demanda m´ınima, por lo tanto basta ponderar la capacidad de cada tipo de avi´on por el n´ umero asignado a cada destino j: 50x1j + 30x2j + 20x3j ≥ dj ∀ j = 1, . . . 4 Donde dj representa la demanda de cada destino j, es decir: 90, 100, 200 y 120 para Antofagasta, Temuco, Puerto Montt y Punta Arenas, respectivamente.

13

F.I.O. Segundo Semestre 2004

Programaci´ on Lineal

Por otro lado, no es posible asignar m´as aviones de los disponibles: 4 X

∀ i = 1, . . . 3

xij ≤ ni

j=1

Donde ni representa la disponibilidad del tipo de avi´on i, es decir, 5, 7 y 10. Tambi´en existe una restricci´on asociada al n´ umero de viajes diarios m´aximo por tipo de avi´on i a cada destino j: xij ≤ mij ∀i×j Los coeficientes mij corresponden a los datos del Tabla 5.7. Finalmente, s´olo se debe agregar la restricci´on de signo: xij ≥ 0

∀i×j

2. Un importador de whisky est´a planificando su negocio considerando que en las pr´oximas temporadas tendr´a las siguientes demandas (en miles de botellas): Tipo Seco Frutoso A˜ nejo

Temporadas 1 2 3 4 10 12 14 8 13 15 17 19 21 25 9 11

El whisky seco lo vende a 34 unidades monetarias por botella, el frutoso a 28, 5 y el a˜ nejo a 22, 5, en las primeras dos temporadas. En las siguientes temporadas se espera poder venderlos en un 5 % m´as caro. Cada tipo de whisky es elaborado mezclando tres materias primas, A, B y C, de las cuales puede importar un m´aximo de 2000, 2500 y 1200 botellas por temporada a un costo de 35, 25 y 20 unidades monetarias, respectivamente. Estos costos, v´alidos para la primera temporada, deber´ıan aumentar un 2 % en cada temporada. El whisky seco debe contener por lo menos un 60 % de la materia prima 1 y no m´as de un 20 % de la materia prima 3, el frutoso debe contener por lo menos un 15 % de la materia prima 1 y no m´as de un 60 % de la materia prima 3, y el a˜ nejo debe contener por lo menos un 50 % de la materia prima 2. Cada botella de whisky fabricada en una temporada puede ser vendida en dicha temporada o almacenada a un costo unitario por temporada de 0, 5 unidad monetaria para ser vendida posteriormente. Formule un modelo de programaci´on lineal que permita optimizar las actividades del importador. Defina claramente variables, funci´on objetivo y restricciones. Modelo: Variables: xijk = cantidad de materia prima k para fabricar whisky i en temporada j yij

= cantidad de whisky tipo i vendido en temporada j

zij

= cantidad de whisky tipo i almacenado en temporada j

14

F.I.O. Segundo Semestre 2004

Programaci´ on Lineal

Funci´on objetivo: m´ax

4 X

(1 + (j − 1) × 0,05) (34y1j + 28,8y2j + 22,5y3j )

j=1

−

4 X 3 X

(1 + (j − 1) × 0,02) (35xijA + 25xijB + 20xijC ) − 0,5

j=1 i=1

3 X 3 X j=1 i=1

Restricciones: • Disponibilidad de materia prima: 3 X

xijA ≤ 2000

∀ j = 1...4

3 X

xijB ≤ 2500

∀ j = 1...4

≤ 1200

∀ j = 1...4

i=1

i=1 3 X

xijC

i=1

• Venta m´axima por temporada: y11 ≤ 10 y12 ≤ 13 y13 ≤ 21

y12 ≤ 12 y22 ≤ 15 y23 ≤ 25

y13 ≤ 14 y23 ≤ 17 y33 ≤ 9

y14 ≤ 8 y24 ≤ 19 y34 ≤ 11

• Proporciones de materias primas: x1jA ≥ 0,6

x1jC

≤ 0,2

C X

k=A C X

x1jk

∀ j = 1...4

x1jk

∀ j = 1...4

k=A C X

x2jA ≥ 0,15

x2jk

∀ j = 1...4

k=A

x2jC

≤ 0,6

x3jB ≥ 0,5

C X

k=A C X

k=A

15

x2jk

∀ j = 1...4

x3jk

∀ j = 1...4

zij

F.I.O. Segundo Semestre 2004

Programaci´ on Lineal

• Producci´on, ventas y almacenaje por temporada: C X

xi1k = yi1 + zi1

∀ i = 1...3

xi2k + zi1 = yi2 + zi2

∀ i = 1...3

xi3k + zi2 = yi3 + zi3

∀ i = 1...3

k=A C X

k=A C X

k=A C X

xi4k + zi3 = yi4

∀ i = 1...3

k=A

• Naturaleza de las variables: xijk ≥ 0 yij , zij

≥ 0

∀ i, j, k ∀ i, j

3. Considere el problema de programaci´on de la producci´on de un conjunto de m tipos diferentes de art´ıculos para los pr´oximos n meses en una f´abrica: En cuanto al uso de materias primas, el costo de producir un art´ıculo de tipo i se estima en ci . Producir un art´ıculo de tipo i requiere moi horas de mano de obra, disponiendo la f´abrica de hj horas de mano de obra durante el mes j. En ciertos meses, la f´abrica puede emplear horas extras para aumentar sus recursos de mano de obra. En general, se puede denotar por stj la cantidad m´axima de horas extras disponibles en el mes j, cada una con un costo unitario de cst. La demanda por art´ıculos de tipo i en el mes j se estima en dij , las cuales necesariamente deben ser satisfechas. El exceso de producci´on puede ser almacenado a un costo mensual unitario de s. Existe capacidad para almacenar un volumen m´aximo de v, pudi´endose representar por v i el volumen de un art´ıculo de tipo i. Pol´ıticas de producci´on exigen que al final del per´ıodo bajo consideraci´on exista un inventario m´ınimo de si unidades de art´ıculos de tipo i. Formule un modelo de programaci´on lineal que permita planificar la operaci´on de la f´abrica durante los pr´oximos n meses de forma tal de minimizar el costo total. Defina claramente variables, funci´on objetivo y restricciones. Modelo: Variables: xij : Cantidad de art´ıculos de tipo i producidos en el mes j; ∀i = 1, . . . , m, j = 1, . . . , n. sij : Cantidad de art´ıculos de tipo i almacenados en el mes j; ∀i = 1, . . . , m, j = 1, . . . , n. yj : Cantidad de horas extras de mano de obra en el mes j: ∀j = 1, . . . , n. Funci´on objetivo:

16

F.I.O. Segundo Semestre 2004

Programaci´ on Lineal

Minimizar costo total = costo de producci´on + costo de mano de obra + costo de almacenamiento M in z =

m n X X

xij × ci +

n X

yj × cst +

j=1

j=1 i=1

m n X X

sij × s

j=1 i=1

Restricciones • Mano de obra: m X

xij × moi ≤ hj + yj ∀j = 1, . . . , n

i=1

yj

≤ stj ∀j = 1, . . . , n

• Demanda: sij = sij−1 + xij − dij ∀i = 1, . . . , m, j = 1, . . . , n • Almacenamiento: m X

sij × vi ≤ v ∀j = 1, . . . , n

i=1

• Inventario final: sin ≥ si ∀i = 1, . . . , m • No-negatividad: xij , sij , yj ≥ 0 ∀i = 1, . . . , m, j = 1, . . . , n 4. El Alto Mando Norteamericano emple´o un modelo de programaci´on lineal para planificar la invasi´on de sus fuerzas armadas a Irak. El plan consisti´o en desembarcar tropas y veh´ıculos militares en las proximidades de la ciudad de Basora, para luego avanzar por tierra a la ciudad de Nasiriya, luego a Karbala, a continuaci´on a Bagdad y finalmente a Mosul. El n´ umero de tropas requeridas para tomar cada una de las cinco ciudades se calcul´o en T i (i = 1 . . . 5). Se estim´o que en cada asalto podr´ıan perecer el 5 % de las tropas y podr´ıan perderse el 2 % de los veh´ıculos militares. El costo unitario de trasladar las tropas y veh´ıculos por tierra entre las ciudades i y j se estim´o en kij y mij , respectivamente. Una vez conquistada una ciudad, el n´ umero de soldados necesarios para asegurar su control se estim´o en Ci . Evidentemente, las tropas dejadas en una ciudad para asegurar su control no pueden seguir en la campa˜ na de invasi´on. En cada tropa, en las que participan en la invasi´on y en las que aseguran cada ciudad, se debe asegurar que al menos exista un veh´ıculo cada 10 soldados. Previo a la invasi´on de cada ciudad, es posible reforzar el contingente militar enviando paracaidistas. El costo de enviar cada soldado en avi´on se estim´o en p, independiente del punto de destino. Los costos de desembarco se estimaron en b para los soldados y en d para los veh´ıculos militares. 17

F.I.O. Segundo Semestre 2004

Programaci´ on Lineal

Formule un modelo de programaci´on lineal que permita planificar la invasi´on de Irak a costo m´ınimo. Modelo: Variables: xi = n´ umero de soldados que llegan por tierra a la ciudad i (i = 1 . . . 5) yi = n´ umero de soldados que llegan por aire a la ciudad i (i = 1 . . . 5) zi = n´ umero de soldados que se quedan en la ciudad i (i = 1 . . . 5) vi = n´ umero de veh´ıculos que llegan a la ciudad i (i = 1 . . . 5) qi = n´ umero de veh´ıculos que se quedan en la ciudad i (i = 1 . . . 5) Funci´on objetivo: M in z = b × x1 + d × y1 +

5 X

ki−1 i × xi +

i=2

5 X

mi−1 i × vi + p

i=2

Restricciones: Basora: x1 + y 1 ≥ T 1 z1 ≥ C 1 x2 = 0,95(x1 + y1 ) − z1 1 (x1 + y1 ) v1 ≥ 10 1 z1 q1 ≥ 10 v2 = 0,98v1 − q1 Nasiriya: x2 + y 2 ≥ T 2 z2 ≥ C 2 x3 = 0,95(x2 + y2 ) − z2 1 (x2 + y2 ) v2 ≥ 10 1 q2 ≥ z2 10 v3 = 0,98v2 − q2 Karbala: x3 + y 3 ≥ T 3 z3 ≥ C 3 x4 = 0,95(x3 + y3 ) − z3 1 v3 ≥ (x3 + y3 ) 10 1 z3 q3 ≥ 10 v4 = 0,98v3 − q3 18

5 X i=1

yi

F.I.O. Segundo Semestre 2004

Programaci´ on Lineal

Bagdad: x4 + y 4 ≥ T 4 z4 ≥ C 4 x5 = 0,95(x4 + y4 ) − z4 1 v4 ≥ (x4 + y4 ) 10 1 q4 ≥ z4 10 v5 = 0,98v4 − q4 Mosul: x5 + y 5 ≥ T 4 z5 ≥ C 5 1 (x5 + y5 ) v5 ≥ 10 1 q5 ≥ z5 10 Naturaleza de las variables: x i , yi , z i , v i , q i ≥ 0

19