运筹学课件（山东大学）

运筹帷幄之中决胜千里之外运筹学课件绪论Introduction运筹学的概况最优化模型教学计划与方法考试与要求参考文献绪论运筹学的由来与发展运筹学的性质与特点运筹学的主要内容运筹学的发展趋势运筹学的学科地位运筹学概况名称的由来OperationResearch运筹帷幄“史记”运作研究发展历程运筹学的由来与发展二战以前萌芽二战期间产生五六十年代发展七八十年代成熟引入数学方法解决实际问题一定性与定量方法结合系统与整体性ー从全局考察问题应用性一源于实践、为了实践、服务于实践交叉学科ー涉及经济、管理、数学、工程和系统等多学科开放性ー不断产生新的问题和学科分支多分支ー问题的复杂和多样性运筹学的性质与特点线性规划数学规划非线性规划整数规划动态规划学科容多目标规划双层规划组优化最优计数问题网络优化排序问题统筹图随机优化对策论排队论库存论决策分析可靠性分析运筹学的主要内容成熟的学科分支向纵深发展新的研究领域产生与新的技术结合与其他学科的结合加强传统优化观念不断变化运筹学的发展趋势在数学学科中的地位运筹数学在系统科学中的地位系统工程1在管理科学中的地位管理与运筹学1与经济学的关系问题与方法1与工程科学的关系方法与应用1与计算机科学的关系核心算法与工具基础理论应用理论应用技术运筹学运筹学的学科地位模型要素变量一可控因素目标ー优化的动カ和依据约束ー内部条件和外部约束研究内容建模概念最优性条件算法灵敏度分析最优化模型实例问线性规划模型建模分析线性规划模型模型线性规划模型教学计划数学规划以线性规划和整数规划为教授重点,组合优化部分主要讲网络优化,而随机优化讲授排队论和对策论,其它部分作为选讲内容。教学方法以授课为主,案例分析与上机实习相结合。而讲课中主要培养用最优化方法解决实际问题的能力。教学计划与方法考核内容理论方法一笔试 50%应用能力ー案例分析 30%计算能カー上机操作 20%考试与要求韩伯棠,管理运筹学,高等教育出版社,北京,2000年徐光辉等,运筹学手册,科学出版社，北京,1999年胡运权等,运筹学教程,清华出版社,北京,1998年刘家壮,王建方,网络最优化,华中工学院出版社,武汉,1987年管梅谷,郑汉鼎,线性规划,山东科学技术出版社，济南，1983年参考资料运筹帷幄之中决胜千里之外线性规划LinearProgramming运筹学课件线性规划线性规划问题可行区域与基本可行解单纯形算法初始可行解对偶理论灵敏度分析计算软件案例分析线性规划问题线性规划实例生产计划问题运输问题线性规划模型一般形式规范形式标准形式形式转换概念某工厂用三种原料生产三种产品,已知的条件如表21></a>.l.l所示,试制订总利润最大的生产计划453单位产品的利润（千元）2000523原料P3800420原料P21500032原料P1原料可用量（公斤/日）Q3产品Q2产品QI单位产品所需原料数量（公斤）生产计划问题问题分析模型计算结果运输问题问题分析模型一般形式目标函数约束条件注释规范形式标准形式概念模型转换约束转换实例目标转换变量转换约束转换不等式变等式不等式变不等式等式变不等式不等式变等式松弛变量剩余变量不等式变不等式例2.1.3把问题转化为标准形式可行区域与基本可行解图解法可行域的儿何结构基本可行解与基本定理图解法例2.2.1解线性规划注释可能出现的情况:可行域是空集可行域无界无最优解最优解存在且唯一,则ー定在顶点上达到最优解存在且不唯一,一定存在顶点是最优解可行域的儿何结构基本假设凸集可行域的凸性基本假设凸集可行域的凸性问题基本可行解与基本定理基本定理问题基本可行解定义基本定理问题单纯形算法理论方法算法步骤单纯形表算例理论方法★★★定理2.3.1定理2.3.2定理2.3.3算法步骤单纯形表算例初始单纯形表迭代1迭代2初始解两阶段法说明两阶段法基本思想第•阶段:通过求解辅助问题的最优基可行解得到原问题的初始基可行解。第二阶段:求原问题的最优解算例辅助问题原辅助题问与题的关系求辅助问题的三种情况算例第1阶段第1阶段第1阶段第1阶段第1阶段第2阶段大M法说明对偶理论对偶规划对偶理论对偶单纯形算法对偶规划标准形式线性规划的对偶规划规范形式线性规划的对偶规划・般形式线性规划的对偶规划实例标准形式的对偶规划规范形式的对偶规划-一般形式的对偶规划实例对偶理论***定理2.5.1定理2.5.2定理2.5.5对偶单纯形算法基本思想算法过程算例基本思想单纯形算法对偶单纯形正贝リ解正则解对偶可行解正则解的单纯性表规划无可行解保持正则性入基变量算法过程否初始正则解检查可行是则停止得最优解选出基变量检查是否无可行解是则停止否无最优解选入基变量计算典式检验数算 例迭 代迭 代迭代灵敏度分析概况改变价值向量改变右端向量概况信息的不确定性信息的变化:价值向量一市场变化右端向量一资源变化系数矩阵ー技术进步认知的误差分析方法静态分析ー比较静态分析ー动态分析改变价值向量一般改变情况改变非基变量的价值向量改变基变量的价值向量算例一般改变非基变量基变量算例改变右端向量基本思想算例基本思想算例计算软件LinDoLinGoMatlabLinDo输入模型求解点击求解按钮 即可结果输入模型!注释内容,可用中文!目标函数:最大-max,最小-min,大小写不分max3xl+5x2+4x3!约束,以subjectto开始subjectto2xl+3x2<=15002x2+4x3<=8003xl+2x2+5x3<=2000end注意事项变量以字母开头,下标写在后面,系数与边量之间加空格不等号为:<尸(<),>=(>),=,<产与<等同变量非负约束可省略结束时以end标示结果LPOPTIMUMFOUNDATSTEP3OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOSTVARIABLEVALUEREDUCEDCOST0.0000000.0000000.0000000.0000000.0000001.0500000.6250000.300000X2 250.000000X3 75.000000ROWSLACKORSURPLUSDUALPRICES0.0000000.0000000.000000LinGo输入模型LinDo模式LinGo模式求解点击求解按钮 即可结果LinDo输入模式model:MAX=3*xl+5*x2+4*x3;2*xl+3*x2<=1500;2*x2+4*x3<=800;3*xl+2*x2+5*x3<=2000;end注意与LinDo的区别目标函数中加等号变量与系数之间用“*”Model:-end可省略LinGo模式Model:Sets:EndsetsData:Enddata调用函数与计算end!定义集合!定义数据集合部分model:!开始sets:!定义集合ve/1..3/:c,x;co/1..3/:b;ma(co,ve):a;endsets!注:集表达式:名称/成员/：属性名称(初始集):属性定义数据data:!定义数据c=354;ba=230024325;Enddata!注:数据的大小与集合定义中・致,分量中间用空格或逗号分开,数据结束后用分号;调用函数max=@sum(ve(j):c(j)*x(j));@for(co(i):@sum(ve(j):a(i,j)*x(j))<=b(i));主要函数:@for(set(set_index_list)|condition:expression)@sum(set(set_index_list)|condition:expression)@min(max)(set(set_index_list)|condition:expression)结果Globaloptimalsolutionfoundatiteration: 3Objectivevalue: 2675.000VariableValueReducedCostC(1) 3.0000000.000000C(2) 5.0000000.000000C(3) 4.0000000.000000X(1) 375.00000.000000X(2) 250.00000.000000X(3) 75.000000.000000B(1) 1500.0000.000000B(2) 800.00000.000000B(3) 2000.0000.000000A(1,1)2.0000000.000000A(1,2)3.0000000.000000A(1,3)0.0000000.000000A(2,1)0.0000000.000000A(2,2)2.0000000.000000A(2,3)4.0000000.000000A(3,1)3.0000000.000000A(3,2)2.0000000.000000A(3,3)5.0000000.000000RowSlackorSurplusDualPrice1 2675.0001.0000002 0.0000001.050000Scilab函数命令1：[xJagr/f]=linpro(pzC/b[zx0])命令2：[x,lagr/f]=linpro(p/C/b/ci/cs[zx0])命令3：[xzlagrzf]=linpro(pzCzbzcizcszme[zx0])命令4：[xzlagrzf]=linpro(pzCzbzcizcszmezxO[zimp])命令5：[xlzcrit]=karmarkar(azbzczxO)注意事项命令1问题形式minp'*xs.t.C*x<=b[xzlagrzf]=linpro(pzCzb[zx0])命令2[xzlagrzf]=linpro(p,C,bzcizcs[zx0])问题形式minp'*xs.t.C*x<=bci<=x<=cs命令3[xzlagrzf]=linpro(pzCzbzcizcszme[zx0])问题minp'*xs.t.C(jz:)x=b(j)zj=lz...zmeC(jz:)x<=b(j)zj=me+lz...zme+mdci<=x<=cs命令4[xzlagrzf]=linpro(pzCzbzcizcszmezxO[zimp])问题形式s.t.C(レ:)x=b(j),j=l,…,meC(レ:)x<=b(j),j=me+l/.../me+mdci<=x<=cs指定初始可行解xO命令5[xlzcrit]=karmarkar(a/b/c/xO)问题形式minc&#O39;*xs.t.a*x=bx>=O注意事项命令2和3中xO可省略,但命令4和5中不可省略向量都是列向量,参数的顺序不可换命令3中等式约束必须在前面人力资源分配问题某个中型百货商场对售货人员(周工资200元)的需求经统计如下表为了保证销售人员充分休息,销售人员每周工作5天,休息2天。问应如何安排销售人员的工作时间,使得所配售货人员的总费用最小?19七18ハ16五14四1512人数星期模型假设每天工作8小时,不考虑夜班的情况;每个人的休息时间为连续的两天时间;每天安排的人员数不得低于需求量,但可以超过需求量问题分析因素:不可变因素:需求量、休息时间、单位费用；可变因素:安排的人数、每人工作的时间、总费用;方案：确定每天工作的人数,由于连续休息2天,当确定每个人开始休息的时间就等于知道工作的时间,因而确定每天开始休息的人数就知道每天开始工作的人数,从而求出每天工作的人数。变量:每天开始休息的人数约束条件:.每人休息时间2天,自然满足。.每天工作人数不低于需求量,第i天工作的人数就是从第i-2天往前数5天内开始工作的人数,所以有约束:.变量非负约束:目标函数:总费用最小,总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息,所以总人数等于模型注解该问题本质上是个整数规划问题,放松的线性规划的最优解是个整数解,所以两规划等价。定义整数变量用函数@gin(xl)......@gin(x7);0-1整数变量为@bin(xl)配料问题某化工厂要用三中原料混合配置三种不同规格的产品各产品的规格单价如表!,253550单价(元/公斤)不限原料I不少于25%原料II不超过50%原料I不少于50%原料!I不超过25%规格CBA产品问如何安排生产使得生产利润最大?352565单价(元/公斤)100100日最大供应量IIIIII原料原料的单价与每天最大供应量如表2配料问题案例问题问题分析模型求解结果分析问题分析变量约束条件目标函数变量生产计划就是要确定每天生产三种产品的数量以及非中产品中三中原料的数量。而由于每种产品的数量等于三种原料数量之和,所以只要确定每天生产三种产品分别含有的原料数量即可。所以变量就是每天生产三种产品所用的原料数,设用于生产第i种产品的第j种原料数为约束条件规格约束约束条件资源约束目标函数总产值总成本总利润=总产值ー总成本模型求解运筹帷幄之中决胜千里之外运筹学课件整数线性规划IntegerLinearProgramming整数规划整数规划问题与模型整数规划算法计算软件应用案例整数规划问题实例特点模型分类应用案例投资组合问题旅游售货员问题背包问题投资组合问题实例模型背景证券投资:把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。项目投资:财团或银行把资金投入到若干项目中以获得中长期的收益最大。案例某财团有万元的资金,经出其考察选中个投资项目,每个项目只能投资ー个。其中第个项目需投资金额为万元,预计5年后获利（ ）万元，问应如何选择项目使得5年后总收益最大?模型变量一每个项目是否投资约束ー总金额不超过限制目标一总收益最大旅游售货员问题背景案例模型旅游线路安排预定景点走且只走ー次路上时间最短配送线路ー货郎担问题送货地到达一次总路程最短案例有・・旅行团从 出发要遍游城市,已知从到的旅费为 ,问应如何安排行程使总费用最小?模型变量一是否从i第个城市到第j个城市约束每个城市只能到达ー•次、离开一次避免出现断裂每个点给个位势 除了初始点外要求前点比后点大目标ー总费用最小背包问题背景案例模型邮递包裹把形状可变的包裹用尽量少的车辆运走旅行背包容量一定的背包里装尽可能的多的物品实例某人出国留学打点行李,现有三个旅行包,容积大小分别为1000毫升、1500毫升和2000毫升,根据需要列出需带物品清单,其中一些物品是必带物品共有7件,其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品,如果不带将在目的地购买,通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表,试给出ー个合理的安排方案把物品放在三个旅行包里。物品12345678910体积200350500430320120700420250100价格15100705075200902030问题分析变量一对每个物品要确定是否带同时要确定放在哪个包裹里,如果增加一个虚拟的包裹把不带的物品放在里面,则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号,则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中约束包裹容量限制必带物品限制选带物品限制目标函数一未带物品购买费用最小模型特征一变量整数性要求来源问题本身的要求引入的逻辑变量的需要性质一可行域是离散集合线性整数规划模型•般整数规划模型0-1整数规划模型混合整数规划模型一般整数规划模型0-1整数规划模型混合整数规划模型算法与线性规划的关系分支定界算法割平面算法近似算法与线性规划的关系整数规划放松的线性规划可行解是放松问题的可行解最优值大于等于放松问题的最优值注释最优解不一定在顶点上达到最优解不一定是放松问题最优解的邻近整数解整数可行解远多余于顶点,枚举法不可取分支定界算法算法思想算法步骤算例注释算法思想隐枚举法求解放松问题最优值比界坏最优解为整数最优值比界好最优解为非整数最优值比界好分支边界分支舍弃分支的方法定界当前得到的最好整数解的目标函数值分支后计算放松的线性规划的最优解整数解且目标值小于原有最好解的值则替代原有最好解整数解且目标值大于原有最好解的值则删除该分支其中无最优解非整数解且目标值小于原有最好解的值则继续分支非整数解且目标值大于等于原有最好解的值则删除该分支其中无最优解选ー,分支写出并求解放松问题,同时从分支集中删除该分支判定是否为整数解初始分支为可行解集,初始界为无穷大判定是否分支集空是停止当前最好解为最优解是否判定最优值是否小于当前界判定最优值是否小于当前界是否按非整数变量分支并加入分支集否是以最优解替代当前最好解最优值替代当前界算例注释求解混合整数规划问题,只对整数变量分支,对非整数变量不分支。对0-1整数规划分支时割平面算法算法思想算法步骤算例算法思想由放松问题的可行域向整数规划的可行域逼近方法一利用超平面切除要求整数解保留放松问题最优值增加割平面生成方法条件一保留整数解删除最优解整数可行解最优基可行解正则解算法步骤求放松问题的最优基可行解判断是否为整数解是停止得到最优解否在单纯性表中加入一列利用对偶单纯性算法求最优解算例计算软件整数变量定义LinDo一般整数变量:GIN<Variable>0-1整数变量:INT<Variable>LinGo一般整数变量:@GIN(variable_name);0-1整数变量:@BIN(variable_name);算例算例max3xl+5x2+4x3subjectto2x1+3x2<=15002x2+4x3<=8003xl+2x2+5x3<=2000endginxlginx3应用案例分析人力资源分配问题应急设施选址问题人力资源分配问题某个中型百货商场对售货人员(周工资200元)的需求经统计如下表为了保证销售人员充分休息,销售人员每周工作5天,休息2天。问应如何安排销售人员的工作时间,使得所配售货人员的总费用最小?19七18六16五14四121512人数星期模型假设每天工作8小时,不考虑夜班的情况;每个人的休息时间为连续的两天时间;每天安排的人员数不得低于需求量,但可以超过需求量问题分析因素不可变因素;需求量、休息时间、单位费用；可变因素;安排的人数、每人工作的时间、总费用；方案确定每天工作的人数,由于连续休息2天,当确定每个人开始休息的时间就等于知道工作的时间,因而确定每天开始休息的人数就知道每天开始工作的人数,从而求出每天工作的人数。变量每天开始休息的人数约束条件1.每人休息时间2天,自然满足。3.变量非负约束:目标函数:总费用最小,总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息,所以总人数等于模型注解该问题本质上是个整数规划问题,放松的线性规划的最优解是个整数解,所以两规划等价。定义整数变量用函数@gin(xl) @gin(x7);0-1整数变量为@bin(xl)应急选址问题某城市要在市区设置k个应急服务中心,经过初步筛选确定了m个备选地，现已知共有n个居民小区,各小区到个备选地的距离为为了使得各小区能及时得到应急服务,要求各小区到最近的服务中心的距离尽可能的短,试给出中心选址方案。问题分析该问题与传统的选址问题的主要区别在于其目标不再是要求费用最小,而是要求最长距离最短。也就是离服务中心距离最远的小区离最近的服务中心距离最小。变量：当中心的位置确定下来后,各小区对应的最近中心也就确定,所以真正的变量也就是小区的位置。设问题分析为了便于说明问题引入间接变量,第i小区是否由第j个中心服务以及最远的距离约束条件小区服务约束问题分析最远距离约束中心个数约束目标函数:最远距离 最小模型运筹帷幄之中决胜千里之外运筹学课件非线性规划Non-linearProgramming非线性规划基本概念凸函数和凸规划ー维搜索方法无约束最优化方法约束最优化方法基本概念非线性规划问题非线性规划方法概述非线性规划问题例1曲线的最优拟合问题例2构件容积问题数学规划约束集或可行域MP的可行解或可行点向量化表示当p=O,q=O时,称为无约束非线性规划或者无约束最优化问题。否则,称为约束非线性规划或者约束最优化问题。最优解和极小点非线性规划方法概述非线性规划基本迭代格式凸函数和凸规划凸函数及其性质凸规划及其性质凸函数及其性质凸规划及其性质约束集如果(MP)的约束集X是凸集,目标函数f是X上的凸函数,贝リ(MP)叫做非线性凸规划,或简称为凸规划。定理4.2.6凸规划的任一局部最优解都是它的整体最优解。ー维搜索方法精确ー维搜索方法0.618法Newton法非精确ー维搜索方法Goldstein法Armijo法0.618法(近似黄金分割法)Newton法Goldstein法Goldstein法步骤Armijo法无约束最优化方法无约束问题的最优性条件最速下降法共喪方向法无约束问题的最优化条件最速下降法共甄方向法二次严格凸函数的无约束最优化问题F-R法步骤约束最优化方法约束最优化问题的最优化条件简约梯度法惩罚函数法其中(MP)约束最优化问题的最优化条件令K-T条件简约梯度法(4.5.12)Wolfe法步骤惩罚函数法思想:利用问题中的约束函数做出适当的带有参数的惩罚函数,然后在原来的目标函数上加上惩罚函数构造出带参数的增广目标函数,把(MP)问题的求解转换为求解一系列无约束非线性规划问题。罚函数法障碍函数法罚函数法设法适当地加大不可行点处对应的目标函数值,使不可行点不能成为相应无约束极小化问题的最优解。罚函数实际应用中,选取・个递增且趋于无穷的正罚函数参数列其中*****罚函数法计算步骤障碍函数法在可行区域的边界上筑起一道“墻”,当迭代点靠近边界时,所构造的增广目标函数值陡然增大，于是最优点就被“挡”在可行区域内部了。构造障碍函数障碍函数法步骤运筹帷幄之中决胜千里之外运筹学课件动态规划DynamicProgramming动态规划综述最优化原理确定性的定期多阶段决策问题确定性的不定期多阶段决策问题综述动态规划所研究的对象是多阶段决策问题。所谓多阶段决策问题是指ー类活动过程,它可以分为若干个相互联系的阶段,在每个阶段都需要作出决策。这个决策不仅决定这ー阶段的效益,而且决定下ー阶段的初始状态。每个阶段的决策确定以后,就得到一个决策序列,称为策略。多阶段决策问题就是求一个策略,使各阶段的效益的总和达到最优。最优化原理??多阶段决策问题及实例例1例2例3多阶段决策问题??最优化原理性质用最优化原理求解例2例1多阶段资源分配问题设有数量为x的某种资源,将它投入两种生产方式A和B中:以数量y投入生产方式A,剩下的量投入生产方式B,则可得到收入g(y)+h(x-y),其中g(y)和h(y)是已知函数，并且g(O)=h(O)=O:同时假设以y与x-y分别投入两种生产方式A,B后可以回收再生产,回收率分别为a与b。试求进行n个阶段后的最大总收入。例1续(1)若以y与x-y分别投入生产方式A与B,在第一阶段生产后回收的总资源为xl=ay+b(x-y),再将xl投入生产方式A和B,则可得到收入g(yl)+h(xl-yl),继续回收资源x2=ayl+b(xl-yl), 若上面的过程进行n个阶段,我们希望选择n个变量y,yl,y2,…,yn-1,使这n个阶段的总收入最大。例1续(2)因此，我们的问题就变成:求y,yl,y2,…,yn-1,以使g(y)+h(x-y)+g(yl)+h(xl-yl)+,,,+g(yn-l)+h(xn-l-yn-l)达到最大,且满足条件xl=ay+b(x-y)x2=ayl+b(xl-yl)xn-l=ayn-2+b(xn-2-yn-2)yi与xi均非负,i=i,2,-,n-l例2生产和存储控制问题某工厂生产某种季节性商品,需要作下•年度的生产计划,假定这种商品的生产周期需要两个月，全年共有6个生产周期，需要作出各个周期中的生产计划。设已知各周期对该商品的需要量如下表所示:850301055需求量654321周期例2续(1)例2续(2)假设这个エ厂根据需要可以日夜两班生产或只是日班生产,当开足日班时,每ー个生产周期能生产商品15个单位,每生产ー个单位商品的成本为100元。当开足夜班时，每•生产周期能生产的商品也是15个,但是由于增加了辅助性生产设备和生产辅助费用,每生产ー单位商品的成本为120元。由于生产能カ的限制,可以在需求淡季多生产ー些商品储存起来以备需求旺季使用,但存储商品是需要存储费用的,假设每单位商品存储一周期需要16元,已知开始时存储为零,年终也不存储商品备下年使用，问应该如何作生产和存储计划,才能使总的生产和存储费用最小?例2续(3)设第i个周期的生产量为xi,周期末的存储量为ui,那么这个问题用式子写出来就是:求xl,x2,…,x6,满足条件:xl=5+ulx2+ul=5+u2x3+u2=10+u3x4+u3=30+u4x5+u4=50+u5x6+u5=80xi30,0 uj,i=l,2,...,6;j=l,2,...,5使S= =为最小,其中例2续(4)例3.机金矿问题两个金矿A,B分别有存储量x,y,现有一部开矿机器,如果开采金矿A,则以概率pl得储量x的rl倍(0<rl<l),并且机器没有损坏,可以继续再去开采金矿A或B。同时又以概率1-pl宣告失败,机器报废,也得不到金子:如果把这部开矿机器用以开采金矿B.则以概率p2得到储量y的r2倍(0<r2<l),并且机器没有损坏,可以继续再去开采金矿A或B,同时又以概率1-P2宣告失败,机器报废,也得不到金子。把机器用于开采金矿A或者B,如果机器没有损坏，将继续把机器用于开采金矿A或者B,直到机器损坏,问应该如何选择开矿的序列使获得金子的期望值最大。多阶段决策问题

