Obj 6

OBJETIVO # 6. APLICAR LOS ALGORITMOS DE TRANSPORTE Y ASIGNACION PARA LA RESOLUCION DE PROBLEMAS MODELO DE TRANSPORTE Es un problema de redes, que no es usual resolverlo por Simplex, ya que queda bastante extenso, porque resultan igualdades al establecer las ecuaciones de oferta entre las fuentes y de demanda hacia los destinos. Usualmente, se tiene una determinada capacidad en cada fuente y se requiere otra en cada destino. El objetivo básico del problema del transporte es satisfacer las expectativas de los clientes estableciendo rutas entre las fuentes y los destinos a un costo mínimo; un ejemplo se muestra a continuación: Orígenes 1 2 3 Requerimient os

envío.

1 C11 C21 C31 R1

Destinos 2 C12 C22 C32 R2

3 C13 C23 C33 R3

Suministros S1 S2 S3

Donde Sn son los suministros, Rn los requerimientos y

Cnm son los costos de

El modelo del transporte es utilizado fundamentalmente cuando un producto (servicio) debe ser enviado de un almacén (fábrica) a un usuario, para lo cual es factible generar varias rutas; de éstas, la óptima es aquella de costo mínimo y corresponde a una solución que puede ser degenerada o no degenerada. Para poder resolver un problema de Transporte, este debe estar balanceado, es decir, ΣRequerimientos = ΣSuministros. Si no lo está, se debe balancear, para hacerlo si ΣRequerimientos > ΣSuministros entonces se agrega un origen, si ΣSuministros > Σ Requerimientos entonces se agrega un destino. Métodos para la resolución del modelo de Transporte Método de la esquina NOROESTE Se selecciona la celda que está mas al norte y al oeste, o lo que es lo mismo mas arriba y a la izquierda y se realiza el máximo envío posible (se resta el requerimiento de los suministros) y se coloca en la celda seleccionada, las celdas restantes quedan en blanco. Esto se repite hasta que todos los suministros y requerimientos sean 0 El costo seria: Z = cij.xij Método de Vogüel 1) Se toman los 2 menores costos en c/fila y c/columna y se halla su diferencia 2) Se selecciona la mayor diferencia y en esa línea (puede ser fila o columna), se elige la celda de menor costo y se realiza el mayor envío posible. Si con el envío se satisface el requerimiento (se hace 0 la columna), se eliminan los elementos de esa columna. Si se agotan los suministros (se hace 0 la fila) se eliminan los elementos de esa fila, si ambos se hacen 0 se eliminan los elementos de la fila y la columna. Esto se repite hasta que todos los suministros y requerimientos sean 0 El costo seria: Z = cij.xij Optimalidad de la solución. Para hallar la optimalidad de la función se utiliza el Método de los Multiplicadores. Una solución básica factible es óptima si y sólo si cij−ui−vj ≥ 0 para toda (i,j) tal que xij es no básica. Método de los Multiplicadores 1) Se escribe una tabla con las variables básicas de la tabla final.

2) Se hallan los costos asociados a cada variable básica, se utiliza la siguiente formula: Cij = ui + vj, donde u y v se hallan partiendo de u1 = 0. Cuando no se pueda hallar alguno de los valores, se dan valores arbitrarios a u o v. VB

Cij = ui + vj

u,v, u1 = 0

3) Se hace una tabla con las variables no básicas y se calcula ∆ij para c/u de ellas. Se usa la siguiente formula: ∆ij = Cij – ui – vj, donde Cij es el costo asociado a la celda en la tabla original. VNB ∆ij = Cij – ui – vj 4) Se hace la prueba de optimalidad verificando si todos los ∆ij ≥ 0. 5) Si existe un ∆ij < 0, se escoge una variable entrante que es el más negativo ∆ij. En caso de empate se selecciona la que tenga menor costo. 6) Se escoge una variable saliente. se hace un circuito en la tabla final empezando en la VE hacia la dirección que se desee tocando al menos 2 VB e intercalando signos en c/celda. 7) Se escribe una nueva tabla. Entre los valores con signo -, se selecciona el valor mas pequeño en el circuito (p), y se coloca en el lugar de la VE 8) Partiendo del valor seleccionado se van modificando los valores en la tabla para cumplir con los requerimientos y los suministros de acuerdo al signo de cada celda, si la celda tiene un + se suma p al valor de la celda y si la celda tiene un – se resta p al valor de la celda. MODELO DE ASIGNACIÓN. Corresponde a un caso especial del problema del transporte en el cual las variables Xij sólo pueden tomar el valor 0 ó 1; tomar el valor 1 si el origen i se hace corresponder al destino j y 0 en caso contrario. Este problema se presenta en diversos casos de toma de decisiones. Los problemas típicos de asignación implican asignar tareas a máquinas, trabajadores a tareas y proyectos, personal de ventas a territorios de ventas, contratos a licitaciones, horarios de aulas disponibles a horarios de maestros disponibles, enfermos a camas disponibles del hospital, cierto número de empleados a cierta cantidad de puestos en una empresa, aviones a destinos aéreos, entre otros. Una característica importante de los problemas de asignación es que se asigna un trabajador, una tarea,..., a una sola máquina, proyecto,.... En particular se busca el conjunto de asignaciones que optimice el objetivo planteado, tal como minimizar costos, minimizar tiempo o maximizar utilidad. Destinos Orígene 1 2 s C11 C12 1 C21 C22 2 Se resuelve por el método húngaro. Método Húngaro. 1) Se debe balancear la tabla inicial en caso de no estarlo. Agregando filas o columnas de ceros. 2) Se selecciona el menor costo en cada fila (mc) y se obtiene la diferencia entre c/elemento de la fila y mc. Se obtiene una nueva matriz de costos 3) En la tabla obtenida en el paso anterior, se selecciona el menor costo en cada columna (mc) y se obtiene la diferencia entre c/elemento de la columna y mc. Se obtiene una nueva matriz de costos 4) Se intenta hacer la asignación: a cada origen se le asignan destinos, tomando las celdas donde el costo sea 0. Si al final cada origen tiene solo un destino y viceversa se obtiene el costo

5) Si no se cumple el paso anterior, se tachan las filas y columnas donde aparecen los 0, tratando de trazar la menor cantidad de líneas. 6) Se busca el menor costo (mc) entre los elementos no tachados 7) Se reescribe la tabla: a. Los elementos tachados mas no cruzados quedan igual b. A los elementos tachados y cruzados se les suma mc c. A los elementos no tachados se les resta mc. 8) Se repite el paso 3