系统工程优化决策理论及其发展战略

来源:中国系统工程学会时间:2020-10-13

摘要:系统工程是一门综合性的技术学科,本文分别从单人优化决策和多人优化决策的角度出发,介绍了系统工程涉及到的优化与决策方法,包括最优化理论、决策理论、博弈论等多种理论方法,综述了每种理论方法研究问题的特征、基本的结论以及发展过程,并对系统工程中使用到的优化与决策理论的发展趋势进行说明,为解决系统工程问题使用到的优化与决策理论方法的研究与应用提供一定的参考。
关键词:系统工程;优化理论;决策理论;博弈论

 

1 引言

1.1 系统工程

系统工程是一门集技术、科学、组织和管理于一体的学科,是一类综合性的整体技术、一种综合集成的技术、一门整体优化的定量技术,它体现了从整体上研究和解决问题的技术方法。
   
我国近代的系统工程学科建设可以追溯到20世纪50年代。1956年,中国科学院在钱学森、许国志教授的创导下,建立了第一个运筹学小组。20世纪60年代,著名数学家华罗庚教授大力推广了统筹法、优选法。钱学森、许国志、王寿云教授于1978年9月27日在《文汇报》上发表了《组织管理的技术——系统工程》,标志着系统工程学科在中国的兴起。1980年中国系统工程学会成立,并在北京举行了中国系统工程学会成立大会暨第一届系统工程学术年会,为促进系统工程和系统科学的研究和应用起到了重要作用,近年来,系统工程在各个领域都取得了许多成果。

1.2 系统工程与优化决策理论的关系

系统工程是组织管理系统的一种综合技术,根据钱学森教授等人的观点,系统工程是组织管理系统的规划、研究、设计、制造、试验和使用的科学方法,是一种对所有系统都具有普遍意义的科学方法,它根据系统总体的目标要求,从系统整体出发,运用综合集成方法把与系统有关的科学理论方法与技术集成起来,对系统的结构、环境和功能进行总体分析、总体论证、总体设计和总体协调,其中包括对系统建模、仿真、分析、优化、设计与评估,以达到可行的、满意的或者最好的系统配置方案并付诸实施。

如何对具体的系统工程问题进行描述、分析与求解,则属于研究系统工程问题的方法论,虽然系统工程作为一门学科成立于20世纪中叶,但是利用优化和决策方法解决系统工程问题则可追溯到公元前,早在公元前500年的春秋时期,就有著名的军事家孙武写出了“孙子兵法”十三篇,指出战争中的战略和策略问题,在公元前250年开始兴建的都江堰,同样是优化决策方法运用到水利工程建设的成功实例,由于实际系统的不同,使用哪种方法和理论来研究系统工程问题,还需要关注于与系统相关的科学理论方法与技术,钱学森教授于1978年就指出,系统工程中用到的数学方法可以概括为一门技术科学学科,叫运筹学,包括线性规划、非线性规划、博弈论、排队论、库存论、决策论等,但是系统工程的理论不能只是一门运筹学,还有其他,需要看系统工程的具体对象,各门系统工程专业都有它各自的理论或者技术基础;但一方面,不论哪一门系统工程又共同地以运筹学为他们的数学方法,说明他们处理问题的基本精神是一致的,又有他们的共性。

优化与决策理论是解决各种涉及实际工程、经济和社会中出现的系统工程问题的重要数学方法之一,当然在部分复杂问题中还涉及到控制论与信息论等理论工具,一个系统可以认为是决策单元的集合,这些决策单元从整体出发考虑达成某种目标,并提供相应的达成目标的过程,处在直接改造客观世界的工程技术层次上的是系统工程,处在为工程技术直接提供理论基础的技术科学层次上由控制论、运筹学、信息论,处在以基础科学为基础,进一步抽象概括成为认识、揭示客观事物规律的基本理论的基础科学层次上的是系统学,而系统科学是以系统作为研究和应用对象的科学技术体系,优化与决策理论为一般系统以及具有不确定性系统的分析提供了必要的数学方法,针对于系统的分析侧重于对系统整体性能的客观判断,采用决策方法进行分析则需要客观判断的同时还需要注意对系统本身的价值以及偏好的分析,这是研究系统工程问题和决策问题在分析方式上的区别。

决策理论是社会科学和自然科学的交叉学科,其中,自然科学研究的是客观的世界,使用的方法以定量为主,其研究成果具有可重复性和客观性的衡量标准,而社会科学主要研究的是由人组成的社会,包括人以及人际关系,其核心在于关于价值的判断,主要的研究成果难以用客观的标准进行衡量,而决策理论的目标是要使用定量的方法研究价值,即对社会科学采用定量化的研究方法,进而辅助决策者进行决策判断。

本文通过研究问题的基本特征来介绍系统工程问题涉及到的决策和优化方法,介绍系统工程问题涉及到的决策和优化理论的发展过程、经典结论和基本的研究方向等,并对未来可能的研究方向进行说明。

2 系统工程中的优化与决策理论

笛卡尔(Rene Descartes,1596-1650)在1637年他发表的最有名的著作《正确思维和发现科学真理的方法论》(通常简称为《方法论》)中指出,分类是使得研究对象条理化的方法,可以将要研究的复杂问题,尽量分解为多个比较简单的小问题;一个一个地分开解决,这里我们依据笛卡尔的观点,对为系统工程技术直接提供理论基础的优化与决策理论进行分类总结,

依据系统工程中涉及到的决策者的数量,把研究系统工程问题中使用到的优化与决策方法分为单人优化与决策方法和多人优化与决策方法两类,并分别对这两类方法以及发展动向进行系统性讨论。

2.1 单人优化与决策方法

2.1.1单目标优化与决策方法

单目标决策问题是指具有一个决策目标的决策问题。单人单目标决策问题按照决策成员决策变量的属性一般分为两类,第一类是最优化问题,第二类是组合优化问题。第一类单目标决策问题中,决策成员的决策变量具有连续性,而第二类单目标决策问题中,决策成员的决策变量具有离散性,这里主要讨论的是第一类单人单目标决策问题,即最优化问题。

