ESTUDIOS PROFESIONALES PARA EJECUTIVOS

(EPE)

TAREA ACADEMICA 3

Curso: INVESTIGACION DE OPERACIONES II

Integrante: HUARAC ROSELL, ALVARO -

U201818617

AMESQUITA MEDINA, MAYCOL -

U201914183

Tema: PROGRAMACION DINAMICA

Profesor: TUPIA DE LA CRUZ, Elmer

FECHA: SETIEMBRE - 2020

 1. PROBLEMA DE APLICACIÓN

La empresa Transportes Cromotex dispone de 6 agencias para

asignar a tres sectores. El aumento de la productividad en los
sectores depende de la asignación, y es la que se indica en el cuadro
siguiente:

Núm. Agencias asign. \ Sector-1 Sector-2 Sector-3

sector
0 0 0 0
1 12 14 13
2 25 19 21
3 30 37 32
4 40 49 48

¿Cuántas agencias asignar a cada sector para hacer máxima la

suma de aumento de la productividad?
Una agencia no asignada no tiene valor asociado en la
productividad. Esto equivale a decir que el valor al horizonte de una
agencia no asignada es de cero, ya que ese valor no influye sobre
el valor de la función objetivo.

2. CALCULO

La función recursiva

Las etapas: Son 3 etapas

Los Estados: Son el número de agencias disponibles.

Decisión: Cantidad de agencias a asignar en cada sector

Retorno: Aumento de la productividad.

n=3

d3 = X3 d2 = X2 d1 = X1

S3 = 6 S2 S1 S0 = 0
3 2 1
f*0(S0) = 0

r3 r2 r1
f1(S1) =Max {r1(S1,d1) + f*0(S0)}
n=1 [sector 1] d1 <= S1
S0 = S1 - d1
d1 = X1 S0 = 0 ----> d1 = S1

S1 1 S0 = 0 f1(S1) =Max {r1(S1,d1)}

f*0(S0) = 0
S1 d1 = X1 f*1 X1
0 0 0 0
r1 1 12 12 1
2 25 25 2
Rango Estado (S) Decisión (d) 3 30 30 3
Mínimo 0 0 4 40 40 4
Máximo 6 6 5 40 40 4
6 40 40 4

n=2 [sector 2]
f2(S2) =Max {r2(S2,d2) + f*1(S1)}
d2 = X2 d2 <= S2
S1 = S2 - d2
S2 2 S1

d2 = X2
S2 f*2 X2
0 1 2 3 4
r2 0 0 --- --- --- --- 0 0
1 12 14 --- --- --- 14 1
Rango Estado (S) Decisión (d) 2 25 26 19 --- --- 26 1
Mínimo 0 0 3 30 39 31 37 --- 39 1
Máximo 6 4 4 40 44 44 49 49 49 3,4
5 40 54 49 62 61 62 3
6 40 54 59 67 74 74 4

n=3 [sector 3]

d3 = X3 f3(S3) =Max {r3(S3,d3) + f*2(S2)}

d3 <= S3
S3 = 6
3
S2 S2 = S3 - d3

r3

Rango Estado (S) Decisión (d) d3 = X3

S3 f*3 X3
Mínimo 6 0 0 1 2 3 4
Máximo 6 4 6 74 75 70 71 74 75 1
Decisiones:

d3 = 1 + d2 = 3 + d1 = 2 = 6

S3 = 6 S2 = 5 S1 = 2 S0 = 0
3 2 1

r3 = 13 + r2 = 37 + r1 =25 = 75

Sector Agencias Productividad

1 1 25
2 3 37
3 2 13
TOTAL 6 75

3. REPORTE ADMINITRATIVO:

- La solución óptima: X1=2, X2= 3, X3=1.

- La mayor productividad óptima del caso planteado es de
75.
- Podemos observar que el sector con mayor productividad
es el sector 2 con 37, le sigue el sector 1 con una
productividad de 25 y por último el sector 3.
- Se logra asignando 2 agencias al sector 1.
- Se logra asignando 3 agencias al sector 2.
- Se logra asignando 1 agencia al sector 3.

