运筹学课件（山东大学）

《运筹学课件（山东大学）》由会员分享，可在线阅读，更多相关《运筹学课件（山东大学）（105页珍藏版）》请在装配图网上搜索。

1、运筹帷幄之中 决胜千里之外 运筹学课件 绪 论Introduction运筹学的概况最优化模型教学计划与方法考试与要求参考文献绪论运筹学的由来与发展运筹学的性质与特点运筹学的主要内容运筹学的发展趋势运筹学的学科地位运筹学概况名称的由来Operation Research运筹帷幄“史记” 运作研究发展历程运筹学的由来与发展二战以前萌芽二战期间产生五六十年代发展七八十年代成熟引入数学方法解决实际问题一定性与定量方法结合系统与整体性从全局考察问题应用性一源于实践、为了实践、服务于实践交叉学科涉及经济、管理、数学、工程和系统等 多学科 开放性不断产生新的问题和学科分支多分支问题的复杂和多样性运筹学的性质

2、与特点线性规划数学规划非线性规划整数规划动态规划学科容多目标规划双层规划组优化最优计数问题网络优化排序问题统筹图随机优化对策论排队论库存论决策分析可靠性分析运筹学的主要内容成熟的学科分支向纵深发展 新的研究领域产生与新的技术结合与其他学科的结合加强 传统优化观念不断变化 运筹学的发展趋势在数学学科中的地位运筹数学在系统科学中的地位系统工程1在管理科学中的地位管理与运筹学1与经济学的关系问题与方法1与工程科学的关系方法与应用1与计算机科学的关系核心算法与工具基础理论应用理论应用技术运筹学运筹学的学科地位模型要素变量一可控因素目标优化的动和依据约束内部条件和外部约束 研究内容建模 概念最优性条件

3、算法灵敏度分析 最优化模型 实例问线性规划模型建模分析线性规划模型模型线性规划模型教学计划数学规划以线性规划和整数规划为教授重点,组合优化部分主要讲网 络优化,而随机优化讲授排队论和对策论,其它部分作为选讲内容。教学方法以授课为主,案例分析与上机实习相结合。而讲课中主要培养用最优化 方法解决实际问题的能力。教学计划与方法考核内容理论方法一笔试50%应用能力案例分析30%计算能上机操作20%考试与要求韩伯棠,管理运筹学,高等教育出版社,北京,2000年徐光辉等,运筹学手册,科学出版社，北京,1999年胡运权等,运筹学教程,清华出版社,北京,1998年刘家壮,王建方,网络最优化,华中工学院出版社,

4、武汉,1987年管梅谷,郑汉鼎,线性规划,山东科学技术出版社，济南，1983年 参考资料运筹帷幄之中决胜千里之外线性规划Linear Programming运筹学课件线性规划线性规划问题可行区域与基本可行解单纯形算法初始可行解对偶理论灵敏度分析计算软件案例分析线性规划问题线性规划实例生产计划问题运输问题线性规划模型一般形式规范形式标准形式形式转换概念某工厂用三种原料生产三种产品,已知的条件如表21.l.l所示,试制 订总利润最大的生产计划453单位产品的利润（千元）2000523原料P3800420原料P21500032原料P1原料可用量（公斤/日）Q3产品Q2产品QI单位产品所需原料数量（公

5、斤） 生产计划问题问题分析模 型计算结果 运输问题 问题分析 模 型一般形式目标函数 约束条件 注 释 规范形式 标准形式 概 念 模型转换 约束转换实例目标转换变量转换约束转换 不等式变等式不等式变不等式 等式变不等式 不等式变等式 松弛变量剩余变量不等式变不等式例2.1.3把问题转化为标准形式可行区域与基本可行解图解法可行域的儿何结构基本可行解与基本定理图解法例2.2.1 解线性规划注 释可能出现的情况:可行域是空集可行域无界无最优解最优解存在且唯一,则定在顶点上达到最优解存在且不唯一,一定存在顶点是最优解可行域的儿何结构基本假设凸集可行域的凸性基本假设凸 集可行域的凸性问 题基本可行解与

