CUESTIONARIO IO GRUPO: 204

1. Qué es la investigación de Operaciones? La Investigación de operaciones es un conjunto de técnicas matemáticas especialmente estructuradas para la torna de decisiones; en ese sentido trata de brindar criterios objetivos para que la gente pueda decidir analíticamente sobre las situaciones a las que se enfrenta ordinariamente en sus actividades industriales y comerciales. También es considerada como una rama de las Matemáticas consistente en el uso de modelos matemáticos, estadística y algoritmos con objeto de realizar un proceso de toma de decisiones. Frecuentemente, trata el estudio de complejos sistemas reales, con la finalidad de mejorar (u optimizar) el funcionamiento del mismo. La investigación de operaciones permite el análisis de la toma de decisiones teniendo en cuenta la escasez de recursos, para determinar cómo se pueden maximizar o minimizar los recursos. Es una ciencia que modela problemas complejos haciendo uso de las matemáticas y la lógica. El método más popular es el simplex (George Dantzig, 1947) dentro de la rama de programación lineal. El algoritmo simplex ha sido elegido como el mejor de los diez de mayor influencia en el desarrollo y la práctica de la ciencia y la ingeniería en el siglo XXII. •

La Investigación de Operaciones aspira a determinar el mejor curso de acción, o curso óptimo, de un problema de decisión con la restricción de recursos limitados.

•

Como técnica para la resolución de problemas, investigación de operaciones debe visualizarse como una ciencia y como un arte.

Como Ciencia radica en ofrecer técnicas y algoritmos matemáticos para resolver problemas de decisión adecuada. Como Arte debido al éxito que se alcanza en todas las fases anteriores y posteriores a la solución de un modelo matemático, depende de la forma apreciable de la creatividad y la habilidad personal de los analistas encargados de tomar las decisiones. En un equipo de Investigación de Operaciones es importante la habilidad adecuada en los aspectos científicos y artísticos de Investigación de Operaciones. Si se destaca un aspecto y no el otro probablemente se impedirá la utilización efectiva de la Investigación de Operaciones en la práctica. La Investigación de Operaciones en la Ingeniería de Sistemas se emplea principalmente en los aspectos de coordinación de operaciones y actividades de la organización o sistema que se analice, mediante el empleo de modelos que describan las interacciones entre los componentes del sistema y de éste con este con su medio ambiente. En la Investigación de Operaciones la parte de "Investigación" se refiere a que aquí se usa un enfoque similar a la manera en la que se lleva a cabo la investigación en los campos científicos establecidos. La parte de "Operaciones" es porque en ella se resuelven problemas que se refieren a la conducción de operaciones dentro de una organización.

2. Cuál es el Operaciones?

contexto

histórico

y

evolución

de

la

Investigación

de

Se inicia desde la revolución industrial, en los libros se dice que fue a partir de la segunda Guerra Mundial. 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. En la investigación de operaciones, las computadoras son la herramienta fundamental en la investigación de operaciones. El problema de la resolución de un sistema lineal de inecuaciones se remonta, al menos, a Fourier, después de quien nace el método de eliminación de Fourier-Motzkin. La programación lineal se plantea como un modelo matemático desarrollado durante la segunda guerra mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejército y aumentar las pérdidas del enemigo. Se mantuvo en secreto hasta 1947. En la posguerra, muchas industrias lo usaron en su planificación diaria. Los fundadores de la técnica son George Dantzig, quien publicó el algoritmo simplex, en 1947, John von Neumann, que desarrolló la teoría de la dualidad en el mismo año, y Leonid Kantorovich, un matemático ruso, que utiliza técnicas similares en la economía antes de Dantzig y ganó el premio Nobel en economía en 1975. Leonid Khachiyan en 1979 fue el primero en demostrar que el problema de la programación lineal se solucionaba en tiempo polinomial, sin embargo, el mejor avance en los principios teóricos y prácticos en el campo se produjo en 1984, cuando Narendra Karmarkar introduce un nuevo método del punto interior para resolver problemas de programación lineal. El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70 personas a 70 puestos de trabajo es un ejemplo de la utilidad de la programación lineal. La potencia de computación necesaria para examinar todas las permutaciones a fin de seleccionar la mejor asignación es inmensa; el número de posibles configuraciones excede al número de partículas en el universo. Sin embargo, toma sólo un momento encontrar la solución óptima mediante el planteamiento del problema como una programación lineal y la aplicación del algoritmo simplex. La teoría de la programación lineal reduce drásticamente el número de posibles soluciones óptimas que deberán ser revisadas. PROGRAMACION LINEAL 3.

