metodos cuantitativos

El modelo de asignación es un caso especial del modelo de transporte, en el que los recursos se asignan a las actividade

Views 166 Downloads 4 File size 442KB

Report DMCA / Copyright

DOWNLOAD FILE

Recommend stories

Citation preview

El modelo de asignación es un caso especial del modelo de transporte, en el que los recursos se asignan a las actividades en términos de uno a uno, haciendo notar que la matriz correspondiente debe ser cuadrada. Así entonces cada recurso debe asignarse, de modo único a una actividad particular o asignación.

Se tiene un costo Cij asociado con el recurso que es asignado, de modo que el objetivo es determinar en que forma deben realizarse todas las asignaciones para minimizar los costos totales. El problema de asignación es una variación del problema original de transporte, variación en la cual las variables de decisión X(i,j) solo pueden tomar valores binarios, es decir ser cero (0) o uno (1) en la solución óptima, lo que supone que la oferta y la demanda están perfectamente alineadas, de hecho ambas son iguales a uno (1).

Múltiples son los casos en los que como ingenieros industriales podemos hacer uso del problema de asignación para resolver diversas situaciones, entre los que cabe mencionar se encuentran la asignación de personal a maquinas, herramientas a puestos de trabajos, horarios a maestros, candidatos a vacantes, huéspedes a habitaciones, comensales a mesas, vendedores a zonas territoriales etc.

En el modelo de asignación la idea fundamental de resolución es ¿qué fuente satisface mejor el destino?, y dado que hemos asociado el modelo a una gran diversidad de circunstancias esta pregunta puede plantearse en múltiples contextos, como ¿qué candidato es el idóneo para la vacante?, o ¿qué personal es el indicado para la línea productiva?, o ¿qué personal es el mejor para ejecutar determinada tarea?. Una característica particular del modelo de asignación es que para su resolución no se hace necesario que el número de fuentes sea igual al número de destinos, lo cual es muy común en la vida real teniendo en cuenta su aplicación, pues generalmente la cantidad de aspirantes es exageradamente superior al número de vacantes (lógicamente haciendo referencia a la aplicación del modelo al contexto de oferta y demanda laboral).

El problema de asignación consiste en encontrar la forma de asignar ciertos recursos disponibles (máquinas o personas) para la realización de determinadas tareas al menor coste, suponiendo que cada recurso se destina a una sola tarea, y que cada tarea es ejecutada por uno solo de los recursos. Es uno de los problemas fundamentales de optimización combinatoria de la rama de optimización o investigación operativa en matemática. El modelo se puede aplicar a la asignación de empleados a tareas, de fábricas a productos, de

vendedores a territorios, de postores a contratos, etc. Con una sencilla manipulación, el método también se puede aplicar al caso en el que se pretende maximizar cierta cantidad. Formalmente, el problema de la asignación consiste en encontrar un emparejamiento de peso óptimo en un grafo bipartito ponderado. El problema de asignación es un caso particular del problema de transporte, en el que la oferta en cada origen y la demanda en cada destino son ambas de valor 1. 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 surge cada vez con mayor frecuencia el uso de este problema en 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.

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 de modo que el coste total de la asignación sea minimo. Este tipo de problemas son lineales, con una estructura de transporte, solo 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 algoritmo 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 sola tarea. 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 está 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ón sin 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.

Los problemas de asignación son casos particulares 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 de 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

Red Modelo de programación lineal Matriz de costos Tabla de transporte 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. 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).

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 qué 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.

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). e 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. 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 de 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.

Pasos para el método húngaro: Paso 1: De la matriz de costos m*m, encontrar primero el mínimo elemento de cada fila, y restarlo a cada costo de la fila. Repetimos la operación por columnas, buscando el costo mínimo en cada columna, y construyendo una nueva matriz (denominada matriz de costos reducidos) al restar de cada costo el costo mínimo de su columna. Paso 2: Repetiremos este paso hasta encontrar una solución: 1) Trace el número mínimo de líneas (horizontales, verticales o ambas) en la última matriz de costos reducidos que cubra todos los ceros. 2) 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 no continuamos. 3) Selecciones el elemento no cubierto más pequeño y réstelo de todos los elementos no cubiertos; después, súmelo a todos los elementos en la intersección de dos líneas. Paso 3: Usando los ceros que hemos obtenido construimos la solución sabiendo que solo es posible asignar i a j, si el elemento xij de la matriz de costos reducidos modificada es 0. Se llega por descarte a una (o varias) soluciones óptimas. 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 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 Húngaro Caso A: Minimización.

