Modelacin en OptimizacinJuan Carlos Ferrer O., Pedro Gazmuri Sch., Juan Carlos Muoz A.Ponticia Universidad Catlica de ChileEscuela de IngenieraMarzo 2006Contents1 Introduccin 52 Modelos de Programacin Lineal 62.1 Produccin ptima de una Fbrica de Telas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2 Produccin de Evento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.3 Concurso de Belleza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4 Presupuesto Comunal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.5 Habilitacin de un Avin Comercial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.6 Fabricacin de un Cohete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.7 Instalacin de Central de Telecomunicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.8 Agua Puricada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.9 Confeccin de Ropa Femenina . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.10 Diseo Automotriz. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.11 El Curanto ms Grande . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.12 FAMAE: Produccin de Tiros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.13 Crisis del Gas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.14 Fbrica de Ladrillos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.15 Decisin de Produccin Agrcola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.16 Proceso Productivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.17 Itinerario Empresa Pesquera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.18 Sistema de Atencin Telefnico. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.19 Fbrica de Papel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362.20 Empresa Qumica de Aditivos Lquidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.21 School Board . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382.22 Central Hidroelctrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392.23 Planicacin de Produccin y Ventas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402.24 Endesa y Operacin de Central Hidroelctrica . . . . . . . . . . . . . . . . . . . . . . . . . . . 412.25 Administracin de Fundo Familiar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422.26 Venta de Acciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432.27 Procesamiento de Carbn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442.28 Iluminacin de Plazas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452.29 Carga en Avin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452.30 Mantencin de Equipos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462.31 Planicacin de Produccin. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46Profesor Auxiliar del Departamento de Ingeniera Industrial y de Sistemas. e-mail: jferrer@ing.puc.clProfesor Titular Asociado del Departamento de Ingeniera Industrial y de Sistemas. e-mail: pgazmuri@ing.puc.clProfesor Auxiliar del Departamento de Ingeniera de Transporte. e-mail: jcm@ing.puc.cl13 Modelos de Programacin No-lineal 483.1 Polticas de Produccin y de Precios en una Panadera . . . . . . . . . . . . . . . . . . . . . . 483.2 Distribucin de Especies en un Predio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493.3 Semaforizacin de una Rotonda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503.4 Diseo de un Edicio Sujeto a las Normativas Vigentes . . . . . . . . . . . . . . . . . . . . . . 503.5 Elaboracin de un Helado de Gusto Masivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.6 Ubicacin de una Zona de Camping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533.7 Diseo ptimo de Caja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553.8 Campo Elctrico al Interior de una Esfera. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563.9 Estrategia de Escape de la Prisin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573.10 Negociacin Colectiva en Empresa de Armado de Lnea Blanca . . . . . . . . . . . . . . . . . 613.11 Planicacin de Produccin Agrcola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633.12 Explanada en el Monte de Masada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663.13 Planta de Revisin Tcnica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693.14 Crculo de Mayor rea Inscrito en Polgono. . . . . . . . . . . . . . . . . . . . . . . . . . . . 703.15 Instalacin de Pozo en Granja Agrcola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733.16 Publicidad en Televisin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 763.17 Prevencin de Accidentes Viales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764 Modelos de Programacin Entera 794.1 Publicidad en Televisin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 794.2 Fiesta de Matrimonio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 794.3 Tareas Semanales en Matrimonio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 804.4 Decisin de Inversin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 814.5 Planicacin de Estudio para Exmenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 824.6 Lanzamiento de Proyectiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 834.7 Consurso Revista "Don Baln" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 854.8 Aumento de Capacidad de Plantas de CMPC. . . . . . . . . . . . . . . . . . . . . . . . . . . 874.9 Empresa Constructora . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 884.10 Instalacin de Estaciones de Bomberos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 894.11 Localizacin de Fbricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 904.12 Instalacin de Tiendas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 914.13 Ubicacin de Grifos de Incendio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 924.14 Planicacin de Vuelos Areos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 924.15 Asignacin de Becas Universitarias. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 934.16 Despacho de Pedidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 934.17 Problema del Cartero Chino . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 944.18 Sistema de Distribucin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 954.19 Planicacin de Produccin. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 954.20 Planicacin de Produccin y Almacenamiento . . . . . . . . . . . . . . . . . . . . . . . . . . 964.21 Empresa de Alimentos de Gatos y Perros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 974.22 Planicacin de Abastecimiento en Botillera . . . . . . . . . . . . . . . . . . . . . . . . . . . 1004.23 Programacin de Trabajos en Mquinas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1014.24 Calendario de Trabajos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1024.25 Turnos de Enfermeras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1034.26 Planicacin de Tareas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1044.27 Cadena de Abastecimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1044.28 Programacin de Partidos de Ftbol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1055 Modelos de Flujo en Redes 1075.1 Ruta a Costo Mnimo en Red de Nodos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1085.2 Arriendo de Casa de Verano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1115.3 Transporte de Carga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1145.4 Empresa de Trompos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11625.5 Empresa de Banquetes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1185.6 Fiesta de Solteros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1215.7 Asignacin de Salas de Clases en Escuela de Ingeniera . . . . . . . . . . . . . . . . . . . . . . 1225.8 Flota Mnima en Sistema de Transporte Pblico . . . . . . . . . . . . . . . . . . . . . . . . . 1255.9 Asignar Colores a Sistema de Transporte Pblico . . . . . . . . . . . . . . . . . . . . . . . . . 1265.10 Sistema de Transporte Pblico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1275.11 Re-Ruteo de Pasajeros en Lnea Area . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1285.12 El cartero y el semaforero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1305.13 Sistema de Seguridad Policial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1325.14 Almacenamiento de Productos en Contenedores (Bin Packing Problem) . . . . . . . . . . . . 1335.15 Equipo de Trabajo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1345.16 Preparacin de Paseo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1345.17 Explotacin Forestal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1355.18 Explotacin en Zona Minera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1365.19 Tablero de Ajedrez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1365.20 Sistema Monetario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1375.21 Empresa de Telecomunicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1375.22 Encuentro Internacional de Jvenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1395.23 Distribucin de Productos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140341 IntroduccinMuy frecuentemente, los individuos y organizaciones deben tomar decisiones de distinto orden de comple-jidad. Estas decisiones consisten tpicamente en escoger una opcin de entre varias disponibles. Muchasveces esta decisin no es trivial y se hace necesario contar con herramientas de apoyo que permitan vislum-brar todas las alternativas disponibles y claricar un mecanismo de seleccin entre dichas alternativas. Estetexto pretende colaborar con este proceso de decisin, por medio de ensear el desarrollo de una valiosaherramienta de apoyo: los modelos matemticos de optimizacin.Cuando alguien est interesado en analizar un determinado problema real que observa, es natural queintente denirlo formalmente, simplicarlo de modo de conservar slo aquello que es medular en el fenmenoque le interesa y, ojal convertir sus partes integrantes y las relaciones que las vinculan en una nuevaestructura que le permita operar en el problema con libertad. Esta estructura puede tener forma fsica oabstracta. Por ejemplo en el plano fsico los arquitectos construyen maquetas, los ingenieros aeronuticosconstruyen aeromodelos o la compaa de telfonos disea un plano de calles de la ciudad. Si se observa, cadauno de estas reducciones del problema original conserva slo lo esencial de la situacin que se representa,simplicando aquello que no entrega informacin til. Es a este procedimiento que le denominamos modelar.Si se quiere una denicin de lo que signica modelar, diremos que un modelo es una estructura que se haconstruido que exhibe caractersticas de un sistema.Es una simplicacin orientada a nuestros propsitosde una realidad concreta.En ciencias, muchos de los problemas que se abordan, interesa modelarlos en forma abstracta usando unlenguaje matemtico. As, se representan los fenmenos haciendo uso de la variedad de representaciones queesta ciencia ha desarrollado. Los modelos de optimizacin representan una de las familias de estos modelosmatemticos.Esta familia comparte una estructura comn la cual consiste en determinar el (o los) puntoque maximiza (o minimiza) una funcin objetivo sujeto a que satisfaga un cierto conjunto de restricciones.Dada la importancia que tiene la creacin de modelos (fsicos o abstractos) para el buen desempeo devarias profesiones, es normal que las escuelas que preparan a estos profesionales destinen muchos esfuerzosen procurar que sus alumnos modelen adecuadamente. Esto es, que sean capaces de convertir realidades queobservan o imaginan en modelos que permitan a un tercero interactuar con ellas.Por otra parte, en las escuelas de ciencias se realizan escasos esfuerzos para ensear a los alumnos atraducir una realidad concreta, escrita en palabras, en un lenguaje matemtico que les permita a ellosmismos desprender conclusiones y soluciones.Normalmente se da por entendido que modelar es sencillo yque el mejor modo de aprender es mediante ejercitar esta habilidad. Si bien compartimos la segunda parte,creemos que esta ejercitacin debiera tener una estructura y una variedad adecuadas. Lamentablemente noexiste (o al menos no conocemos) un texto que presente una abundante, variada y estructurada coleccin deproblemas modelados de optimizacin. Este texto pretende llenar este vaco.El texto se nutre de problemas desarrollados por los autores y por otros profesores de la escuela deIngeniera de la Ponticia Universidad Catlica de Chile. Estos problemas han sido pensados en el espritude ensear a modelar mediante ejercicios que signiquen un esfuerzo en trminos de ingenio y abstraccin.Los ejercicios han sido resueltos por los autores de modo que esta traduccin desde el lenguaje oral al lenguajematemtico trasluzca una metodologa.52 Modelos de Programacin LinealEn esta seccin queremos presentar las principales herramientas de modelamiento continuo, es decir, aquellaspara modelar problemas cuyas variables de decisin pertenezcan a un espacio continuo. Se presentan diversastcnicas para abordar ciertas dicultades de modelacin y/o de posterior resolucin, como por ejemplo, cmorepresentar en forma lineal un problema de naturaleza no lineal.Comenzamos con problemas lineales ya que en la prctica stos juegan un rol fundamental dentro deinvestigacin de operaciones. Esto se debe a que las personas piensan y razonan en forma lineal lo cualfacilita la aceptacin de este tipo de modelos para apoyar la toma de decisiones. Esto tambin se reejaen los principales libros de investigacin operativa, por la extensin y el detalle con que tratan el tema deproblemas lineales.Como veremos a lo largo de este libro en cada esfuerzo de modelacin, una aplicacin efectiva de pro-gramacin lineal requiere: (i) entender muy bien los supuestos que hay detrs, y (ii) saber interpretar lassoluciones obtenidas.La formulacin general de un problema de programacin lineal es de la siguiente forma. La funcinobjetivo:Max/Min f(x1, x2, ..., xn) = c1x1 +c2x2 +... +cnxnest sujeta a las siguientes restricciones tcnicasai1x1 +ai2x2 +... +ainxn__ =__bii = 1, ..., my a las siguientes restricciones de signo(xj 0) (xj 0) (xjlibre) j = 1, ..., ndonde libre signica que la variable no tiene restriccin de signo.Como podemos ver, tanto la funcin objetivo como el lado izquierdo de las restricciones tcnicas cor-responden a funciones lineales.De esta forma el supuesto que implica la linealidad es lo que determina laaplicabilidad en problemas del mundo real.Para tener una mejor idea del concepto de linealidad, asumamos que las variables x1, ..., xn correspondenvarias actividades, y los valores que se les asignen (soluciones) corresponden al nivel de cada actividad.Teniendo esta interpretacin en mente, la propiedad de linealidad implica los siguientes dos supuestos: Aditividad: El consumo total de cada recurso (restriccin) as como el valor total del objetivo son elresultado de la agregacin de los consumos de recursos y contribuciones luego de llevar a cabo cadaactividad en forma independiente. Proporcionalidad: Los consumos de recursos y contribuciones para cada actividad son proporcionalesal nivel de actividad actual.A continuacin se presentan una serie de problemas de Programacin Lineal.2.1 Produccin ptima de una Fbrica de TelasUna fbrica textil, se dedica a la produccin de 5 tipos de telas (i): Seda, Viscosa, Gabardina, Lycray Franela. Cada una genera distintas utilidades (ui) y tiene una demanda diaria promedio (di), datosconocidos a travs de un estudio de mercado. Por otra parte, cada tipo de tela (i) est compuesta porcuatro tipos de materia prima (j): algodn (ai), polyester (pi), lycra (li) y seda (si) en distinta proporcin.La fbrica dispone diariamente de un stock limitado de estos productos (mj). El objetivo del problema escalcular la cantidad (xi) a producir de cada tipo de tela para que la utilidad diaria de la fbrica sea mxima.Asumiendo para esto, que tanto la mano de obra como la maquinaria podrn adaptarse sin inconvenientesa los valores obtenidos.6SOLUCIN1Ya que el objetivo del problema es determinar la cantidad a producir de cada tipo de tela, emplearemosla variable de decisin:xi = Cantidad a producir de la tela ii = {1 = seda, 2 = viscosa, 3 = gabardina, 4 = lycra, 5 = franela}Se debe maximizar la utilidad de la fbrica sujeta a las restricciones de satisfacer la demanda y nosobrepasar el stock mximo de materia prima. Adems, por tratarse de cantidad de tela, las variables dedecisin deben ser no negativas.Considerando que:ui = Utilidad generada por la tela i.di = Demanda diaria promedio de la tela i.ai, pi, li, si = Materia prima empleada en cada tela i.mj = Stock de materia prima, j = {1 =algodn, 2 =polyester, 3 =lycra, 4 =seda}son datos del modelo, el problema de optimizacin se puede expresar como:P) Max5

