基于分支定界算法的三层决策模型与应用研究
|
摘要
多跟随者三层决策建立在具有层级关系的组织中,上层是领导者,下层是追随者,其执行顺序是从顶层到底层。不同层级的每个决策实体都有独自的决策目标,但目标的实现又是相互关联的,每个决策实体也考虑其它层级决策实体的决策。这样的决策存在于国家政策的制定、科学技术的运用、企业管理和日常生活等多个方面。优化多层决策、探索多层决策算法、实现多层决策应用逐渐成为决策研究的热点内容。
本文从三个方面进行研究：首先介绍多层决策的模型,详细讲解多层规划理论知识；然后给出Kuhn-Tucker条件的三个定理,由二层分支定界算法引出三层分支定界算法,用两个数值案例详细说明Kuhn-Tucker条件的转化过程和分支定界算法流程；并基于此算法开发出三层决策支持系统,可以快速有效的解决多层规划决策问题；最后给出三层决策的实际应用,结合某化工企业的销售-生产-采购的实际情况建立了三层决策数学模型,将此模型运用到三层决策支持系统中,可以快速求出最优解决方案,帮助企业优化资源配置和产业结构,降低生产和采购成本,给企业带来更大利润,为决策者提供科学的决策依据。
Multi-follower Tri-level decision is established in the hierarchical organization. It implements from the top level to the bottom. The top level is leader, and the bottom level is follower. Different levels of decision making entities have their own decision-making targets, but the realization of them is relevant to each other, so they should concern about each other when making the decisions. National policy formulation, science and technology application, business management and daily life are all filled with such decisions. Optimizing the hierarchical form decision-making, exploring Multi-follower Tri-level decision algorithm, and the realizing of hierarchical form decision-making application have became the hot area for researchers.
There are three aspects of this study:firstly, a multilevel decision model is given, the basic theory of multilevel programming is explained. Then a tri-level branch and bound algorithm is illustrated based on the bi-level algorithm, and detailed description of two numerical examples of process for branch and bound algorithm under the Kuhn-Tucker condition are given. A tri-level decision support system is developed based on the algorithm, which can effectively solve the multi-level decision system. Finally, the practical application of three level application of decision making is given. A tri-level programming model of sales-production-stock is established by combining the situation in a chemical enterprise. The optimal solution is quickly obtained by using the model in the tri-level decision support system. The solution can help the enterprises to optimize resource allocation and industrial structure, to reduce the production and procurement costs. All these provide a scientific decision making method for the decision maker in the enterprise.
本文从三个方面进行研究：首先介绍多层决策的模型,详细讲解多层规划理论知识；然后给出Kuhn-Tucker条件的三个定理,由二层分支定界算法引出三层分支定界算法,用两个数值案例详细说明Kuhn-Tucker条件的转化过程和分支定界算法流程；并基于此算法开发出三层决策支持系统,可以快速有效的解决多层规划决策问题；最后给出三层决策的实际应用,结合某化工企业的销售-生产-采购的实际情况建立了三层决策数学模型,将此模型运用到三层决策支持系统中,可以快速求出最优解决方案,帮助企业优化资源配置和产业结构,降低生产和采购成本,给企业带来更大利润,为决策者提供科学的决策依据。
Multi-follower Tri-level decision is established in the hierarchical organization. It implements from the top level to the bottom. The top level is leader, and the bottom level is follower. Different levels of decision making entities have their own decision-making targets, but the realization of them is relevant to each other, so they should concern about each other when making the decisions. National policy formulation, science and technology application, business management and daily life are all filled with such decisions. Optimizing the hierarchical form decision-making, exploring Multi-follower Tri-level decision algorithm, and the realizing of hierarchical form decision-making application have became the hot area for researchers.
There are three aspects of this study:firstly, a multilevel decision model is given, the basic theory of multilevel programming is explained. Then a tri-level branch and bound algorithm is illustrated based on the bi-level algorithm, and detailed description of two numerical examples of process for branch and bound algorithm under the Kuhn-Tucker condition are given. A tri-level decision support system is developed based on the algorithm, which can effectively solve the multi-level decision system. Finally, the practical application of three level application of decision making is given. A tri-level programming model of sales-production-stock is established by combining the situation in a chemical enterprise. The optimal solution is quickly obtained by using the model in the tri-level decision support system. The solution can help the enterprises to optimize resource allocation and industrial structure, to reduce the production and procurement costs. All these provide a scientific decision making method for the decision maker in the enterprise.
引文
[1]盛昭瀚.主从递阶决策论[M].科学出版社,1998.
[2]Amat J, McCarl B. A representation and economic interpretation of a two-level programming problem[J]. Operational Research Society,1981,32:783-792.
[3]Amouzegar MA, Moshirvaziri K. Strategic management decision support system:An analysis of the environmental policy issues[J]. Environmental Modeling and Assessment, 2001,6:297-306.
[4]Cao D, Chen M. Capacitated plant selection in a decentralized manufacturing environment:A Bi-Level optimization approach[J]. European Operational Research, 2006,169:97-110.
[5]Feng C, Wen C. Bi-Level and multi-objective model to control traffic flow into the disaster area post earthquake[J]. Eastern Asia Society for Transportation Studies,2005,6: 4253-4268.
[6]Hobbs BF, Metzler B, Pang JS. Strategic gaming analysis for electric power system:An mpec approach[J]. IEEE Transactions on Power System,2000,15:637-645.
[7]H.V. Stackelberg. Theory of the Market Economy[M]. New York:Oxford University Press,1952.
[8]Bracken, McGill. Convex Analysis[M]. princeton University PRESS,1962.
[9]Candler W.R., Norton. Multilevel programming[M]. World Bank Development Research Center,1977.
[10]G. Anandalingam, T. Friesz. Hierarchical optimization:an introduction[J]. Annals of Operations Research 1992,34 1-11.
[11]W. Bialas, M. Karwan. Two-level linear programming[J]. Management Science,1984,30: 1004-1020.
[12]Bard, Falk. An explicit solution to the multi-level programming problem[J]. Computer and Operations Research,1982,977-100.
[13]J. Bard, J. Falk. Necessary conditions for the linear three-level programming problem[J]. Proceedings of the 21st IEEE Conference on Decision andControl,1982,21:642-646.
[14]Y.J. Lai. Hierarchical optimization:a satisfactory solution[J]. Fuzzy Sets and Systems 1996,77:321-335.
[15]S. Sinha, S.B. Sinha. KKT transformation approach for multi-objective multi-level linear programming problems[J]. European Journal of Operational Research 2002,143 19-31.
[16]M.A. Abo-Sinna, I.A. Baky. Interactive balanced space approach for solving multi-level multi-objective programming problems[J]. Information Sciences,2007,177 (16): 3397-3140. [17] X. Shi, H. Xia. Interactive bilevel multi-objective decision making[J]. Operational Research Society,1997,48:943-949.[18] 夏洪胜,潘伟.一类两层决策问题的模型及迭代决策方法[J].系统工程与电子技术,1994，5：50-56.
[19]夏洪胜.基于置换率和满意度的两层多目标决策问题的交互式算法研究[D].东南大学,1992.
[20]夏洪胜,王浣尘.一种多人有关联两层多目标决策的交互式算法[J].上海交通大学学报,1994,28(2)：90-97.
[21]夏洪胜,郜林春,贺建勋.两层决策问题的全局优化方法[J].海南大学学报(自然科学版),1994,12(2)：108-113.
[22]阮国祯,左晓波.线性多级规划的最优性条件和基本性质[J].系统科学与数学,1998.
[23]刘红英.多层规划的理论与算法研究[D].西安电子科技大学,2000.
[24]刘红英,刘三阳.带上层约束的两层线性规划[J].应用数学,1999,12(1)：106-109.
[25]刘红英,刘三阳.下层以最优值反应上层的两层线性规划[J].运筹学报,2001,5(3)：63-70.
[26]杨若黎,顾基发.一类非线性双层线性规划问题的模拟退火算法求解[J].系统工程理论与实践,1997,8(7)：52-58.
[27]刘国山.双层优化问题的信赖域算法[J].科学通报,1998,43(4)：383-387.
[28]腾春贤,李智慧.二层规划的理论与应用[M].北京：科学出版社,2002.
[29]王先甲,冯尚友.二层系统最优化理论[M].北京：科学出版社,1995.
[30]王广民,万仲平,王先甲.二(双)层规划综述[J].数学进展,2007,36(5).
[31]张美芳,成央金,邓胜岳.一种线性三层规划的改进的Frank-Wolf解法[J].湖南工业大学学报,2009,23(1).
[32]W.F.Bialas, M.N.Chew. On two-level programming[J]. IEEE transactions on automatic control,1982,26:211-214.
[33]W.F.Bialas, M.H.Karwan. Two-level linear programming[J]. Management Science,1983, 30:1004-1020.
[34]W.Candle, R.Townsley. A linear two-level programming problem[J]. Computers and Operations Research,1982,9:59-76.
[35]Guangquan Zhang, Jie Lu. Model, solution concept, and Kth-best algorithm for linear trilevel programming[J]. Information Sciences,2010,180:481-492.
[36]Anandalingam, White.D.JG. Asolution method for the stackelberg problem using penalty funtions[J]. IEEE Transactions on Automatic Control,1990,35(10):1170-1173.
[37]Bard.JF. An Investigation of the Linear Three Level Programming[J]. IEEE Translations Research,1990,38(5):911-921.
[38]Y.J. Lai. Hierarchical optimization:a satisfactory solution[J]. Fuzzy Sets and Systems, 1996,77:321-325.
[39]Bard.J.F, Falk.J.E. An explidt solution to the bilevel programming problem[J]. Computers and Operations Research,1982,9:77-100.
[40]吕一兵.关于线性二层规划分枝定界方法的探讨[J].运筹与管理,2006,15(5).
[41]沈厚才,徐南荣,仲伟俊.一类含0-1变量的目标两层决策方法研究[J].东南大学学报,1995,25(6)：125-130.
[42]H.S. Shih, Y.J. Lai, E.S. Lee. Fuzzy approach for multi-level mathematical programming problems[J]. Computers and Operational Research 1996,23:73-91.
[43]裴峥,黄天民.二层线性规划的模糊数学解法[J].西南交通大学学报,2000,35：98-101.
[44]Masatoshi Sakawa, Ichiro Nishizaki. Interactive fuzzy programming for two-level linear fractional programming problems[J]. Fuzzy Sets and Systems,2001,119(1):31-40.
[45]H.I. Calvete, C. Gale, P.M. Mateo. A new approach for solving linear bilevel problems using genetic algorithms[J]. European Journal of Operational Research,2008,188: 14-28.
[46]Liu B.D. Stackelberg-Nash equilibrium for mutilevel programming with multiple followers using genetic algorithm[J]. ComputMathApp,1998,36(7):79-89.
[47]赵茂先,高自友.求解线性双层规划问题的割平面法[J].北京交通大学学报,2005,29(3)：65-69.
[48]仲伟俊,徐南荣.两层决策的波尔兹曼机方法[J].系统工程学报,1995,10(1)：7-13.
[49]Bialas W F, Karwan M H, Shaw J. Aparametric complementary pivot approach for two level linear programming[M].1980.
[50]Cohen M A, Lee H L. Strategic analysis of integrate productio[J] Operations Research, 1988,36(2):216-228.
[51]BrownG G, Graves G W, Honczarenko M D. Design and operation Of multicommodity production distrucbution system using primal goal decomposition[J]. Managememnt Science,1987,33(11):1469-1479.
[52]Gerchak Y, Wang Y. Coordination in decentralized assembly systems with random demand[M]. Working paper,1999.
[53]Klastorin T D, Kamran Moinzadeh, Joong Son. Coordinating orders in supply chains through price discounts[J].34,2002,8(679-689).
[54]丁立.多阶供应链中的响应周期优化研究[D].合肥工业大学,2007.
[55]胡耀光,范玉顺,王田苗.基于二层规划模型的统一采购方法研究[J].中国机械工程,2007,18(1)：52.
[56]Tyagi, Rajeev K. On the effects of downstream entry[J]. Management Sciences,1999, 45(1):59-73.
[57]Gupta D, W.Weerawat. Supplier manufacturer coordination in capacitated two stage supply chains[J]. European Journal of Operational Research,2006,175:67-89.
[58]田厚平.二层规划若干理论及其在供应链中的应用研究[D].东北大学,2004.
[59]李应,杨善林.供应链分布式多层协同生产-分销计划模型与求解[J].中国机械工程,2008,19(21)：52-55.
[2]Amat J, McCarl B. A representation and economic interpretation of a two-level programming problem[J]. Operational Research Society,1981,32:783-792.
[3]Amouzegar MA, Moshirvaziri K. Strategic management decision support system:An analysis of the environmental policy issues[J]. Environmental Modeling and Assessment, 2001,6:297-306.
[4]Cao D, Chen M. Capacitated plant selection in a decentralized manufacturing environment:A Bi-Level optimization approach[J]. European Operational Research, 2006,169:97-110.
[5]Feng C, Wen C. Bi-Level and multi-objective model to control traffic flow into the disaster area post earthquake[J]. Eastern Asia Society for Transportation Studies,2005,6: 4253-4268.
[6]Hobbs BF, Metzler B, Pang JS. Strategic gaming analysis for electric power system:An mpec approach[J]. IEEE Transactions on Power System,2000,15:637-645.
[7]H.V. Stackelberg. Theory of the Market Economy[M]. New York:Oxford University Press,1952.
[8]Bracken, McGill. Convex Analysis[M]. princeton University PRESS,1962.
[9]Candler W.R., Norton. Multilevel programming[M]. World Bank Development Research Center,1977.
[10]G. Anandalingam, T. Friesz. Hierarchical optimization:an introduction[J]. Annals of Operations Research 1992,34 1-11.
[11]W. Bialas, M. Karwan. Two-level linear programming[J]. Management Science,1984,30: 1004-1020.
[12]Bard, Falk. An explicit solution to the multi-level programming problem[J]. Computer and Operations Research,1982,977-100.
[13]J. Bard, J. Falk. Necessary conditions for the linear three-level programming problem[J]. Proceedings of the 21st IEEE Conference on Decision andControl,1982,21:642-646.
[14]Y.J. Lai. Hierarchical optimization:a satisfactory solution[J]. Fuzzy Sets and Systems 1996,77:321-335.
[15]S. Sinha, S.B. Sinha. KKT transformation approach for multi-objective multi-level linear programming problems[J]. European Journal of Operational Research 2002,143 19-31.
[16]M.A. Abo-Sinna, I.A. Baky. Interactive balanced space approach for solving multi-level multi-objective programming problems[J]. Information Sciences,2007,177 (16): 3397-3140. [17] X. Shi, H. Xia. Interactive bilevel multi-objective decision making[J]. Operational Research Society,1997,48:943-949.[18] 夏洪胜,潘伟.一类两层决策问题的模型及迭代决策方法[J].系统工程与电子技术,1994，5：50-56.
[19]夏洪胜.基于置换率和满意度的两层多目标决策问题的交互式算法研究[D].东南大学,1992.
[20]夏洪胜,王浣尘.一种多人有关联两层多目标决策的交互式算法[J].上海交通大学学报,1994,28(2)：90-97.
[21]夏洪胜,郜林春,贺建勋.两层决策问题的全局优化方法[J].海南大学学报(自然科学版),1994,12(2)：108-113.
[22]阮国祯,左晓波.线性多级规划的最优性条件和基本性质[J].系统科学与数学,1998.
[23]刘红英.多层规划的理论与算法研究[D].西安电子科技大学,2000.
[24]刘红英,刘三阳.带上层约束的两层线性规划[J].应用数学,1999,12(1)：106-109.
[25]刘红英,刘三阳.下层以最优值反应上层的两层线性规划[J].运筹学报,2001,5(3)：63-70.
[26]杨若黎,顾基发.一类非线性双层线性规划问题的模拟退火算法求解[J].系统工程理论与实践,1997,8(7)：52-58.
[27]刘国山.双层优化问题的信赖域算法[J].科学通报,1998,43(4)：383-387.
[28]腾春贤,李智慧.二层规划的理论与应用[M].北京：科学出版社,2002.
[29]王先甲,冯尚友.二层系统最优化理论[M].北京：科学出版社,1995.
[30]王广民,万仲平,王先甲.二(双)层规划综述[J].数学进展,2007,36(5).
[31]张美芳,成央金,邓胜岳.一种线性三层规划的改进的Frank-Wolf解法[J].湖南工业大学学报,2009,23(1).
[32]W.F.Bialas, M.N.Chew. On two-level programming[J]. IEEE transactions on automatic control,1982,26:211-214.
[33]W.F.Bialas, M.H.Karwan. Two-level linear programming[J]. Management Science,1983, 30:1004-1020.
[34]W.Candle, R.Townsley. A linear two-level programming problem[J]. Computers and Operations Research,1982,9:59-76.
[35]Guangquan Zhang, Jie Lu. Model, solution concept, and Kth-best algorithm for linear trilevel programming[J]. Information Sciences,2010,180:481-492.
[36]Anandalingam, White.D.JG. Asolution method for the stackelberg problem using penalty funtions[J]. IEEE Transactions on Automatic Control,1990,35(10):1170-1173.
[37]Bard.JF. An Investigation of the Linear Three Level Programming[J]. IEEE Translations Research,1990,38(5):911-921.
[38]Y.J. Lai. Hierarchical optimization:a satisfactory solution[J]. Fuzzy Sets and Systems, 1996,77:321-325.
[39]Bard.J.F, Falk.J.E. An explidt solution to the bilevel programming problem[J]. Computers and Operations Research,1982,9:77-100.
[40]吕一兵.关于线性二层规划分枝定界方法的探讨[J].运筹与管理,2006,15(5).
[41]沈厚才,徐南荣,仲伟俊.一类含0-1变量的目标两层决策方法研究[J].东南大学学报,1995,25(6)：125-130.
[42]H.S. Shih, Y.J. Lai, E.S. Lee. Fuzzy approach for multi-level mathematical programming problems[J]. Computers and Operational Research 1996,23:73-91.
[43]裴峥,黄天民.二层线性规划的模糊数学解法[J].西南交通大学学报,2000,35：98-101.
[44]Masatoshi Sakawa, Ichiro Nishizaki. Interactive fuzzy programming for two-level linear fractional programming problems[J]. Fuzzy Sets and Systems,2001,119(1):31-40.
[45]H.I. Calvete, C. Gale, P.M. Mateo. A new approach for solving linear bilevel problems using genetic algorithms[J]. European Journal of Operational Research,2008,188: 14-28.
[46]Liu B.D. Stackelberg-Nash equilibrium for mutilevel programming with multiple followers using genetic algorithm[J]. ComputMathApp,1998,36(7):79-89.
[47]赵茂先,高自友.求解线性双层规划问题的割平面法[J].北京交通大学学报,2005,29(3)：65-69.
[48]仲伟俊,徐南荣.两层决策的波尔兹曼机方法[J].系统工程学报,1995,10(1)：7-13.
[49]Bialas W F, Karwan M H, Shaw J. Aparametric complementary pivot approach for two level linear programming[M].1980.
[50]Cohen M A, Lee H L. Strategic analysis of integrate productio[J] Operations Research, 1988,36(2):216-228.
[51]BrownG G, Graves G W, Honczarenko M D. Design and operation Of multicommodity production distrucbution system using primal goal decomposition[J]. Managememnt Science,1987,33(11):1469-1479.
[52]Gerchak Y, Wang Y. Coordination in decentralized assembly systems with random demand[M]. Working paper,1999.
[53]Klastorin T D, Kamran Moinzadeh, Joong Son. Coordinating orders in supply chains through price discounts[J].34,2002,8(679-689).
[54]丁立.多阶供应链中的响应周期优化研究[D].合肥工业大学,2007.
[55]胡耀光,范玉顺,王田苗.基于二层规划模型的统一采购方法研究[J].中国机械工程,2007,18(1)：52.
[56]Tyagi, Rajeev K. On the effects of downstream entry[J]. Management Sciences,1999, 45(1):59-73.
[57]Gupta D, W.Weerawat. Supplier manufacturer coordination in capacitated two stage supply chains[J]. European Journal of Operational Research,2006,175:67-89.
[58]田厚平.二层规划若干理论及其在供应链中的应用研究[D].东北大学,2004.
[59]李应,杨善林.供应链分布式多层协同生产-分销计划模型与求解[J].中国机械工程,2008,19(21)：52-55.