UNIVERSIDAD PRIVADA TELESUPINGENIERIA DE SISTEMAS E INFORMATICA

WINQSB

CURSO: INVESTIGACION OPERATIVA IICICLO:VIPROFESOR:ALEJANDRO CHAMBERGO GARCIAALUMNOS : ALFREDO JOSE REYES VARGASMANUEL JOSE SANCHEZ RODRIGUEZ

Mayo 2013

Agradecemos a nuestras familias el apoyo incondicional que nos brindan para alcanzar nuestros objetivos.

INDICE

RESUMEN5SUMMARY6INTRODUCCION7ANTECEDENTES8HISTORIA DE LA PROGRAMACION LINEAL8Uso de software en la programacin lineal10Microsoft Excel10Geogebra11La calculadora grfica PL (v 1.0)11WINQSB14QUE HACE ESTE SOFTWARE?14PARA QU SIRVE EL APLICATIVO?14QUE MDULOS TIENE?14VISTA DEL SOFTWARE WINQSB18APLICACIN DEL WINQSB21Problema de transporte21EL PROBLEMA21INGRESANDO A NETWORK MODELING22Mtodos heursticos26Mtodo de Aproximacin de Vogel28Mtodo del Costo Mnimo29Mtodo de la Esquina Noroeste30PROBLEMAS PARA UTILIZAR EL WINQSB31DONDE UBICAR EL SOFTWARE31EJERCICIOS RESUELTOS CON WINQSB32PROGRAMACIN LINEAL32TRANSPORTE34ASIGNACIN36TEORIA DE COLAS37MATRIZ DE PAGOS39RBOL DE DECISIN41CONTROL DE INVENTARIOS43PERT45CPM48ANALISIS DE MARKOV51TEORIA DE JUEGOS52CONCLUSIONES53FUENTES DE INFORMACION54Referencias bibliogrficas54Referencias electrnicas54ANEXOS55ANEXO N 1. HISTORIA DE PROGRAMACION LINEAL55ANEXO N 2. Interface Geogebra56ANEXO N 3. Biblioteca de clases57ANEXO N 4. TIPOS DE ALMACENES58

RESUMEN

WinQSB es un sistema interactivo de ayuda a la toma de decisiones que contiene herramientas muy tiles para resolver distintos tipos de problemas en el campo de la investigacin operativa. El sistema est formado por distintos mdulos, uno para cada tipo de modelo o problema. Entre ellos destacaremos los siguientes:

Linear programming (LP) and integer linear programming (ILP): este mdulo incluye los programas necesarios para resolver el problema de programacin lineal grficamente o utilizando el algoritmo del Simplex; tambin permite resolver los problemas de programacin lineal entera utilizando el procedimiento de Ramificacin y Acotacin (Branch&Bound).

Linear goal programming (GP) and integer linear goal programming (IGP): resuelve modelos de programacin multiobjetivo con restricciones lineales.

Quadratic programming (QP) and integer quadratic programming (IQP): resuelve el problema de programacin cuadrtica, es decir, problemas con funcin objetivo cuadrtica y restricciones lineales. Utiliza un mtodo Simplex adaptado. Los modelos de IQP los resuelve utilizando algoritmos de ramificacin y acotacin.

Network modeling (NET): incluye programas especficos para resolver el problema del transbordo, el problema del transporte, el de asignacin, el problema del camino ms corto, flujo mximo, rbol generador, y problema del agente viajero.

Nonlinear programming (NLP): permite resolver problemas no lineales irrestringidos utilizando mtodos de bsqueda lineal, y problemas no lineales con restricciones utilizando el mtodo SUMT (funcin objetivo con penalizaciones sobre el incumplimiento de las restricciones).

PERT/CPM: mdulo de gestin de proyectos en los que hay que realizar varias actividades con relaciones de precedencia.

SUMMARY

WinQSB is an interactive aid to decision-making that contains powerful tools to solve different types of problems in the field of operations research. The system consists of several modules, one for each model type or problem. Among them we highlight the following: Linear programming (LP) and integer linear programming (ILP): This module includes the programs needed to solve the linear programming problem graphically or using the Simplex algorithm and also allows solving integer linear programming problems using the method of branch and dimension (Branch & Bound). Linear goal programming (GP) and integer linear goal programming (IGP): solve multiobjective programming models with linear constraints. Quadratic programming (QP) and integer quadratic programming (IQP) solves the quadratic programming problem, ie, problems with quadratic objective function and linear constraints. Use Simplex method adapted. IQP models solved using the branch and bound algorithms. Network modeling (NET) includes specific programs to solve the problem of the transfer, the transportation problem, the assignment, the problem of shortest path, maximum flow, spanning tree, and traveling salesman problem. Nonlinear programming (NLP) can solve nonlinear problems irrestringidos search methods using linear and nonlinear problems with constraints using the method SUMT (objective function with penalties for failure to comply with restrictions). PERT / CPM: Project management module in which you have to perform various activities with precedence relationships.

INTRODUCCION

