Semana 1 UCV

0

INVESTIGACIN OPERATIVA

y Aspectos

Lic. Mario Ninaquispe Soto

fundamentales de la Investigacin Operativa como Ciencia: y Programacin Lineal y Ejercicios: Planteamiento de Modelos de Programacin Lineal

EAP. Ingenieria de Sistemas - Lic. Mario Ninaquispe Soto

02/04/2011

La Investigacin Operativa como ciencia1

La primera actividad de la Investigacin de Operaciones (IO) se dio durante la segunda guerra mundial en Gran Bretaa, donde a un grupo de cientficos de distintas reas del saber los reunieron para que estudiaran los problemas tcticos y estratgicos asociados a la defensa del pas. El nombre de IO fue dado aparentemente por que el equipo fue dado aparentemente estaba llevando a cabo la actividad de Investigar Operaciones Militares. Motivados por los resultados, los administradores militares de Estados Unidos comenzaron a realizar investigaciones similares. Para eso reunieron a un grupo selecto de especialistas, l os cuales empezaron a tener buenos resultados en la planeacin de minas en el mar y la utilizacin efectiva del equipo electrnico.EAP. Ingenieria de Sistemas - Lic. Mario Ninaquispe Soto

02/04/2011


Al trmino de la guerra y atrados por los buenos resultados obtenidos por los estragas militares, los administradores industriales empezaron a aplicar las herramientas de la IO en la resolucin de sus problemas que empezaron a originarse debido al crecimiento en tamao y complejidad de las industrias. Los gerentes han sufrido los cambios sobre todo en lo relacionado a tecnologa y mtodos o procesos de trabajo, haciendo ms compleja la toma de decisiones, solo basta ver todo lo que implica trabajar a travs del Internet.


02/04/2011


En resumen, la IO se ocupa de la toma de decisiones ptimas y del modelo de sistemas determinanticos y probabilsticos que se originan en la vida real. Estas aplicaciones, que ocurren en el gobierno, en los negocios, en las industrias, en las ingenieras en la economa, y en las ciencias naturales y sociales, se caracterizan en gran parte por la necesidad de asignar recursos escasos. La IO adopta el mtodo cientfico como estructura para la solucin de los problemas, dando mayor nfasis al juicio objetivo que al juicio subjetivo. En su sentido ms amplio la IO, puede ser caracterizada como la aplicacin de mtodos cientficos, tcnicas cientficas e instrumentos cientficos a problemas que involucran operaciones de sistemas, de modo que provean a los tomadores de decisiones (ejecutivos) responsables de las operaciones, soluciones ptimas para los problemas.


02/04/2011


Definicin de Toma de Decisiones:Es un proceso de elegir entre diferentes Decisiones: cursos alternativos de accin para obtener metas y objetivos. Metodologa Cientfica: Como es obvio, el enfoque principal de un estudio Cientfica: de IO es la Toma de Decisiones. Es decir el resultado que derive del anlisis, debe tener consecuencias directas y no ambiguas para el tomador de decisiones. El mtodo cientfico aplicado en un proceso de IO, se inicia con la observacin cuidadosa y formulacin del problema; para luego construir un modelo cientfico que trate de abstraer la esencia del problema real. De este modelo se obtendrn las conclusiones y soluciones que tambin son vlidas para el problema real; por lo que en forma iterativa el modelo se llega a verificar con la experimentacin adecuada.


02/04/2011


Posteriormente se trata de encontrar una solucin, la mejor o la ptima, y para ello se define una medida de efectividad que considere las metas. Esta medida servir para comparar los cursos de accin alternos. Los pasos a seguir normalmente son: Construccin de un modelo que extrae los elementos del problema de decisin del mundo real. Realizar el examen y anlisis de las relaciones que determina las consecuencias de la decisin. Desarrollar una tcnica de solucin que produzca un valor ptimo basado en los objetivos del tomador de decisiones.


02/04/2011


