ESCUELA NACIONAL DE MARINA MERCANTE

“ALMIRANTE MIGUEL GRAU”

PROGRAMA DE ADMINISTRACIÓN MARÍTIMA Y PORTUARIA

PROGRAMACION LINEAL
MODELOS DE ASIGNACIÓN

INVESTIGACION OPERATIVA

Mg. Ing. César Peña Carrillo

 Modelo de Asignación
Situación:
Asignar m trabajos (o trabajadores) a n máquinas.

Un trabajo i (=1, 2, 3 ,...,m) cuando se asigna a la

máquina
j (=1,2,....,n) incurre en un costo cij.

El objetivo es asignar los trabajos a las máquinas uno a uno

al menor costo.

La formulación de este problema puede considerarse como

un caso especial del modelo de transporte.
 Descripción

Los trabajos representan las “fuentes” y las máquinas los

“destinos”
La oferta disponible en cada fuente es 1 como también lo
es la demanda en cada destino.

es el costo de transportar (asignar) el trabajo i a la

cij
máquina j
El costo puede representar también características
de competencia de cada trabajador
Descripción

En el caso que un trabajo no deba ser asignado

(porque no cumple con los requisitos) a una máquina
(actividad) en particular, este costo debe tener
un valor alto (M)

En el caso de existir desequilibrio, esto es, más

trabajos que máquinas o más máquinas que trabajos,
hay que equilibrar con máquinas o trabajos figurados
(ficticios), logrando de esta forma que m = n
 Expresión matemática del modelo

0, si el i-ésimo trabajo no se asigna a la j-ésima

Xij =
máquina 1, si el i-ésimo trabajo se asigna a la j-ésima
máquina
Máquina
1 2 ….. n
1 ….. 1
C11 C12 C1n
2 ….. 1
Trabajo ….. ….. …..
C21 C22 C2n
n ….. 1
….. …. ….
. ….. .
Cn1
Cn2 Cnn
1
Por lo tanto el modelo está dado por:

n n
minimizar z = c
i1 j
ij xij

n 1

sujeto a   i=1,2, ...,n

j 1
xij 1
n
j=1,2,..n
x 1 ij
i1

xij = 0 ó bien 1
Ejemplo:
La gerencia general de RPG (ejemplo de transporte) con sede
en Bruselas, este año, como parte de su auditoría anual, decidió
que cada uno de sus cuatro vicepresidentes visite e inspeccione
cada una de sus plantas de ensamblaje durante las primeras dos
semanas de junio. Las plantas están ubicadas en Leipzig
(Alemania), Nancy (Francia, Lieja (Bélgica) y Tilburgo
(Holanda).
Para decidir a que vicepresidente enviar a una planta
determinada, se asignaron puntos (costos) a cada uno de ellos
de acuerdo a su experiencia, habilidades lenguísticas, tiempo
que durará la inspección y otros. Estos datos se muestran en la
siguiente tabla:
Ejemplo

PLANTA
Leipzig (1) Nancy(2) Lieja (3) Tilburgo(4)
Finanzas (F) (1) 24 10 21 11
Mercadotecnia(M) (2) 14 22 10 15
Operaciones (O) (3) 15 17 20 19
Personal(P) (4) 11 19 14 13

Plantear el modelo de PL
Ejemplo: Modelo de PL
MIN Z = 24 X11 + 10 X12 + ... + 14 X43 + 13 X44

sujeto a:
a) Oferta X11 + X12 + X13 + X14 = 1
X21 + X22 + X23 + X24 = 1
X31 + X32 + X33 + X34 = 1
X41 + X42 + X43 + X44 = 1
b) Demanda
X11 + X21 + X31 + X41 = 1
X12 + X22 + X32 + X42 = 1
X13 + X23 + X33 + X43 = 1
X + X + X + X44 = 1
c) No negatividad14 X24ij >= 340 i=1,...,4,
j=1,....,4
Métodos de Solución
Existen varias formas de obtener la solución:
a) Listar todas las alternativas posibles con sus costos y
seleccionar la de menor costo (algoritmo exhaustivo)
b) Método Húngaro: método iterativo

