El método de aproximación de Vogel PDF

Preview

Summary

método de aproximación Vogel...

Description

El método de aproximación de Vogel Es un método heurístico de resolución de problemas de transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere de la realización de un número generalmente mayor de iteraciones que los demás métodos heurísticos existentes con este fin, sin embargo, produce mejores resultados iniciales que los mismos. Es un método de resolución de problemas de transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere de la realización de un numero generalmente mayor de iteraciones que los demás métodos heurísticos existentes con este fin, sin embargo, produce mejores resultados iniciales que los mismos Este procedimiento trata de eliminar casi toda la tabla simplex además de los datos de entrada, para llegar a la única información necesaria que es la solución básica factible actual, los valores actuales y los valores resultantes de las variables no básicas. Es posible apreciar de manera global la gran diferencia en eficiencia y conveniencia entre los métodos simplex de transporte y simplex si ambos se aplican al mismo problema pequeño. Algoritmo de Vogel El método consiste en la realización de un algoritmo que consta de 3 pasos fundamentales y 1 más que asegura el ciclo hasta la culminación del método.

•

Paso 1 Determinar para cada fila y columna una medida de penalización restando

los dos costos menores en filas y columnas. •

Paso 2 Escoger la fila o columna con la mayor penalización, es decir que de la

resta realizada en el (Paso 1) se debe escoger el número mayor. En caso de haber empate, se debe escoger arbitrariamente (a juicio personal). •

Paso 3 De la fila o columna de mayor penalización determinada en el paso anterior

debemos de escoger la celda con el menor costo, y en esta asignar la mayor cantidad posible de unidades. Una vez se realiza este paso una oferta o demanda quedará satisfecha por ende se tachará la fila o columna, en caso de empate solo se tachará 1, la restante quedará con oferta o demanda igual a cero (0). •

Paso 4: De ciclo y excepciones Si queda sin tachar exactamente una fila o columna con cero oferta o

demanda, detenerse. Si queda sin tachar una fila o columna con oferta o demanda positiva, determine las variables básicas en la fila o columna con el método de costos mínimos, detenerse.

Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda, determine las variables básicas cero por el método del costo mínimo, detenerse. Si no se presenta ninguno de los casos anteriores vuelva al paso 1 hasta que las ofertas y las demandas se hayan agotado. ventajas 1. Conduce rápidamente a una mejor solución. mediante los cálculos de las llamadas penalizaciones de fila y columna, los cuales representan el posible coste de penalización que se obtendría por no asignar unidades a transportar a una determinada posición. 2. Tiene en cuenta en el análisis la diferencia entre los menores costos de transporte, mediante los cálculos de las llamadas penalizaciones de fila y columna, los cuales representan el posible coste de penalización que se obtendría por no asignar unidades a transportar a una determinada posición. 3. Es un método preciso y totalmente imparcial. 4. Se escogerá aquel sitio que produzca los menores costos de transporte, tanto de la materia prima como del producto terminado. desventajas 1. No aporta ningún criterio que permita determinar si la solución obtenida por este método es la mejor (óptima) o no. 2. Las cantidades de oferta y demanda no varían con el tiempo.

3. No considera más efectos para la localización que los costos de transporte. 4. requiere mayores esfuerzos de cálculos que el Método de la esquina noroeste

Objetivo Es reducir al mínimo posible los costos de transporte destinados a satisfacer los requerimientos totales de demanda y materiales. Específicos 1. Identificar los elementos necesarios para un servicio óptimo de entrega y de satisfacción al cliente que recibirá su producto en las condiciones ofrecidas. 2. Determinar los beneficios del rediseño del área de distribución del departamento de operaciones. 3. Minimizar el tiempo del proceso de distribución desde el momento de carga del producto, hasta su recepción. 4. Diseñar un programa de mantenimiento preventivo de los vehículos para evitar una depreciación alta en los activos de la empresa. 5. Establecer las zonas de entrega óptimas que permitan hacer una distribución eficiente.

