Deterministicos

INTRODUCCION

Apreciado estudiante:

A continuación encontrará explicación a los algoritmos utilizados para solucionar los temas de la segunda unidad como son:

- METODOS DE TRANSPORTE

- ASIGNACION

- CPM-PERT

- PROGRAMACION DINAMICA

De cada tema se presenta: la descripción general, los pasos para solucionar los ejercicios, un ejemplo práctico y unas preguntas, las cuales usted debe responder para obtener la respectiva calificación.

La cantidad de preguntas a responder son 10 en total .

Tiene posibilidad de 2 intentos para realizar la actividad.

Exitos.

METODOS DE TRANSPORTE

Se han desarrollado varios métodos para resolver un problema de transporte, dentro de los cuales, loscomunes son:

Esquina Noroeste

Mínimos

Vogel

Prueba de Optimidad

La meta de un modelo de transporte es minimizar el costo total de un envío de un producto desde los puntos de existencia hasta los puntos de demanda bajo las siguientes condiciones:

La función objetivo y las restricciones deben ser lineales.

Las mercancías para distribuir deben ser uniformes.

La suma de la capacidad de todos los orígenes deben ser iguales a la capacidad de los destinos; es decir oferta igual a demanda.

Identificación de las restricciones:

El embarque total de cada planta no se debe exceder de su capacidad.

El embarque total recibido por cada tienda al por menor debe satisfacer se demanda.

EJEMPLO

A continuación se dan las capacidades de 3 fábricas y las necesidades de 3 almacenes y los costos unitarios de transporte.

ESQUINA NOROESTE

Es uno de los métodos más fácil para determinar una solución básica factible inicial. Este también considerado por ser el menos probable para dar una buena solución de "bajo costo" porque ignora la magnitud relativa de los costos.

Pasos para desarrollar este método:

1. Seleccionar la celda de la esquina noroeste (esquina superior izquierda).

2. Haga el más grande envío 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.

3. Corrija los números del suministro y requerimiento para reflejar lo que va quedando de suministro y vuelva al paso uno.

Reglas para el desarrollo del método esquina noroeste:

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.

DESARROLLO DEL EJERCICIO

Costo Total = (400*2)+(100*3)+(600*1)+(200*5)+(1000*12)

Costo Total = 800+300+600+1000+12000

Costo Total = $ 14.700

Es improbable que este plan factible sea también el plan de envío factible del mínimo costo, ya que ignoramos la magnitud relativa de los costos unitarios en cada interacción.

En general para saber si la solución es óptima existe una regla la cual dice que m+n-1 debe ser igual al número de casillas ocupadas por cantidades en donde n = a las columnas y m = a las filas, esta es utilizada para determinar si la solución inicial es degenerada o no

METODO DE LOS MINIMOS

El método de la celda del mínimo costo es similar al método anterior diferenciándose solo en el primer paso:

Considere todas las celdas que están contenidas en las filas o columnas señaladas. Seleccione la celda que tenga el bajo costo, se empieza a saturar como en los pasos anteriores.

Como se mencionó el procedimiento a seguir en adelante será de la misma forma que el de la E:N, es decir una vez asignada la cantidad en la casilla seleccionada con el menor costo se reiterará el procedimiento hasta agotar todas las existencias y satisfacer todas las necesidades o requerimientos, siempre teniendo en cuenta el bajo costo de la celda.

Costo Total = (400*2)+(100*6)+(700*1)+(100*5)+(1000*12)

Costo Total = 800+600+700+500+12000

Costo Total = $ 14.600

METODO DE APROXIMACION DE VOGEL

Este método es considerado el más cercano a una solución óptima para evaluar una solución factible de bajo costo.

Procedimiento

Se restan los dos valores mínimos de cada columna e igualmente en las filas,

Se toma como punto de partida el valor mínimo de la columna o fila en donde se encuentra ubicado el mayor valor obtenido en la resta inicial(mayor diferencia)

Se repite los pasos anteriores con las filas y columnas que aún quedan sin saturar hasta que se asignen todas las cantidades requeridas para satisfacer la demanda de acuerdo a la oferta dada.

Se determina el costo y se verifica que la tabla no sea degenerada.

Se aplica la técnica del salto de la piedra para buscar la solución óptima en caso de poder hacerlo.

METODO VOGEL(CONTINUACION)

Ct= 400 * 2 + 100 * 6 + 700 * 1 + 100 * 5 + 1000 * 1 = 3600

M + n – 1 = 5 lo que corresponde al mismo número de casillas ocupadas.

Estamos listos para aplicar la prueba de optimalidad.

En los modelos de transporte la meta que se propone es:

Su respuesta :

Minimizar el costo de envío total de un producto

correcto

La esquina noroeste es la más fácil para determinar una solución básica factible, pero su problema es

Su respuesta :

Su solución es adecuada pero no siempre es la de bajo costo.

correcto

PRUEBA DE OPTIMALIDAD, SALTO DE LA PIEDRA

Para saber que tan factibles son todos los métodos anteriores se ha desarrollado la prueba de optimalidad que determina si el método es el que ofrece el menor costo de envío. La prueba se lleva a cabo mediante el cálculo de un solo número conocido como costo reducido, para cada celda vacía.

Para calcular el costo reducido seleccione en orden los ceros que encuentre.

1.9 REGLAS PARA EL DESARROLLO DE LA PRUEBA DE OPTIMALIDAD O SALTO DE LA PIEDRA

Las piedras serán las cantidades asignadas a cada casilla de la tabla.

Se llamaran charcos las casillas vacías de la tabla.

Salto horizontal en piedra, es decir en forma vertical o en forma horizontal.

Realizar el mínimo de saltos posibles.

La casilla a evaluar comienza con un signo (+) positivo y a medida

...