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,

...