有一个系统,可以分成若干个阶段,任意一个阶段k,系统的状态可以用xk表示(可以是数量、向量、集合等)。在每ー阶段k的每一状态都有一个决策集合Qk(xk),在Qk(xk)中选定一个决策qkQk(xk),状态xk就转移到新的状态xk+l=Tk(xk,qk),并且得到效益Rk(xk,qk)。我们的目的就是在每ー个阶段都在它的决策集合中选择ー个决策,使所有阶段的总效益达到最大。这样的多阶段问题称为动态规划。最优化原理动态规划最优化原理:ー个过程的最优策略具有这样的性质,即无论其初始状态及其初始决策如何,其以后诸决策对以第・个决策所形成的状态作为初始状态而言,必须构成最优策略。最优化原理的性质对于多阶段决策问题的最优策略,如果用它的前步策略产生的情况(加上原有的约束条件)来形成一个前步问题,那么所给最优策略的前阶段的策略构成这前步问题的ー个最优策略。用最优化原理求解例2如果一,开始的存储量uO已经给定,要求最后一个周期结束时有存储量un,那么最优生产和存储费用就完全由uO,un决定。对某一个周期k,如果这个周期开始时有库存量uk-1,要求结束时有库存量uk,那么它的生产数量xk=sk+uk-uk-l,sk是这个周期的商品需求量,所以它的生产和存储费为f(xk)+16uk-1,其中续(1)用Fk(uO,uk)表示开始的存储量为uO,第k个周期结束时存储量为uk的满足前k个周期需要的前k个周期的最优生产和存储费用,由最优化原理xk=sk+uk-uk-lzxk=sk+uk-uk-lzk=2,3,…,6xl=sl+ul-uOz让k=2,3,…,6,求出F6(u0,u6),就得到问题的解确定性的定期多阶段决策问题旅行售货员问题多阶段资源分配问题用最优化原理解某些非线性规划问题排序最优排序法旅行售货员问题旅行售货员问题是图论中一个著名问题,就是在网络N上找一条从vO点出发,经过vl,v2,…,vn各一次最后返回vO的最短路线和最短路程。现把它看成一个多阶段决策问题。从vO出发,经过n个阶段,每个阶段的决策是选择下一个点。如果用所在的位置来表示状态,那么状态与阶段数就不能完全决定决策集合了,因为走过的点不需要再走,所以决策集合与以前选的决策有关。用(vi,V)表示状态,vi是所处的点,V是还没有经过的点集合。在状态(vi,V)的决策集合中,取决策vjV,获得的效益是vi到vj的距离dij,转入下ー个状态(vj,V\{vj}),现在用最优化原理来找递推公式。续⑴用fk(vi,V)表示从vi点出发，经过V中的点各一次,最后回到vO点的最短路程,V是ー个顶点集合,|V|=k,dij是vi到vj的弧长,则多阶段资源分配问题下面讨论有限资源分配问题,它的递推公式是:一般情况下,g(y),g(y)是很复杂的函数时,这个问题的解不容易找。当g(y),g(y)为凸函数,且h(O)=g(O)=O时,可以证明在每个阶段上y的最优决策总是取其端点的值。续⑴引理521设g(x),g(y)是凸函数,则对任何固定的x,F(y)=g(y)+h(x-y)是y的凸函数。引理5.2.2设Fl(x),F2(X)是x的凸函数,则F(x)=max{Fl(x),F2(X)}也是x的凸函数。续⑵定理5.2.1设g(y),g(y)是凸函数,h(O)=g(O)=O,则n阶段资源分配问题的最优策略y在每个阶段总取Oyx的短点的值,并且用最优化原理解某些非线性规划问题假设有数量xO的物资可用于n种生产，若以x!投入第i种生产时可得收益gi(xi),问应如何选取xi,使得xO用于n种生产时得到的总收益最大。这个问题可以写成数学规划问题:续⑴假设每个gi(xi)在内连续,显然F的极大值存在,这是一个特殊类型的非线性规划问题,由于这类问题的特殊结构,可以把它看成一个多阶段决策问题,并利用动态规划的递推关系求解。把数量为xO的物资投入n种生产方式,可以看成是n阶段决策问题每阶段投入一定数量物资与某种生产。第i阶段初还有资源y,用y表示状态,投入i中生产的资源为xi,(Oxiy),还剩下资源y-xi,并获得效益gi(xi)。续⑵用fk(y)表示有资源y投入于前k种生产方式所得到的最大收入。由最优化原理排序问题设有n个エ件需要在机床A,B上加工,每个エ件都必须经过先A后B的两道加工エ序,我们一号码i(l<i<n)表示第i个エ件,以Ai,Bi分别表示エ件i在A,B上的加工时间,由于エ序的不同,所用的时间也是不同的,因此,加工完这个エ件的总时间是排列顺序的函数,现在的问题是怎样安排加工顺序才使总时间最少?用(X,t)来描述状态,X表示在机床A上等待加工的工件集合,就是说,这是A已经把X以外的工件全加工完了,准备选择X中某个エ件加工,t表示B还需时刻t才能把X以外的工件加工完.续⑴在状态(X,t),决策集合是工件集合X,选定决策{i}属于X,就转入新的状态(X\{i},zi(t)),并获得效益.用最优化原理得到这是ー个递推公式,有{X}=0开始,直到X=n.最优排序法1：找出al,a2,…,an,bl,b2,…,bn中的最小数.2:若最小者为ai,则将工件i排在第一位,并从エ件集合中去掉这个エ件.3:若最小者为bj,则将工件j排在最后一位,并从エ件集合中去掉这个エ件.4:对剩下的工件重复上述手续,直到エ件集合为空集合时停止.例给定5个エ件,在A,B上的加工时间如下表所示.用上述方法,很容易得到最优化顺序是1 3 5 4 243775473A5432n确定性的不定期多阶段决策问题有的多阶段决策过程,给定一个状态集合XT,当状态xXT时,过程停止,这是阶段不确定的多阶段决策过程,如果经过有限阶段,状态x一定能进入XT，就是阶段数有限的,否则就是阶段数无限的.这类问题通常利用最优化原理得到・个函数方程来求解.主要有:1:最优线路问题.2:有限资源分配问题.不作详细讲述.运筹帷幄之中决胜千里之外运筹学课件网络分析NetworkAnalysis网络分析图与子图图的连通与割集树与支撑树最小树最短有向路最大流最小费用流最大对集图与子图图与网络无向图的基本概念网络的基本概念关联矩阵和邻接矩阵关联矩阵邻接矩阵主要结论子图无向图的基本概念无向图G：一个有序二元组（N,E）,记为G=（N,E）G的点集合:（例如:图（1）中的的点的集合）N=（1,2,3,4,5）是一个无向图的点的集合）G的边集合:E={eij}且eij={ni,nj}为右图无序二元组eij的端点:有eij={ni,nj},贝リ称ni和nj为eij的端点,且称eij连接点ni和川圈:两个端点重合为ー点的边（例如右图中的ell）孤立点：不与任何边关联的点（例如右图中的n5）345续(1)关联:一条边的端点称为这条边的关联邻接:与同一条边关联的端点称为是邻接的,同时如果两条边有一个公共端点,则称这两条边是邻接的有限图:点和边都是有限集合的图空图:没有任何边的图平凡图:只有一个点的图简单图:既没有圈也没有两条边连接同一对点的图续(2)完全图:每ー对点之间均有一条边相连的图二分图G=(N,E)：存在的一个二分划(S,T),使得G的每条边有一个端点在S中,另一个端点在T中完全二分图G=(S,T,E)：S中的每个点与T中的每个点都相连的简单二分图简单图G的补图:与G有相同顶点集合的简单图,且中的两个点相邻当且仅当它们在G中 不相邻网络的基本概念有向图G：ー个有序二员组(N,A),记为G=(N,A)G的弧集合:A={aij}且aij={ni,nj}为有序二元组,若aij={ni,nj},则称aij从ni连向nj,ni称为aij的尾,nj为aij的头,ni称为nj的先辈，nj称为ni的后继有向图G的基本图：对于G的每条弧用一条边代替后得到的无向图(有向)网络G:对(有向)图G的每条边(弧)都赋予ー个实数,并称为边(弧)的权，则连同它边(弧)上的权称为(有向)网络。关联矩阵关联矩阵示例右图的关联矩阵是右图的关联矩阵是34521342邻接矩阵示例图（7）的邻接矩阵是图（8）的邻接矩阵是342主要结论子图图的连通与割集图的连通无向图有向图图的割集概念主要结论无向图的路135426图G中路:ー个点和边交替序列(ni,eij,nj/--,nk,ekl,nl),简单路:边不重的路初级路:点不重的路回路：在G中,一条至少包含ー个边并且ni=nl的｛ni,nl｝路简单回路:边不重的回路初级回路：点不重的回路连通性点i和j点是连通的:G中存在一条(i,j)路G是连通的:G中任意两点都是连通的连通分支:G的极大连通子图命题621设G有p个连通分支,则G的邻接矩阵可以表示成分块矩阵有向路134256有向图G中的•条有向路：个点和弧的交错序列(ni,aij,nj,—,nk,akl,nl),记为有向路简单有向路:弧不重的有向路初级有向路：点不重的有向路有向回路：至少包含一条弧且ni=nj的(ni,nj)有向路简单有向回路:弧不重的有向回路初级有向回路：点不重的有向回路点i和点j是强连通的：G中存在一条(i,j)有向路,也存在一条(j,i)有向路G是强连通的：G中任意两点都是强连通的G的强连通分支：G的极大连通子图命题622设G有p个强连通分支,则G的邻接矩阵可以表示成如下形式:强连通性割集割集的性质树与支撑树树及其基本性质概念及符号基本性质支撑树及其基本性质概念及符号基本性质概念及符号树的基本性质概念及符号支撑树的基本性质最小树最小树及其性质求最小树的Kruskal算法算法步骤算例算法复杂性Dijkstra算法算法步骤算例算法复杂性最小支撑树算法步骤算例计算的迭代过程算法复杂性算法步骤算例计算的迭代过程算法复杂性最短有向路最短有向路方程求最短有向路的Dijkstral算法算法步骤算例算法复杂性最短有向路方程算法步骤算例计算的迭代过程算法复杂性最大流最大流最小割定理基本概念主要结论最大流算法算法步骤算例算法复杂性基本概念主要定理算法步骤算例计算的迭代过程算法复杂性最小费用流最小费用流算法规划形式算法步骤算例算法复杂性最特殊的最小费用流ーー运输问题规划形式算法步骤算例问题线性规划形式对偶规划算法步骤算例计算的迭代过程（1）Stababsta3,4,。1,2,3,4,。1,2,03,1,01,2,0stab5tab(+s,2)(+a,2)stab(+s,2)计算的迭代过程(2)staabstab(+s,2)stab(+a,2)(+b,2)stab(1,1)(+s,l)stab1,2,23,4,01,2,23,1,01,2,2计算的迭代过程(3)abstabb(-b,l)(+s,l)(+aコ)算法复杂性运输问题对偶规划算法步骤算例求如图所示运输问题的最优解1231234-45355040869991213714916初始原可行解(1)1520302010302131234续213123481014对偶解uV1126845169-1142175139810-268ww续(2)15-2030+20-10302131调整原始可行解续(3)213123403666101对偶解-1106665162（4）20- 45143713129091068续131234调整原始可行解续（5）102131234033662对偶解u

