• Author / Uploaded
• Juan Carlos Polinario Damian

Citation preview

MÉTODO de ASIGNACIÓN: El problema de asignación tiene que ver con la asignación de tareas a empleados, de territorios a vendedores, de contratos a postores o de trabajos a plantas. Al aplicar el método de transporte y el método de asignación la gerencia está buscando una ruta de distribución o una asignación que optimizará algún objetivo; éste puede se la minimización del costo total, la maximización de las utilidades o la minimización del tiempo total involucrado. Al igual que el método de transporte el método de asignación es computacionalmente más eficiente que el método simplex para una clase especial de problemas. El método de asignación también conocido como la Técnica de flood o el método Húngaro de asignación. Hay básicamente tres pasos en este método Determine la tabla de costo de oportunidad: Reste el elemento del costo más bajo en cada columna de la tabla de costo dada, de todo los elementos en esa columna. Reste el asiento más bajo en cada renglón de la tabla obtenida en la parte 1.1 de todos los números en ese renglón. Determine si se puede hacer una asignación óptima: El procedimiento es dibujar líneas rectas (verticales y horizontales) a través de la tabla de costos total de oportunidad, de tal manera que se minimice el número de líneas necesarias para cubrir todos los cuadros CERO. Si el número de líneas dibujadas es menor que el número de renglones o columnas, no se puede hacer una asignación óptimas y el problema no está resuelto. Revise la tabla de costo total de oportunidad. Seleccione el número más pequeño en la tabla no cubierto, por una línea recta y reste este número de todos los números no cubiertos por una línea recta. Añada este mismo número a los números que están en la intersección de dos líneas cualesquiera. Regrese al paso 2 . II. ASIGNACIÓN DE TRABAJOS O CONTRATO DE TAREAS El alumno elige los trabajos o las tareas que realiza individualmente o en pequeños grupos, a fin de ejercitar conocimientos y usar capacidades. Están (o quedan) formulados generalmente por escrito y, cuando es posible, integran aspectos intelectuales, sociales, artesanales o artísticos. Otras denominaciones del modelo de trabajo o contrato de aprendizaje: Enseñanza activa; método de actividades; asignación de trabajo; estudio supervisado; aprender haciendo; método de tareas; método de proyectos;

talleres de arquitectura o pasos prácticos (en un laboratorio). Active/activity method; active-based method; the method of learning by doing; assignment method; assignment seminar learning; assignment laboratory; method or projects method. Variantes _ Método Montessori (usado principalmente en escuelas básicas) _ Plan Dalton, contrato de aprendizaje y Plan Winnetka ( se usan, de preferencia, en educación media) _ Plan Jena ( impulsado por Peter Peterson en Alemania en todos los niveles) _ Seminario de proyecto o seminario activo (especialmente en la universidad) _ Método del rendimiento valorado; método del texto-conductor y UDIS Método de trabajos El modelo didáctico “método de trabajo” suele usar una distribución del espacio distinta de las filas tradicionales usadas en el método frontal. Los estudiantes se sientan en pequeños grupos cada uno alrededor de su respectiva mesa y, en el Plan Dalton, algunos pueden estar en la biblioteca o en el jardín. Se dispone de bastantes medios de trabajo que suelen están colocados en las paredes. También hay un lugar para la exposición del producto. La sala de clases puede ser un pequeño taller. Se suelen oír conversaciones entre los estudiantes durante la clase y es bueno que ocurran. El profesor a veces se sienta en su mesa, pero suele transitar entre los estudiantes o ir a un grupo que pida ayuda. Esta forma de clase se desarrolló a principios del siglo XX como una reacción a las tradicionales clases frontales. Buscó integrar actividades y dar la posibilidad de un trabajo individualizado frente a la usual pasividad y estandarización. Además, trata de combinar el trabajo mental con

manual; no sólo un pensamiento reproductivo, sino que también una actividad productiva, para desarrollar así una personalidad integral del alumno. Los representantes del método de trabajos o tareas formaron el primer movimiento pedagógico del siglo XX. Los nombres más conocidos en Estados Unidos son John Dewey (cuya filosofía educacional es la base de este método); William Kilpatrick, Helen Parkhurst (Plan Dalton) y Carleton Washburne (Plan Winnetka). En otros países europeos son Maria Montessori (Italia), Adolph Ferriere (Suiza), Ovide Decroly (Bélgica), Celestin Freinet (Francia) y Kerschensteiner, Gaudig y Peter Peterson (con el Plan Jena) en Alemania. Más adelante se desarrolló el “método del texto conductor”, OIT que difundió como “cartillas de trabajo”, especialmente para la formación de profesionales (nivel superior). En el perfeccionamiento en el trabajo (por ejemplo, de los docentes) en la enseñanza a distancia se han utilizado variantes del método de trabajo o de tareas en forma de “aprendizaje mediante la realización de tareas” que puedan estar asociadas al mismo trabajo de la persona que se perfecciona. Cuatro Principios didácticos identificados en este método _ Aprendizaje independiente (autodirigido, es decir, diferente del aprendizaje guiado) en que los que aprenden eligen las tareas y, a veces, el tiempo, procedimientos y orientaciones. A veces hay autoevaluación de procesos y productos. _ Aprendizaje singular (personalizado o independiente) gracias a una “diferenciación interna” de la clase a fin de atender diferencias en intereses y habilidades y desarrollar la cooperación y valores democráticos (ser y convivir). _ Aprendizaje globalizado, gracias a la integración del trabajo manual e intelectual y de temas “transversales”, es decir, de otras asignaturas

(el alumno al trabajar con la realidad abarca, a veces, todas las asignaturas en un pensamiento interdisciplinario). _ Aprendizaje aplicado, ya que une la realización de tareas de aprendizaje formuladas en forma escrita (hacer) con la adquisición de conocimientos de los medios de información o el uso de conocimientos ya existentes (previos). Ambiente del aprendizaje Cuando se lleva a cabo en un local cerrado cada alumno debe tener a disposición por lo menos 4 metros cuadrados. Para generar un ambiente de aprendizaje que facilite la adquisición (transmisión) del conocimiento y el desarrollo de las competencias se necesita: (i) Textos (por ejemplo, textos de orientación , obras de consulta o algún “reader”); (ii) Medios audiovisuales (por ejemplo, cuadros, filmes, vídeos o radiocassetes) (iii) Software con el acceso a Internet y (iv) Objetos materiales y herramientas (para elaboración de materiales o información). Tareas y metas de aprendizaje Las tareas de aprendizaje estructuradas y precisadas de manera minuciosa constituyen el núcleo del método de tareas. Se presenta al alumno un grupo tareas seleccionadas como importantes y se lo invita —individualmente, con su compañero o en un pequeño grupo— a realizar la que elija (se suelen presentar como alternativas) en forma independiente. Las tareas pueden consistir en: (i) solucionar un problema “bien acotado”, de complejidad compatible con la experiencia previa del alumno, que implique producir algún producto o ejecutar una actividad, (ii) integrar conocimientos (apropiarse de ellos) mientras realiza lo anteriormente mencionado (se suele ofrecer consejo y supervisión), (iii) presentar los resultados de la persona o del grupo y (iv) reflexionar, discutir, valorar y a su vez fijar (asegurar) estos resultados y la capacidad de usarlos. Competencias que promueve el modelo de asignación de trabajos