La toma de decisiones en los distintos niveles de las organizaciones cada vez es de mayor complejidad, dadas las crecientes restricciones de disponibilidad de todo tipo de recursos. Las acadmicos se han preocupado de investigar y proporcionar herramientas que faciliten a los gerentes el abordaje de estos procesos, teniendo en cuenta que no es recomendable asumir un curso de accin confiados nicamente en la intuicin. La llamada administracin cientfica aboga por el uso de los mtodos cuantitativos en la toma de decisiones empresariales; de ah que en los planes de estudio correspondientes a la formacin de profesionales de ingeniera industrial, la administracin en sus diferentes matices, las finanzas y muchas ms disciplinas, figuren asignaturas que pretendan que los egresados de estas titulaciones se apropien de un cmulo de herramientas que les facilite el anlisis y la toma de decisiones en situaciones complejas. Con la popularizacin de los computadores personales (PC's) han surgido programas y aplicaciones muy completas para el tratamiento de los problemas de gestin mediante herramientas cuantitativas, las que en su conjunto constituyen los mtodos de la investigacin de operaciones.

QSB (Quantitative System Business), podra decirse que es el software ms utilizado en la actualidad por estudiantes de pregrados y postgrados que incluyen en su plan de estudios asignaturas como la investigacin de operaciones o temas relacionados. Sin embargo no existe en nuestro medio una gua en espaol para el docente y el estudiante, que permita el aprovechamiento mximo de los mdulos que contempla la aplicacin.

La presente monografa tiene como finalidad el comprender el desarrollo y evolucin del WINQSB.

ANTECEDENTES

HISTORIA DE LA PROGRAMACION LINEALEl problema de la resolucin de un sistema lineal de inecuaciones se remonta, al menos, a Fourier, despus de quien nace el mtodo de eliminacin de Fourier-Motzkin. La programacin lineal se plantea como un modelo matemtico desarrollado durante la Segunda Guerra Mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejrcito y aumentar las prdidas del enemigo. Se mantuvo en secreto hasta 1947. En la posguerra, muchas industrias lo usaron en su planificacin diaria.Los fundadores de la tcnica son George Dantzig, quien public el algoritmo simplex, en 1947, John von Neumann, que desarroll la teora de la dualidad en el mismo ao, y Leonid Kantorvich, un matemtico ruso, que utiliza tcnicas similares en la economa antes de Dantzig y gan el premio Nobel en economa en 1975. En 1979, otro matemtico ruso, Leonid Khachiyan, demostr que el problema de la programacin lineal era resoluble en tiempo polinomial. Ms tarde, en 1984, Narendra Karmarkar introduce un nuevo mtodo del punto interior para resolver problemas de programacin lineal, lo que constituira un enorme avance en los principios tericos y prcticos en el rea.

El ejemplo original de Dantzig de la bsqueda de la mejor asignacin de 70 personas a 70 puestos de trabajo es un ejemplo de la utilidad de la programacin lineal. La potencia de computacin necesaria para examinar todas las permutaciones a fin de seleccionar la mejor asignacin es inmensa; el nmero de posibles configuraciones excede al nmero de partculas en el universo. Sin embargo, toma slo un momento encontrar la solucin ptima mediante el planteamiento del problema como una programacin lineal y la aplicacin del algoritmo simplex. La teora de la programacin lineal reduce drsticamente el nmero de posibles soluciones ptimas que debern ser revisadas.

La programacin lineal constituye un importante campo de la optimizacin por varias razones, muchos problemas prcticos de la investigacin de operaciones pueden plantearse como problemas de programacin lineal. Algunos casos especiales de programacin lineal, tales como los problemas de flujo de redes y problemas de flujo de mercancas se consideraron en el desarrollo de las matemticas lo suficientemente importantes como para generar por si mismos mucha investigacin sobre algoritmos especializados en su solucin. Una serie de algoritmos diseados para resolver otros tipos de problemas de optimizacin constituyen casos particulares de la ms amplia tcnica de la programacin lineal. Histricamente, las ideas de programacin lineal han inspirado muchos de los conceptos centrales de la teora de optimizacin tales como la dualidad, la descomposicin y la importancia de la convexidad y sus generalizaciones. Del mismo modo, la programacin lineal es muy usada en la microeconoma y la administracin de empresas, ya sea para aumentar al mximo los ingresos o reducir al mnimo los costos de un sistema de produccin. Algunos ejemplos son la mezcla de alimentos, la gestin de inventarios, la cartera y la gestin de las finanzas, la asignacin de recursos humanos y recursos de mquinas, la planificacin de campaas de publicidad, etc.

Uso de software en la programacin lineal Existen muchas herramientas y materiales didcticos disponibles para ser utilizadas en el tema de la programacin lineal de Bachillerato de Ciencias Sociales. Sin pretender ser exhaustivos, vamos a repasar las caractersticas de algunos de ellos.El software a disposicin de los institutos, profesores y alumnos, puede clasificarse de muchas maneras. Una clasificacin til es la que divide los programas disponibles en programas de propsito general y programas de propsito especfico. Con la vista puesta en el aprendizaje de algn punto del currculo, podemos considerar comosoftware de propsito especficoaquel que est especialmente diseado para ser utilizado en un nico momento del itinerario curricular (por ejemplo, en el tema de la programacin lineal); el software de propsito general sera aquel que puede ser utilizado dentro de los lmites de una unidad didctica, pero que puede ser reutilizado en el aprendizaje de otros temas.Por lo general, el software de propsito general requerir, tanto para el alumno como para el profesor, un aprendizaje previo para interactuar con el programa, que es un coste adicional al que supone la interaccin con la mquina, mientras que el de propsito especfico, puesto que en general tendr una funcionalidad restringida, requerir un aprendizaje menor, o incluso ningn aprendizaje previo.

Microsoft ExcelCon esta distincinin mente, y con esta caracterizacin de cada uno de los tipos de software, podemos citar como software de propsito general la hoja de clculo de Microsoft, Excel, que cuenta con un complemento denominado Solver, que permite calcular la solucin al problema de programacin lineal general (utilizando diversos algoritmos); y, por supuesto, programas de geometra dinmica como Geogebra, que pueden ser utilizados para resolver problemas de programacin en dimensin n = 2.

La hoja de clculo Excel, que tiene grandes ventajas para cubrir diferentes puntos del currculo de matemticas en distintos niveles de la enseanza, resulta algo alambicada cuando se quiere aplicar a la programacin lineal de segundo de Bachillerato de Ciencias Sociales. Aparte, por supuesto, de la desventaja que supone el hecho de que Excel no es un software gratuito (y que, por consiguiente, no se puede esperar que los alumnos puedan usarlo fuera del mbito escolar, si es que la escuela posee licencia de uso), su uso requiere un aprendizaje previo del manejo de la hoja de clculo y, si ya se tiene, del complemento que sirve para resolver este tipo de problemas. Existen experiencias documentadas del uso de Excel como herramienta tecnolgica para explicar la programacin lineal, con resultados prometedores para muchos docentes que han seguido la prueba y pueden ser tambin camino de esperanza para otros compaeros, segn los autores.

GeogebraAl contrario que Excel, Geogebra es gratuito y est disponible en red, de modo que no es necesario instalarlo en los equipos antes de que se vaya a utilizar. En relacin al tema de la programacin lineal, puede emplearse para calcular las soluciones de un problema en dimensin n = 2, pero es necesaria cierta inversin de tiempo en aprender a manejar el programa. Permite cierto grado de andamiaje para calcular la solucin de problemas concretos (en el sentido de que Geogebra realiza parte de los clculos algebraicos necesarios para llegar a ella), pero no dispone de objetos especficos para programacin lineal, de manera que el estudiante que utilice directamente el programa como apoyo en sus clculos debe dominar ya la tcnica de resolucin grfica (y no puede, por tanto, ser utilizado como andamio para actividades ms conceptuales para aquellos alumnos que no dominan dicha tcnica suficientemente).

La calculadora grfica PL (v 1.0)PL es un prototipo de calculadora grfica y algebraica pensada para resolver problemas de programacin lineal en dimensin 2.Est disponible en la siguiente direccin web:http://www.perfectea.es/PL/PL.htm

y tiene licencia Creative Commons (Reconocimiento, Compartir igual). El prototipo acepta regiones factibles definidas con un nmero de inecuaciones menor o igual a tres, y calcula el mximo o el mnimo de la correspondiente funcin objetivo grficamente, detallando tambin las caractersticas de la regin factible y el conjunto solucin, cuando existe, tanto grfica como analticamente (explicitando las causas de la inexistencia de soluciones en cada caso correspondiente).Los siguientes ejemplos grficos muestran distintos tipos de situaciones que, normalmente, quedan fuera del estudio que se hace en las aulas, debido a que la regin factible presenta anomalas. (Y en todo caso, recomendamos utilizar la herramienta para comprobar posibilidades alternativas.)Est diseado con una interfaz web, que consta fundamentalmente de 3 partes o ventanas bien definidas: una primera en la que se introducen los datos del problema a resolver (ventana Enunciado), una segunda ventana (ventana Solucin) donde pueden leerse los datos relativos a la solucin del problema, una vez que se ha calculado (ptimo, forma de la regin factible y del conjunto de lo soluciones), y una tercera ventana grfica, donde se muestra la representacin grfica de la solucin. La ventana grfica es una ventana abierta por un applet de Geogebra.De hecho, la solucin construida por PL es lo que podra llamarse una pseudoconstruccin en Geogebra, en el sentido de que todos los clculos matemticos que realiza el programa estn realizados utilizando Geogebra, aunque el algoritmo utilizado para encontrar la solucin est programado en JavaScript. Como resultado, aunque la solucin se obtiene mediante una construccin completamente realizada dentro del programa de geometra dinmica, no se garantiza que dicha solucin sea resistente a variaciones dinmicas de los objetos libres que la definen, razn por la cual no se ha habilitado ms interaccin con la ventana grfica que la necesaria para centrar, mediante movimiento de los ejes y cambio de escala, el dibujo que da lugar a la solucin.Por supuesto, sera deseable una construccin de la solucin tal que pudiera interactuarse grficamente con la misma, aprovechando as todas las caractersticas propias del software de geometra dinmica.Dicha construccin es posible (y est realizada) si se restringe la forma de la regin factible, aunque una nica construccin resistente a cualquier variacin de los objetos que definen la regin factible ha sido imposible de obtener. Por consiguiente, si se desea utilizar la calculadora PL para trabajar la alternancia de registros analtico y grfico, en el sentido del segundo al primero, debe ser utilizada estableciendo conjeturas acerca de qu inecuaciones definirn regiones con cierta forma que sean comprobadas despus, o relegar directamente PL en favor de otro tipo de herramientas ms adecuadas a este fin.

WINQSB

WinQSB es una aplicacin creada por el Dr. Yih-Long Chang, que consta de una serie de mdulos (subprogramas) que nos ayudan a resolver y automatizar algunos problemas de clculos lineales, investigacin de operaciones, planteamiento de produccin, evaluacin de proyectos, etc.

QUE HACE ESTE SOFTWARE?Es un sistema interactivo de ayuda a la toma de decisiones que contiene herramientas muy tiles para resolver distintos tipos de problemas en el campo de la investigacin operativa. El sistema est formado por distintos mdulos, uno para cada tipo de modelo o problema.Partido de la base que este software se desarrolla con el fin de resolver diversos problemas presentados en el campo de la investigacin operativa, en este primer acercamiento se conocer el funcionamiento particular de este aplicativo.

PARA QU SIRVE EL APLICATIVO?Winqsb fue diseado para optimizar los procesos al interior de una organizacin mediante herramientas heursticas y matemticas como lo son la programacin lineal, programacin entera, programacin dinmica, diagramas per cpm, y procesos markovianos.

QUE MDULOS TIENE?Hoy en da el mundo empresarial se ha vuelto ms complicado que en aos anteriores, debido a un mercado muy competitivo en donde solo el mejor se lleva la mejor parte, es por eso que las empresas han comenzado a usar una variedad de modelos de optimizacin en sus procesos tanto operativos como administrativos y financieros apoyados en los diferentes modelos cuantitativos, como es la investigacin de operaciones y es en este punto donde aparece WINQSB, este aplicativo tiene como finalidad solucionar problemas de tipo empresarial en cada una de las diferentes reas, resolviendo por medio de modelos matemticos y heursticos, diferentes problemas de orden cuantitativo que se pueden presentar en una organizacin, esto da apoyo igualmente a profesores y estudiantes de carreras como la ingeniera industrial quienes pueden simular situaciones empresariales donde hay que solucionar problemas de diferente ndole. WINQSB esta divido en 19 mdulos: Acceptance sampling analysis (ASA): Este programa desarrolla y analiza los planes de muestreos de tolerancias para atributos y caractersticas de calidad variable. Aggregate planning (AP): Soluciona los problemas de planeamiento agregado a las demandas de satisfaccin del consumidor con mnimos o aceptables costos relacionados. Decision analisys (DA): El programa resuelve 4 tpicos problemas de decisin: Anlisis Beyesiano, anlisis de tablas de rentabilidad, anlisis de rbol de decisin y la teora del juego de cero suma. Dynamic Programming (DP): Resuelve 3 tipos populares de problemas dinmicos: Diligencia, mochila y problemas de planeacin de produccin e inventarios. Facility location and layout (FLL): Este mdulo resuelve los problemas de facilidades de localizacin, disposicin funcional y balanceo de lnea de produccin. Forecasting (FC): Este mdulo resuelve proyecciones de series de tiempo usando 11 diferentes mtodos y adems utilizando regresiones lineales de mltiples variables. Linear Goal Programming (GP) e Integer Linear Goal Programming (IGP): Este programa resuelve los problemas de GP usando el mtodo simplex modificado o el mtodo grfico y los problemas de IGP usando el procedimiento branch-and-bound. Inventory theory and systems (ITS) : Resuelve problemas de control de inventarios: problemas de cantidades econmicas a pedir (EOQ), problemas de descuento de cantidad de la orden, problemas de periodos probabilsticos simples y problemas de tamao dinmico de lotes; y evala y simula 4 sistemas de control de inventarios: (s, Q), (s, S), (R, S) y (R, s, S). Job scheduling (JOB): Este programa resuelve los problemas de taller de tareas y programacin del flujo de trabajo usando generacin heurstica y aleatoria. Linear Programming (LP) e Integer Linear Programming (ILP): Este programa resuelve los problemas de LP usando el metodo simplex o el mtodo grfico y los problemas de ILP usando el procedimiento branch-andbound. Markov process (MKP): Este programa resuelve y analiza el proceso de Markov. Material requirements planning (MRP): El programa efecta la planeacin de requerimiento de materiales y determina que, cuanto y cuanto cuestan los materiales y componentes que son requeridos para satisfacer un plan de produccin de productos finales para un horizonte de planeacin. Network Modeling (NET): Este modulo resuelve los problemas de red incluyendo flujo de red (transbordo), transporte, asignacin, caminos cortos, mximo flujo, cruces mnimos y problemas de viajes de vendedores. Nonlinear Programming (NLP): Este programa resuelve los problemas no lineales no forzados usando el mtodo de bsqueda y los problemas no lineales forzados usando el mtodo de la funcin de castigo. PERT/CPM: Este mdulo resuelve los problemas de planeacin de proyectos usando el mtodo de ruta crtica y la tcnica de evaluacin y revisin. As mismo realiza anlisis de choque, anlisis de costos, anlisis de probabilidad y simulacin. Quadratic Programming (QP) e Integer Quadratic Programming (IQP): Este programa resuelve los problemas de QP usando el mtodo simplex modificado o el mtodo grfico y los problemas de IQP usando el procedimiento branch-and-bound. Quality control charts (QCC): Construye grficos de control de calidad para variables y datos de atributos y as mismo realiza anlisis de grficas relacionadas. Queuing analysis (QA): Este programa resuelve el rendimiento de sistemas de colas de etapa simple usando la formula de cercana, aproximacin o simulacin. Queuing system simulation (QSS): Este programa modela y simula sistemas de colas simples y multi etapas con componentes, incluyendo poblaciones de clientes arribando, servidores, colas y/o colectores de basuras.

VISTA DEL SOFTWARE WINQSBWinQSB utiliza los mecanismos tpicos de la interface de Windows, es decir, ventanas, mens desplegables, barras de herramientas, etc. Por lo tanto el manejo del programa es similar a cualquier otro que utilice el entorno Windows. Una vez seleccionado el mdulo con el cual se desee trabajar, aparecer una ventana cuyas caractersticas inciales sern similares para todos los mdulos del WinQSB. Al acceder a cualquiera de los mdulos se abre una ventana en la que debemos elegir entre crear un nuevo problema (File > New Problem) o leer uno ya creado (File > Load Problem). Las extensiones de los ficheros con los modelos las pone el programa por defecto, por lo tanto solamente debemos preocuparnos del nombre, que no deber tener ms de 8 caracteres. Todos los mdulos del programa tienen en comn los siguientes mens desplegables: File: incluye las opciones tpicas de este tipo de mens en Windows, es decir, permite crear y salvar ficheros con nuevos problemas, leer otros ya existentes o imprimirlos. Edit: incluye las utilidades tpicas para editar problemas, copiar, pegar, cortar o deshacer cambios. Tambin permite cambiar los nombres de los problemas, las variables, y las restricciones. Facilita la eliminacin o adicin de variables y/o restricciones, y permite cambiar el sentido de la optimizacin. Format: incluye las opciones necesarias para cambiar la apariencia de las ventanas, colores, fuentes, alineacin, anchura de celdas, etc. Solve and Analyze: esta opcin incluye al menos dos comandos, uno para resolver el problema y otro para resolverlo siguiendo los pasos del algoritmo. Results: incluye las opciones para ver las soluciones del problema y realizar si procede distintos anlisis de la misma. Utilities: este men permite acceder a una calculadora, a un reloj y a un editor de grficas sencillas. Window: permite navegar por las distintas ventanas que van apareciendo al operar con el programa. WinQSB: incluye las opciones necesarias para acceder a otro mdulo del programa. Help: permite acceder a la ayuda on-line sobre la utilizacin del programa o las tcnicas utilizadas para resolver los distintos modelos. Proporciona informacin sobre cada una de las ventanas en la que nos encontremos.

La parte superior de la ventana llamada TITULO indica el nombre del mdulo seleccionado, en este caso se opt por mostrar el mdulo de Programacin Lineal y Entera (Linear and integer programming).Debajo encontramos los men Archivo (File) y Ayuda (Help). El men archivo comprende las siguientes opciones: Nuevo problema (New Problem): Permite introducir un nuevo problema. Abrir Problema (Load Problem): Abre un problema que se ha guardado con anterioridad. Salir (Exit): Sale del programa.El men Ayuda (Help) lo conforman:

Contenido (Contents): Contenido completo de la ayuda sobre el mdulo seleccionado. Buscar ayuda en... (Search for Help on...): Bsqueda de ayuda mediante palabras claves. Cmo usar la ayuda (How to Use Help): Indicaciones (puede ser en espaol) de como se utiliza la ayuda para sacarle el mximo provecho. Ayuda sobre la ventana actual (Help on Current Windows): Interesante opcin que muestra la ayuda slo sobre los elementos que aparecen actualmente en la ventana. Acerca de... (About LP-ILP): Muestra datos sobre la creacin del programa e informacin sobre la licencia.El programa tambin cuenta con una barra de herramientas que ayuda de forma significativa la seleccin de las opciones ms usadas.

El primer botn permite la creacin de un nuevo problema, el segundo abre un problema existente, mientras que el tercero, permite salir del programa.

APLICACIN DEL WINQSB

Problema de transporteEl problema del transporte como un modelo especial dentro de la programacin lineal presenta una metodologa de resolucin que resulta ser muchos ms sencilla que los problemas de programacin tradicionales. "WinQSB" tambin distingue el problema de transporte como un caso especial y desarrolla un mdulo dedicado de manera exclusiva al trabajo con este tipo de modelos en el llamado Network Modeling.Este programa resuelve los problemas de red, incluyendo flujo de red capacitados (transbordo), transporte, asignacin, la ruta ms corta, flujo mximo, rbol de expansin mnima, y problemas del vendedor viajero. Una red incluye nodos y conexiones (arcos / enlaces) Cada nodo tiene una capacidad para el flujo de red y los problemas de transporte. Si hay una conexin entre dos nodos, puede haber un costo, un beneficio, una distancia o la capacidad de flujo asociado a la conexin. Con base en el tipo de problema especfico, NET resuelve la conexin o el envo satisfaciendo las restricciones con el nimo de optimizar la funcin objetivo especificada. El primer paso para resolver un problema de transporte mediante WinQSB es ingresar al mdulo Network Modeling.

EL PROBLEMAUna empresa energtica colombiana dispone de cuatro plantas de generacin para satisfacer la demanda diaria elctrica en cuatro ciudades, Cali, Bogot, Medelln y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al da respectivamente. Las necesidades de las ciudades de Cali, Bogot, Medelln y Barranquilla son de 70, 40, 70 y 35 millones de Kw al da respectivamente.

Los costos asociados al envo de suministro energtico por cada milln de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla.

Formule un modelo de programacin lineal que permita satisfacer las necesidades de todas las ciudades al tiempo que minimice los costos asociados al transporte.

INGRESANDO A NETWORK MODELINGUna vez se haya ingresado al mdulo Network Modeling, se abrir una ventana de inicio del mdulo, tal como se muestra a continuacin.

Aqu podemos crear un nuevo problema o cargar uno que ya nos encontremos desarrollando, en este caso abriremos un nuevo problema. Una vez demos click en "Nuevo Problema" se abrir un men emergente que nos pedir ingresar la informacin bsica del problema.

En este men debemos completar la informacin concerniente al tipo de problema, criterio de la funcin objetivo y el nmero de fuentes y destinos que tenga nuestro problema, en este caso tenemos 4 fuentes y 4 destinos. Una vez completado el proceso damos click en "OK" y observaremos la siguiente ventana. En esta ventana podemos observar la matriz en la que ingresaremos los datos.

El proceso de reconocimiento de la ventana matriz es rpido, adems de las ya explicadas herramientas se encuentran funciones de edicin bastante conocida y de formato alfanumrico. Antes de ingresar los datos podemos modificar los nombres de las fuentes y destinos en el men "Edicin (Edit / Node Names)". Nosotros renombraremos en este caso los nodos por los indicados en el problema.

Ahora se consignan los costos asociados al modelo, igualmente se consignan la respectiva oferta de cada una de las plantas y las demandas de las ciudades.

Ahora que se ha completado de suministrar toda la informacin se procede a resolver el modelo (click en resolver), la ventana que se abrir tendr la informacin respecto a las unidades enviadas de cada Planta hacia cada ciudad y el costo total ptimo.

De esta manera se obtiene la solucin ptima del modelo de transporte, sin embargo no es todo lo que WinQSB tiene para ofrecer respecto al modelo de transporte, dado que este software posee herramientas que entregan el resultado grficamente y presenta los resultados que se obtienen mediante los mtodos heursticos que hemos visto en mdulos anteriores como Mtodo de Aproximacin de Vogel, Mtodo de Costos Mnimos y el Mtodo de la Esquina Noroeste, que una vez se ha obtenido la solucin mediante el programa sirven para entornos netamente acadmicos.

Mtodos heursticosPara poder visualizar (recordamos que esto es regularmente requerido con fines acadmicos) los tabulados finales obtenidos mediante los mtodos heursticos en Network Modeling tenemos que acceder a la pestaa llamada "Solve and Analyze" una vez ah debemos seleccionar la opcin "Select Initial Soluction Method", Tal como lo mostramos a continuacin.

Una vez cumplido este procedimiento se abrir un men en el cual podremos seleccionar el mtodo heurstico cuyo tabulado final queremos observar.

Una vez hemos seleccionado el mtodo damos click en "OK" y procedemos a acceder a la opcin "Solve and Display Steps - Tableu" que se encuentra en la pestaa "Solve and Analyze" tal como lo mostramos a continuacin.

Ahora veremos el tabulado final del mtodo heurstico escogido.

Mtodo de Aproximacin de Vogel

Mtodo del Costo Mnimo

Mtodo de la Esquina Noroeste

PROBLEMAS PARA UTILIZAR EL WINQSBActualmente con el avance de los sistemas operativos se ha presentado una dificultad notoria para poder trabajar con el WINQSB, esto debido a que el software solo funciona en sistemas operativos de 32 bits. Si bien en la actualidad los sistemas operativos Windows 7 y 8 tienen sus versiones correspondientes para 32 bits, debido al avance de los equipos de cmputo se aconseja utilizar las versiones de 64 bits lo cual dificulta el uso del WINQSB.La solucin planteada ante este problema es utilizar mquinas virtuales en el computador que se est empleando para usar un sistema de 32 bits y ejecutar el programa. Actualmente uno de los programas ms utilizados en virtualizacin es el Virtual Box.

DONDE UBICAR EL SOFTWAREEn el caso de WINQSB a pesar de ser un software de amplio uso por parte de los estudiantes e ingenieros es difcil de encontrar en internet. Podemos recomendar visitar la siguiente pgina web:http://ingenierosindustriales.jimdo.com/herramientas-para-el-ingeniero-industrial/investigacin-de-operaciones/descargas-y-mutimedia/En el link correspondiente se puede hallar el software alojado en Dropbox.

EJERCICIOS RESUELTOS CON WINQSB

PROGRAMACIN LINEAL

Matriz de Datos:

Matriz de Solucin:

a) Cul es la solucin que maximiza la funcin objetivo y cul es el valor de sta?X1=31.4706, X2=46.3805, X3=39.7800, X4=0Z=833.4361

