American Journal of Computational Mathematics, 2011, 1, 247-251
doi:10.4236/ajcm.2011.14029 Published Online December 2011 (http://www.SciRP.org/journal/ajcm)
Chebyshev Approximate Solution to Allocation Problem in
Multiple Objective Surveys with Random Costs
Mohammed Faisal Khan1*, Irfan Ali2, Qazi Shoeb Ahmad1
1Department of Mat hem at i cs, Integral University, Lucknow, India
2Department of Statistics & Operations Research, Aligarh Muslim University, Aligarh, India
Received July 23, 201 1; revised August 29, 2011; accepted September 8, 2011
Abstract
In this paper, we consider an allocation problem in multivariate surveys as a convex programming problem
with non-linear objective functions and a single stochastic cost constraint. The stochastic constraint is con-
verted into an equivalent deterministic one by using chance constrained programming. The resulting multi-
objective convex programming problem is then solved by Chebyshev approximation technique. A numerical
example is presented to illustrate the computational procedure.
Keywords: Chance Constrained Programming, Multivariate Stratified Sampling, Optimum Allocation,
Chebyshev Approximation
1. Introduction
Optimum allocation of sample sizes to various strata in
univariate stratified random sampling is well defined in
the literature. But usually in real life problems more than
one population characteristics are to be estimated, which
may be of conflicting nature. There are situations where
the cost of measurement varies from stratum to stratum.
Also the cost of enumerating various characters is gener-
ally much different. Further the strata variances for the
various characters may not be distributed in the same way.
Allocation based on one character may not be optimum
for the others. One way to resolve this problem is to
search for a compromise allocation, which is in some
sense optimum for all the characters.
Kokan and Khan [1], Chatterjee [2], Huddleston [3],
Bethel [4], Chromy [5] all discussed the use of convex
programming in relation to multivariate optimal allocation
problem. The above convex programming approaches
give the optimal solution to the problem with given tol-
erance limits on variances but the resulting cost may not
be acceptable so that a further search is usually required
for an optimal solution which falls within the budgetary
constraint limit.
The case when sampling variances are random in the
constraints has been dealt with by Diaz-Ga rcia [6]. Javai d
and Bakhs hi [7] applied m odifi ed E-m odel for s olving t he
multivariate allocation problem when the costs are con-
sidered random in the objective function. Bakhshi [8] find
the optimal Sample Numbers with a Probabilistic Cost
Constraint.
In this pa per, we consider t he problem of allocating the
sample to various strata when several characters are under
study and the budget is fixed. We minimize the variances
of various characters subject to the condition of given
budget. The problem is transformed to a convex pro-
gramming problem (CPP) with several linear objective
functions and single convex constraint. The resulting CPP
is then solved by Chebyshev approximation approach.
2. Formulation of the Problem
We consider a multivariate population consisting of
units which is divided into disjoint strata of sizes
N
L
12
,,,
L
NN N such that
1
L
i
i
N

N
. Suppose that cha- p
racteristics


1, ,j
th
i
p are measured on each unit of
the population. We assume that the strata boundaries are
fixed in advance. Let i
n units be drawn without re-
placement from the stratum For
character, an unbiased estimate of the population mean
1,, .iLth j


,p1,Yj
j. denoted by ,
j
st
y has its sampling vari-
ance

22
1
11
,1,,
L
jsti ij
iii
VyWSjp
nN


 


 (2.1)

M. F. KHAN ET AL. 248
where i
iN
WN  is the stratum weight and

2
2
1
1
1
i

N
ijijh ij
h
i
Sy
N

Y is the variance for the
th
j
character in the stratum.
th
i
Let ij be the cos t of enumerat ing the character in
the stratum and let the overhead cost 0 be constant.
Let
cth
j
c
th
i
C be the upper limit on the total cost of the survey.
Then assuming linear cost function one should have
0
11
p L
ij i
ij
cn cC


 or , (2.2)
1
L
ii
i
cn C



where is the cost of enumeration of all the
1
p
i
j
c

i
j
cp
character in the stratum and
th
i0
CCc.
The restrictions on the sample size from various strata
are
2,1,
ii
nNi L , (2.3)
Let us assume that the survey is to be cond ucted in such
a way that the variances for all the p characters are mini-
mized for a fixed budget i.e., we have to minimize all the
variances together given by (2.1).
Ignoring the constant terms in (2.1), th e NLP problems
to be solved are
22
1
1
min, 1,...,
Subject to
and 2,1,,,
Liij
nii
L
ii
i
ii i
WS
Vjp
n
cn C
nNi LnN



 







 





(2.4)
By making the transformation 1,1,,
ii
ni
x
p and
putting the problems (2.4) are transformed
into
22
,
iji ij
aWS
1
min,1,...,,(1)
Subject to
(2)
11
and,1, ,(3)
2
L
ij i
i
i
i
i
ax jp
cC
x
xi L
N










 




(2.5)
In many practical situations the costs i in the various
strata ar e not fixed a nd vary f rom one uni t to the ot her. Let
us assume that i, are independently nor-
mally distributed random variables. So, we write the
above problem in the following chance constrained pro-
c
c1, ,i
1
0
min,1,,(1)
Subject to
(2)
2,1,..., ,(3)
Lax
ij j
i
i
i
ii i
j p
c
PCp
x
nNi LnN















 




(2.6)
where

0
p, 0 01p

 is a specified probability.
3. Deterministic Equivalent Using Chance
We have assumed that the cost, in the
Constrained Programming
si c
en 1, ,iL ntly and noconstraint function 2.6 (2) are inde pd ermally
distributed random variables. Then function 1
Li
c
ii
x


, will
also be nor mally distri b uted with mean as

11
1
,
LL
ii
L
ii i
i
ii i
cEc
E

x
xx








  (3.1)
wher

e


ii
Ec  , 1, ,iL

, and variance as

2
L
22
1
1
ii
ii
iii
c
VVc
x x

L
gramming form:
x







(3.2)
where


2
ii
Vc  .
Now let

1
Li
ii
c
fc
x



, where then
{2.6 (2)} is given by

1,, , n
cc c




0,fc Cp P
or
 


 
 
 
0,
fcEfcCEfc
Pp
Vfc Vfc







 



f
cEfc
Vfc









where is a standard normal variable
with mean zero and variance one. Thus the probability of
realizing




f
c less than or equal to C can be written
as
 
 
 
CEfc
Pfc CVfc 










, (3.3)
where


z 
stand represents the cumulative density function of the ard normal variable evaluated at z. If
K

represents the value of the standard normal variable
which at


0
K
p



, then the constraint (3.3) can be writ-

M. F. KHAN ET AL.249
defined by inequalitie qten as
 
 

.
CEfc K
Vfc








(3.4)
The inequality (3.4) will be satisfied only if


 
,
CEfc
K
Vfc







or equivalently,
   


.EfcK VfcC

 (3.5)
Substituting from (3.1) and (3.2) in (3.5), we get
2
LL
2
11
.
ii
ii
ii
K
C
xx






(3.6)
If the constants


i

and i

din (3.6) are unknown then
we use their estimas 2
ˆˆ
an .
ii
tor


Thus

1
ˆ
ˆL
i
ii
i
ii
Ec
cc
E
i
x
xx








, say,
2
2
1
ˆi
Lc
i
i
ii
c
Vx
x






, say,
where i cand 2
i
c

are the estimated means and variances
le. lent deterministic constraint to the sto-
ch
from the samp
Thus, an equiva
astic constraint 2.6 (2) is given by
2
02
11
.
i
LL
c
i
ii
ii
ccK C
xx




 



The equivalent deterministic non-linear programming
problem to the chance constrained programming problem
(2.6) is obtained as
1
2
2
11
min,1,,(1)
Subject to
(2)
11
, 1,...,(3).
2
i
L
jijj
i
LL
c
i
ii
ii
i
i
Vaxj p
cKC
xx
xi L
N





 




 

 
 

 





(3.7)
4. Convex Chebyshev Approximation
Consider p convex smooth functions
Problem



,, ,1,
jjin ,
g
xgx xjp (4.1)
and a region

s




1,,0,1,, ii n
x
xx iq  (4.2)
where i

are also convex smooth functions.
The Convex Chebyshev Approximation Problem (CCAP)
aints (4.2)
co
for minimizing the system (4.1) under Constr
nsists in finding * x

 for which


maxmin max.
x jj
jj
g
xf
Since
x
 (4.3)


max j
i
g
xis convex as can be
Figure 1 below, th
seen from the
e convex Chebyshev approximation
problem is convex.
Corresponding to the points

15
,,xx, we have



 

   

2 23
33 1424 15
, ,
,,
x fx
41 3
max ,
ik
ifxfx f
f
xfx fxfx 

In the general (CCAP) (4.1) & (4.2) we introduce an
auxiliary variable 1n
x

and the auxiliary constraints


1
j
jn
g xxa

, where
j
a are some constants. The pro-
blem (4.3) then is equient to
1
min n Zx


val
11
1
subject to
(, , )0,1,,
and(,,)0,1,,
jj n n
in
ag xxxjp
xx iq








 


(4.4)
5. Solutions Using Chebyshev Approximation
Th functions in 3.7 (1) are linear. The sin-
Technique
e p ob jective
gle coaint 3.7 (2) is convex (see Kokan and Khan [1]).
So (3.7) represents p convex programming problems.
Let us den ote the feasibl e region de fined by 3.7 (2) and (3)
introduce an auxiliary variable 1,1,,
L
nstr
x
jp
.From


.
i
max
i
f
x Figure 1. Convexity of the function

M. F. KHAN ET AL. 250
by s not void. Let us tion procedure. The data used in this example is from a
stratified random sample survey conducted in Varanasi
district of Uttar Pradesh (U.P), India to study the distri-
bution of manurial resources among different crops and
cultural practices (see Sukhatme[9]). Relevant data with
respect to the two characteristics “area under rice” and
“total cultivated area” are given in Table 1. The total num-
ber of villages in the district was 4190.

) to
. Suppose that the feasible region i
(4.1 (4.3) it follo ws that the problem (3.7) is equivalent
to the convex Chabyshev’s approximation problem of
finding * x such that
 
maxin maxjj
jj
aV x
 , (5.1)
where
m
jj x
aVx 
j
a are the weights assigned to the p variances
according to their importance. The problem .1) is then
equivalent to the following problem with a linear objec-
tive function:
(5 In order to demonstrate the procedure the following
are also assumed. The per unit travel costs i
c,


1,, 4i of measurement in various strata are inde-
pendently normally distributed with the following means
and variances


13Ec

, ,

24Ec


3
Ec 5

,


47Ec

and


10.6Vc , ,

20.5Vc 


3
Vc 0.7

,


40.8Vc 
1L
Zx


11
1
2
2
11
(1)
subject to
()or0,1, ,(2)
(3)
11
and,1, ,(4)
2
i
L
jj LjijiL
i
LL
c
i
ii
ii
i
i
aV xxaaxxjp
cKC
xx
xi L
N




















 






(5.2)
The non-linear programming problem in (5.2) is con-
ve
Let us assign the weights to the variances of the two
characters in proportion to the inverse of the sums
44
1
11
and
i
ii
S

2 i
S

 which turn out to be and
10.75a
20.25a

.
The total amount available for the survey is as-
sumed as 600 units including an expected overhead cost
= 100 u ni t s.
C
0
tLet the chance constraint 2.6 (2) be required to be sat-
isfied with 99% probability. Then k

is such that


0.99k

 . The value of standard normal variable
K

corresponding to 99% confidence limits is 2.33. Thus,
the problem (5.2) is obtain ed as:
x as the object ive functi ons in 5. 2 (1) an d the constrai nt
5.2 (2) are linear. Further the left hand side in 5.2 (2) is
convex. So it is possible to solve the convex programming
problem (5.2) by using a ny standard conve x programmi ng
algorithm. The optimal sample numbers thus obtained
may turn out to be fractional. However, it is known that
the variance functions are flat at the optimum solution. So
for large or even moderate sample size it is enough to
round the fractional values to the nearest integers. How-
ever, for small 1
ii
nx the branch and bound method
should be appli ed for fi nding t he optim al integer solut ion.
6. Numerical Illustration
Table 1. Data for four strata and two characteristics.
Stratum ii
N i W 2
1i
S 2
2i
S
1 1419 0.3387 4817.72 130121.15
2 619 0.1477 6251.26 7613.52
3 1253 0.2990 3066.16 1456.40
4 899 0.2146 56207.25 66977.72
The following numerical example demonstrates the solu-


5
12 345
12345
2222
1234 1234
12
min X
Subject to
0.75 552.640136.277274.1142588.3430
0.25 14926.197165.9747130.2023084.3240
3457 0.60.50.70.8
2.33 500
11111
,,
141926192 12
XX XXX
XXXXX
XXXX XXXX
XX

 

 


 34
11 1
,.
532 8992
XX











 

(6.1)
The Chebyshev point by solving the convex programming problem (6.1) is


*0.02159,0.12169,0.10866,0.03882withXX
5119.0883 ch

M. F. KHAN ET AL.251
The values of sample sizes rounded to nearest integers
ar = 46, = 8, = 9 and = 26, with a
to
lu
e 1
n
ar
2
n 3 n
c
4
n
e
tal of 89. Corresponding to this allocation the values of
the viances for the twoharacters arobtained as 1 V
= 159.05, 2 V = 478.32
Remark: We may co mpare these results with the co m-
promise sotion (Cochran [10]) which is obtained by
solving the following NLP problem:

123 4
1234
1234
2222
1234
123
min
552.640136.277274.11
nV

4 2588.343
0.75
14926.197 165.39747 130.2023084.324
0.25
Subject to
3457
2.33 0.60.50.70.8500
2 1419,2619,21253
nnn n
nnnn
nnn n
nnnn
nnn










 4 ,2 899n
The integer solution is obtained as = 44, = 9,
= 10 and = 29 with a total o. The
s
n problem in multivariate strati-
random costs has been formulat
8. References
nd S. Khan, “Optimum Allocation in Mul-
ys: An Analytical Solution,” Journal of the
tio
1
n
f 922
n
valu
oc
Ame
3
n
th
are
4
n es of Computational Statistics and Data Analysis, Vol. 51, No.
6, 2007, pp. 3016-3026.
e individual variances, corresponding to this allation
obtained as1
V = 144.36 and 2 V = 476.90.
7. Conclusion
The optimum allocatio
fied sampling withed as
a problem in multiple linear objectives under the single
probabilistic constraint. An equivalent deterministic mo-
del of the stochastic programming problem is established
by using Chance Constrained programming method. The
problem is then solved by using the Chebyshev appro-
ximation technique. A comparative study of the increases
in the variance using Chebyshev approximation as com-
pared to the compromise allocation is also presented.
[1] A. R. Kokan a
tivariate Surve
Royal Statistical Society. Series B, Vol. 29, No. 1, 1967,
pp. 115-125.
[2] S. Chatterjee, “Multivariate Stratified Surveys,” Journal
of the American Statistical Association, Vol. 63, No. 322,
1968, pp. 530-534.
[3] H. F. Huddlesto, et al., “Optimal Sample Allocation to
Strata Using Convex Programming,” Journal of the Royal
Statistical Society. Series C, Vol. 19, No. 3, 1970, pp.
273-278.
[4] J. Bethel, “An Optimum Allocation Algorithm for Multi-
variate Survey,” Proceeding of the Survey Research Sec-
n, American Statistical Association, 1985, pp. 204-
212.
[5] J. R. Chromy, “Design Optimization with Multiple Ob-
jectives,” Proceeding of the Survey Research Section,
rican Statistical Association, 1987, pp. 194-199.
[6] J. A. Diaz-Garcia and M. M. Garay-Tapia, “Optimum al-
location in Stratified surveys: Stochastic Programming,”
doi:10.1016/j.csda.2006.01.016
[7] S. Javed, Z. H. Bakhshi and M. M. Khalid, “Optimum
allocation in Stratified Sampling with Random Costs,”
International Review of Pure and Applied Mathematics,
Vol. 5, No. 2, 2009, pp. 363-370.
[8] Z. H. Bakhshi, M. F. Khan and Q. S. Ahmad, “Optimal
Sample Numbers in Multivariate Stratified Sampling with
a Probabilistic Cost Constraint,” International Journal of
Mathematics and Applied Statistics, Vol. 1, No. 2, 2010,
pp. 111-120.
[9] P. V. Sukhatme, B. V. Sukhatme, S. Sukhatme and C. Asok,
“Sampling Theory of Survey s with Applications,” 3rd Edi-
tion, Iowa State University Press, Ames, 1984.
[10] W. G. Cochran, “Sampling Technique s,” 3rd Edition, John
Wiley and Sons, New York, 1977.