Issuu

Investigación de Operaciones Unidad 1. Programación lineal, planteamiento de problemas Contenido nuclear

Universidad Abierta y a Distancia de México Licenciatura en Matemáticas 11° Cuatrimestre Programa de la asignatura Investigación de operaciones

Clave 050941142

Unidad 1. Programación lineal, planteamiento de problemas

Ciencias exactas e ingenierías/Licenciatura en Matemáticas

Investigación de Operaciones Unidad 1. Programación lineal, planteamiento de problemas Contenido nuclear

´Indice general Introducci´ on

1. Programaci´ on lineal, planteamiento de problemas 1.1. Planteamiento de problemas de programaci´on lineal . . . . . . . . . . 1.2. Forma del planteamiento del PPL . . . . . . . . . . . . . . . . . . . .

5 5 9

Bibliografı´a

Ciencias exactas e ingenierías/Licenciatura en Matemáticas

Investigación de Operaciones Unidad 1. Programación lineal, planteamiento de problemas Contenido nuclear

Introducci´ on La programación lineal es una de las técnicas más utilizadas en la modelación y resolución de problemas que surgen en la Investigación de Operaciones, esta técnica modela problemas en donde se busca optimizar el valor de una función objetivo que es lineal en las variables de decisión y donde también se debe cumplir un conjunto de relaciones lineales entre dichas variables. La programación lineal tiene un desarrollo importante a partir de la Segunda Guerra Mundial, en donde su uso resolvió importantes problemas de asignación de recursos. Las aplicaciones de la programación lineal posteriores a la guerra son variados, hoy constituyen una de las herramientas más utilizadas para los modelos de planificación de actividades y su éxito ha rebasado el a´mbito de los departamentos de Investigación de Operaciones, ha llegado a convertirse en una herramienta u ´ til para la toma de decisiones debido a la capacidad de modelar problemas grandes y complejos y la habilidad de los usuarios para resolver problemas a gran escala en un lapso de tiempo razonable con ayuda de computadoras. En esta unidad se aborda el planteamiento de problemas de programación lineal y la forma que puede tener el palanteamiento.

Ciencias exactas e ingenierías/Licenciatura en Matemáticas

Investigación de Operaciones Unidad 1. Programación lineal, planteamiento de problemas Contenido nuclear

Etapas de la Investigación de Operaciones

Ciencias exactas e ingenierías/Licenciatura en Matemáticas

Investigación de Operaciones Unidad 1. Programación lineal, planteamiento de problemas Contenido nuclear

Cap´ıtulo 1 Programaci´ on lineal, planteamiento de problemas 1.1.

Planteamiento de problemas de programaci´ on lineal

La creación del modelo lineal que representa al problema real puede ser una actividad ingeniosa y no hay una fórmula para plantear los problemas, además hay un campo de aplicación muy vasto y en cada área se obtienen diferentes planteamientos de programación lineal. Para ilustrar la forma de plantear modelos lineales vamos a considerar algunas situaciones representativas como: problemas de producción, asignación, transporte, mezclas, dieta, almacén. Otros tipos de problemas que no abordamos son, por ejemplo, econom´ıa, horarios, inventarios, planificación financiera, distribución de actividades. Ejemplo 1. Se lanzan dos nuevos productos al mercado para la actual temporada construidos con piezas nacionales e importadas. El modelo T que se fabrica con doble suspensión y cuadro nacional con un precio de venta de $ 220, el modelo W lleva triple suspensión, tijera importada y cuadro nacional, su precio es de $ 330. Las piezas se arman y ajustan en talleres que disponen de un total de 260 y 1100 horas hombre para cada actividad. La cantidad de horas hombre Modelo Armado Ajuste que requiere cada modelo por taller son: T 3 10 W 2 11

Los costos y la disponibilidad de los materiales son los siguientes:

Pieza Doble. Susp. Triple. Susp. Tijera Import. Cuadro Nal.