b) Cules son las restricciones activas e inactivas del problema?Restricciones activas = C1, C2, C4Restricciones inactivas = C3

c) Cul es la restriccin de mayor holgura y de cunto es sta?La restriccin con mayor holgura es la C3, con un valor de 542.2161

d) Utilizando como referencia los precios sombra, cul ser el valor de la funcin objetivo si se agregan 10 unidades de C1? 10 unidades de C2? 10 unidades de C3? 10 unidades de C4?10 unidades C1: Z = 833.4361 + 10 (0.0139) = 833.575110 unidades C2: Z = 833.4361 + 10 (0.0405) = 833.841110 unidades C3: Z = 833.4361 + 10 (0) = 833.436110 unidades C4: Z = 833.4361 + 10 (0.1031) = 834.4671

e) Para qu valores de contribucin por cada unidad de X1, la solucin del problema diferir a la del inciso a? Y para la variable X2?El vrtice de solucin del problema ser diferente si la contribucin por cada unidad de X1 es superior a 10.8430.El vrtice de solucin del problema ser diferente si la contribucin por cada unidad de X2 es inferior a 4.4417.

f) Encontrar la solucin que maximice en caso que en la respuesta slo fuesen vlidos valores enteros.

X1=31, X2=46, X3=40, X4=0Z=833