4. RECOMENDACIONES:

- Se recomienda aumentar las agencias con la finalidad de

aumentar la producción de los sectores.
- La Empresa Transportes Cromotex debe aumentar el
valor de su productividad para los sectores donde se va
ofrecer, ya que de por si cuenta con pocas agencias
generando mayor rentabilidad para cada sector con el
aumento de dichas agencias.
UNA APLICACION DE LA PROGRAMACION DINAMICA EN LA
UTILIZACION DE UNA RED DE AGENCIAS

M a n u e l del R i o Bueno
Departamento de Estadistica Mat. e I. O.
Facultad de Ciencias. Universidad de Madrid.

Consideramos en esta nota una soluci6n al problema consistente

en satisfacer k necesidades mediante n agencias, de modo que los
costes de desplazamiento y servicio sean mfnimos. Se utiliza el princi-
pio de la programaci6n dinfimica, idea que hemos tomado de un
trabajo de J. P. Saksena. Se ha considerado tambi6n la existencia de
un orden en la satisfacci6n de las necesidades.

Nos damos cuenta de las posibles dificultades de c6mputo que

pueden presentarse al resolver asf este problema. Nuestro fin es, senci-
llamente, indicar un posible planteamiento y su soluci6n, sin pretender
sean los mejores.

1. Planteamiento del problema.

Consideremos el caso general en que cada agencia puede satisfacer

mils de una necesidad. Descomponemos cada agencia en un nflmero de
agencias igual al de necesidades que resuelve, agrupando estas nuevas
agencias de acuerdo con las necesidades que satisfacen. Tenemos asf, un
origen O, una serie de conjuntos N ~ - . - N t , satisfaci6ndose la nece-
sidad i en las agencias A i l . . . A i n i que componen el conjunto N i.

159
 Conociendo los costes de transporte entre el origen y las agencias,
T(O, Aq), entre dos agencias, T(Ai] , Alto) , y los costes de servicio en
cada agencia S (Ai]), se trata de encontrar el camino de mfnimo coste
total que parta de O y pase por una agencia en cada conjunto Ni, de
este m o d o se cubrir~in todas las necesidades de forma 6prima.

2. Aplicaci6n del principio de la programaci6n dinfimica.

Supongamos que nos encontramos en Ast y nos falta satisfacer

las necesidades rl . . . rm, denotaremos por f (Ast ; Nrl. . . Nrm )el coste
minimo de los caminos que parten de Ast Y pasan por una agencia de
cada conjunto N r I " " Nrm.

El principio de 6ptimo de Bellman proporciona,

f ( A s t ; N r l " " Nrm) = rain ( rain [T(Ast, Ari i) + S (ArH) +

ri ~1~ ] ~ n i
l~i~m

+ f(Ari],Nrl."Nri".Nrm)] (1)

donde el simbolo Nri indica que Nri ha sido suprimido.

Este proceso iterativo comienza con,

f(Ast, Nr) = min [T(Aq, Ar/)+S(Ari)]

l~i~n r

y conduce a la resoluci6n 6ptima dada por,

f(O;N~...Nk)= min l min [T(O,'Ai])+S(Ai])+

l~i~k [ l~]~n i

+ I(Aii;N~ " 9 N" 9 9 Ark)]

La sucesi6n de pares (ri,]) que conducen a este 6primo proporcio-

na el orden en que deben reconocerse los conjuntos Ni y la agencia
que debe visitarse en cada uno.

Desde el punto de vista de necesidades de c6mputo, para conocer