Qué es la Programación Lineal (PL)?

Procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal. La programación lineal consiste en optimizar (minimizar o maximizar) una función lineal, que denominaremos función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales. A pesar de que la programación lineal se empezó a estudiar desde finales del S.XIX no fue hasta mediados del presente siglo en que tuvo auge como técnica matemática aplicable a los problemas de la empresa. El Dr. G. Damtzing desarrolló el método simplex y con ello hizo posible la solución de grandes problemas modelados con programación lineal que solo quedaban en la situación de estudios. Paralelamente a la invención de este método a partir de mediados del siglo se

desarrollo la computación digital y se pudo tener resultados óptimos a los problemas estudiados que se quedaron como modelos. La programación lineal es actualmente la técnica matemática utilizada mas actualmente gracias a que el algoritmo simplex es muy eficiente y al desarrollo de la computación. Lo que se busca con la aplicación de la programación lineal es resolver problemas comunes y a la vez muy variados de la empresa en donde en general se tienen necesidades por satisfacer con cierto número de recursos limitados o escasos y con el objetivo de lograrlo en forma óptima. Esto significa la búsqueda de un valor máximo cuando se trata de beneficios; o bien la búsqueda de un mínimo cuando se trata de esfuerzos a desarrollar. Un modelo de programación lineal es un conjunto de expresiones matemáticas las cuales deben cumplir la característica de linealidad que puede cumplirse siempre y cuando las variables utilizadas sean de primergrado. 4. Qué es un Modelo PL? Un modelo es una representación ideal de un sistema y la forma en que este opera. El objetivo es analizar el comportamiento del sistema o bien predecir su comportamiento futuro. Obviamente los modelos no son tan complejos como el sistema mismo, de tal manera que se hacen las suposiciones y restricciones necesarias para representar las porciones más relevantes del mismo. Claramente no habría ventaja alguna de utilizar modelos si estos no simplificaran la situación real. En muchos casos podemos utilizar modelos matemáticos que, mediante letras, números y operaciones, representan variables, magnitudes y sus relaciones. 5. Cómo se plantea un Modelo de PL? Un modelo de PL consta al menos de tres conjuntos básicos de elementos: 1. Variables de decisión y parámetros: Las variables de decisión son incógnitas que deben ser determinadas a partir de la solución del modelo. Los parámetros representan los valores conocidos del sistema o bien que se pueden controlar. 2. Restricciones: Las restricciones son relaciones entre las variables de decisión y magnitudes que dan sentido a la solución del problema y las acotan a valores factibles. Por ejemplo si una de las variables de decisión representa el número de empleados de un taller, es evidente que el valor de esa variable no puede ser negativa. 3. Función Objetivo: La función objetivo es una relación matemática entre las variables de decisión, parámetros y una magnitud que representa el objetivo o producto del sistema. Por ejemplo si el objetivo del sistema es minimizar los costos de operación, la función objetivo debe expresar la relación entre el costo y las variables de decisión. La solución ÓPTIMA se obtiene cuando el valor del costo sea mínimo para un conjunto de valores factibles de las variables. Es decir hay que determinar las variables x1, x2, ..., xn que optimicen el valor de Z = f(x1, x2, ..., xn) sujeto a restricciones de la forma g(x1, x2, ..., xn) b. Donde x1, x2, ..., xn son las variables de decisión Z es la función objetivo, f es una función matemática.

Los pasos para plantear un Modelo de PL son, primero, Definir las variables de decisión, Definir el objetivo o meta en términos de las variables de decisión, Definir las restricciones y Restringir todas las variables para que no sean negativas. 6. Cuales son las suposiciones y características de un modelo de PL? Un modelo de P.L debe tener las propiedades de: •

Proporcionalidad: En el modelo de programación lineal los pagos deben ser proporcionales. El modelo de programación lineal es estático, plantea una situación del momento. x = progreso de la actividad • Aditividad (adición): Siempre los pagos se suman, Requerimientos, Costos y Utilidades. • Divisibilidad: Las variables involucradas en el modelo de programación lineal pueden no ser un número entero. Si los valores son muy pequeños no importa el redondeo. Si son muy altos afecta el redondeo. • Certidumbre(certeza): Todos los parámetros que se manejan deben ser basados con certeza

De forma obligatoria se deben cumplir los siguientes requerimientos para construir un modelo de Programación Lineal: • • •

Función objetivo. (FO): Debe haber un objetivo (o meta o blanco) que la optimización desea alcanzar. Restricciones y decisiones: Debe haber cursos o alternativas de acción o decisiones, uno de los cuáles permite alcanzar el objetivo. La FO y las restricciones son lineales. Deben utilizarse solamente ecuaciones lineales o desigualdades lineales.