Ciencias exactas e ingenierías/Licenciatura en Matemáticas

Costo 70 100 90 100

Disponibilidad 80 70 260 100

Investigación de Operaciones Unidad 1. Programación lineal, planteamiento de problemas Contenido nuclear ´ LINEAL, PLANTEAMIENTO DE PROBLEMAS CAPÍTULO 1: PROGRAMACION La experiencia en ventas del periodo anterior para modelos similares estima que la demanda será tal, que se requieren al menos 3 modelos T por cada 7 modelos W. Una parte importante del planteamiento del problema es definir las variables de decisión, si se definen adecuadamente es posible expresar con ellas todos los requerimientos del problema. Para este caso observamos que se desea conocer cuantos modelos se producirán para la actual temporada, por lo que definimos las variables como: t.- Cantidad de modelos T a producir para la actual temporada w.- Cantidad de modelos W a producir para la actual temporada La disponibilidad de suspensiones dobles, triples y cuadros nacionales limita la producción de los modelos T y W, puesto que son componentes imprescindibles, las primeras restricciones son: t ≤ 80, w ≤ 70 y t + w ≤ 100. Esta u ´ ltima restricción se debe a que ambos modelos incluyen cuadro nacional para su producción y sólo se dispone de 100 cuadros. La disponibilidad de horas hombre para el taller de armado y de ajuste nos dan las siguientes restricciones: 3t + 2w ≤ 260 y 10t + 11w ≤ 1100 respectivamente, además la experiencia en ventas del periodo anterior se refleja con la restricción −7t + 3w ≤ 0 y por u ´ ltimo, las restricciones de no negatividad t ≥ 0, w ≥ 0, pues no tiene sentido producir cantidades negativas. Se puede pensar que debemos restringir los valores de las variables t y w en el conjunto de n´ umeros enteros, puesto que no tiene sentido producir fracciones de alg´ un modelo, sin embargo en la programación lineal se aceptan resultados fraccionales y los casos que estrictamente requieren soluciones enteras se resolverán con programación entera1 . El objetivo es maximizar la utilidad de la producción, que resulta de sumar la utilidad del modelo T con la utilidad del modelo W: (precio de T-costo de T) x unidades producidas de T + (precio de W-costo de W) x unidades producidas de W, es decir, (220-70-100)t+(330-100-90-100)w, o bien, 50t + 40w. Por lo que el planteamiento que obtenemos es el siguiente: Max s.a. P

z = 50t + 40w t ≤ 80 w ≤ 70 t + w ≤ 100 3t + 2w ≤ 260 10t + 11w ≤ 1100 −7t + 3w ≤ 0 t, w ≥ 0

Puede consultar bibliograf´ıa que aborde el tema de programaci´on entera.

Ciencias exactas e ingenierías/Licenciatura en Matemáticas

Investigación de Operaciones Unidad 1. Programación lineal, planteamiento de problemas Contenido nuclear ´ LINEAL 1.1 PLANTEAMIENTO DE PROBLEMAS DE PROGRAMACION Usualmente se escriben las restricciones del problema abajo de la función objetivo poniendo las letras s.a. para abreviar a la frase sujeto a las restricciones. Ejemplo 2. La compa˜ n´ıa Pemex produce en sus refiner´ıas gasolina magna, m, y gasolina s´ uper, s, a partir de dos tipos de crudos C1 y C2 . Cuenta con dos tipos de tecnolog´ıas para el proceso: la nueva y la anterior, denotadas por Tn y Ta , respectivamente. La tecnolog´ıa nueva utiliza en cada sesión de destilación 7 unidades de C1 y 12 de C2 para producir 8 unidades de gasolina m y 5 de gasolina s; con la tecnolog´ıa anterior, en cada destilación se obtienen 10 unidades de gasolina m y 7 de s con un consumo de 10 unidades de C1 y 8 de C2 . Estudios de demanda permiten estimar que el próximo mes se deben producir al menos 900 unidades de m y entre 700 y 1700 unidades de s. La disponibilidad del crudo C1 y C2 son 1400 y 2000, respectivamente. Los beneficios por unidad de gasolina producida son $4 y $7, para m y s, respectivamente. Se desea conocer cómo utilizar parcial o total ambos procesos as´ı como el crudo disponible para que el beneficio sea máximo. Es muy u ´ til esquematizar la información involucrada en el problema, en este caso proponemos el siguiente esquema. 7C1