i=1xiuisujeto a:xi dii

5i=1aixi m1i

5i=1pixi m2i

5i=1lixi m3i

5i=1sixi m4ixi 0 iProblemas Propuestos:1. Replantee el modelo para una fbrica que produce ntipos de tela, a partir de m materias primas.2. En poca de crisis, la fbrica se da cuenta que ya no puede seguir fabricando los 5 tipos de tela, yaque la gente est invirtiendo cada vez menos en este rubro, y decide reducir su variedad a slo 3 tipos.Cmo se puede adaptar este modelo para que la fbrica sepa cules son los 3 tipos que le convieneseguir fabricando? Para esto, considere que las materias primas tienen un costo de cj.2.2 Produccin de EventoUna persona que acaba de ganar un premio decide celebrarlo y hacer una esta con sus amigos. Para estoha decidido invertir $1.300.000, los cuales se dividen en $1.000.000 para el arriendo del local y $300.000 parainsumos.El objetivo del evento es que todos lo pasen lo mejor posible, y para medir esto se utilizar unafuncin que llamaremos funcin felicidad, la cual depende de 7 variables (xi):donde x1 corresponde alnmero de personas, x2 a la duracin (en horas), x3 a los litros de cerveza (con un costo unitario de c3),x4 corresponde a los litros de otros tragos (con un costo unitario de c4), x5 a los litros de bebida (con uncosto unitario de c5),x6 a los paquetes de picadillo (con un costo unitario de c6) y x7 corresponde a laambientacin. El valor de esta funcin se mide en unidades de felicidad (f). Luego de una encuesta entre1Gonzalo Bustos X. Csar Momares A. Optimizacin 1erSemestre, 2003.7los amigos se concluy que por cada 50 personas que asistan a la esta, se alegran 15 (15f) y que por cadahora de duracin se alegran 100 personas (100f). Por el lado de los bebestibles, se obtuvo que por cada litrode cerveza se alegran 2 personas (2f), por cada litro de otros tragos se alegran 4 personas (4f) y por cadalitro de bebida se alegra slo 1 (1f).Finalmente por cada paquete de picadillo se alegra 1 persona (1f) ypor cada $10.000 que se gasten en ambientacin se alegran 15 (15f). Adems, se sabe que para que la estaresulte no se podr gastar menos de $80.000 en ambientacin. Para la organizacin del evento habr queconsiderar varios aspectos: primero que nada, la cantidad de cada tipo de bebestible y picadillo, deber sermayor o igual a 1; el arriendo del local parte de un precio base de $100.000 y aumenta en $150.000 porcada hora de arriendo, con una disponibilidad mxima de 8 horas; por otra parte, el local cuenta con unsistema de refrigeracin con una capacidad mxima de 800 litros. Tambin, por seguridad se pide que elgrado alcohlico no supere en promedio los 20 por persona, considerando que cada litro de cerveza tiene 5y cada litro de otro trago tiene 35. Por ltimo, existe una capacidad del local, donde el nmero mximo depersonas es de 800.SOLUCIN2El objetivo del problema es determinar qu cantidad de cada recurso utlizar, de tal manera que la variablede decisin viene dada por:xi = Cantidad a emplear de cada uno de los recursos, i = 1, ..., 7Se debe maximizar la funcin felicidad considerando como restricciones la capacidad de refrigeracinde 800 lts para los bebestibles (cervezas, tragos y bebidas), la suma mxima de $1.000.000 destinada parael arriendo del local que considera un costo jo y un costo variable dependiente de las horas de duracinde la esta, la cantidad mxima de $300.000 destinada a bebestibles, picadillos y ambientacin, el mayorgrado alcohlico por persona (20o) permitido por seguridad, el gasto mnimo de $80.000 en ambientacin,la duracin mxima de 8 horas de la esta y la cantidad mxima de personas. Se debe considerar adems,que cada una de las variables debe ser no negativa, y en particular la cantidad de cervezas, bebidas, tragosy picadillo debe ser mayor o igual a 1.Por lo tanto, el problema de optimizacin es:P) Max 0.3x1 + 100x2 + 2x3 + 4x4 +x5 +x6 + 0.015x7x3 +x4 +x5 800100.000 + 15.000x2 1.000.000c3x3 +c4x4 +c5x5 +c6x6 +x7 300.0005x3 + 35x4 20x180.000 x7x2 8x1 800xi 0 i = 1, 2, 7xi 1 i = 3, 4, 5, 6Problemas Propuestos:1. Analice como cambia el problema si en lugar de existir 3 tipos de bebestibles hay slo 1. Se man-tendr la cantidad total de bebestibles? Realice el anlisis para cada uno de los tipos de bebestible,considerando primero, que cada uno alegra a distinto nmero de personas (tal como lo indica el enun-ciado); y luego, que cada uno alegra a un nmero igual al promedio de la felicidad que cada unoproduce por separado.2Diego Gallardo A. Jos Luis Noguer. Optimizacin 1996.8Caracterstica Costo (millones)Belleza (cirujas, gimnasio, etc.) $ 25Inteligencia (cursos de capacitacin) $ 7Personalidad (cursos de desarrollo) $ 7Simpata (cursos de desarrollo y manejo) $ 7Traje tpico (diseo y confeccin) $ 8Traje de noche (diseo y confeccin) $ 12Table 1: Concurso de Belleza2. Suponga que al local pueden ingresar todas las personas que lo deseen, i.e., la restriccin de capacidadmxima del local ya no existe. Cambia el resultado del problema?2.3 Concurso de BellezaCon el n de reposicionar la belleza de la mujer chilena en el mundo, una organizacin que dispone de uncapital de $40.000.000 decide buscar a la mujer ideal para que gane el concurso internacional. Para estodeciden contratar una agencia, con personas muy capacitadas, para que realize un estudio que indique culesson las caractersticas que esta mujer debe tener para que la posibilidad de ganar sea mxima. Las bases delconcurso indican que el puntaje que asigna el jurado se distribuye en las diferentes caractersticas (xi) de lasiguiente manera: de 0 a 20 puntos por belleza (x1) (por ejemplo, si x1 = 1 hay 20 puntos, si x1 = 0.5 hay10 puntos y si x1 = 0 hay 0 puntos); de 0 a 20 puntos por intelecto (x2), de 0 a 5 por personalidad (x3),de 0 a 15 puntos por simpata (x4), de 0 a 10 puntos por presentacin en traje tpico (x5), y lo mismo parala presentacin en traje de noche (x6); y nalmente de 0 a 10 puntos extra (x7), a criterio del jurado parafavorecer a la candidata si es que ella lo amerita. La agencia, con bastante experiencia en mujeres y en estetipo de eventos, tiene sus propias estadsticas a priori, las cules indican que el porcentaje de belleza msinteligencia, es menor o igual al 100% (x1 +x2 1), que la relacin entre simpata e inteligencia, se da dedos formas: x4+3x2 3 y x4+ x23 1; que la relacin entre el carcter y los posibles puntos extras ganadospuede ser: 3x3 +x7 3 x3 + 2x7 2; y que la relacin entre belleza y puntos extras es x1 +2x7 2. Porotra parte, la agencia cuenta con personas especializadas para reforzar las reas ms dbiles (yi) de cadacandidata, asegurando xito total y cobrando segn sea el caso. La lista de precios se presenta en la Tabla1.Cmo tendr que ser la candidata para obtener un puntaje mximo en la competencia internacional?SOLUCIN3Se desea maximizar el resultado obtenido por la candidata en el concurso de belleza, para ello se debedeterminar el porcentaje de cada caracterstica que posee y el porcentaje de cada caracterstica que puedeobtener con ayuda de la agencia, para esto se consideran las siguientes variables de decisin:xi = Porcentaje de la caracterstica i en la candidata, i = 1, ...7.yi = Porcentaje de la caracterstica i a cargo de la agencia, i = 1, ...6.El objetivo del modelo es maximar la cantidad de puntos obtenidos por la candidata, sujeto a las restric-ciones de que la suma de la caracterstica intrnseca de la candidata ms la caracterstica reforzada por laagencia no puede ser mayor a 1,de cumplir las relaciones obtenidas segn estudios de la agencia, y de que elcapital mximo a invertir para reforzar a la candidata no puede superar los $40 millones, adems de la nonegatividad de las variables. Por lo tanto, el problema de optimizacin es:P) Max 20(x1 +y1) + 20(x2 +y2) + 5(x3 +y3) + 15(x4 +y4) + 10(x5 +x6 +x7 +y5 +y6)3Felipe Mera, Juan Guiresse, Optimizacin 1996.91. Personal de carabineros 18 %2. Implementos para carabineros 10 %3. Recintos penales 2 %4. Personal de seguridad en recintos penales 3 %5. Recintos hospitalarios 24 %6. Personal mdico 20 %7. Proyectos de investigacin en salud 8 %8. Aseo y ornato 4 %9. Areas verdes 7 %10. Eventos 4 %Table 2: Presupuesto Comunalxi +yi 1 i = 1, ..., 6x1 +x2 1x1 + 3x4 33x1 +x4 33x3 +x7 3x3 + 2x7 2x1 + 2x7 225y1+7y2+7y3+7y4+8y5+12y6 40xi, yi 0 i = 1, ..., 7Problemas Propuestos:1. Si la agencia a modo de oferta decide rebajar en un 50% todos sus precios, cambian las caractersticasde la mujer que se debe encontrar?2. Analice que ocurre si el descuento se aplica a un slo item de la lista.3. Suponga usted que el presidente del jurado fuera chileno, y que por su sentimiento patriota asegure10 puntos extras (el mximo) a favor para la candidata. Replantee el modelo considerando este nuevodato e indique como varan (si es que lo hacen) las caractersticas que debe tener la candidata.2.4 Presupuesto ComunalUn alcalde con planes de reeleccin desea demostrar preocupacin extrema por su comuna, por lo que realizauna encuesta con el n de conocer las prioridades de los habitantes de ella, para as distribuir de una formams eciente los fondos municipales, que ascienden a $100.000.000. Con esto dejar ms contenta a la gentey asegurar tambin votos para la eleccin. La encuesta constaba de 10 puntos, a cada uno de los cualeshaba que asignarle un porcentaje de preferencia que indicara el benecio que les gustara entregarle a lasdiferentes reas, cuidando que la suma total fuera de un 100%. Los resultados obtenidos se presentan en laTabla 2.Ahora, en conocimiento de los porcentajes (pi) de preferencia, el alcalde necesita conocer el monto (xi)que deber destinar a cada una de las reas para poder cumplir su objetivo de reeleccin. La experienciaseala que existe una directa relacin entre la obtencin de votos y el desempeo del alcalde, de la forma