7. Cuales son los modelos más aplicados de PL ? Un modelo es producto de una abstracción de un sistema real: eliminando las complejidades y haciendo suposiciones pertinentes, se aplica una técnica matemática y se obtiene una representación simbólica del mismo •

Modelos Matemáticos

Los modelos planteados se conocen como modelos determinísticos. En contraste, en algunos casos, quizá no se conozcan con certeza los datos, más bién se determinan a través de distribuciones de probabilidad, se da cabida a la naturaleza probabilistica de los fenómenos naturales. Esto da orígen a los así llamados modelos probabilísticos o estocásticos. Las dificultades evidentes en los cálculos de los modelos matemáticos han obligado a los analistas a buscar otros métodos de cálculo que aunque no garantizan la optimalidad de la solución final, buscan una buena solución al problema. Tales métodos se denominan heuristicos. Suelen emplearse con dos fines: En el contexto de un algoritmo de optimización exacto, con el fin de aumentar la velocidad del proceso. En segundo lugar para obtener una solución al problema aunque no óptima, la que puede ser muy difícil encontrar.

•

Modelos de optimización restringida

En un problema de optimización se busca maximizar o minimizar una cantidad específica llamada objetivo, la cual depende de un número finito de variables, en un modelo de optimización restringida, éstas se encuentran relacionadas a través de una o más restricciones. El planteamiento de este modelo se conoce como programa matemático. 8. Qué es el Método Simplex? El método símplex fue desarrollado en 1947 por el Dr. George Dantzig y conjuntamente con el desarrollo de la computadora hizo posible la solución de problemas grandes planteados con la técnica matemática de programación lineal. El algoritmo denominado símplex es la parte medular de este método; el cual se basa en la solución de un sistema de ecuaciones lineales con el conocido procedimiento de Gauss−Jordan y apoyado con criterios para el cambio de la solución básica que se resuelve en forma iterativa hasta que la solución obtenida converge a lo que se conoce como óptimo. Las definiciones siguientes fundamentadas en 3 importantes teoremas, ayudan a entender la filosofía de este eficiente algoritmo. El método simplex es un procedimiento iterativo que permite tender progresivamente hacia la solución óptima. Es un procedimiento sistemático y eficiente para encontrar y probar soluciones situadas en los vértices de optimalidad. El método requiere que las restricciones sean ecuaciones en lugar de inecuaciones, lo cual se logra añadiendo variables de holgura a cada inecuación del modelo, variables que nunca pueden ser negativas y tienen coeficiente 0 en la función objetivo. Aspectos Fundamentales Del Método Simplex • • • •

Encuentra una solución óptima Es un método de cambio de bases Requiere que la función objetivo sea expresada de tal forma que cada variable básica tenga como coeficiente 0 Requiere que cada variable básica aparezca en una y solamente una ecuación de restricción.

9. Como se construye una tabla Simplex? El método Simplex se utiliza como una herramienta poderosa para la solución de problemas de optimización, ya que solamente evalúa algunos puntos extremos al basarse en dos condiciones: una de optimalidad, que asegura que no se encontrará una solución inferior relativa al punto de solución actual y una de factibilidad que garantiza que a partir de una solución básica factible únicamente se encontraran soluciones básicas factibles, por ello, cada nueva solución tiene la facultad de mejorar el valor de la función objetivo. El procedimiento para llevar a cabo la resolución del método Simplex es el siguiente: a) Elegir la solución básica factible más obvia, si es posible. b) Expresar la función objetivo de la forma siguiente:

c)

Colocar el sistema de manera tabular como se muestra en la siguiente tabla: Inicio del método

Simplex d) Posteriormente se determina una nueva solución básica factible con un valor mejorado de la función objetivo. Esto se logra eligiendo una variable actual no básica con el fin de cambiar de vértice en el espacio d soluciones y que además mejore el valor de f. Como un punto extremo debe tener n – m variables no básicas, una de las básicas actuales debe hacerse no básica siempre que la nueva solución sea factible. Se le llama variable que entra a aquella no básica actual que debe hacerse básica; y se le llama variable que entra a aquella no básica actual que debe hacerse básica; y se le llama variable que sale a la variable básica actual que debe hacerse no básica. La condición de optimalidad estipula que la variable que entra será elegida como la variable no básica que tenga un coeficiente negativo en la ecuación f de la tabla. Usualmente se elige la variable con el mayor coeficiente negativo. La condición de factibilidad muestra que si la variable que entra se aumenta, la solución debe moverse a la siguiente solución básica factible que mejore el valor objetivo. Esta información se obtiene de la anterior tabla generando el cociente entre los valores de la columna solución y los coeficientes positivos de la restricción bajo la columna xi. La variable básica asociada a la relación mínima es la variable que entra (la intersección mas pequeña). Variables que entran y variables que salen