El método de trabajos o tareas tiene como objetivo que el alumno aprecie el valor del aprendizaje en la acción, incluso al conversar sobre un tema con otros y no adquiera sólo un conocimiento orientado (transmitido). Cada vez que el alumno este con un compañero de trabajo o con un pequeño grupo tiene que desarrollar competencias sociales. Finalmente darse cuenta que sí desea lograr competencias adicionales, puede realizar un aprendizaje de nuevas tareas en forma individual o en forma colectiva, gracias a una motivación propia y al control de sí mismo. Cinco fases de la correcta aplicación del modelo _ Fase de orientación. Ofrece una visión global del contexto o perspectiva en que se llevan a cabo las tareas. Esta fase aclara dudas y vincula con conocimientos previos y busca despertar el interés del alumno. Junto con introducir en el trabajo propuesto proporciona antecedentes sobre recursos, materiales e información útiles para el trabajo. Suele incluir una definición de los criterios para evaluar los resultados. Fase de planificación (identificación, selección y formulación de la tarea). Se debe tener en cuenta tanto los aspectos objetivos como los subjetivos, ya que el alumno participa o colabora en el proceso de definir las tareas. Por ejemplo, debe tener tiempo disponible para planear lo que va a hacer (decisiones). La distribución de tareas en un grupo se debe conversar y a menudo queda una constancia escrita . Ocasionalmente se puede especificar en un “contrato de aprendizaje”. _ Fase de interacción (realización del trabajo). Constituye el núcleo del método de tareas. En esta fase los alumnos trabajan individualmente o en pequeños grupos, en la misma o diferentes tareas, con ayuda de información escrita y, a veces, otros medios, hasta obtener los resultados. En ciertas ocasiones pueden recibir consejos de otras personas. Los resultados se presentan en forma escrita, como un producto (una

planta que creció con estímulos muy precisos, un diario mural, un dibujo o la maqueta de un proyecto arquitectónico) o como un proceso, en el caso de una dramatización. En cada caso puede incluir algún control de calidad. _ Fase de presentación. Los estudiantes presentan sus resultados al curso, a un público general o un jurado, para que así todos (presentadores y público) aprendan de todo lo acontecido en la aplicación del modelo. Es importante que se conversen los puntos de vista comunes y superiores. _ Fase de evaluación “formativa”. Las reflexiones sistemáticas sobre los productos o las soluciones encontradas y la exposición del trabajo o tarea se comparten con los demás en un proceso de intercambio de las experiencias vividas. Estos resultados se comparan con los criterios acordados previamente para generar una crítica formativa. Finalmente, se proponen posibles mejorías y comentan las perspectivas futuras abiertas por el trabajo realizado. Rol de los alumnos En este método el rol de los alumnos es un actor responsable, pero limitado (dentro de un marco dado). Al desempeñarlo ellos son, simultáneamente, compañeros y miembros de un grupo, competidores y “profesores para los demás”; así como también son evaluadores de las soluciones o productos de los demás participante. Esta variedad de roles corresponde a la variedad de las perspectivas, que pueden ocupar los alumnos en relación a las tareas del aprendizaje. A diferencia de las “acciones responsables en situaciones reales” en este modelo su responsabilidad está limitada ya que las consecuencias de sus acciones, por lo general, no van más allá de la sala de clases y , además, comparten las tareas con su grupo. Rol del profesor o facilitador En este método el profesor actúa como organizador, moderador, estimulador,

experto y consejero. Los alumnos, en cuanto miembros del grupo o competidores, también son ayudantes y asistentes del aprendizaje. Ámbito institucional de aplicación Este método se puede aplicar en cualquier escuela en la que se aplique el método frontal. Sin embargo, existen diferentes variantes de “métodos de asignación de tareas” para las escuelas básicas, los niveles medios o las instituciones de nivel superior. Ámbitos del conocimiento en el que el modelo es útil En casi todos los ámbitos del conocimiento hay ejemplos de aplicación del método de tareas. En especial, es útil que el alumno de las clases de ciencias naturales realice este tipo de ejercicio. Aunque también hay un gran número de ejemplos en las asignaturas de áreas sociales y espirituales. El balance que se logra, en la adquisición de conocimientos y capacidades, facilita una asimilación (o dominio) eficiente e independiente. Tipos de grupos a los que se puede aplicar A través de este método es posible lograr los objetivos de cualquier grupo, en la medida que el grupo tenga las capacidades básicas en los aspectos mentales, espirituales, sociales y manuales, necesarios para cumplir o completar las tareas. Momento del desarrollo de un curso ( programa) en que conviene utilizarlo El método de tareas juega, sobretodo, un importante rol en las fases intermedias de los cursos. En especial, cuando se busca la adquisición (y la primera aplicación) de destrezas o habilidades. Este método se puede usar tanto como una alternativa o como un complemento para las clases frontales. Comentarios sobre algunas variantes El método del texto conductor (pasos prácticos y cuadernillos de aprendizaje) ha sido bastante usado en América Latina en las instituciones

de formación profesional, tales como SENA y SENAI y difundido por OIT. Aquí los alumnos (por ejemplo, aprendices) realizan tareas de aprendizaje en un laboratorio o en una práctica en terreno, a partir de instrucciones escritas, es decir, difiere del método de tareas que comúnmente se realiza en la sala de clase o en locales del colegio. Generalmente realizan estas tareas solos (mientras que el método de tareas se suele aplicar en parejas o en pequeños grupos). Los diseños didácticos que emplea esta variante, presentan las descripciones muy claras de las tareas y se debe asegurar que el alumno tenga el acceso a los medios y recursos necesarios para ejecutarlas. El modelo de guías de trabajo o cartillas de exigencias individuales se suele aplicar en las instituciones de formadores de profesionales. Este modelo se divide en siete fases: (i) Informar, (ii) Planificar, (iii) Decidir, (iv) Realizar, (v) Funciones de supervisión y control, (vi) Evaluación y (vii) Acumulación en banco de datos para uso de otros estudiantes. El contrato de aprendizaje organiza y estructura actividades individuales de aprendizaje a partir de una descripción precisa de las actividades que propone realizar un alumno (Plan Dalton) Alumno y profesor se ponen de acuerdo sobre las actividades que se realizarán, se escriben los términos del acuerdo en una forma precisa y ambos firman ese contrato. Los contratos de aprendizaje no tienen consecuencias legales. En un contrato de aprendizaje se describen aspectos como: especificar por lo menos una de las competencias que se debe lograr como resultado del acuerdo; actividades de aprendizaje; elementos del ambiente de aprendizaje; distribución del tiempo; modificación de evaluación o autoevaluación de los éxitos del alumno; oportunidades para aconsejar el alumno; entrevistas para evaluar el aprendizaje; encuentros con los profesores; documentación del progreso del aprendizaje y posibles actividades de cierre. El método Montessori se concentra en la educación preescolar y primaria.

Como elementos del ambiente de aprendizaje emplean, preferentemente, materiales de juego estructurados que permiten el aprendizaje independiente. Este modelo acentúa el aspecto sensible en el proceso del desarrollo mental y espiritual de los niños. Otras variantes del modelo didáctico “método de asignación de tareas” desarrollado a principios del siglo XX son el Plan-Winnetka y el Plan-Jena y el Círculo de trabajo UDIS (Unterrichtsdifferenzierug in der Sekundarstufe I) que diferencia las clases en segundo grado en Alemania (equivalente a la educación de los grados 4to a 8to en América Latina). Los proyectos UDIS desarrollan clases integradas (incluyen varias asignaturas). La diferenciación interna de las clases toma en cuenta el rendimiento del alumno y su interés. Incluye la ejecución de técnicas de trabajo tanto en las formas de trabajo individuales como en grupo. Los fundamentos de las experiencias de “open classrooms” realizados en los Estados Unidos se encuentra en el “modelo de trabajos”. También ha dado origen a la metodología de Pierre Faure usada en los colegios ignacianos. BIBLIOGRAFÍA Champagne, D.W., Goldman, R. M., 1975. Handbook for Managing Individualized Learning in the Classroom, Englewood Cliffs (Educational Technology Publications) pp 5- 201. Metzner, R.C., 1980. The Core Package. Englewood Cliffs, New Jersey (Educational Technology Publications), pp 107. El tema central de los “core packages” son tareas (formuladas por escrito) de una disciplina especial que presentan un tema ligado a las demás asignaturas. Los “core packages” contienen además de los recursos y medios de ayuda, que se requieren (o pueden ser utilizados) para solucionar las tareas. Race P., 1989, 1990. The Open Learning Handbook. Selecting and Supporting Open Learning Materials, london (Kogan Page)/New York (Nichols Publishig) pp. 156.

Referencias para navegar en Internet por sitios relacionados con este método: • Maria Montessori http://www.montessori.educ/method.html The Montessori “Method” of bringing up and educating children. http:/7orbita.starmedia.com/colgv/montesso.html ¿Qué es el método Montessori?, ¿Qué son los materiales Montessori? http://www.civila.com/educacion/articulos/comparaciones-montessori.html Algunas comparaciones del Método Montessori con el método tradicional (método frontal) http://www.sistema.itesm.mx/va/planes90/sinteticos/Analiticos/ cc90004.html Objetivos generales del curso, temas y subtemas según contenidos, objetivos específicos de aprendizaje por tema, metodologías sugeridas, tiempo estimado según el método Montessori. • John Dewey http://utm.edu/research/iep/d/dewey.htm. Works, Theory of Knowlegde, Etical and Social Theory, Critical Reception and Influence. • Celestin Freinet http://www.freinet.org/icem/history.htm History of Freinet Pedagogy, The Esencial Concepts of Freinet Pedagogy, the Freinet Myth and the Influence of the new Education movement. http://www.xerais.es/htm/online/n030/020.html Técnicas Freinet da Escola moderna

Problema de la asignación