Características: 1. se debe enviar las mayores cantidades al mayor costo posible 2. tienen diferentes orígenes con diferentes destinos 3. un origen puede abastecer a diferentes destinos 4. Al finalizar el ejercicio la oferta y la demanda deben ser 1. Satisfecha en su totalidad y terminando sus valores en cero 5. la aproximación de Vogel finaliza en costo mínimo 6. es más elaborado que los anteriores, más técnico y dispendioso 7. tiene en cuenta los costos, las ofertas y las demandas para hacer las asignaciones 8. generalmente nos deja cerca al óptimo Una Aproximación es una representación inexacta que, sin embargo, es suficientemente fiel como para ser útil. Aunque en matemáticas la aproximación típicamente se aplica a números, también puede aplicarse a objetos tales como las funciones matemáticas, figuras geométricas o leyes físicas. Por otra parte, existen problemas que son demasiado complejos para resolverse analíticamente, o bien imposibles de resolver con las herramientas disponibles. En estos casos, una aproximación puede arrojar una solución suficientemente exacta, reduciendo significativamente la complejidad del problema y el costo de su solución. El método de aproximación de Vogel es un método heurístico (se basan en hallar una solución de calidad aceptable mediante la exploración de una parte del universo de todas soluciones posibles) de resolución de problemas de transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere

de la realización de un número generalmente mayor de iteraciones que los demás métodos heurísticos existentes con este fin, sin embargo produce mejores resultados iniciales que los mismos. Este método punta al análisis de los costos de transporte, tanto de materias primas como de productos terminados. APLICACIÓN El modelo se utiliza para ayudar a la toma de decisiones en la realización de actividades como: control de inventarios, flujo de efectivo, programación de niveles de reservas en prensas entre otras. Este método es heurístico y suele producir una mejor solución inicial, produce una solución inicial óptima, o próxima al nivel óptimo. Este método requiere mayor esfuerzo que el método de la Esquina Noreste, pero conduce a una solución inicial bastante mejor, pues tiene en cuenta la in formación de los costes de transporte a través de penalizaciones de fila y columna, que representan el posible coste de penalización que se obtendría por no situar unidades a transportar en una determinada posición. El método de la esquina noroeste y el método de Vogel se diferencian únicamente en el paso de selección de la variable a asignar. Para la selección de dicha variable se calculan en la tabla de costes las diferencias por filas y por columnas que se definen de la siguiente manera •

DFi = diferencia en valor absoluto de los 2 costes menores de la fila i.

•

DCj = diferencia en valor absoluto de los 2 costes menores de la columnaj.

El objetivo de este modelo es dimensionar la flota de reparto y obtener una adecuada utilización de la misma, mediante integración en tamaño y en modalidad de dependencia. El centro de distribución está destinado a dimensionar el espacio necesario para almacenar producto, envases vacíos, preparación de pedidos, carga, descarga de vacíos y devoluciones, la demanda de mano de obra a lo largo del año y su distribución horaria a lo largo del día de trabajo. El plan de mejora continua que se propone permitirá contar con empleados hábiles, entrenados para hacer el trabajo bien, para controlar los defectos, errores y realizar diferentes tareas u operaciones; contar con empleados motivados que pongan empeño en su trabajo, que busquen realizar las operaciones de manera óptima y sugieran mejoras; contar con empleados con disposición al cambio, que puedan ser capaces y estén dispuestos a adaptarse a nuevas situaciones en la organización. El método comienza calculando por cada columna y por cada fila el castigo. El castigo se calcula como la diferencia entre los dos costos menores en la columna o en la fila según corresponda. A continuación, se determina la fila o columna con un mayor valor de castigo. Luego, se selecciona como variable basal la celda con menor costo de la fila o columna, según corresponda, y se le asigna la máxima cantidad posible. Una vez realizada la asignación, se descarta la fila o columna cuya oferta o demanda haya sido completa. Se recalcula la demanda u oferta disponible en la fila o columna. La primera asignación se ha completado. Se vuelven a calcular los castigos por fila y por columna y se repite el procedimiento descrito hasta completar las asignaciones posibles en la tabla. La ventaja del método de Vogel por sobre el de la Esquina Noroeste es que va

adelante algunas iteraciones y por lo tanto se obtiene una solución inicial mejor. Eventualmente puede ocurrir que aplicando el método se llegue directamente a la solución óptima. La desventaja del método de Vogel radica en que sin duda es más complejo que el de la esquina noroeste, por lo tanto, es más difícil de implementar y más propenso a errores en la aplicación. Este método requiere mayores esfuerzos de cálculos que el MEN; sin embargo, permite obtener una solución inicial mejor que en el caso anterior puesto que tiene en cuenta la información de los costes de transporte, mediante los cálculos de las llamadas penalizaciones de fila () y columna, los cuales representan el posible coste de penalización que se obtendría por no asignar unidades a transportar a una determinada posición. Ha sido el método más popular durante muchos años, en parte porque es relativamente fácil hacerlo a mano. Este método también es denominado método de Balas-Hammer. Algoritmo esquina noreste Como antes mencionado, este método, es relativamente fácil de aplicarlo para problemas de transporte y determinar una solución factible inicial, se debe tomar en cuenta que esta solución no necesariamente es la más óptima. El primer paso del algoritmo es en seleccionar la celda de la esquina noroeste. El siguiente paso está en escoger el más grande suministro como pueda en la esquina de la celda de la esquina noroeste, esta operación agotará completamente la disponibilidad de suministros en un origen a los requerimientos