10i=1xici, es decir, mientras mayor sea esta cifra, mayor ser la cantidad de votos obtenida por el alcalde.Por otra parte, las exigencias mnimas impuestas por el consejo municipal indican que el gasto en el reade seguridad (los primeros cuatro items) no debe ser menor a $37.000.000, mientras que los montos asignadosal desarrollo de la salud (items 5 ,6 y 7), deben ser al menos $52.000.000. Finalmente, en los ltimos 3 items,10la inversin no debe ser superior a los $25.000.000, y en particular, en ningn item se podr invertir menosde $1.000.000.SOLUCIN4El alcalde desea conocer la cantidad de dinero que debe destinar a cada una de las areas para cumplir suobjetivo de reeleccin, luego emplearemos la variable de decisin:xi = Cantidad en dinero destinada al desarrollo del punto i, i = 1, ..., 10.El objetivo del problema es que el alcalde obtenga la mayor cantidad de votos, considerando las restric-ciones de capital total disponible, inversin mnima en seguridad y salud, inversin mxima en las otros reasy que en cada rea se deben invertir al menos $1.000.000.Por lo tanto, el problema de optimizacin es:P) Max10

i=1cixi

10i=1xi 100.000.000

4i=1xi 37.000.000

7i=5xi 52.000.000

10i=8xi 25.000.000xi 1.000.000 iProblemas Propuestos:1. Si por cada $500.000 adicionales que se inviertan en salud el alcalde se asegura 10 votos en la eleccin,y se sabe que con 400 votos sale reelegido. Como afectar esto las decisiones del alcalde?2. Si un nuevo estudio seala que por cada $100.000 invertidos en el rea seguridad el alcalde se asegura2 votos, en el rea de salud 3 votos y en las otras reas 1 voto. Plantee un nuevo modelo considerandoque el objetivo del alcalde es ser reelegido, lo que se consigue con un mnimo de 400 votos.2.5 Habilitacin de un Avin ComercialUna lnea area decide incorporar un nuevo avin para vuelos comerciales a su ota. Para habilitarlonecesita conocer cul es el nmero ptimo de asientos por clase (xi), la cantidad requerida de azafatas (y1)y auxiliares de vuelo (y2), de tal manera que la utilidad sea mxima. Existen 3 tipos de clases:Primera,Ejecutiva y Econmica. Por polticas internas se debe ofrecer un mnimo de asientos por clase de 25, 80 y120 respectivamente. Adems un estudio de mercado indic que la demanda mxima para cada clase es de45, 100 y 210, por lo que tener un nmero superior de asientos por clase no tendr ningn sentido. Por otraparte, el nmero de azafatas y auxiliares tambin est acotado. Por un lado, el avin no puede funcionarcon menos de 8 azafatas y 2 auxiliares de vuelo; y por lmite de espacio no podrn ser ms de 18 azafatas y 5auxiliares de vuelo. Adems, para entregar un buen servicio en cada clase, deber haber al menos 1 azafatapor cada 10 pasajeros de Primera, por cada 20 de Ejecutiva y por cada 40 de Econmica. Tambin deberhaber un auxiliar de vuelo por cada 100 pasajeros del avin. El sueldo de cada azafata es de $200 dlares yel de un auxiliar de $120 dlares.El avin dispone de 420 m2para distribuir los asientos (el espacio parapasillos, cabinas y baos no esta includo), y habr que considerar que un asiento de Primera ocupa 1, 8m2, uno de Ejecutiva 1, 4 m2y uno de Econmica 1 m2. El valor de un pasaje en cada una de las clases es de$2.000, $1.300 y $900 dlares respectivamente, mientras que el costo de la comida para cada una de las claseses de $80, $60 y $50 dlares.El costo de mantencin del avin es de $75.000 dlares.Finalmente, tras un4Yamille Del Valle K.Marcos Orchard C. Optimizacin 1er Semestre 1996.11cuidadoso estudio de servicio e imagen, la lnea area concluy que por cada azafata que tuviera por sobreel mnimo, recibira un benecio total equivalente a $100 dlares, y por cada auxiliar de vuelo adicional elbenecio sera de $50 dlares; esto debido a que entregaran un mejor servicio y los clientes preferiran viajaren su lnea.SOLUCIN5Para plantear el modelo es necesario identicar dos grupos de variables, un grupo que identique lacantidad de asientos a instalar en cada clase y otro grupo que permita decidir la cantidad de personal(azafatas y auxiliares de vuelo) que debe ser asignado a cada avin.xi = Nmero de asientos en la clase i, i = {1 =Primera, 2 =Ejecutiva, 3 =Econmica}yi = Cantidad de personal i, i = {1 =Azafatas, 2 =Auxiliares de vuelo}El objetivo del problema es maximizar la utilidad de la lnea area, esto es la diferencia entre ingresos(pasajes vendidos y benecios por servicio) y costos (costo de comida y costo de mantencin). El modelodebe considerar las restricciones del problema, las que incluyen un nmero mximo y mnimo de asientospor cada clase, adems del espacio disponible para su instalacin; y un nivel mnimo de servicio reejado enla cantidad de azafatas y auxiliares de vuelo por clase.Por lo tanto, el problema de optimizacin se puede expresar como sigue:P) Max [1.920x1 + 1.240x2 + 840x3 + (y18)100 + (y2 2)50] [200y1 + 120y2 + 75.000]1, 8x1 + 1, 4x2 +x3 4200.1x1 + 02x2 + 0.4x3 y1

3i=1xi 100 y225 x1 4580 x2 100120 x3 2108 y1 182 y2 5Es importante destacar que ste corresponde al problema relajado del modelo original, ya que no se estconsiderando que el nmero de azafatas y de auxiliares de vuelo (yi) debe ser un nmero entero.Problemas Propuestos:1. Cmo cambia el problema si el sueldo de los auxiliares de vuelo fuera el mismo que el de las azafatas?Plantee el nuevo modelo.2. Si no existiera la restricciones de mximo y mnimo para el personal del avin, cuntas azafatas yauxiliares convendr llevar abordo?3. Por reformas internas, la lnea rea decide fusionar sus dos primeras clases a una sola, promediandotodas las especicaciones que cada una tiene por separado, para tener las nuevas especicaciones deesta clase. Replantee el modelo y analice su resultado. La cantidad de asientos que debe tener estanueva clase, es un promedio de la cantidad de asientos ptima encontrada en el modelo original delas clases Primera y Ejecutiva?5Andrs Flores M. Michael Ridell H. Optimizacin 1erSemestre 1996.122.6 Fabricacin de un CoheteUna fbrica de cohetes, desea conocer la cantidad y tipo ptimo de combustible (xijk) que debe tener cadacohete con el n de que recorra la mayor cantidad de kilmetros por litro. La fbrica tiene asignado unvalor mximo (M) para gastar en combustible por cada viaje del cohete. Se cuenta con 3 proveedores (i),los cules a su vez ofrecen gasolina con y sin plomo (j), de 3 octanajes diferentes (k): 93, 95 y 97 octnos.Cada litro de combustible tiene asociado un rendimiento (rijk) km/l, distinto para cada proveedor, comotambin un costo (cijk) y un peso (pijk) por litro. Como los cohetes ya estn diseados, ya tienen un peso yvolumen especco, y por lo tanto estos datos no afectarn el problema. Lo que s es importante, y por esose mencion, es el peso del litro de combustible, ya que limitar la cantidad que podr llevar el cohete paraque no incida en la distancia recorrida por ste, este peso no podr ser mayor a P kilos.SOLUCIN6El objetivo del problema es determinar la cantidad y tipo de combustible que se debe adquirir paramaximizar el rendimiento del cohete, para esto consideraremos las siguientes variables de decisin:xijk = Cantidad de combustible que se debe comprar al proveedor i, del tipo j, con k octnos;i = {1, 2, 3}, j = {1 = con plomo, 2 = sin plomo}k = {1 = 93 octnos, 2 = 95 octnos, 3 = 97 octnos}El modelo debe considerar, adems, las restricciones de capital asignado a cada viaje del cohete y el pesomximo de combustible que puede transportar. Obtenindose el siguiente problema de optimizacin:P) Max3

i=12

j=13

k=1xijkrijk3

i=12

j=13

k=1xijkcijk M3

i=12

j=13

k=1xijkpijk Pxijk 0 i, j, kProblemas Propuestos:1. Uno de los proveedores decide igualar sus precios a otro de los proveedores. Cmo se puede modicarel modelo para que se vea representada esta situacin?.2. Nuevamente, uno de los proveedores decide, a modo de oferta, bajar sus precios, igualndolos todos alde la gasolina ms barata. Cmo sera el nuevo modelo?2.7 Instalacin de Central de TelecomunicacionesSe quiere evaluar la instalacin de una central de telecomunicaciones en una zona austral, optimizando lacantidad de servicios que se presten con el n de maximizar las ganancias. Esta empresa ofrece 3 tipos deservicios: telefona, TV cable e Internet, los cules pueden ser contratados individualmente o en combos de2 o 3 servicios, en los cules se les hace un descuento a los clientes. Por lo tanto, consideraremos que laempresa ofrece 7 servicios (xi) (los 3 individuales, 3 combinaciones de a 2 y 1 con los 3 servicios juntos),cada uno con un valor (yi) y un costo para la empresa (ci). El valor de cada servicio depende exclusivamentede la empresa, ya que no existe competencia en la zona.Adems, estos valores son tarifas planas, y en el6Mariangel Arratia L. Pedro Asencio H. Optimizacin 1erSemestre 2003.13caso de la telefona que se cobra tambin por el uso, se le agreg un valor adicional promedio para poderevaluar el problema. Para evaluar si el proyecto es o no rentable, habr que considerar que la empresa tieneuna imagen enfocada principalmente a entregar servicios de televisin por cable, por lo que el proyecto noles interesar si no entregan un mnimo de 100 servicios en esta rea. Por otra parte, la municipalidad de lazona slo le dar permiso para instalarse si logran satisfacer una demanda mnima de 180 telfonos. Adems,el servicio de internet que sera llevado a la zona, puede soportar un mximo de 200 abonados para asegurarla buena calidad del servicio. Tambin, para justicar sus combos de servicio, cada uno deber tener porlo menos 10 clientes. Finalmente, se tiene un capital de $5.000.000 para cubrir los gastos del primer mes(antes de recibir el pago de los abonados).SOLUCIN7El objetivo de la empresa es maximizar sus utilidades y para ello debe decidir la cantidad a ofrecer decada tipo de servicio, de esta manera la variable de decisin a emplear en el modelo resulta ser:xi =Cantidad de servicio del tipo i a ofreceri = {1 =TV cable, 2 =telfono , 3 = internet, 4 = TV cable, Internet y Telfono,5 = TV cable e Internet, 6 = Telfono e Internet, 7 = TV cable y Telfono}La funcin objetivo debe considerar la maximizacin de la utilidad, expresada como la diferencia entre lasganacias obtenidas y los costos incurridos por la entrega de cada tipo de servicio. El modelo debe considerarlas restricciones de un mnimo de servicio en TV cable y telfonos, un mximo de clientes de Internet yun mnimo de clientes para la entrega de servicios conjuntos, adems de las restricciones de capital para lainversin. Considerando esto el problema de optimizacin queda expresado por:P) Max7

