sábado, 19 de abril de 2008



Para cada renglón o columna en el que quede alguna oferta o alguna demanda, se calcula su penalización, que es la diferencia no negativa entre los 2 costos más pequeños de transporte Cij asociados con las variables no asignadas en ese renglón o en esa columna. Se considera el renglón o la columna para la mayor diferencia (en caso de empate se selecciona uno arbitrariamente). En este renglón o columna se localiza la variable no asignada (celdilla) que tenga el costo unitario más pequeño de transporte y se le asignan tantas unidades como sea posible sin ir en contra de las restricciones; se calculan las nuevas diferencias y se repite el procedimiento anterior hasta satisfacer todas las demandas.


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

Para cualquier problema de Programación Lineal (primal), debe tener su metodología (dual); el problema primal puede tener más restricciones que variables, esto significa la solución dual y debe resolverse con nuevas restricciones.
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

Es una forma del Método Simplex y de Programación Lineal para resolver situaciones de Origen-Destino basandose en dos tipos de Método:

  • Esquina Noroeste
  • Vogel


La oferta y demanda deben estar equilibradas.
Debe haber linealidad.
n= filas
m= columnas
n+m-1=No. de asignaciones





























































































































Método de la gran "M"




Existen problemas de Programación Lineal para el caso de minimización donde el método simplex ya conocido no es funcional debido a que los valores de una o más variables básicas son negativas y eso significa que se está violando el principio de no negatividad en las restricciones para ello el problema se podrá resolver por otros métodos que son:

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