TRANSPORTE

Matriz de Datos:

Matriz de Solucin:

a) Encontrar la solucin que minimice. Cul es el costo total?

Fabrica 3TEG L. 478,400.00

Fabrica 4CEIBA L. 84,000.00

Fabrica 5NACAOME L. 492,800.00

Fabrica 7DANLI L. 132,600.00

Fabrica 7COMAYAGUA L. 172,800.00

Fabrica 8SPS L. 561,600.00

Fabrica 8JUTICALPA L. 235,200.00

Fabrica 9CHOLUTECA L. 431,200.00

Fabrica 10DANLI L. 592,000.00

Fabrica 10JUTICALPA L. 396,000.00

Costo Total L. 3,576,600.00

b) Cul es el costo marginal de la ruta S3-D5? Y de la ruta S2-D7?El costo marginal de la ruta S3-D5 es de L. 72.00El costo marginal de la ruta S2-D7 es de L. 73.00c) Cul ser el menor valor del costo unitario de transporte en la ruta S3-D5 sin que cambie la asignacin ptima? Y en la ruta S2-D7?Para la ruta S3-D5 es de L. 22.00Para la ruta S2-D7 es de L. 24.00d) De ser posible tener mayor disponibilidad en las fuentes, determine a qu fuente asignara ms unidades y por qu?

