CAP. 5

PROGRAMACIN LINEAL

Programacin Lineal Programacin Lineal tiene las siguientes aplicaciones tpicas:Un fabricante desea elaborar un programa de produccin y una poltica de inventarios que satisfaga la demanda del futuro, minimizarn la produccin y costos de inventario.Un analista financiero debe seleccionar un portafolios de inversin entre acciones y bonos, debe maximizar el retorno de la inversin.

Programacin LinealUn gerente de mercadotecnia desea determinar como asignar el presupuesto de publicidad entre varios medios alternativos , buscar la mezcla de medios para maximizar la efectividad de la publicidad.Una empresa tiene almacenes en diferentes ubicaciones , con una demanda especfica determinar cuanto embarcar de cada almacn para cada cliente, minimizar los costos de transporte.

Naturaleza y estructura de los modelos matemticosVariables y parmetros de decisinRestriccionesFuncin Objetivo

Programacin Lineal : Formulacin deProblemasUna empresa dispone de 70 trabajadores con cualificaciones diferentes (Economistas, Ingenieros, Auxiliares Administrativos, etc..) a los que hemos de asignar 70 actividades tambin diferentes. Para decidir una determinada asignacin de tareas deberamos escoger de entre un total de 70! (Permutaciones de 70 elementos) aquella que maximiza el resultado final de la empresa. Como 70! es aproximadamente igual a 10100, an revisando un 1 milln de asignaciones diferentes al segundo necesitaramos aproximadamente 1087 aos para revisar todas las asignaciones posibles.Este tipo de problemas requiere desarrollar modelos de programacin matemtica, otros mtodos matemticos, para llegar a algn tipo de conclusiones.

Caractersticas de la P. L.1. Un nico objetivo lineal a optimizar (maximizar o minimizar)2. Unas variables de decisin que siempre son continuas y no negativas3. Una o ms restricciones lineales4. Un conocimiento exacto de los parmetros y recursos utilizados en la construccin del modelo.

Formulacin de ModelosPrimero veremos como con la programacin lineal se puede expresar matemticamente.Ejemplo: Dos empresas Mineras extraen dos tipos diferentes de minerales, los cuales son sometidos a un proceso de trituracin, con tres grados: alto , medio y bajo. Las compaas han firmado un contrato para proveer de mineral a una planta de fundicin, cada semana, 12 toneladas de mineral de grado alto, 8 toneladas de grado medio y 24 toneladas de grado bajo. Cada una de las empresas tiene diferentes procesos de fabricacin.Mina Coste por da (miles de $US.) Producci(toneladas/da)Alto MedioBajoX180634Y160116Cuntos das a la semana debera operar cada empresa para cumplir el contrato con la planta de fundicin?

Formulacin matemtica bsica en un problema de I.O.Debemos buscar una solucin que minimice el coste de produccin de las empresas, sujeta a las restricciones impuestas por el proceso productivo as como el contrato con la planta de fundicin.

Traduccin del problema en trminos matemticosdefinir las variableslas restriccionesel objetivo

Formulacin matemtica bsica en un problema de I.O.VariablesRepresentan las decisiones que puede tomar la empresa: Dx = nmero de das a la semana que la empresa X produceDy= nmero de das a la semana que la empresa Y produceNotar que Dx0 y Dy0 RestriccionesSe recomienda primero plantear las restricciones con palabras antes de pasar a su formulacin matemticaRestriccin 1. Refleja el balance entre las limitaciones productivas de la fbrica y el contrato con la planta de fundicin GradoAlto6Dx+1Dy12Medio3Dx+1Dy8Bajo 4Dx+6Dy24Restriccin 2. Das de trabajo disponibles a la semanaDx5 y Dy5ObjetivoComo objetivo buscamos minimizar el coste

Formulacin matemtica bsica en un problema de I.O.La representacin completa del problema tomara la siguiente forma:Minimizar 180Dx+160DyRestriciones: 6Dx+1Dy123Dx+1Dy84Dx+6Dy24Dx5, Dy5Dx0, Dy0

Algunas reflexiones Hemos pasado de la definicin del problema a su formulacin matemtica.Error de especificacin, el error ms frecuente consiste en descuidar las limitaciones (restricciones, caractersticas de las variables, etc,)En el ejemplo anterior:Todas las variables son continuas (admitimos fracciones de da)Existe un nico objetivo (minimizar los costes)El objetivo y las restricciones son linealesLas tres consideraciones anteriores nos llevan a lo que denominamos un problema de Programacin Lineal PL