106635169143713129091068最大对集二分图对集基本概念主要定理二分图的最大基数对集基本思想算法步骤算例算法复杂性二分图的最大权对集ーー分派问题规划形式算法步骤算例基本概念主要定理基本思想算法步骤算例求下图a所示的二分图G的最大基数对集,若初始解如下图b所示1234567Aa1234567A98b迭代过程（1）1234567A98313234567A98333517810标号1234567A增广路1234567A98增广路迭代过程1234567A981257108(2)

234567A98增广路算法复杂性分派问题对偶规划算法步骤算例12345678求如图所示的二分网络中的最大权对集计算的迭代过程（1）=44400002312232标号234567812345684444000024241021标号标号标号增广路计算的迭代过程（2）1234533400001343202标号8123456781234023230011标号标号标号增广路计算的迭代过程（3）

345678标号标号123456781245678444010013431010标号标号增广路=2=1=1计算的迭代过程（4）23323010011240010标号=1=112345678标号运筹帷幄之中决胜千里之外运筹学课件排队论QueueingTheory基本模型M/M/1模型M/M/c模型其他模型结束语排队论基本的排队模型基本组成概念与记号指数分布和生灭过程基本组成输入来源队歹リ服务机构排队系统顾客服务完离开排队系统的三个基本组成部分.输入过程（顾客按照怎样的规律到达）；排队规则（顾客按照一定规则排队等待服务）；服务机构（服务机构的设置,服务台的数量,服务的方式,服务时间分布等）基本排队模型ー输入过程顾客来源有限/无限顾客数量有限无限经常性的顾客来源顾客到达间隔时间:到下ー个顾客到达的时间服从某一概率分布（指数分布）顾客的行为假定为在未服务之前不会离开当看到队列很长的时候离开从•・个队列移到另ー个队列基本排队模型ー队列/排队规则队列队列容量有限/无限排队规则先来先服务（FCFS）;后来先服务;随机服务;有优先权的服务;基本排队模型一服务规则服务机构服务设施,服务渠道与服务台服务台数量服务时间分布:指数,常数,k级Erlang基本排队模型ー记号方案ServerQueueArrival顾客到达时间间隔分布/服务时间分布/服务台数目/排队系统允许的最大顾客容量/顾客总体数量/排队规则(Kendall记号)M/M/レ??/??/FCFSM/M/1/??M:指数分布(Markovian)D:定长分布(常数时间)Ek:k级Erlang分布G:普通的概率分布(任意概率分布)基本排队模型ー记号系统状态=排队系统顾客的数量。N(t)=在时间t排队系统中顾客的数量。队列长度=等待服务的顾客的数量。Pn(t)=在时间t,排队系统中恰好有n个顾客的概率。s=服务台的数目。基本排队模型ー统计平稳条件下的记号??n =系统有n个顾客时的平均到达率(单位时间平均到达的顾客人数即是平均到达率)??n =系统有n个顾客时的平均到达率?? =对任何n都是常数的平均到达率.=对任何n都是常数的平均到达率.レ?？=期望到达间隔时间レ?？=期望服务时间?? =服务强度,或称使用因子,？?/(s??)统计平稳条件下的记号平均队长平均等待队长平均等待时间平均逗留时间L,W,Lq,WqLittle/sformula指数分布密度函数均值方差随机变量T分布函数??仃⑴t指数分布性质1??仃(t)??t??tfT(t)是ー个严格下降函数指数分布性质2无后效性不管多长时间什?。已经过去,逗留时间的概率分布与下ー个事件的相同.指数分布性质3儿个独立的指数分布的随机变量的最小有一个指数分布几个独立的指数分布的随机变量的和还是ー个指数分数的随机变量T(??l+??2+??3)Tl(??l)Tl(??2)Tl(??3)min指数分布性质4指数分布Poisson分布服务时间的概率在t时间内已经服务n个顾客的概率レ??:平均服务时间平均服务率=??指数分布性质5M/M/V??/??或M/M/1模型ー个基本的排列模型.ー个服务台,到达率??和服务率??都服从指数分布。M/M/1举例M/M/1/N/??固定长度排队意味着若到了最大系统容量顾客将不能进入系统.单一服务台,固定长度M/M/1/N/??举例增加更多服务台M/M/c所有服务台是空的概率P0,和所有服务台都在忙的概率P??,需要下面比较复杂的公式。M/M/c举例其他模型M/M/c/K/K顾客来源是有限的服务系统.例如:ー个饭店有X张桌子和丫个服务生服务来源有限的顾客.M/D/1服务时间不变的服务系统.D/M/1确定性到达模式,及指数分布服务时间.例如:医生赴约治病的时间表.M/Ek/1服务服从Erlang分布.例如:用相同平均时间去完成一些程序。结束语排队论是专门研究带有随机因素,产生拥挤现象的优化理论。也称为随机服务系统。排队论应用十分广泛。运筹帷幄之中决胜千里之外运筹学课件决策分析DecisionAnalysis决策分类确定性决策非确定性决策不确定性决策风险决策（1）目标（2）至少有2个以上的行动方案（3）不同方案得失可计算（4）决策环境确定大致概率完全不确定例1某石油公司计划开发海底石油,有四种勘探方案A1,A2,A3,A4可供选择。勘探尚未进行,只知可能有以下三种结果：S1:干井,S2：油量中等,S3:油量丰富,对应于各种结果各方案的损益情况已知,应如何决策?例2某洗衣机厂,根据市场信息,认为全自动洗衣机应发展滚筒式,有两种方案。A1:改造原生产线,A2：新建生产线。市场调査知,滚筒式销路好的概率为0.7,销路不好为0.3。两种方案下各种情况的损益情况已知,应如何决策?第一节不确定性决策例1电视机厂,99年产品更新方案:A1：彻底改型A2：只改机芯，不改外壳A3：只改外壳,不改机芯问:如何决策?收益矩阵事件方案高SI中S2低S3（万元）Al201-6A2980A3654SIS2S3Vi=max{Vij}Al201-620A29809A36546(-)乐观准则（最大最大法则）选Almax[maxVij](-)悲观准则（最大最小法则）选A3S1S2S3Vi=min{Vij}Al201-6-6A29800A3j6544jmax[minVij]maxVi=4i选Al（三）、折衷准则（乐观系数准则）SIS2S3Vil=maxVi2=min加权平均Al201 -620-69.6A298 0905.4A365 4645.2max=9.6加权系数a（〇??a??1）a=0.6max{a(maxVij)+(l-a)(minVij)}a=0.6选A2