En la fbrica 8, porque cada unidad adicional disponible reduce el costo total en L. 3.00e) Qu destino genera mayor costo adicional por cada unidad adicional demandada?En Danli, porque cada unidad adicional demandada aumenta el costo total en L. 34.00

ASIGNACIN

Matriz de Datos:

Matriz de Solucin:

a) Encontrar la solucin que maximice. Cul es la utilidad total?Fuente 2Destino 6 L. 1,774.00

Fuente 3Destino 9 L. 1,921.00

Fuente 4Destino 8 L. 1,251.00

Fuente 5Destino 7 L. 1,715.00

Fuente 6Destino 2 L. 1,710.00

Fuente 7Destino 5 L. 1,832.00

Fuente 8Destino 1 L. 1,780.00

Fuente 9Destino 3 L. 1,218.00

Fuente 10Destino 4 L. 1,935.00

Costo Total L. 15,136.00

b) Cul es la utilidad marginal de asignar desde 2 hasta 5? Y desde 3 hasta 4?La utilidad marginal de asignar desde 2 hasta 5 es de L. 0.00La utilidad marginal de asignar desde 3 hasta 4 es de L. 254.00c) Cul ser el mayor valor de utilidad unitaria en la ruta 2-5 sin que cambie la asignacin ptima? Y de la ruta 3-4?El mayor valor de utilidad unitaria en la ruta 2-5 es de L. 0.00 + L. 1748.00 = L. 1748.00El mayor valor de utilidad unitaria en la ruta 3-4 es de L. 254.00 + L. 1712.00 = L. 1966.00