Algunas reflexiones El ejercicio anterior plantea un PROBLEMA DE DECISINHemos tomado una situacin real y hemos construido su equivalente matemtico MODELO MATEMTICODurante la formulacin del modelo matemtico nosotros consideramos el mtodo cuantitativo que (esperanzadamente) nos permitir resolver el modelo numricamente ALGORITMO El algoritmo es un conjunto de instrucciones que siguiendo de manera gradual producen una solucin numricaLlegamos a una nueva definicin de I.O.Ciencia para la representacin de problemas reales mediante modelos matemticos que junto con mtodos cuantitativos nos permiten obtener una solucin numrica a los mismos

DificultadesDificultades de este tipo de enfoques:Identificacin del problema (debemos ignorar partes o tratar el problema entero)Eleccin del modelo matemtico adecuado as como el algoritmo adecuado para resolverlo (validacin del algoritmo)Dificultades en la implementacinVelocidad (costes) que supone llegar a una solucinCalidad de la solucinConsistencia de la solucin

EJEMPLO DE ASIGNACION DE PERSONALFarmacias Bolivia en sus 9 sucursales ha decidido ampliar su servicio a 24 horas, con la consiguiente necesidad de nuevo personal de atencin al cliente. La gerencia de la Empresa ha estimado las necesidades mnimas de personal por tramos horarios para poder cubrir los requerimientos de los clientes que se presenten. Se definieron 6 tramos de 4 horas. La necesidad mnima de personal en cada tramo se indica en el Cuadro. Por otro lado, el departamento de recursos humanos ha informado a la gerencia que los contratos laborales han de ser de ocho horas seguidas, segn normativa laboral, independientemente de los horarios de entrada y salida del personal.El problema es encontrar el nmero mnimo de personal necesario para cubrir la demanda.

REQUERIMIENTO DE PERSONAL

J100:00 - 04:00204:00 - 08:00308:00 - 12:00412:00 - 16:00516:00 - 20:00620:00 - 24:00

PERSONAL N j 953756

Formulacin del problemaEn primer lugar, se tienen que definir las variables del modelo que queremos desarrollar. Como se controlar el nmero de personal en cada turno, definimos Xj como la cantidad de personal que entra a trabajar en el turno j, en donde vara j=1,...,6. Es decir, hay una variable para cada turno.

Las restricciones del modelo tienen que reflejar la necesidad de que la cantidad de personal que entren en el periodo j ms el nmero de personas que entraron a trabajar en el turno j-1 sean suficientes para cubrir las necesidades del turno j (Nj). Esta situacin queda reflejada en el Cuadro 2. En esta tabla, un trabajador que entra a trabajar, por ejemplo, a las 4:00, trabajar en los turnos 2 y 3, y por tanto, contribuir a cubrir las necesidades de estos dos turnos. En otras palabras, el turno j estar siendo atendido por Xj-1 y Xj. En consecuencia, tendremos que Xj-1 + Xj (el personal que trabaja durante el turno j) tiene que ser, como mnimo, igual a Nj, que es el nmero mnimo de personal de la farmacia que sera necesario para este turno. En trminos matemticos la restriccin es la siguiente: Xj-1 + Xj Nj

El objetivo de la gerencia consiste en la minimizacin del nmero total de personal de atencin necesario para cubrir las necesidades diarias. Este nmero ser igual a X1 +X2 +X3 +X4 +X5 +X6 que representa la suma del nmero de personal que entra en cada periodo.Finalmente, el modelo matemtico es el siguiente: 6 min Z = Xj j=1Con las restricciones: X6 + X1 9 Xj > 0, j= 1,...,6 X1 + X2 5 X2 + X3 3 X3 + X4 7 X4 + X5 5 X5 + X6 6

100:00 - 04:00204:00 - 08:00308:00 - 12:00412:00 - 16:00516:00 - 20:00620:00 - 24:000:00X1X104:00X2X208:00X3X312:00X4X416:00X5X520:00X6X6PersonalNj953756