i=1xi(yici)x1 +x4 +x5 +x7 100x2 +x4 +x6 +x7 180x3 +x4 +x5 +x6 2007

i=1xici 5.000.000xi 10 i = 1, ..., 7Problemas Propuestos:1. Analice qu ocurre si no existiera requerimiento de parte de la empresa en cuanto al nmero mnimode contratos de TV cable.Haga lo mismo para el requerimiento de la municipalidad y luego para elnmero mximo de abonados a Internet.2. Suponga que la empresa llega a una zona donde ya existe una empresa de condiciones similares peroque no ofrece combos o descuentos por contratar ms de un servicio. Esta empresa cuenta con 120contratos de telfono, 50 de Internet y 70 de TV cable. La nueva empresa decide comprarle sus clientes,pagando un monto de $20.000.000 ms un bono de 2ci por cada cliente (donde ci sigue siendo el costoque tiene para la empresa entregar el servicio).Toda esta gestin se realiza antes de que la empresase instale, i.e. la empresa sigue teniendo los mismos $5.000.000 para gastar durante el primer mes. Enesta zona tambin existen requerimientos; para telfonos el mnimo debe ser de 150, para Internet de100 y para TV cable de un mximo de 200. Plantee un nuevo modelo que maximice las utilidades dela empresa.7Cristian Andrs Salazar Huln, Optimizacin 1er Semestre 2003.142.8 Agua PuricadaUn comerciante compra agua puricada en grandes cantidades para luego venderla al detalle, en dos tipos deenvases (xi): botella de 1 lt y bidn de 5 lt. El precio de venta es de $350 y $300 por litro respectivamente.Se abastece a partir de dos proveedores (yi); el primero, puede venderle como mximo 10.000 lt a un valorde $100 por litro; y el segundo le ofrece la cantidad que l desee pero a un precio de $120 por litro. Entotal, el comerciante puede vender a lo ms 15.000 botellas de 1 lt y 10.000 bidones de 5 lt. al mes en elmercado, en base a un estudio de demanda realizado Por otro lado, el comerciante tiene un contrato segurocon una clnica a la cual debe entregarle adicionalmente 600 bidones de 5 lt. Por otra parte, en los lugaresa los cuales el comerciante abastece, compran ms botellas que bidones, pero igualmente, se cumple que lacantidad de litros de agua vendida en botellas es menos de13 del total de agua comprada.El comerciantenecesita decidir de qu forma abastecerse, de manera de maximizar su utilidad. Para simplicar el problema,considere que los costos de envasado son nulos, y que el comerciante vende todo lo que envasa.SOLUCINEl comerciante debe tomar dos decisiones, por un lado la cantidad de envases de cada tipo (botella ybidn) a vender, y por otro lado el modo de abastecerse de manera de satisfacer la demanda y maximizarsu utilidad, de esta manera las variables de decisin para el modelo pueden ser:xi = Cantidad de envases tipo i que vende el comerciante,i = {1 = botellas de 1lt, 2 = bidones de 5lt}yi = Cantidad de agua que el comerciante compra al proveedor i.El problema consiste en maximizar la utilidad del comerciante, como la diferencia entre los ingresospercibidos por la venta del agua, y los costos de abastecimiento. El modelo debe considerar como restricciones,la satisfaccin de la demanda total, la satisfaccin de la demanda adicional de la clnica, el mximo de litrosque se le puede comprar al proveedor 1, la proporcin de agua vendida en botellas de 1 lt y el hecho de queel comerciante vende todo lo que envasa, adems de las restricciones de no negatividad de las variables.El modelo de optimzacin para este problema queda expresado por:P) Max 350x1 + 1500x2100y1 120y2x1 15.000x2 10.600x2 600y1 10.0003x1 y1 +y2x1 + 5x2= y1 +y2xi, yi 0 i = 1, 2Problemas Propuestos:1. Qu pasa si se elimina la restriccin de que el comerciante vende todo lo que envasa?2. Analice como cambia el problema si el segundo proveedor:a) iguala los precios del primero, b) vende agua a un menor precio, pero con un mximo de 5.000 litros.3. Replantee el problema para el caso en que el comerciante decide vender adems botellas individualesde 500cc, a un valor de $200 (es decir, a un valor de $400 por litro).152.9 Confeccin de Ropa FemeninaCada ao, la moda tiene nuevos exponentes. Los diseos son cada vez ms exclusivos e irreverentes, enespecial la ropa femenina. Las mujeres quieren lucir mejor con cada prenda, quieren comodidad, estilo yvanguardia. Cada vez hay ms competencia en el rubro de la moda, las empresas desean vender ms paratener ms prestigio, estampar su nombre en la vestimenta femenina a largo plazo, para as obtener mayoresganancias.Para la confeccin de ropa femenina, hay que elegir muy bien las telas a usar para cada prenda, por susdistintos usos, su textura, grosor, cada y calidad.Cada empresa manufacturera tiene distintos estndaresde calidad y comodidad, segn el estilo que quiere imponer en una poca determinada, adems, los diseosestn enfocados a un pblico de una edad determinada. Adems se cuenta, con el gusto generalizado delpblico juvenil, dado por encuestas y estadsticas realizadas por socilogos que estudian el comportamientode la juventud en cuanto a su manera de vestir.Las diseadoras de ropa femenina, Mara Paz y Cristina, quieren sacar a la competencia en ropa femenina,su coleccin otoo-invierno, enfocada a las jvenes. Para lograr mayores ventas, han realizado un minuciosoestudio de mercado, que les permita lograr su objetivo. Para esto, cuentan con diseos nicos y novedososque se vendern con seguridad. Buscaron telas apropiadas para la confeccin de cada prenda: poleras, faldas,chaquetas, vestidos, abrigos, pantalones y chales.Por sus distintas cualidades, eligieron las siguientes telas: algodn, lino, raso, lycra, falla, y encaje. Todaslas telas de excelente calidad y usadas en distintas cantidades (en metros cuadrados) en la confeccin decada prenda.El objetivo de las diseadoras es maximizar las ventas de ropa femenina para as tener ms prestigio ymayores ganancias. Para esto se tiene una cantidad limitada dj de tela (en metros cuadrados), cada prendatiene un precio pi determinado por el mercado, y se usar una cantidad aij de tela j en la confeccin de laropa i. Se quiere encontrar la cantidad de unidades de cada prenda a confeccionar de modo de maximizarlas ventas.SOLUCION8Debido a que se desea encontrar la cantidad de unidades de cada prenda a confeccionar de modo demaximizar las ventas, las variables de decisin del modelo corresponden a:xi = Cantidad de prenda i a confeccionar, i = 1, ..., MAdems, dada la gran cantidad de prendas a confeccionar, no es necesario tomar en consideracin elhecho de que las variables de decisin deben ser enteras.Luego el modelo debe considerar como funcin objetivo la maximizacin de las ventas (precio por cantidadvendida), adems de la restriccin de que cada prenda requiere de una cierta cantidad de los distintos tiposde tela, existiendo un stock limitado de esta ltimas. Lo que queda expresado matemticamente por:P) MaxM

i=1pixiM

i=0aijxi djj = 1, 2..., Nxi 0 i = 1, 2..., M8Mara Paz Arriaza y Mara Cristina Manterola. Optimizacin 1er Semestre 2004.16Estruct. Mecnicos Elctricos Diseadores Transp.Esttica 2 1 0 2 0Estructura 2 1 1 1 1Mecnica 1 3 0 1 1Confort 1 1 0 2 0Tecnologa 0 0 2 2 1Seguridad 1 1 1 1 1Medio Ambiente 0 0 1 1 2Costo Semanal $15.500.000 $ 16.500.000 $ 17.200.000 $ 14.350.000 $ 14.750.000Table 3: Equipos Necesarios para cada Faceta del Automvil2.10 Diseo AutomotrizSuponga que usted es un magnate y, aburrido con los negocios convencionales, se ha decidido por empezar unnegocio automotriz cumpliendo el sueo que ha tenido desde pequeo: fabricar su propio vehculo. Para esto,luego de construir su propia empresa automotriz, ha contratado un equipo de ingenieros que se encargarnde disear cada faceta del nuevo vehculo, las cuales se han desglosado en: Esttica (Diseo de la carrocera) Estructura (Diseo de amortiguacin) Mecnica (Diseo del motor, transmisin, etc.) Confort (Diseo del interior, aislamiento sonoro, etc) Tecnologa (Implementacin de adelantos tecnolgicos, GPS, etc) Seguridad (Diseo de dispositivos de seguridad, air-bags, etc) Integracin con el medio ambiente (Baja emisin de contaminantes, reutilizacin de los componentes)El equipo de ingenieros que ha contratado para realizar semejante hazaa est dividido, segn la espe-cialidad de los profesionales que integran cada uno de stos, en los siguientes departamentos: Equipo de Ingenieros Estructurales Equipo de Ingenieros Mecnicos Equipo de Ingenieros Elctricos Equipo de Diseadores Equipo de Ingenieros de TransportePara lograr una total penetracin en el mercado usted ha decidido contratar a una empresa externaespecialista en la clasicacin de los automviles, la que est encargada de cuanticar el logro alcanzadopor este nuevo vehculo en trminos de puntaje. As, para cada una de los distintos aspectos del automvilse le ha asignado un puntaje de 1 a 10, donde 1 sera un aspecto logrado psimamente y un 10 sera unaspecto alcanzado a la perfeccin. Su objetivo sera entonces lograr la mayor suma de puntos en total, peroexiste un inconveniente. . . todo tiene su precio y la empresa externa especialista que lo asesora ha estimadoque se necesitan determinadas semanas de trabajo en cada aspecto para subir un punto. Adems, cadaaspecto debe ser atendido por ms de un equipo de desarrollo. Lo anterior se resume en la Tabla 3, dondese presentan adems, los costos semanales por equipo de trabajo.Por otra parte, el automvil contra el cual desea competir en el mercado ha sido evaluado por diversasrevistas especializadas y a usted le interesa que este nuevo vehculo salga eventualmente mejor evaluado entodas estas pruebas. Pero lamentablemente ninguna revista ha efectuado un desglose tan minucioso de lascaractersticas de los automviles y se dispone de la siguiente informacin:17Aspecto Costo por PuntoEsttica $ 76.200.000Estructura $ 93.800.000Mecnica $ 94.100.000Confort $ 60.700.000Tecnologa $ 77.850.000Seguridad $ 78.300.000Medio Ambiente $ 61.050.000Table 4: Costo de Aumentar un Punto cada Variable Revista No1: Esttica, Mecnica y Confort: 22 puntos Revista No2: Confort, Tecnologa, Seguridad y Mecnica: 21 puntos Revista No3: Esttica, Estructura Tecnologa y Seguridad: 28 puntos Revista No4: Medio Ambiente, Esttica y Mecnica: 24 puntosPor ltimo, un estudio de marketing indica que el vehculo no debe tener ningn aspecto con puntuacinmenor que 5 y a su vez el auto debe promediar una nota 7 como mnimo, para evitar una identicacinnegativa con la marca desde su lanzamiento.Su objetivo es crear un automvil que cumpla con todas estos requerimientos y, a la vez, sea lo mas baratoposible, es decir, que el dinero invertido sea el menor posible. El capital disponible es de US$6 millones,aproximadamente $3.810 millones.SOLUCION9El problema consiste en decidir que cantidad de dinero invertir en cada uno de los tems o facetas delvehculo, de esta manera la variable de decisin para el modelo resulta ser:xi = Cantidad de dinero a invertir en cada tem i, i = 1, ..., 7Analizando el problema, se aprecia que aumentar un punto en cada faceta del automvil tiene diferentescostos, dependiendo de los equipos involucrados. As, se debe determinar el precio que tiene aumentar enun punto cada variable, lo que se obtiene multiplicando el costo semanal de cada equipo por las semanasnecesarias para cada faceta. Los valores obtenidos (Ci, i = 1, ..., 7) se presentan en la Tabla 4.El objetivo del problema es minimizar el costo total, considerando las restricciones de que la puntuacindel automvil debe ser mayor o igual a 7, que ningn item puede tener una puntuacin menor a 5 ni mayorque 10 y que se deben superar las evaluaciones publicadas del otro vehculo. De esta manera, el modeloresulta ser:P) Min7