6、基本定理基本定理问题基本 可 行解定义 基本定理 问 题 单纯形算法 理论方法算法步骤单纯形表算例理论方法定理2.3.1定理2.3.2定理2.3.3算法步骤 单纯形表算 例初始单纯形表迭代1迭代 2初始解 两阶段法说明两阶段法基本思想第阶段:通过求解辅助问题的最优基可行解得到原问题的初始基可行解。第二阶段:求原问题的最优解算例辅助问题原辅助题问与题的关系求辅助问题的三种情况算 例第1阶段第 1 阶段第1阶段第1阶段第1阶段第2阶段大M法说 明对偶理论对偶规划对偶理论对偶单纯形算法 对偶规划标准形式线性规划的对偶规划规范形式线性规划的对偶规划般形式线性规划的对偶规划实例标准形式的对偶规划规范形式

7、的对偶规划-一般形式的对偶规划实 例对偶理论*定理 2.5.1定理 2.5.2定理2.5.5对偶单纯形算法基本思想算法过程算例基本思想单纯形算法对偶单纯形正贝解正则解对偶可行解 正则解的单纯性表 规划无可行解 保持正则性 入基变量 算法过程 否初始正则解 检查可行 是则停止 得最优解 选出基变量 检查 是否无可 行解 是则停止 否 无最优解 选入基变量 计算典式检验数 算例迭代迭代迭 代灵敏度分析 概况改变价值向量改变右端向量概 况信息的不确定性信息的变化:价值向量一市场变化 右端向量一资源变化 系数矩阵技术进步认知的误差分析方法静态分析比较静态分析动态分析改变价值向量一般改变情况改变非基变量

8、的价值向量改变基变量的价值向量算例一般改变非基变量基变量算 例改变右端向量基本思想算例基本思想算 例计算软件LinDoLinGoMatlabLinDo输入模型求解点击求解按钮即可结果输入模型!注释内容,可用中文!目标函数:最大-max,最小-min,大小写不分max 3 xl+5 x2+4 x3!约束,以subject to开始subject to2 xl+3 x2<=15002 x2+4 x3<=8003 xl+2 x2 +5 x3<=2000end注意事项变量以字母开头,下标写在后面,系数与边量之间加空格不等号为:<尸(<),>=( >), =, &

9、lt产与 <等同变量非负约束可省略结束时以end标示结 果LP OPTIMUM FOUND AT STEP 3OBJECTIVE FUNCTION VALUEVARIABLEVALUEREDUCED COST0.0000000.0000000.0000001.0500000.6250000.300000XI375.000000X2250.000000X375.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.0000003) 0.0000004) 0.000000LinGo输入模型LinDo模式LinGo模式求解点击求解按钮即可结果LinDo输入模式m

10、odel: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=3

11、5 4;b=1500 800 2000;a=2 3 00243 2 5;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)