最优化问题有时也称为数学规划问题,包括线性、非线性规划两类,非线性规划问题按照是否存在约束条件又分为有约束非线性规划问题以及无约束非线性规划问题两类。

2.1.1.1线性规划问题

线性规划(linear programming,简写为LP)是解决优化问题最常使用的方法。1947年,George Dantzig发明了一种有效的方法,单纯形法,来解决线性规划问题,自从单纯形法出现以来,线性规划已被用于解决银行、林业、石油和污染等多个行业中出现的系统工程问题,在一项财富500强企业的调查中,85%的受访者表示他们使用过线性规划方法,  一个线性规划问题是具有如下特征的优化问题:
1)我们试图最大化(或最小化)一个具有决策变量的线性函数,要最大化或最小化的函数称为目标函数。
2)决策变量的取值必须满足一组约束,每个约束必须是一个线性方程或线性不等式。
3)每个变量都有一个符号限制,即对于任何变量,符号限制规定变量必须是非负的或不受限制的,

线性规划的目标函数必须是决策变量的线性函数这一事实有两个含义:
1)目标函数中的每个决策变量的贡献与决策变量的取值成正比。
2)任何决策变量对目标函数的贡献与其他决策变量的取值无关。

类似地,每个线性规划约束必须是一个线性不等式或线性方程这一事实有两个含义:
1)每个决策变量对每个约束左边的贡献与变量的取值成比例。
2)决策变量对每个约束左边的贡献与其他决策变量的取值无关。

每个列表中给出的第一个含义称为线性规划的比例假设,第一个列表中的第二个含义意味着目标函数的价值是各个变量贡献的总和,第二个列表中的第二个含义意味着每个约束的左边是每个变量贡献的总和,由于这个原因,每个列表中的第二个含义称为线性规划的可加性假设。
 
为了使线性规划适当地表示实际情况,决策变量必须满足比例性和可加性假设,另外两个假设也必须得到满足,这样才能使用线性规划解决实际问题,这两个额外的假设为可分性和确定性假设。
 
可分性假设要求允许每个决策变量可以取实数值,特别地,一个线性规划问题的一些或所有的变量为非负整数时,该线性规划问题称为整数规划问题,确定性假设是每个参数(目标函数的系数、约束条件左边项系数)都是确定的。
 
与线性规划问题相关的两个最基本的概念是可行域和最优解,线性规划的可行域是满足所有线性规划约束和符号约束的所有点的集合,对于一个最大化问题,线性规划的最优解是是可行域中使得目标函数值最大的点,对于极小化问题,最优解是可行域中使得目标函数值最小的点。

在工业生产以及制造行业中,许多线性规划问题产生于决策者希望最小化生或者制造成本,以满足一系列的要求的问题中,下面列举部分线性规划问题的应用。

食品的营养学问题:在食品的营养学问题中,Stigler于1945年提出了一个饮食问题,其中有77种食物可供选择,10种营养需求必须得到满足。Balintfy于1973指出,营养学问题中关于实物的配置问题实际上就是一个数学规划问题。2003年发表的《营养和健康科学中的数学模型》一书专门介绍了食品科学中使用到的数学规划模型。
   
工作安排问题:1980年,Krajewski等使用线性规划来安排美国俄亥俄国家银行处理支票职员的工作时间问题。
 
资本预算分配问题:Weingartner于1966年就开始使用整数规划等数学方法来研究资本预算决策问题Maier和Vander Weide则在Weingartner的基础上更进一步,于1976年使用线性规划算法研究分权公司的资本预算设计与协调问题。

线性规划作为优化理论中最为基础、方法较成熟的一个重要分支,其研究成果直接推动了整数规划、非线性规划等数学规划问题算法的研究。研究其它类型的数学规划方法时,时常对目标函数以及约束条件左边项函数进行线性假设,进而取得初步的研究成果,例如二层规划中首先以线性二层规划为研究对象,模糊规划中对模糊线性规划进行研究等,这种在新的规划问题中套用线性规划的形式成为研究新的优化问题的一种基本方法。

2 .1.1.2非线性规划问题

在许多的最大化和最小化问题中,目标函数可能不是线性函数,或者某些约束可能不是线性约束,这样的最优化问题称为非线性规划问题(nonlinear programming,简记为NLP)。

一个一般的非线性规划问题(NLP)可以表述为如下形式:

与线性规划的形式相同,f (X1,X2,…,Xn)为非线性规划问题的目标函数,g1(XI,X2,…,Xn)(≤=≥)b1,…,gm(XI,X2,…,Xn)(≤=≥)bm为非线性规划问题的约束条件,没有约束条件的非线性规划问题称为无约束非线性规划问题,存在约束条件的非线性规划问题称为有约束非线性规划问题。
   
同样,类似于线性规划问题,非线性规划问题同样有可行域和最优解的基本概念,非线性规划问题的可行域为满足所有m个约束条件的点的集合,在可行域中使得目标函数最大的点称为非线性规划问题的最优解。
 
依据线性规划与非线性规划的基本形式可知,先性规划问题的可行域为一个凸集,如果线性规划问题有最优解,那么可行域的极值点是最优的,但是对于非线性规划问题来说,即使非线性规划问题的可行域是一个凸集,最优解不一定是非线性规划问题可行域的极值点,在极大值问题中,只有当非线性规划问题的可行域为凸集并且目标函数满足凹性时,局部的极大值点才是最值点;在极小值问题中,只有当非线性规划问题的可行域为凸集并且目标函数满足凸性时,局部的极小值点才是最值点。

求解无约束非线性规划问题的方法为基本的微分理论,求解有约束非线性规划问题所依据的是Lagrange乘子法和K uhn- Tucker定理。