i=1xi9Jos Toms Cumsille y Camilo Flores. Optimizacin 1er Semestre 2004.187

i=1xiCi 495Ci xixi 10Cix1C1 + x3C3 + x4C4 22x3C3 + x4C4 + x5C5 + x6C6 21x1C1 + x2C2 + x5C5 + x6C6 28.x1C1 + x3C3 + x7C7 24xi 0 i = 1, ..., 72.11 El Curanto ms GrandeLa comunidad de Castro, con motivo de su semana de aniversario, ha decidido preparar el curanto ms grandejams hecho por alguna islea. Con este motivo, realiz diversas encuestas de opinin entre los mejorescocineros de la zona. La idea es poder determinar los ingredientes a utilizar, adems de sus cantidadesrespectivas, para lograr la mejor combinacin de sabores.El objetivo del estudio consiste en maximizar la calidad del curanto, calidad que se ver reejada enuna funcin de sabor, por ende, se requerir maximizar el sabor del plato.El estudio realizado incluy ensu desarrollo siete ingredientes, determinados como posibles por la encuesta hecha a los cocineros. Estosingredientes son: mariscos (x1), arroz (x2), pescado (x3), chorizo (x4), caldo (x5), verduras (x6), y pollo(x7).Como se sabe, el curanto es un plato que se prepara introduciendo todos los ingredientes en un hoyohecho en la tierra con brasas en el fondo. Por razones de sanidad (para poder asegurar la correcta coccinde todos los ingredientes), el volumen del hoyo no debe ser superior a los 1.000 lts. Cada ingrediente aporta,segn su cantidad, un cierto volumen al total. Por ejemplo, se ha estimado que un kilogramo de mariscos,ocupa 1, 5 lts de espacio (recordar que los mariscos van con concha), el volumen ocupado por los mariscos ylos restantes ingredientes se resumen en la Tabla 5.Por otro lado, la Municipalidad de Castro cuenta con un presupuesto de $500.000 para la realizacin delcuranto. Cada ingrediente tiene un costo asociado. Por ejemplo, un kilo de verduras tiene un costo de $400,mientras que el kilo de chorizo tiene un costo de $1.300 el kilo; los restantes costos se presentan en la Tabla5.La correcta consistencia del curanto, se debe en parte, a la cantidad de productos vegetales utilizados ensu preparacin. De esta forma, la cantidad de arroz y verduras a utilizar no debe superar los 200 kilos.En cuanto al modelo de calidad para determinar la funcin objetivo se consider lo siguiente: segn losdatos registrados por la Municipalidad, los diferentes ingredientes tienen distintos grados de aceptacinentre el pblico, por ejemplo, gusta ms una mayor cantidad de mariscos a una mayor cantidad de caldo. Deesta forma, cada ingrediente fue evaluado en una escala de 1 a 10, siendo 10 el mximo, los valores obtenidosse presentan en la Tabla 5.SOLUCION10El problema consiste en determinar la cantidad de cada ingrediente a utilizar de modo de lograr la mejorcombinacin de sabores, de modo que el modelo quedar bien expresado a travs de la variable de decisin:xi = Kilos de ingrediente i a utilizar en el curanto, i = 1, ..., 7Para expresar el objetivo del problema, que es maximizar la calidad del curanto, se debe hacer uso delestudio de aceptacin elaborado por la Municipalidad, adems de considerar las restricciones de volumen y10Javier Egaa. Optimizacin 1er Semestre 2004.19Ingrediente Volumen Costo AceptacinMariscos 1.5 1500 10Arroz 1.2 300 7Pescado 1.1 1000 7Chorizo 1.4 1300 9Caldo 1 500 5Verduras 1.3 400 6Pollo 1.6 1150 9Table 5: Volumen, Costo y Aceptacin de Ingredientesde costo asociadas, y la restriccin que asegura la correcta consistencia del curanto. Esto permite plantearel siguiente modelo:P) Max10x1 + 7x2 + 7x3 + 9x4 + 5x5 + 6x6 + 9x71.5x1 + 1.2x2 + 1.1x3 + 1.4x4 +x5 + 1.3x6 + 1.6x7 10001500x1 + 300x2 + 1000x3 + 1300x4 + 500x5 + 400x6 + 1150x7 500000x2 +x6 200xi 0 i2.12 FAMAE: Produccin de TirosFAMAE, Fbrica de Maestranzas del Ejrcito, es una empresa dependiente del Ejrcito de Chile que cuentacon una larga trayectoria en la historia de Chile y el mundo. Fundada en 1810, es la fbrica militar msantigua de Amrica y naci para dar solucin principalmente a los problemas de mantenimiento y provisinde los sistemas de armas nacionales. Su importancia recibi un gran empuje en la dcada de los 70 debido alefecto de la Enmienda Kennedy, que impeda el acceso a repuestos e insumos del mercado internacional dearmas, cuyo efecto ms crtico se alcanz en 1978, para la cuasi-guerra con Argentina. Luego de la crisis dela deuda del ao 1982, el empuje liberalizador de la Economa no slo alcanz a las empresas privadas, sinotambin a las militares. De esta forma FAMAE dio un gran paso al incorporarse al rubro de la maquinariaagrcola y sistemas de riego. Dentro de la misma dcada y especialmente en los aos 90, esta empresa se hamodernizado hasta el punto de empezar la produccin de armas de diseo nacional:SAF, Mini-SAF, etc.que se suman a la fabricacin de fusiles de asalto ocial, SIG 542 y SIG 540. Adems, se compr lalicencia a Suiza para la fabricacin de los Carros de Transporte 88 y 1010 Mowag Piranha. Este auge dela empresa ha sido adems acompaado por una mejora en la eciencia, tanto en los costos de produccin yeducacin del personal como en la mecanizacin de la fbrica. En especial, se han implementado laboratoriosmuy sosticados de balstica, resistencia al impacto de materiales, vidrios antibalsticos, qumica, etc. steltimo se benecia de la planta de qumicos del Ejrcito en Talagante, muy moderna y eciente.Actualmente se est llevando a cabo la segunda fase del gran proceso modernizador del Ejrcito (quees parte de un proceso que afecta a todas las FF.AA), que se expresa en hechos como: reduccin del per-sonal, cambio de planes de formacin en las Escuelas Matrices, adquisicin de equipo sosticado, exigenciasmayores para el personal de planta y Especializaciones en el extranjero, etc. Un aspecto muy importanteen este proceso es el de uniformar el armamento con el n de reducir costos de operacin. En particular,la Comandancia en Jefe ha solicitado al Director de FAMAE un plan de trabajo para municin estndarNATO, con el orden de produccin respectivo: Tiros Pistola 9 19 mm. Parabellum (entre 710 y 850 mil) Tiros 5, 56 45 mm. NATO (entre 2,4 y 4 millones) Tiros 7, 62 51 mm. NATO (entre 4,6 y 5,4 millones) Tiros 12, 7 99 mm. NATO (entre 1,9 y 2,7 millones) Tiros 20 110 mm. (entre 1,5 y 1,9 millones)20XiTiro Polvora Cobre Plomo Madera Precio1 9 mm. Parabellum 4.17 3.7 8.03 15 3322 5.56 NATO 1.9 3.04 3.56 14 2663 7.62 NATO 9.37 5.3 9.33 36 3104 12.7 NATO 5.9 12.05 11.3 37 3815 20 x 110 mm. 2.9 9.9 12.3 35 4226 7.62 x 39 mm. 5.1 4.7 7.9 23 3427 20 x 102 mm. 3.9 12.1 9.9 32 453Costo (US$/Kg) 5.25 0.81 12.95 0.25Table 6: Famae Produccin de TirosSin embargo, FAMAE enfrenta simultneamente otra demanda por parte de Brasil, quien no ocupa elestndar NATO, sino que el oriental: Tiros 7, 62 39 mm. (hasta 870 mil) Tiros 20 102 mm. (hasta 540 mil)Todos estos productos necesitan de insumos que se adquieren de proveedores nacionales y tambin dedivisiones internas del Ejrcito, como el complejo qumico ya sealado. Adems, los tiros de bajo calibre(desde 5, 56 a 7, 62 mm.) se distribuyen nicamente en cajas de madera de 1.000 cartuchos; los de 12, 7 mm.en cajas de 250, mientras que los ms pesados de 20 mm. se venden en cajas de 100. En la Tabla 6 sepresentan todos los datos (en Kg/caja) concernientes a unidades de componente por cada caja, precio deventa, etc.Es necesario aclarar que FAMAE dispone de un presupuesto para este proyecto de US$6, 78 millones,por lo que probablemente no cuenta con el dinero suciente para cumplir todos los pedidos. Adems, losstocks en el mercado de plvora y plomo son limitados. En el caso de la plvora, el Complejo Qumico deTalagante se ha comprometido a entregar hasta 198 toneladas de plvora. Por otra parte, la cantidad deplomo disponible est limitada por parte de la minera a 419 toneladas.El objetivo de nuestro taller es maximizar las utilidades por concepto de ventas.SOLUCION11Con este modelo se pretende determinar la cantidad de cada tipo de tiro a fabricar, de manera demaximizar la utilidad de la empresa. Por esta razn la variable de decisin para el modelo puede ser:xi = Cantidad de cajas de cada tipo de tiro i a fabricar. i = 1, ..., 7La funcin objetivo debe maximizar las utilidades por concepto de ventas, esto es la diferencia entre losingresos por ventas y los costos de materias primas. La Tabla 6 presenta el valor que se obtiene por la ventade cada tiro, el costo de cada materia prima y la cantidad de cada materia prima a emplear en los diferentestiros, de modo que la funcin objetivo resulta ser:Max 332x1 + 266x2 + 310x3 + 381x4 + 422x5 + 342x6 + 453x7[5.25 (4.17x1 + 4.9x2 + 9.37x3 + 5.9x4 + 2.9x5 + 5.1x6 + 3.9x7) +0.81 (3.7x1 + 3.04x2 + 5.3x3 + 12.05x4 + 9.9x5 + 4.7x6 + 12.1x7) +12.95 (8.03x1 + 3.56x2 + 9.33x3 + 11.3x4 + 12.3x5 + 7.9x6 + 9.9x7) +0.25 (15x1 + 14x2 + 36x3 + 37x4 + 35x5 + 23x6 + 32x7)]Lo que simplicado es equivalente a:Max 199.37x1 + 188.21x2 + 126.69x3 + 184.68x4 + 230.72x5 + 203.36x6 + 286.52x711Oscar Isler. Optimizacin 1er Semestre 2004.21Gas Licuado Carbn PetroleoPas 1 0.52 0.2 0.55Pas 2 0.58 0.26 0.5Pas 3 0.6 0.19 0.57Table 7: Costos Asociados a Importacin de CombustiblesTiempo Base (das) Gas Licuado Carbn PetroleoPas 1 75 0.07 0.06 0.072Pas 2 60 0.056 0.045 0.075Pas 3 60 0.061 0.07 0.062Table 8: Tiempo Adicional de Llegada de CombustibleEste modelo se debe completar con las restricciones del problema, las que incluyen la restriccin depresupuesto y de stock de materias primas (plvora y plomo), adems de los intervalos de produccin.Elmodelo completo se presenta a continuacin:P) Max 199.37x1 + 188.21x2 + 126.69x3 + 184.68x4 + 230.72x5 + 203.36x6 + 286.52x7132.63x1 + 77.79x2 + 183.31x3 + 196.32x4 + 191.28x5 + 138.637x6 + 166.48x7 6.78 1064.17x1 + 4.9x2 + 9.37x3 + 5.9x4 + 2.9x5 + 5.1x6 + 3.9x7 198.0008.03x1 + 3.56x2 + 9.33x3 + 11.3x4 + 12.3x5 + 7.9x6 + 9.9x7 419.000710.000 x1 850.0002.400.000 x2 4.000.0004.600.000 x3 5.400.0001.900.000 x4 2.700.0001.500.000 x5 1.900.0000 x6 8700 x7 5402.13 Crisis del GasDebido a la reduccin de las importaciones de gas natural desde Argentina, el gobierno chileno ha solicitadoa un grupo de expertos idear una poltica energtica que asegure de antemano los requerimientos mnimosdel pas para el ao 2005. De este modo, se requiere importar la materia prima suciente para generarexactamente 5.000 GWh de energa. Las plantas generadoras de energa se modicarn para operar con tresalternativas al gas natural: carbn, petrleo y gas licuado. Por otro lado, hay tres pases que poseen estosrecursos y estn dispuestos a exportarlos a Chile. Para poder comparar los tres combustibles entre s, nosconcentraremos slo en su capacidad de producir energa. O sea, el enfoque estar basado en decidir cuantosde los 5000 GWh necesarios se debern generar a partir de cada combustible.La Tabla 7 presenta los costos (en millones de dlares) asociados a la importacin de la cantidad sucientede cada combustible para generar 1 GWh.Es substancial que los combustibles importados lleguen al pas en un perodo no mayor a 180 das.Laimportacin total desde cada pas tarda cierto tiempo base en llegar, a lo que se debe agregar una demoraadicional variable en das (Tabla 8) que depende de la cantidad de cada combustible que se importe de esepas.Tambin se deben tomar en cuenta ciertas medidas relacionadas con el medio ambiente. El total de CO2emitido por las plantas energticas en Chile no podr superar las 1.300 toneladas al momento de generar los22CO2Emitido (Toneladas)Gas Licuado 0.16Carbn 0.4Petrleo 0.19Table 9: Emisin de CO2 de cada Combustible5.000 GWh. Evidencias experimentales muestran que por cada GWh generado a partir de cada combustiblese emite la cantidad de CO2 especicada en la Tabla 9Por ltimo, se han rmado dos acuerdos con los pases exportadores. Se deber adquirir la cantidadsuciente de petrleo del pas 3 para generar al menos 500 GWh. Adems, entre los tres tipos de combustible,se deber importar del pas 1 la cantidad suciente para producir 1.500 GWh.SOLUCIN12El objetivo del modelo es determinar una poltica energtica que asegure los requerimientos del pas parael ao 2005. Para ello debe generar 5.000 GWh a partir de tres tipos de combustibles, abastecindose desde3 pases; por lo tanto la decisin se basa en determinar la cantidad de cada tipo de combustible a importarde cada pas, en funcin de la energa que generar cada combustible, lo que es equivalente a emplear lavariable de decisin:xij = Cantidad de energa que generar el combustible i importado desde el pas jDe acuerdo a los datos expresados en las Tablas 7,??,8 y 9, cosideraremos conocidos los siguientesparmetros:cij = Costo asociado a importar la cantidad necesaria para generar 1 GWh a partir del combustible iproveniente del pas j.tij = Demora adicional por importar la cantidad necesaria para generar 1 GWh a partir del combustiblei proveniente del pas j.ai = Toneladas de CO2 emitidas al generar 1 GWh a partir del combustible i.Ntese que esto se emplea solo para simplicar la presentacin del problema, usando una notacin agre-gada en lugar de usar cada uno de los datos dados por separado, como se ha hecho en problemas anteriores.Ahora bien, el objetivo del modelo es minimizar los costos asociados a importar los combustibles nece-sarios, considerando como restricciones cumplir con la poltica energtica de 5.000 GWh, el hecho de quelos combustibles no pueden demorar ms de 180 das en llegar al pas, que en el proceso de generacin deenerga no se pueden emitir ms de 1300 toneladas de CO2 y que se deben cumplir los acuerdos establecidoscon los pases exportadores.De acuerdo a lo anterior, el modelo de optimizacin se puede expresar por:P) Min3