a) Listar todas las alternativas:

¿Cuántas alternativas posibles existen?
- El primer trabajo se puede asignar de n formas formas posibles
- El segundo de n-1 formas
- El último sólo de 1 forma
En total existen n! formas de hacer la asignación completa
Método Húngaro:
Paso 0: Construir la matriz de asignación
Para obtener la solución óptima cada nueva
matriz de asignación debe satisfacer:
Propiedad 1: Todos los números son no negativos
Propiedad 2: Cada fila y cada columna tiene al menos una celda con
un valor cero
Paso 1:
a) Reducción de filas: Restar el costo menor de cada fila a la fila
correspondiente y/o
b) Reducción de columnas: Restar el costo menor de cada
columna a la columna correspondiente
Con esto se crea una nueva matriz con las propiedades 1 y 2
Método Húngaro:

Paso 2: Determinar si la matriz es reducida (Prueba de Optimalidad).

Trazar el menor número de líneas rectas sobre las filas y columnas
para cubrir todos los ceros.
Si el número de rectas es igual al número de filas o columnas se dice
que esta matriz es reducida.
Si la matriz no es reducida pasar al paso 3, sino pasar al paso 4
Método Húngaro:
Paso 3: Movimiento
De todas las celdas no cruzadas identifique una con el menor
valor y haga lo siguiente:
a) Restar el valor a cada celda no cruzada
b)Sumar el valor a cada celda de intersección de rectas
Volver al paso 2
Método Húngaro:

Paso 4: Solución óptima (Asignación)

Primero se asigna a las que tengan sólo una alternativa, se van
marcando y así sucesivamente
Determinar el costo: Se suman todos los
costos correspondientes a las asignaciones (o sumar todos los pi
y qj).

¿Qué valor se obtiene al sumar todos los valores que se restaron

en las reducciones de filas y columnas?
Ejemplo: Aplique el método Húngaro al ejemplo

Paso 0: Matriz de Asignación

1 2 3 4 pi
F 24 10 21 11
M 14 22 10 15
O 15 17 20 19
P 11 19 14 13
qj

Nota: En negrita los menores de cada fila

Paso 1: Reducción de filas y columnas

1 2 3 4 pi
F 14 0 11 1 10
M 4 12 0 5 10

Filas
O 0 2 5 4 15
P 0 8 3 2 11
qj 1

1 2 3 4 pi
F 14 0 11 0 10
M 4 12 0 4 10
O 0 2 5 3 15
P 0 8 3 1 11
qj 1

Columnas
Paso 2: Determinar si la matriz es reducida

1 2 3 4 pi
F 14 0 11 0 10
M 4 12 0 4 10
O 0 2 5 3 15
P 0 8 3 1 11
qj 1

No es reducida: sólo tres rectas (para ser reducida deben ser

4)

Ir al paso 3
Paso 3: Movimiento (Seleccionar el menor: restar a las
no tachadas, sumar a las intersecciones)

1 2 3 4 pi
F 14 0 11 0 10
M 4 12 0 4 10
O 0 2 5 3 15
P 0 8 3 1 11
qj 1

1 2 3 4 pi
F 15 0 12 0 10
M 4 11 0 3 10
O 0 1 5 2 15
P 0 7 3 0 11
qj 1+1

Volver al paso 2 !!
Iteración paso 2:

1 2 3 4 pi
F 15 0 12 0 10
M 4 11 0 3 10
O 0 1 5 2 15
P 0 7 3 0 11
qj 1+1

Se tachan todos los ceros con cuatro rectas, por tanto es óptima
Ir al paso 4 !!
Paso 4: Asignación
1 2 3 4 pi
F 15 0 12 0 10
M 4 11 0 3 10
O 0 1 5 2 15
P 0 7 3 0 11
qj 1+1

Costo = c12 + c23 + c31 +c44

= 10+10+15+13 = 48

Ver Asignación RPG