Lagrange乘子法可以被用来解决所有约束条件为等式约束的非线性规划问题,通过引入新的与约束条件对应的m个参数(称为Lagrange乘子),将约束条件与目标函数联系起来构造一个新的函数,称为La-grange函数,通过求解Lagrange函数的最值点进而得到约束条件为等式约束的非线性规划问题的最优解。Lagrange乘子法不同于运用约束条件等式使用代入法和消元法求解无约束规划问题,当约束条件等式是一个复杂的函数时,即使知道变量之间为一个隐函数并且使得隐函数定理的条件得以满足,实际上也很难应用消元法,此时Lagrange乘子法的优势就可以体现出来。

Kuhn-Tucker定理则适用于一般形式的有约束非线性规划问题。Kuhn- Tucker定理给出了一般形式下的有约束非线性规划问题的最优解满足的必要条件,只有满足特定的条件,Kuhn-Tucker定理才是必要条件,这个条件称为约束规范(例如Mangasarian-Fromovitz条件)。约束规范是对非线性规划中的约束函数施加的某些限制,目的是为了排除可行域边界上的满足某些不规则性的点,这些不规则性可能会违背能够产生最优解的Kuhn-Tucker条件,例如岐点是最常引起的使得Kuhn- Tucker条件失效的原因,但事实上岐点的出现既不是Kuhn-Tucker条件失效的必要条件,也不是充分条件,为了得到有约束非线性规划问题的最优解的充分条件,甚至是充要条件,需要对目标函数以及约束条件左侧函数进行进一步假设,例如,在目标函数为凹函数和约束条件左侧函数为凸函数并且这两类函数二阶连续可微时,满足Kuhn-Tucker极大化条件的点是原极大化非线性规划问题的极大值点,此时我们称该极大化问题为凹规划问题。

为了应用Kuhn-Tucker充分性定理,必须满足某些凹凸性条件,对目标函数和约束条件左边函数施加凹凸性的假设是非常严格的,为此,Arrow和Enthoven弱化了凹凸性的要求,于1961年提出了Arrow-Enthoven充分性定理,它只要求目标函数和约束条件左边函数具有拟凹性和拟凸性,这使得充分条件的应用范围进一步扩大。

除了从理论上得到优化问题最优解满足的条件以外,还有使用迭代的思想逐步趋近于最优解的方法。
   
求解无约束规划问题的迭代算法包括:下降法、最速下降法、Newton法、拟Newton法、共轭梯度法、信赖域法等。

求解有约束规划问题的迭代算法包括:增广目标法(包括罚函数法和乘子法等)、可行方向法、序列二次规划(SQP)算法、信赖域序列二次规划法等。
 
对于非线性规划的研究,从理论上来说集中于研究最优性条件上。应用非线性规划理论解决实际问题时,更偏向于设计迭代算法来求解最优解,最优性条件的形式和算法的构造成为研究非线性规划问题的重点,对于非线性规划问题的研究同样为研究其他特殊形式的优化问题提供了一定的基础和思路。

2.1.2多目标优化决策理论

由于实际系统工程问题的复杂性,决策者需要同时决策多个目标,并在多个目标之间进行权衡,例如水利工程问题中,水电站在选址时会综合考虑蓄水位、投资分配、发电量分配、防洪等多个方面的目标,总的来说,多目标问题具有如下的特征:
1)决策问题的目标多于一个。
2)决策问题的目标之间不可公度(non-commensurable);即各目标之间没有一个统一的计量单位或者衡量标准,难以进行比较。
3)决策问题的各目标之间存在矛盾。
   
由于多目标决策问题存在上述三个特征,因此不能把多目标简单地化为单目标,相比于单目标的求解方法,求解多目标决策问题的方法有所不同。
   
多目标优化问题可以认为是一个特殊的单目标优化问题,特殊性体现在决策者的决策变量空间不是一个完全序上,我们把目标优化问题看成是一个向量优化问题时,单目标优化问题中的决策者需要决策的变量向量为一维,因此可在决策变量空间中进行比较;多目标优化问题中的决策者需要决策的变量向量为多维向量,受到多目标优化问题的第三个特征的影响,始终存在部分可行点无法在多维空间中之间进行比较排序。
   
多目标规划问题中解的概念称为非劣解或者Pareto最优解,它可以认为是在可行的向量空间中不存在严格好于该点的一种解的形式,这是由于多目标优化问题的第三个特征决定的,与单目标优化问题最优解的本质区别在于,多目标规划问题的解并非唯一,而是存在一组由众多Pareto最优解组成的最优解集合,一般称为是Pareto前沿。
   
同样,类似于单目标优化问题最优解的K uhn- Tucker条件。向量优化问题同样存在对应的Kuhn-Tucker条件,其中的区别在于用多个目标函数的梯度的线性组合取代了单目标优化问题K uhn- Tucker条件中的目标函数的梯度,虽然Kuhn-Tucker条件具有类似性,仍然需要生成具体地非劣解。
   
目前生成多目标优化问题非劣解的常用方法包括数学规划方法和进化算法两类,其中,使用传统的数学规划方法生成多目标优化问题的Pareto前沿上的非劣解,常用的方法包括。
   
1)加权法,即对多目标优化问题的目标函数赋予一定的权重并进行求和,进而以加权的目标函数替代多目标优化问题的目标函数,使用Kuhn-Tucker条件来保证加权后的单目标规划问题的最优解是原多目标规划问题的非劣解。

2)ϵ约束法,即选择某个目标并对约束条件左侧函数大于对应的£参数,这个单目标优化问题的解在一定条件下是原来多目标优化问题的非劣解,这一条件可以通过Kuhn-Tucker条件推出。
 
使用进化算法生成多目标优化问题的Pareto前沿上的非劣解的核心思想是从一组随机生成的点集(称为种群)出发,通过对其执行选择、交叉和变异等演化操作,使得种群的适应度不断增加,从而逐步逼近多目标优化问题的Pareto最优解,依据更新规则、个体选择等方面的不同,常用的遗传算法包括。