Este artículo o sección necesita una revisión de ortografía y gramática. Puedes colaborar editándolo. Cuando se haya corregido, puedes borrar este aviso. Puedes ayudarte del corrector ortográfico, activándolo en: Mis preferencias → Accesorios → Navegación → El corrector ortográfico resalta errores ortográficos con un fondo rojo. El problema de la asignación es encontrar un emparejamiento de peso máximo en un grafo bipartido ponderado. Es uno de los problemas fundamentales de optimización combinatoria de la rama de optimización o investigación operativa en matemática. Una descripción apropiada de lo que trata de lograr el modelo de asignación es: “La mejor persona para el trabajo” El problema de asignación tiene que ver con la asignación de tareas a empleados, de territorios a vendedores, de contratos a postores o de trabajos a plantas, etc. En otras palabras, a la disposición de algunos recursos(máquinas o personas) para la realización de ciertos productos a 'costo mínimo. Una definición más formal pudiera ser: Problema de Asignación: Caso particular del problema de transporte donde los asignados son recursos destinados a la realización de tareas, los asignados pueden ser personas, máquinas, vehículos, plantas o períodos de tiempo. En estos problemas la oferta en cada origen es de valor 1 y la demanda en cada destino es también de valor 1. Índice [ocultar] 1Historia 2Definición del problema de asignación 3Características 4Diferencias con el Modelo de Transporte y Asignación 5Formas de representación de un problema de asignación 6Asignación Inicial 7Elementos del problema de asignación 8Red 9Casos especiales 10Método de Selección 11Balanceado

12Algoritmos y generalizaciones 13Modelo binario 14Teorema Fundamental de la Asignación 15Definición matemática formal 16Método Húngaro 17Caso especial al aplicar el Método Húngaro cuando se trata de Maximizar 18Método de Flood 19Ejemplos 20Ejemplo 1 20.1Ejemplo 1: Balanceando 21Ejemplo 2 21.1Ejemplo 2: Modelo de Programación Lineal 21.2Ejemplo 2: Matriz de costos 21.3Ejemplo 2: Solución por el Método Húngaro 21.4Ejemplo 2: Interpretación de resultados 22Ejemplo 3 22.1Ejemplo 3: Modelo de Programación Lineal 22.2Ejemplo 3: Tabla de Transporte 22.3Ejemplo 3: Solución por el Método Húngaro 22.4Ejemplo 3: Interpretación de resultados 23Ejemplo 4 23.1Ejemplo 4: Tabla de asignación 23.2Ejemplo 4: Red 23.3Ejemplo 4: Modelo de Programación Lineal 23.4Ejemplo 4: Solución 23.5Ejemplo 4: Interpretación de resultados 24Ejemplo 5 24.1Ejemplo 5: Tabla de asignación 24.2Ejemplo 5: Solución

25Ejemplo 6 25.1Ejemplo 6: Tabla de asignación 25.2Ejemplo 6: Modelo de programación lineal 25.3Ejemplo 6: Interpretación de resultados 26Ejemplo 7 26.1Ejemplo 7: Modelo de Programación lineal 26.2Ejemplo 7: Matriz de costos 26.3Ejemplo 7: Solución por medio del Método Húngaro 26.4Ejemplo 7: Interpretación de resultados 27Ejemplo 8 27.1Ejemplo 8: Modelo de Programación Lineal 27.2Ejemplo 8: Tabla de transporte 27.3Ejemplo 8: Solución por medio del Método Húngaro 27.4Ejemplo 8: Interpretación de resultados 28Ejemplo 9 28.1Ejemplo 9: Modelo de Programación Lineal 28.2Ejemplo 9: Solución por medio del Método Húngaro 28.3Ejemplo 9: Interpretación de resultados 29Ejemplo 10 29.1Ejemplo 10: Tabla de asignación 29.2Ejemplo 10: Solución por medio del Método Húngaro 30Ejemplo 10: Interpretación de resultados 31Ejemplo 11 32Ejemplo 12 32.1Ejemplo 12: Solución por medio del Método Húngaro 33Ejemplo 13: Ejemplo con oferta ficticia 34Ejemplo 14 35Referencias Historia[editar]

El problema de asignación tuvo su origen en la revolución industrial, ya que el surgimiento de las máquinas hizo que fuera necesario asignar una tarea a un trabajador. Thomas Jefferson en 1792 lo sugirió para asignar un representante a cada estado, pero formalmente aparece este problema en 1941, cuando F.L. Hitchcook publica una solución analítica del problema, pero no es hasta 1955 cuando Harold W. Kuhn plantea el Método húngaro, que fue posteriormente revisado por James Munkres en 1957; dicho método está basado fundamentalmente en los primeros trabajos de otros dos matemáticos húngaros: Dénes Köning y Jenö Egervary. Hoy en día en pleno apogeo de la globalización este problema surge cada vez con mayor frecuencia el uso de este problema de la rama de la investigación de operaciones, podemos decir que es la aplicación del método científico para asignar los recursos o actividades de forma eficaz, en la gestión y organización de sistemas complejos, su objetivo es ayudar a la toma de decisiones. Definición del problema de asignación[editar] En su forma más general, el problema es como sigue: Hay un número de agentes y un número de tareas. Cualquier agente puede ser asignado para desarrollar cualquier tarea, contrayendo algún coste que puede variar dependiendo del agente y la tarea asignados. Es necesario para desarrollar todas las tareas asignar un solo agente a cada tarea para que el coste total del asignación sea minimizado. Este tipo de problemas son lineales, con una estructura de transporte, sólo que la oferta en cada origen es de valor uno y la demanda en cada destino es también de valor uno. Sería muy ineficiente resolver este tipo de problemas por medio del método simplex o por medio del de transporte. Debido a la estructura propia de los problemas de asignación, existen métodos de solución llamados algoritmos de asignación que son más eficientes que el simplex o que el método de transporte. Los problemas de asignación presentan una estructura similar a los de transporte, pero con dos diferencias: asocian igual número de orígenes con igual número de demandas y las ofertas en cada origen es de valor uno, como lo es la demanda en cada destino. La restricción importante para cada agente es que será asignado a una y solo una tarea. Características[editar] El problema de asignación presenta las siguientes características: El Problema de Asignación debe estar equilibrado, es decir, que las ofertas y las demandas sean igual a 1. Un elemento importante para el problema de asignación es la matriz de costos, si el número de renglones o columnas no son iguales el problema esta desbalanceado y se puede obtener una solución incorrecta, para obtener una solución correcta la matriz debe ser cuadrada. Si el número de agentes y tareas son iguales y el coste total de la asignación para todas las tareas es igual a la suma de los costes de cada agente (o la suma de los costes de cada tarea, que es lo mismo en este caso), entonces el problema es llamado problema de asignación lineal.

Normalmente, cuando hablamos de problema de asignaciónsin ninguna matización adicional, nos referimos al problema de asignación lineal. Oferta: Cantidad que representa la disponibilidad del artículo en la fuente/fábrica de donde proviene. 4 Demanda: Cantidad de artículos que necesita recibir el destino para cumplir sus necesidades. 4 Diferencias con el Modelo de Transporte y Asignación[editar] Los problemas de asignación son un caso particular de los problemas de transporte y constituyen la clase más sencilla de los problemas lineales, en el cual los trabajadores representan las fuentes y los puestos representan los destinos. En el problema de transporte existen m orígenes y n destinos, y el flujo se realiza desde un origen hacia cada uno de los diferentes destinos. Si en este caso permitimos el flujo en ambos sentidos (de origen a destino y destino a origen) se puede hablar de un problema de m + n orígenes y m + n destinos. A este tipo de problemas se les conoce con el nombre de problemas de transbordo (transhipment problems) o transporte con nodos intermedios. En el caso más general, cada punto origen o destino pude ser un punto de transbordo, es decir, cada origen puede evitar o transportar a otros orígenes o a distintos; y los destinos pueden transportar a su vez a otros destinos o volver a los orígenes. Un punto conserva su identidad, origen o destino, solamente cuando sea respectivamente, un punto que originalmente disponga de un suministro o un punto que tenga una demanda a satisfacer. En los problemas de asignación las ofertas en cada origen es de valor uno, como lo es la demanda en cada destino; una gran diferencia con respecto a los problemas de transporte. Formas de representación de un problema de asignación[editar] Red. Modelo de programación lineal. Matriz de costos. Tabla de transporte. Asignación Inicial[editar] Implica asignar números a las celdas para satisfacer las restricciones de oferta y demanda. Para realizar esto se puede emplear alguno de estos métodos: El método de la esquina noroccidental, el método de menor costo y el método de aproximación de Vogel. Elementos del problema de asignación[editar]