Modelo de Asignación: Otras consideraciones
El modelo de asignación de RPG es un modelo de minimización
en el cual el número de vicepresidentes es igual al número de
plantas, y todas las asignaciones posibles son aceptables.

Existen modelos tipo asignación donde no todas las condiciones

anteriores se cumplen. En particular se considerarán situaciones
en las que:
1 Hay una desigualdad entre el número de “personas” por
asignar y el número de “destinos” que requieren personas
asignadas.
2 Hay un modelo de maximización
3 Existen asignaciones inaceptables
CASO 1 – ENCONTRAR LA ASIGNACIÓN CORRECTA

EMPLEADO T1 T2 T3

E1 0 4 9

E2 0 2 12

E3 2 0 4
EMPLEADO T1 T2 T3

E1 0 4 9

E2 0 2 12

E3 2 0 4

EMPLEADO T1 T2 T3

E1 0 4 5

E2 0 2 8

E3 2 0 0
EMPLEADO T1 T2 T3

E1 0 4 5

E2 0 2 8

E3 2 0 0

EMPLEADO T1 T2 T3

E1 0 2 3

E2 0 0 6

E3 4 0 0
EMPLEADO T1 T2 T3

E1 0 2 3

E2 0 0 6

E3 4 0 0

E1 -- T1 = 11
E2 -- T2 = 15
E3 -- T3 = 22
____
48
EJEMPLO 2: MINIMIZACION MATRIZ DESBALANCEADA

10 8 9 0
Una empresa evalúa a 4 postulantes para trabajar en
7 5 14 0
3 maquinas de producción, obteniéndose el costo de Matriz de
producción, según el resultado de la tabla. Se desea 11 6 4 0
costos
saber a que postulante no se va contratar porque 9 7 12 0
genera mayor costo y cual seria la distribución
optima.

POSTULANTES/MAQUINAS M1 M2 M3
P1 10 8 9
P2 7 5 14 10 8 9 0
P3 11 6 4 Paso 1: Reste el 7 5 14 0
P4 9 7 12
número más 11 6 4 0
9 7 12 0
pequeño de cada
Balanceo de matriz renglón a cada
número del renglón. 10 8 9 0
POSTULANTES/MAQUINAS M1 M2 M3 MF 7 5 14 0
P1 10 8 9 0
Esto se llama 11 6 4 0
P2 7 5 14 0 reducción de 9 7 12 0
P3 11 6 4 0 renglón.
P4 9 7 12 0
 10 8 9 0
7 5 14 0
11 6 4 0
9 7 12 0

3 3 5 0
0 0 10 0
4 1 0 0
2 2 8 0
1 1 3 0
0 0 10 2
4 1 0 2
0 0 6 0

Matriz de costos
reducidos

3 3 5 0
Paso 3: Pruebe si se 0 0 10 0
puede hacer una 4 1 0 0
asignación óptima. Se 2 2 8 0

hace mediante la
determinación del
número mínimo de Como el número de líneas es
líneas necesarias igual al número de renglones
para cubrir todos los se tiene una solución óptima.
ceros. Se puede pasar al último
paso.
Paso 5: Se hacen las asignaciones una a una en Solución
las posiciones que tienen elemento cero. optima
Comience con los renglones y columnas que
tienen solo un cero. Cada renglón y columna POSTULANTES/MAQUINAS M1 M2 M3
necesita recibir exactamente una asignación. P1 10 8 9
Después continúe con los renglones y columnas P2 7 5 14
P3 11 6 4
que no han sido asignados. Siga hasta que todos P4 9 7 12
los renglones y columnas estén asignados.

POSTULANTES/MAQUINAS M1 M2 M3 MF
P1 1 1 3 0
P2 0 0 10 2
P3 4 1 0 2
P4 0 0 6 0
P1 MF 0 P1 MF 0
P2 M1 7 P2 M2 5
P3 M3 4 P3 M3 4
Distribución P4 M2 7 P4 M1 9

optima RESPUESTA 18 RESPUESTA 18

1 2