TEORIA DE COLAS

Matriz de Datos:

Matriz de Solucin:

a) Calcular el nmero de servidores que generarn un costo mnimo total. Cul es este costo?Con 15 servidores, a un costo mnimo de $ 180.8268.

b) Cul es el valor de los principales parmetros y costos de colas?U = Coeficiente de utilizacin = 79.0434%Ls = Longitud promedio del sistema = 12.9736Lq = Longitud promedio de la cola = 1.1171Ws = Tiempo promedio de un cliente en el sistema = 0.0782 horas Wq = Tiempo promedio de un cliente en la cola = 0.0067 horasPo = Probabilidad que todos los servidores estn desocupados = 0.0006%Costo de espera total = $94.8520 + $18.8610 = $ 113.7130Costo de servicio total = $11.1713 + $47.4260 = $58.5973Costo por clientes rechazados = $ 0.1164 por horaCosto por espacio para uso de cola = $ 8.40 por horaCOSTO TOTAL DEL SISTEMA = $180.8268/hora

MATRIZ DE PAGOS

Matriz de Datos:

Matriz de Solucin:

a) Cul es la alternativa ptima de solucin?La alternativa ptima de solucin es la 8, con un valor esperado de L. 736.32b) Encontrar la alternativa ptima para valores de coeficiente de optimismo p=0, p=0.25, p=0.5, p=0.75 y p=1.P = 0 Alternativa 8, L. 385