12、结 果Global optimal solution found at iteration:3Objective value:2675.000Variable ValueReduced CostC( 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.0000

13、000.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.000000Row Slack or Surplus Dual Price12675.0001.00000020.0000001.050000Scilab 函数命令 1： xJagr/f=lin

14、pro(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问题形式min p'*xs.t. C*x <= bxzlagrzf=linpro(pzCzb zx0)命令2xzlagrzf=linpro(p,C,bzcizcs zx0)问题形式min p'*xs.t. C*x &l

15、t;= bci <= x <= cs命令3xzlagrzf=linpro(pzCzbzcizcszme zx0)问题min p'*xs.t. C(jz:) x = b(j)z j=lz.zmeC(jz:) x <= b(j)z j=me+lz.zme+mdci <= x <= cs命令4xzlagrzf=linpro(pzCzbzcizcszmezxO zimp)问题形式s.t. C(:)x = b(j), j=l,meC(:)x <= b(j), j=me+l/./me+mdci <= x <= cs指定初始可行解xO命令5xlzcr

16、it=karmarkar(a/b/c/xO)问题形式min c&#O39;*xs.t. a*x = bx>=O注意事项命令2和3中xO可省略,但命令4和5中不可省略向量都是列向量,参数的顺序不可换命令3中等式约束必须在前面人力资源分配问题某个中型百货商场对售货人员(周工资200元)的需求经统计如下表为了保证销售人员充分休息,销售人员每周工作5天,休息2天。问应 如何安排销售人员的工作时间,使得所配售货人员的总费用最小?19七1816五14四1512人数星期模型假设每天工作8小时,不考虑夜班的情况;每个人的休息时间为连续的两天时间;每天安排的人员数不得低于需求量,但可以超过需求量问题分析因

17、素:不可变因素:需求量、休息时间、单位费用；可变因素:安排的人数、 每人工作的时间、总费用;方案：确定每天工作的人数,由于连续休息2天,当确定每个人开始休息的 时间就等于知道工作的时间,因而确定每天开始休息的人数就知道每天开始工作 的人数,从而求出每天工作的人数。变量:每天开始休息的人数约束条件:1 .每人休息时间2天,自然满足。2 .每天工作人数不低于需求量,第i天工作的人数就是从第i-2天 往前数5天内开始工作的人数,所以有约束:3 .变量非负约束:目标函数:总费用最小,总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息,所以总人数等于模型注 解该问题本质上是个整数规划问题,

18、放松的线性规划的最优解是个整数解,所 以两规划等价。定义整数变量用函数gin(xl).gin(x7);0-1整数变量为bin(xl)配料问题某化工厂要用三中原料混合配置三种不同规格的产品各产品的规格单价如表!,253550单价(元/公斤)不限原料I不少于25%原料II不超过50%原料I不少于50%原料!I不超过25%规格CBA产品问如何安排生产使得生产利润最大?352565单价(元/公斤)100100日最大供应量IIIIII原料原料的单价与每天最大供应量如表2配料问题案例问题问题分析模型求解结果分析问题分析变量约束条件目标函数变量生产计划就是要确定每天生产三种产品的数量以及非中产品中三中原料

19、的数量。而由于每种产品的数量等于三种原料数量之和,所以只要确定每天生产 三种产品分别含有的原料数量即可。所以变量就是每天生产三种产品所用的原料 数,设用于生产第i种产品的第j种原料数为约束条件规格约束约束条件资源约束目标函数总产值 总成本 总利润=总产值总成本 模 型求解运筹帷幄之中 决胜千里之外 运筹学课件整数线性规划Integer Linear Programming 整数规划 整数规划问题与模型整数规划算法计算软件应用案例整数规划问题 实例特点模型分类 应用案例 投资组合问题旅游售货员问题背包问题投资组合问题实例模型背景证券投资:把一定的资金投入到合适的有价证券上以规避风险并获得最大的

20、利润。项目投资:财团或银行把资金投入到若干项目中以获得中长期的收益最大。案例某财团有 万元的资金,经出其考察选中 个投资项目,每个项目只能投 资个。其中第 个项目需投资金额为 万元,预计5年后获利 （）万元，问应如何选择项目使得5年后总收益最大?模 型变量一每个项目是否投资约束总金额不超过限制目标一总收益最大旅游售货员问题背景案例模型旅游线路安排预定景点走且只走次路上时间最短配送线路货郎担问题送货地到达一次总路程最短案例有旅行团从出发要遍游城市,已知从 到 的旅费为,问应如何安排行程使总费用最小?模型变量一是否从i第个城市到第j个城市约束每个城市只能到达次、离开一次避免出现断裂每个点给个位势除

21、了初始点外要求前点比后点大目标总费用最小 背包问题 背景案例模型邮递包裹把形状可变的包裹用尽量少的车辆运走旅行背包容量一定的背包里装尽可能的多的物品实例某人出国留学打点行李,现有三个旅行包,容积大小分别为1000毫升、1500 毫升和2000毫升,根据需要列出需带物品清单,其中一些物品是必带物品共有 7件,其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。 尚有10件可带可不带物品,如果不带将在目的地购买,通过网络查询可以得知 其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表,试给出 个合理的安排方案把物品放在三个旅行包里。物品123456789

22、10体积200350500430320120700420250100价格15100705075200902030问题分析变量一对每个物品要确定是否带同时要确定放在哪个包裹里,如果增加一个 虚拟的包裹把不带的物品放在里面,则问题就转化为确定每个物品放在哪个包裹 里。如果直接设变量为每个物品放在包裹的编号,则每个包裹所含物品的总容量 就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中约束包裹容量限制必带物品限制选带物品限制目标函数一未带物品购买费用最小模型特征一变量整数性要求来源问题本身的要求引入的逻辑变量的需要性质一可行域是离散集合线性整数规划模型般整数规划模型0-1整数规划模

23、型混合整数规划模型一般整数规划模型0-1整数规划模型混合整数规划模型算法与线性规划的关系分支定界算法割平面算法近似算法与线性规划的关系整数规划放松的线性规划可行解是放松问题的可行解最优值大于等于放松问题的最优值注释最优解不一定在顶点上达到最优解不一定是放松问题最优解的邻近整数解 整数可行解远多余于顶点,枚举法不可取 分支定界算法算法思想算法步骤算例注释算法思想隐枚举法求解放松问题最优值比界坏最优解为整数最优值比界好最优解为非整数最优值比界好分支边界分支舍弃分支的方法定 界当前得到的最好整数解的目标函数值分支后计算放松的线性规划的最优解整数解且目标值小于原有最好解的值则替代原有最好解整数解且目标

24、值大于原有最好解的值则删除该分支其中无最优解非整数解且目标值小于原有最好解的值则继续分支非整数解且目标值大于等于原有最好解的值则删除该分支其中无最优解选,分支写出并求解放松问题,同时从分支集中删除该分支判定是否为整数解初始分支为可行解集,初始界为无穷大判定是否分支集空是停止当前最好解为最优解是否判定最优值是否小于当前界判定最优值是否小于当前界是否按非整数变量分支并加入分支集否是以最优解替代当前最好解最优值替代当前界算例注释求解混合整数规划问题,只对整数变量分支,对非整数变量不分支。对0-1整数规划分支时割平面算法算法思想算法步骤算例算法思想由放松问题的可行域向整数规划的可行域逼近 方法一利用超

25、平面切除要求整数解保留放松问题最优值增加割平面生成方法条件一保留整数解删除最优解整数可行解最优基可行解正则解算法步骤求放松问题的最优基可行解判断是否为整数解是停止得到最优解否在单纯性表中加入一列利用对偶单纯性算法求最优解算 例计算软件整数变量定义LinDo一般整数变量:GIN <Variable>0-1 整数变量:INT <Variable>LinGo一般整数变量:GIN( variable_name);0-1 整数变量:BIN( variable_name);算例算 例max 3 xl+5 x2+4 x3subject to2x1+3 x2<=15002 x2+

26、4 x3<=8003 xl+2 x2 +5 x3<=2000endgin xlgin x3应用案例分析人力资源分配问题应急设施选址问题人力资源分配问题某个中型百货商场对售货人员(周工资200元)的需求经统计如下表为了保证销售人员充分休息,销售人员每周工作5天,休息2天。问应 如何安排销售人员的工作时间,使得所配售货人员的总费用最小?19七18六16五14四121512人数星期模型假设每天工作8小时,不考虑夜班的情况;每个人的休息时间为连续的两天时间;每天安排的人员数不得低于需求量,但可以超过需求量问题分析因素不可变因素;需求量、休息时间、单位费用；可变因素;安排的人数、每人工作的时

27、间、总费用；方案 确定每天工作的人数,由于连续休息2天,当确定每个人开始休息的 时间就等于知道工作的时间,因而确定每天开始休息的人数就知道每天开始工作 的人数,从而求出每天工作的人数。变量每天开始休息的人数约束条件1.每人休息时间2天,自然满足。3.变量非负约束:目标函数:总费用最小,总费用与使用的总人数成正比。由于每个人必然在 且仅在某一天开始休息,所以总人数等于模型注解该问题本质上是个整数规划问题,放松的线性规划的最优解是个整数解,所 以两规划等价。定义整数变量用函数gin(xl)gin(x7);0-1整数变量为bin(xl)应急选址问题某城市要在市区设置k个应急服务中心,经过初步筛选确定

28、了 m个备选 地，现已知共有n个居民小区,各小区到个备选地的距离为 为了使得各小区能及时得到应急服务,要求各小区到最近的服务中心的距离尽可 能的短,试给出中心选址方案。问题分析该问题与传统的选址问题的主要区别在于其目标不再是要求费用最小, 而是要求最长距离最短。也就是离服务中心距离最远的小区离最近的服务中心距 离最小。变量：当中心的位置确定下来后,各小区对应的最近中心也就确定,所 以真正的变量也就是小区的位置。设问题分析为了便于说明问题引入间接变量,第i小区是否由第j个中心服务以及最远的距离约束条件小区服务约束问题分析最远距离约束中心个数约束目标函数:最远距离最小模型运筹帷幄之中 决胜千里之外

29、 运筹学课件 非线性规划Non-linear Programming非线性规划基本概念凸函数和凸规划维搜索方法无约束最优化方法约束最优化方法基本概念非线性规划问题非线性规划方法概述非线性规划问题例1曲线的最优拟合问题例2构件容积问题数学规划约束集或可行域 MP的可行解或可行点向量化表示当p=O,q=O时,称为无约束非线性规划或者无约束最优化问题。否则,称为约束非线性规划或者约束最优化问题。最优解和极小点非线性规划方法概述非线性规划基本迭代格式凸函数和凸规划凸函数及其性质凸规划及其性质凸函数及其性质凸规划及其性质约束集如果(MP)的约束集X是凸集,目标函数f是X上的凸函数,贝(MP)叫做非线 性

30、凸规划,或简称为凸规划。定理4.2.6凸规划的任一局部最优解都是它的整体最优解。维搜索方法精确维搜索方法0.618 法Newton 法非精确维搜索方法Goldstein 法Armijo 法0.618法(近似黄金分割法)Newton 法Goldstein 法Goldstein法步骤Armijo 法无约束最优化方法无约束问题的最优性条件最速下降法共喪方向法无约束问题的最优化条件最速下降法共甄方向法二次严格凸函数的无约束最优化问题F-R法步骤约束最优化方法约束最优化问题的最优化条件简约梯度法惩罚函数法其中(MP)约束最优化问题的最优化条件令K-T条件简约梯度法(4.5.12)Wolfe法步骤惩罚函数

31、法思想:利用问题中的约束函数做出适当的带有参数的惩罚函数,然后在原来 的目标函数上加上惩罚函数构造出带参数的增广目标函数,把(MP)问题的求解转 换为求解一系列无约束非线性规划问题。罚函数法障碍函数法罚函数法设法适当地加大不可行点处对应的目标函数值,使不可行点不能成为相应无 约束极小化问题的最优解。罚函数实际应用中,选取个递增且趋于无穷的正罚函数参数列其中* * * *罚函数法计算步骤障碍函数法在可行区域的边界上筑起一道“墻”,当迭代点靠近边界时,所构造的增广 目标函数值陡然增大，于是最优点就被“挡”在可行区域内部了。构造障碍函数障碍函数法步骤运筹帷幄之中决胜千里之外运筹学课件动态规划Dyna

32、mic Programming动态规划综述最优化原理确定性的定期多阶段决策问题确定性的不定期多阶段决策问题综述动态规划所研究的对象是多阶段决策问题。所谓多阶段决策问题是指类活动过程,它可以分为若干个相互联 系的阶段,在每个阶段都需要作出决策。这个决策不仅决定这阶段的效益,而 且决定下阶段的初始状态。每个阶段的决策确定以后,就得到一个决策序列,称为策略。多阶 段决策问题就是求一个策略,使各阶段的效益的总和达到最优。最优化原理?多阶段决策问题及实例例1例2例3多阶段决策问题?最优化原理性质用最优化原理求解例2例1多阶段资源分配问题设有数量为x的某种资源,将它投入两种生产方式A和B中:以 数量y投入

33、生产方式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)因

34、此，我们的问题就变成:求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)假设这个厂根据