1) SPEA、SPEA-II算法,称为(改善的)强度帕累托进化算法。SPEA算法通过聚类分析对非劣解集进行修剪,剔除多于的解,利用二元锦标赛的方式选择个体进入下一代。SPEA-II算法则是在SPEA算法的基础上在适应度赋值、个体密度值计算方法和外部档案集合维护三个方面进行改进。
2) NSGA、NSGA-II算法,称为(带精英策略的)非劣排序遗传算法。NSGA算法采用的非劣排序的方式对种群进行分层,引入了基于拥挤策略的小生境(NIChe)技术,即通过适应度共享函数的方法对原先指定的虚拟适应度值进行重新指定,保证在选择操作下等级较低的非支配个体有更多的机会被选择进入下一代,进而使得算法以最快的速度收敛到Pareto前沿。NSGA-II算法则在NSGA算法的基础上提出了快速非劣排序法,提出拥挤度和拥挤度比较算子在快速排序后的同级比较中作为胜出标准,代替了需要指定共享半径的适应度共享策略,引入精英策略,扩大采样空间,进而防止最佳个体的丢失,提高了算法的运算速度和鲁棒性。
  
目前设计进化算法求解多目标优化问题的方法取得了大量成果,并被广泛运用工程、工业等多种系统工程领域。
   
多目标优化问题由于其本身目标存在的矛盾性以及不可公度性,使得其最优解与单目标优化问题的最优解在形式上存在很大差异,把多目标转化为单目标是求解多目标优化问题的主要思想,对最优解的“合理性”设定和由目标的“轻重”程度为基础设计算法是多目标规划在理论上研究的主要方向。

2.1.3随机决策理论

随机决策理论研究不确定条件下的决策问题,决策人必须确定如何收集相关的信息,以及如何依据所收集到的信息做出相应的决策,系统工程问题中,决策者当面临不确定信息时,可以使用随机决策理论辅助进行决策。

随机决策具有的特征:
1)决策人面临选择时,可以采取的备选方案(行动)不唯一。
2)自然状态存在不确定性。
3)结果的价值不确定,

自然状态的不确定性是决策问题的基本特点,由于自然状态的不确定性,决策者在进行决策时其结果受到自然状态的影响,决策者进行决策之前,还需要使用两个基本工具对随机决策问题在自然状态以及结果价值上的不确定性进行定量化描述,这两个工具为概率论和效用理论,概率是定量表达不确定性的重要工具,可以使用概率论对设定自然状态的概率分布所涉及的问题进行处理和分析,而效用理论是定量化结果价值的工具,偏好是准确判断结果对决策者的实际价值的描述方式,而效用是偏好的量化表现形式,因此,效用理论可以描述结果不确定时决策者对结果的选择。

依据自然状态的不确定性特征,当随机决策问题的前期工作准备完成时,决策者需要按照一定的准则进行决策,按照决策者对自然状态以及结果的不确定性,决策准则分为两类,严格不确定型决策和风险型决策。

严格不确定型决策中,决策人无法确切知道真实的自然状态,只知道有哪些自然状态可能会出现,但是无法以任意形式量化这种不确定性,即不知道每种自然状态出现的概率。

严格不确定型决策问题的四种主要决策准则包括:悲观准则、乐观准则、后悔值极大极小准则和等概率准则,这四种准则反映了决策者对自然状态不确定性引起的结果价值的不确定性的一种处理方式。

风险型决策中,决策人无法确切知道真实的自然状态,但他不仅知道那些自然状态可能会出现,而且知道每种可能出现的自然状态的概率。

风险型决策问题的主要决策准则包括:最大可能值准则、贝叶斯准则、伯努利准则、E-V准则、不完全信息下的决策决策准则和优势原则与随机决策准则。

随机决策涉及到概率更新、效用、偏好以及评价等多个方向的内容,其基本思想在于把状态、结果的不确定性转化为可供决策的部分确定性信息和结果,决策准则的设定以及对采取决策准则的“合理性”的公理化分析方法是随机决策问题的重要研究方向。

2.1.4组合优化决策理论

组合优化问题是最优化理论的一类,最优化问题中,决策者具有离散性的决策空间的优化问题认为是组合优化问题,组合优化问题涉及到排序、分类、筛选等问题。

系统工程中的人员管理、资源调度、工程施工设计等方面都可能使用组合优化理论,组合优化问题包括旅行商问题、生产调度问题、0-1背包问题、装箱问题、图着色问题、聚类问题、匹配问题等等,涉及到图论、匹配、整数规划等优化理论。

组合优化问题的目标是从组合问题的可行解中求出最优解,组合优化问题描述起来简单,但是最优化求解很困难,其主要原因是求解组合优化问题的算法需要很长的时间或者需要很大的存储空间。

2.1.4.1图优化理论

图优化的实质是形式为图的一个优化问题,通过由点和边组成的图形来描述具有某种二元关系的系统,并依据图的性质进行分析,提供研究各种系统的分析方法,一个图由顶点和边构成,图上的优化问题主要研究图中的路径问题、匹配问题、遍历问题、着色问题和网络流问题等。

求解图优化问题的算法源自于图论中关于各种图问题的基本算法。对图论的研究是解决具有一定网络结构特征的系统工程问题的基础,随着实际问题的复杂程度的不断增加,设计相应的算法解决复杂网络上的优化问题是图优化理论发展的重要方向之一。

2.1.4.2匹配理论

不同于图优化问题中的匹配问题,一般意义上的匹配问题不仅仅包括图优化理论研究的图上的匹配问题,还包括依据决策者之间的序关系决定决策者之间的关联关系的一类优化问题,研究决策者之间关联关系的稳定性等特征。具有代表性的问题为研究大学录取、劳动力市场招聘等匹配问题。