la funci6n f ( A s t ; N r l ' " Nrm) al variar sus argumentos necesitamos
k--1
conocer los valores f ( A q , N v l ' ' " Nvm_l). Fijado i tenemos ( m - - 1 )
elecciones posibles de v~. 9 9 Vm Y para cada una de e l i a s / p u e d e tomar
n i valores. Por tanto, para completar el paso m debemos reservar

160
 k k--1 k--1 k
Z ) ni ) Z ni
i=l (m--1 = (m--1 i-1

expresiones, siendo su nflmero m~iximo a lo largo del cfilculo

mfix (m--1) I2 n i = ~ 12 n i
2~m~k-1 i=1 [ ] i=1

k--1
donde [ ] representa la parte entera de 2

Creemos que bajo este aspecto mejoramos una soluci6n dada por
J. P. Saksena, en la que una cota superior de las expresiones que se
reservaban en cada paso venfa dada por

pk k mfix ni
[ ] ' P=l~i<<.~

Ejemplo 1. Consideremos tres agencias A~, A 2, A3 que satisfacen,

respectivamente, las necesidades [1, 2, 3], [2, 3], [1], los costes se
muestran en la tabla 1.

TABLA 1

C 0 A1 A: A 3 S A 1 A: Aa

O - 7 9 1 N1 7 - 9
A1 - 8 10 N2 30 15 -
A: -- 3 N 3 l0 25 -
A3

Descomponiendo cada agencia obtenemos seis agencias agrupadas

en los siguientes conjuntos:

N, = {AII, A 12},
N2 = {A2,, A22},

N3 = {Aa,, A32],

]'/1 -'~ 1'12 ~ H3 --~ 2.

161
 Los costes, que se obtienen trivialmente de los anteriores, se
indican en la tabla 2.

TABLA 2

C (Ai/, Aim ) 0 All All A21 Am A31 A32

0 7 1 7 9 7 9
All - 10 0 8 0 8
Aj~ - 10 3 10 3
- 8 0 8
-- 8 0
-- 8

- 7 9 30 15 10 25

una necesidad.

n [0 + 30, 8 + 15] = 2 3 ; j = 2 : A l l - + A 2 2

[0 + 10, 8 + 25] = 10;1 = 1 : A l l ' + A 3 1

z/= 18;]=2:AI2-~A22" f(A12;Na)=20;]= 1 :AI2-+ Aal

c) f ( A 2 1 ; N I ) = 7 ; ] = 1 :A21"~AI1 " f ( A e i ; N a ) = 1 0 ; ] = 1 : A 2 1 ~ A 3 1
d) f ( A 2 2 ; N 1 ) = 1 2 ; ] = 2 : A 2 2 - ~ A 1 2 " f ( A 2 2 ; N a ) = 18;]= 1 : A22-~A31

e) f ( A 3 1 ; N l ) = 7 ; ] = 1 : A 3 1 ~ A l l " f ( A a l ; N 2 ) = 2 3 ; ] = l :A31~A22

f) f ( A 3 2 ; N I ) = 1 2 ; ] = 2 : A a 2 - ~ A 1 2 " f ( A 3 2 ; N 2 ) = 1 5 ; ] = 2 :A32 ~ A22

2. Falta satisfacer dos necesidades.

a) f ( A n ;N2, N a ) = m i n t min [0+30+10, 8+15+18],

rain [0+10+23, 8 + 2 5 + 1 5 1 / = 33;

ri = 3, ] = 1 : A I I - ~ A a l + A I I

b) f ( A 1 2 ;N2, N 3 ) = 36; ri = 2, ] = 2 : A I 2 " - ~ A 2 ~ " ~ A l l

c) f ( A 2 1 ; N 1 , N 3 ) = 17; ri = 1, ] = I : A 2 1 - ~ A n ~ A 3 1

ri=3, ]= 1 :Aal-~A3t~All

162
d) f(A22;NI, N3)=25; ri = 1, j = 1 A22-+AlI-+A22

ri = 3, / = 1 " A22--'>A31 -+All

e) f ( A 3 1 ; N I , N:)=30; ri = I, / = 1 "AaI-+AlI-+A22

