Tarea ejercicios Vogel PDF

Preview

Summary

Ejercicios resueltos vogel...

Description

Universidad Nacional Autónoma de Honduras Valle de sula Clase: Investigación de Operaciones

Seccion clase: 1100

Catedrática: Ing. Maria Recinos

Estudiante: Hesler Aldair Paz

Número de cuenta estudiante: 20172001839

Trabajo: Informe sobre modelo de asignación y método Vogel

Fecha: 30/04/2020

Introducción Modelo de transporte es una técnica que busca determinar un programa de transporte de productos o de mercancías desde los origines hasta los destinos al menor costo posible. El método de asignación se utiliza para resolver problemas de programación lineal con unas características muy especiales. Ambos métodos tienen diferente función, bueno son utilizados para resolver problemas distintos con diferente aplicación. Justamente sobre estos temas tratara este informe, el cual su objetivo es el entendimiento por medio de investigación acerca de estos temas, y será acompañado de ejercicios para demostrar la perfecta comprensión del tema.

Marco teórico El modelo de transporte Definición del modelo Supongamos que existen m orígenes y n destinos. Sea ai el número de unidades disponibles para ofrecerse en cada origen i (i=1,2,...,m) y sea bj el número de unidades requeridas en el destino j (j=1,2,.,n) Sea cij el costo de del transporte por unidad en la ruta (i,j) que une el origen i con el destino j. El objetivo es determinar el número de unidades transportadas del origen i la destino j de manera que minimicen los costos totales de transporte. Sea xij el número de unidades transportadas del origen i al destino j; entonces el modelo de programación lineal equivalente está dado como:

sujeto a:

A fin de apreciarla estructura especial del modelo de transporte consideremos un ejemplo con dos orígenes ( m=2 ) y tres destinos (n=3). La tabla del programa lineal asociado al problema se muestra en la Tabla 1. Todos los elementos que faltan son iguales a cero.

Variables del origen 1

Variables del origen 2

Z │ x11 x12 x13 x21 x22 x23 ───────────────────┼─────────────────────────────────────────── Ecuación │ objetivo │ c11 c12 c13 c21 c22 c23 ───────────────────┼─────────────────────────────────────────── Restricciones 0 │ 1 1 1 a1 de origen 0 │ 1 1 1 a2 ...................│........................................ ... Restricciones 0 │ 1 1 b1 de destino 0 │ 1 1 b2 0 │ 1 1 b3 ───────────────────┴─────────────────────────────────────────── Tabla 1 Todos los coeficientes diferentes de 0 son iguales a +1. La forma rectangular de la Tabla 1 no ofrece una solución obvia de inicio. Esta dificultad se evita presentando el problema de una forma más conveniente. Esta clase de disposición ( Tabla 2 ) es la que se utiliza para desarrollar la técnica de transporte.

1 1 Origen i 2

c11 x11

Destino j 2 c12 x12

Demanda

c13

c22 x22

b1

Oferta

x13

c21 x21

3

c23 x23

b2

a1 a2

b3

Balanceo del modelo del transporte La definición general del modelo de transporte implica que:

Esto significa que la oferta en todos los orígenes debe igualar a la demanda de todos los destinos. En problemas reales esta restricción no necesita satisfacerse siempre. En otras palabras la oferta disponible puede ser menor que la demanda o excederla. En este caso se dice que el modelo no está balanceado. La restricción mi=1 ai = nj=1 bj se impone únicamente porque es fundamental al desarrollar la técnica de transporte. Sin embargo cualquier problema real puede balancearse artificialmente convirtiéndolo a un problema con igual oferta y demanda.