关于匹配问题的研究主要集中于两类匹配市场问题:单边匹配市场问题和双边匹配市场问题,单边匹配市场是指经济主体在市场上对不可分离的商品进行交换或分配。一般是以房屋分配为例,并称这类问题为房屋市场问题,在其它方面也有重要的应用,如器官移植、医疗资源的分配等。房屋市场问题最早由Shapley和Scarf于1974年提出。对于双边匹配市场中的匹配问题的研究起源于1962年Gale和Shapley的著名论文《大学录取和婚姻的稳定性》,文中给出了最优稳定匹配的定义,并且利用给出的延迟接受(Gale-Shapley)算法,证明了稳定匹配的存在性,这些开创性的研究为匹配理论的后续发展奠定了基础。Gale-Shapley算法已成为求解双边匹配市场中的匹配问题而获得稳定的匹配的基本方法。2012年诺贝尔经济学奖颁发给Roth和Shapley,以表彰他们对在稳定配置理论及市场设计实践上所做出的贡献。Shapley对匹配理论的贡献在于研究了稳定匹配的性质以及求解方法。Roth的贡献在于发现Shapley的理论在一些重要市场中的运作方式,将这些研究成果运用于实验,并帮助重新设计了现有的诸多匹配机制。

对于匹配问题的研究,从理论上说,主要集中于各种满足各种特性下的匹配机制的形式以及稳定性分析上。匹配机制满足的特性包括个体理性、Pareto有效性、防策略操作性、单调性、匿名性等,由于实际问题的复杂性不断增加,应用匹配理论解决实际问题对匹配机制中的算法也提出了更高的要求,设计满足一定特性的匹配机制,并保证相应的算法的时间复杂性为多项式时间是匹配理论在应用上的主要研究方向之一。

2.1.4.3整数规划

整数规划是一部分或者全部决策变量为整数的最优化问题,系统工程中涉及到经济、管理、交通、通信和工业工程中的部分最优化问题可以建模为一个整数规划问题。

绝大多数的组合优化问题可以使用整数规划模型来表示,例如背包问题、指派问题、旅行售货员问题(TSP)等都可以统称为线性混合整数规划问题,最大割问题、投资组合等属于非线性混合整数规划问题。

求解整数规划的一般方法包括:
1)割平面法,它适用于求解全整数规划问题,其基本思想是在松弛问题中通过单纯形法求解线性规划问题,如果的得到的解为整数解,则它也是原整数规划问题的最优解,若得到的解不是整数解,则在原整数规划基础上增加适当的线性不等式约束,然后继续解这个新的整数规划,直至求得最优整数解为止。

2)枚举法,它是求解混合整数规划问题的方法,其中分支定界法是一种基本的枚举法,分支定界法的关键是“分支”和“定界”,若松弛问题的最优解不符合整数约束,则依据不符合约束的变量构造两个约束,将其并入松弛问题中,继续求解两个问题,直到获得整数规划问题的最优解为止,这就是所谓的“分支”,而“定界”是在分支过程中,部分获得整数解的后续问题满足整数约束条件,其目标函数值可以作为一个衡量处理其他分支下优化问题的一个依据,其目的在于减少最优解的求解范围。

求解整数规划问题的难点在于,一方面,绝大部分的整数规划问题是NP-难问题,因此不可能对一般类型的整数规划有很有效的算法,另一方面,在整数规划涉及到的关于整数点集和整数变量函数的理论(例如格理论)在数学上缺乏有效的理论分析工具,特别是定义在整数点集上的凸分析理论的发展较慢,给出最优解满足的必要条件的可计算的方法较困难,整数规划算法的有效性与每类整数规划问题的特征密切相关,应该利用每类问题的独特性质来设计相应的算法。

组合优化是一类特殊的整数规划问题,具有整数规划的形式但很难使用一套普适的整数规划方法进行求解,组合优化问题涉及排序、分类、筛选等问题,其难点和重点内容都集中于针对特定的组合优化问题设计合适的算法,使得算法的收敛速度达到一定的指标。

2.1.5鲁棒优化

“鲁棒性”是一个系统在内部结构和外部环境发生变化时,仍然保持系统功能的能力,是工程技术、自然环境、社会等多方面广泛存在的一种系统功能性质。

不确定性是系统的基本属性之一,在系统工程学科中,对于不确定性的分析主要依据概率分布的统计或者预测结果,但在实际中很难准确预测到不确定因素的概率分布信息,此时,在进行随机决策时,其结果将面临很大扰动。

鲁棒优化起源于Wald于1950年提出的悲观决策准则的思想,即要求决策者依据每种决策方案的最坏结果来进行决策,鲁棒优化是解决内部结构(参数)和外部环境(随机扰动)存在不确定因素时的优化方法,优化问题的内部结构存在不确定因素时,不确定性体现在约束条件或者目标函数的参数的不确定情形上,优化问题的外部环境存在不确定因素时,主要体现在存在不确定性的扰动,在鲁棒优化的目的使得最优解具有鲁棒性,此时,鲁棒对应,即对应于原不确定性问题的鲁棒问题,是一个半无限规划问题,因此,鲁棒对应的可行解与最优解与鲁棒优化的可行解与最优解相对应,通过研究鲁棒优化问题的鲁棒对应来分析鲁棒优化问题是一种研究鲁棒优化问题的基本方法。

相比于随机决策方法,鲁棒优化方法具有如下特点:1)决策者只需要关注于不确定参数的边界,而无需关注与其精确的概率分布。2)鲁棒优化可以转化为一个确定的等价模型进行求解。3)鲁棒优化的解具有一定的保守性,即针对不确定性参数引发的最坏结果进行决策。

到目前为止,鲁棒优化的研究已从最初的具有线性规划形式的鲁棒优化问题发展到具有二次规划、半定规划等形式的鲁棒优化问题,并且还发展到研究离散优化形式的鲁棒优化问题,对部分存在不确定因素影响组合优化问题提供了分析工具。

分析无法准确估计的不确定因素对决策的影响是鲁棒优化问题研究重点。鲁棒优化的算法还停留在寻找近似的鲁棒对应来处理优化问题,类似于最优化问题的基本算法,设计求解一般优化问题的鲁棒对应是鲁棒优化理论需要进一步需要深入和研究的问题,同时,决策者在决策时同样可能受到其他决策者的影响,并且可能对其他决策者的特征存在不准确的估计。因此,把鲁棒性推广到对策问题(博弈问题)中,同样是可以深入研究的方向。除此之外,在如何描述现存系统的鲁棒性以及如何保持其鲁棒性从而增强系统的抗冲击能力方面,鲁棒优化方法具有广阔的研究前景,在特定的应用研究中怎样正确描述系统的鲁棒性,并利用相对简单的计算方法解决实际问题,是鲁棒优化方法在实践应用中面临的主要挑战。

