SESIÓN 6 INVOP2 PDD ASIGNACIÓN DE RECURSOS PRESENTACIÓN

INVESTIGACIÓN DE OPERACIONES 2
Sesión 6: PDD – Asignación de Recursos

LOGRO DE LA SESIÓN

•

Los estudiantes al finalizar la sesión
tendrán las competencias para resolver
problemas de decisión de asignación de
recursos
mediante
el
uso
de
programación dinámica determinística.

CASO 1: ASIGNACIÓN DE RECURSOS
Un inversionista tiene $6000 para invertir en tres posibles alternativas (A, B y C).La
inversión nos proporciona los siguientes retornos:

Cantidad Invertida
(miles de dólares)

A

B

C

0
1
2
3
4
5
6

0.0
0.5
1.0
3.0
3.1
3.2
3.3

0.0
1.5
2.0
2.2
2.3
2.4
2.5

0.0
1.2
2.4
2.5
2.6
2.7
2.8

¿Cuál es la estrategia óptima de inversión?

CASO 1: ASIGNACIÓN DE RECURSOS
x1

y1

x2

y2

x3

y3

y4

1

2

3

f1(x1,y1)

f2(x2,y2)

f3(x3,y3)

Variables de Decisión:
xi : Cantidad (miles) ainvertir en la alternativa i

Variables de Estado:
yi : Cantidad (miles) disponibles antes de invertir en i
i = 1, 2, 3 (1=A, 2=B, 3=C)

CASO 1: ASIGNACIÓN DE RECURSOS
x1

y1

x2

y2

x3

y3

y4

1

2

3

f1(x1,y1)

f2(x2,y2)

f3(x3,y3)

Condiciones de borde:
y1 = 6

Reglas de transformación:
y1 = y2 + x1
y2 = y3 + x2
y3 = y4 + x3

CASO 1: ASIGNACIÓN DE RECURSOS
x1

y1

x2

y2

x3

y3

y4

1

2

3f1(x1,y1)

f2(x2,y2)

f3(x3,y3)

Funciones de retorno:
fi (xi, yi) : ganancia obtenida luego de invertir en i, xi miles de dólares cuando se
disponía de yi miles de dólares
Función recursiva:
Fi(Yi) = maxxi { fi (xi, yi) + Fi+1 (Yi+1) }

i = 1, 2, 3

CASO 1: ASIGNACIÓN DE RECURSOS
Etapa 3:

X3

0

1

2

3

4

5

6

F3(Y3)

X3

0

0.0

NP

NP

NP

NP

NP

NP

0.0

0

1

0.0

1.2

NP

NP

NP

NPNP

1.2

1

2

0.0

1.2

2.4

NP

NP

NP

NP

2.4

2

3

0.0

1.2

2.4

2.5

NP

NP

NP

2.5

3

4

0.0

1.2

2.4

2.5

2.6

NP

NP

2.6

4

5

0.0

1.2

2.4

2.5

2.6

2.7

NP

2.7

5

6

0.0

1.2

2.4

2.5

2.6

2.7

2.8

2.8

6

Y3

CASO 1: ASIGNACIÓN DE RECURSOS
Etapa 2:
X2

0

1

2

3

4

5

6

F2 (Y2)

X2

0

0.0 + 0.0
= 0.0

NP

NP

NP

NP

NP

NP

0.0

0

1

0.0 + 1.2 1.5 + 0.0
= 1.2
=1.5

NP

NP

NP

NP

NP

1.5

1

2

0.0 + 2.4 1.5 + 1.2 2.0 + 0.0
= 2.4
= 2.7
= 2.0

NP

NP

NP

NP

2.7

1

3

0.0 + 2.5 1.5 + 2.4 2.0 + 1.2 2.2 + 0.0
= 2.5
= 3.9
=3.2
= 2.2

NP

NP

NP

3.9

1

4

0.0 + 2.6 1.5 + 2.5 2.0 + 2.4 2.2 + 1.2 2.3 + 0.0
= 2.6
= 4.0
= 4.4
= 3.4
= 2.3

NP

NP

4.4

2

5

0.0 + 2.7 1.5 + 2.6 2.0 + 2.5 2.2 + 2.4 2.3 + 1.2 2.4 + 0.0
= 2.7
= 4.1
= 4.5
= 4.6
= 3.5
= 2.4

NP4.6

3

6

0.0 + 2.8 1.5 + 2.7 2.0 + 4.6 2.2 + 2.5 2.3 + 2.4 2.4 + 1.2 2.5 + 0.0
= 2.8
= 4.2
= 4.6
= 4.7
= 4.7
= 3.6
= 2.5

4.7

3.4

Y2

CASO 1: ASIGNACIÓN DE RECURSOS
Etapa 1:

X1

0

Y1
6

1

2

3

4

5

6

0.0 + 4.7 0.5 + 4.6 1.0 + 4.4 3.0 + 3.9 3.1 + 2.7 3.2 + 1.5 3.3 + 1.5
= 4.7
= 5.1
= 5.4
= 6.9
= 5.8
= 4.7
= 4.7

F1 ( Y1)

X1

6.9

3

SOLUCIÓN:
ETAPA 1:

y1 = 6

X1 = 3

ETAPA 2:

y2 = y1 –x1 = 6 – 3 = 3

X2 = 1

ETAPA 3:

y3 = y2 – x2 = 3 – 1 = 2

X3 = 2

Se debe invertir $ 3000 en la Alternativa A, $ 1000 en la Alternativa B y $ 2000 en la
Alternativa C; con el fin de obtener una ganancia máxima de $ 6900.

CASO 2: PROBLEMA DE LA MOCHILA
Un barco con 4 toneladas de capacidad puede ser cargado con una o más unidades de
tres artículos diferentes. La tabla siguiente muestra el pesounitario pn , en toneladas y el
ingreso por unidad in , en miles de $, para el artículo n.

Artículo
n

Peso
pn

Ingreso
in

1
2
3

2
3
1

31
47
14

¿Cómo se debe cargar el barco para maximizar los ingresos totales?
Tener en cuenta que el barco puede cargar estos artículos en cualquier orden, además,
como el peso unitario y el peso permisible son valores enteros, las variables sólo deben
tenervalores enteros.

CASO 2: PROBLEMA DE LA MOCHILA
x1
y1

x2
y2

x3
y3

y4

1

2

3

f1(x1,y1)

f2(x2,y2)

f3(x3,y3)

Variables de decisión:
xi : cantidad de artículos tipo i a transportar

Variables de estado:
yi : capacidad disponible en Tn. antes de asignar los artículos tipo i a la barco.
i = 1, 2, 3, 4

CASO 2: PROBLEMA DE LA MOCHILA
x1
y1

x2
y2

x3
y3

y4

1

2

3

f1(x1,y1)

f2(x2,y2)...