Problemas resueltos IO

Segundo Control INFO 171 (2001)
1.- Una empresa tiene un trabajo compuesto de 5 módulos para ser desarrollado por 5 programadores, se
desea que cada módulo sea desarrollado por un solo programador y que cada programador desarrolle un solo
módulo. Debido a los diferentes grados de dificultad de los módulos y a las diferencias individuales de los
programadores, el tiempo (en días) que ellosemplean es diferente y se da en la siguiente tabla:

Módulo 1
Módulo 2
Módulo 3
Módulo 4
Módulo 5

A
2
2
5
3
8

B
4
6
6
5
5

C
4
5
5
7
6

D
3
4
3
2
2

E
6
6
7
4
1

a) Determine la asignación óptima de modo de minimizar el tiempo total
b) Para cuándo debe comprometerse a entregar el trabajo
c) Cómo sería la formulación si un programador puede
desarrollarmás de un módulo?
d) Cuál es la opción que más le conviene hacer a la
empresa?

2.- Una empresa que tiene 3 fábricas: A, B y C y 4 depósitos distribuidores: 1, 2, 3 y 4. los costos unitarios,
oferta y demanda mensual es:

A
B
C
Dda
a)
b)
c)
d)

1
7
6
9
200

2
9
10
8
240

3
9
12
10
280

4
6
8
14
340

Oferta
300
100
500

Halle el programa óptimo dedistribución y su costo asociado.
La solución es única?, es degenerada?. Justifique
Existe oferta o demanda insatisfecha, de ser así, quién la absorve? Cuántas unidades?
Si se tiene que la capacidad de transporte esta limitado a 250 unidades, se modifica la solución óptima
del problema, de ser así, cómo obtiene la nueva solución? (sólo indíquelo)

3.- En un problema con nodos intermedios, lapolítica actual de la empresa es la siguiente:
A envía 200 unidades a 1 y 100 unidades a 2. B envía 200 unidades a A y 1 envía 100 unidades a 3.
La tabla de costos unitarios, oferta y demanda mensual es la siguiente:

A
B
Dda

1
10
20
100

2
20
50
100

3
30
40
100

1
2
3

1
0
10
80

2
40
0
20

3
10
20
0

Oferta
100
250

1
2
3

A
B

A
20
40
60

A
050

B
30
20
70

B
80
0

a) La empresa está trabajando con la política óptima. Justifique
b) Cuál es el costo mínimo
Los tres ejercicios tienen la misma ponderación.
Buena suerte!

SOLUCION
1.-a
Módulo 1
Módulo 2
Módulo 3
Módulo 4
Módulo 5

A
0
0
3
1
6

B
0
2
2
1
1
(1)

C
0
1
1
3
2

1 hace
2 hace
3 hace
4 hace
5 hace

Ao
A
Co
D
Do

BoC

D
1
2
1
0
0

E
5
5
6
3
0

(1)

⇒

A
0
0
2
1
6

Módulo 1
Módulo 2
Módulo 3
Módulo 4
Módulo 5
1 hace B
2 hace A
3 hace C
4 hace D
5 hace E

D
E

B
0
2
1
1
1
(1)

C
0
1
0
3
2

Tpo tot
(1)

D
1
2
0
0
0

E
5
5
5
3
0

=14
(4+2+5+2+1)

1 b.- Debe comprometerse a terminar el trabajo en 5 dias .

(1)

1 c.- La formulaciónsería PL
MIN
SA

2X1A+4X1B+4X1C+......2X5D+X5E
(1)
X1A+X1B+X1C+X1D+X1E = 1
.......................................................
módulo hace un solo programador
X5A+X5B+X5C+X5D+X5E = 1
X1A+X2A+X3A+X4A+X5A > 1
.......................................................
X1E+X2E+X3E+X4E+X5E > 1
X ij = 0 o 1

(1)

programador hace uno o más módulos (1)
(1)

1 d. Conviene la opción enla cual la duración de los proyectas sea mínima. (1)
2.- a) Usando Vogel, la soluc.bas.ini es:

A
B
C
Dda

1
7
6 60
9 140
0
200
140

2
9
10
8 240
0
240

Aplicando MODI
vj
9
ui
1
-5
A
7
4
-3
B
6 60
0
C
9 140
-10
0 -1
Dda 200
vj
ui
-4
-3
0
-10

A
B
C

9
1
7
6
9
0

3
9
12
10 140
0 160
280
140

4
6 300
8 40
14
0
340
40

Oferta300
100
60
500
160

8
2
9
3
10 5
8 240
0
-2
240

10
3
9 5
12 7
10 140
0 160
280

11
4
6 300
8 40
14 11
0
1
340

8
2
5 9
4
100 10 5
100 8 240
-1
0
-2

10
3
9 6
12 7
10 160
0 120

10
4
6 300
8 7
14 10
0
40

(3)

Ruta es:
1
A
B
6 60
(1/2) C
9 140

2

3

4
8

10 140
0 160

40

+

(1/2)

(1/2)

Solución óptima es:...