Elementos de un proceso de decisin: Los elementos de una decisin constan de: Un tomador de decisiones (que puede ser un individuo, grupo, organizacin o la sociedad misma). Un conjunto posible de cursos de accin que pueden tomarse para resolver el problema de decisiones. Un conjunto posible de estados que pueden ocurrir. Un conjunto de consecuencias asociadas a cada curso de accin y estado posible que pueda ocurrir. La relacin entre las consecuencias y los valores del tomador de decisiones.


02/04/2011

El Proceso de la Investigacin de Operaciones7

Segn Moskowitz, define 5 pasos principales: Formulacin y definicin del problema Construccin del modelo Solucin del modelo Validacin del modelo Implementacin de resultados


02/04/2011


Fase 1: Formulacin y Definicin del problemaSe requiere: Descripcin precisa de las metas u objetivos del estudio Identificar las variables de decisin controlables y no controlables del sistema de decisin Reconocer las limitaciones o restricciones en las variables del sistema


02/04/2011


Fase 2: Construccin del ModeloSe detalla el proceso. Primero, le investigador debe decidir el modelo ms adecuado para representar el sistema. Este modelo debe especificar las relaciones cuantitativas para el objetivo y las restricciones del problema en trminos de las variables de decisin. Debe proporcionar estimados de los parmetros, obtenidos bien se a partir de daros histricos, subjetivos o formalmente estimados por medio de algn mecanismo estadstico. Se debe escoger un horizonte de tiempo. Tambin se debe determinar si el sistema es determinsticos, dependiendo de la complejidad y posibilidad de solucin de las relaciones matemticas.


02/04/2011


Fase 3: Solucin del ModeloEl modelador debe, junto a los parmetros especficos por datos histricos, tecnolgicos o prcticos, calcular o derivar una solucin matemtica. Si el modelo se acomoda a uno de los modelos matemticamente bien conocidos como el de programacin lineal, se puede obtener una solucin ptima utilizando estas tcnicas. Si por lo contrario, las relaciones matemticas del modelo son muy complejas para permitir una solucin analtica, entonces el mtodo de simulacin puede ser lo ms apropiado. En la solucin del modelo, se deben realizar anlisis de sensibilidad, para determinar el comportamiento del sistema ante cambios en las especificaciones y parmetros del sistema. Es una prctica importante, toda vez que los datos de entrada (parmetros) no necesariamente son precisos o estables y las suposiciones estructurales del modelo puede que no sean vlidas.


02/04/2011


Fase 4: Validacin del ModeloRequiere que se determinen si tal modelo puede predecir confiablemente el comportamiento del sistema. Tambin comprende la prueba de las suposiciones estructurales del modelo (variables, relaciones funcionales, etc.) para determinar su validez. Una prctica importante es comprar el desempeo del modelo actual con datos de entrada histricos. El modelo ser vlido, si bajo condicione similares de entrada, puede reproducir razonablemente el comportamiento pasado del sistema. Es importante resaltar, que no hay garanta de que el comportamiento futuro del sistema contine duplicando la historia pasada.


02/04/2011


Fase 5: ImplementacinEs importante que quieres participen en la toma de decisiones como resultado del estudio analicen el problema. De esta forma el proyecto toma validez real y no sea considerado un mero ejercicio acadmico.


02/04/2011

Modelos de Investigacin Operativa InvestigacinMODELOS DE INVESTIGACIN OPERATIVA

13

DETERMINISTICOS

PROBABILSTICOS

ESTOCSTICOS

OPTIMIZACIN NO LINEAL MTODOS CLSICOS

OPTIMIZACIN LINEAL PROGRAMACIN LIENAL TRANSPORTE Y ASIGNACIN PROGRAMACIN ENTERA Y BINARIA

PROGRAMACIN DINMICA INVENTARIOS

PROGRAMACIN ESTOCSTICA COLAS

MTODOS DE BSQUEDA PROGRAMACIN NO LINEAL

SIMULACIN

PROCESOS ESTOCSTICOS TEORA DE DECISIONES Y JUEGOS