P = 0.25 Alternativa 8, L. 518.25

P = 0.50 Alternativa 8, L. 678.50

P = 0.75 Alternativa 8, L. 838.75

P = 0.1 Alternativa 8, L. 999

c) Encontrar la alternativa ptima si todos los estados tuviesen probabilidades iguales.La alternativa ptima sera la 8, con L. 678.10

d) Cul es el valor esperado con informacin perfecta? Cul ser el valor mximo a pagar por dicha informacin?El valor esperado es de L. 990.39El valor mximo a pagar por la informacin perfecta es de L. 254.07

e) Pagara usted $100 por la informacin perfecta? Por qu?Si porque pagando los $100 el valor esperado aumenta a L. 254.07

RBOL DE DECISINMatriz de Datos:

Matriz de Solucin:

Qu secuencia genera el mayor valor esperado?

En la decisin 1, se toma el Evento 2. En la decisin 6, se toma el evento 14. El mayor valor esperado es de L. 4,814.94

CONTROL DE INVENTARIOS

Matriz de Datos:

Matriz de Solucin:

a) Cul es el costo anual actual por inventario?El costo anual por inventario es de $ 16,600.00

b) Cul debe ser la cantidad ptima por pedido?La cantidad ptima por pedido debe ser de 585.54 unidades.

