Problema de Asignacion

PROBLEMA DE ASIGNACIN

Materia:

Investigacin de Operaciones IElaborado por:

Castillo Martnez Janeth Ivonne

UNIVERSIDAD DE SONORAUnidad Regional Sur

DIVISIN DE CIENCIAS E INGENIERA.Departamento de Fsica, Matemticas e Ingeniera

Navojoa, Sonora a 11 de Mayo de 2015

Problema de asignacinEl problema de asignacin es un tipo especialde problema de programacin lineal en elque los asignados son recursos que sedestinan a la realizacin de tareas. Porejemplo, los asignados pueden ser personas aquienes se tiene que dar trabajo.

Sin embargo, los asignados no siempre tienenque ser personas. Tambin pueden sermquinas, vehculos o plantas, o inclusoperiodos a los que se asignan tareas.

Personas Trabajo

Para que un problema se ajuste a la definicin de un problema de asignacin, esnecesario que este cumpla los siguientes supuestos:

1. El nmero de asignados es igual al nmero de tareas. (Este nmero se denotapor n.)

2. A cada asignado se le asigna slo una tarea.3. Cada tarea debe realizarla slo un asignado.4. Existe un costo cij asociado con el asignado i (i = 1, 2, . . . , n) que realiza la

tarea j ( j = 1, 2, . . . , n).5. El objetivo es determinar cmo deben hacerse las n asignaciones para

minimizar los costos totales.

Nota: Los primeros tres supuestos son bastante restrictivos. Muchas aplicaciones potenciales no lassatisfacen por completo. Con frecuencia es posible reformular el problema para hacerlo que se ajuste.Por ejemplo, muchas veces se pueden usar asignados ficticios o tareas ficticias con este fin.

Modelo del problema de asignacinEl modelo matemtico para manejar el problema de asignacin utiliza las siguientesvariables de decisin:

= 10para i = 1, 2, . . . , n y j = 1, 2, . . . , n.

Si Z es el costo total, el modelo del problema de asignacin es

==1

1

si se asigna i para realizar la tarea j,si no es as,

Modelo del problema de asignacin

Sujeto a

=1

= 1 =1

= 1 0

para i = 1, 2, . . . , n para j = 1, 2, . . . , n

para toda i y j

Tabla de la representacin general del modelo de asignacin

Para resolver un problemade asignacin se utiliza:

El mtodo Hngaro.

Ejemplo. Problema de asignacinLa compaa de manufactura "Jimnez y Asociados" desea realizar una jornada demantenimiento preventivo a sus tres mquinas principales A, B y C. El tiempo que demandarealizar el mantenimiento de cada mquina es de 1 da, sin embargo la jornada demantenimiento no puede durar ms de un da, teniendo en cuenta que la compaa cuentacon tres proveedores de servicios de mantenimiento debe de asignarse un equipo demantenimiento a cada mquina para poder cumplir con la realizacin del mantenimientopreventivo. Teniendo en cuenta que segn el grado de especializacin de cada equipoprestador de servicios de mantenimiento el costo de la tarea vara para cada mquina enparticular, debe de asignarse el equipo correcto a la mquina indicada con el objetivo deminimizar el costo total de la jornada. Los costos por mantenimientos ($) asociados se puedenobservar en la siguiente tabla:

Mquina 1 Mquina 2 Mquina 3

Equipo de mantenimiento 1 10 9 5



Paso 1. Reste el nmero ms pequeo (el menor costo Ci j = Ui ), de cada rengln acada nmero del rengln.

ji Mquina 1 Mquina 2 Mquina 3 Ui

Equipo de mantenimiento 1 10 9 5 U1=5



ji Mquina 1 Mquina 2 Mquina 3




Paso 2. Reste el nmero ms pequeo (el menor costo Ci j = Vij ), de cada columna acada nmero del columna.





Vj V1=2 V2=0 V3=0





Paso 3. Pruebe si se puede hacer una asignacin ptima. Hgalo mediante la determinacindel nmero mnimo de lneas necesario para cubrir (es decir, cruzar) todos los ceros. Se tienela solucin ptima cuando el mnimo necesario de renglones y columnas sombreadas paracubrir los ceros es n. En este problema el mnimo es n =3.





Paso 4. Si el nmero de lneas es menor que el nmero de renglones, modifique la tabla de lasiguiente forma:a) Reste el nmero no cubierto ms pequeo de todos los nmeros no cubiertos de la tabla.b) Sume el nmero no cubierto ms pequeo a los nmeros que se encuentran en lasinterseccionesde las lneas.c) Los nmeros cruzados pero que no se encuentran en las intersecciones de las lneaspermanecen sin cambio en la siguiente tabla.





Menor elemento de los no cubiertos 3





Paso 5. Repita los pasos 3 y 4 hasta que sea posible tener un conjunto deasignaciones ptimo.





Paso 6. Haga las asignaciones una a una en las posiciones que tienen elementoscero. Comience con los renglones y columnas que tienen slo un cero.





Por ende la asignacin que representa el menor costo para la jornada demantenimiento preventivo determina que:

El Equipo 1 realice el mantenimiento de la Mquina 1 El Equipo 2 realice el mantenimiento de la Mquina 3 El Equipo 3 realice el mantenimiento de la Mquina 2

Por lo tanto, la jornada tendr un costo total de $17.

Costos ($)1043

PROBLEMA DE ASIGNACINNmero de diapositiva 2Nmero de diapositiva 3Nmero de diapositiva 4Nmero de diapositiva 5Nmero de diapositiva 6Nmero de diapositiva 7Nmero de diapositiva 8Nmero de diapositiva 9Nmero de diapositiva 10Nmero de diapositiva 11Nmero de diapositiva 12

Documents

Problema de Asignacion