PERT CPM

REDES

METAHEURSTICA HEURSTICA


02/04/2011

Modelo de Programacin Lineal14

CASO DE ESTUDIO.Un taller de mantenimiento fabrica dos tipos de piezas para la reparacin de equipos fundamentales del proceso productivo. Estas piezas requieren un cierto tiempo de trabajo en cada una de las tres mquinas que las procesan. Este tiempo, as como la capacidad disponible (h) y la ganancia por cada pieza se muestran en el cuadro siguiente:Mquina I II III Ganancia ($/Pieza) Tiempo por Pieza A 2 1 4 6 B 2 2 2 4 Fondo de Tiempo (h) 160 120 280

Se logra vender todo lo producido y se desea determinar la cantidad de piezas a fabricar que optimice la ganancia. Cmo lograra optimizar el sistema en estudio?EAP. Ingenieria de Sistemas - Lic. Mario Ninaquispe Soto

02/04/2011


El objetivo de la programacin lineal (PL) es optimizar (maximizar o minimizar) una funcin lineal de n variables sujeto a restricciones lineales de igualdad o desigualdad. Ms formalmente, se dice que un problema de PL consiste en encontrar el ptimo (mximo o mnimo) de una funcin lineal en un conjunto que pueda expresarse como la interseccin de un nmero finito de hiperplano semiespacios en Rn.

Caractersticas generales de los modelos de PL: PL:Una sola funcin objetivo (FO) Maximizacin o minimizacin de la FO sujeta a disponibilidad de recursos Proporcionalidad de la funcin objetivo y de las restricciones con respecto al nivel de produccin de cada artculo, etc.


02/04/2011


Si se expresan estas condiciones en forma ligeramente modificadas y se consideran ms de acuerdo con el orden en el cual se relacionan con el planteamiento del modelo, entonces es posible enunciar que un problema puede resolverse a travs de la PL si satisface los siguientes requerimientos: 1. 2. Puede plantearse un FO para el problema en trminos de variables de decisin, es decir: x1, x2, x3, x4, , xn. Las variables del problema deben estar interrelacionadas para generar el resultado total, es decir, puede dejarse de fabricar un producto (variable) para fabricar o utilizar una mayor cantidad de otro producto. Las restricciones relacionadas con la disponibilidad o uso de los recursos, la satisfaccin de los requerimientos o surtimiento de la demanda deben ser de forma lineal. Los valores de las variables en la solucin pueden ser fraccionarios, pero deben ser mayores o iguales a cero.02/04/2011

3.

4.


Modelo Matemtico de PL17

Maximizar (Minimizar) Sujeto a (s.a.):

Z ! c1 x1 c 2 x 2 c3 x3 ........ c n x n

a11 x1 a12 x 2 ........ a1n x n a 21 x1 a 22 x 2 ........ a 2 n x n a11 x1 a12 x 2 ........ a1n x n

?e, u, !A b1 ?e, u, !A b2 ?e, u, !A b1... ... ... ... ... ...

... ... ...

.... .... ....

... ... ...

a m1 x1 a m 2 x 2 ........ a mn x n x1, x 2, x3,Dondex1, x2, x3, , xn u 0

?e, u, !A bm

, xn u 0representan las variables de decisin02/04/2011



Planteamiento de Problemas: Problemas:La habilidad para transformar un problema del mundo real en un modelo de PL debidamente planteado es un arte. Al plantear los problemas, se han encontrado que los siguientes procedimientos son muy tiles: 1. Debe concentrarse en identificar la funcin objetivo general. Cul es el objetivo final del problema, maximizar utilidades, minimizar costos, minimizar las materias primas, que se requieren, maximizar el uso de la fuerza de trabajo, etc.) Debe plantearse el objetivo en forma verbal, incluyendo en la expresin la forma que el objetivo se relaciona con los diversos factores (variables de decisin) sobre las cuales tiene control quien toma las decisiones. Se debe identificar y plantear en forma verbal cada restriccin. Otros consideran en primer lugar reunir todos los datos del problema.