2.2 多人优化决策理论

大到国家级的经济、政治问题,小到个人的生活问题,决策者在面临决策时都会以自身为中心进行决策,然而决策的结果可能受到该问题中涉及到的其他决策者或者行动者的影响,此时,多人的优化和决策理论为决策者进行决策时提供了一定的理论依据。

2.2.1博弈论

博弈论主要研究两个或者两个以上利益相关的决策者进行决策时的策略选择问题,与优化理论的主要区别在于:优化理论研究的问题中,决策者进行决策时不会考虑该决策对其他决策者的影响,而博弈论研究的问题中,决策者进行决策时会考虑其他决策者对其的影响,博弈论以单人优化决策理论为基础,推广了优化和决策理论,但博弈论对解的理解和信息的理解较优化和决策理论有较大区别,博弈论的解的更加关注于效用的合理预期、互为最有反应和选择的稳定性上,博弈的参与者对信息的理解主要是:不仅有自然的不确定性,还有关于信息的不完全性和非对称性。

博弈论又称为对策论,按照其表达方式分为三类,第一类为标准型,第二类为扩展型,第三类为特征函数型。

标准型的博弈问题称为静态博弈问题,静态博弈问题中,参与者在做出行动时不知道其他参与者的行动,扩展型的博弈问题称为动态博弈问题,动态博弈问题中,参与者在做出行动之前可以观测到其他参与者的行动,这里的“静态”和“动态”主要体现在参与者的行动时序以及观测到的其他参与者的行动信息上,两者缺一不可,例如,静态博弈中参与者的行动可以是非同时选择的,但是不能观测到其他参与者的行动,静态博弈和动态博弈统称为非合作博弈。

博弈的共同知识是完全信息博弈理论的基本假设,具体而言,完全信息下,参与者知道谁在进行博弈,每个参与者可能采取的行动以及结果与支付的关系,并且关于这个博弈的共同知识自身同样也是共同知识的。

共同知识假设下的博弈环境在实际的系统工程涉及到的政治、经济以及生活问题中很少遇到。20世纪60年代中期,Harsanvi在处理不完全信息下的博弈问题时认识到,基于参与者行动上的信念和基于他的其他特征之上的信念之间,存在着一定的相似性。他使用一种称为“Harsanvi转换”的技术,引入一个虚拟的参与者“自然”,并首先行动,它决定每个参与者的类型特征,每个参与者知道自己的类型特征,但不知道其他参与者的类型,这种方法把不完全信息博弈问题转换为不完美信息博弈问题,从而可以用分析完全信息博弈的方法进行分析。

不完全信息博弈可以分为不完全信息静态博弈和不完全信息动态博弈,不完全信息静态博弈是指参与者在同时博弈时至少存在一个参与者不完全了解另一个参与者的类型,即不知道某一参与者的真实类型,但是知道每种可能出现的类型以及相应的概率,不完全信息动态博弈是指参与者的行动有先后顺序,且后行动的参与者能够观察到先行动的参与者所选择的行动;每个参与者对其他所有参与者的类型、策略空间及支付函数没有准确的认识,可以认为是不知道先行动的参与者的具体位置,不完全信息博弈理论自从其建立以来广泛运用于各类经济和经济问题,拍卖、机制设计等问题都涉及到不完全信息情形下参与者之间策略的选择。

特征函数型的博弈问题称为合作博弈问题。合作博弈与静态、动态博弈的区别在于博弈的参与者之间是否存在一个具有约束力的协议,如果没有此种协议,参与者之间完全按照自身对其他参与者行为的最优反应进行行动,而如果存在一个具有约束力的协议,参与者按照协议进行行动,因此,参与者之间存在具有约束力的协议时,可以认为参与者之间“合作”进行博弈。

博弈问题的解的构造是博弈论研究的主要内容。

在非合作博弈问题中,理性的参与者会按照其他行动的最优反应进行行动,当所有参与者都采取最优反应时,是否会存在一个稳定的策略组合使得其中任意参与者的行动是其他所有参与者行为的最优反应。Nash于20世纪50年代初给出了答案,他通过不动点定理证明了这种稳定的策略组合的存在性,这种稳定的策略组合称为Nash均衡,Nash均衡是非合作博弈的最重要的解概念,它可以解释为参与者之间形成了一种无法通过改变自身策略来提高自身收益的一种策略组合状态,以Nash均衡为基础,Selten提出了子博弈精炼纳什均衡的概念,用以描述完全信息下动态博弈的解。Harsanyi则在不完全信息下扩展了Nash均衡的概念。这三位学者于1994年被授予诺贝尔经济学奖,用以表彰他们在非合作博弈的均衡分析理论方面做出了开创性的贡献,以及对博弈论和经济学产生了的重大影响。