e)

Después de inicio aplicando condición izquierdo posible.

de determinar las variables que entran y salen, se modifica la tabla dando los nuevos valores de f y las nuevas variables básicas reducción de Gauss-Jordan. Se repiten los pasos hasta alcanzar la de optimalidad, es decir, cuando todos los coeficientes en el lado de la ecuación f son no negativos y ninguna mejora adicional es

Reducción de Gauss-Jordan

Conclusión del método

La solución optima para este ejemplo se encuentra en xi= 1.5, x2= 1 y la función objetivo es f= 9. 10. Que relación existe entre el método Simplex y el método grafico? La resolución de problemas lineales con sólo dos o tres variables de decisión se puede ilustrar gráficamente, mostrándose como una ayuda visual para comprender muchos de los conceptos y términos que se utilizan y formalizan con métodos de solución más sofisticados, como por ejemplo el Método Simplex, necesarios para la resolución de problemas con varias variables. Para ello se puede usar el método Gráfico. Aunque en la realidad rara vez surgen problemas con sólo dos o tres variables de decisión, es sin embargo muy útil esta metodología de solución e interpretación, en la que se verán las situaciones típicas que se pueden dar, como son la existencia de una solución óptima única, de soluciones óptimas alternativas, la no existencia de solución y la no acotación. Describimos aquí las fases del procedimiento de solución del Método Gráfico: a) Dibujar un sistema de coordenadas cartesianas en el que cada variable de decisión esté representada por un eje, con la escala de medida adecuada a su variable asociada. b) Dibujar en el sistema de coordenadas las restricciones del problema (incluyendo las de no negatividad). Para ello, observamos que si una restricción es una inecuación, define una región que será el semiplano limitado por la línea recta que se tiene al considerar la restricción como una igualdad. Si la restricción fuera una ecuación, la región que define se dibuja como una línea recta. La intersección de todas las regiones determina la región factible o espacio de soluciones (que es un conjunto convexo). Si esta región es no vacía, ir a la fase siguiente. En otro caso, no existe solución que satisfaga

(simultáneamente) todas las restricciones y el problema no tiene solución, denominándose no factible. c) Determinar los puntos extremos (puntos que no están situados en segmentos de línea que unen otros dos puntos del conjunto convexo) de la región factible (que, como probaremos en la siguiente sección, son los candidatos a solución óptima). Evaluar la función objetivo en estos puntos y aquél o aquellos que maximicen (o minimicen) el objetivo, corresponden a las soluciones óptimas del problema. 11. Que es el concepto de dualidad en el Método Simplex? Asociado a cada problema de Programación Lineal existe un llamado dual, de hecho al de Programación Lineal se le llama primal. La forma general del problema dual es la siguiente: Optimizar Z = b1Y1+ b1Y2 +….+ bn Yn). Función objetivo. Sujeta a a11Y1+ a11Y2 +…..+ am1Y1) £ C1 a21Y1+ a22Y2 +…..+ am2Y2) £ C1. Restricciones : a1mY1+ a2mY2 +…..+ amnYm) £ Cn. Para facilitar la comprensión de lo anterior considérese el diagrama siguiente: Primal

Dual

C1……. Cn (1) a11 b1 (2) (3) b1……. bm (3) (2) a11……. am1 C1 (1) am1 bm C2 Variables

Variables

X1……. Xn

Y1……. Ym

El problema dual tiene las siguientes características: 1) El objetivo de la optimización es contrario al del primal. 2) Las inecuaciones de restricción son inversas y 3) La solución del dual es la misma que la del primal. Desde el punto de vista económico, el significado de las variables duales es de gran interés para los gerentes, ya que representan el valor por unidad de recurso adicional, lo cuál permite tomar decisiones sobre donde invertir para incrementar las utilidades. El Análisis de Sensibilidad tiene como objetivo determinar la influencia de ciertos valores en la solución óptima, que nos permite la interpretación razonable de los resultados obtenidos. En muchos casos la información lograda por la aplicación del análisis de sensibilidad puede ser más importante y más informativa que simple resultado obtenido en la solución óptima. El análisis deviene del resultado de los cambios en los coeficientes en la función objetivo y en los términos independientes en las restricciones.