EJEMPLO DE Programacin FinancieraEl Banco BISA SA est preparando su plan de inversiones para los prximos dos aos. Actualmente, la empresa tiene 1,5 millones de dlares para invertir y espera ingresar, gracias a inversiones pasadas, un flujo de dinero al final de los meses, 6 12 y 18 prximos. Por otra parte, la empresa quiere expandirse y tiene dos propuestas sobre la mesa.La primera es asociarse con la empresa Minera San Cristobal y la segunda con la empresa Gravetal SA

En el Cuadro se muestra el flujo de caja (MILES DE DOLARES)del Banco BISA SA si entrara con un 100% en cada uno de los proyectos.

INICIAL6 MESES12 MESES18 MESES24 MESESINVERSIONES PASADAS500400380MINERA SAN CRISTOBAL- 1000- 7001800400600GRAVETAL S.A.- 800500-200- 7002000

Debido a regulaciones, al Banco BISA SA no se le permite pedir prstamos directos.Pero si que puede, cada seis meses, invertir sus fondos excedentes (es decir, aquellos que no ha invertido en ningn proyecto) en un fondo que le dara un 7% cada seis meses. Por otro lado, BISA SA puede participar en cada uno de los proyectos con un nivel inferior al 100% y, consecuentemente, el flujo de caja se reducir en la misma proporcin. Es decir, que si decide entrar por ejemplo con el 50% en el proyecto de Gravetal, el flujo correspondiente tambin se reducir en la misma proporcin. El problema que se plantea BISA SA es cuanto invertir en cada proyecto para maximizar el dinero en efectivo que tendr la empresa en dos aos

Formulacin del problemaUna vez el problema ha sido identificado y los parmetros del modelo han sido definidos, se tienen que definir las variables. Sea X1 el porcentaje de participacin en el proyecto Minera San Cristobal y X2 el porcentaje de participacin en el proyecto Gravetal SA (0 X1 1, 0 X2 1). Por otro lado, sean S0, S6, S12 y S18 el dinero que se depositar en el fondo en los periodos 0, 6 12 y 18 respectivamente.

Para formular las restricciones del modelo se utilizar un razonamiento secuencial. La empresa dispone de 1,5 millones de dlares hoy (periodo 0) y las quiere gastar considerando las opciones siguientes:1. participar en el proyecto Minera San Cristobal, que implicara desembolsar 1.000.000X1 dlares en el periodo 0;2. participar en el proyecto Gravetal SA, teniendo que gastar 800.000X2;3. depositar el dinero al 7%Estas opciones no son excluyentes entre ellas. Por lo tanto, se tiene que cumplir la siguiente ecuacin de equilibrio: 1.500 = 1.000X1 + 800X2 + S0

Al cabo de seis meses, la empresa ingresar 500.000 dlares, gracias a inversiones realizadas anteriormente. Tambin el dinero depositado en el fondo en el periodo anterior estar a disposicin junto con los intereses: S0 + 0,07S0 .Por otra parte, el proyecto Gravetal SA dar una entrada de dinero igual a 500.000X2. Con este dinero tendr que hacer frente al compromiso adquirido con Minera San Cristobal, 700.000X1, y depositar lo que quede al 7% una vez ms.Matemticamente: 500 + 500X2 + 1,07S0 = 700X1 + S6

En el periodo 12, la empresa recibir 400.000 dlares, de inversiones anteriores, y 1.800000X1 del proyecto Minera San Cristobal y el dinero del fondo junto con los intereses. Con estos ingresos tendr que cubrir el compromiso del proyecto Gravetal SA, 200X2 y depositar S12 en el fondo. En trminos matemticos: 400 + 1.800X1 + 1,07S6 = 200X2 + S12

En el periodo 18, los ingresos que tendr la empresa vendrn de inversiones anteriores (380.000), del proyecto Minera San Cristobal (400.000X1) y del depsito realizado en el periodo anterior incluyendo los intereses (1,07 S12 ). Con este dinero tendr que realizar un gasto de 700.000 X2 en el proyecto Gravetal y el resto puede volver a ponerlo en el fondo (S18). Es decir: 380 + 400X1 + 1,07S12 = 700X2 + S18

Finalmente, al cabo de dos aos (periodo 24), el BISA tendr nicamente ingresos y no tendr ningn gasto. Los ingresos provienen de los dos proyectos (600.000 X1 + 2.000.000 X2) y del dinero depositado en el periodo anterior, 1,07 S18. Si se define Z como los ingresos realizados en el periodo 24 en miles de dlares, tendremos que: Z = 600X1 + 2.000X2 + 1,07S18Este es el objetivo del problema: Maximizar los ingresos al cabo de dos aos.