在合作博弈问题中,由于参与者之间签订了具有约束力的协议,可以认为签订协议的参与者之间按照协议进行行动,一个协议达成的条件是每个参与者的收益得到满足,因此合作博弈问题主要涉及到的是如何分配合作收益的理论,针对合作收益分配的“公平性”的不同理解,因此出现了不同的解概念。Nash于1951年提出,可以把合作行动看成是由参与者之间的某种讨价还价过程的结果,他建立了Nash讨价还价理论并使用公理化方法确定了满足一定数量的“公平性”分配规则对应的唯一分配解的形式。合作博弈的概念首次出现于1944年Von Neumann和Morgenstern的著作《博弈论与经济行为》。Gillies与Shapley分别提出了合作博弈问题中的最重要的两个解的概念,分别是核和Shapley值。合作博弈理论的重要突破以及后来的发展很大程度上源自于Gillies对于核的刻画和Shapley用公理化方法刻画并提出的Shapley值的概念,使用公理化方法来刻画分配的公平性成为了研究合作博弈理论的基本方法,但是公理化方法有太一般化、要求完全信息、公理的合理性难以检验和不能反映协商的动态过程等缺点,总的来说,限于特征函数及其分配解的概念,合作博弈发展很缓慢,合作博弈理论经过几十年的发展得到了多种解的形式,目前为止,研究较多的合作博弈问题中的解的形式有:1)由Von Neumann和Morgenstern提出的稳定集;2) Gillies为研究稳定集而建立的并由Shapley和Shubik进一步发展而得到的核(core);3)由Aumann和Maschler提出的谈判集(bargaining set);4)Schmeidler提出的核仁(nucleolus);5)Peleg提出的内核(kernel);6)Maschler,Peleg和Shapley提出的预核(Prekernel);7)由Shapley提出的Shapley值及其拓展形式。如有权重的Shapley值等。

由于研究对象的一般性以及具有较为严格的数学表示、推导等形式,博弈论可以认为是20世纪中叶以来最伟大的思想理论之一。博弈论的各分支在生物学、经济学、国际关系、计算机科学、政治学、军事战略和其他很多学科都有广泛的应用,例如,协商理论与合作博弈理论是目前为止处理通过协商方式达成协议的数学方法。演化博弈理论从其建立之初就是为了研究生物学中种群演化结果,进而推广到研究种群合作的演化过程。可以说,博弈论适用于涉及到互相影响的多个个体之间关于行为预测的所有类型的系统工程问题。

2.2.2层次优化决策理论

层次优化问题研究的是决策者的权利具有层次结构时各决策者如何进行决策的问题,系统工程的交通、管理和工程设计等问题都可能涉及到使用二层规划理论,在博弈问题中,Stackberg博弈问题是最基础多阶段博弈问题,在优化问题中,二层规划问题是应用最广泛、最基础的多层规划问题。
  
层次规划问题的特点:
1)优化问题分层决策,各层决策者依次做出决策。
2)各层决策者有不同的目标,且互相矛盾。
3)各层决策者只控制部分决策变量,以优化自身目标。
4)上层决策者优先做出目标,下层决策者的决策不会影响上层决策者的决策选择。
5)下层决策者的决策不仅影响自身目标,而且还影响上层决策者的目标。
6)所有决策者的决策空间不可分离,并且一般为一个整体。
   
多层规划一词由Candler和Norton于1977年研究奶制品工业模型和农业模型时首次提出的,它的形式为一组嵌套式的数学规划问题,即在约束条件中含有优化问题的数学规划问题。20世纪80年代以来,国内外许多学者先后提出了一般化的二层规划或者n层规划的数学模型。
 
二层规划是一种具有二层递阶结构的优化问题,是最基本的具有层次优化问题,任何多层递阶优化问题可以认为是一系列的二层系统的复合,一个二层问题中,上层问题和下层问题都有各自的目标函数与约束条件,但是上层问题的目标函数和约束条件不仅和上层决策者的决策变量有关,而且还依赖于下层优化问题的最优解,而下层问题的最优解又受到上层决策变量的影响。
 
求解二层规划的常见算法包括。

1)极点搜索法,通过隐枚举线性二层规划问题约束域的所有极点,在一个个极点和与之相邻的极点之间寻找,重复这样的过程直到得到线性二层规划问题的最优解的算法。
2)分支定界法,将二层规划的下层规划问题用其Kuhn-Tucker条件代替并带入上层规划问题中,使得整个二层规划问题变为一个单层规划问题,求解这个单层规划问题,然后在来判断其解是否满足二层规划问题最优解的条件。
3)下降方向法,设计使得目标函数值减少的迭代方向,以此为基础计算精确的迭代步长,使得迭代点对应的目标函数值逐渐减少的迭代算法,最常见的为最速下降法。
4)罚函数法,通过下层规划问题设计不同的惩罚项,然后把惩罚项加入到上层目标函数中,从而将二层规划问题转化为一个带惩罚参数的单层规划问题,进而通过求解一系列非线性规划问题得到二层规划问题的最优解。

除此之外,类比于解决最优化问题的算法,解决二层规划问题的算法还包括遗传算法、信赖域法、同伦法等。

二层规划问题的研究,从算法上来说主要集中于设计有效的、可行的算法来解决特定形式的二层规划问题,从理论上来说主要是研究二层规划最优解最优性条件及其性质,通过对目标函数或者是约束条件左边项函数加入额外的假设,例如光滑性、凸性、多目标性等,进而得到更加具体的最优性条件。在应用层面上,二层规划的模型和方法广泛应用于涉及到多层次、动态等系统工程问题,因此,应用二层规划建模解决实际问题仍是今后的发展方向之一。

2.2.3机制设计

机制设计理论基于经济学中一个由来已久的观念:只要把许多各自拥有部分信息的行为人的信息而非所有相关信息汇总起来,就可以有效的做出关键的经济决策,而为了做出相应的决策,我们需要设计一种方式把所有人的私人信息汇总起来,此时,经济决策的效率很大程地上取决于选取的方式如何有效地收集和整合所有分散的信息,因此,机制设计理论研究的是选择博弈规则的理论,博弈论以博弈规则为前提,对参与人的行为选择进行预测。而机制设计理论更进一步,来选择博弈的最优规则,

机制设计理论是由Hurwicz、Maskin和Mverson -起建立,被广泛运用于公共物品、双边交易、拍卖、委托代理问题等不完全信息博弈问题,用以解决博弈的主导者或者机制设计者遇到其他参与者存在私人信息时选择博弈规则来达到一定目标的博弈问题,这三位学者于2007年被授予诺贝尔经济学奖,用以表彰他们的研究为机制设计理论的贡献。
 