P1 MF P1 MF No se contrata al postulante 1
P2 M1 P2 M2
P3 M3 P3 M3
P4 M2 P4 M1
 EJEMPLO 3: MAXIMIZACION

3 9 4 4
Una empresa desea exportar cuatro productos a Matriz de 6
6
3
4
1
0
9
8
cuatro países diferentes, determinándose los costos 9 6 8 9
beneficios de cada uno de ellos de acuerdo al
resultado de la tabla (miles de dólares). Se desea
saber con qué combinación se maximiza los Luego de todos los pasos de minimización
beneficios. FRANCIA ALEMANIA CHINA NORUEGA
ARANDANOS 0 8 5 0 FRANCIA
CHOMPAS DE ALPACA 1 0 0 3 ALEMANIA
FRANCIA ALEMANIA CHINA NORUEGA CAMARON 2 2 0 3 CHINA
ARANDANOS 13 7 12 12 TRUCHA 1 0 4 0 NORUEGA
CHOMPAS DE ALPACA 10 13 15 7
CAMARON 10 12 16 8 Distribución
TRUCHA 7 10 8 7
optima
Respuesta:
Paso previo: convertir a minimización ARANDANOS 13 FRANCIA
CHOMPAS DE ALPACA 13 ALEMANIA
CAMARON 16 CHINA
Se escoge el mayor valor de la matriz y se resta TRUCHA 7 NORUEGA
ese número a todos los valores de la tabla. Solución
MAXIMIZACION 49 optima
CASO PRACTICO 1

• El [Link]. “Angamos” tiene un compromiso operacional con la armada de Estados

Unidos, por lo que debe hacer mantenimiento correctivo a 3 de sus 4 maquinas
principales dentro de 21 días, solicitando el trabajo al Servicio Industrial de la
Marina (SIMA).
• Ante el corto tiempo que dispone la unidad submarina antes de zarpar, SIMA
debe asignar 3 grupos de mantenimiento con el fin de que a cada maquina se le
efectúe el mantenimiento requerido. Sin embargo entre cada grupo de
mantenimiento existe diferencia de experiencia variando los costo de trabajo por
jornada.

Maquina 1 Maquina 2 Maquina 3

Grupo de S/. 100 S/. 200 S/. 150
mantenimiento 1
Grupo de S/. 300 S/. 150 S/. 200
mantenimiento 2
Grupo de
mantenimiento 3 S/. 90 S/. 120 S/. 100
 CASO PRACTICO 2

DESCRIPCIÓN DEL PROBLEMA

La empresa SAAM TOWAGE desea realizar maniobra de posicionamiento de
buques empleando remolcadores.

Obtener la asignación de remolcadores a los diferentes buques de tal

manera que se minimicen los costos.

METODO DE ASIGNACIÓN:
El objetivo es asignar los trabajos de remolcadores uno a uno al menor
costo, Permitiendo optimizar los beneficios de la empresa.
 DATOS (TIPOS Y CAPACIDADES)
BUQUE BUQUE BUQUE
CONSUMO DE COMBUSTIBLE
TRB < 40000 TRB < 60000 CONTEINER
Remolcador ALBATROS 50 55 60
Remolcador VALKYRIA 47 50 53
Remolcador TAURA 45 48 51
COSTO COMBUSTIBLE ($4.5 X BUQUE BUQUE BUQUE
GLN) TRB < 40000 TRB < 60000 CONTAINERO
Remolcador ALBATROS 225 248 270
Remolcador VALKYRIA 212 225 239
Remolcador TAURA 203 216 230

SUELDO TRIPULACIÓN X HORA

($) 17 $
COSTO TOTAL $ BUQUE BUQUE BUQUE
(COMBUSTIBLE + SUELDO ) TRB < 40000 TRB < 60000 CONTAINERO
Remolcador ALBATROS 242 264 287
Remolcador VALKYRIA 228 242 255
Remolcador TAURA 219 233 246

MANIOBRA REMOLCADOR 1 hora

 FIN
GRACIAS