第10章 双层规划.ppt

第第1010章章双双层层规规划划BiLevel Programming层次性是系统的六大特征之一。社会---不断发展,实际问题---规模越来越大,结构越来越复杂,进行决策的人也越来越多,而且这些决策者各自处于不同的层次上。一般,高一级决策机构(者)对下一级决策机构(者)行使某种控制、引导权,而下一级决策机构(者)在这一前提下,亦可以在其管理职责范围内行使一定的决策权,但这种决策权处于从属地位。,在这种多层次决策系统中,每一级都有自身的目标函数。高层机构的决策目标:重要、权威、具有全局性。最终的决策结果往往是寻求使各层决策机构之间达到某种协调的具体方案。“最优”,也可使作为上级决策“约束”的较低层决策机构的目标在从属位置上相应达到“最优”。一般称具有以上基本特征的决策问题为主从递阶(或多层)决策问题。主从递阶决策问题最初是由Von ,是一对策论问题,决策者有上下层关系和不同目标,但策略集通常是彼此分离。20世纪60年代,Dantzig和Wolfe提出了大规模线性规划的分解算法,相当于承认有一个核心决策者,他的目标高于一切,其他各层次的决策者实现自己的目标只不过是为实现核心决策者的目标的一种分工。现在的多层规划承认有最高决策者,但允许下层决策者有各自不同的利益。20世纪70年代发展起来的多目标规划通常是寻求一个决策者的互相矛盾的多个目标的折衷解,有些技术,如分层优化,也可用来求层次问题,但下层决策不影响上层,可以逐层独立求解。而当前的多层规划正是要强调下层决策对上层目标的影响,因此多层规划问题通常不能逐层独立求解。20世纪70年代以来,人们在各种现实的层次分散系统优化决策问题的研究中,遇到了用上述方法不能解决的实际问题,开始寻找各种特定的方法解决这些问题,逐渐形成了多层规划的概念和方法。如:Cassidy(1971)的政府政策效力分析,Kyland(1975)的经济层次分析,Bracken (1973-1977)等人的战备武器配置研究,Candler和 Norton(1977)的奶制品工业模型和墨西哥农业模型等。多层规划(Multilevel Programming)一词就是Candler和 Norton在其论文中提出的,它的原意是一组嵌套着的数学规划问题,即在约束条件中含有优化问题的数学规划。20世纪80年代至今,多层规划的数学模型更加明确和形式化了,国内外学者也发表了许多有意义的成果。总之,在过去20年中,多层规划的理论、方法及应用都有很大发展,正在逐渐形成一个新的运筹学分支。目前,很多国家对多层规划的研究都非常重视,把它列为科学基金资助项目,并取得了巨大成功。最为常见且得到广泛研究与应用的多层规划是双层规划问题,即考虑只有两层决策者的情形。这是因为现实的决策系统大都可以看成双层决策。例如:中央和地方,公司和子公司,工厂的厂部和车间,高校的校部和院所等。实际上任何多层决策系统都是一系列双层决策系统的复合。