2.

3. 4.


02/04/2011

Modelo de Programacin LinealLuego de haber descrito el problema en forma verbal, se debe transformar las descripciones verbales en forma matemtica: 1. Identificar y definir las variables de decisiones (las xj) asociadas con el problema, incluyendo en sus unidades de medicin. 2. Identificar los coeficientes de contribucin (los cj) asociados con cada variable. 3. Plantear la funcin objetivo y verificar que existe consistencia en las unidades de medicin. 4. Identificar la tasa fsica de los coeficientes de sustitucin (los aij), incluyendo en la definicin las unidades de medicin relacionadas con el coeficiente respectivo. 5. Identificar los recursos o requerimientos disponible, es decir los coeficientes del segundo trmino (los bi), que son los valores que aparecen al lado derecho del signo igual en las ecuaciones de restriccin. 6. Plantear las restricciones relacionadas con cada uno de los respectivos recursos o requerimientos y verificar que haya consistencia en las unidades de medicin para cada restriccin. 7. Definir las condiciones de no negatividad asociadas con las variables de decisinEAP. Ingenieria de Sistemas - Lic. Mario Ninaquispe Soto

19

02/04/2011


Variables Continuas y Variables Discretas: Discretas:Los valores de las variables en la solucin pueden ser fraccionarios o continuos. No siempre es prctico en la vida real. Puede evitarse este problema en la programacin lineal redondeando los valores continuos para que sean discretos; sin embargo, esto no siempre da como resultado una solucin factible. Existen algoritmos que proporcionan valores discretos ptimos en las soluciones.


02/04/2011

Ejercicios Prcticos21

1.- Un taller de mantenimiento fabrica dos tipos de piezas para la reparacin de equipos fundamentales del proceso productivo. Estas piezas requieren un cierto tiempo de trabajo en cada una de las tres mquinas que las procesan. Este tiempo, as como la capacidad disponible (h) y la ganancia por cada pieza se muestran en el cuadro siguiente:Mquina I II III Ganancia ($/Pieza) Tiempo por Pieza A 2 1 4 6 B 2 2 2 4 Fondo de Tiempo (h) 160 120 280

Se logra vender todo lo producido y se desea determinar la cantidad de piezas a fabricar que optimice la ganancia.


02/04/2011

Formulando el modelo PPL:22

Variables: X1 : Nmero de piezas del tipo A. X2 : Nmero de piezas del tipo B. Optimizando la ganancia (Z). Max Z = 6X1 + 4X2 Sujeto a las restricciones: 2X1 + 2X2 e 160 Fondo de tiempo de la mquina 1. X1 + 2X2 e 120 Fondo de tiempo de la mquina 2. 4X1 + 2X2 e 280 Fondo de tiempo de la mquina 3. Como ninguna variable implicada puede ser negativa. X1 u 0; X2 u 0


02/04/2011

Formulando el modelo PPL:23

Formulacin completa del modelo matemtico: Max Z = 6X1 + 4X2 S.A. 2X1 + 2X2 e 160 X1 + 2X2 e 120 4X1 + 2X2 e 280 X1 u 0; X2 u 0


02/04/2011

24

2.- Una compaa fabrica tres productos de caucho: Airtex, Extendex y Resistex ; los tres requieren los mismos polmetros qumicos. La cantidad de cada ingrediente usada por libra del producto es como sigue:PRODUCTO Airtex Extendex Resistex Polmetro A 4 3 6 Polmetro B 2 2 3 Polmetro C 4 2 5 Base 6 9 2

La empresa tiene el compromiso de producir al menos 1000 libras de Airtex, 500 libras de Extendex y 400 libras de Resistex para la prxima semana, pero la gerencia sabe que puede vender ms de cada producto. Los inventarios actuales de los ingredientes son 500 libras del Polmetro A, 425 libras del polmetro B, 650 libras del polmetro C y 1100 libras de la base. Cada libra de Airtex produce a la compaa una ganancia de $7, cada libra de Extendex produce una ganancia de $7 y cada libra de Resistex una ganancia de $6. Determine un plan ptimo de produccin para esta semana.EAP. Ingenieria de Sistemas - Lic. Mario Ninaquispe Soto