8m Tn

12C2

10C1

10m Ta

8C2

umero de destilaciones con cada tecnoObservamos que se desea conocer el n´ log´ıa, por lo que definimos las variables de decisi´on como sigue. x1 .- N´ umero de destilaciones con la tecnolog´ıa nueva x2 .- N´ umero de destilaciones con la tecnolog´ıa anterior La disponibilidad de ambos tipos de crudo generan las restricciones 7x1 + 10x2 ≤ 1400 y 12x1 + 8x2 ≤ 2000, de acuerdo a las cantidades del crudo necesarias para la destilaci´on con cada tipo de tecnolog´ıa. Si se realizan x1 destilaciones con Tn y x2 destilaciones con Ta , los productos obtenidos son 8x1 + 10x2 unidades de m y 5x1 + 7x2 unidades de s. Por lo que el beneficio resulta 4(8x1 + 10x2 ) + 7(5x1 + 7x2 ) = 67x1 + 89x2

Ciencias exactas e ingenierías/Licenciatura en Matemáticas

7x1 + 10x2 ≤ 1400 12x1 + 8x2 ≤ 2000 8x1 + 10x2 ≥ 900

5x1 + 7x2 ≥ 300 5x1 + 7x2 ≤ 1700 x1 , x2 ≥ 0. En los ejemplos anteriores se explicaron y justificaron las restricciones as´ı como la función objetivo, esto se debe a que se desea ilustrar la manera de realizar los planteamientos. Sin embargo, cuando se pide escribir el planteamiento de un problema lo más com´ un es proponer el planteamiento haciendo solo algunas observaciones, como se muestra en el siguiente ejemplo. Ejemplo 3. Problema de Almacén. Una empresa que se dedica a la compra y venta de harina tiene un alamacén con capacidad de 730 t, t indica toneladas. En la actualidad dispone de 265 t de reserva y maneja una predicción de los precios por tonelada, en miles de pesos, para los próximos 7 meses como se indica en la tabla. Mes Precio

1 2 80 90

3 4 5 6 7 100 95 110 130 125

Hay un costo de almacenamiento por tonelada-mes de 6000 pesos. El precio de la harina tiene variaciones, de modo que la empresa busca una pol´ıtica de compra a precios bajos y venta cundo éstos son más altos, teniendo en cuenta que esto es posible debido a que el mercado es muy dinámico y siempre hay disponibilidad y demanda de harina. La empresa desea construir un modelo de programación lineal que refleje tal pol´ıtica proporcionando el mayor beneficio posible. Las variables de decisión van a ser: Ci .- Cantidad de harina a comprar en el mes i Vi .- Cantidad de harina a vender en el mes i Ai .- Cantidad de harina almacenada el mes i con i = 1, 2, 3, 4, 5, 6, 7. La relación dinámica entre estas variables está determinada por la ecuación inventario

i−1

+ compra i = venta i + inventario

Ciencias exactas e ingenierías/Licenciatura en Matemáticas

Investigación de Operaciones Unidad 1. Programación lineal, planteamiento de problemas Contenido nuclear FORMA DEL PLANTEAMIENTO DEL PPL 1.2 El problema del Almac´en resulta Max

z = 80(V1 − C1 ) + 90(V2 − C2 ) + 100(V3 − C3 ) + 95(V4 − C4 )

+110(V5 − C5 ) + 130(V6 − C6 ) + 125A6 − 6(A1 + A2 + A3 + A4 + A5 + A6 ) Ai ≤ 730, i = 1, ..., 6