（四）等可能准则A1A2A32313max=523max{1nnj=lSI S220 1 -69 8 06 5 4??Vij}S3Vi=555??Vij1选Al（五）、后悔值准则（最小机会损失）SI S2 S3maxAl 20 1 -6 0 7A2 9 8 0 11 0A3 6 5 4 14 3min=10SI1040S2101114S3{max{Vij}-Vij}例:产品,成本30元/件,批发价35元/件,当月售不完ー1元/件。每批10件,最大生产カ40件/月（批量生产与销售）,应如何决策?150102030 40Vi=??Vij00000 0010-1050505050190/520-2040100100100320/530-303090150150390/540-402080140200400/5AiSi第二节风险决策（一）、期望值准则（1）、矩阵法例1PjSIS2S30.30.50.2Al201-65.3A29806.7A36545.1SiAj??PjVij选A2例2Al 500 -200 290A2 -150 1000 195??PjVij分析当a=P(S1)为何值时,方案会从Al—A2当P(S1)=0.8 P(S2)=0.2时,E(A1)=0.8x500+(-200)x0.2=360E(A2)=0.8X(-150)+0.2X(1000)=80,选Al当P(S1)=0.6 P(S2)=0.4时E(A1)=220E(A2)=310,选A2一般:E(A1)=ax500+(l-a)(-200)=700a-200E(A2)=ax(-150)+(l-a)(1000)=-1150a+1000令El=E2 得a=0.65称a=0.65为转折概率0>0.65 选Ala<0.65 选A2⑵决策树法方案分枝概率分枝概率分枝 标自然状态的概率决策点 标决策期望效益值方案点 标本方案期望效益值结果点 标每个方案在相应状态下面的效益值例1SIS2TOC\o"1-5"\h\z0.4 0.6A1 100 -20A2 75 10电视机厂试生产三种电视机Ai(i=l,2,3)。市场大、小Sj(j=l,2)。生产:哪种?解:100-207510503012340.60.40.60.40.6A1A2A3P(S1)=0.4解:100-207510502823633840.60.40.60.40.6AlA2A3P(S1)=0.4??多级决策问题例2化工原料厂,由于某项エ艺不好,影响效益,现厂方欲改革エ艺,可自行研究(成功可能为〇⑹,买专利(成功可能为0.8)。若成功,则有2种生产方案可选,1是产量不变,2是增产;若失败,则按原方案生产,有关数据如下表。试求最优方案。按原工艺方案生产TOC\o"1-5"\h\z价低0.1 -100 -200 -300 -200 -300中0.5 0 50 50 0 -250价高0.4 100 150 250 200 600买专利(0.8)自研(0.6)产量不变增产产量不变增产(万元)最优决策买入专利,成功则增产,失败则保持原产量。⑶贝叶斯法(后验概率法)(Bayes法)处理风险决策问题时,需要知道各种状态出现的概率:P(??l),P(??2),…，P(??n),这些概率称为先验概率。风险是由于信息不充分造成的,决策过程还可以不断收集信息,如果收集到进ー步信息S,对原有各种状态出现概率估计可能会有变化,变化后的概率为P(??j??S),此条件概率表示在追加信息S后对原概率的ー个修正,所以称为后验概率。Bayes法就是ー种后验概率方法.P(??j??Si)通过概率论中Bayes公式计算得出Bayes公式:P(??j)P(Si????j)P(??j??Si)=P(Si)其中P(Si):预报为Si的概率,P(Si/??j):状态??j被调查预报为Si的概率例1某钻井大队在某地进行石油勘探,主观估计该地区为有油け?1)地区的概率为P(??l)=0.5,没油け?2)的概率为P(??2)=0.5,为提高勘探效果,先做地震试验,根据积累资料得知:有油地区,做试验结果好(F)的概率P(F????1)=0.9有油地区,做试验结果不好(U)的概率P(U????1)=0.1无油地区,做试验结果好(F)的概率P(F????2)=0.2有油地区,做试验结果不好(U)的概率P(U????2)=0.8求:在该地区做试验后,有油和无油的概率各为多少?解做地震试验结果好的概率P(F)=P(??l)P(F????1)+P(??2)P(F????2)=0.5X0.9+0.5X0.2=0.55做地震试验结果不好的概率P(U)=P(??l)P(U????1)+P(??2)P(U????2)=0.5X0.8+0.5X0.1=0.45用Bayes公式求解各事件的后验概率:做地震试验结果好的条件下有油的概率P(??l)P(F????1)0.459P(??1??F)===P(F)0.5511做地震试验结果好的条件下无油的概率P(??2)P(F????2)0.102P(??2??F)===P(F)0.5511用Bayes公式求解各事件的后验概率：做地震试验结果不好的条件下无油的概率P(??2)P(U????2)0.408P(??2??U)=二=P(U)0.459做地震试验结果不好的条件下有油的概率P(??l)P(U????1)0.051P(??1??U)=二=P(U)0.459某公司有资金500万元,如用于某项开发事业,估计成功率为96%,一年可获利润12%；若失败则丧失全部资金;若把资金全存在银行,可获得年利率6%,为辅助决策可求助于咨询公司,费用为5万元,根据咨询过去公司类似200例咨询工作,有下表:试用决策树方法分析该公司是否应该咨询?资金该如何使用?投资 投资成功 失败可以投资1542156次不宜投资38644次合计 192咨询意见实施结果合计T1:咨询公司意见:可以投资T2；咨询公司意见:不宜投资E1:投资成功E2;投资失败156P(T1)= xlOO%=0.7820044P(T2)= xlOO%=0.22200P(El)=0.96 P(E2)=0.04154P(E1/T1)= =0.9871568200次P（EひTl）= =0.01315638P（E1/T2