Embed Size (px)
Citation preview
PROGRAMA DE ESTUDIO
CONTENIDO Reseña histórica de la I.O. Definición de la I.O Características de la I.O Fases de un estudio de I.O Limitaciones de la I.O Áreas de aplicación de la I.O en la gerencia. Técnicas utilizadas en la I.O
Definición de la Programación Lineal. P.L.
Aplicaciones gerenciales y formulación de problemas de P.L
Métodos de resolución: Método gráfico. Método simplex. Método de solución por computadora.
• BIBLIOGRAFIA
• Hillier, Frederick y Lieberman, Gerald: “Introducción a la Investigación de Operaciones”, McGraw – Hill Interamericana
• Hamdy Taha: “Investigación de Operaciones”. Ed. AlfaOmega.
Programa de Estudio
Objetivo
Familiarizar al alumno con las técnicas de modelamiento y metodologías de
resolución de problemas de la Investigación de operaciones, con especial énfasis en
la aplicación de algoritmos de solución para modelos de programación matemática,
en especial modelos lineales .
Toma de Decisiones
Toda toma de decisión empieza con la detección de un problema.
Definir el problema en forma clara
Identificar las restricciones
Identificar las alternativas de solución
Formular el o los objetivos
Evaluar las alternativas y elegir la mejor
Para tomar la decisión correcta, se debe:
FASES DE UN ESTUDIO DE INVESTIGACION DE OPERACIONES
1. Definición del problema y recolección de datos relevantes: Implica establecer el alcance de problema que se está investigando. Se deben identificar tres elementos de decisión del problema: (a) la descripción de las alternativas de decisión, (b) la determinación del problema y (c) la especificación de las limitantes bajo las cuales opera el sistema que se modela.
2. Formulación de un modelo matemático que describa el problema: implica traducir la definición del problema a relaciones matemáticas.
3. Obtención de soluciones a partir del modelo: implica el empleo de algoritmos de optimización definidos para encontrar soluciones factibles al modelo.
4. Prueba o validación del modelo y mejoramiento (análisis de sensibilidad): verifica que el modelo propuesta haga lo que se supone que debe hacer. También se puede recurrir al análisis de sensibilidad para probar la solución óptima encontrada a partir de variaciones en los parámetros originales del modelo.
5. Preparación para aplicar el modelo: implica establecer y documentar los procedimientos (de solución, análisis pos óptimo, operativos) que permitan llevar el modelo a un sistema de uso cotidiano según los requerimientos de la administración.
6. Implementación: requiere la traducción de la solución del modelo validado a instrucciones de operación, impartidas de forma que sea comprensible para los individuos que administran el sistema.
¿Como se elige la mejor alternativa?¿Como se elige la mejor alternativa?
Métodos Cualitativos
Métodos Cuantitativos
En base a la experiencia y al juicio profesional de la persona que toma la decisión
En base a la utilización de herramientas matemáticas que permitan maximizar la efectividad en la toma de decisiones.
Toma de Decisiones
La dificultad de tomar decisiones ha hecho que el hombre se aboque en la búsqueda de una herramienta o método que le permita tomar las mejores decisiones de acuerdo a los recursos disponibles y a los objetivos que persigue.
Este conjunto de herramientas o métodos es lo que llamaremos Investigación de Operaciones.
“Enfoque científico de la toma de decisiones que requiere la operación de sistemas organizacionales”.
Definición más formal
La IO nos ofrece una serie de herramientas cuantitativas para la toma de decisiones.
La IO nos ofrece una serie de herramientas cuantitativas para la toma de decisiones.
Investigación de Operaciones
Un poco de Historia
●La investigación de operaciones se aplica a casi todos los problemas.
●En 1947, en E.U., George Datzing encuentra el método SIMPLEX para el problema de programación lineal.
●Se inicia desde la revolución industrial, usualmente se dice que fue a partir de la segunda Guerra Mundial.
En 1947, el matemático George Dantzig desarrolla un algoritmo para la solución eficiente de problemas de programación lineal, esta herramienta se conoce como el método simplex. Su implementación inicial se registra en el ordenador UNIVAC para la solución de problemas lineales grandes.
INVESTIGACION DE OPERACIONES
La Investigación de Operaciones (IO) es una rama de las matemáticas que emplea modelos matemáticos y algoritmos con el objetivo de sustentar el proceso de toma de decisión, cuyas mayores aplicaciones se encuentran dentro de la industria y los negocios a través de la Ingeniería Industrial.
La IO permite de manera sistemática obtener soluciones más eficientes, ya sea para lograr mayores beneficios, ahorros en la utilización del tiempo y/o recursos, u obtener menores costos, que los que se obtendrían si las decisiones se toman por intuición o basados simplemente en consideraciones particulares sin previo análisis.
La Investigación de Operaciones se aplica a problemas que se refieren a la coordinación eficiente de las operaciones o actividades dentro de una organización. Las herramientas de IO se aplican generalmente en los negocios, la industria, la milicia, el gobierno, los hospitales, etc., alrededor del mundo se visualizan muchas organizaciones que establecen grupos de Investigación de Operaciones para mejorar sus desempeños obteniendo muy buenos resultados y/o ahorros sustanciales.
Las aplicaciones de la IO se encuentran en las industrias, que incluye la aérea, automotriz, de comunicaciones, computación, energía eléctrica, electrónica, alimenticia, metalúrgica, minera, del papel, del petróleo y del transporte. También han encontrado un sinnúmero de aplicaciones en el sector servicio, como las instituciones financieras y hospitales, a través de las evaluaciones del nivel de servicio requerido por medio de las teorías de colas.
Para la aplicación de la IO se siguen los siguientes pasos:
Investigación de Operaciones
La IO comienza con la observación cuidadosa de la realidad.
Formular el problema.
Construir un modelo que intente abstraer la esencia del problema real.
Solución del modelo.
Análisis de sensibilidad, hay que ver como se comporta el modelo ante cambios en las restricciones y/o parámetros del modelo.
Implementar los resultados, se debe interpretar los resultados y dar conclusiones y cursos de acción para la optimización del problema real
La Programación Lineal es una herramienta para resolver problemas de optimización que se caracterizan por tener como función objetivo y restricciones combinaciones lineales de las variables de decisión.
FO: Max o Min Z = C XSujeto a A X B Xj 0 ; j = 1, 2,...., n
Conceptos Básicos:
Programación Lineal
Variables de Decisión Función Objetivo Restricciones Restricciones de Signo
Consideremos el siguiente ejemplo para describir los conceptos básicos presentes en todo problema de programación lineal (PPL)
Programación Lineal
1.- Una mueblería produce mesas y sillas de madera. Cada mesa es vendida en $27.000 y se requiere $10.000 en materiales para su construcción, además, el costo unitario por mano de obra es de $14.000. En el caso de las sillas, el precio de venta es de $21.000 y los costos de materiales y mano de obra son $9.000 y $10.000 respectivamente.
La fabricación de cada producto requiere de dos labores: carpintería y terminaciones. Una mesa requiere de 1 hora de carpintería y 2 de terminaciones, mientras que la silla requiere de 1 hora en cada labor
Cada semana, la mueblería puede obtener todos los materiales que desee, sin embargo, se pueden dedicar hasta 100 horas a las terminaciones y hasta 80 horas a la carpintería. La demanda por mesas no está limitada, mientras que la demanda por sillas es de 40 unidades.
Formule un modelo matemático que permita maximizar las utilidades de la mueblería.
Variables de decisión: Variables de decisión:
Programación Lineal
Se debe comenzar definiendo las variables de decisión relevantes. En un PPL las variables de decisión deben ser capaces de describir completamente las decisiones que puedan ser tomadas y todas las variantes que existan
X1 = Número de mesas producidas por semana.X2 = Número de sillas producidas por semana.
X1 = Número de mesas producidas por semana.X2 = Número de sillas producidas por semana.
Programación Lineal
Antes de definir las variables de decisión es importante definir las unidades involucradas en el problema.
En este caso, se habla de unidades de sillas y mesas, de horas de trabajo por unidad y de demanda semanal. De acuerdo a ello, una buena opción para definir las variables de decisión consiste en asociar las variables al número de unidades de sillas y mesas a producir por semana. Por lo tanto, podemos definir:
Función Objetivo: Función Objetivo:
En un PPL, se debe tomar la decisión de maximizar (usualmente las utilidades) o de minimizar (usualmente los costos) cierta función de las variables de decisión.
En el ejemplo, los costos e ingresos no dependen del valor de X1 o X2 por lo tanto basta concentrarse en maximizar la diferencia entre:
La función que se va a optimizar se llama Función Objetivo (FO) y en ella no aparece ningún término independiente o constante. Los valores de las variables de decisión son independientes de cualquier constante.
Ingresos Semanales – Costos de Materiales – Costos por mano de obraIngresos Semanales – Costos de Materiales – Costos por mano de obra
Programación Lineal
Luego se deben expresar los términos anteriores en función de las variables de decisión X1 y X2.
Por lo que la función objetivo queda (expresada en miles de $):
(27X1 + 21X2) – (10X1 + 9X2) – (14X1 + 10X2) = 3X1 + 2X2 (27X1 + 21X2) – (10X1 + 9X2) – (14X1 + 10X2) = 3X1 + 2X2
Así, el objetivo de la mueblería es escoger los valores X1 y X2 tal que se maximice 3X1 + 2X2
Denotando por Z el valor de la FO para cualquier PPL, la función de la mueblería es:
Max Z = 3X1 + 2X2 Max Z = 3X1 + 2X2
El coeficiente que acompaña a cada variable en la FO se denomina coeficiente en la función objetivo de la variable y refleja el aporte unitario de dicha variable a la función objetivo
Programación Lineal
Restricciones: Restricciones:
En las medidas que las variables crecen, la FO aumenta su valor. Por lo tanto si se pudiera escoger arbitrariamente el valor de la variables, la mueblería podría hacer crecer el valor de sus utilidades en forma infinita. En la práctica esto no es posible y en el ejemplo el valor que toman las variables está limitado por las siguientes 3 restricciones:
Luego, el próximo paso consiste en formular matemáticamente las restricciones anteriores en función de las variables de decisión.
Programación Lineal
Máximo 100 horas semanales para terminaciones. Máximo 80 horas semanales para carpintería. Producción máxima de 40 sillas semanales.
Para formular la primera restricción en función de las variables X1 y X2 observamos que:
Hrs. terminaciones x mesa + hrs. terminaciones x silla hrs. disponibles para terminaciónHrs. terminaciones x mesa + hrs. terminaciones x silla hrs. disponibles para terminación
Por lo que la restricción queda:
2X1 + X2 1002X1 + X2 100
Es importante notar que todos los valores en la expresión anterior son por semana, ya que las variables de decisión se han escogido con esa referencia.
Programación Lineal
Análogamente la segunda restricción queda:
X1 + X2 80X1 + X2 80
Finalmente, la tercera restricción sólo limita el valor de la variable X2
X2 40X2 40
Restricciones de Signo: Restricciones de Signo:
Xi 0Xi 0
Programación Lineal
Para completar la formulación del modelo es importante definir si existe alguna restricción de signo para cada variable de decisión.
Si una variable de decisión Xi debe cumplir condiciones de NO NEGATIVIDAD, debemos agregar la siguiente restricción:
Combinando todas las expresiones anteriores, es posible completar el modelo matemático para este problema de optimización, quedando de la siguiente forma:
En el ejemplo ambas variables de decisión se refieren a cantidades a producir, por lo tanto son no negativas. Sin embargo, en otros ejemplos las variables pueden ser SRS, por ejemplo en el caso de que Xi se refiere al saldo de alguna cuenta.
Programación Lineal
Si la variable de decisión Xi puede asumir valores positivos o negativos se dice que Xi no tiene restricción de signo (SRS).
Definición de variables:
X1: número de mesas producidas por semana.X2: número de sillas producidas por semana.
F.O:
Max Z = 3X1 + 2X2
S a:
2X1 + X2 100 Horas disponibles para terminaciones por semana
X1 + X2 80 Horas disponibles para carpintería por semana
X2 40 Producción máxima de sillas por semana
Xj 0 j = 1 y 2 No negatividad
Programación Lineal
Dado un conjunto de m desigualdades o ecuaciones lineales, con n variables, se requiere hallar valores de estas variables que satisfagan las restricciones y maximicen o minimicen alguna función lineal de las variables
Generalización:
FO: Max o Min Z = C XSujeto a A X B Xj 0 ; j = 1, 2,...., n
FO: Max o Min Z = C XSujeto a A X B Xj 0 ; j = 1, 2,...., n
Programación Lineal
Matemáticamente
Max o Min Z = C1 X1 + C2 X2 +...+ Cn XnMax o Min Z = C1 X1 + C2 X2 +...+ Cn Xn
Sujeto a
a11 X1 +...+ a1j Xj +...+ a1n Xn ó b1
. . . . . .ai1 X1 +...+ aij Xj +...+ ain Xn ó bi
. . .
. . .am1 X1 +...+ amj Xj +...+ amn Xn ó bm
Xj 0 j = 1, 2,..., n
a11 X1 +...+ a1j Xj +...+ a1n Xn ó b1
. . . . . .ai1 X1 +...+ aij Xj +...+ ain Xn ó bi
. . .
. . .am1 X1 +...+ amj Xj +...+ amn Xn ó bm
Xj 0 j = 1, 2,..., n
Hallar Xj ; j = 1, 2,..., n
Para
Programación Lineal
1.- Una función f(X1, X2, ..., Xn) de X1, X2, ..., Xn es una función lineal sí y sólo sí para un conjunto de constante C1, C2, ..., Cn se tiene:
X 1 X 2 X 32 a14 log X 4
2.- Asume las propiedades aditivas y multiplicativas
Linealidad asume que no pueden haber términos del siguiente tipo:
f(X1, X2, ..., Xn) = C1X1 + C2X2 + ... + CnXnf(X1, X2, ..., Xn) = C1X1 + C2X2 + ... + CnXn
Características de la PL
Si una unidad tipo 1 necesita 2 horas en la máquina A y una unidad tipo 2 necesita 3 horas, entonces ambas necesitan 5 horas. Si una unidad tipo 3 necesita 1 hora en la máquina B, entonces 5 unidades necesitan 5 horas
4.- Los valores de las variables de decisión deben satisfacer un conjunto de restricciones. Cada restricción debe ser una ecuación o desigualdad lineal.
5.- Existe una restricción de signo asociada a cada variable. Para toda variable Xi la restricción de signo especifica si Xi debe ser no negativa o bien sin restricción de signo.
6.- En las m restricciones no deben considerarse las condiciones de no negatividad de las variables (Xj 0)
3.- La función que se va a optimizar se llama Función Objetivo y en ella no aparece ningún término independiente o constante. Los valores de las Xj son independientes de cualquier constante
Características de la PL
8.- Supuesto de Certeza: exige que cada parámetro, es decir, coeficientes de la función objetivo, coeficientes del lado derecho de las restricciones, etc. sean conocidos con certeza, es decir, no se acepta incertidumbre en sus valores
7.- Supuesto de Divisibilidad, requiere que cada variable puede tomar valores fraccionarios. En el ejemplo anterior, el supuesto se traduce en que es aceptable producir 2,4 sillas o 1,6 mesas. Evidentemente este supuesto no es válido en el ejemplo, en este caso se puede proceder a formular el problema como un problema de programación lineal entera (PPE), problema en que una o más variables deben ser enteras. Cuando no se satisface el supuesto de divisibilidad, una posibilidad es redondear la solución obtenida a un valor entero, sin embargo, no existe garantías que dicha solución sea la mejor.
Características de la PL
Regiones Factibles y Soluciones Óptimas
Dos de los conceptos más fundamentales en los PPL son el de región factible y de solución óptima de un problema. Llamaremos punto a la especificación de un valor para cada variable de decisión.
La región factible para un PPL es el conjunto de puntos que satisfacen todas las restricciones (incluidas las de signo) del problema.
En el caso de un problema de maximización, una solución óptima del PPL es un punto de la región factible que está asociado al mayor valor posible de la función objetivo. Similarmente, para un problema de minimización, una solución óptima es un punto que está asociado al menor valor.
Características de la PL
Cualquier conjunto Xj que satisface las restricciones se llama “solución al problema”. Si satisface la condición de no negatividad se llama “solución factible” y si además optimiza la función objetivo se llama “solución factible óptima”
Usualmente hay un número infinito de soluciones factibles al problema, de todas estas se tiene que tratar de hallar, en lo posible,
una óptima.
Usualmente hay un número infinito de soluciones factibles al problema, de todas estas se tiene que tratar de hallar, en lo posible,
una óptima.
Características de la PL
MÉTODO GRÁFICO
El gráfico es un método de solución de problemas de programación lineal muy limitado en cuanto al número de variables (2 si es un gráfico 2D y 3 si es 3D) pero muy rico en materia de interpretación de resultados e incluso análisis de sensibilidad. Este consiste en representar cada una de las restricciones y encontrar en la medida de lo posible el polígono (poliedro) factible, comúnmente llamado el conjunto solución o región factible, en el cual por razones trigonométricas en uno de sus vértices se encuentra la mejor respuesta (solución óptima).
La fábrica de Hilados y Tejidos "SALAZAR" requiere fabricar dos tejidos de calidad diferente T y T’; se dispone de 500 Kg de hilo a, 300 Kg de hilo b y 108 Kg de hilo c. Para obtener un metro de T diariamente se necesitan 125 gr de a, 150 gr de b y 72 gr de c; para producir un metro de T’ por día se necesitan 200 gr de a, 100 gr de b y 27 gr de c.
El T se vende a $4000 el metro y el T’ se vende a $5000 el metro. Si se debe obtener el máximo beneficio, ¿cuántos metros de T y T’ se deben fabricar?
EL PROBLEMA
VARIABLES
XT: Cantidad de metros diarios de tejido tipo T a fabricar XT’: Cantidad de metros diarios de tejido tipo T’ a fabricar
RESTRICCIONES
0,12XT + 0,2XT’ <= 500 Hilo “a”0,15XT + 0,1XT’ <= 300 Hilo “b”0,072XT + 0,027XT’ <= 108 Hilo “c”
Las restricciones de no negatividad no son necesarias en este ejemplo dado que se trata de un ejercicio de maximización, cuando el ejercicio sea de minimización lo más recomendado es incluirlas.
FUNCIÓN OBJETIVO
ZMAX = 4000XT + 5000XT’
LA SOLUCIÓN MEDIANTE MÉTODO GRÁFICO
PASO 1: GRAFICAR LAS RESTRICCIONESPara iniciar con el trazado de las restricciones es indispensable igualar las restricciones a 0, de esta manera podemos mediante despeje de ecuaciones iniciar con la tabulación que nos otorgará las coordenadas para esbozar cada una de las gráficas. Además dado que se trabajará en el plano cartesiano sería prudente renombrar las variables
XT = xXT' = y
Igualamos las restricciones,
0,12X + 0,2y = 500 0,15X + 0,1y = 300 0,072X + 0,027y = 108
Acto seguido iniciamos con la primera restricción, hallamos las primeras dos coordenadas. Para hallar las coordenadas regularmente llevamos una de las variables a cero, para de esta manera despejar más fácilmente la segunda.
Por ejemplo, para un x = 0 0,12(0) + 0,2y = 5000,2y = 500500/0,2 = y2500 = y
y para un y = 0 0,12x + 0,2(0) = 5000,12x = 500x = 500/0,12x = 4167
Seguimos con la segunda restricción0.15 x+ 0.1y= 300
tercera restricción,
0,072X + 0,027y = 108
En el siguiente gráfico se muestra el polígono solución de color gris, en este conjunto es donde cada coordenada cumple con todas las restricciones, las cuales se caracterizan por ser restricciones de menor o igual y esta característica se representa con una flecha hacía abajo.