Tabla de transporte Tabla de transporte: Otra forma de plantear el problema de transporte ( recordemos que el problema de asignación es un caso especial del de transporte) es mediante una tabla llamada tabla de transporte, la cual tiene forma de matriz donde los renglones representan las fuentes y las columnas los destinos o trabajos. En las casillas que se encuentran en la esquina se colocan los coeficientes de costo. Una vez realizado esto, utilizamos alguno de los métodos (vogel, esquina noroeste, costos mínimos) para obtener una solución inicial Donde no exista un coeficiente de costo se le anota una M. 4 Matriz de costos: Es una matriz cuadrada de n*n, donde cada elemento representa el costo de asignar el enésimo trabajador al enésimo trabajo; renglones = trabajadores. Es la tabla en donde, se identifica, se evalúa y se cuantifica los beneficios económicos, costos y riesgos de los productos/servicios, después de definir la necesidad el alcance y el alineamiento estratégico de los productos/servicios, en donde se evalúa el beneficio total de la propiedad (características), una vez creada la matriz se demuestra el valor económico para la realización del producto o servicio correspondiente. 4 Matriz de Costos Reducida Es la matriz que se obtiene después de haber restado el elemento más pequeño a cada renglón (reducción de renglones) y restarle a esa nueva matriz el elemento más pequeño a cada columna (reducción de columnas). Distribución óptima: Sean un conjunto de fragmentos F = {F1, F2,..., Fn} y una red formada por el conjunto de sitios S = {S1, S2,..., Sm} en la cual un conjunto de aplicaciones Q = {q1, q2,..., qq} se ejecutan. El problema de la asignación implica encontrar la distribución óptima de F sobre S. (multi) Método Simplex: Método de solución de los problemas de programación lineal donde se obtiene una solución factible y óptima (en donde se pueden obtener resultados como solución múltiple, solución no acotada, o que el problema no tenga solución). Solución Óptima: El conjunto de los vértices del recinto se denomina conjunto de soluciones factibles básicas y el vértice donde se presenta la solución óptima se llama solución máxima (o mínima según el caso). Red[editar] Muchos problemas de redes son más que una representación abstracta de procesos o actividades, tales como el camino crítico en las actividades entre las redes de un proyecto. Para definir lo que es una red necesitaremos saber que es un nodo. Nodo: Es uno de los elementos de una lista enlazada, de un árbol o de un grafo. Cada nodo será una estructura o registro que dispondrá de varios campos, y al menos uno de esos campos será un puntero referencia a otro nodo, de forma que, conocido un nodo, a partir de esa referencia, será posible en teoría tener acceso a otros nodos de la estructura.

Una red consiste en una serie de nodos enlazados con arcos (o ramas). La notación para describir una red es (N,A), donde N es el conjunto de nodos y A es el conjunto de

arcos. Casos especiales[editar] Oferta y demanda desiguales. Cuando la oferta y la demanda son desiguales, se asigna una actividad ficticia con un costo de cero para mantener la condición de método que deben ser igual número de ofertas y demandas Problemas de Maximización. Considere un problema de asignación en el que la respuesta a cada asignación es una utilidad en vez de un costo. Considere la matriz de utilidades del problema como la característica nueva la cual consiste en que el número que aparece en cada celdilla representa un beneficio en lugar de un costo. Problemas con asignación inaceptable. Supóngase que se está resolviendo un problema de asignación y que se sabe que ciertas asignaciones son inaceptables. Para alcanzar esta meta, simplemente asigna un costo arbitrariamente grande representado mediante la letra M. M es un número tan grande que si se le resta un número finito cualquiera, queda todavía un valor mayor que los demás. Problema de selección: Es un caso especial donde la función u objetivo es maximizar pero el problema se trata igual que una minimización al multiplicar por (-1). Método de Selección[editar] Cuando el problema de asignación es de maximización se le llama problema de selección Balanceado[editar] Se dice que un problema de asignación se encuentra balanceado, si los recursos totales son iguales a las demandas totales, en caso contrario se dice que no está balanceado el problema. Además en el modelo, m = n (obtener una matriz cuadrada), en donde m número de renglones y n es número de columnas. Para lograr que el modelo este balanceado se pueden agregar trabajadores/tareas ficticias con costos de cero. Algoritmos y generalizaciones[editar]

El algoritmo Húngaro es uno de los muchos algoritmos que han sido diseñados para resolver el problema del asignación lineal con un tiempo acotado por una expresión polinómica del número de agentes. El problema del asignación es un caso especial del problema del transportador, que es un caso especial del problema del flujo de coste mínimo. El problema de asignación también puede ser resuelto por medio del algoritmo simplex (creado en 1947 por el matemático George Dantzig). El método del simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables, es un método iterativo que permite ir mejorando la solución en cada paso. Cada especialización tiene algoritmos más eficientes tomando ventaja de su estructura espacial. Si Xij=1 Si se asigna el trabajador i a la tarea j. Si Xij=0 No se asigna el trabajador i a la tarea j. Cij: Costo de asignar al trabajador i la tarea j. Parámetro M: M es un número muy grande en los problemas de asignación se utiliza para representar que al trabajador i no se le puede asignar la tarea j. Modelo binario[editar] Problema Binario: Son los problemas en los cuales la variable Xij solo puede tomar valores de 0 y 1; el problema de asignación es un problema binario. Es un modelo de programación lineal donde en la solución las variables sólo pueden tomar los valores de cero o uno.

Teorema Fundamental de la Asignación[editar] Si a todos los elementos de una fila o de una columna de una matriz de rendimientos se le suma o se le resta una cantidad constante la asignación óptima no varia. Definición matemática formal[editar] La definición formal del problema del asignación (o problema asignación lineal) es Dados dos conjuntos, A y T. de igual tamaño, juntos con una función peso C: A × T → R. Encuentra una biyección f: A → T como la función de coste:

está minimizada. Normalmente la función peso es vista como una matriz cuadrada de valores reales C, con lo que el coste de la función queda así:

El problema es "lineal" porque la función coste a optimizar así como todas las restricciones contienen solo términos lineales. Método Húngaro[editar] Pasos para el método húngaro Paso 1: Encontrar primero el elemento más pequeño en cada fila de la matriz de costos m*m; se debe construir una nueva matriz al restar de cada costo el costo mínimo de cada fila; encontrar para esta nueva matriz, el costo mínimo en cada columna. A continuación se debe construir una nueva matriz (denominada matriz de costos reducidos) al restar de cada costo el costo mínimo de su columna. Paso 2: Consiste en trazar el número mínimo de líneas (horizontales o verticales o ambas únicamente de esas maneras) que se requieren para cubrir todos los ceros en la matriz de costos reducidos; si se necesitan m líneas para cubrir todos los ceros, se tiene una solución óptima entre los ceros cubiertos de la matriz. Si se requieren menos de m líneas para cubrir todos los ceros, se debe continuar con el paso 3. El número de líneas para cubrir los ceros es igual a la cantidad de asignaciones que hasta ese momento se pueden realizar (En algunos textos este paso se atribuye a Flood). Paso 3: Encontrar el menor elemento diferente de cero (llamado k) en la matriz de costos reducidos, que no está cubierto por las líneas dibujadas en el paso 2; a continuación se debe restar k de cada elemento no cubierto de la matriz de costos reducidos y sumar k a cada elemento de la matriz de costos reducidos cubierto por dos líneas (intersecciones). Por último se debe regresar al paso 2. (scrib2) Paso 4: En caso de no encontrar una solución factible con los pasos anteriores aplicar entonces este: 1) Trace el número mínimo de líneas horizontales y verticales en la última matriz reducida que cubrirá TODAS las entradas cero. 2) Selecciones el elemento no cubierto más pequeño y réstelo de todos los elementos no cubiertos; después, súmelos a todos los elementos en la intersección de dos líneas. 3) Si no es posible encontrar una asignación factible entre las entradas cero resultantes, repita es paso. De lo contrario regrese al paso 3 para determinar la asignación óptima. Caso especial al aplicar el Método Húngaro cuando se trata de Maximizar[editar] Cuando hay que pasar de maximizar a minimizar en lugar de operar con el menor de toda la matriz podemos ir tomando el mayor de cada fila o columna e ir restándole todos los elementos de esa fila o columna con lo cual conseguiremos de camino obtener por lo menos un cero como mínimo en cada fila o columna. Si en alguna columna no hubiera ceros le quitamos el mayor a la columna.. Método de Flood[editar] Este método es utilizado en aquellos casos donde no se ha podido hacer una asignación óptima después de haber realiza el método húngaro.

El método consta de los siguientes pasos: Paso 1: Señalar todas las filas que no tienen una asignación. (Cuando se dice señalar puede ser una pequeña X a la izquierda de la fila o arriba de la columna) Paso 2: Señalar todas las columnas que tengan un cero en la columna señalada. Paso 3: Señalar todas las filas que tienen una asignación en las columnas indicadas. Paso 4: Repetir estos pasos hasta que no pueda señalarse más columnas o filas. (No hay más filas que no tengan asignación) Dibujar una línea por cada fila NO señalada y por cada columna SI señalada. Paso 5: Encontrar el mínimo valor de los elementos no cubiertos y restarlo a todos los elementos no cubiertos, y sumar este valor a cada elemento que se encuentre en la intersección de una línea horizontal con una línea vertical. Paso 6: Realizar la asignación como en el método húngaro. (arqui) Ejemplos[editar] Ejemplo 1[editar] Una empresa de logística cuenta con 4 máquinas para realizar 3 tareas, cada máquina realiza la tarea según el tiempo en que esta pueda ejecutarla. En la siguiente tabla se muestran los tiempos en horas para dichas tareas.