35、需要可以日夜两班生产或只是日班生产,当开足日班 时,每个生产周期能生产商品15个单位,每生产个单位商品的成本为100 元。当开足夜班时，每生产周期能生产的商品也是15个,但是由于增加了辅 助性生产设备和生产辅助费用,每生产单位商品的成本为120元。由于生产能 的限制,可以在需求淡季多生产些商品储存起来以备需求旺季使用,但存储 商品是需要存储费用的,假设每单位商品存储一周期需要16元,已知开始时存 储为零,年终也不存储商品备下年使用，问应该如何作生产和存储计划,才能使 总的生产和存储费用最小?例2续(3)设第i个周期的生产量为xi,周期末的存储量为ui,那么这个问题用式子写出来就是:求xl,x2

36、,x6,满足条件:xl=5+ulx2+ul=5+u2x3+u2=10+u3x4+u3=30+u4x5+u4=50+u5x6+u5=80 xi 30,0uj,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),并且机器没有损坏,可以继

37、续再去开采金矿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)。我们的目的就是在每个阶段 都在它的决策集合中选择个决策,使所有阶段的总效

38、益达到最大。这样的多阶段问题称为动态规划。最优化原理动态规划最优化原理:个过程的最优策略具有这样的性质,即无论其初始状态及其初始决策如何,其以后诸决策对以第个决策所形成的状态作为初始状态而言,必须构成最优策略。最优化原理的性质对于多阶段决策问题的最优策略,如果用它的前步策略产生的 情况(加上原有的约束条件)来形成一个前步问题,那么所给最优策略的前阶段 的策略构成这前步问题的个最优策略。用最优化原理求解例2如果一,开始的存储量uO已经给定,要求最后一个周期结束时 有存储量un,那么最优生产和存储费用就完全由uO, un决定。对某一个周期k, 如果这个周期开始时有库存量uk-1,要求结束时有库存量

