一类随机优化问题的交互式算法及应用
|
摘要
实际生产和生活中,许多因素具有不确定性,如证券的收益率、消费者对某种商品的需求量及某商品的市场供应量等.用不确定性优化模型刻画管理决策中的优化问题,并设计有效的求解方法在目前运筹学研究中已得到广泛关注.
本文从实际问题中提出了一类多目标随机优化问题,该问题含有一个随机线性和随机二次目标函数,还含有随机线性约束.首先基于决策者的期望水平将多目标优化模型转化为单目标优化问题,提出了新的方差期望综合法.利用方差期望综合法研究了此类优化问题的确定性等价类,并设计了这一问题的基于决策者偏好的交互式算法.经数值实验表明,所提出的交互式算法能够在反映决策者满意度的基础上求出模型的最优解.
其次,在方差期望综合法的基础上提出了一类求解这类多目标随机优化问题的混合方法,同样针对问题中涉及的参数提出了相应的交互式算法,数值实验表明所设计的基于三个参数的交互式算法同样可以在反映决策者满意度的基础上求出模型的最优解.
再次,通过两种比较方法对解决该类多目标随机优化问题的三种方法：期望方法,方差期望综合法和混合方法的优劣性进行了比较.比较方法一是用数值模拟的方法产生随机样本,通过比较样本模型最优解与分别使用三种方法求解模型所得最优解之间的距离来比较三种方法的优劣；比较方法二是用三种方法分别求出样本模型的最优解,通过比较最优解对模型约束条件的约束违反度,来比较三种方法的优劣.经数值实验表明：混合方法优于方差期望综合法,优于期望方法.
最后,分别使用方差期望综合法和混合方法求解证券市场中存在的双目标随机优化问题,验证了所提出的两种方法的实用性.
In the real production and life, there are many uncertain factors, such as the return rate of securities, the consumer's demand for certain products and the market supply capacity of some commodities. In the process of decision-making in the field of management science, it has obtained extensive attention to use uncertainty optimization models to describe the real decision making problems and design effective solution methods in operation research.
A class of stochastic multiple-objective optimization problems with one quadratic and one linear objective functions and several linear constraints have been introduced from the practical problems. We convert multiple-objective optimization problems into a single-objective optimiz-ation problem based on the Decision-Maker's expectation level;The dete-rministic equivalent formulation is obtained by a new approach, called hybrid method of variance and expectation.Then,an interactive algorithm is presented,which can reflect the preference of the Decision-Maker. Numerical experiments show that the proposed interactive algorithm can obtain a robust solution which can reflect the satisfaction degree of Decision-Maker.
Secondly, a class of hybrid method was proposed for solving such a class of stochastic multiple-objective optimization problems based on the variance-expectation method, the interactive algorithm with three parameters was proposed, a corresponding numerical experiments show that the proposed interactive algorithm can obtain a robust solution which can reflect the satisfaction degree of Decision-Maker.
Thirdly, we made some comparisons for the three methods to abtain the deterministic equivalent formulations from the multiple-objective optimization problem by two ways. One way is to compare the distances between the optimal solution of sample models and the optimal solutions of models converted by the three methods. Another way is to compare the degrees of violance of constraints in the model obtaind by the different methods. The numerical experiments verified that:the hybrid method is superior to the variance-expectation method, which is superior to the expectation method.
Lastly, the two proposed methods were used to solve a multiple objective optimization problem that exits in the domain of securities, which verified the practical of the two methods.
本文从实际问题中提出了一类多目标随机优化问题,该问题含有一个随机线性和随机二次目标函数,还含有随机线性约束.首先基于决策者的期望水平将多目标优化模型转化为单目标优化问题,提出了新的方差期望综合法.利用方差期望综合法研究了此类优化问题的确定性等价类,并设计了这一问题的基于决策者偏好的交互式算法.经数值实验表明,所提出的交互式算法能够在反映决策者满意度的基础上求出模型的最优解.
其次,在方差期望综合法的基础上提出了一类求解这类多目标随机优化问题的混合方法,同样针对问题中涉及的参数提出了相应的交互式算法,数值实验表明所设计的基于三个参数的交互式算法同样可以在反映决策者满意度的基础上求出模型的最优解.
再次,通过两种比较方法对解决该类多目标随机优化问题的三种方法：期望方法,方差期望综合法和混合方法的优劣性进行了比较.比较方法一是用数值模拟的方法产生随机样本,通过比较样本模型最优解与分别使用三种方法求解模型所得最优解之间的距离来比较三种方法的优劣；比较方法二是用三种方法分别求出样本模型的最优解,通过比较最优解对模型约束条件的约束违反度,来比较三种方法的优劣.经数值实验表明：混合方法优于方差期望综合法,优于期望方法.
最后,分别使用方差期望综合法和混合方法求解证券市场中存在的双目标随机优化问题,验证了所提出的两种方法的实用性.
In the real production and life, there are many uncertain factors, such as the return rate of securities, the consumer's demand for certain products and the market supply capacity of some commodities. In the process of decision-making in the field of management science, it has obtained extensive attention to use uncertainty optimization models to describe the real decision making problems and design effective solution methods in operation research.
A class of stochastic multiple-objective optimization problems with one quadratic and one linear objective functions and several linear constraints have been introduced from the practical problems. We convert multiple-objective optimization problems into a single-objective optimiz-ation problem based on the Decision-Maker's expectation level;The dete-rministic equivalent formulation is obtained by a new approach, called hybrid method of variance and expectation.Then,an interactive algorithm is presented,which can reflect the preference of the Decision-Maker. Numerical experiments show that the proposed interactive algorithm can obtain a robust solution which can reflect the satisfaction degree of Decision-Maker.
Secondly, a class of hybrid method was proposed for solving such a class of stochastic multiple-objective optimization problems based on the variance-expectation method, the interactive algorithm with three parameters was proposed, a corresponding numerical experiments show that the proposed interactive algorithm can obtain a robust solution which can reflect the satisfaction degree of Decision-Maker.
Thirdly, we made some comparisons for the three methods to abtain the deterministic equivalent formulations from the multiple-objective optimization problem by two ways. One way is to compare the distances between the optimal solution of sample models and the optimal solutions of models converted by the three methods. Another way is to compare the degrees of violance of constraints in the model obtaind by the different methods. The numerical experiments verified that:the hybrid method is superior to the variance-expectation method, which is superior to the expectation method.
Lastly, the two proposed methods were used to solve a multiple objective optimization problem that exits in the domain of securities, which verified the practical of the two methods.
引文
[1]Zadeh L. Fuzzy sets. Information and Control,1965,8(3):338-353
[2]刘宝碇,赵瑞清,王纲.不确定规划及应用.北京：清华大学出版社,2003
[3]Liu B. Theory and Practice of Uncertain Programming. Heidelberg: Physica-Verlag,2002
[4]刘宝碇,赵瑞清.随机规划与模糊规划.北京：清华大学出版社,1998
[5]Liu B. Uncertain programming:A unifying optimization theory in various uncertain environments. Applied Mathematics and Computation,2001,120(1-3): 227～234
[6]Liu B. Uncertainty Theory:An Introduction to Its Axiomatic Foundations. Heidelberg:Springer-Verlag,2004
[7]刘宝碇,彭锦.不确定理论教程.北京：清华大学出版社,2004
[8]Birge J.R, Louveaux F. Introduction to stochastic programming. New York: Springer,1997
[9]Kall P, Wallace S.W, Stochastic Programming. Chichester:Wiley,1994
[10]方述诚,汪定伟.模糊数学与模糊优化.北京：科学出版社,1997
[11]Alefeld G., Herzberger J. Introduction to Interval Computions. New York: Academic Press,1983
[12]Lwamura K, Liu B. Stochastic operation models for open inventory networks. Journal of Information & Optimization Sciences,1999,20(3):347～363
[13]Liu B, Esogbue A.O. Decision criteria and optimal inventory processes. Boston:Kluwer Academic Publishers,1999,57 (6):193～206
[14]Lwamura K, Liu B. Chance constrained integer programming models for capital budgeting in fuzzy environments. Journal of the Operational Research Society,1998,49 (8):854～860
[15]Lwamura K, Liu B. Dependent-Chance integer programming applied to capital budgering. Journal of the Operations Research Society of Japan,1999, 42(2):117～127
[16]Kall P. Stochastic programming:Achievements and open problems. In: Models, Methods and Decision Support for Management:Essays in Honor of Paul Stahly, Heidelberg, New York:Physica-Verlag.2001,285～302
[17]Zhao R., Liu B. Stochastic programming models for general redundancy optimization problems. IEEE Trans-actions on Reliability,2003,52(2):181～191
[18]Peng J, Song K. Fuzzy flow-shop scheduling models based on credibility measure. Proceedings of the IEEE International Conference on Fuzy Systems, 2003,1423～1427
[19]Zhou J, Liu B. New stochastic models for capacitated location-all ocation problem. Computers & Industrial Engineering,2003,45(1):111～125
[20]Beale E. On minimizing a convex function subject to linear inequalities. Journal of the Royal Statistical Society,1955,17(2):173～184
[21]Charnes A, Cooper W. W..Chance-constrained programming, Management Science,1959,6(1):73～79
[22]Charnes A, Cooper W. W.. Management Models and Industrial Applications of Linear Programming. New York:Wiley,1962,4(3):267～268
[23]Charnes A, Cooper W. W..Chance constraints and normal deviates. Journal of the American Statistical Assocition,1962,57(297):134～148
[24]Dantzig G., Linear programming under uncertainty, Management science, 1955,1(3～4):197～206
[25]王金德.随机规划.南京：南京大学出版社,1990
[26]Dempster M.A.H, Stochastic Programming. London:Academic Press, 1980
[27]Kall P. Stochastic linear Programming. Berlin:Springer-Verlag,1976
[28]Mayer J. Stochastic linear Programming Algorithms:A comparison Based on Model Management Systems. London:Gordon and Breach,1998
[29]Prekopa A. Stochastic programming, Dordrecht:Kluwer A cadamic Publishers,1995
[30]Vajda S. Probabilistic Programming. New York:Academic Press,1972
[31]Birge J.R, Louveaux F. Introduction to Stochastic Programming. New York: Springer,1997
[32]VanderVlerk M.H. Stochastic Programming bibliography. Word Wide Web, http://mally. eco. rug. nl/biblio/stoprog. html,1996～2003
[33]VanderVlerk M.H. Stochastic integer Programming bibliography. Word Wide Web, http://mally. eco. rug. nl/biblio/spbib. html,1996～2003
[34]Fabio S, Stochastic techniques for global optimization:A survey of recent advances, Journal of global optimization,1991,1 (3):207～228
[35]Rhode R, Weber R. Multiple objective quadretic-linear programming in:J.P.Brand. OperationalResearch, Notth-Holland, Amesterdam, IFOR,1981,405～ 420
[36]Cunha MDC, Groundwater cleanup the optimization perspective. Eng-inneering Optimization,2002,34(6):689～702
[37]Das A., Datta B. Application of optimization techniques in groundwater quantity and quality management.Sadhana,2001,26(4):293～316
[38]Davorin Kofjac,Miroljub Kljajic, et al. The anticipative concept in ware-house optimization using simulation in an uncertain environment.European Journal of Operatinmal Researchm,2009,193(3):660-669
[39]Mahmoud H, Alrefaei, AmeenJ.Alawneh. Solution quality of random search methods for discrete stochastic optimization.Mathematics and Comuters in Simulation,2005,68(2):115～125
[40]Maria Jose Pardoa, David de la Fuente. Design of a fuzzy finite capacity queuing model based on the degree of customer satisfaction:Analysis and fuzzy optimization. Fuzzy Sets and Systems,2008,159(9):3313～3332
[41]杜丽莉,高兴宝.线性多目标规划的神经网络方法.陕西师范大学学报(自然科学版),2000,28(4)：15～18
[42]王文龙,王晓敏.多目标线性规划的交互式线性加权内点算法.贵州大学学报(自然科学版),2004,21(1)：30～35
[43]邹自德.求多目标线性规划妥协解的旋转迭代算法.运筹与管理,2004,13(1)：68～72
[44]姚升保,彭叶辉,施保昌.线性约束多目标规划的非单调信赖域算法.运筹与管理,2002,11(4)：52～55
[45]彭叶辉,姚升保,施保昌.线性约束多目标规划的非单调信赖域算法.华中科技大学学报(自然科学版),2003,31(7)：113～114
[46]宋海洲.基于相对目标接近度的多目标决策方法及其应用.数学的实践与认识,2004,34(5)：30～35
[47]袁松琴,李泽民.线性等式约束多目标规划的一个降维算法.运筹学报,2005,9(1)：70～74
[48]刘旺梅,韩旭里.一种求解多目标规划的新方法.系统工程与电子技术,2001,23(8)：15～17
[49]罗罡辉,叶艳妹.多目标规划的LNDO求解方法.计算机应用与软件,2004,21(2)：108～110
[50]Jiang C, Han X. A nonlinear interval number programming method for uncertain optimization problems.European Journal of Operational Research,2008,188 (1):1～13
[51]J P.Xu, J.Li. A class of stochastic optimization problems with one quadratic several linear objective functions and extended protfolio section model. Journal of Computational and Applied Mathematics,2002,146(1):99～113
[52]Ling.W, Liang.Z. Stochatic optimization using simulated annealing with hypothesis test. Applied Mathematics and Computation,2006,174(22):1329～1342
[53]施宝昌等,多目标规划的一类基于精确罚函数的交互式方法.系统科学与数学,1999,19(1)：106～110
[54]Mahmoud H.Alrefaei,Ameen J.Alawneh. Solution quality of random search methods for discrete stochastic optimization. Mathematics and Computers in Simulation,2005,68(2):115～125
[55]Korhonen P, Laasko J. A visual interactive method for solving the multiple criteria problem. European K.Oper.Res,1996,24(2):277-287
[56]X.S.Qin, G..H.Huang. An inexact chance-constrained quadratic program-ming model for stream water quality managemeng. Water Resour Manage,2009,23(4): 661～695
[57]戎小霞.不确定优化问题的若干模型与算法研究：[硕士学位论文].济南：山东大学,2005
[58]姜林.多目标以及多目标分式规划的最有性条件：[硕士学位论文].重庆：重庆大学,2007
[59]高雷阜.最优化理论与方法.沈阳：东北大学出版社,2005
[60]魏权龄,闫洪.广义最优化理论和模型.北京：科学出版社,2003
[61]魏权龄,胡显佑.运筹学基础教程.北京：中国人民大学出版社,2008
[62]申培萍.全局优化方法.北京：科学出版社,2006
[63]王晓陵,陆军.最优化方法与最优控制.哈尔滨：哈尔滨工程大学出版社,2007
[64]夏少刚.运筹学经济优化方法与模型.北京：清华大学出版社,2005
[65]孙麟平.运筹学.北京：科学出版社,2005
[66]卢险峰.最优化方法应用基础.广州：同济大学出版社,2003
[67]J.K.Wu, J.Z, Q.W, Y.L. Fuzzy random chance-constrained progamming for quantifying transmission reliability margin. Lecture Notes in Computer Science,2006, 4223:1020～1024
[68]Z.Wan, S.J.Zhang,Y.L.Wang. Penalty algorithm based on conjugate gradient method for solving portfolio management problem. Journal of inequalities and applications,2009
[2]刘宝碇,赵瑞清,王纲.不确定规划及应用.北京：清华大学出版社,2003
[3]Liu B. Theory and Practice of Uncertain Programming. Heidelberg: Physica-Verlag,2002
[4]刘宝碇,赵瑞清.随机规划与模糊规划.北京：清华大学出版社,1998
[5]Liu B. Uncertain programming:A unifying optimization theory in various uncertain environments. Applied Mathematics and Computation,2001,120(1-3): 227～234
[6]Liu B. Uncertainty Theory:An Introduction to Its Axiomatic Foundations. Heidelberg:Springer-Verlag,2004
[7]刘宝碇,彭锦.不确定理论教程.北京：清华大学出版社,2004
[8]Birge J.R, Louveaux F. Introduction to stochastic programming. New York: Springer,1997
[9]Kall P, Wallace S.W, Stochastic Programming. Chichester:Wiley,1994
[10]方述诚,汪定伟.模糊数学与模糊优化.北京：科学出版社,1997
[11]Alefeld G., Herzberger J. Introduction to Interval Computions. New York: Academic Press,1983
[12]Lwamura K, Liu B. Stochastic operation models for open inventory networks. Journal of Information & Optimization Sciences,1999,20(3):347～363
[13]Liu B, Esogbue A.O. Decision criteria and optimal inventory processes. Boston:Kluwer Academic Publishers,1999,57 (6):193～206
[14]Lwamura K, Liu B. Chance constrained integer programming models for capital budgeting in fuzzy environments. Journal of the Operational Research Society,1998,49 (8):854～860
[15]Lwamura K, Liu B. Dependent-Chance integer programming applied to capital budgering. Journal of the Operations Research Society of Japan,1999, 42(2):117～127
[16]Kall P. Stochastic programming:Achievements and open problems. In: Models, Methods and Decision Support for Management:Essays in Honor of Paul Stahly, Heidelberg, New York:Physica-Verlag.2001,285～302
[17]Zhao R., Liu B. Stochastic programming models for general redundancy optimization problems. IEEE Trans-actions on Reliability,2003,52(2):181～191
[18]Peng J, Song K. Fuzzy flow-shop scheduling models based on credibility measure. Proceedings of the IEEE International Conference on Fuzy Systems, 2003,1423～1427
[19]Zhou J, Liu B. New stochastic models for capacitated location-all ocation problem. Computers & Industrial Engineering,2003,45(1):111～125
[20]Beale E. On minimizing a convex function subject to linear inequalities. Journal of the Royal Statistical Society,1955,17(2):173～184
[21]Charnes A, Cooper W. W..Chance-constrained programming, Management Science,1959,6(1):73～79
[22]Charnes A, Cooper W. W.. Management Models and Industrial Applications of Linear Programming. New York:Wiley,1962,4(3):267～268
[23]Charnes A, Cooper W. W..Chance constraints and normal deviates. Journal of the American Statistical Assocition,1962,57(297):134～148
[24]Dantzig G., Linear programming under uncertainty, Management science, 1955,1(3～4):197～206
[25]王金德.随机规划.南京：南京大学出版社,1990
[26]Dempster M.A.H, Stochastic Programming. London:Academic Press, 1980
[27]Kall P. Stochastic linear Programming. Berlin:Springer-Verlag,1976
[28]Mayer J. Stochastic linear Programming Algorithms:A comparison Based on Model Management Systems. London:Gordon and Breach,1998
[29]Prekopa A. Stochastic programming, Dordrecht:Kluwer A cadamic Publishers,1995
[30]Vajda S. Probabilistic Programming. New York:Academic Press,1972
[31]Birge J.R, Louveaux F. Introduction to Stochastic Programming. New York: Springer,1997
[32]VanderVlerk M.H. Stochastic Programming bibliography. Word Wide Web, http://mally. eco. rug. nl/biblio/stoprog. html,1996～2003
[33]VanderVlerk M.H. Stochastic integer Programming bibliography. Word Wide Web, http://mally. eco. rug. nl/biblio/spbib. html,1996～2003
[34]Fabio S, Stochastic techniques for global optimization:A survey of recent advances, Journal of global optimization,1991,1 (3):207～228
[35]Rhode R, Weber R. Multiple objective quadretic-linear programming in:J.P.Brand. OperationalResearch, Notth-Holland, Amesterdam, IFOR,1981,405～ 420
[36]Cunha MDC, Groundwater cleanup the optimization perspective. Eng-inneering Optimization,2002,34(6):689～702
[37]Das A., Datta B. Application of optimization techniques in groundwater quantity and quality management.Sadhana,2001,26(4):293～316
[38]Davorin Kofjac,Miroljub Kljajic, et al. The anticipative concept in ware-house optimization using simulation in an uncertain environment.European Journal of Operatinmal Researchm,2009,193(3):660-669
[39]Mahmoud H, Alrefaei, AmeenJ.Alawneh. Solution quality of random search methods for discrete stochastic optimization.Mathematics and Comuters in Simulation,2005,68(2):115～125
[40]Maria Jose Pardoa, David de la Fuente. Design of a fuzzy finite capacity queuing model based on the degree of customer satisfaction:Analysis and fuzzy optimization. Fuzzy Sets and Systems,2008,159(9):3313～3332
[41]杜丽莉,高兴宝.线性多目标规划的神经网络方法.陕西师范大学学报(自然科学版),2000,28(4)：15～18
[42]王文龙,王晓敏.多目标线性规划的交互式线性加权内点算法.贵州大学学报(自然科学版),2004,21(1)：30～35
[43]邹自德.求多目标线性规划妥协解的旋转迭代算法.运筹与管理,2004,13(1)：68～72
[44]姚升保,彭叶辉,施保昌.线性约束多目标规划的非单调信赖域算法.运筹与管理,2002,11(4)：52～55
[45]彭叶辉,姚升保,施保昌.线性约束多目标规划的非单调信赖域算法.华中科技大学学报(自然科学版),2003,31(7)：113～114
[46]宋海洲.基于相对目标接近度的多目标决策方法及其应用.数学的实践与认识,2004,34(5)：30～35
[47]袁松琴,李泽民.线性等式约束多目标规划的一个降维算法.运筹学报,2005,9(1)：70～74
[48]刘旺梅,韩旭里.一种求解多目标规划的新方法.系统工程与电子技术,2001,23(8)：15～17
[49]罗罡辉,叶艳妹.多目标规划的LNDO求解方法.计算机应用与软件,2004,21(2)：108～110
[50]Jiang C, Han X. A nonlinear interval number programming method for uncertain optimization problems.European Journal of Operational Research,2008,188 (1):1～13
[51]J P.Xu, J.Li. A class of stochastic optimization problems with one quadratic several linear objective functions and extended protfolio section model. Journal of Computational and Applied Mathematics,2002,146(1):99～113
[52]Ling.W, Liang.Z. Stochatic optimization using simulated annealing with hypothesis test. Applied Mathematics and Computation,2006,174(22):1329～1342
[53]施宝昌等,多目标规划的一类基于精确罚函数的交互式方法.系统科学与数学,1999,19(1)：106～110
[54]Mahmoud H.Alrefaei,Ameen J.Alawneh. Solution quality of random search methods for discrete stochastic optimization. Mathematics and Computers in Simulation,2005,68(2):115～125
[55]Korhonen P, Laasko J. A visual interactive method for solving the multiple criteria problem. European K.Oper.Res,1996,24(2):277-287
[56]X.S.Qin, G..H.Huang. An inexact chance-constrained quadratic program-ming model for stream water quality managemeng. Water Resour Manage,2009,23(4): 661～695
[57]戎小霞.不确定优化问题的若干模型与算法研究：[硕士学位论文].济南：山东大学,2005
[58]姜林.多目标以及多目标分式规划的最有性条件：[硕士学位论文].重庆：重庆大学,2007
[59]高雷阜.最优化理论与方法.沈阳：东北大学出版社,2005
[60]魏权龄,闫洪.广义最优化理论和模型.北京：科学出版社,2003
[61]魏权龄,胡显佑.运筹学基础教程.北京：中国人民大学出版社,2008
[62]申培萍.全局优化方法.北京：科学出版社,2006
[63]王晓陵,陆军.最优化方法与最优控制.哈尔滨：哈尔滨工程大学出版社,2007
[64]夏少刚.运筹学经济优化方法与模型.北京：清华大学出版社,2005
[65]孙麟平.运筹学.北京：科学出版社,2005
[66]卢险峰.最优化方法应用基础.广州：同济大学出版社,2003
[67]J.K.Wu, J.Z, Q.W, Y.L. Fuzzy random chance-constrained progamming for quantifying transmission reliability margin. Lecture Notes in Computer Science,2006, 4223:1020～1024
[68]Z.Wan, S.J.Zhang,Y.L.Wang. Penalty algorithm based on conjugate gradient method for solving portfolio management problem. Journal of inequalities and applications,2009