f) f ( A 3 2 ; N 1, N 2) = 27; ri = 2, j = 2 9 A a z - + A 2 z - + A ~ =

Los filtimos caminos se han o b t e n i d o de la parte 1.

3. Falta satisfacer tres necesidades.

f(O;N~, N=, N a ) = rain {min [ 7 + 7 + 3 3 , 1 + 9 + 3 6 ] , min [ 7 + 3 0 + 1 7 ,

9 + 1 5 + 2 5 ] , rain [ 7 + 1 0 + 3 0 , 9 + 2 5 + 2 7 ] / = 46; i = 1, J = 2.

E1 camino 6 p t i m o serfi O - + A 1 2 - + A 2 z - + A 3 1 , q u e e n los t6rminos

iniciales corresponde a satisfacer la necesidad 1 en A3, pasar a A= y
resolver la necesidad 2, f i n a l m e n t e se satisface la necesidad 3 en A i-

3. Necesidades ordenadas.

i) Ordenaci6n parcial.

Supongamos que las necesidades est~n parcialmente ordenadas,

siendo previas a la satisfacci6n de la necesidad i las necesidades
il...iqi, sea Qi el c o n j u n t o de estas necesidades previas Qi = [ N i l " "
-. Niqi}. Si Pi representa las necesidades que p u e d e n satisfacer desde
Ni, aun c u a n d o no lo sean de m o d o i n m e d i a t o (puede ser preciso
a t e n d e r otras antes), se tiene Pi = (Qi t o N i ) c, por tanto, Pi = { N i l " "
9" Nipi }, Pi = k -- qi -- 1.
Estas restricciones reducen los cdlculos pues basta c o n o c e r
f ( A s t ; N q . . 9 N r m ) c u a n d o N q , 999, Nrm E Ps, es decir, para indices
q , 9 9 9, rm E is1. 99 Sps}; si Ps < m la funci6n no estfi definida. E1 mf-
n i m o en ri que se consideraba en ( 1 ) d e b e ahora extenderse finica-
m e n t e a ri para los cuales f ( A r i j ; N r l . . . N r i " " N r m ) e s t ~ definida,
es decir, cuando

m
Nri E N Prl , l--/=i.
l=1

163
 Para obtener todo valor f ( A s t ; N r l ' ' " Nr m) posible debemos
conocer los valores posibles de f(Aij;Nv.~ - 9 9Nvm-1). Fijado i, elegimos
Vla " " Vm - ~ entre i ~ . - . i P i , e x i s t e n ( , , , Pi
--~
) elecciones(entendemosque
( b ) est~i definido Va, b ~ Z , c o n l o c u a l ( a ) = 0 si a < b, situaci6n
que se presenta cuando Pi < m - - l ) y para cada una de elias ] puede
tomar n i valores. Por tanto, d e b e m o s reservar
k
Yl i
E (mPi
1_ )
i=1

expresiones, siendo su nflmero mfiximo a lo largo del proceso

k
m~ix y, ( Pi ) ni
2~m~k-1 i=1 m--1

Creemos que, tambi6n en este caso y bajo este aspecto, mejoramos

la soluci6n dada por J. P. Sakena, basada en una estructura de hiper-
cubo tomada de una idea de Gonzfilez. Sin embargo, es preciso observar
que el procedimiento descrito obtiene valores de la funci6n f corres-
pondientes a caminos no admisibles, siendo posible su supresi6n finica-
mente a la vista del grafo particular que describa la ordenaci6n parcial.
Este exceso de c~ilculo es el que hace posible la aplicaci6n del m6todo
independientemente del grafo que se considere.

E]emplo 2.- Afiadamos a l ejemplo anterior la restricci6n de que