机制设计问题可以被理解为一个特殊的全局优化问题,机制设计者的目标是在所有可能想到的规则下找到最优博弈规则,进而使得在此规则下的目标函数达到最优值,例如在拍卖问题中,卖者不知道买者对于拍卖品的真实估价,卖者为了使得通过拍卖的方式出售物品并获得最大收益,他需要在所有可能的拍卖方式中选择出一种拍卖方式来出售物品,进而使得自身收益最大,这种选择拍卖方式的问题是一个机制设计问题,在委托代理问题中,委托人可能不知道代理人的私人信息,例如工作的努力程度等。委托人为了达成某个项目,他可能通过转移支付的方式来激励代理人的行为,如何设计转移支付同样是一个机制设计问题,这两个问题有一个共同的特征,即机制设计者的目标函数是自身收益或者效用值,选择决策的定义域为所有可能的博弈规则,或者其中的一个子集,此时,机制设计问题可以认为是机制设计者在以所有可能的博弈规则为定义域中选择一个博弈规则,使得自身收益或者效用达到最值的全局优化问题。
 
机制设计理论的主要内容可以理解为把合同理论扩展到多人情形,合同理论为机制设计者为单个行为人构建激励机制的问题。例如只存在一个买者的物品出售、拍卖问题,或者在供应链中,只存在一个制造商和一个供应商的定价、搭售问题。合同理论缺少多个行为人之间的互动。
 
显示原理是机制设计理论得以发展的基石,由于一般的机制设计问题需要在所有可能出现的博弈规则中进行选择,其范围过大。Myerson的研究缩小了我们寻找所需机制的范围,把机制设计者选择的机制缩小到一类直接机制中。例如,在最优出售机制设计中,一个直接机制是由两个基本函数构成的,一个函数反映买者获得物品的概率,另一个函数反映获得物品后向卖者的转移支付,显示原理表明,我们可以把卖者寻找使得自身收益最大的出售机制的范围缩小到买者如实报告自身私人信息的直接机制中,并且参与者在任意出售机制的均衡策略中得到物品的概率和参与者期望收益等于在如实报告自身真实私人信息的直接机制中得到物品的概率与期望收益,任意出售机制和一类直接机制在策略和收益上是等价的,显示原理通过复合函数把一个复杂的一般化机制与一个直接机制相对应,大大简化了机制设计者选择机制的范围。

机制设计最为成功的应用方向是拍卖、公共物品和委托代理问题。拍卖中的VCG机制、AGV机制以及合谋等方向的研究都涉及到机制设计理论。Laffont关注组织中的激励问题,并将这些理论贡献集成在《激励与政治经济学》-书中。Laffont和Martimort合著的《激励理论:委托一代理模型》-书详细介绍了设计激励性规则的一般框架。机制设计理论已经从一种理论方法逐渐转变为一种思想,更加一般化的机制设计问题属于一类变分问题或者是最优控制问题,从数学角度出发解决更加一般化的机制设计问题以及机制设计中的合作行为可能是今后机制设计理论发展的方向之一。

3 总结与展望

系统工程的迅速发展和广泛应用,与相关的优化与决策方法的发展有着密切的关系,从决策对象之间互不影响的最优化、决策理论,到决策对象之间互相影响的博弈论,解决系统工程问题的数学工具不断地发展,优化与决策理论方法为系统工程提供了越来越多的理论方法,相应的算法为解决实际系统工程问题提供了技术支持,同样,实际的系统工程问题为优化决策理论的创新提供了研究背景。

基于系统工程问题的复杂性,包括多主体、多属性和多层次等特征,解决复杂的系统工程问题所涉及到的优化和决策方法具有交叉融合的特点,从具体的工程、经济、管理、生物、物理等学科抽象而提炼出具有交叉和融合特点的优化与决策问题,建立和完善相应的优化与决策方法,进而应用该方法解决实际的系统工程问题,仍然是系统工程学科发展的主要方向之一。

系统工程涉及到的优化决策理论在未来的发展方向可能包括。
  
1)复杂系统
复杂系统是有众多系统单元组成的,并且系统的整体行为不能由其系统单元的行为和特征来解释,包括多种整体行为或者特征,具有多主体、多属性、多层次的特点,研究具有复杂性特征的系统工程问题是为了揭示复杂特征对系统中决策者决策行为的影响。

2)演化与动态
具有演化和动态特征的系统涉及到动态规划与博弈、演化博弈、控制论等多种优化与决策理论方法,研究演化与动态的系统工程问题是为了揭示动态过程对系统的稳定以及系统最优运行方式的选择等方面的影响。

3)复杂网络
系统可能具有一定的网络结构,包括小世界、无标度网络等,这激发了学术界对复杂网络的研究,使得复杂网络成为了研究系统工程涉及到的复杂性科学的研究重点之一,使用优化与决策理论对于复杂网络的研究目标之一是为了揭示网络结构对系统稳定性等方面的影响。
 
4)依据最优性条件构造算法
算法设计以及计算机的运用是解决实际大型、复杂系统工程问题的技术方法与手段。针对求解复杂的系统工程问题而设计相应的算法是系统工程涉及到的优化决策理论在未来发展的主要研究方向之一,对于特定形式的优化问题求解,可能会归于依据优化问题的最优性条件来设计相应的算法,这同样对优化问题关于最优性条件的分析提出了更高的要求。
 
5)多种优化理论互相交叉
系统工程问题复杂程度不断增加,进而导致涉及到的优化问题具有结构交叉的特征,无法在标准的优化和决策理论中直接寻找解决方案,例如在动态优化中加入随机性,非线性、多目标优化中的目标函数具有非可微性,组合优化中加入随机性、鲁棒性等,对于这些非标准化的优化和决策问题,在理论和应用层面上,为具有结构交叉特征的系统工程问题寻找适当的解决方案仍然是近期以及以后优化和决策理论发展的主要方向之一。

 

本文摘自中国系统工程学会主办的《系统工程理论与实践》2020年第40卷第8期,作者刘佳,博士,助理研究员,武汉大学经济与管理学院博士后,研究方向:博弈论、优化理论;王先甲,教授,博士生导师,研究方向:博弈论、决策理论。