Se plantea la red de la siguiente forma:

Ejemplo 1: Balanceando[editar]

Para resolver el problema usando el método Húngaro será necesario equilibrar la tabla de costos, si se construye una tabla sobre la base de la red tendremos 4 filas ≠ 3 columnas, por tanto será necesario agregar una nueva columna con costos 0, esto significa que se añadirá una tarea falsa.

Ahora se tienen 4 filas = 4 columnas, por tanto el modelo está balanceado y listo para aplicar el método Húngaro para su solución. Ejemplo 2[editar] Machineco tiene cuatro máquinas y cuatro tareas por completar. Cada máquina se debe asignar para completar una tarea. El tiempo requerido para preparar cada máquina para completar cada tarea se muestra en la siguiente tabla. Machineco desea reducir el tiempo de preparación total necesario para completar las cuatro tareas.

Planteamiento del modelo de programación lineal Machineco debe determinar qué máquina debe asignarse a cada tarea. Xij=1 si la máquina i se asigna para satisfacer las demandas de la tarea j Xij=0 si la máquina i no se asigna para satisfacer las demandas de la tarea j Ejemplo 2: Modelo de Programación Lineal[editar] Entonces el modelo de P.L. de Machineco es el siguiente:

Las restricciones de máquina aseguran que cada máquina se asignó a una tarea, y las restricciones de trabajo aseguran que se completó cada tarea. Si Xij = 1 entonces la función objetivo tomará el tiempo requerido para preparar la máquina i para la tarea j, si Xij =0 entonces la función objetivo no tomara el tiempo requerido. Se puede notar que Machineco enfrenta un problema de transporte equilibrado en el que cada punto de suministro tiene un suministro de 1 y cada punto de demanda tiene una demanda de 1. En general el problema de asignación es un problema de transporte equilibrado en el que suministros y demandas son iguales a 1, Así, un problema de asignación se caracteriza porque se conoce el costo de asignar cada punto de suministro a cada punto de demanda. Ejemplo 2: Matriz de costos[editar]

Ejemplo 2: Solución por el Método Húngaro[editar] Paso 1: Reste el número más pequeño de cada renglón a cada número del renglón. Esto se llama reducción de renglón.

Paso 2: Reste el número más pequeño de la nueva matriz a cada número de la columna. Esto se llama reducción de columna.

Al momento de realizar los dos pasos anteriores la matriz nueva recibe el nombre de matriz reducida de costos. Paso 3: Pruebe si se puede hacer una asignación óptima, se hace mediante la determinación del número mínimo de líneas necesarias para cubrir todos los ceros.

Como el número de líneas no es igual al número de renglones no es posible hacer una asignación, en este caso se continúa con el método. Paso 4: Reste el número no cubierto más pequeño de todos los números no cubiertos de la matriz. Sume el número no cubierto más pequeño a los números que se encuentren en intersección de líneas. Los números cruzados pero que no se encuentran en intersección de líneas permanece igual.

Paso 5: Repetir los pasos 3 y 4 hasta que el número de líneas sea igual al número de renglones de la matriz.

Como el número de líneas es igual al número de renglones se tiene una solución óptima. Se puede pasar al último paso. Paso 6: Se hacen las asignaciones una a una en las posiciones que tienen elemento cero. Comience con los renglones y columnas que tienen sólo un cero. Cada renglón y columna necesita recibir exactamente una asignación, después continúe con los renglones y columnas que no han sido asignados. Continúe hasta que todos los renglones y columnas estén asignados.

Ejemplo 2: Interpretación de resultados[editar]

'z = 2 + 5 + 3 + 5 = 15' Ejemplo 3[editar] Doc Concillman reúne a un equipo de relevos para el relevo de 400 metros.Cada nadador debe nadar 100 metros de brazada de pecho, dorso, mariposa o estilo libre. Doc cree que cada nadador obtendrá los tiempos en segundos dados en la tabla. ¿Qué nadador debe nadar que estilo? Nadado Libr r e

Pech o

Maripos a

Dors o

Gary

54

54

51

53

Mark

51

57

52

52

Jim

50

53

54

56

Chet

56

54

55

53

Ejemplo 3: Modelo de Programación Lineal[editar] Min z= 54x11 + 54x12 + 51x13 + 53x14 + 51x21 + 57x22 + 52x23 + 52x24 + 50x31 + 53x32 + 54x33 + 56x34 + 56x41 + 54x42 + 55x43 + 53x44 S.A x11 + x12 + x13 + x14 = 1 x21 + x22 + x23 + x24 = 1 x31 + x32 + x33 + x34 = 1 x41 + x42 + x43 + x44 = 1 x11 + x21 + x31 + x41 = 1 x12 + x22 + x32 + x42 = 1 x13 + x23 + x33 + x43 = 1 x14 + x24 + x34 + x44 = 1 xij = {0,1}

i,j = Z

Ejemplo 3: Tabla de Transporte[editar] 1

2

3

4

1 54 54 51 53 1 2 51 57 52 52 1

3 50 53 54 56 1 4 56 54 55 53 1 1

1

1

1

1

Ejemplo 3: Solución por el Método Húngaro[editar] 1. Se escribe la matriz de costos.

2. Se escoge el número más pequeño de cada renglón y se le resta a cada número del renglón y los resultados se pone en una nueva matriz. Queda de la siguiente manera:

3. De la nueva matriz se escoge el número más pequeño de cada columna y se le resta a cada número de la columna. Queda de la siguiente manera:

4. Procedemos a encontrar el número mínimo de rectas que cubren todos los ceros de la matriz.

5.Si el número de rectas es igual al número de renglones es posible hacer una asignación, como en este caso son diferentes se hace el siguiente paso. 6. Se escoge el número más pequeño no cubierto y se le resta a los demás números no cubiertos. En los números de intersección de rectas se suma este número.

Procedemos a encontrar el número mínimo de rectas que cubren todos los ceros de la matriz.

Como el número de rectas es igual al número de renglones procedemos a asignar. Se escoge el cero donde solo este una vez en el renglón o la columna.

Así queda la asignación. Nadador Estilo 1

3

4

2

2

4

3

1

Ejemplo 3: Interpretación de resultados[editar] Con esto se hizo una asignación la cual quiere decir que: El nadador 1 hará el estilo mariposa. El nadador 4 hará el estilo pecho. El nadador 2 hará el estilo dorso. El nadador 3 hará el estilo libre. En total se harán como mínimo 207 minutos entre los 4 nadadores. Ejemplo 4[editar] Una empresa ha preseleccionado 5 candidatos para ocupar 4 puestos de trabajo en dicha empresa. Los puestos de trabajo consisten en manejar 4 máquinas diferentes (un trabajador para

cada máquina). La empresa puso a prueba a los 5 trabajadores en las 4 máquinas, realizando el mismo trabajo todos ellos en cada una de las máquinas, obteniendo los siguientes tiempos: Ejemplo 4: Tabla de asignación[editar] M á q ui n a 1

M á q ui n a 2

M á q ui n a 3

M á q ui n a 4

C a n di d at o 1

1 0

6

6

5

C a n di d at o 2

8

7

6

6

C a n di d at o 3

8

6

5

6

C a n di d

9

7

7

6

at o 4 C a n di d at o 5

8

7

6

5

Ejemplo 4: Red[editar] Comenzamos por plantear la red

Posteriormente se determina qué candidatos debe seleccionar la empresa y a qué máquinas debe asignarlos. Se determinan las variables de decisión, en este caso: Xij: acción de que el trabajador i es asignado a la máquina j (0 indica que el trabajador no ha sido asignado y 1 que sí ha sido asignado) Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas restricciones son que cada trabajador debe ser asignado a una sola máquina y no debe quedar ninguna máquina sin un trabajador asignado a ella: Cada trabajador debe estar asignado a una sola máquina o a ninguna si no se selecciona: Ejemplo 4: Modelo de Programación Lineal[editar] X11 + X12 + X13 + X14 ≤ 1 X21 + X22 + X23 + X24 ≤ 1 X31 + X32 + X33 + X34 ≤ 1 X41 + X42 + X43 + X44 ≤ 1

X51 + X52 + X53 + X54 ≤ 1 En cada máquina debe haber un trabajador: X11 + X21 + X31 + X41 + X51 = 1 X12 + X22 + X32 + X42 + X52 = 1 X13 + X23 + X33 + X43 + X53 = 1 X14 + X24 + X34 + X44 + X54 = 1 Se expresan todas las condiciones implícitamente establecidas por la naturaleza de las variables: que no puedan ser negativas, que sean enteras, que solo puedan tomar determinados valores,... En este caso las restricciones son que las asignaciones de trabajadores a máquinas no puede ser negativa y debe ser además una variable booleana (0 no se asigna, 1 se asigna): Xij ≥ 0 Xij es booleano Se determina la función objetivo: Min Z = 10X11 + 8X21 + 8X31 + 9X41 + 8X51 + 6X12 + 7X22 + 6X32 + 7X42 + 7X52 + 6X13 + 6X23 + 5X33 + 7X43 + 6X53 + 5X14 + 6X24 + 6X34 + 6X44 + 5X54 Ejemplo 4: Solución[editar]