la necesidad 3 debe satisfacerse antes que la necesidad 2. En este caso
Q, = ~b, Q2 = N3, Q3 = q~ Y P , = IN2, N3], P2 = {N,}, P3 = [ N , , N2},
pl=p3=2, P2 = 1.
En el primer paso se calcular~in los valores considerados en el
ejemplo l, excepto f ( A 2 1 ; N3) y f ( A 2 2 ; N3). En el segundo paso se
calcularfin los valores de los apartados 2e), 2f); no est~in definidos
ahora 2c), 2d) y los valores correspondientes a 2a), 2b) son ahora

f ( A 11; N2, N3) = rain [0+ 1 0 + 2 3 , 8 + 2 5 + 15 ] = 33 ;ri=3,j= 1 :A 11~ A 31~ A 22

f (A 12;N2,Ns) = min [lO+lO+23,3+25+15]=33;ri=3,j=l :A 12~A31-~A22

ri=3 ,j=2 :A 12-->A a2--+A22

Finalmente se tiene,

164
f(O; Nl, N2, N3) = rain t m i n [ 7 + 7 + 3 3 , 1+9+43], min [ 7 + 1 0 + 3 0 ,

9+25+27]}=47; i = 1, j = 1 "O~AII~A31~A2:

i=3, ]= 1 :O~A31~Alx~A22

ii) O r d e n a c i 6 n total.

S u p o n g a m o s ahora que las n e c e s i d a d e s est~n t o t a l m e n t e o r d e n a -

das, siendo previa a la satisfaccidn de cada necesidad i la necesidad i - - 1.
Este es u n caso particular del a n t e r i o r con Pi = { N i + l ' " Nk}, sin
embargo es posible una r e d u c c i 6 n m a y o r ya que s61o en una etapa d a d a
p o d e m o s partir de Ni y f l n i c a m e n t e p o d e m o s llegar a Ni+l.

E1 p r o b l e m a p u e d e r e p r e s e n t a r s e gr~ificamente det siguiente m o d o

(fig. 1 ), c o n unos ejes XY, en cada r e c t a X = i c o n s i d e r a m o s n i p u n t o s
asociados a l a s agencias de Ni.

A 2n2 Akn k
A in1
Ak-i nk_ 1

A12 A22 Ak-22 Ak2

A11 A21 Ak-ll Akl

O X=I X=2 X=k-i X=k

Figura 1

D e b e m o s e n c o n t r a r un c a m i n o de coste m f n i m o que parta de O y

llegue a la recta X = k c o r t a n d o a X = 1 , - - . X = k - - 1 .

Sea f(Ast) el coste m / n i m o de los caminos que parten de Ast y

pasan p o r Ns+l 9 9 9 Nk en este o r d e n . T e n e m o s ,

f(Ak-lt) = min [C (Ak-lt, Ak/) + S (Akj) ]

l <<.j~nk
f(Ast) = rain [C (Ast, As+l/) + S (As+l/) + f(As+l])]
l <<.j<~ns+l

165
proccso quc conduce a la soluci6n 6ptima,

f(O) rain [C(O, Al/) +S(AI/) +f(A~i)]

l~/~n 1

Los fndiccs ] que |teven a cste m i n i m o muestran las agencias que

deben visitarse en cada conjunto.

Para el cfilculo de cada f(Ai/) necesitamos conocer hi+ l valores,

siendo su nfimero m~iximo a 1o largo del cfilculo m~x ni.

4. Observaci6n.

La idea descrita podria extenderse al caso estoc~istico en que

existen unas probabilidades de que ciertas agencias est6n completas
y sea preciso, por tanto, trasladarse a otra agencia que satisfaga la
necesidad en 1o que se present6 la imposibilidad del servicio.

BIBLIOGRAFIA.

R. BELLMAN, (1957): Dynamic Programming, Princeton University

Press.

R. BELLMAN, S. DREYFUS, (196 2 ): Applied Dynamic Programming,

Princeton University Press.

J_ P. SAKSENA, (1970): Mathematical model of scheduling clients,

through welfare agencies. Journal of the Canadian Operations
Research Society, 8 (3), pgs. 185-200.

166