ecuaciones diferenciales

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

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

1.

Formulaci´n del Problema deAsignaci´n
o
o
A modo de ejemplo, construyamos el modelo de programaci´n lineal para el siguiente problema.
o

Ejemplo 1 Una f´brica dispone de cuatro obreros para completar cuatro trabajos. Cada obrero s´lo
a
o
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

Trabajo1
14
2
7
2

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

Trabajo 4
7
5
9
10

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

1

(1.1)

Primer Semestre 2004

m´
ın

4
i=1Asignaci´n
o

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´n del obrero i al trabajo j. Las restricciones
o
de trabajos obligan a que todotrabajo deba ser asignado a un obrero. Las restricciones de obreros
imponen que s´lo puede ser asignado un trabajo a cada obrero.
o
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´n es un problemade transporte balano
ceado con oferta y demanda igual a 1.
Se puede demostrar que como las ofertas y demandas tienen valores num´ricos enteros, la soluci´n
e
o
´ptima debe corresponder a un conjunto de valores enteros. Como a la derecha de cada restricci´n
o
o
se tiene un 1, los unicos valores posibles para las variables son 1 y 0. Luego, podemos olvidarnos de
´
la condici´n de que lasvariables deben ser enteras y resolver el problema mediante un tableau de
o
transporte. Siguiendo ese camino, se obtiene el Cuadro 1.2.
Trabajo 1
14
Obrero 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

1

1

1

10

0

Demanda

1

5
1

7

Oferta

1
1

Cuadro1.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´n
o

M´todo H´ ngaro
e
u

2.1.

Descripci´n
o

En general, el m´todo Simplex para problemas de transporte es poco eficiente para resolver probe
lemasde asignaci´n, especialmente en problemas de gran tama˜o. Por ello, para resolver problemas
o
n
de asignaci´n (minimizaci´n) se emplea normalmente el M´todo H´ngaro. La principal ventaja es que
o
o
e
u
el m´todo h´ngaro es considerablemente m´s simple que el m´todo Simplex del problema de transporte.
e
u
a
e
Para aplicar el m´todo se deben seguir los siguientes pasos:
e
Paso 1...