Revisar que todas las casillas tengan su costo ( beneficio) unitario correspondiente. Si alguna no lo tiene asignarlo en términos del tipo de matriz y problema considerado.

1. Balancear el modelo, es decir obtener m=n (obtener una matriz cuadrada)

En donde m= número de renglones.

En donde n= número de columnas.

Todo renglón o columna tendrá un costo (beneficio ) unitario de cero.

2. Para cada renglón escoger el MENOR VALOR y restarlo de todos los demás en el MISMO RENGLÓN.

3. Para cada columna escoger el MENOR VALOR y restarlo de todos los demás en la MISMA COLUMNA.

4. Trazar el MÍNIMO número de líneas verticales y horizontales de forma tal que todos los ceros queden tachados.

5. Criterio de optimidad:

¿El número de líneas es igual al orden de la matriz?

SI, el modelo es óptimo y por tanto hacer la asignación y traducir la solución.

La asignación se debe hacer en las casillas donde haya ceros cuidando que cada renglón y cada columna tenga una sola asignación.

NO pasar al siguiente punto.

6. Seleccionar el menor valor no tachado de toda la matriz. El valor restarlo de todo elemento no tachado sumarlo a los elementos en la interacción de dos líneas.

7. Regresar al paso 4.

Caso B: Maximización.

Metodología:

Seleccionar el MAYOR ELEMENTO de toda la matriz de beneficio. Este valor restarlo de todos los demás, los valores negativos que se obtengan representan los costos de oportunidad, lo que se deja de ganar o producir.

Para el caso de la solución del modelo considerar solo valores absolutos. Con esta transformación se ha obtenido un modelo de minimización y por tanto resolverlo como tal.

Apartándonos un poco de la idea expresada en módulos anteriores respecto a la facilidad de resolver problemas atinentes a la investigación operativa en especial aquellos de transporte mediante el uso de herramientas tecnológicas como lo son WinQSB, LINGO, TORA, STORM, Excel etc.. vale la pena ya sea para fines académicos o de cultura ingenieril realizar la resolución del problema de asignación mediante el algoritmo que se creó para tal fin, como lo es el Método Húngaro.

El método Húngaro es un método de optimización de problemas de asignación, conocido como tal gracias a que los primeros aportes al método clásico definitivo fueron de Dénes König y Jenő Egerváry dos matemáticos húngaros. El algoritmo tal como se detallará a continuación está diseñado para la resolución de problemas de minimización únicamente, será entonces cuestión de agregar un paso adicional para abordar ejercicios de maximización.

El Problema de Transbordo, Intertransporte o Reembarque es una variación del modelo original de transporte que se ajusta a la posibilidad

común de transportar unidades mediante nodos fuentes, destinos y transitorios, mientras el modelo tradicional solo permite envíos directos desde nodos fuentes hacia nodos destinos.

Existe la posibilidad de resolver un modelo de transbordo mediante las técnicas tradicionales de resolución de modelos de transporte y este procedimiento se basa en la preparación del tabulado inicial haciendo uso de artificios conocidos con el nombre de amortiguadores, los cuales deben ser iguales a la sumatoria de las ofertas de los nodos de oferta pura y de coeficiente cero (0) en materia de costos.

Sin embargo la resolución de un problema de transbordo haciendo uso de los algoritmos de resolución de modelos de transporte es una idea anacrónica, teniendo en cuenta la posibilidad de acceso a herramientas de cómputo capaces de resolver problemas complejos una vez modelados mediante las técnicas de programación lineal.

La importancia de los modelos de transbordo aumenta con las nuevas tendencias globales de gestión de cadenas de abastecimiento, en las cuales se deben de optimizar los flujos logísticos de productos teniendo en cuenta la importancia de minimizar los costos, asegurar disponibilidad de unidades y reconociendo la importancia de los centros de distribución en la búsqueda del equilibrio entre las proyecciones y la realidad de la demanda.

RESOLUCIÓN DE UN PROBLEMA DE TRANSBORDO MEDIANTE PROGRAMACIÓN LINEAL