02/04/2011

Formulando el modelo:25

Variables: A = N libras de Airtex por producir esta semana E = N libras de Extendex por producir esta semana R= N libras de Resistex por producir esta semana Optimizando la ganancia (Z). Max Z = 7A+7E+6R Sujeto a las restricciones: Restricciones de Recursos: Cantidad empleada del Polmetro A 500 4A+3E+6R e 500 Cantidad empleada del Polmetro B 425 2A+2E+3R e 425 Cantidad empleada del Polmetro C 650 4A+2E+5R e 650 Cantidad empleada del Polmetro de la Base 1100 6A+9E+2R e 1100EAP. Ingenieria de Sistemas - Lic. Mario Ninaquispe Soto

02/04/2011

26

Restricciones de Demanda: A u 1000 (Airtex) E u 500 (Extendex) R u 400 (Resistex) Restricciones lgicas: como ninguna variable implicada puede ser negativa: A u 0; E u 0, Ru 0


02/04/2011

Formulacin completa del modelo matemtico:27

Max Z = 7A+7E+6R S.A. 4A + 2A + 4A + 6A + A

3E 2E 2E 9E E

+ + + +

6R e 500 3R e 425 5R e 650 2R e 1100 1000 u u 500 R u 400

A u 0; E u 0, Ru 0


02/04/2011

28

3.- El taller de Joe se especializa en cambios de aceite del motor y regulacin del sistema elctrico. El beneficio por cambio del aceite es $7 y de $15 por regulacin. Joe tiene un cliente fijo con cuya flota, le garantiza 30 cambios de aceite por semana. Cada cambio de aceite requiere de 20 minutos de trabajo y $8 de insumos. Una regulacin toma una hora de trabajo y gasta $15 en insumos. Joe paga a los mecnicos $10 por hora de trabajo y emplea actualmente a dos de ellos, cada uno de los cuales labora 40 horas por semana. Las compras de insumos alcanzan un valor de $1,750 semanales. Joe desea maximizar el beneficio total. Formule el problema


02/04/2011

29

4.- El departamento de nutricin de un Hospital prepara 30 mens de cena, uno para cada da del mes. Una comida consiste en espagueti, pavo, papas, espinacas y pastel de manzana. Como Director de Nutricin, se ha determinado que esta comida debe proporcionar 63,000 miligramos (mg) de protenas, 10mg de hierro, 15 mg de niacina, 1mg de tiamina y 50 mg. de vitamina C. Cada 100 gramos de esta comida proporciona la cantidad de cada nutriente y grasas indicadas en la siguiente tabla:COMIDASEspagueti Pavo Papas Espinacas Pastel de manzana

Nutrientes mg/100g PROTENAS HIERRO NIACINA5,000 29,300 5,300 3,000 4,000 63,000 1.1 1. 0.5 2.2 1.2 10 1.4 5.4 0.9 0.5 0.6 15

TIAMINA0.1 0.06 0.06 0.0 0.15 1

VITAMINA C 0.0 0.0 10.0 2 .0 3.0 50

GRASA5,000 5,000 ,900 3,000 14,300 300gr 300gr 200gr 100gr 100

Para evitar demasiada cantidad de un tipo de comida, no debe incluirse en ella ms de 300 gr de espagueti, 300 gr de pavo, 200 gr. de papas, 100 gr. de espinaca, y 100 gr. de pastel de manzana. Se desea determinar la composicin de una comida que satisfaga los requerimientos nutricionales y proporcione la mnima cantidad de grasas.EAP. Ingenieria de Sistemas - Lic. Mario Ninaquispe Soto

02/04/2011

30

Muchas gracias

!Lic. Mario Ninaquispe Soto02/04/2011

Documents

Semana 1 UCV