preg

INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009

EJERCICIOS SOBRE DE ASIGNACIONES

Este será un ejercicio modelo para resolver los
demás ejercicios de Asignación:

Ejercicio Nº 1:
Una agencia de publicidad trata cual de entre 4 ejecutivos de
contabilidad debe asignarse a cada uno de los clientes mayores.
Use el método conveniente para encontrar la solución optima, a
continuación sepresentan los costos estimados de la asignación
de cada ejecutivo.
CONTABILIDA
D
1

2

3

4

A

1
5

1
9

2
0

1
8

B

1
4

1
5

1
7

1
4

C

1
1

1
5

1
5

1
4

D

2
1

2
4

2
6

2
4

SOLUCION:
Realizando operación renglón, primero buscamos el menor de la fila
correspondiente.
1

2

3

4

menor
es

A

1
5

1
92
0

1
8

15

B

1
4

1
5

1
7

1
4

14

Investigación Operativa I

1

INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
C

1
1

1
5

1
5

1
4

11

D

2
1

2
4

2
6

2
4

21

Como no se tienen los suficientes ceros pasamos a operación columna
1 2 3 4
A

0 4

5 3

B

0 1

3 0

C

0 4

4 3

D

0 3

5 3menor
es

1

3

Una vez hecho la operación queda:
1 2 3 4
A 0

3 2 3

B 0

0 0

0

C 0

3 1

3

D 0

2 2

3

Pero como no se encuentran los suficientes Ceros para cada fila se
procede a buscar el menor de toda la matriz que no estén tachados (en
nuestro caso con rojo). En este caso el menor es 1. Entonces restaremos
este valor a cada uno de los elementos no tachados ysumaremos este
mismo valor a los elementos que están en las intersecciones, los demás
se copian sin operación alguna.
1 2 3 4
A 0

2

B 1

0 0

0

C 0
Investigación Operativa I

2 1

2 0

2

2

INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009

D 0

1 1

2

Como tampoco obtenemos al menos un cero en las filas se vuelve a
realizar la operación anterior. Entoncesel menor de los elementos de la
matriz no tachada será nuevamente 1, entonces queda:
1 2 3 4
A 0

1 0

1

B 2

0 0

0

C 1

3 0

2

D 0

0 0

1

Aquí encontramos al menos un cero en todas las filas, entonces si
tenemos más de 1 Cero en una determinada fila se compara quien es el
menor y se toma este. Luego se tacha los ceros que podrían existir en
las filas ycolumnas correspondientes al número tomado.
Luego
comparamos con la matriz original y se toman los números en las que
están los ceros no tachados, luego sumamos y encontramos la solución
óptima.

(A, 1)=15

(B, 4)=14

(C, 3)=15

(D, 2)=24

15 + 14 + 15
∴

+ 24 = 68

Ejercicio Nº 2:
Un corredor de bienes raíces planea la venta de cuatro lotes de
terreno y ha recibido ofertasindividuales de cuatro clientes.
Debido a la cantidad de capital que se requiere, estas ofertas se
han hecho en el entendimiento de que ninguno de los cuatro
Investigación Operativa I

3

INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
clientes comprara más que un lote, las ofertas se muestran en el
cuadro siguiente, el corredor de bienes raíces quiere maximizar
su ingreso total a partir deesas ofertas. Resolver el problema
mediante el método húngaro. Establezca el valor de la función
objetivo.

1

2

3

4

W 1
6

1
5

2
5

1
9

X

1
9

1
7

2
4

1
5

Y

1
5

1
5

1
8

0

Z

1
9

0

1
5

1
7

SOLUCION:
Como este es un problema de maximización
pasaremos a convertirlo en minimización:
1 2

3
0

0

X

0 0

14

Y

4 2

7

1
9

Z

0 1
7

1
0

primero

4

W 3 2

entonces

2

Una vez hecho esto pasamos a trabajarlo como una minimización así
como el ejercicio Nº 1.
1 2
W 1 1
Investigación Operativa I

3 4
0 0

4

INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009

X

0 0

1 3

Y

2 0

5 1
7

Z

0 1
5

8 0

Como aquí se encuentra la...