i=13

i=1cijxij12Christian Araya. Optimizacin 1erSemestre 2004.23

3i=1

3i=1xij= 5000

3i=1ti1xi1 + 75 180

3i=1ti2xi2 + 60 180

3i=1ti3xi3 + 60 180

3i=1xi1 1500

3i=1

3i=1aixij 1300x13 500xij 0 i, j2.14 Fbrica de LadrillosUna fbrica produce tres tipos de ladrillos: de primera, segunda y tercera calidad. Para un metro cbico deladrillos, se requiere un metro cbico de material base y aditivos adicionales. La calidad de los ladrillos sedistingue en los aditivos que cada uno requiere. En este momento la planta tiene 2.000 m3de material basey se debe decidir cunto producir de modo de maximizar el ingreso por ventas. Los precios de los ladrillosson $2.000, $1.800 y $1.500 el m3respectivamente segn la calidad.Existen dos tipos de aditivos, clase A y B. Cada metro cbico de ladrillo de primera calidad requiere 500 ml del aditivo A. Cada metro cbico de ladrillo de segunda calidad requiere 250 ml del aditivo A y 350 ml del aditivo B. Cada metro cbico de ladrillo de tercera calidad requiere 800 ml del aditivo B.La fbrica maneja un stock de 200 lts del aditivo A y 1.000 lts del aditivo B. Se le pide generar un modelode programacin que reeje las caractersticas del problema descrito.SOLUCIONEl objetivo del problema es decidir cunto producir de cada tipo de ladrillo de manera de maximizar elingreso por ventas, por lo que resulta conveniente emplear la variable:xi = Cantidad a producir del ladrillo tipo i,i = {1: Primera calidad, 2: Segunda calidad, 3: Tercera calidad}Como dato del problema se nos da la cantidad a emplear de cada aditivo para producir un metro cbicode cada ladrillo, as como el precio de venta de cada uno de ellos.El objetivo del problema es maximizar los ingresos por concepto de ventas, sujeto a las restricccionesde stock de cada una de las materias primas (material base y aditivos), adems de las restricciones de nonegatividad exigidas por la implementacin del modelo Con esto en consideracin, el modelo de optimizacinqueda expresado por:P) Max 2.000x1 + 1.800x2 + 1.500x30.5x1 + 0.25x2 2000.35x2 + 0.8x3 1.000x1 +x2 +x3 2.000x1, x2,x3 0Problemas Propuestos24Descripcin Choclo Alfalfa Porotos TrigoProduccin por hectreas (unidades) 50 40 40 15Precio de venta por unidad 2.75 1 2.5 3Costo de plantacin por hectrea 25 10 25 22Trabajo requerido en hrs-hombre en Septiembre 0 1.5 0 1Trabajo requerido en hrs-hombre en Diciembre 1.5 0 2.5 0.5Table 10: Datos del Problema Decisin de Produccin Agrcola1. Replantee el modelo para el caso en que, aadiendo un aditivo C a los ladrillos de primera, segunda ytercera, se obtiene un ladrillo de superprimera, supersegunda o supertercera. Considere que los preciosde estos ladrillos son el doble de los normales, y que las cantidades necesarias de aditivo por ladrilloson 150 ml, 95 ml y 80 ml, respectivamente. El precio por litro del aditivo C es de $10.000. Cuantose producira ahora de cada uno de los seis tipos de ladrillo?.2. Como modicara el modelo si es que le ofrecen una nueva tecnologa, para la cual se requieren tresmquinas, una para el proceso con el material base, otra para la aplicacin del aditivo A, y otra para laaplicacin del aditivo B, cuyos precios son $10.000, $120.000 y $8.000, respectivamente. Al utilizar estanueva tecnologa, los ladrillos pasan a requerir: el ladrillo de primera, 200 ml de aditivo A y 800 cm3dematerial base; el ladrillo de segunda, 100 ml de aditivo A, 200 ml de aditivo B y 900 cm3de materialbase; y el ladrillo de tercera, 250 ml de aditivo B y 850 cm3de material base. Considere el caso en quela tecnologa debe instalarse completa y el caso en que se pueden instalar independientemente cadauno de los procesos, esto es, se pude instalar la maquinara correspondiente a la aplicacin del aditivoA independientemente de la que modela el material base.2.15 Decisin de Produccin AgrcolaUn agricultor tiene 300 hectreas de tierra, 200 horas-hombre disponibles en Septiembre y 300 horas-hombredisponibles en Diciembre. Puede plantar cualquier combinacin de los siguientes productos: choclo, alfalfa,porotos y trigo.Formule un modelo de programacin lineal que, considerando los datos dados en la Tabla 10, permitadeterminar cundo y cunto debe plantar el agricultor de cada producto de modo de maximizar sus ganancias.El modelo debe considerar, adems, los siguientes supuestos: La tierra plantada en septiembre no se puede utilizar en diciembre. Considere que lo plantado en septiembre y diciembre se cosecha en el mismo tiempo (en el futuro). Se vende todo lo que se produce. El trabajo requerido en horas-hombres por hectreas durante septiembre y diciembre, se incurr slosi plant o est plantado el cereal respectivo. Los meses que el trabajo necesario por hectrea es cero son interpretados como que en esos meses nose puede plantar ese producto, o no es necesario dedicarle tiempo a la plantacin, una vez hecha.SOLUCIONEl objetivo del problema es determinar la poltica de cultivo que debe seguir el agricultor, de manerade maximizar su utilidad. Esta poltica incluye la opcin de plantar cualquier combinacin de productos,considerando incluso la de no plantar. Para poder responder a la pregunta de cunto y cundo debe plantarel agricultor, emplearemos la variable de decisin:xij = Nmero de hectreas del producto i que el agricultor debe plantar en el mes j.i = {1 : choclo, 2 : alfalfa, 3 : porotos, 4 : trigo} j = {A : Septiembre, B : Diciembre}25Descripcin Choclo Alfalfa Porotos TrigoBenecio por Hectrea 112.5 30 75 23Table 11: Benecio de cada Producto CultivadoDe acuerdo a los datos entregados en la Tabla 10 podemos obtener el benecio por hectrea de cada tipode cultivo, empleando la relacin dada por la expresin en (1). Los valores obtenidos se presentan en laTabla 11Benecio por hectrea = Produccin por hectreaPrecio unitario - Costo por hectrea (1)De esta manera, el objetivo del problema es maximizar el benecio total para el agricultor, considerandolas restricciones de terreno de cultivo (mximo de 300 hectreas) y de mano de obra disponible durante cadames. Por otro lado, se debe considerar que las variables son no negativas, y que x1A, x3A y x2B siempre soncero, ya que no es posible realizar ese tipo de cultivo en el mes correspondiente.Esto permite formular elsiguiente problema de optimizacin:P) Max 112.5x1B + 30x2A + 75x3B + 23(x4A +x4B)x1B +x2A +x3B +x4A +x4B 3001.5x2A +x4A 2001.5x1B + 2.5x3B + 0.5x4B 300x1B, x2A, x3B, x4A, x4B 0Problemas Propuestos1. Suponga que un vecino ofrece al agricultor arrendarle hectreas para cultivar, a un precio de $15 lahectrea al ao. Considere que esta tierra cuenta con caractersticas diferentes a la propia cmoincluira esta nueva posibilidad en el modelo?2. Ahora considere que un vecino ofrece arrendarle sus tierras por $20 la hectrea anual de qu maneraincluira esta nueva condicin en el modelo?3. Que ocurrira si ahora se ofrecen para ser contratados obreros, que le cobrarn $0,2 por hora trabajada?Implemente esta nueva condicin en el modelo. Considere el caso opuesto, en que a Ud. le ofrecencontratarlo para labrar otra tierra a $0,3 la hora.4. Cmo modicara el problema si le informan que pueden transportarle a otro mercado, donde le pagan$5.5, $2, $5 y $6 por unidad de choclos, alfalfa, porotos y trigo, pero que para llegar a l debe pagarun costo por transporte que le cuesta $500 el viaje y que en cada viaje puede llevar o 200 choclos o150 alfalfas o 150 porotos o 75 unidades de trigo, o una combinacin que mantenga esta proporcin,por ejemplo 100 choclos y 75 alfalfas? Aada esta nueva condicin al modelo primitivo.2.16 Proceso ProductivoUna empresa produce tres productos: A, B, y C. Para esto dispone de tres mquinas: 1, 2 y 3, adems de3 tipos de personal: a, b y c y 2 insumos base e y f.El proceso de produccin de cada uno de estos tresproductos es el siguiente:Para producir una unidad de A, un funcionario tipo a toma 100 gramos de e y los procesa por 20 minutos.Luego, lo deja en la mquina 1 por 40 minutos. A continuacin lo toma nuevamente el funcionario tipo a ylo entrega en la sala donde trabajan los hombres tipo b, esto le toma 5 minutos. All, se procesa el productoen la mquina 2 y se le agregan 20 cm3de insumo f, demorando el paso por el taller 45 minutos (de uso26intensivo de hombre y mquina), trabajando en una unidad 2 funcionarios simultneamente todo el tiempo.As, se obtiene una unidad de tipo A que se vende en el mercado a $150 cada una.Para producir una unidad de B, un funcionario tipo a toma 100 gramos de e, 50 cm3de insumo f y dosunidades de A. Los mezcla bien durante 25 minutos y lo pasa a la sala donde trabajan los individuos tipoc. All, estos hombres mediante 50 minutos de la mquina 3 dejan listo una unidad de tipo B que se vendeen el mercado a $400 cada una.Para producir una unidad de C, un funcionario tipo a junto a uno de tipo c toman tres unidades de A yuna unidad de B, agregan 25 cm3de insumo f y lo trabajan por 40 minutos en una mquina 2.De estemodo se obtiene una unidad de tipo C que se vende en el mercado a $2.500 cada una.En este momento en la empresa trabajan 10 operarios de cada tipo, trabajando cada uno de ellos 40horas semanales (una semana se considera de cinco das hbiles y un mes de 20 das hbiles). Supondremosque en el corto plazo estos funcionarios no son modicables. Actualmente existe disposicin ilimitada deinsumo e, pero slo 25.000 cm3diarios de insumo f.El sueldo de los operarios es M$250, M$400 y M$450 al mes para los tipos a, b y c respectivamente.El costo del insumo e es $30 cada 100 gramos y del insumo f es $50 el litro.Suponga que por efectos dearriendo de las mquinas la empresa debe pagar $1.000, $1.200 y $1.500 diarios respectivamente. En el cortoplazo, la estructura de las mquinas no puede modicarse, es decir no se puede devolver una mquina niarrendar ms de una adicional.Adems la empresa tiene otros costos en administracin, ventas, marketing, arriendo y otros equivalentea $12.000 diarios.Cree un modelo de optimizacin que maximice las utilidades de esta empresa en el corto plazo con-siderando las caractersticas aqu expuestas.SOLUCIONDada la forma en que se presenta el problema, el primer paso ser identicar y organizar los datosentregados. Note que la siguiente informacin es conocida: Cantidades especcas para la produccin de cada producto en cuanto a insumos (e y f), mquinas(1, 2 y 3) y personal (a, b y c). Sueldos de cada funcionario (a, b y c) y costos de mantencin de maquinaria (costos jos). Precio de los insumos e y f, y precio de venta de los productos A, B y C. Detalles relacionados con la forma de trabajo de los obreros a, b y c. Gasto jo por otros conceptos,de 12.000 diarios.Esta informacin se presenta organizada y resumida en las Tablas 12 y 13.Notemos que lo nico que vara son aquellos parmetros que dependen de la produccin. Es decir, nuestravariable de decisin debe ser la cantidad a producir de cada uno de los productos, el problema es que elsistema se retroalimenta, esto es para producir B utiliza A y para producir C utiliza A y B. Una primeraformulacin del problema considera la cantidad que la empresa produce de cada elemento, incluidos aquellosque se utilizan para la produccin de otro. Se podra hacer un modelo alternativo utilizando como variablela cantidad de producto que sale desde la fbrica, esto requiere slo un cambio de variable al primer modelo,el cual especicaremos posteriormente.Luego, las variables de decisin a emplear son:A = Cantidad producida del elemento AB = Cantidad producida del elemento BC = Cantidad producida del elemento CComo notacin consideraremos:27A B Ca (minutos) 25 25 40b (minutos) 2*45c (minutos) 50 40e (gramos) 100 100f (cm3) 20 50 251 (minutos) 402 (minutos) 45 403 (minutos) 50A (unidades) 2 3B (unidades) 1C (unidades)Precio ($) 150 400 2500Table 12: Datos del Problema Proceso ProductivoCosto ($) Tiempo Disponible (minutos) Cantidad Mensuala250000mesfuncionario40460mesfuncionario10b400000mesfuncionario40460mesfuncionario10c450000mesfuncionario40460mesfuncionario10e0.3grf0.05cm3250000 20 cm31201000mes40460mesmquina12201200mes40460mesmquina13201500mes40460mesmquina1Otros2012000mesTable 13: Datos del Problema Proceso Productivo28e = Gramos consumidos del insumo ef = cm3consumidos del insumo fEl objetivo del modelo es maximizar las utilidades por concepto de venta de los productos, ahora bien,de acuerdo a las variables de decisin escogidas la cantidad que se vende del producto A corresponde enrealidad a A 2B 3C, de la misma manera lo que se vende de B es B C, mientras que el productoC es destinado completamente para la venta.Por otro lado la funcin objetivo debe considerar los costosvariables por insumo (e y f), y los costos jos por mquinas, operarios y otros.Las restricciones del modelo deben considerar las restricciones de tiempo para los operarios y mquinas(ver Tabla 13), las restricciones de stock para los insumos, la equivalencia de e y f en trminos de A, B y Cy el hecho de que las cantidades que se venden y que se producen de cada producto deben ser no negativas.De acuerdo a las consideraciones anteriores, el modelo de optimizacin resulta ser:P) Max 150(A2B 3c) + 400(B C) + 2.500C 0.3e 0.05f [20(1.000 + 1.200 + 1.500)] + [10(250.000 + 400.000 + 450.000)] + (20 12.000)25A+ 25B + 40C 9.6002 45A 9.60050B + 40C 9.60040A 9.60045A+ 40C 9.60050B 9.600100A+ 100B = e20A+ 50B + 25C = f25.000 20 fA2B 3C 0B C 0A, B, C 0Eliminando la notacin de e y f y simplicando expresiones, el modelo anterior es equivalente a:P) Max 119A+ 67.5B + 1648.75C 10.814.00025A+ 25B + 40C 9.60090A 9.60050B + 40C 9.60040A 9.60045A+ 40C 9.60050B 9.60020A+ 50B + 25C 500.000A2B 3C 0B C 0A, B, C 0Adems, como se mencion anteriormente existe la posibilidad de modicar el modelo planteado, uti-lizando como variables de decisin las cantidades que se venden (o salen al mercado) de cada producto, esto29% de Pesca segn sector Peso promedioTipo de pez I II III IV por pezAtn 12 15 32 43 3 KgsSardina 38 27 18 22 2 KgsJurel 24 33 38 17 2.5 KgsMerluza 26 25 12 18 1.5 KgsTable 14: Pocentaje Promedio de Pesca y Peso por Pezes A, b y c. Para eso basta emplear el cambio de variables dado en (2) en el modelo anterior.A= A2B 3C (2)B= B CC= CProblemas Propuestos1. Como modicara el modelo para el caso en que se pudiera contratar o despedir a operarios? Considereadems que la oferta mxima de operarios en el mercado es de 25 de tipo A, 15 de tipo B y 20 de tipoC.2. Considere ahora, adems de lo anterior, que tiene la posibilidad de comprar ms maquinaria, a unprecio de $12.000 la mquina 1, $8.000 la mquina 2, y $10.000 la mquina 3. Le ofrecen slo dosmquinas 1, tres mquinas 2 y una mquina 1. Considere el caso en que las mquinas pueden comprarsepor unidad, el caso en que se deben comprar todas las mquinas de un tipo, y un tercer caso en que elpaquete de venta esta conformado por las seis mquinas.3. Suponga que le ofrecen una tecnologa con la cual puede producir insumo f, a partir del insumo e,mediante un proceso que consume 50 gramos de e, y produce 1 litro de f, en un plazo de diez minutosmediante el uso de agua, con un costo que se considera despreciable. Para esto debe adquirir lamaquinaria necesaria, cuyo costo asciende a $15.000. Considere que debe pagarle a un operario extrade tipo d, el que recibe un sueldo de $1.500 por hora trabajada.2.17 Itinerario Empresa PesqueraUsted trabaja en una empresa pesquera y se le ha pedido que optimice el recorrido de un barco especcoen su itinerario de pesca alrededor de una isla. En la Figura 1 se observa la isla, el barco debe comenzar yterminar su itinerario en el punto A. En su recorrido deber pasar por cuatro sectores (I, II, III y IV) queson puntos de inters pesquero debido a la alta densidad de peces.El barco tiene una velocidad mxima de 15 Km/hr y una velocidad mnima de 10 Km/hr. Su rendimiento(en Km/lt) puede estimarse como 1/V elocidad, cuando la velocidad se expresa en Km/hr. El barco tieneuna capacidad de 5.000 toneladas de carga de pago (slo los peces) y de 430 lts de combustible.Para simplicar el problema suponga que los sectores pueden modelarse como puntos en los cuales sepesca y que las distancias entre sectores es AI: 8Kms, I II : 10Kms, II III : 5Kms, III IV : 7Kms,IV A : 9Kms. Suponga tambin que cuando el barco est en un sector, no consume combustible.En cada uno de los sectores se encuentran cuatro tipos de peces en distintas proporciones, cada uno deesos peces tiene un peso promedio distinto. Ambas informaciones se presentan en la Tabla 14.En cada sector la velocidad de pesca se estima en 60 peces por minuto. El viaje debe iniciarse a las 8:00hrs. y debe concluir a las 18:00 hrs no importando la hora en que pase por cada sector. Por ltimo, se conoceel costo de procesar cada uno de estos peces y el precio de venta del kilo de pez faenado. Esta informacinse encuentra en la Tabla 15.El costo del combustible es $150 el litro y existe un costo jo de realizar la operacin equivalente a cincomillones de pesos.30Figure 1: Itinerario Empresa PesqueraHead Costo de proceso Porcentaje de pescado til Precio de venta del pezAtn $100/pez 80% $600/KgSardina $125/pez 90% $400/KgJurel $90/pez 75% $200/KgMerluza $85/pez 85% $250/KgTable 15: Costo, Precio y Porcentaje de cada Pez31Usted debe escribir un modelo de optimizacin que maximize las utilidades de este viaje por medio deuna adecuada programacin de los tiempos que se queda el barco en cada sector.SOLUCINEl objetivo del problema es determinar la forma de realizar la pesca de modo de maximizar los beneciosdel proceso. Esto signica determinar el tiempo de pesca en cada sector y el tiempo a usar para ir entreun sector y otro (notar que ste ultimo implica conocer la velocidad, ya que se conoce la distancia paracada trayecto), mientras que la cantidad de combustible a utilizar queda determinada por la ecuacin derendimiento. De esta manera emplearemos las siguietes variables de decisin:tk = Tiempo (en horas) que el barco permanece detenido en el sector k, k = I, II, III, IVxij = Tiempo (en horas) de trayecto entre el sector i y el sector j,i = A, I, II, III, IV j = I, II, III, IV, AAdems, por comodidad, deniremos las siguientes variables dependientes:vij = Velocidad entre el sector i y el sector j.lij = Litros de combustible gastados entre el sector i y el sector j.Adems, emplearemos notacin agregada para referirnos a algunos de los datos dados, de tal manera que:dij = Distancia (en kilmetros) entre el sector i y el sector j.plk = Porcentaje de pesca del pez l en el sector k, l = {1 : Atn, 2 : Sardina, 3 : Jurel, 4 : Merluza}pl = Peso promedio del pez l l = {1, 2, 3, 4}cl = Costo de proceso (por pez) del pez l.ul = Porcentaje de pescado til del pez l.sl = Precio de venta del pescado l.Ahora bien, la velocidad ser igual a la distancia recorrida dividida por el tiempo utilizado en recorrerla(ver (3)), mientras que los litros de combustibles gastados corresponden al nmero de kilmetros recorridosmultiplicado por el rendimiento (inverso de la velocidad) como se aprecia en (4).vij = dijxij(3)lij = dijxijdij = xij(4)El ingreso que reporta la extraccin de cada tipo de pez, se obtiene empleando la relacin dada en (5).Ingreso Pez l = sl pl ul

