Planteamiento del modelo de programación lineal

Ejemplo

Machineco tiene cuatro maquinas y cuatro tareas por completar. Cada maquina se debe asignar para completar una tarea. El tiempo requerido para preparar cada maquina para completar cada tarea se muestra en la siguiente tabla. Machineco desea reducir el tiempo de preparación total necesario para completar las cuatro tareas.

Planteamiento del modelo de programación lineal

Machineco debe determinar qué máquina debe asignarse a cada tarea. Xij=1 si la máquina i se asigna para satisfacer las demandas de la tarea j Xij=0 si la máquina i no se asigna para satisfacer las demandas de la tarea j

Modelo de Programación Lineal

Entonces el modelo de P.L. de Machineco es el siguiente:

Las restricciones de maquina aseguran que cada maquina se asignó a una tarea, y las restricciones de trabajo aseguran que se completó cada tarea. Si Xij = 1 entonces la función objetivo tomará el tiempo requerido para preparar la maquina i para la tarea j, si Xij =0 entonces la función objetivo no tomara el tiempo requerido.

Se puede notar que Machineco enfrenta un problema de transporte equilibrado en el que cada punto de suministro tiene un suministro de 1 y cada punto de demanda tiene una demanda de 1. En general el problema de asignación es un problema de transporte equilibrado en el que suministros y demandas son iguales a 1, Así, un problema de asignación se caracteriza porque se conoce el costo de asignar cada punto de suministro a cada punto de demanda.

Matriz de costos

Solución por el Método Húngaro

Paso 1: Reste el numero más pequeño de cada renglón a cada número del renglón. Esto se llama reducción de renglón.

Paso 2: Reste el número mas pequeño de la nueva matriz a cada número de la columna. Esto se llama reducción de columna.

Al momento de realizar los dos pasos anteriores la matriz nueva recibe el nombre de matriz reducida de costos.

Paso 3: Pruebe si se puede hacer una asignación óptima, se hace mediante la determinación del número mínimo de líneas necesarias para cubrir todos los ceros.

Como el número de líneas no es igual al número de renglones no es posible hacer una asignación, en este caso se continúa con el método.

Paso 4: Reste el número no cubierto más pequeño de todos los números no cubiertos de la matriz. Sume el número no cubierto más pequeño a los números que se encuentren en intersección de líneas. Los números cruzados pero que no se encuentran en intersección de líneas permanece igual.

Paso 5: Repetir los pasos 3 y 4 hasta que el número de líneas sea igual al número de renglones de la matriz.

Como el número de líneas es igual al número de renglones se tiene una solución óptima. Se puede pasar al último paso.

Paso 6: Se hacen las asignaciones una a una en las posiciones que tienen elemento cero. Comience con los renglones y columnas que tienen sólo un cero. Cada renglón y columna necesita recibir exactamente una asignación, después continúe con los renglones y columnas que no han sido asignados. Continúe hasta que todos los renglones y columnas estén asignados.

Interpretación de resultados

'z = 2 + 5 + 3 + 5 = 17'

Ejemplo

Doc Concillman reúne a un equipo de relevos para el relevo de 400 metros.Cada nadador debe nadar 100 metros de brazada de pecho, dorso, mariposa o estilo libre. Doc cree que cada nadador obtendrá los tiempos en segundos dados en la tabla. ¿Qué nadador debe nadar que estilo?

Nadador Libre Pecho Mariposa Dorso

Gary 54 54 51 53

Mark 51 57 52 52

Jim 50 53 54 56

Chet 56 54 55 53

Modelo de Programación Lineal

Min z= 54x11 + 54x12 + 51x13 + 53x14 + 51x21 + 57x22 + 52x23 + 52x24 + 50x31 + 53x32 + 54x33 + 56x34 + 56x41 + 54x42 + 55x43 + 53x44

S.A

x11 + x12 + x13 + x14 = 1

x21 + x22 + x23 + x24 = 1

x31 + x32 + x33 + x34 = 1

x41 + x42 + x43 + x44 = 1

x11 + x21 + x31 + x41 = 1

x12 + x22 + x32 + x42 = 1

x13 + x23 + x33 + x43 = 1

x14 + x24 + x34 + x44 = 1

xij = {0,1} i,j = Z

Tabla de Transporte

1 2 3 4

1 54 54 51 53 1

2 51 57 52 52 1

3 50 53 54 56 1

4 56 54 55 53 1

1 1 1 1 1

Solución por el Método Húngaro

1. Se escribe la matriz de costos.

2. Se escoge el número mas pequeño de cada renglón y se le resta a cada numero del renglón y los resultados se pone en una nueva matriz. Queda de la siguiente manera:

3. De la nueva

...