American Journal of Computational Mathematics, 2011, 1, 247251 doi:10.4236/ajcm.2011.14029 Published Online December 2011 (http://www.SciRP.org/journal/ajcm) Copyright © 2011 SciRes. 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 Email: *faisalkhan004@yahoo.com 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 nonlinear 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 DiazGa rcia [6]. Javai d and Bakhs hi [7] applied m odifi ed Em 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 ,,, NN N such that 1 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,, .iLth j ,p1,Yj j. denoted by , 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 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 , will also be nor mally distri b uted with mean as 11 1 , LL ii L ii i i ii i cEc E 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: (3.2) where 2 ii Vc . Now let 1 Li ii c fc , where then {2.6 (2)} is given by 1,, , n cc c 0,fc Cp P or 0, fcEfcCEfc Pp Vfc Vfc cEfc Vfc where is a standard normal variable with mean zero and variance one. Thus the probability of realizing 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 represents the value of the standard normal variable which at 0 p , then the constraint (3.3) can be writ Copyright © 2011 SciRes. AJCM
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 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 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 xx , say, 2 2 1 ˆi Lc i i ii c Vx , 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 nonlinear 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 , xgx xjp (4.1) and a region s 1,,0,1,, ii n 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 xf Since x (4.3) max j i 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 xfx fxfx In the general (CCAP) (4.1) & (4.2) we introduce an auxiliary variable 1n and the auxiliary constraints 1 jn g xxa , where 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 jp .From . i max i x Figure 1. Convexity of the function Copyright © 2011 SciRes. AJCM
M. F. KHAN ET AL. Copyright © 2011 SciRes. AJCM 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 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 nonlinear 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 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. 30163026. 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. 115125. [2] S. Chatterjee, “Multivariate Stratified Surveys,” Journal of the American Statistical Association, Vol. 63, No. 322, 1968, pp. 530534. [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. 273278. [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. 194199. [6] J. A. DiazGarcia and M. M. GarayTapia, “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. 363370. [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. 111120. [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. Copyright © 2011 SciRes. AJCM
