GESTIN DE INVESTIGACIN DE OPERACIONES (GIO) ILN250
PROF. FRANCISCO YURASZECK E. INGENIERO COMERCIAL UTFSM MAGSTER EN MARKETING UAI
SOCIO INSTITUTO CHILENO DE INVESTIGACIN OPERATIVA (ICHIO) E-MAIL: [email protected]
DEPARTAMENTO DE INDUSTRIAS UNIVERSIDAD TCNICA FEDERICO SANTA MARA
GESTIN DE INVESTIGACIN DE OPERACIONES
Primer Semestre 2015
Contacto
Para cualquier consulta respecto a los contenidos del curso, evaluaciones, etc, por favor escribir a [email protected]
Horario de Consultas:
Durante o una vez finalizada la clase (de preferencia) o por correo electrnico. Las consultas enviadas por este ltimo medio se respondern a la brevedad (considerar un mayor tiempo de respuesta si las consultas son enviadas los fines de semana).
2
Contenidos
I. Introduccin a la Investigacin Operativa
II. Modelos de Programacin Matemtica
Programacin Lineal
Programacin Entera
Programacin No- lineal
III. Modelos Probabilsticos
Cadenas de Markov
Sistemas de Espera
3
Bibliografa
Bibliografa bsica, comprende textos generales de introduccin a la investigacin de operaciones (Libros disponibles en coleccin de alta demanda y/o coleccin general de la Biblioteca Casa Central):
Hillier, F. S. y Lieberman, G.J.
Taha, H. A.
Ortiz, C., Varas, S. y Vera, J.
Bibliografa complementaria, lista de ttulos en cada tema especfico. (Ver Programa del Curso)
4
Introduccin
Elementos bsicos de un modelo de optimizacin.
La Optimizacin, en particular, es una de las
metodologas ms importante para formular y resolver
diversos problemas orientados a la toma de decisiones
en las diferentes reas de la Ingeniera, la Economa y,
en particular, en la Investigacin Operativa.
5
Introduccin
La Optimizacin se relaciona con problemas de minimizar o maximizar una funcin (objetivo) de una o varias variables, cuyos valores usualmente estn restringidos por ecuaciones y/o desigualdades.
El enfoque de la Investigacin de Operaciones es el modelaje. Un modelo es una herramienta que nos sirve para lograr una visin bien estructurada de la realidad. As, el propsito del modelo es proporcionar un medio para analizar el comportamiento de las componentes de un sistema con el fin de optimizar su desempeo (identificar el mejor curso de accin posible)
6
Introduccin Metodologa de la IO
7
Definicin del problema
Construccin de un modelo
Solucin del modelo
Validacin Implementacin y control de la
solucin
Introduccin
Hoy en da el uso de modelos de optimizacin es cada vez ms frecuente en la toma de decisiones. Este mayor uso se explica, principalmente, por un mejor conocimiento de estas metodologa en las diferentes disciplinas, la creciente complejidad de los problemas que se desea resolver, la mayor disponibilidad de software y el desarrollo de nuevos y mejores algoritmos de solucin. Links de Inters: https://www.informs.org/Sites/Getting-Started-With-Analytics http://www.ichio.cl http://www.dii.uchile.cl/~ris/ http://www.neos-guide.org/ http://www.gestiondeoperaciones.net/category/programacion_lineal/
8
Introduccin: Ejemplo
Supongamos que se dispone de determinadas piezas
para la elaboracin de dos productos finales. Se
dispone de 8 piezas pequeas y 6 piezas grandes.
Estas piezas son utilizadas para elaborar sillas (usando
2 piezas pequeas y 1 pieza grande) y mesas (usando
2 piezas de cada tipo).
9
Introduccin: Ejemplo
Interesa decidir cuntas sillas y mesas fabricar de modo
de obtener la mxima utilidad, dado un beneficio neto
de U$ 10 por cada silla y de U$16 por cada mesa
fabricada.
10
Introduccin: Ejemplo
La solucin ptima de este problema se encuentra enumerando las posibles soluciones factibles a considerar, esto es soluciones que respetan las restricciones del nmero de piezas disponibles, son por ejemplo soluciones factibles, fabricar:
4 sillas, que reportan una utilidad de U$40
1 sillas y 2 mesas , utilidad de U$42
3 mesas, utilidad de U$48
1 mesa y tres sillas, utilidad de U$46
2 sillas y 2 mesas, utilidad de U$52
etc.
11
Introduccin: Ejemplo
El conjunto de puntos factibles (o soluciones factibles) se puede
representar grficamente en este ejemplo de 2 variables:
12
Un software para representar grficamente un modelo de PL en 2 variables
es Geogebra. Descargar desde www.geogebra.org
Introduccin: Ejemplo
Un modelo de optimizacin para hallar la mejor solucin
factible a este problema tiene tres componentes bsicas:
i) Las variables de decisin, que consiste en definir cules son
las decisiones que se debe tomar. En el ejemplo,
x: nmero de sillas elaboradas.
y: nmero de mesas elaboradas.
13
Introduccin: Ejemplo
ii) La funcin objetivo del problema, que permita tener un
criterio para decidir entre todas las soluciones factibles. En el
ejemplo, maximizar la utilidad dada por:
z = f(x,y) = 10x + 16y
14
Introduccin: Ejemplo
iii) Restricciones del problema, que consiste en definir un conjunto de ecuaciones e inecuaciones que restringen los valores de las variables de decisin a aquellos considerados como factibles. En el ejemplo, respetar la disponibilidad de piezas para la fabricacin de sillas y mesas:
Piezas pequeas: 2x + 2y 8
Piezas grandes : x + 2y 6
Tambin se impone restricciones de no negatividad:
x 0, y 0
15
Introduccin: Ejemplo
En resumen:
Max 10x + 16y
s.a. 2x + 2y 8
x + 2y 6
x 0, y 0
Solucin ptima:
16
Introduccin
El ejemplo corresponde a un modelo de Programacin Lineal.
Si adems restringimos los valores de x e y a nmeros enteros,
tendramos un modelo de Programacin Entera.
Por otra parte, si hubiese retornos crecientes a escala,
deberamos emplear una funcin objetivo no lineal como ser
f(x,y)=cxa+dyb con a,b >1, y tendramos un modelo de
Programacin No Lineal.
17
Introduccin
Supuestos Bsicos de la Programacin Lineal:
i) Linealidad
ii) Modelos deterministas
iii) Variables reales
iv) No - negatividad
18
Introduccin
Existen numerosos programas computacionales para resolver
diversos problemas de optimizacin.
Gua de software NEOS:
http://neos.mcs.anl.gov/neos/solvers/index.html
19
Introduccin
Empleando un software de modelado algebraico (AMPL: www.ampl.com), el modelo lineal introductorio corresponde simplemente a:
var x >=0 ; # numero de sillas
var y >=0 ; # numero de mesas
maximize beneficio_total : 10*x + 16*y ;
subject to pza_peq : 2*x + 2*y
Introduccin
Descargar AMPL versin estudiantil desde www.ampl.com
21
Introduccin
Empleando Solver de EXCEL, el ejemplo introductorio corresponde simplemente a:
22
Introduccin
De donde se obtiene la siguiente solucin ptima:
23
Tambin se puede utilizar OpenSolver o WhatsBest! como alternativa a Solver de Excel.
Actividad en Clases
S. T. vende dos productos: colonia y perfume
La colonia se vende por $3000/100ml ; cada 100ml requiere
2 gramos de fragancia
6 gramos de intensificador
El perfume se vende por $8000/100ml ; cada 100ml requiere
4 gramos de fragancia
2 gramos de intensificador
1 gramo de estabilizador
S. T. tiene inventario limitado. En particular, tiene
1.600 gramos de fragancia
1.800 gramos de intensificador
350 gramos de estabilizador
S. T. debe usar sus insumos ahora! (no necesariamente a mxima capacidad)
Cul es la estrategia de produccin ptima? Cul es el ingreso asociado a esta estrategia?
24
Variables de Decisin:
Funcin Objetivo:
Restricciones:
Actividad en Clases
Problema de S.T.
-100
0
100
200
300
400
500
600
700
800
900
-100 0 100 200 300 400 500 600 700 800 900
Colonia (C) (100ml)
Perf
um
e (
P)
(100m
l)
Regin
Factible
Estabilizador
Intensificador
Fragancia
Z = 0
Z = 900
Z = 7200
Z = 3100
Solucin
Optima
Actividad en Clases
Ejercicio Propuesto
Mega-Marketing est planeando una campaa de marketing intensiva, de una
semana, para una nueva lnea de ropa. Los avisos ya han sido diseados y
producidos y ahora quieren determinar cunto dinero gastar en cada tipo de
publicidad. En la prctica Mega-Marketing tiene decenas de alternativas, pero
ilustraremos el problema suponiendo que solo hay dos opciones: tiempo prime
de televisin (24 horas de TVN) y prensa escrita (cuerpo C de El Mercurio).
La empresa quiere que su campaa tenga el mayor impacto posible y ha
establecido ciertos objetivos en trminos del nmero de avisos que espera que
cada segmento de la poblacin vea. Los estudios de mercado habituales
indican que cada minuto de TV y cada aviso escrito alcanzan a un nmero de
personas de acuerdo con la tabla siguiente:
27
Ejercicio Propuesto
28
Con esto, un aviso (de un minuto) en 24 horas de TVN es visto por 500.000 nios
(17 aos o menos), 100.000 mujeres adultas y 300.000 hombres adultos, y tiene
un costo de $1.800.000. Por otra parte el objetivo de Mega-Marketing es que al
menos 2.4 millones de nios, 1.8 millones de mujeres y 2.4 millones de hombres
vean su publicidad (si una persona determinada ve la publicidad dos o ms veces
se considera como dos o ms personas ya que estar ms propenso a comprar).
Formule y resuelva un modelo de Programacin Lineal que ayude a Mega-
Marketing a decidir su inversin en publicidad (suponga que se puede contratar
fracciones de minutos de TV o fracciones de pginas de prensa).