39、uk,那么它的生产数 量xk=sk+uk-uk-l,sk是这个周期的商品需求量,所以它的生产和存储费为f(xk)+16 uk-1,其中续(1)用Fk(uO,uk)表示开始的存储量为uO,第k个周期结束时存储 量为uk的满足前k个周期需要的前k个周期的最优生产和存储费用,由最优化 原理xk=sk+uk-uk-lzk=2,3,6xl=sl+ul-uOz让k=2,3,6,求出F6(u0,u6),就得到问题的解确定性的定期多阶段决策问题旅行售货员问题多阶段资源分配问题用最优化原理解某些非线性规划问题排序最优排序法旅行售货员问题旅行售货员问题是图论中一个著名问题,就是在网络N上找 一条从vO点出发,经过

40、vl,v2,vn各一次最后返回vO的最短路线和最短路程。 现把它看成一个多阶段决策问题。从vO出发,经过n个阶段,每个阶段的决策 是选择下一个点。如果用所在的位置来表示状态,那么状态与阶段数就不能完全 决定决策集合了,因为走过的点不需要再走,所以决策集合与以前选的决策有关。 用(vi,V)表示状态,vi是所处的点,V是还没有经过的点集合。在状态(vi,V) 的决策集合中,取决策vjV,获得的效益是vi到vj的距离dij,转入下个状态 (vj,Vvj),现在用最优化原理来找递推公式。续用fk(vi,V)表示从vi点出发，经过V中的点各一次,最后回到 vO点的最短路程,V是个顶点集合,|V|=k,

