Programación entera

INVESTIGACION OPERATIVA Programación Entera (Algoritmo de Asignación)
Segundo semestre 2006

Problema de Asignación
Está relacionado con el problema de Transporte. Cambios: Fuente (Origen)Objetivo (Destino) Oferta (Si) Demanda (Dj) Relación ( m : n ) Xij ∈ Variable Básica à Asignado (Recurso) à Asignación (Tarea) à 1 à 1 à 1 : 1 (Univoca) à Xij = 1

Xij ∈ Variable No Básica à Xij = 0Problema de Asignación
Un Problema de Asignación llevado a un PPL, se tiene que:

Min Z = ∑ ∑ cij x ij
i=1 j=1

m

n

Minimización del Costo de Asignación. Cada recurso asignado es uno solo.Cada tarea asignada es uno solo.

s.a.

∑ x ij = 1
i=1 n

m

j = 1,..., n i = 1,..., m

∑ x ij = 1
j=1

x ij = {0,1} ∀ i, j

Problema de Asignación
METODO HUNGARO. Paso 1.Localizaral menor elemento de costo unitario de la matriz de costos, por cada reglón y luego réstelo a todos los demás elementos del mismo reglón incluido el seleccionado. Seguidamente repita el mismoprocedimiento por cada columna una vez finalizada la resta de los reglones. Finalmente la matriz de costos tendrá como mínimo un cero por cada reglón y columna. Paso 2.Determine si existe una asignaciónfactible que involucre costos ceros en la nueva matriz, es decir, determine si la matriz nueva tiene “n” anotaciones ceros, sin que dos de ellas se encuentren dentro del mismo reglón o columna. Si existedicha asignación entonces esta es óptima. Si no existe continúe con el Paso 3.

Problema de Asignación
Paso 3.Cubrir todos los ceros de la nueva matriz con el menor número posible de líneashorizontales y verticales. Las líneas horizontales deben pasar por todo el reglón y las verticales por toda la columna. El número total de líneas debe ser menor que “n”. Luego localice el menor número que noesté cubierto por una línea en la nueva matriz y seguidamente réstelo a cada uno de los miembros que no está cubierto por una línea incluyéndose y súmelo a cada elemento que este cubierto por dos...