Source: http://www.researchgate.net/publication/42539979_MATERIALES_INTERACTIVOS_PARA_LA_RESOLUCIN_DE_UN_PROBLEMA_DE_PROGRAMACIN_LINEAL_USANDO_EL_MTODO_SIMPLEX
Timestamp: 2015-03-27 22:30:09+00:00

Document:
MATERIALES INTERACTIVOS PARA LA RESOLUCIÓN DE UN PROBLEMA DE PROGRAMACIÓN LINEAL USANDO EL MÉTODO SIMPLEX - ResearchGate
MATERIALES INTERACTIVOS PARA LA RESOLUCIÓN DE UN PROBLEMA DE PROGRAMACIÓN LINEAL USANDO EL MÉTODO SIMPLEX
M. J. García-Ligero y P
ABSTRACT In this paper we present educational interactive materials for a pleasant learning of the resolution of a Linear Programming Problem using the Simplex method. First of them provides, through an example, the steps involved in the graphic resolution of a Linear Programming Problem with two variables. The following materials correspond to the different steps to solve a Linear Programming Problem: Transformation of a Linear Problem to standard form, Construction of the first Simplex table and Simplex Algorithm.
171 REVISTA INVESTIGACION OPERACIONAL VOL., 31, No 2, 171-179, 2010 MATERIALES INTERACTIVOS PARA LA RESOLUCIÓN DE UN PROBLEMA DE PROGRAMACIÓN LINEAL USANDO EL MÉTODO SIMPLEX M. J. García-Ligero y P., Román, P1. Departamento de Estadística e Investigación Operativa Universidad de Granada (España) ABSTRACT In this paper we present educational interactive materials for a pleasant learning of the resolution of a Linear Programming Problem using the Simplex method. First of them provides, through an example, the steps involved in the graphic resolution of a Linear Programming Problem with two variables. The following materials correspond to the different steps to solve a Linear Programming Problem: Transformation of a Linear Problem to standard form, Construction of the first Simplex table and Simplex Algorithm. RESUMEN En este trabajo presentamos materiales docentes interactivos para un aprendizaje ameno de la resolución de un problema de Programación Lineal mediante el método Simplex. En el primero se proporciona, mediante un ejemplo, los pasos a seguir en la resolución gráfica de un problema de Programación Lineal con dos variables. Los siguientes materiales se corresponden con las distintas fases a seguir desde el planteamiento de un problema de Programación Lineal hasta su resolución: Transformación de un problema de Programación Lineal general a forma estándar, Construcción de la primera tabla del Simplex y Algoritmo Simplex. KEY WORDS: Linear programming, Simplex method, Interactive materials. MSC: 90C05, 97C80, 97D40. 1. INTRODUCCIÓN En la actualidad los sistemas educativos en Europa y, en particular en España, están sufriendo un cambio drástico motivado, en parte, por la utilización de nuevas tecnologías y, por otra, por la implantación del Espacio Europeo de Educación Superior el cual conlleva un aumento del trabajo personal de- sarrollado por el alumno. Por ello, numerosos esfuerzos se han realizado para la adaptación de la docencia de la Investigación Operativa a las nuevas tendencias de aprendizaje; podemos citar, en el ámbito del sistema educativo español, el desarrollo de entornos virtuales de enseñanza (Cobo [1] y Cobo Ortega y Gómez García [2]) en la Universidad de Cantabria (España) y, en general, el sitio web “The Simplex Place” [3] de la Universidad de Melbourne (Australia). En este sentido, nuestra tarea en los últimos años también ha ido dirigida a la adaptación de la docencia de la Investigación Operativa a las nuevas tecnologías. El trabajo que presentamos va dirigido a alumnos que van a tomar contacto por primera vez con la Investigación Operativa y el mundo de la optimización, y en nuestro caso en concreto, a alumnos de segundo curso de la titulación Diplomado en Estadística de la Universidad de Granada. Por esta razón, en una primera fase, nos hemos centrado en el estudio de problemas de Programación Lineal (P. L.), punto de arranque en el estudio de esta materia y, en concreto, a su resolución mediante el método Simplex. Nuestro objetivo ha sido la realización de materiales interactivos de apoyo sobre cuestiones concretas que ayuden a nuestros alumnos a salvar las principales dificultades encontradas y adquirir destrezas para la resolución de un problema de P. L. En la sección 2 1 {mjgarcia, proman}@ugr.es
172 se describen con detalle los materiales realizados y está estructurada en varias subsecciones. En la subsección 2.1. proponemos materiales relativos a la resolución gráfica de ejemplos concretos de un problema de P.L. con los que pretendemos que los alumnos tengan una visión geométrica del problema lineal, familiarizándose visualmente con conceptos básicos como región factible, conjunto convexo, punto extremo, que son claves para el desarrollo del método Simplex. En las subsecciones 2.2-2.4 se presentan materiales relativos a la resolución de un P.L. mediante el método Simplex. La transformación de un problema de P.L. a forma estándar se trata en la subsección 2.2. El material realizado permite al alumno seleccionar el tipo de problema y el tipo de restricciones de que dispone y se le indica cómo actuar y el procedimiento de resolución. En la subsección 2.3 se presenta un material relativo a la construcción de la tabla inicial del Simplex, que muestra al alumno cómo disponer los elementos necesarios en la tabla inicial y cómo identificar las variables básicas y solución básica inicial. Finalmente, la subsección 2.4 muestra el material relativo a la resolución interactiva del Simplex. En él se guía al alumno en los pasos a seguir en la resolución de ejemplos concretos pudiendo seleccionar en cada paso el nivel de detalle en las explicaciones mostradas. Dichos materiales han sido realizados con Microsoft Power Point 2003 y están disponibles para los alumnos en dicho formato así como sus versiones en flash (obtenidas mediante un conversor apropiado). El trabajo finaliza con una sección de conclusiones en la que comentamos nuestra experiencia en la aplicación de los materiales presentados para el aprendizaje de los estudiantes. 2. MATERIALES INTERACTIVOS 2.1. Resolución gráfica de un problema de Programación Lineal En este material se proporciona, en diversos ejemplos que cubren las diversas situaciones que pueden presentarse en la práctica (inexistencia de solución, solución óptima única y no única en los casos de regiones factibles acotadas y no acotadas), los pasos a seguir en la resolución gráfica de un problema de P.L. con dos variables (representación de la región factible, identificación de los puntos extremos y, por último, la obtención de la solución). En este caso se pretende no sólo que el alumno aprenda el mecanismo de la resolución sino también que se familiarice con conceptos básicos y comprenda visualmente el mecanismo del algoritmo Simplex. Así, en primer lugar, después de seleccionar un ejemplo de una de las posibles situaciones que pueden aparecer (ver figura 1), se le muestra su enunciado y el alumno puede seleccionar cada uno de los pasos citados. Nos centramos en el caso de solución óptima única y región factible acotada (ver figura 2) para mostrar con detalle su desarrollo. En la construcción de la región factible se van dibujando, paso a paso, cada uno de los semiespacios que constituyen las restricciones del problema y se finaliza obteniendo la intersección de todos ellos (ver figura 3). Una vez construida la región factible que, en este caso, es un conjunto convexo acotado, el siguiente paso para determinar la solución es la obtención de sus puntos extremos, la cual puede verse en la figura 4. Finalmente, la solución al problema puede obtenerse mediante la evaluación de la función objetivo en los puntos extremos o bien, mediante el desplazamiento de la función objetivo por la región factible. Se consideran las dos opciones que se muestran en las figuras 5 y 6. 2.2. Transformación de un problema de Programación Lineal a forma estándar. El primer paso para la resolución de un problema de P. L. mediante el algoritmo Simplex es su transformación a forma estándar mediante el cambio, si es necesario, a un problema de maximizar y/o la incorporación, en su caso, de variables excedentes y artificiales además de las de holgura. Debido a la dificultad que suelen encontrar los alumnos para realizar tal transformación y decidir el algoritmo adecuado para resolver el problema transformado, se ha realizado una segunda aplicación interactiva en la que el alumno puede seleccionar en primer lugar el tipo de problema al que se enfrenta (figura 7) y, a continuación el tipo de restricciones de la que dispone (figura 8). En todo momento se le guía mediante los pasos a seguir para transformar el problema de partida a uno en forma estándar y, finalmente el procedimiento que debe aplicar en cada caso. En la figura 9 puede verse una situación de un problema de partida de tipo minimizar y con restricciones únicamente del tipo menor o igual; en este caso se le indica como transformar el problema a uno de tipo maximizar, cómo transformar las restricciones de menor o igual en igualdades mediante la incorporación de variables de holgura y, por último, se le indica que puede resolver el problema transformado mediante el algoritmo Simplex. Por otra parte, en la figura 10 se
173 plantea un problema de maximizar con los tres tipos de restricciones posibles. En este caso, se le indica cómo debe actuar ante cada una de las posibles restricciones: incorporar un variable de holgura por cada restricción de menor o igual, una variable artificial por cada restricción en igualdad y una excedente y una artificial por cada una del tipo mayor o igual. Finalmente, se le indica que debe aplicar el método de la M o el método de las dos fases para resolver el problema transformado. Figura 1: Selección del tipo de problema para su resolu- Figura 2: Pasos a seguir en la resolución gráfica de un ción gráfica. problema de Programación Lineal. Figura 3: Un paso en la construcción de la región facti ble Figura 4: Determinación de los puntos extremos en un de un problema de Programación Lineal. problema de Programación Lineal. Figura 5: Obtención de la solución de un problema de Figura 6: Obtención de la solución de un problema de P. L. mediante la evaluación de la función objetivo en P. L. mediante el desplazamiento de la función objetivo los puntos extremos. por la región factible.
174 Figura 7: Selección del tipo de problema para la trans- Figura 8: Selección del tipo de restricciones para la trans- formación de un problema de P. L. a forma estándar. formación de un problema de P. L. a forma estándar. Figura 9: Indicación de los pasos a seguir para tranfor- Figura 10: Indicación de los pasos a seguir para transfor- mar un problema de P.L. (de minimizar y con restriccio- mar un problema de P.L. (de maximizar y con los tres ti-nes de menor o igual) a forma estándar. pos de restricciones) a forma estándar. 2.3. Construcción de la tabla inicial del método Simplex. Una vez que el alumno ha adquirido la destreza para transformar cualquier problema de Programación Lineal a forma estándar se enfrenta con el problema de su resolución y el primer paso que debe llevar a cabo es la construcción de la primera tabla del Simplex. Por ello, el siguiente material interactivo que hemos realizado muestra de una forma visualmente atractiva (con desplazamientos interactivos) cómo disponer los elementos necesarios para la construcción de dicha tabla inicial, identificando las variables básicas y la solución básica inicial. Se han distinguido los siguientes pasos: determinación del número de filas y columnas de la tabla (figura 11), rellenado del interior de la tabla con las tasas de uso y coeficientes de las variables introducidas (figura 12), inclusión de los costos (figura 13), identificación de las variables básicas (figura 14), identificación de los costes básicos (figura 15) y, finalmente, identificación de la solución básica inicial (figura 16). 2.4. Resolución interactiva del Simplex. El último de los materiales docentes interactivos que presentamos consiste en la resolución interactiva de ejemplos concretos de un problema de P.L. mediante el método Simplex. De la misma forma que en el caso de la resolución gráfica el alumno selecciona en primer lugar el tipo de ejemplo concreto, del cual se le va a guiar de forma interactiva en su resolución, entre los disponibles asociados a cada una de las posibles situaciones que se pueden presentar. Debido a las múltiples posibilidades que hay, hemos optado por mostrar de forma detallada un ejemplo con solución óptima única y, al final, comentaremos cómo se tratan algunas de las otras situaciones.
175 Figura 11: Determinación del número de filas y Figura 12: Rellenado de la tabla inicial del Simplex con columnas en la construcción de la tabla inicial del las tasas de uso y coeficientes de las nuevas variables. método Simplex. Figura 13: Inclusión de los costos en la tabla inicial Figura 14: Identificación de las variables básicas en del método Simplex. la tabla inicial del método Simplex. Figura 15: Identificación de los costos básicos en la Figura 16: Identificación de la solución básica inicial tabla inicial del método Simplex. en la tabla inicial del método Simplex. Así, partiendo de la tabla inicial para dicho problema la primera cuestión que se plantea al alumno es si la solución básica factible inicial es óptima, ante la cual puede seleccionar dos opciones: si el alumno cree que es capaz de responder a esta pregunta debe elegir el botón Continuar y comprobar, o bien, no sabe, en cuyo caso debe seleccionar el botón Necesito ayuda (figura 17). Si el alumno selecciona la opción Continuar y comprobar, se le suministra la solución, sin detalles, a la pregunta propuesta (figura 18); si por el contrario selecciona Necesito ayuda, se le explica de forma detallada y con animaciones cómo realizar los cálculos necesarios y comprobar las condiciones necesarias para llegar a la respuesta adecuada (figuras 19, 20, 21 y 22). Además en el primer caso puede optar por la opción Volver si comprueba que su respuesta no era la adecuada y debe seleccionar el botón Necesito ayuda.
View other sources Hide other sources MATERIALES INTERACTIVOS PARA LA RESOLUCIÓN DE UN P...
M.J. García-Ligero, P. Román
Diseño de un modelo matemático para el despacho de vehículos de emergencias médicas en Colombia
Alvaro José, Rengifo Campo, María Gulnara, Baldoquin De, La Peña, John Wilmer Escobar
Programación lineal / H.M. Mora Escobar.

References: RESOLUCIÓN 
 RESOLUCIÓN 
 RESOLUCIÓN 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 RESOLUCIÓN