Finalmente, como solo se puede invertir un mximo de 100% en cada proyecto, las variables X1 y X2 no pueden exceder la unidad. Por lo tanto, hay que aadir las restricciones siguientes: X1 1 X2 1El programa lineal se escribe de la forma siguiente: Max Z = 600X1 + 2.000X2 + 1,07S18Con restricciones:1000X1 + 800X2 + S0 = 1.500700X1 -500X2 -1,07S0 + S6 = 500-1.800X1 + 200X2 -1,07S6 + S12 = 400-400X1 + 700X2 -1,07S12 + S18 = 380X1 1 ; X2 1 ; X1, X2, S0, S6, S12, S18 0

Mtodos de ResolucinUn modelo matemtico de decisin, por muy bien formulado que est, no sirve de nada sino podemos encontrar una solucin satisfactoria.Una de las caractersticas de la programacin lineal es que, gracias a sus propiedades matemticas, se consigue la solucin ptima sin muchas dificultades. En primer lugar se ver el mtodo grfico, un sistema limitado a problemas con dos variables, y a continuacin el mtodo Simplex, el algoritmo ms comn para solucionar problemas lineales con muchas variables y restricciones.

Un modelo matemtico de decisin, por muy bien formulado que est, no sirve de nada sino podemos encontrar una solucin satisfactoria.Una de las caractersticas de la programacin lineal es que, gracias a sus propiedades matemticas, se consigue la solucin ptima sin muchas dificultades. En primer lugar se ver el mtodo grfico, un sistema limitado a problemas con dos variables, y a continuacin el mtodo Simplex, el algoritmo ms comn para solucionar problemas lineales con muchas variables y restricciones.

Anatina Toys fabrica 2 tipos de juguetes de madera, autitos y rompecabezas. Un autito se vende en Bs. 54 y requiere 20 Bs. de materia prima. Cada autito que se fabrica incrementa la mano de obra variable y los costos globales en 28 Bs. Un rompecabezas se vende en Bs. 42 y requiere 18 Bs. de materia prima. Cada rompecabezas incrementa la mano de obra variable y costos globales en 20 Bs. Para la fabricacin se requiere mano de obra especializada: carpintera y acabados. Un autito requiere 2 h de acabado y1 h de carpinteria. Un rompecabezas requiere 1h acabado y 1h de carpinteria.

Todas las semanas Anatina Toys consigue todo el material , pero solo 100h de trabajo de acabado y 80h de trabajo de carpinteria.La demanda de rompecabezas es ilimitada y solo se vende 40 autitos por semana.Anatina Toys debe maximizar las utilidades semanales (ingresos costos)Disear un modelo matemtico y resolver por el metodo grafico.

X1 = cantidad de autitos fabricados cada semana X2 = cantidad de rompecabezas fabricados a la semana

La funcin objetivo ser: Los ingresos semanales menos los costos de materia prima y menos los costos varables.Ingresos por semana = 54 X1 + 42 X2Costos materia prima semana = 20 X1 + 18 X2Costos variables semana = 28 X1 + 20 X2

Entonces Anatina Toys quiere maximizar: (54 X1 + 42 X2)-(20 X1 + 18 X2)-(28 X1 + 20 X2) = Max Z = 6 X1 + 4 X2Los coeficientes para X1 es 6 y para X2 es 4 que es la utilidad.

RESTRICCIONESRestriccin 1: 100h de trabajo de acabado 2 X1 + X2 100Restriccin 2: 80h de trabajo de carpintera X1 + X2 80Restriccin 3: Debido a la demanda limitada de autitos no debe producirse mas de 40 autitos. X1 40Restriccin 4 De signo: La produccin no puede ser negativa. Entonces: X1 0 ; X2 0

REGION FACTIBLEEs el conjunto de todas las soluciones que satisfacen las restricciones. Por ej. Para X1 = 40 y X2 = 20 CumplePara X1 = 15 y X2 =70 No CumplePara X1 = 10 y X2 = 70 CumplePara X1 = 20 y X2 = 60 CumpleSOLUCION OPTIMA:En Maximizacin es el punto donde el valor es el mas alto en la funcin objetivoEn minimizacin es lo contrario.En nuestro caso el mximo es en Max Z = 6 X1 + 4 X2Para X1 = 20 y para X2 = 60 Max Z = 360