Ejemplo 4: Interpretación de resultados[editar] Por lo tanto: El candidato 1 trabajara con la máquina 2 El candidato 2 trabajara con la máquina 1 El candidato 3 trabajara con la máquina 3 El candidato 5 trabajara con la máquina 4 El candidato 4 no trabajaría Así tendremos un costo de: 24 ( Z*=6+8+5+0+5) Ejemplo 5[editar] Un profesor han determinado 4 capítulos de un libro X y está pensando en pedir ayuda ´para terminarlo. Él ha elegido a 4 secretarias que podrían tipearle cada uno de sus capítulos. El costo asociado refleja la velocidad de la secretaria y la exactitud del trabajo. Ejemplo 5: Tabla de asignación[editar]

Los datos están en la tabla.

Ejemplo 5: Solución[editar]

Ejemplo 6[editar] El profesor Michell ha terminado 4 capítulos de su libro y está pensando en pedir ayuda para terminarlo. Él ha elegido a 4 secretarias que podrían mecanografiarle cada uno de sus capítulos. El costo asociado refleja la velocidad de la secretaría y la exactitud con la que realiza el trabajo.

Además los capítulos difieren en la cantidad de hojas y en la complejidad. ¿Qué puede hacer el profesor si conoce la siguiente tabla: Ejemplo 6: Tabla de asignación[editar]

Ejemplo 6: Modelo de programación lineal[editar] Xij =Secretaria i asignada al capítulo j.

C a pí t ul o 1 4

C a pí t ul o 1 5

C a pí t ul o 1 6

C a pí t ul o 1 7

SE CR ET 9 AR 6 IA 1

9 9

1 0 5

1 0 8

SE CR 1 ET 1 AR 6 IA 2

1 0 9

1 0 7

9 6

SE CR 1 ET 2 AR 0 IA 3

1 0 2

1 1 3

1 1 1

SE CR 1 ET 1 AR 4 IA 4

1 0 5

1 1 8

1 1 5

Min Z= 96X11 + 99X12 + 105X13 +108X14 + 116X21 + 109X22 + 107X23 + 96X24 + 120X31 + 102X32 + 113X33 + 111X34 + 114X41 + 105X42 + 118X43 + 115X44. s.a X11 + X12 + X13 + X14 = 1 X21 + X22 + X23 + X24 = 1 X31 + X32 + X33 + X34 = 1 X41 + X42 + X43 + X44 = 1 X11 + X21 + X31 + X41 = 1 X12 + X22 + X32 + X42 = 1 X13 + X23 + X33 + X43 = 1 X14 + X24 + X34 + X44 = 1 Xij ≥0 Después de aplicar el Método Húngaro se obtiene la solución: C a pí t ul o 1 4

C a pí t ul o 1 5

C a pí t ul o 1 6

C a pí t ul o 1 7

Se cr et 0 ar ia 1

5

0

1 4

Se cr et 1 ar 8 ia 2

1 3

0

0

Se cr 1 et 6 ar

0

0

9

ia 3 Se cr et 7 ar ia 4

0

2

1 0

Por lo que al tomar los valores en donde existan ceros, se elige alguno y se eliminan los ceros consecuentes por fila y por columna, por lo tanto la solucioón es: Ejemplo 6: Interpretación de resultados[editar] Juana escribirá el Cap.14 María escribirá Cap. 17 Jackeline escribirá Cap.16 Edith escribirá Cap.15 Costo de Asignación es: 96 + 96 + 113 + 105 = 410 Ejemplo 7[editar] En la empresa Sinco se tienen tres vacantes, que ya han sido solicitadas por tres profesionistas, Jorge, Karen y Armando. El gerente de recursos humanos, Martín, pidió propuestas de salarios a cada uno de los profesionistas para las actividades de capturista de datos, programador y análista de base de datos, que todos los solicitantes podrían realizar. Se sobreentiende que después los tres aceptarán la decisión de Martín sobre quién hace que actividad. La tabla siguiente resume las propuestas recibidas por lo que cobra un profesionista por realizar las diferentes actividades por hora.

Jo rg e

Ca pt uri sta de da tos

Pro gra ma dor

A na lis ta d e ba se d e da to s

16 0

110

10 0

Ka re n

10 0

160

11 0

Ar m 11 an 0 do

130

90

Con base en esta información ¿ Cómo debe asignar las actividades el gerente de recursos humanos? Ejemplo 7: Modelo de Programación lineal[editar] xij = La asignación del profesionista i a la actividad j Min z = 160 X11+ 110X12 + 100X13 + 100X21 + 160X22 + 110X23 + 110X31 + 130X32 + 90X33 s.a. Delimitamos a los profesionistas X11 + X12 + X13 = 1 X21 + X22 + X23 = 1 X31 + X32 + X33 = 1 Delimitamos a las tareas X11 + X21 + X31 = 1 X12 + X22 + X32 = 1 X13 + X23 + X33 = 1 Xij ≥ 0, xij ε {0,1} Ejemplo 7: Matriz de costos[editar]

Ejemplo 7: Solución por medio del Método Húngaro[editar] Reste el número más pequeño de cada renglón, esto se llama reducción de renglón. Introduzca los resultados en una nueva matriz

Reste el número más pequeño de la nueva matriz a cada número de la columna, esto se llama reducción de columna. Introduzca los nuevos datos en otra matriz.

Pruebe si puede hacer una asignación óptima. Hágalo mediante la determinación del número mínimo de líneas necesarias para cubrir todos los ceros (horizontales y verticales). Si el número de líneas es igual al número de renglones entonces es posible hacer una asignación.

En este caso tuvimos suerte, el número de líneas es igual al número de renglones de la matriz por lo tanto podemos hacer una asignación. Nos pasamos al paso 6, les dejó también los pasos que hubiéramos tenido que realizar en caso de no fuera igual el número de renglones que de columnas. Si el número de líneas es menor que el número de renglones, modifique la matriz de la siguiente forma: a) Reste el número no cubierto más pequeño de todos los números no cubiertos de la matriz. b) Sume el número no cubierto más pequeño a los números que se encuentran en intersección de líneas. c) Los números cruzados pero que no se encuentren en intersección de líneas permanecen igual. Repita los pasos 3 y 4 hasta que el número de líneas sea igual al número de renglones de la matriz. Haga las asignaciones una a una en las posiciones que tienen elementos cero, comience con los renglones y columnas que tienen un sólo cero. Cada renglón y columna necesita recibir exactamente una asignación, después continue con los renglones y columnas que no han sido asignados, continue hasta que todos los renglones y columnas hayan sido asignados. En nuestro ejemplo asignamos las posiciones X21, X12 y X33. Ejemplo 7: Interpretación de resultados[editar] Pr of es io ni st a

A c ti vi d a d

1

2

2

1

3

3

Jorge va a ser el programador, Karen la capturista de datos y Armando el analista de base de datos. El costo total será de 110 + 100 + 90 = $300 por hora. Ejemplo 8[editar] En la empresa de computo llamada “El Lago Azul” se tienen 6 circuitos lógicos para ser colocados en 5 equipos. Se requiere saber cual es el costo mínimo en la adaptación de los circuitos a las computadoras. En la siguiente tabla se muestran los costos que se llevan a cabo en la adaptación:

Ejemplo 8: Modelo de Programación Lineal[editar] Xij = Circuito i, Computadora j Min z = 1000X11 + 1500X12 + 3200X13 + 500X14 + 1900X15 + 700X21 + 920X22 + 2000X23 + 1100X24 + 3000X25 + 840X31 + 799X32 + 1600X33 + 2300X34 + 1500X35 + 1500X41 + 2000X42 + 1800X43 + 3400X44 + 2600X45 + 1300X51 + 3200X52 + 600X53 + 980X54 + 1000X55 + 2000X61 + 2500X62 + 700X63 + 640X64 + 1500X65. s.a X11 + X12 + X13 + X14 + X15≤1 X21 + X22 + X23 + X24 + X25≤1 X31 + X32 + X33 + X34 + X35≤1 X41 + X42 + X43 + X44 + X45≤1 X51 + X52 + X53 + X54 + X55≤1 X61 + X62 + X63 + X64 + X65≤1 X11 + X21 + X31 + X41 + X51 + X61 = 1 X12 + X22 + X32 + X42 + X52 + X62 = 1 X13 + X23 + X33 + X43 + X53 + X63 = 1 X14 + X24 + X34 + X44 + X54 + X64 = 1