Si la demanda excede a la oferta, se aumenta un origen ficticio que suministrará la cantidad de j bj - i ai. Si existe exceso de oferta se utiliza un destino ficticio para absorber la cantidad de i ai - j bj. Los costos de "transporte" por unidad desde el origen ficticio a todos los destinos son cero ya que esto es equivalente a no transportar desde el origen ficticio. En forma semejante, los costos de "transporte" por unidad desde todas las fuentes a todos los destinos ficticios son cero. Físicamente las cantidades enviadas desde un origen ficticio pueden interpretarse como escasez de la demanda, mientras que los asignados a un destino ficticio pueden interpretarse como capacidades no utilizadas en el origen. Método de Aproximación de Vogel (MAV) Este método es heurístico y usualmente proporciona una mejor solución de inicio que los dos métodos anteriores. Generalmente el MAV produce una solución de inicio óptima o cercana a la óptima. Los pasos del procedimiento son los siguientes: Paso 1: Evaluar una penalización para cada fila ( columna ) restando el elemento de costo más pequeño en la fila (columna) del siguiente elemento de costo más pequeño en la misma fila (columna). Paso 2: Identificar la fila o columna con la penalización mayor, rompiendo arbitrariamente los empates. Asignar tanto como sea posible a la variable con el costo mínimo en la fila o columna seleccionados. Ajuste la oferta y la demanda y tache la fila o la columna satisfechas. Si una fila y una columna se satisfacen simultáneamente, únicamente uno de ellos se tacha y a la fila ( columna ) restante se le asigna una oferta (demanda) cero. Cualquier fila o columna con oferta o demanda cero no deberán ser utilizados al calcular futuras penalizaciones ( en el paso 3 ). Paso 3: a) Si exactamente una fila o una columna permanece sin tachar; parar. b) Si únicamente una fila ( columna ) con oferta (demanda) positiva permanece sin estar tachada, determinar las variables básicas en la fila (columna) por el método de costo mínimo. c) Si todos las filas y columnas no tachados tienen oferta y demanda cero, determinar las variables básicas por el método de costo mínimo. Parar d) En cualquier caso calcular las penalizaciones para las filas y columnas no tachadas y después ir al paso 2. Modelo de asignación 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.

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. Método húngaro cuando se trata de maximizar 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.

1) La empresa JJK Tech posee 4 empleados para 4 procesos en la producción de una consola de videojuegos, encuentre la persona ideal para cada puesto de trabajo. Los costos asociados se pueden observar en la siguiente tabla: Producción 3 5 4 6

Persona 1 Persona 2 Persona 3 Persona 4

Ensamblado 8 4 3 2

Empaque 1 7 9 3

Venta 6 7 4 1

SOLUCION: Persona 1 Persona 2 Persona 3 Persona 4

Producción 3 5 4 6

Ensamblado 8 4 3 2

Empaque 1 7 9 3

Venta 6 7 4 1

# Fila men 1 4 3 1

Una vez restado el número menor de cada fila, en cada fila, queda lo siguiente Persona 1 Persona 2 Persona 3 Persona 4 # Col men

Producción 2 1 1 5 1

Ensamblado 7 0 0 1 0

Empaque 0 3 6 2 0

Venta 5 3 1 0 0

Se hace lo mismo pero ahora con las columnas, quedando lo siguiente Persona 1 Persona 2 Persona 3 Persona 4

Producción 1 0 0 4

Ensamblado 7 0 0 1

Empaque 0 3 6 2

Venta 5 3 1 0

Se trazan la menor cantidad de líneas para cubrir los ceros, en este caso al quedarnos 4, ya tenemos la solución de nuestro sistema. Persona 1 = Empaque

1

Persona 2 = Ensamblado 4 Persona 3 = Producción Persona 4 = Venta

4 1

Costo mínimo total= 20 um

2) Una empresa tiene 3 vacantes para 3 puestos de trabajo y necesita contratar personal, por lo que convoca a personas que quieran hacerse del cargo. llegaron a concursar 5 personas, por lo que la empresa deberá decidir a quienes contratar, y para que puesto de trabajo, por lo que han tomado a bien analizar el nivel de productividad de cada concursante, arrojando lo siguientes resultados. Puesto 1 7 5 10 10 8

Ana Alejandra Fausto Hesler Alex

Puesto 2 10 2 1 4 6

Puesto 3 3 9 8 10 3

SOLUCION: Puesto que no está balanceada se procederá a agregar dos columnas nuevas con el mínimo valor posible. Y al ser de maximización, se procederá a restar el negativo menor a cada numero de cada fila o columna, luego se trabaja como en minimizar, restando el menor de cada fila y columna. Quedando lo siguiente: Puesto 1 3 3 0 0 0

Ana Alejandra Fausto Hesler Alex Ana = Puesto 2

10

Fausto = Puesto 1

10

Hesler = Puesto 3

10

Puesto 2 0 8 9 6 2

Puesto 3 7 1 2 0 5

F1 0 0 0 0 0

F2 0 0 0 0 0

Zmax= 30 um

3) La empresa JJK Tech tiene un mercado muy exclusivo con su nueva consola, la SP5, distribuyéndola a Canadá, USA, Honduras y China. La sede de esta empresa es Honduras y Consta de 4 fábricas a lo largo del territorio catracho. Los costos de envío, La oferta y demanda están incluidos en la siguiente tabla: Fabrica 1 Fabrica 2 Fabrica 3 Fabrica 4 Demanda

