大规模复杂管理问题的优化与决策方法

管理科学与工程学科综合课大规模复杂管理问题的优化与决策方法方卫国2010年3月19日大纲•决策与优化的关系•管理中的优化问题•案例：深圳市粪渣清运排班优化•大规模复杂管理问题的优化方法•几种启发式优化算法•对管理决策的一些讨论决策与优化的关系•按结构化程度划分决策问题–结构化决策•决策过程和方法有固定规律可循，能用明确语言和模型加以描述，可依据一定通用模型和决策规则求解。–非结构化决策•决策过程和方法无固定规律可循，无固定决策规则和通用模型可依，决策者的经验、直觉、判断力、偏好和决策风格等对决策效果有相当影响。–半结构化决策决策与优化的关系•结构化决策按自然条件或外界环境划分–确定型决策–风险型决策•决策树，期望值理论，贝叶斯理论，熵理论–不确定型决策•等概率法，最大最小法，等等决策与优化的关系•狭义理解（工程领域）：结构化的确定型决策=优化•广义理解（管理领域）：决策=优化–决策就是找出最优的行动方案•实际操作–优化作为决策的一个环节：对问题进行简化，建立模型，进行优化求解，然后增添无法建模的信息，综合权衡作出决策管理中的优化问题•很多管理问题可建立一个优化模型解决,称为运筹学(MS/OR)问题。•如果模型形式比较单纯,具有较好的性质(如可导、可行域连通、凸集等)或者规模较小,则可采用经典算法求解。管理中的优化问题•经典算法–线性规划:单纯形法和内点法–非线性规划:可行方向法、罚函数法、序列二次规划法、约束变尺度法、乘子罚函数法–整数规划:分支定界，割平面法，0-1规划的隐枚举法–动态规划:Bellman最优性原理管理中的优化问题•管理中的优化问题往往是组合优化问题–组合优化的对象是解空间的离散状态，函数优化的对象是一定区间内的连续变量。•组合优化描述–令={S1,S2,...,Sn}为所有状态构成的解空间，C(Si)为状态Si对应的目标函数值，要求寻找最优解S*，使得对所有的Si,有C(S*)=minC(Si)管理中的优化问题•典型的组合优化问题–旅行商问题(travelingsalesmanproblem，TSP)–加工调度问题(schedulingproblem，如Flow-shop，Job-shop)–0-1背包问题(knapsackproblem)–装箱问题(binpackingproblem)–图着色问题(graphcoloringproblem)–聚类问题(clusteringproblem)等管理中的优化问题•n个城市的对称TSP问题，解空间或搜索空间的大小为(n-1)!/2。–n=7，解的数目为6!/2=128–n=10，解的数目约为18,000–n=20，解的数目约为1016–n=50，解的数目约为1062•随着变量个数增加，解空间规模急剧增大。管理中的优化问题•经济的发展、管理水平的提高以及管理视野的扩展，使得求解大规模和超大规模的现实管理优化问题成为一项重要的社会需求–大规模物流系统优化问题–大规模交通网络优化设计问题–航空公司大规模排班优化问题–大规模生产系统优化问题–大规模电网调度优化问题–突发事件下多部门多环节多目标动态优化问题大规模复杂管理问题的优化方法一般的优化问题求解算法：−精确算法：基于数学规划理论的经典算法•Exactalgorithms:guaranteeoptimality,butmaynotbealwaysapplicable.−近似算法：启发式算法，基于经验、直觉甚至是技巧•Approximatealgorithms:capableofproducinggoodsolutionstoevenlargeproblems,butdonotguaranteeoptimality.•从模型和算法的精确性而言,问题的求解有四种基本的组合:模型与算法的组合精确算法+精确模型精确算法+近似模型近似算法+精确模型近似算法+近似模型谁更重要?模型优先还是算法优先?•Itisbettertohaveagoodandacceptablesolutiontoatrueproblem(exactmodel)ratherthananoptimalsolutiontoasimplifiedproblem(Approximatemodel)thatmayhavelittleresemblancetotheoriginalproblem.大规模优化问题的求解三种思路•思路一：基于数学规划理论的经典算法，如[1]钱富才,刘丁,刘甲.大规模系统的全局优化[J].数学的实践与认识,2003,33(3):41-45.针对一类特殊大规模优化问题，即目标和约束函数可分离的非凸大规模系统优化，提出一种3级递阶优化算法。[2]CervelleraC,ChenVCP,WenA.Optimizationofalarge-scalewaterreservoirnetworkbystochasticdynamicprogrammingwithefficientstatespacediscretization[J].EuropeanJournalofOperationalResearch,2006,171:1139–1151.采用随机动态规划方法求解大规模水库网络中水资源的调度问题，但给出的算例只针对包括30个水库的优化问题。大规模优化问题的求解三种思路•思路一：基于数学规划理论的经典算法，如[3]BoggsPT,TolleJW.Sequentialquadraticprogrammingforlarge-scalenonlinearoptimization[J].JournalofComputationalandAppliedMathematics,2000,124:123-137.探讨如何应用SQP法求解大规模非线性约束优化问题，但未实际应用。大规模优化问题的求解三种思路•思路二:启发式算法,如[4]YangZ,TangK,YaoX.Largescaleevolutionaryoptimizationusingcooperativecoevolution[J].InformationSciences,2008,178:2985–2999提出了一种求解大规模不可分优化问题的演化算法，给出了一个含1000个决策变量的算例。[5]HouZ-G.Ahierarchicaloptimizationneuralnetworkforlarge-scaledynamicsystems[J].Automatica,2001,37:1931-1940提出采用神经网络方法优化大规模动态系统，但最终只在一个小规模算例上实现（能源控制系统）。大规模优化问题的求解三种思路•思路二:启发式算法,如[6]ZhaoF,ZengX.Optimizationoftransitroutenetwork,vehicleheadwaysandtimetablesforlarge-scaletransitnetworks[J].EuropeanJournalofOperationalResearch,2008,186:841–855组合模拟退火、禁忌搜索和贪婪算法，提出了一种元启发式算法求解大规模交通运输网络优化设计问题，给出了一个称得上是“大规模”问题的实际算例，涉及由15个节点组成的街道网络和15,570个日常出行线路。大规模优化问题的求解三种思路•思路三:数学规划理论和启发式算法结合的混合算法[7]WangY-J,ZhangJ-S.Anefficientalgorithmforlargescaleglobaloptimizationofcontinuousfunctions[J].JournalofComputationalandAppliedMathematics,2007,206:1015-1026将模拟退火算法与基于梯度的算法结合起来，构造了一种求解大规模连续函数优化的快速下降算法。他们给出的算例只含有1000个变量。大规模优化问题的求解三种思路•思路三:数学规划理论和启发式算法结合的混合算法[8]ClarkSJ，BarnhartC,KolitzSE.Large-scaleoptimizationplanningmethodsforthedistributionofUnitedStatesarmymunitions[J].MathematicalandComputerModelling,2004,39:697-714研究从美国本土运送军火到海外基地过程中的运输工具和运输线路最优安排问题，建立了线性混合整数规划。采用Dantzig-Wolfe分解将原问题分解为两级问题求解，使用启发式算法生成初始可行解，在初始可行解基础上进行优化。给出的超大规模实际算例，涉及单一军火，200天规划期，13个军火仓库，7个装运港口和17个目的港口，175艘运输船和美国本土卡车及铁路资源。虽然算例是一个超大规模问题，但问题模型具有相对较好的性态，即是一个线性问题。大规模复杂管理问题的优化方法思路一的经典算法对大规模管理优化问题存在困难：−对大规模函数优化问题（管理领域不多），经典算法的非多项式时间算法使得计算时间指数增加。−线性规划的单纯形法并非多项式算法,适合中小规模问题,在变量和约束从103-104量级开始,性能快速下降。−对组合优化（管理领域较多），所有基于梯度的算法统统失效−整数规划和动态规划:分支定界的组合爆炸和动态规划的维数灾难,导致算法失效。大规模复杂管理问题的优化方法−思路二和思路三均为近似算法，或称为启发式算法−若问题规模很大，但模型性态良好，可采用思路三的混合算法−大部分大规模管理优化问题，是组合优化问题，模型一般不具备良好的性态，只能考虑采用思路二的纯启发式算法求解。•启发式算法一般基于对具体问题的理解，根据常识性知识、规则或者类比其他系统诸如进化过程、退火过程、蚁群智能、鸟群智能等构造,求取问题的次优解或以一定的概率求取最优解。上述思路基于一定的直观基础而非数学理论本身,因而称为启发式算法.•目的是构造一个容易理解的求解模式,在一个可接受的合理的计算时间内,提供一个”好”的解。启发式算法•启发式算法分类–基于搜索的启发式•要求对问题的解进行表示，在解空间按照不同的逻辑进行搜索。–基于构造规则的启发式•要求根据问题具体特征设计合理的解构造规则，在该规则指导下，对解进行分段构造最终形成一个完整解而非对完整解进行搜索，避开对完整解的计算机表示并大大降低计算机存储空间开销。启发式算法•质朴型:下降算法/摄动算法•局部搜索型:禁忌搜索/模拟退火•群体进化型:遗传算法•群体智能型:蚁群算法/粒子群/鱼群算法•基于数学逻辑的方法:Lagrangian分解/不完全分支定界•组合算法:GA+ANN/GA+Newton/PSO+1-dimensionalsearch……基于搜索的启发式算法•启发式算法难以从数学上精确度量其效果,一般可以从两方面评价一个启发式算法的性能:–解的质量–计算成本(CPU计算时间，存储空间)算法性能与计算复杂性−Empiricaltesting:basedonthebestsolutionsofsomeoftheexistingheuristicswhentestedonasetofpublisheddata.−Benchmarking:seehowtheheuristicsolutioncompareswiththebenchmarksolution.(例子)解的质量−TimeComplexity−definedbyO(g(N)),whereNthesizeoftheproblem.−Ifg(N)isapolynomialfunctionofN,thentheproblemcanbesolvedoptimallywithinareasonableamountofcomputationtime.−Ifg(N)isanexponentialfunction,theproblemmaybedifficulttosolveoptimal