X15 + X25 + X35 + X45 + X55 + X65 = 1 X16 + X26 + X36 + X46 + X56 + X66 = 1 Ejemplo 8: Tabla de transporte[editar] Para resolver el problema es necesario balancearlo, la tabla resulta de la siguiente forma: Ejemplo 8: Solución por medio del Método Húngaro[editar] Resta por renglón. Para realizar la resta por renglón elegimos el menor número que se encuentra en cada uno, en este caso todos los números menores por renglón pertenecen a la columna ficticia por lo tanto en este ejemplo no habrá ningún cambio.

Resta por columna. Ahora restamos el número menor que se encuentra en cada columna, que son los marcados de color verde, a cada elemento que se encuentre en la columna correspondiente. El resultado de los pasos anteriores se le llama matriz resultante.

Trazado de líneas. Ahora trazamos la menor cantidad de líneas que cubra la mayor cantidad de ceros, todos los ceros deben de terminar cubiertos, nosotros los marcamos de color rojo.

6 renglones y 5 líneas. Para que el problema se de por terminado tendría que ser igual el número de renglones con el número de líneas, en este caso no se cumple. Por lo tanto se realiza una segunda iteración. Se elige el número menor no marcado en este caso que no este de color rojo y lo restamos a los demás números no marcados mientras tanto en las intersecciones de las líneas anteriormente marcadas le sumamos este número. En este caso es el número 100.

Trazado de líneas Ahora nuevamente trazamos las líneas, y en este caso se cumple la condición.

Elegimos las columnas que tengan un cero y esa será la asignación de cada circuito a computadora. En el caso que tengan 2 ceros asignamos uno que no haya sido asignado anteriormente mientras que tachamos el cero sobrante.

Finalmente aquí se puede apreciar mejor cada asignación. Como podemos ver el circuito 4 no tiene computadora asignada, si recordamos anteriormente agregamos una columna ficticia para balancear el problema por lo tanto sobrara un circuito.

Ejemplo 8: Interpretación de resultados[editar] z = 500 + 700 + 799 + 1000 + 700 = $ 3699 Lo que buscaba el problema era encontrar el costo mínimo así que ya dada la asignación sumamos los costos que cada celda tenía en la primera tabla. Ejemplo 9[editar] Suponga que Aero-México tiene el siguiente horario de vuelos diarios

El problema que tiene Aero-México es la calendarización de la tripulación en estos vuelos. Resulta que una tripulación que sale de México un lunes a las 7:30, llega a Río el mismo lunes a las 13:30; sale el martes de Río a las 9 y llega a México a las 15 horas. El tiempo transcurrido desde las 13:30 del lunes hasta las 9 del martes siguiente, es un tiempo muerto. Se trata entonces de reducir los tiempos muertos de as tripulaciones en estos vuelos, sujeto a ciertas condiciones. En este caso, las condiciones son que cada tripulación debe descansar al menos 8 horas, pero no más de 24. El problema se puede enunciar de la siguiente manera: dónde deben vivir las tripulaciones y qué tripulaciones deben asignarse a qué vuelos, tal que los tiempos muertos totales se minimicen y al mismo tiempo se respeten las condiciones de descanso de las tripulaciones. Suponga que una tripulación que vive en la ciudad de México que trabaja en el vuelo C y regresa en el vuelo 2 de Río de Janeiro. De acuerdo con los tiempos de vuelo, esa tripulación llega a las

17:30 y sale a las 9 de la mañana rumbo a México, tras 15 y media horas de tiempo muerto. En cambio, una tripulación que vive en Río y sale en el vuelo 1 hacia México, y regresa en el vuelo A a Río, tiene un tiempo muerto de 18 y media horas. Así se pueden construir 2 matrices de tiempos muertos, a saber:

Dadas estas dos matrices, se construye una nueva, donde los elementos tij serán. tij=mín (tij1, tij2), siempre y cuando 8≤tij≤24. En caso de que tij no cumpla con esta restricción, la asignación i,j es imposible y por lo tanto, tij = M, donde M>>0. En efecto, la nueva matriz es:

Ejemplo 9: Modelo de Programación Lineal[editar] Así el Modelo de Programación Lineal quedaría: Minimizar Z= 17.5 Xa1 + 15Xa21 + 9Xa3 +... 12Xe4 + 17.5Xe5 s.a Xa1 + Xa2 + Xa3 + Xa4 + Xa5 = 1 Xb1 + Xb2 + Xb3 + Xb4 + Xb5 = 1 Xc1 + Xc2 + Xc3 + Xc4 + Xc5 = 1 Xd1 + Xd2 + Xd3 + Xd4 + Xd5 = 1 Xe1 + Xe2 + Xe3 + Xe4 + Xe5 = 1

Xa1 + Xb1 + Xc1 + Xd1 + Xe1 = 1 Xa2 + Xb2 + Xc2 + Xd2 + Xe2 = 1 Xa3 + Xb3 + Xc3 + Xd3 + Xe3 = 1 Xa4 + Xb4 + Xc4 + Xd4 + Xe4 = 1 Xa5 + Xb5 + Xc5 + Xd5 + Xe5 = 1 Xij = { 0, 1 } Xij Z Ejemplo 9: Solución por medio del Método Húngaro[editar] Como A ya está balanceada, se le aplica el método Húngaro para obtener la solución. Paso 1. Ceros en cada columna

Ceros en cada renglón

Paso 2. Vemos si se puede hacer una asignación, determinando el número mínimo de líneas necesario para cubrir los ceros (para poder hacerse el número de líneas tiene que ser igual al número de renglones)

No se puede hacer la asignación, por tanto seguimos con el paso 3 Paso3. Si el número de líneas es menor que el de renglones a) Restamos el número no cubierto más pequeño a todos los números no cubiertos

b) sumamos el número no cubierto más pequeño a los números que se encuentran en las intersecciones de las líneas c) Los demás números permanecen igual.

Con esta iteración ya son 5 líneas y por tanto ya podemos continuar Paso 4. Hacemos asignaciones 1 a 1 de acuerdo a las posiciones de los ceros. Comenzamos por los renglones y columnas que sólo tienen un cero. Cada renglón y cada columna debe recibir una sola asignación. La asignación óptima queda

A- 3 con tiempo muerto de 9 horas B- 5 con tiempo muerto de 10.5 horas C- 1 con tiempo muerto de 12 horas D- 2 con tiempo muerto de 8 horas E- 4 con tiempo muerto de 12 horas Ejemplo 9: Interpretación de resultados[editar] Refiriéndonos a las 2 matrices originales se tiene que en términos de donde viven las tripulaciones la asignación óptima es:

El tiempo muerto total mínimo es de 51.5 horas. Ejemplo 10[editar] Los tres hijos de Joe Klyne, John, Karen y Terri, quieren ganar algún dinero para cubrir sus gastos personales durante un viaje organizado por la escuela al zoológico local. El señor Klyne eligió tres tareas para sus hijos: podar el césped, pintar la cochera y lavar los automóviles de la familia. Para evitar las competencias anticipadas entre hermanos, les pidió que presentaran licitaciones (secretas) para lo que ellos creían era un pago justo para cada una de las tres tareas. Quedaba entendido que los tres hijos aceptarían la decisión de su padre en lo concerniente a quién desempeñaría cada tarea. La siguiente tabla resume las licitaciones recibidas. Ejemplo 10: Tabla de asignación[editar] P o d a r

P i n t a r

L a v a r

J $$ o $ 11 h 7 50 n K a $$ $ r 11 9 e 00 n

T e$ $$ r 1 28 r 0 i Ejemplo 10: Solución por medio del Método Húngaro[editar] Basándose en esta información, ¿Cómo debe asignar las tareas el señor Klyne? Este problema se resolverá con los primeros tres pasos del método Húngaro. 1.ª iteración.

P o d a r

P i n t a r

L a v a r

r e n g l ó n m í n i m o

J p o11 1 9 h50 = n 1 K p a 112 r 9 50= e 1 n T p e 11 3 r 8 02 = r 1 i En seguida restamos el renglón mínimo de cada renglón respectivo, para obtener la matriz reducida.

P o d a r

P i n t a r

L a v a r

J o 610 h n K a 0 r 61 ' e n T e r 240 r i C o l u m q n 1 a = m 0 í n i m a

q 2 = 1

q 3 = 0

La aplicación del paso 2 nos da los mínimos en la columna. restando estos valores de las columnas respectivas obtenemos las matriz reducida. P P L i o a n d v t

aaa r r r J o 600 h n K a r 051 e n T e r 230 r i Ejemplo 10: Interpretación de resultados[editar] Los cuadros con las entradas cero en negritas proporcionan la solución óptima. Eso quiere decir que John pintará la cochera, Karen podará el césped y Terri lavará los automóviles de la familia. El costo total para el sr Klyne es 9+10+8 =27 dólares. Además esa cantidad siempre igualará (p1 + p2 + p3) + (q1 + q2 + q3)=(9+9+8)+(0+1+0)= 27 dólares. Ejemplo 11[editar] Asignar maximizando el siguiente Problema.

