Upload
joinergac
View
5.991
Download
36
Embed Size (px)
Citation preview
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 se presentan los costos estimados de la asignación de cada ejecutivo.
CONTABILIDAD
1 2 3 4
A 15
19
20
18
B 14
15
17
14
C 11
15
15
14
D 21
24
26
24
SOLUCION:
Realizando operación renglón, primero buscamos el menor de la fila correspondiente.
1 2 3 4 menores
A 15
19
20
18
15
B 14
15
17
14
14
Investigación Operativa I 1
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
C 11
15
15
14
11
D 21
24
26
24
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 3
menores
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 y sumaremos 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 1 2
B 1 0 0 0
C 0 2 0 2
Investigación Operativa I 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. Entonces el 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 y columnas 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 ofertas individuales 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 de esas ofertas. Resolver el problema mediante el método húngaro. Establezca el valor de la función objetivo.
1 2 3 4
W 16
15
25
19
X 19
17
24
15
Y 15
15
18
0
Z 19
0 15
17
SOLUCION:
Como este es un problema de maximización entonces primero pasaremos a convertirlo en minimización:
1 2 3 4
W 3 2 0 0
X 0 0 1 4
Y 4 2 7 19
Z 0 17
10
2
Una vez hecho esto pasamos a trabajarlo como una minimización así como el ejercicio Nº 1.
1 2 3 4
W 1 1 0 0
Investigación Operativa I 4
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
X 0 0 1 3
Y 2 0 5 17
Z 0 15
8 0
Como aquí se encuentra la solución, entonces el resultado es:
19 + 24 + 15 + 19 =77
Ejercicio Nº 3 :
Asignar maximizando el siguiente Problema.
a b c d e
A 2 3 5 7 8
B 3 2 6 5 4
C 1 4 4 5 2
D 6 7 3 8 4
E 4 4 5 2 1
Al igual que el ejercicio Nº 2 lo pasamos a minimización con operación columna
a b c d e
A 4 4 1 1 0
B 3 5 0 3 4
C 5 3 2 3 6
D 0 0 3 0 4
E 2 3 1 6 7
Ahora como una minimización primero operación fila:
Investigación Operativa I 5
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
a b c d e
A 3 3 0 0 0
B 0 2 0 0 1
C 3 1 0 1 4
D 0 0 0 0 1
E 1 2 0 5 6
Ahora operación columna
a b c d e
A 2 2 0 0 0
B 0 1 0 0 0
C 2 0 0 0 3
D 0 0 0 0 0
E 0 1 0 4 5
Como aquí se encuentra la solución entonces se compara con la matriz original, Por lo tanto el resultado será:
8 + 6 + 5 + 7 + 4 = 30
Ejercicio Nº 4 :
Una compañía que vende carros tiene disponible un FORD, un OPEL, un RAMBLER y un CHEVROLET, cuatro oficinas de la compañía lo solicitan. Se ha decidido enviar solo un automóvil a cada oficina de manera que el costo total sea mínimo. La matriz de costos se muestra a continuación.
1 2 3 4
FORD 10
5 3 8
OPEL 4 3 7 5
RAMBLER 13
10
12
14
Investigación Operativa I 6
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
CHEVROLET
7 8 4 6
Al igual que el ejercicio anterior: primero operación fila:
1 2 3 4
FORD 7 2 0 5
OPEL 1 0 4 2
RAMBLER 3 0 2 4
CHEVROLET
3 4 0 2
Ahora operación columna:1 2 3 4
FORD 6 2 0 3
OPEL 0 0 4 0
RAMBLER 2 0 2 2
CHEVROLET
2 4 0 0
Pero aquí no se encuentra la solución entonces se opera como el ejercicio Nº 1
1 2 3 4
FORD 4 0 0 3
OPEL 0 0 6 2
RAMBLER 2 0 4 4
CHEVROLET
0 2 0 0
Pero tampoco aquí no se encuentra la solución entonces se ejecuta el paso anterior nuevamente
1 2 3 4
FORD 2 0 0 1
OPEL 0 2 8 2
RAMBLER 0 0 4 2
CHEVROL 0 4 2 0
Investigación Operativa I 7
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
ET
Como aquí se encuentra la solución entonces el resultado es:3 + 4 + 10 + 6 =23
EJERCICIOS SOBRE DE TRANSPORTES
Este será un ejercicio modelo para resolver los demás ejercicios de método de Transportes:
EJERCICIO Nº 1________________________________________________________________________________
Una empresa manufacturera ubicada en la ciudad de lima, tiene 3 fábricas, actualmente los productos fabricados se embarcan a 3 bodegas diferentes, la localización y capacidades de las bodegas son:
Trujillo : 1200 unidades
Ica : 800 unidades
Huancayo : 1000 unidades
La capacidad de cada fábrica y la tarifa unitaria de flete de cada fábrica a cada bodega son:
FABRICA CAPACIDAD FLETE A $ UNIDAD
1 600 Trujillo 5
Ica 6
Hyo. 8
2 1000 Trujillo 4
Investigación Operativa I 8
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
Ica. 7
Hyo. 7
3 1400 Trujillo 6
Ica. 8
Hyo. 6
Determinar que fabrica debe embarcar y en qué cantidades a las tres bodegas a fin de reducir al mínimo los costos de flete.
SOLUCION AL PROBLEMA POR METODO VOGEL
Trujillo Ica Hyo. Oferta Mayor
Diferencia
Fabrica 15 6 8 600 1
Fabrica 24 7 7
1000
3
Fabrica 36 8 6
1400
2
Demanda
1200
800
1000
Mayor Diferencia
1 1 1
Se toma en nº con mayor diferencia para saturar la fila o columna, en este caso es 3, entonces queda saturada esa fila 2, ahora se busca nuevamente la nueva mayor diferencia.
Investigación Operativa I 9
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
Trujillo Ica Hyo. Oferta Mayor
Diferencia
Fabrica 1
5 6 8 600 1
600
Fabrica 2
4 7 71000
1000
Fabrica 36 8 6
1400
2
Demanda
1200
800
1000
200200
Mayor Diferencia
1 2 2
En esta ocasión tenemos números iguales entonces se toma cualquiera. Con lo que se satisface la fila 1.
Trujillo Ica Hyo. Oferta Mayor
Diferencia
Fabrica 1 5 6 8 600
60
Investigación Operativa I 10
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
0
Fabrica 2
4 7 71000
1000
Fabrica 36 8 6
1400
2
Demanda
1200
800
1000
200200
Mayor Diferencia
1 2 2
Se hace lo mismo que lo anterior.
Trujillo Ica Hyo. Oferta Mayor
Diferencia
Fabrica 1
5 6 8 600
600
Fabrica 2
4 7 71000
1000
Fabrica 3
6 8 61400
2
1000
400
Demanda
1200
800
1000
200200
Mayor
Investigación Operativa I 11
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
Diferencia
Se hace lo mismo.
Trujillo Ica Hyo. Oferta Mayor
Diferencia
Fabrica 1
5 6 8 600
600
Fabrica 2
4 7 71000
1000
Fabrica 3
6 8 61400
2
200200
1000
400
Demanda
1200
800
1000
200200
Mayor Diferenci
a
Con lo que toda la matriz queda saturada quedando los resultados así:
Trujillo Ica Hyo. Oferta Mayor
Diferencia
Fabrica 1
5 6 8 600
60
Investigación Operativa I 12
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
0
Fabrica 2
4 7 71000
1000
Fabrica 3
6 8 61400
200200
1000
400
Demanda
1200
800
1000
200200
Mayor Diferenci
a
Por lo tanto el resultado será:
600(6) + 100(400) + 200(6) + 200(8) + 1000(6) =16400
EJERCICIO Nº 2________________________________________________________________________________
Una fabrica dispone de tres centros de distribución A, B, C cuyas disponibilidades de materia prima son 100 120 y 120 tn respectivamente, dicha materia prima debe ser entregada a cinco almacenes I, II, III, IV y V los cuales deben recibir respectivamente 40, 50, 70, 90, y 90 tn , determinar una solución inicial factible por el método de la esquina noroeste , luego hallarla solución óptima por cualquier método.
I II III IV VOfert
a
A 1 2 5 9 1 100
Investigación Operativa I 13
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
0 0 0
B 210
830
5 120
C 120
710
4 120
Demanda
40
50
70
90
90
SOLUCION AL PROBLEMA POR METODO DE NOROESTE
I II III IV V Oferta
A
10
20
5 910
100
40
60
B2
10
830
5120
C1
20
710
4120
Demanda
40
50
70
90
90
I II III IV V Oferta
A
10
20
5 910
100
60
40
50
10
B 2 1 8 3 5 12
Investigación Operativa I 14
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
0 0 0
C1
20
710
4120
Demanda
40
50
70
90
90
I II III IV V Oferta
A
10
20
5 910
100
60
40
50
10
10
B2
10
830
5120
C1
20
710
4120
Demanda
40
50
70
90
90
60
I II III IV V Oferta
A
10
20
5 910
100
60
40
50
10
10
B 2 1 8 3 5 12 60
Investigación Operativa I 15
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
0 0 0
60
C1
20
710
4120
Demanda
40
50
70
90
90
60
I II III IV V Oferta
A
10
20
5 910
100
60
40
50
10
10
B
210
830
5120
60
60
60
C
120
710
4120
30
Demanda
40
50
70
90
90
60
30
I II III IV V Oferta
Investigación Operativa I 16
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
A
10
20
5 910
100
60
40
50
10
10
B
210
830
5120
60
60
60
C
120
710
4120
30
90
Demanda
40
50
70
90
90
60
30
Por lo tanto el resultado será:
40(10) + 50(20) + 10(5) + 60(8) + 60(30) + 30(10) + 90(4)= 4390
EJERCICIO Nº 3________________________________________________________________________________
Las tiendas EFE dispone de cinco puntos de venta A, B , C, D, E y cuatro fabricas X, Y, Z , T , los pedidos mensuales de los puntos de venta expresados en miles de unidades son:
A B C D E TOTAL
150
40
30
50
80
350
Investigación Operativa I 17
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
La producción mensual en miles de unidades es:
X Y Z T TOTAL
120
150
160
70
500
La matriz de costos unitarios de transporte es el siguiente:
A B C D E
X 0.8
2.7
1.5
2.5
2.7
Y 0.9
1.2
2.0
0.7
2.5
Z 0.7
2.0
2.5
1.8
3.5
T 2.3
0.9
1.5
1.6
2.5
Determinar la solución optima del problema previa determinación de la solución inicial factible por el método de la matriz mínima (celda de costo mínimo).
SOLUCION AL PROBLEMA POR METODO DE MATRIZ MINIMA
A B C D EFictici
oOferta
X
0.8
2.7
1.5
2.5
2.7 0 120
120
Y 0.9
1.2
2.0
0.7
2.5 0 150
Investigación Operativa I 18
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
40
Z
0.7
2.0
2.5
1.8
3.5 0 160
150
T
2.3
0.9
1.5
1.6
2.5 0 70
Demanda
150 40 30 50 80 150
A B C D EFictici
oOferta
X
0.8
2.7
1.5
2.5
2.7 0 120
120
Y
0.9
1.2
2.0
0.7
2.5 0 150
50
Z
0.7
2.0
2.5
1.8
3.5 0 160
150
T
2.3
0.9
1.5
1.6
2.5 0 70
Demanda
150 40 30 50 80 150 30
Investigación Operativa I 19
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
A B C D EFictici
oOferta
X
0.8
2.7
1.5
2.5
2.7 0 120
120
Y
0.9
1.2
2.0
0.7
2.5 0 150
40
50
Z
0.7
2.0
2.5
1.8
3.5 0 160
150
T
2.3
0.9
1.5
1.6
2.5 0 70
Demanda
150 40 30 50 80 150 30
A B C D EFictici
oOferta
X
0.8
2.7
1.5
2.5
2.7 0 120
120
Y
0.9
1.2
2.0
0.7
2.5 0 150
40
50
30
Z 0.7
2.0
2.5
1.8
3.5 0 160
15
Investigación Operativa I 20
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
0
T
2.3
0.9
1.5
1.6
2.5 0 70
Demanda
150 40 30 50 80 150 30
A B C D EFictici
oOferta
X
0.8
2.7
1.5
2.5
2.7
0120
120
Y
0.9
1.2
2.0
0.7
2.5
0150
40
50
30
30
Z
0.7
2.0
2.5
1.8
3.5
0160
150
10
T
2.3
0.9
1.5
1.6
2.5
0 70
30
40
Demanda
150 40 30 50 80 150 30
Por lo tanto el resultado será:
120(0) 40(1.2 + 50(0.7) + 30(2.5) + 30(0) + 150(0.7) + 10(3.5) + 40(2.5) + 30(1.5) = 443
Investigación Operativa I 21
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
EJERCICIO Nº 4
Un problema de transporte se caracteriza por tener la siguiente matriz.
Destino 1
Destino 2
Destino 3
Destino 4
SUMINISTRO
Origen 1
6 16 18 12 60
Origen 2
16 8 12 6 40
Origen 3
20 12 16 8 100
Origen 4
16 10 14 10 120
PEDIDO
100 80 160 60
Determinar cómo debería hacerse este reparto para minimizar el costo total de transporte.
SOLUCION AL PROBLEMA POR METODO VOGEL
Destino 1
Destino 2
Destino 3
Destino 4
SUMINISTR
Mayor Diferenci
Investigación Operativa I 22
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
a
Origen 16 16 18 12 60
Origen 216 8 12 6 40
Origen 320 12 16 8 100
Origen 416 10 14 10 120
FICTICIO0 0 0 0 80
PEDIDO
100
80160
60
Mayor Diferenci
a
UNA VES BALANCEADO LA MATRIZ PROCEDEMOS A EVALUAR COMO EL EJERCICIO Nº 1
Destino 1
Destino 2
Destino 3
Destino 4
SUMINISTR
Mayor Diferenci
a
Origen 16 16 18 12 60 6
Origen 216 8 12 6 40 2
Origen 320 12 16 8 100 4
Origen 416 10 14 10 120 4
Investigación Operativa I 23
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
FICTICIO0 0 0 0 80 0
80
PEDIDO
100
80160
60
80
Mayor Diferenci
a6 8 12 6
Destino 1
Destino 2
Destino 3
Destino 4
SUMINISTR
Mayor Diferenci
a
Origen 16 16 18 12 60 6
60
Origen 216 8 12 6 40 2
Origen 320 12 16 8 100 4
Origen 416 10 14 10 120 4
FICTICIO0 0 0 0 80
80
PEDIDO
100
80160
60
60 80
Mayor 12 2 2 2
Investigación Operativa I 24
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
Diferencia
Y así sucesivamente llegamos hasta la tabla final.
Destino 1
Destino 2
Destino 3
Destino 4
SUMINISTR
Mayor Diferenci
a
Origen 16 16 18 12 60
60
Origen 216 8 12 6 40
40
Origen 320 12 16 8 100
40 60
Origen 416 10 14 10 120
40 40
FICTICIO0 0 0 0 80
80
PEDIDO
100
80160
60
Mayor Diferenci
a
Por lo tanto el resultado será:
60(6) + 40(8) + 40(16) + 60(8) +40(10) + 40(14) + 80(0) = 3400
EJERCICIO Nº 5
Una Cia. Tiene tres fábricas de los que tiene que embarcar productos de primera necesidad a siete bodegas. El costo unitario de transporte de las fábricas a cada bodega, los
Investigación Operativa I 25
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
requerimientos de las bodegas y las capacidades de las fábricas son:
FABRICAS
BODEGAS 1 2 3 REQUERIMIENTOS
A 6 11 8 100
B 7 3 5 200
C 5 4 3 450
D 4 5 6 400
E 8 4 5 200
F 6 3 8 350
G 5 2 4 300
Las capacidades de las fabricas son 700, 400 y 100
a) Encontrar el plan inicial de mínimo costo.b) Representar la forma general del modelo de transporte.c) Encontrar la solución optima del problema de transporte.
A continuación solo se muestra la tabla final de este ejercicio:
6 7 5 4 8 6 5 0 700
100
100
100
100
11 3 4 5 4 3 2 0 400
350
50
8 5 3 6 5 8 4 0 1000
200
450
200
150
100
200
450
400
200
350
300 100
Por lo tanto el resultado del es:
Investigación Operativa I 26
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
100(6)+400(4)+100(5) + 100(0) +350(3)+ 50(2) + 200(5) + 450(3)+200(5)+150(4)=7800
EJERCICIO Nº 6
Una empresa manufacturera produce alimentos balanceados para aves tiene cuatro plantas y distribuye a cinco centros de consumo, existentes en diferentes distritos del capital y se caracteriza por tener constante la siguiente matriz de costos.
Destino 1
Destino 2
Destino 3
Destino 4
Destino 5
EXIST.
Origen 1
28 32 34 2436
240
Origen 2
36 24 42 3244
380
Origen 3
40 30 38 3638
120
Origen 4
32 26 50 4042
100
EXIGENC.
160 200 240 220120
a) Determinar el programa optimo de transporte de costo mínimob) Si de manera obligatoria se transporta como mínimo 100 de
Origen1 a Destino 2, de Origen 3 a destino 1 y 160 de Origen 4 a
Investigación Operativa I 27
INGENIERÍA DE SISTEMAS Y COMPUTACÓN – UNDAC - 2009
Destino 3, determinar el nuevo programa de transporte con lo expuesto.
A continuación solo se muestra la tabla final de este ejercicio:
28 32 34 24 36 240
120
120
36 24 42 32 44 380
200
180
40 30 38 36 38 120
60 20 40
32 26 50 40 42 100
100
0 0 0 0 0 100
100
160
200
240
220
120
120(34)+120(36)+200(24)+180(32)+60(40)+20(38)+40(36)+100(32)+100(0)=26760
Investigación Operativa I 28