sábado, 19 de abril de 2008
Asiognación
El problema de asignación tiene que ver con la asignación de tareas a empleados, de territorios a vendedores, de contratos a postores o de trabajos a plantas. Al aplicar el método de transporte y el método de asignación la gerencia está buscando una ruta de distribución o una asignación que optimizará algún objetivo; éste puede se la minimización del costo total, la maximización de las utilidades o la minimización del tiempo total involucrado.
Al igual que el método de transporte el método de asignación es computacionalmente más eficiente que el método simplex para una clase especial de problemas. El método de asignación también conocido como la Técnica de flood o el método Húngaro de asignación. Hay básicamente tres pasos en este método
Determine la tabla de costo de oportunidad:
Reste el elemento del costo más bajo en cada columna de la tabla de costo dada, de todo los elementos en esa columna.
Reste el asiento más bajo en cada renglón de la tabla obtenida en la parte 1.1 de todos los números en ese renglón.
Determine si se puede hacer una asignación óptima: El procedimiento es dibujar líneas rectas (verticales y horizontales) a través de la tabla de costos total de oportunidad, de tal manera que se minimice el número de líneas necesarias para cubrir todos los cuadros CERO. Si el número de líneas dibujadas es menor que el número de renglones o columnas, no se puede hacer una asignación óptimas y el problema no está resuelto.
Revise la tabla de costo total de oportunidad.
Seleccione el número más pequeño en la tabla no cubierto, por una línea recta y reste este número de todos los números no cubiertos por una línea recta.
Añada este mismo número a los números que están en la intersección de dos líneas cualesquiera. Regrese al paso 2 .
Método Dual
1. Si el primal se refiere a maximizar el problema dual será minimizar.
2. Los coeficientes de la función objetivo del primal serán los coeficientes del vector de disponibilidad de recursos en el dual.
3. Así los coeficientes del vector disponibilidad de recursos del problema primal serán los coeficientes de la función objetivo (vector costos, precios, utilidad) en el problema dual.
4. Los coeficientes de las restricciones en el primal (transpuesta de la matriz) será la matriz de coeficientes en el dual.
5. Los signos de desigualdad del problema dual son controlables a los del problema primal
6. Las variables ¨x¨ del primal se convierten en nuevas variables ¨Y¨ en el dual.
Considerando el siguiente problema primal, calcular su modelo dual.
Sea maximizar
Z = 3x + 5y
El resultado como consecuencia de un sistema primal a un sistema dual queda de la siguiente forma:
Método de Transporte
Método de la gran "M"
a) El método de la gran ¨M¨
b) El método de las dos fases
Método de la gran M (Penalización)
Consiste en modificar el problema original para dar lugar a un nuevo problema, agregando una variable ¨W ¨ llamada artificial y que se penalizara mediante un costo ¨M¨ de valores grandes y positivos que en forma arbitraria, permite que la función objetivo forme valores muy grandes también cuando sea minimización llegara el momento en que ¨W¨ = O y esto indica haber regresado al problema original, pero si se llega W > 0 entonces el problema no tiene solución.
≥ Variable artificial = -R1
≤ Variable artificial = +R2
Minimice
Z = 4x1 + x2
Sujeta a 3x1 + x2 = 3
4x1 + 3x2 ≥ 6
X1 + 2x2 ≤ 4
X1, x2 ≥ 0 3x1 + x2 = 3 → 3x1 + x2 = 3
4x1 + 3x2 ≥ 6 → 4x1 + 3x2 + -x3 = 6
X1 + 2x2 ≤ 4 → x1 + 2x2 + x4 = 4
X1, x2 ≥ 0 → x1, x2, x3, x4 ≥ 0 condición de no negatividad
Minimice z= 4x1 + x2 + Mr1 + Mr2
3x1 + x2 + R1 = 3
4x1 + 3x2 –x3 + R2 = 6
X1 + 2x2 +x4 = 4
X1, x2, x3, x4, R1, R2 ≥ 0
Z = -4x – x2 – Mr1 – Mr2 = 0