El Problema De Asignacion

1- PROBLEMA Y JUSTIFICACIÓN

Se origina al no tener la información impresa en un libro a la mano de cada alumno de la clase, lo cual origina que los alumnos del ITVH investiguen por su cuenta el tema número 3. De la materia modelos de optimización de recursos, en la cual es tema 3. Se llama “algoritmos especiales de programación lineal” el cual desprende otros 3 puntos o subtemas, lo cuales son 3.1 el problema de transporte, 3.1.1planteamiento del problema, 3.1.2determinacion de la solución básica factible inicial, 3.1.3 el criterio de optimabilidad y el algoritmo de mejoramiento de la solución, 3.2 el problema de asignación, 3.2.1 planteamiento del problema, 3.2.2 algoritmo para determinar la asignación optima, 3.3 el uso de software.

2- OBJETIVO GENERAL Y ESPECIFICO

Definir las características de los algoritmos especiales de programación lineal respecto de los problemas clásicos.

Modelar fenómenos relativos a problemas de transporte y asignación, optimizar soluciones a los problemas de transporte y asignación utilizando los algoritmos específicos en cada caso, utilizar e interpretar el software en la solución de problemas.

TIPO DE INVESTIGACIÓN:

DOCUMENTAL

MARCO TEORICO

ALGORITMOS ESPECIALES DE PROGRAMACIÓN LINEAL

PROGRAMACIÓN LINEAL:

La programación lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de un sistema de inecuaciones lineales, optimizando la función objetivo, también lineal.

Consiste en optimizar (minimizar o maximizar) una función lineal, denominada función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales

PROGRAMACIÓN ENTERA:

En algunos casos se requiere que la solución óptima se componga de valores enteros para algunas de las variables. La resolución de este problema se obtiene analizando las posibles alternativas de valores enteros de esas variables en un entorno alrededor de la solución obtenida considerando las variables reales. Muchas veces la solución del programa lineal truncado esta lejos de ser el óptimo entero, por lo que se hace necesario usar algún algoritmo para hallar esta solución de forma exacta.

El más famoso es el método de 'Ramificar y Acotar' o Branch and Bound por su nombre en inglés. El método de Ramificar y Acotar parte de la adición de nuevas restricciones para cada variable de decisión (acortar) que al ser evaluado independientemente (ramificar) lleva al óptimo entero.

APLICACIONES:

La programación lineal constituye un importante campo de la optimización por varias razones, muchos problemas prácticos de la investigación de operaciones pueden plantearse como problemas de programación lineal.

Algunos casos especiales de programación lineal, tales como los problemas de flujo de redes y problemas de flujo de mercancías se consideraron en el desarrollo de las matemáticas lo suficientemente importantes como para generar por si mismos mucha investigación sobre algoritmos especializados en su solución. Una serie de algoritmos diseñados para resolver otros tipos de problemas de optimización constituyen casos particulares de la más amplia técnica de la programación lineal.

3.1 EL PROBLEMA DEL TRANSPORTE: PLANTEAMIENTO DEL PROBLEMA DETERMINADO DE LA SOLUCIÓN BASICA FACTIBLE INICIAL, EL CRITERIO DE OPTIMALIDAD Y EL ALGORITMO DE MEJORAMIENTO DE LA SOLUCIÓN (RUTA DE LOS SIGNOS).

En matemáticas y economía, un problema de transporte es un caso particular de problema de programación lineal en el cual se debe minimizar el coste del abastecimiento a una serie de puntos de demanda a partir de un grupo de puntos de oferta —posiblemente de distinto número—, teniendo en cuenta los distintos precios de envío de cada punto de oferta a cada punto de demanda.

PLANTEAMIENTO:

Se disponen puntos de oferta o factorías con una producción determinada (representada mediante un vector, F) y puntos de demanda o mercados de demanda determinada (vector M):

Además se dispone como dato de una matriz de precios, C, de forma que es el precio de envío por unidad desde la factoría al mercado

El objetivo es calcular una nueva matriz, X, de forma que sea el número de unidades que se envían de la factoría al mercado

Con estos datos podemos formular las condiciones que se han de cumplir:

El precio total a pagar por el transporte, , que se ha de minimizar, se determinará por la suma de los productos del precio de cada unidad por el coste de envío por unidad de cada fábrica a cada mercado:

PROBLEMAS BALANCEADOS:

Se dice que el problema está balanceado cuando se cumple que:

(o, abreviadamente, es decir, la oferta es igual a la demanda).

En caso de que se incorporaría un mercado adicional al problema, el mercado artificial, de forma que su demanda sea el excedente y el coste de envío a este mercado sea nulo:

SOLUCIÓN CON MÉTODO DE CRUCE DEL ARROYO

Para que un problema de transporte pueda ser resuelto a través de éste método debe cumplir con las características que se mencionarán. Si no es posible, se deben resolver por el método simplex.

• Ser un problema balanceado.

• Contar con (n+m-1) variables de decisión, siendo n los puntos de demanda y m los puntos de oferta.

ALGORITMO:

• Crear tabla de transporte

Proveedor 1 Proveedor 2 Proveedor m

Punto de oferta 1 costo(i, j) costo(i, j+1) costo(i, j+m) Oferta 1

Punto de oferta 2 costo(i+1,j) costo(i+2,j+1) costo(i+n, j+m) Oferta 2

Punto de oferta n costo(i, j) costo(i+1,j+1) costo(i+n, j+m) Oferta n

Demanda 1 Demanda 2 Demanda m

• Establecer solución inicial

Existen varios métodos para hacer esto: Noreste y sus variaciones(Suroeste, Suroeste, etc), y Costo mínimo. Para el de costo mínimo:

•

• Ordenar los costos de mayor a menor

• En la celda (i, j) asignar el mínimo entre la demanda j, y la oferta i

• Restar a la oferta j y la demanda i el valor asignado

• repetir los últimos dos pasos hasta que la oferta y la demanda de todas las filas y columnas sea igual a 0

• Calcular índices de mejora

Todos los lugares que no contienen un valor se les considera agua y los valores asignados piedras los índices se calculan para todos los lugares que contienen agua, de tal forma que se busca moverse por fila y columna hasta generar un circuito, se multioplican los costos por +1,-1...

• Si existe una mejora realizarla y volver al paso de calcular los índices de mejora

Si se encuentra un índice negativo en los circuitos, se busca el de los -1 el menor y se le suma o resta según el signo a todo los circuitos

3.2 EL PROBLEMA DE ASIGNACIÓN: PLANTEAMIENTO DEL PROBLEMA, ALGORITMO PARA DETERMINAR LA SOLUCIÓN ÓPTIMA

EL PROBLEMA DE ASIGNACION

El problema del 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 designació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.

HISTORIA

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

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

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/fabrica de donde proviene.

Demanda: Cantidad de artículos que necesita recibir el destino para cumplir sus necesidades.

...