de demanda en un destino. A este procedimiento o paso se le llama con frecuencia saturar. Finalmente, el tercer paso de la primera iteración está en corregir los números del suministro y requerimiento para reflejar lo que va quedando de suministro y vuelva al paso uno. Algunas sugerencias a tomar en cuenta al momento de realizar el método: Los envíos son indicadores dentro de cada celda. Los suministros y requerimientos que quedan pueden ser registrados a la derecha de los números originales. Las filas correspondientes a los orígenes pueden ser eliminadas o señaladas, después de que sus requerimientos estén completamente llenos. Algoritmo de Vogel Como antes mencionado este método es más óptimo que el método anterior, ya que la solución que este encuentra se le puede decir que es una solución óptima o más cercana a la óptima. A continuación, se muestran los pasos para la solución mediante el método Vogel. En el primer paso es siempre importante verificar que el problema dado este balanceado, lo que se quiere decir con esto es que ya sea tanto la oferta como la demanda sean iguales entre ellos. Si se diera el caso de que el problema dado no esté balanceado entonces se procede a solucionarlo de la siguiente manera:

1. En el caso de que la oferta total es mayor a la demanda total se agregara un destino ficticio. 2. Caso contrario de que si la demanda total es superior a la oferta total se agregara un origen ficticio. Continuando con el segundo paso, se construirá una matriz de transporte, en este paso se supone que el problema ya deberá estar balanceado. En el tercer paso, se aplica unas reglas necesarias para la solución del método: Se obtiene la resta entre los dos coeficientes de costo más pequeños para cada fila y para cada columna, este resultado se puede escribir al margen derecho y el margen inferior según corresponda. Se identifica la fila o columna con la diferencia de costos mínimos más grande. Asignar tanto como sea posible a la celda que tiene el costo más pequeño tratando de satisfacer la demanda en función también de la disponibilidad de la oferta, e ir disminuyendo la oferta y demanda correspondiente. Se deberá eliminar la fila y también si existe una columna en donde se haya agotado la oferta o la demanda este satisfecha. Se repite el paso tres hasta que las columnas y las filas se eliminen. Finalmente se podría decir que el algoritmo está dado por acabado, pero también existe una manera de analizar si la solución es factible. Para poder realizar esto se utilizará una función de m + n – 1 = Numero de asignaciones.

En donde tenemos que m = número de filas, y n = número de columnas. Ejemplo La empresa energética de Guatemala dispone de cuatro plantas de generación para satisfacer la demanda diaria eléctrica en cuatro departamentos Izabal Jutiapa, peten y Cobán. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día respectivamente. Las necesidades de los departamentos de Izabal, Jutiapa, peten y Cobán son de 70, 40, 70 y 35 millones de Kw al día respectivamente. Los costos asociados al envío de suministro energético por cada millón de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla.

Izabal Planta 1 Planta 2 Planta 3 Planta 4

Jutiapa 2 6 1 3

5 3 6 4

Peten

Cobán 3 1 4 6

7 6 2 6

El primer paso es determinar las medidas de penalización y consignarlas en el tabulado de costos, tal como se muestra a continuación. Izabal

Jutiapa

Peten

Cobán

Oferta

Penalizació n

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

5 3 6 4 70 1

2 6 1 3 40 1

7 6 2 6 70 4

3 1 4 6 35 2

80 30 60 45

1 2 1 1

•

De color verde están los 2 datos menores de la columna 3 y 4 estos valores se restan al valor absoluto =1

•

De color amarillo están los dos datos menores de la fila 2 y 3 estos se restan al valor absoluto =1

El paso siguiente es escoger la mayor penalización Izabal

Jutiapa

Peten

Cobán

Oferta

Penalizació n

Planta 1 Planta 2 Planta 3 Planta 4 Demanda Penalizació

5 3 6 4 70 1