kplk 3.600 tk(5)El costo de extraccin y procesamiento del pescado se obtiene empleando la relacin dada en (6).Costo de Procesar el pez l = cl

kplk 3.600 tk(6)Adems, existe un costo jo por realizar el circuito y un costo de combustible consumido, el que seexpresa en (7).Otros Costos = 150(xAI +xIII +xIIIII +xIIIIV +xIV A) + 5.000.000 (7)Ahora bien, el objetivo del problema es maximizar la utilidad de la empresa, esto es la diferencia entrelos ingresos percibidos y los costos incurridos, lo que de acuerdo a lo expresado anteriormente es equivalentea:32

l

kplk 3.600 tk(sl pl ul cl) 150(xAI +xIII +xIIIII +xIIIIV +xIV A) 5.000.000 (8)Por otro lado, el modelo debe considerar las restricciones de velocidad mxima y mnima, capacidad delbarco (en cunto a carga de pago y combustible) y el tiempo mximo de viaje, adems de la no negatividad delas variables (ntese que no es necesario agregar restricciones de signo para xij, ya que stas se encuentranacotadas). Considerando esto, y las relaciones dadas en (3), (4) y (8), se obtiene el siguiente modelo deoptimizacin:M ax l

kplk 3.600 tk(sl pl ulcl) 150(xAI +xIII +xIIIII +xIIIIV +xIV A) 5.000.000dij15 xij dij10i, j