41、 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阶段资源分配问题的 最优

42、策略y在每个阶段总取Oyx的短点的值,并且用最优化原理解某些非线性规划问题假设有数量xO的物资可用于n种生产，若以x!投入第i种生产时可 得收益gi(xi),问应如何选取xi,使得xO用于n种生产时得到的总收益最大。这 个问题可以写成数学规划问题:续假设每个gi(xi)在内连续,显然F的极大值存在,这是一个特殊 类型的非线性规划问题,由于这类问题的特殊结构,可以把它看成一个多阶段决 策问题,并利用动态规划的递推关系求解。把数量为xO的物资投入n种生产方式,可以看成是n阶段决策 问题每阶段投入一定数量物资与某种生产。第i阶段初还有资源y,用y表示状 态,投入i中生产的资源为xi, (Oxi y)

43、,还剩下资源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以外的工

44、件加工完.续在状态(X,t),决策集合是工件集合X,选定决策i属于X,就转入新 的状态(Xi, zi(t),并获得效益.用最优化原理得到这是个递推公式,有X=0开始,直到X=n.最优排序法1：找出al,a2,an,bl,b2,bn中的最小数.2:若最小者为ai,则将工件i排在第一位,并从件集合中去掉这个件.3:若最小者为bj,则将工件j排在最后一位,并从件集合中去掉这个件.4:对剩下的工件重复上述手续,直到件集合为空集合时停止.例给定5个件,在A,B上的加工时间如下表所示.用上述方法,很容易得到最优化顺序是1354243775473 A5432n确定性的不定期多阶段决策问题有的多阶段决策过程,

45、给定一个状态集合XT,当状态xXT时,过程 停止,这是阶段不确定的多阶段决策过程,如果经过有限阶段,状态x 一定能进入 XT，就是阶段数有限的,否则就是阶段数无限的.这类问题通常利用最优化原理得 到个函数方程来求解.主要有:1:最优线路问题.2:有限资源分配问题.不作详细讲述.运筹帷幄之中决胜千里之外运筹学课件网络分析Network Analysis网络分析图与子图图的连通与割集树与支撑树最小树最短有向路最大流最小费用流最大对集图与子图图与网络无向图的基本概念网络的基本概念关联矩阵和邻接矩阵关联矩阵邻接矩阵主要结论子图无向图的基本概念无向图G： 一个有序二元组（N,E）,记为G=（N,E）G的

46、点集合:（例如:图（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)完全