Como este es un problema de maximización entonces primero pasaremos aconvertirlo en minimización: lo pasamos a minimización con operación columna

Ahora como una minimización primero operación fila:

Ahora operación columna

Como aquí se encuentra la solución entonces se compara con la matriz original, Por lotanto el resultado será: A le corresponde e B se le asigna c C lo canalisamos con d D lo asignamos a b E le corresponde a ⇒ Z=8 + 6 + 5 + 7 + 4 =30 Ejemplo 12[editar] Una agencia de publicidad trata cual de entre 4 ejecutivos de contabilidad debe asignarse a cada uno de los clientes mayores. Use el método conveniente para encontrar la solución óptima, a continuación se presentan los costos estimados de la asignación de cada ejecutivo. Ejemplo 12: Solución por medio del Método Húngaro[editar] Realizando operación renglón, primero buscamos el menor de la fila correspondiente. Como no se tienen los suficientes ceros pasamos a operación columna: Pero como no se encuentran los suficientes Ceros para cada fila se procede a buscar el menor de toda la matriz que no estén tachados (en nuestro caso con rojo). En este caso el menor es 1. Entonces restaremos este valor a cada uno de los elementos no tachados y sumaremos este mismo valor a los elementos que están en las intersecciones, los demás se copian sin operación alguna. Como tampoco obtenemos al menos un cero en las filas se vuelve a realizar la operación anterior. Entonces el menor de los elementos de la matriz no tachada será nuevamente 1, entonces queda: Aquí encontramos al menos un cero en todas las filas, entonces si tenemos más de 1 Cero en una determinada fila se compara quien es el menor y se toma este. Luego se tacha los ceros que podrían existir en las filas y columnas correspondientes al número tomado. Luego comparamos con la matriz original y se toman los números en las que están los ceros no tachados, luego sumamos y encontramos la solución óptima. (A, 1)=15 (B, 4)=14 (C, 3)=15 (D, 2)=24 entonces 15 + 14 + 15 + 24 = 68, en otras palabras el cliente A estará con el contador 1, el B con el 4, el C con el 3 y el cliente D con el contador 2.

Ejemplo 13: Ejemplo con oferta ficticia[editar] Existen 3 empleados que se pueden asignar al trabajo con 4 máquinas. Un estudio de tiempos y movimientos ha arrojado los siguientes tiempos por empleado para las 4 máquinas. Indicar que empleado debe trabajar en que máquina y cuál de ellas no será asignado a ningún empleado. MMMM áááá qqqq uuuu i i i i nnnn aaaa 1234 E m p l 1 e 798 0 a d o 1 E m p l e7589 a d o 2 E m p l 1 e98 7 0 a d o 3

Como la matriz no está balanceada, es necesario incluir un empleado ficticio: (esto es fundamental para asegurar que haya una respuesta. Si la matriz no está balanceada, el problema no será factible de resolver) MMMM áááá qqqq uuuu i i i i nnnn aaaa 1234 E m p l 1 e 798 0 a d o 1 E m p l e7589 a d o 2 E m p l 1 e98 7 0 a d o 3 F 0000 i

c t i c i o Xij = Se debe asignar el operario i a la máquina j? Sí o no? Existen dos números cuyas propiedades hacen que puedan representar estas respuestas son el 1 y el 0, debido a que todo número multiplicado por 1 da el mismo número entonces el 1 se puede reemplazar por la respuesta Sí y como todo número multiplicado por cero da cero entonces se puede reemplazar por la respuesta No. Así por ejemplo: 10X11 + 7X12 + 9X13 + 8X14 representa el tiempo sumado que requiere el empleado 1 en operar las máquinas, pero solo una variable de las tres anteriores puede tomar el valor de Sí, o sea de 1 las demás tendrán que tomar el valor de 0, y eso es debido a que el empleado 1 sólo puede ser asignado a una máquina, lo que significaría que el tiempo que utilice el empleado1 puede ser ya sea de "10" de "7" o de "9". o de “8”. Con base en esto podemos formular la función objetivo: Min Z = 10X11 + 7X12 + 9X13 + 8X14 + 7X21 + 5X22 + 8X23 + 9x24 +9X31 + 8X32 + 10X33 + 7x34 Restricciones: Como cada empleado sólo puede estar asignado a una máquina. X11 + X12 + X13 + X14 = 1 X21 + X22 + X23 + X24 = 1 X31 + X32 + X33 + X34 = 1 X41 + X42 + X43 + X44 = 1 Y como cada máquina solo puede tener un operario asignado... X11 + X21 + X31 + X41 = 1 X12 + X22 + X32 + X42 = 1 X13 + X23 + X33 + X43 = 1 X14 + X24 + X34 + X44 = 1 Xij = 1 o 0 para toda i,j. Al resolver utilizando Software, por ejemplo el Solver del Excel, la respuesta que se obtiene es la siguiente: MMMM áááá qqqq uuuu i i i i nnnn aaaa 1234 E0010 m

p l e a d o 1 E m p l e0100 a d o 2 E m p l e0001 a d o 3 F i c t 1000 i c i o Esto significa que al empleado 1 queda asignado a la máquina 3, el empleado 2 se asigna a la máquina 2, el empleado 3 se asigna a la máquina 4 y el empleado Ficticio se asigna a la máquina 1 (es decir, es la que sobra). Ejemplo 14[editar] DocConcilman reúne a un equipo de relevos para el relevo de 400m. cada nadador debe nadar 100m de brazada de pecho, dorso, mariposa o estilo libre. Doc cree que cada nadador obtendrá los tiempos en segundos dados en la tabla. Que nadador debe nadar que estilo?

L i b r e

P e c h o

M a D r o i r p s o o s a

G a5555 r 4413 y M a5555 r 1722 k J 5555 i 0346 m C h5555 a6453 t Xij = Asignar el nadador i al estilo j? Sí o no? Planteamiento: El Modelo de Programación Lineal será un modelo binario. 1 Se asigna al asigna en nadador i a la tarea j Xij = 0 No se asigna Min Z= 54X11 + 54 X12 + 51X13 +53X14 +... + 55X43 +53X44 s.a. X11 + X12 +X13 +X14= 1 X21 + X22 +X23 +X24= 1 X31 + X32 +X33 +X34= 1

NADADORES

X41 + X42 +X43 +X44= 1 X11 + X21 +X31 +X41= 1 X12 + X22 +X32 +X41= 1 X13 + X23 +X33 +X43= 1

ESTILOS

X14 + X24 +X34 +X44= 1 Xij>=0 APLICACIÓN DEL MÉTODO HÚNGARO 1. Obtener matriz de costos. 2. Realizar la reducción por renglón, restando el número más pequeño del renglón a cada renglón, después realizar lo mismo para las columnas. Archivo:Tableau dos.png 3. Determinación del número de líneas necesario para hacer una asignación óptima. Archivo:Tableau tres.png El número de renglones es 4, y es mayor que el número de columnas que cubren los ceros, por lo tanto realizaremos el paso 5 5. Como el número de líneas es menor que el número de renglones, modificaremos la matriz de la siguiente manera: Restaremos el número no cubierto más pequeño al número que se encuentra en intersección de las líneas. Sumaremos el número no cubierto más pequeño a los números que se encuentran en la intersección de las líneas. Archivo:Tableau cuatro.png RESULTADOS Como el número de renglones es igual al número de Líneas que cubren los ceros, podemos hacer una asignación óptima. Archivo:Tableau cinco.png INTERPRETACIÓN DE RESULTADOS. De esta forma, se observa que la mejor asignación de nadadores a estilos según sus tiempos, es la siguiente:

Archivo:Tableau seis.png Referencias[editar] (1) * Autor: Anónimo. Polilibros del IPN. Investigación de Operaciones. Capítulo 4. Aplicaciones de la Programación Lineal. 4.3.3. Modelo de asignación pura.http://148.204.211.134/polilibros/portal/Polilibros/P_Terminados/Investigacion_de_Operaci ones_Careaga/Common/IO-modulo4-asignacionpura.htm (2) * Autor: Dr. Franco Bellini. Investigación de Operaciones. Curso de la Escuela de Administración y Contaduría Universidad Santa María, Tema 4: Modelos de transporte, Caracas-Venezuela, Julio 2004. http://www.investigacion-operaciones.com/modelo_de_transporte.htm (3) * Autor: Anónimo. Medelo de Asignación http://antiguo.itson.mx/dii/elagarda/apagina2001/PM/asignacion.html#define (4) * Hamdy A. Taha. (2004). Investigación de operaciones. México. Pearson Educación. (5) * Wayne L. Winston. (2005) Investigación de operaciones y aplicación de algoritmos, 4.ª ed.. México, Ed Thomson. (6) * Tutorial del Método de asignación http://www.ingenieriaindustrial.net/index.php?accion=1&id=73 Ingenieria-industrial.net] Tutorial del Método de Asignación