lpl

kplk 3.600 tk 5.000.000xAI +xIII +xIIIII +xIIIIV +xIV A 430IV

k=Itk +xAI +xIII +xIIIII +xIIIIV +xIV A 12tk 0 kProblemas Propuestos1. Qu cambiara en el modelo si los sectores de pesca no fueran ya puntos y uno siguiera viajando porellos, gastando combustible y recorriendo as los sectores de pesca?2. Que pasara si el costo jo de 5.000.000 fuera ahora dependiente del tiempo de viaje? Y si ahora loque queremos optimizar es el tiempo de viaje, pero queremos percibir un benecio neto de 5.000.000?3. Que ocurrira si se sabe que la demanda por atn es 1.000 pescados, por sardina 1.250, por jurel 640y por merluza de 980?4. Cmo debemos arreglar el modelo si ahora se nos pide hacer una programacin anual para la pesca,donde se nos entregan temporadas de pesca, temporadas de veda, etc? Considere adems que mensu-almente variarn los porcentajes extrados en cada zona, por pez. Adems, considere que en inviernoexisten en promedio dos das a la semana en que no se podr pescar debido al clima, pero de todasmaneras se deber cancelar el sueldo de la tripulacin, que corresponde al 20% del costo total de cadaviaje.5. Que pasara si para hacer la extraccin se nos ofrecen dos tipos de barcos, con diferentes precios, perocon diferentes porcentajes de extraccin por sector y cantidad de pesca por minuto?2.18 Sistema de Atencin TelefnicoUsted es ingeniero de una empresa de servicios que recibe las solicitudes de compra, los reclamos y lainformacin por medio del telfono. Esta empresa cuenta con un sistema con capacidad de 100 llamadassimultneas. Cuando llega una llamada, si existe al menos una telefonista desocupada, una de ellas toma elllamado, si todas estn ocupadas, entonces la llamada dar tono ocupado y se perder la comunicacin.El problema se suscita al contratar a las telefonistas, debido a que la empresa trabaja de lunes a domingo,sin embargo los contratos con las operarias deben tener das de descanso.El departamento de marketing le informa que, de acuerdo a sus estimaciones, de lunes a viernes debe habercomo mnimo 100 telefonistas trabajando. Ellos estiman que las solicitudes caen los sbados y domingos ypor lo tanto se requieren como mnimo 70 telefonistas el sbado y 45 el domingo.Por otra parte, el departamento jurdico le informa a usted que el sistema tradicional de trabajar lunes aviernes y descansar sbados y domingos no es obligatorio en los contratos laborales, es decir pueden crearsenuevos arreglos, sin embargo deben respetarse ciertas normas:331. No se puede trabajar ms de diez das continuados ni menos de tres.2. No se puede dar ms de cuatro das de descanso seguidos ni das aislados.3. Cualquier frmula debe contemplar que los das laborales y los festivos deben estar en proporcin cincoes a dos.4. Todos los operarios deben tener al menos un domingo libre al mes.En base a estos argumentos, el departamento jurdico le propone a usted tres tipos de contrato:1. Un primer tipo es para telefonistas que trabajan de lunes a viernes y descansan sbados y domingos.2. Un segundo consistir en que la primera semana la persona descansar lunes y martes, la segundamartes y mircoles, la tercera mircoles y jueves, la cuarta jueves y viernes, la quinta viernes y sbado,la sexta sbado y domingo y la sptima domingo y lunes.De ah en adelante se repetir otra vez laprimera y as sucesivamente.Para esto se contratarn grupos de siete personas que realicen su ciclode trabajo con una semana de desfase.3. Otro contrato consistir en que la primera semana descansar lunes y martes, la segunda mircoles yjueves, la tercera viernes y sbado, la cuarta sbado y domingo.De ah en adelante se repetir otravez la primera y as sucesivamente.Para esto se contratarn grupos de cuatro personas que realicensu ciclo de trabajo con una semana de desfase.El departamento de personal le informa que el sueldo de una persona segn el primer tipo de contrato esde $200.000. Para el segundo tipo es de $240.000 y el tercero es de $250.000. Le indican adems que creenque habr suciente gente interesada en trabajar.Usted debe formular un problema de optimizacin para determinar cuntas telefonistas contratar demodo de satisfacer los requerimientos de marketing y qu los costos para la empresa sean mnimos.SOLUCINEl objetivo del problema es determinar cuntas telefonistas contratar en cada tipo de contrato de modode satisfacer los requerimientos de marketing y qu los costos para la empresa sean mnimos.Para el desarrollo de este modelo supondremos que los meses constan de 28 das, o lo que es lo mismo,que los sueldos se pagan por cada perodo de ese largo. Esto nos ayuda a eliminar cualquier tipo de problemaque se podra originar en una semana incompleta, con los sueldos, el nmero de operarios trabajando, etc.Ahora bien, la forma de contratar es por personas segn algunos contratos y por grupos segn otros, porlo tanto, las variables de decisin del modelo deben ser coherentes con stas condiciones, de esta manera,sea:x = Nmero de personas contratadas por contrato de tipo 1.y = Nmero de grupos de 7 personas contratadas por contrato de tipo 2.z = Nmero de grupos de 4 personas contratadas por contrato de tipo 3.Es necesario relacionar las variables de decisin con el nmero de operarios que se encontraran trabajandocada da, para esto se elaboraron tablas, las cuales se rellenaron con cruces si ese da el usuario en cuestintrabaja, estableciendo los totales de trabajo por da para cada uno