c) Compare el costo total anual en el caso actual respecto al caso ptimo.El costo total anual actual es de $16,600 siendo mayor al ptimo de $ 16395.12 con una diferencia de $ 204.88, lo que representa una reduccin de apenas 1.23%.

d) Cul es el punto de reorden?El punto de reorden es de 395.20 unidades.

e) Si se desea un costo mnimo, cada cuntos das ha de pedirse una orden?Se ha de pedir cada 0.0366 aos, o sea cada 13.176 das.

f) Grafique costo total anual de inventario respecto a cantidad de producto por pedido.

PERT

Matriz de Datos:

Matriz de Solucin:

a) Cul es la ruta crtica del proyecto?

La ruta es la C-H-O-S con un tiempo de terminacin de 101.50 semanas y una desviacin estndar de 9.59.

b) Cul es la posibilidad de adelantar la culminacin del proyecto en 10 semanas?

Adelantar la culminacin del proyecto en 10 semanas tiene un 14.85%

c) Cul es la probabilidad que el proyecto termine con un atraso mximo de 20 semanas?

Atrasar la culminacin del proyecto en 20 semanas tiene un 98.15%

d) El diagrama de Gantt del proyecto mostrando la ruta crtica del mismo.

CPM

Matriz de Datos:

Matriz de Solucin:

Normal Intensivo

a) Determinar ruta crtica, tiempo y costo de proyecto normal.

La ruta critica es la B-F-J-K en 267das, y un costo de $164,500.00

b) Determinar tiempo y costo de proyecto intensificado. Qu actividades deben ser intensificadas?El tiempo del proyecto intensificado es de 253 das, con un costo de $249,500.00

c) Determine el costo mnimo del proyecto intensificando 5 y 10 das.Para 5 semanas el costo mnimo es de $165,333.34Para 10 semanas el costo mnimo es de $169,571.44

d) Suponga que cada semana de atraso en la finalizacin del proyecto representa una penalizacin de $1,000/semana. Cul es el tiempo ptimo de finalizacin del proyecto?

El tiempo ptimo de finalizacin es de 260 das.

ANALISIS DE MARKOV

Matriz de Datos:

Matriz de Solucin:

a) Suponiendo que el primer estado del sistema es el estado 1, calcule la probabilidad de ocurrencia de cada uno de los estados durante las primeras tres iteraciones y durante el estado estable.Iteracin 1: S1=0.482499, S2=0.077868, S3=0.186352, S4=0.148852, S5=0.104429Iteracin 2: S1=0.482573, S2=0.077839, S3=0.186288, S4=0.148856, S5=0.104443Iteracin 3: S1=0.482560, S2=0.077844, S3=0.186300, S4=0.148855, S5=0.104440

Estado Estable: S1=0.4826, S2=0.0778, S3=0.1863, S4=0.1489, S5=0.1044

b) En promedio, cada cuntos cambios de estado en el sistema se espera que se repita el estado 4?Se espera que se repita el estado 4 cada 6.7179 ocasiones.TEORIA DE JUEGOS

Matriz de Datos:

Matriz de Solucin:

a) Cul es el valor esperado para el jugador 1?El valor esperado para el jugador 1 es de 216.27

b) Qu estrategias deber jugar el jugador 1 y en qu proporcin?La estrategia 7, 83% y la 4, 17%c) Qu estrategias deber jugar el jugador 2 y en qu proporcin?La estrategia 7, 85% y la 1, 15%

CONCLUSIONES

Es una herramienta informtica capaz de reducir el tiempo y la complejidad de resolver problemas de investigacin operativa. Winqsb es una herramienta que brinda la posibilidad de desarrollar temas especficos de un total de 13 materias, lo cual es de gran importancia para el aprendizaje de los estudiantes, pues de esa manera se facilita la resolucin y anlisis de una gran cantidad de problemas relacionados con la planeacin de la produccin, el control de la calidad y la toma de decisiones cuantitativas de la administracin. En el mercado informtico actual existen otras herramientas aplicables en la investigacin operativa con el Solver de Excel, Tora y Lingo, sin embargo el atractivo de WINQSB es la facilidad de su uso y amplitud de temas.

FUENTES DE INFORMACION

Referencias bibliogrficas

TAHA, Hamdy A. Investigacin de operaciones. 7 edicin. PEARSON EDUCACION, Mexico.2004.

WINQSB,YI LOGN CHAN Version 2.0. Wiley

Referencias electrnicas

http://www.dia.fi.upm.es/~jafernan/teaching/operational-research/WinQSB2.0.pdfhttp://www.eumed.net/libros-gratis/2006c/216/1a.htmhttp://recursostic.educacion.es/observatorio/web/es/component/content/article/1056-monografico-una-calculadora-grafica-para-la-ensenanza-de-las-matematicas?start=3http://hemaruce.angelfire.com/Mwinqsb.pdfhttp://www.pcdigital.org/descargar-winqsb-20/

ANEXOS

ANEXO N 1. HISTORIA DE PROGRAMACION LINEAL

54

ANEXO N 2. Interface Geogebra

ANEXO N 3. Biblioteca de clases

ANEXO N 4. TIPOS DE ALMACENES

55