s.a.

V1 + A1 − C1 = 265 Vi+1 + Ai+1 − Ci+1 − Ai = 0, i = 1, ..., 6 Ai , Ci , Vi ≥ 0, i = 1, ..., 7. Observemos que las restricciones no excluyen la posibilidad de que en el mismo mes se compre y venda, sin embargo, alguna de las variables Ci o Vi deber´ıa ser igual a cero, pues no tiene sentido comprar y vender cuando el precio en ambos casos es el mismo. Si en la solución óptima existe alg´ un i con la condición Ci > 0 y Vi > 0, entonces redefinimos los valores de las variables de la siguiente manera Ci = Ci − min{Ci , Vi }, Vi = Vi − min{Ci , Vi }, que mantiene la factibilidad, pues en las restricciones sólo aparece la diferencia Vi − Ci .

1.2.

Forma del planteamiento del PPL

Una vez que se tiene planteado el modelo lineal del problema o Problema de Programación Lineal, P.P.L., es posible que las desigualdades de las restricciones no estén todas en el mismo sentido o incluso haya igualdades. Existen dos formas particulares que puede tener el P.P.L., forma can´ onica y forma est´ andar, a continuación se describe cada una de estas formas. En el caso de maximizar, el problema está en forma can´ onica si todas las restricciones tienen el sentido de la desigualdad como menor que o igual y todas las variables deben ser no negativas: Max P s.a.

z = cx Ax ≤ b x ≥ 0.

Para el caso de minimizar, el problema est´a en forma can´ onica si todas las restricciones tienen el sentido de la desigualdad como mayor que o igual y todas las variables deben ser no negativas: Min P s.a.

z = cx Ax ≥ b x ≥ 0.

Ciencias exactas e ingenierías/Licenciatura en Matemáticas

Investigación de Operaciones Unidad 1. Programación lineal, planteamiento de problemas Contenido nuclear ´ LINEAL, PLANTEAMIENTO DE PROBLEMAS CAPÍTULO 1: PROGRAMACION El problema de maximizar o minimizar está en forma est´ andar si todas las restricciones están definidas con igualdad y todas las variables deben ser mayor que o igual a cero: Max z = cx Min z = cx P s.a. Ax = b P s.a. Ax = b x ≥ 0. x ≥ 0. Para los tres casos c denota un vector renglón de n componentes, x un vector columna de tama˜ no n, A una matriz de tama˜ no m × n y b un vector columna de m componentes. Es posible cambiar la forma en que está escrito un problema, por ejemplo, de forma canónica a forma estándar o viceversa. Esto se hace agregando variables de holgura 2 o escribiendo las igualdades como dobles desigualdades. Si el planteamiento del modelo tiene variables negativas, estas se pueden expresar como la diferencia de dos variables no negativas.

Las variables de holgura se agregan a la desigualdad para tener la ecuaci´ on, ya sea sumando o restando la variable de holgura seg´ un sea el caso, de modo que la variable de holgura tenga valores n n P P no negativos. Si la restricci´on es del tipo aij xj ≥ bi la holgura se agrega as´ı: aij xj − hi = bi , j=1

j=1

con hi ≥ 0 y se logra la igualdad.

Ciencias exactas e ingenierías/Licenciatura en Matemáticas

Investigación de Operaciones Unidad 1. Programación lineal, planteamiento de problemas Contenido nuclear

Bibliograf´ıa Bazaraa, M.S. (1999). Programaci´ on Lineal y Flujo en Redes. Segunda Edición. México: Limusa. Kaufmann, A. (1976). Métodos y modelos de la Investigaci´ on de Operaciones. Espa˜ na: Compa˜ nia Editorial Continental. Taha, H. (1992). Operations Research: An Introduction. Fifth Edition. U.S.A.: Macmillan Publishing Company.

Ciencias exactas e ingenierías/Licenciatura en Matemáticas