47、图:每对点之间均有一条边相连的图二分图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的每条弧用一条边代替后得到的无

48、向图(有向)网络G:对(有向)图G的每条边(弧)都赋予个实数,并称为 边(弧)的权，则连同它边(弧)上的权称为(有向)网络。关联矩阵关联矩阵示例右图的关联矩阵是右图的关联矩阵是34521342邻接矩阵示例图（7）的邻接矩阵是图（8）的邻接矩阵是342主要结论子图图的连通与割集图的连通无向图 有向图图的割集概念主要结论无向图的路135426图G中路:个点和边交替序列 (ni,eij,nj/-,nk,ekl,nl),简单路:边不重的路初级路:点不重的路回路：在G中,一条至少包含个 边并且ni=nl的 ni,nl路简单回路:边不重的回路 初级回路：点不重的回路连通性点i和j点是连通的:G中存在一条(

49、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

50、的邻接矩阵可以表示成如下形式: 强连通性割集割集的性质树与支撑树树及其基本性质概念及符号基本性质支撑树及其基本性质概念及符号基本性质概念及符号树的基本性质概念及符号支撑树的基本性质最小树最小树及其性质求最小树的Kruskal算法算法步骤算例算法复杂性Dijkstra 算法算法步骤算例算法复杂性最小支撑树算法步骤算例计算的迭代过程算法复杂性算法步骤算例计算的迭代过程算法复杂性最短有向路最短有向路方程求最短有向路的Dijkstral算法算法步骤算例算法复杂性最短有向路方程算法步骤算例计算的迭代过程算法复杂性最大流最大流最小割定理基本概念主要结论最大流算法算法步骤算例算法复杂性基本概念主要定理算法步

51、骤算例计算的迭代过程算法复杂性最小费用流最小费用流算法规划形式算法步骤算例算法复杂性最特殊的最小费用流运输问题 规划形式 算法步骤算例问题线性规划形式对偶规划算法步骤算例计算的迭代过程（1）Stababs ta3,4,。1, 2, 01,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)a bstabb(-b,l)(+s,l)(+a )算法复杂性运输问题对偶规划算法步骤算

52、例求如图所示运输问题的最优解1231234-45355040869991213714916初始原可行解(1)1520302010302131234续213123481014对偶解uV1126845169-1142175139810-268ww续(2)15-2030+20-10302131调整原始可行解续(3)213123403666101对偶解-1106665162（4）20-45143713129091068续131234调整原始可行解续（5）102131234033662对偶解u106635169143713129091068最大对集二分图对集基本概念主要定理二分图的最大基数对集基本思想算

53、法步骤算例算法复杂性二分图的最大权对集分派问题规划形式算法步骤算例基本概念主要定理基本思想算法步骤算例求下图a所示的二分图G的最大基数对集,若初始解如下图b所示1234567Aa1234567A98b迭代过程（1）1234567A98313234567A98333517810标号1234567A增广路1234567A98增广路迭代过程1234567A981257108(2)234567A98增广路 算法复杂性 分派问题 对偶规划算法步骤 算例12345678求如图所示的二分网络中的最大权对集 计算的迭代过程（1）=44400002312232标号234567812345684444000024241021标号 标号 标号 增广路计算的迭代过程（2）1234533400001343202标号81234567812340232 30011标号标号 标号增广路计算的迭代过程（3）345678标号 标号123456781