2 6 1 3 40 1

7 6 2 6 70 4

3 1 4 6 35 2

80 30 60 45

1 2 1 1

n

•

En este paso se escoge la personalización “4” y se selecciona la columna o fila a la cual corresponde.

El paso siguiente es escoger de esta columna el menor valor, y en una tabla paralela se le asigna la mayor cantidad posible de unidades, podemos observar como el menor costo es 2 y que a esa celda se le pueden asignar como máximo 60 unidades que es la capacidad de la planta 3. Izabal

Jutiapa

Peten

Cobán

Oferta

Penalizació n

Planta 1 Planta 2 Planta 3 Planta 4 Demanda Penalizació

5 3 6 4 70 1

2 6 1 3 40 1

7 6 2 6 70 4

3 1 4 6 35 2

80 30 60 45

1 2 1 1

n Este es el menor valor de la columna penalizada, entonces se le asigna la mayor cantidad de unidades posibles, que en este caso es 60 unidades. Izabal Planta 1 Planta 2 Planta 3 Planta 4 Demanda

Jutiapa

Peten

Cobán

60 70

40

70

Oferta 80 30 60 45

35

Dado que la fila de la Planta 3 ya ha asignado toda su capacidad 60 unidades esta debe desaparecer. Izabal

Jutiapa

Peten

Cobán

Oferta

Penalizació n

Planta 1 Planta 2

5 3

2 6

7 6

3 1

80 30

1 2

Planta 4 Demanda Penalizació

4 70 1

3 40 1

6 10 4

6 35 2

45

1

n

Se procede a eliminarse la fila correspondiente a la planta que ha quedado sin unidades, además observamos como la demanda de peten se modifica, ahora solo necesita 10 unidades, dado que se le resta la cantidad ya asignada.

Se ha llegado al final del ciclo, por ende, se repite el proceso Izabal

Jutiapa

Peten

Cobán

7 6 6 10 0

3 1 6 35 2

Oferta

Penalizació n

Planta 1 Planta 2 Planta 4 Demanda Penalizació

5 3 4 70 1

2 6 3 40 1

80 30 45

1 2 1

n

Aquí en los datos en verde tenemos datos iguales “empate” se elige de manera arbitraria. Izabal

Jutiapa

Peten

Cobán

7 6 6 10 0

3 1 6 35 2

Oferta

Penalizació n

Planta 1 Planta 2 Planta 4 Demanda Penalizació

5 3 4 70 1

2 6 3 40 1

80 30 45

1 2 1

n

El dato más pequeño de esta columna es 1. Izabal Jutiapa Peten Cobán Oferta Planta 1 80 Planta 2 30 30 Planta 3 60 60 Planta 4 45 Demanda 70 40 70 35 Asignamos en esta celda la mayor cantidad de unidades posibles, es decir 30 por la capacidad de la planta 2. Izabal

Jutiapa

Peten

Cobán

Oferta

Penalizació

n Planta 1

5

2

7

3

80

1

Planta 4 Demanda Penalizació

4 70 1

3 40 1

6 10 0

6 5 2

45

1

n Dado que la planta 2 se ha quedado sin unidades se elimina y la demanda de barranquilla ahora es 35-30=5. Se inicia una nueva interacción. Izabal

Jutiapa

Peten

Cobán

Oferta

Penalizació n

Planta 1 Planta 4 Demanda Penalizació

5 4 70 1

2 3 40 1

7 6 10 1

3 6 5 3

80 45

1 1

n El menor valor de esta columna es 3, por ende, se le asigna la mayor cantidad de unidades posibles, la cual se ve restringida por la demanda de Cobán la cual es de 5 unidades. Izabal Planta 1 Planta 2 Planta 3 Planta 4 Demanda

Jutiapa

Peten

Cobán 5 30

60 70

40

70

Oferta 80 30 60 45

35

Observamos como queda satisfecha la demanda de Cobán por ende desaparecerá, así mismo la oferta de la demanda 1 queda limitada a 80-5= 75 unidades.

Izabal

Jutiapa

Peten

Oferta

Penalizació n

Planta 1 Planta 4 Demanda Penalizació

5 4 70 1

2 3 40 1

7 6 10 1

75 45

n

Continúan las interacciones.

Izabal

Jutiapa

Peten

Oferta

Penalizació n

Planta 1 Planta 4 Demanda Penalizació

5 4 70 1

2 3 40 1

7 6 10 1

75 45

3 1<...