Canadá 10 20 45 24 200

USA 27 20 30 50 200

Honduras 20 10 34 5 250

China 54 37 13 39 150

Oferta 300 100 150 250 800

SOLUCION: Se identifican los dos costos más bajos por renglón y columna y se restan entre sí, y se identifica la penalización más grande y se le asigna la mayor cantidad de producción o material a transportar Fabrica 1 Fabrica 2 Fabrica 3 Fabrica 4 Demanda Penalización

Canadá 10 20 45 24 200 10

USA 27 20 30 50 200 10

Honduras 20 10 34 5 250 5

China 54 37 13 (150) 39 150 24

Oferta 300 100 150 250 800

Penalización 10 10 17 19

Se repite el proceso con las filas y columnas sin sombrear Fabrica 1 Fabrica 2 Fabrica 3 Fabrica 4 Demanda Penalización

Canadá 10 20 45 24 200 10

USA 27 20 30 50 200 7

Honduras 20 10 34 5 (250) 250 5

China 54 37 13 (150) 39 150

Oferta 300 100 (150) 250 800

Penalización 10 10

Fabrica 1 Fabrica 2 Fabrica 3 Fabrica 4 Demanda Penalización

Canadá 10 (200) 20 45 24 200 10

USA 27 20 30 50 200 7

Honduras 20 10 34 5 (250) 250

China 54 37 13 (150) 39 150

Oferta 300 (100) 100 (150) (250) 800

Penalización 17 0

Canadá 10 (200) 20 45 24 200

USA 27 (100) 20 (100) 30 50 200

Honduras 20 10 34 5 (250) 250

China 54 37 13 (150) 39 150

Oferta 100 100 (150) (250) 800

Penalización

Fabrica 1 Fabrica 2 Fabrica 3 Fabrica 4 Demanda

Honduras 20 10 34 5 (250) 250

China 54 37 13 (150) 39 150

Oferta 100 100 150 250 800

Queda todo cubierto, por lo tanto Fabrica 1 Fabrica 2 Fabrica 3 Fabrica 4 Demanda

Canadá 10 (200) 20 45 24 200

USA 27 (100) 20 (100) 30 50 200

Costo global de envío = 10(200)+27(100)+20(100)+5(250)+13(150) Zmin = 9900 um

19

4) El equipo de futbol Olimpia cuenta con 3 canteras de futbolistas ubicadas en Tegucigalpa, San Pedro Sula, Santa Bárbara. Y tiene un mercado de futbolistas que abarca a España, Inglaterra y Alemania. Las utilidades de cada exportación de futbolistas, así como las demandas y ofertas están en la siguiente tabla. Tegucigalpa San pedro sula Santa Bárbara Demanda

España 3 7 2 20

Inglaterra 9 10 5 10

Alemania 4 7 1 15

Oferta 10 15 20

SOLUCION: Tegucigalpa San pedro sula Santa Bárbara Demanda Penalización

España 3 7 2 20 4

Inglaterra 9 (10) 10 5 10 1

Alemania 4 7 1 15 3

Oferta 10 15 20

Penalización 5 3 3

España 3 7 2 (20) 20 5

Inglaterra 9 (10) 10 5 10

Alemania 4 7 (15) 1 15 6

Oferta 10 15 20

Penalización

Tegucigalpa San pedro sula Santa Bárbara Demanda Penalización

Zmax= 2(20)+9(10)+7(15) = 235 um

0 1

Conclusión Hoy en día, la gran mayoría de las industrias a nivel mundial, utilizan este tipo de estrategias para lograr un mayor nivel de competitividad comercial, ya que, se logra obtener las mejores rutas para incrementar la economía y estabilidad empresarial. El método de transporte es tan sólo una parte de todo el sistema de distribución que se encuentra dentro de la compañía. Es muy difícil resolver o encontrar el mejor programa de transporte que interactúe en cuestiones de servicio y bajo costo al mismo tiempo. Esa área de la empresa requiere de una constante atención y un análisis muy preciso para implementar todos los cambios que genere la solución factible del método.

Bibliografía Problema de la asignación. (2020). Retrieved 30 April 2020, from https://es.wikipedia.org/wiki/Problema_de_la_asignaci%C3%B3n#M%C3%A9todo_H%C3%BAngaro

Modelo de transporte y asignaci�n. (2020). Retrieved 30 April 2020, from http://www.geocities.ws/mdmoli/archivos/ioi3/unidad3ioi.html...