Asignacion_y_Vendedor_Viajero

Fundamentos de Investigaci´on de Operaciones
Asignaci´on y Vendedor Viajero
23 de mayo de 2004

Si bien la resoluci´
on del problema de transporte mediante tableau parece ser muy expedita, existen
ciertos tipos de problemas de transporte, para los cuales el m´etodo no es eficiente. Estos problemas
son los llamados Problemas de Asignaci´
on.

1.

Formulaci´
on del Problema de Asignaci´
on
A modode ejemplo, construyamos el modelo de programaci´on lineal para el siguiente problema.

Ejemplo 1 Una f´
abrica dispone de cuatro obreros para completar cuatro trabajos. Cada obrero s´
olo
puede hacer uno de los trabajos. El tiempo que requiere cada obrero para completar cada trabajo se
entrega en el Cuadro 1.1.

Obrero
Obrero
Obrero
Obrero

1
2
3
4

Trabajo 1
14
2
7
2

Tiempo (Horas)
Trabajo 2Trabajo 3
5
8
12
6
8
3
4
6

Trabajo 4
7
5
9
10

Cuadro 1.1: Tiempos requeridos por obreros
La f´
abrica desea minimizar el tiempo total dedicado a los cuatro trabajos. Formule y resuelva un
modelo que determine la mejor asignaci´
on de los obreros.
En primer lugar debemos definir las variables de decisi´on necesarias para representar las posibles
alternativas de asignaci´on. Evidentemente, de acuerdoa la naturaleza del problema conviene emplear
variables binarias. Sea:
xij = asignaci´on de obrero i a trabajo j
La variable binaria xij valdr´a 1 si se asigna al obrero i al trabajo j y 0 en caso contrario.
Por lo tanto, la formulaci´on del problema queda:

1

(1.1)

Primer Semestre 2004

m´ın

4
i=1

Asignaci´
on

n
j=1 cij xij

s.t.
j=4
j=1 xij
i=4
i=1 xij

xij

=
1
=
1
= {0, 1}

(i = 1 . . .4)
(j = 1 . . . 4)
(i = 1 . . . 4; j = 1 . . . 4)

(Restricciones de obreros)
(Restricciones de trabajos)
(Variables binarias)

(1.2)

Donde cij representa el costo (tiempo) de la asignaci´on del obrero i al trabajo j. Las restricciones
de trabajos obligan a que todo trabajo deba ser asignado a un obrero. Las restricciones de obreros
imponen que s´olo puede ser asignado un trabajo a cada obrero.Olvidando la naturaleza de las variables, podemos decir que el problema anterior es un problema
de transporte balanceado donde cada punto de oferta entrega una unidad y cada punto de demanda
requiere una unidad. En general, un problema de asignaci´
on es un problema de transporte balanceado con oferta y demanda igual a 1.
Se puede demostrar que como las ofertas y demandas tienen valores num´ericosenteros, la soluci´on
´optima debe corresponder a un conjunto de valores enteros. Como a la derecha de cada restricci´on
se tiene un 1, los u
´nicos valores posibles para las variables son 1 y 0. Luego, podemos olvidarnos de
la condici´on de que las variables deben ser enteras y resolver el problema mediante un tableau de
transporte. Siguiendo ese camino, se obtiene el Cuadro 1.2.
Trabajo 1
14Obrero 1

Trabajo 2
5
1

2

Trabajo 3
8

12

Trabajo 4
7
0

6

Obrero 2
8

3

Obrero 3

1
9

1
2

4

1
6

Obrero 4

1

0

0

Demanda

1

1

1

1

5
1

7

Oferta

10
1
1

Cuadro 1.2: Tableau de Transporte para el Ejemplo 1
Por lo tanto, se asigna el obrero 1 al trabajo 2, el 2 al 4, el 3 al 3 y el 4 al 1, incurriendo en un
tiempo total de 5 + 5 + 3 + 2 = 15 horas.

2

Primer Semestre 2004

2.Asignaci´
on

M´
etodo H´
ungaro

2.1.

Descripci´
on

En general, el m´etodo Simplex para problemas de transporte es poco eficiente para resolver problemas de asignaci´on, especialmente en problemas de gran tama˜
no. Por ello, para resolver problemas
de asignaci´on (minimizaci´on) se emplea normalmente el M´etodo H´
ungaro. La principal ventaja es que
el m´etodo h´
ungaro es considerablemente m´assimple que el m´etodo Simplex del problema de transporte.
Para aplicar el m´etodo se deben seguir los siguientes pasos:
Paso 1 Determine el menor elemento en cada fila de la matriz de costos (m × m). Construya una
nueva matriz restando a cada costo el costo menor de esa fila. A continuaci´
on determine el costo
m´ınimo en cada columna de la matriz resultante. Construya una nueva matriz (matriz de...