Para poder resolver un problema de transbordo mediante programación lineal basta con conocer una nueva familia de restricciones, las llamadas restricciones de balanceo. En un problema de transbordo existen 3 clases de nodos, los nodos de oferta pura, los de demanda pura y los nodos transitorios que posibilitan el transbordo y que deben de balancearse para hacer que el sistema sea viable, es decir, que todas las unidades que ingresen a un nodo sean iguales a las que salgan del mismo (unidades que salen + unidades que conserve el nodo). EL PROBLEMA

Modelar mediante programación lineal el problema de transbordo esbozado en la siguiente figura Problema de Transbordo

La figura muestra una serie de nodos y sus respectivas rutas mediante las cuales se supone distribuir las unidades de un producto, el número que lleva cada arco (flecha) representa el costo unitario asociado a esa ruta (arco), y las cantidades que se ubican en los nodos iniciales representan la oferta de cada planta, así como las cantidades de los nodos finales representa la demanda de cada distribuidor. LAS VARIABLES DE DECISIÓN

En este caso como en la mayoría las variables de decisión deben representar la cantidad de unidades enviadas por medio de cada ruta. Es muy aconsejable denotar cada nodo con un número para simplificar la definición nominal de las variables.

Una vez renombrado cada nodo definiremos las variables:

XA,C = Cantidad de unidades enviadas desde P1 hacia T1 XA,D = Cantidad de unidades enviadas desde P1 hacia T2 XB,C = Cantidad de unidades enviadas desde P2 hacia T1 XB,D = Cantidad de unidades enviadas desde P2 hacia T2 XC,D = Cantidad de unidades enviadas desde T1 hacia T2 XC,E = Cantidad de unidades enviadas desde T1 hacia D1 XC,F = Cantidad de unidades enviadas desde T1 hacia D2 XD,F = Cantidad de unidades enviadas desde T2 hacia D2 XD,G = Cantidad de unidades enviadas desde T2 hacia D3 XE,F = Cantidad de unidades enviadas desde D1 hacia D2

XF,G = Cantidad de unidades enviadas desde D2 hacia D3

RESTRICCIONES Existen en este modelo 3 tipos de restricciones y están estrechamente relacionadas con los tipos de nodos existentes, para un nodo oferta pura existe la restricción de oferta; para un nodo demanda pura existe la restricción de demanda, y para un nodo transitorio y/o transitorio de demanda existe la restricción de balance. Recordemos que los nodos transitorios son aquellos que tienen rutas (arcos o flechas) de entrad y salida, y si además este presenta un requerimiento de unidades se denomina transitorio de demanda.

Restricciones de Oferta:

XA,C + XA,D = 1000 XB,C + XB,D = 1200

Restricciones de demanda:

XD,G + XF,G = 500

Restricciones de balanceo para nodos únicamente transitorios: Con estas restricciones aseguramos que todas las unidades que lleguen sean iguales a las unidades que salgan.

XA,C + XB,C - XC,D - XC,E - XC,F = 0 XA,D + XB,D + XC,D - XD,F - XD,G = 0

Restricciones de balanceo para nodos transitorios con requerimientos:

Con estas restricciones aseguramos que todas las unidades que lleguen sean iguales a la sumatoria de las unidades que salen más los requerimientos del nodo (demanda).

XC,E - XE,F = 800 XC,F + XD,F + XE,F - XF,G = 900

FUNCIÓN OBJETIVO En este caso la definición de la función objetivo se limita a la consignación de cada ruta con su respectivo costo bajo el criterio "minimizar".

ZMIN = 3XA,C + 4XA,D + 2XB,C + 5XB,D + 7XC,D + 8XC,E + 6XC,F + 4XD,F + 9XD,G + 5XE,F + 3XF,G

INGRESANDO EL MODELO A WINQSB

SOLUCIÓN OBTENIDA MEDIANTE WINQSB

Esta es la representación grafica de la solución cuyo costo óptimo es de 20.700 unidades monetarias

Modelo de programación lineal para el modelo de asignación . 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

Candidato 1 Candidato 2 Candidato 3 Candidato 4 Candidato 5

Máquina 1 10 8 8 9 8

Red Comenzamos por plantear la red

Máquina 2 6 7 6 7 7

Máquina 3 6 6 5 7 6

Máquina 4 5 6 6 6 5

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: Modelo de Programación Lineal 

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: Interpretación de resultados 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 trabajará con la máquina 4 El candidato 4 no trabajaría Así tendremos un costo de: 24 ( Z*=6+8+5+0+5)