运筹学 最新12.3

1、运筹学 Operational Research贵州大学理学院 周国利教授运筹学作为一门学科诞生于20世纪30年代末期，从第二次世界大战早期军事部门开始的，英国和美国军队中的运筹学小组诸如护航舰队保护商船队的编队问题；当船队遭受德国潜艇攻击时，如何使船队损失最小的问题；反潜深水炸弹的合理起爆深度问题；稀有资源在军队中的分配问题等。研究了船只受到敌机攻击时应采取的策略，他们提出大船应急转向，小船应缓慢转向的躲避方法，该研究成果使船只的中弹率有47%降到29%，研究了反潜深水炸弹的合理起爆深度后，德国潜艇的被摧毁数增加到400%。第二次世界大战后英、美的一些部门开始着重研究战略问题，如未来武器系统

2、的设计和未来战争的战略，1957年美国研究北极星导弹提前二年完成，由于运筹学在军事上的显著成功，很快就深入到工业、农业、商业及政府管理部门等，并得到了迅速发展。为了有效地应用运筹学，一般要遵循六条原则：（1）合伙原则，尤其是同实际部门的工作者合作；（2）催化原则，创新思想，突破常规的看法；（3）相互渗透原则，多部门协作，彼此渗透考虑问题；（4）独立原则，研究问题时，独立工作，不受干扰，（5）宽容原则，解决问题时，思路要宽，方法要多，（6）平衡原则，要考虑各种矛盾、关系的平衡；应用运筹学解决问题时，关健是建立数学模型，再选择数学软件进行计算，结合实际作出决策。第一章 线性规划及对偶问题Linea

3、r programming and Dual problem1、两个引例 引例1. 环保排污问题 设某条河流上下游有两个化工厂，如图所示化工厂1、2每小时排出污水分别为2万m3、1.4万m3，环保要求河水中污水含量不超过2，且化工厂1排入河流的污水到化工厂2有20%自然净化，两个化工厂处理污水的费用分别是1000元/万m3、800元/万m3，在满足环保的要求下，两个化工厂每小时应处理多少万m3的污水，可使得总费用达最省？解：（1）首先建立数学模型，设两个化工厂每小时分别处理污水万m3，称为决策变量； 目标是使总费用达到最省，即求最小值=1000+800，称之为目标函数，（受约束于）（近似模型）

4、化工厂1，11.6-0.8-0，化工厂2， 2 1.4，且有： 0 0(非负约束)称以上数学模型为线性规划问题，记为问题。（2）图解法求最优解（仅限于两个决策变量情形） 图中阴影部分围成可行区域D（本例由四条直线围成），且标出可行区域D顶点的坐标。目标函数等值线，令：=1000+800= 等值线的斜率，过2、4象限，并标出目标函数值减少方向，一簇相互平行的目标函数等值线既要在可行域D内，又要目标函数值达到最小，最优解一定可在某一顶点处取得，（此结论可用于问题的单纯形算法） 本例最优处理污水化工厂1、2为：=1, =0.8(万m3)最省费用=10001+8000.8=1640元。引例2.银行理财

5、的最优投资方法某银行有资金1亿元，拟投资两个理财项目，第一个项目利率为10% ，第二个项目利率为5%。银行要求第一个项目的投资额不少于3000万，第二个项目的投资额不少于第一、二项目投资总额的25%，如何理财可使银行利润最大？解：（1）数学模型设两个项目的投资额分别为万元，目标是使银行利润最大，即求=0.1+0.05 +10000 3000 0.25(+) 3 0 0（2）求最优解令=0.1+0.05 目标函数等值线的斜率=-2（并标出目标函数值增加方向），如图： 最优投资方案：=7500万，=2500万， Z* =0.17500+0.052500=875万元，为问题的最优值，即银行的最大利润

6、。2、问题的一般数学模型及标准型 求 是决策变量，是对应的价值系数，Z=为目标函数 (=,) (=，) 0 ， 为资源限制 为投入产出矩阵, 表第种资源的投入对第种产品的产出量。若引入价值行向量， 引入决策列向量 ， 资源列向量=，则问题的矩阵形式为：求（由矩阵乘法） (=，) 0。问题的标准形为： 求 0 。用，软件包计算时都要化为标准形。下面给出化标准形方法（1） 若目标函数是求，化为求最大值，仅需在目标函数上加一负号，即求。（2） 若约束条件为“”形式，可在不等式左边加上一个非负松弛变量0，可使等式成立。（3） 若约束条件为“”形式。可在不等式左边减去一个非负的剩余变量0（或松弛变量）使

7、等式成立。（4）若0，只需将等式或不等式两端同乘以-1即可。（5）若决策变量无非负约束，令其中：。（6）若决策变量0，则令0即可。3、问题的单纯形法及对偶问题 生产的最优安排问题（综合题型） 某工厂在一个生产期内生产甲、乙两种产品，需三种资源，如表所示单位甲产品资源数单位乙产品资源数资源限制资源2140资源1240资源1125单位利润2030 如何组织生产，可使工厂获利最大？（1） 建立数学模型设在该生产时期分别生产甲、乙两种产品为个单位，目标是使工厂获利最大，即：求=20+30 0 0（2） 图解法求最优生产条件 =-0 （为目标函数等值线的斜率） 最优生产条件=10, =15， 最大利润Z

8、*=2010+3015=650（单位） （3） 单纯形法，先化为标准形，求最大值即求=20+30 0 为松弛变量标准形约束条件中的3行及后3列组成3阶单位矩阵为基矩阵，对应的变量为基变量，单纯形表给出单纯形算法 ： 初始基本可行解为：，满足约束条件，为基变量为检验数，j=1,2,n当0时可得最优解。取 进基取出基2为主元素作行初等变换，将其化为1,且1所在的列其余元素化为0。进基出基为主元素，作迭代， 最优解， ，生产最优安排例中求=20+30 ，（资源约束） ，（资源约束） ，（资源约束） 0 0最优生产条件=10, =15， 最大利润Z*=2010+3015=650。单纯形法的检验数为：，

9、 得最优解（第一个考试题与它有关）。（4） 对偶问题若生产的组织者不准备安排生产，而是将设备出租，资源转让，在市场经济的条件下，如何定价？（涉及到资产评估问题）假设三种资源转让的附加值，分别为、10 生产一个单位的甲产品，分别用三种资源为2、1、1个单位获利20个单位，则厂方要求，20 生产一个单位的乙产品，分别用三种资源为1、2、1个单位获利30个单位，则厂方要求，30 购买方购买三种资源，组织生产另一类产品，则希望价格最省，即求， 称求 0是原线性规划问题的对偶问题，记为问题, 问题有三个决策变量，不可能用图解法，但由于对偶的对偶是原问题，若题目要求求的解，先转化为问题，用图解法求最优解（

10、=10, =15，）,再用互补松弛条件求出问题的最优解（成倍放大，最优解不变，最优值要变）。（5）影子价格对市场经济有调节作用 影子价格是指某种资源在公司、企业中的特定价格 由为问题的目标函数及多元函数求极值的必要条件，有，是目标函数对第种资源求偏导数（其它资源为常数），表明对第种资源的变化率的影子价格，由单纯形法最终表的检验数行中，松弛变量对应的检验数，变号即有 (资源) （资源） （资源）10 表明资源增加一个单位从4041， ， 其它资源不变，解方程组 ， 最优解 =10, =15， 最大利润仍为Z*=2010+3015=650，表明资源没有升值，按原价转让。20 表明资源增加一个单位，

11、从4041 ， ，其它资源不变，解方程组， 最优解 =9, =16， 最优值 Z*=209+3016=660，函数值增加了10个单位，表明资源升值，转让的附加值为10个单位。30 表明C资源增加一个单位，从2526 ，其它资源不变，解方程组， 最优解 =12, =14， 最优值 Z*=2012+3014=660，函数值增加了10个单位，表明C资源升值，转让的附加值为10个单位。40 若两种资源同时增加一个单位，分别从4041 2526，解方程组， 最优解 =11, =15， 最优值 Z*=2011+3015=670， 函数值增加了20个单位。50 若甲乙产品每单位的利润都为30，目标函数 =-

12、10 （为目标函数等值线的斜率）与斜率相同，直线上点点是最优解，如点（10,15），（15,10）都是最优解 最优值 Z*=3010+3015=750。公司经营决策：若某种资源的市场价格低于该公司的影子价格，则应该购进该资源扩大再生产，若某种资源的市场价格高于该公司的影子价格，则出售该资源以获得最大利润。（6）问题与问题的互补求 0的最优解，其对偶问题，求=20+30 0 0 可用图解法求最优解 最优解 =10, =15， 最大利润为Z*=2010+3015=650设原问题的最优解分别为，则由互补松弛条件，给出5个方程： 二项乘积中一项不为0，则另一项一定取0=10>0 =15>0

13、 =0 >0 >0 2*+3*=20 22*+3*=30 2*=10 3*=10=(20,30)=2010+3015=650=(0,10,10) =040+1040+1025=650原问题和对偶问题的目标函数值相等。（强对偶定理）4、 问题的一个应用：最优下料问题某建筑工地需要制作套钢架，每套钢架要用长为的圆钢各一根。已知原料长，如何下料，使用料最省？解：下料方法很多，最简单的想法是：在每一个原料上截取，的圆钢各一根，组成一套钢架，这样每制作一套钢架，就多余一根料头，制作套钢架，需要用原料根，剩余料头，显然不是用料最省的方法。如何巧妙搭配，才能既满足配套要求又使所用原料最省，这就是

14、所谓套裁。方法1：下料一根三根，用料，余料，表示，方法2：下料二根一根，用料，余料，表示，方法3：下料二根二根，用料，余料，表示，方法4：下料一根二根，用料，余料，表示，方法5：下料一根三根，用料，余料，表示，建立数学模型如下：求以上数学模型可用，软件包计算，最优下料方法为：，即方法1下料30根，方法2下料10根，方法4下料50根，总共需要原料长的圆钢90根即可制作套钢架。又若，的圆钢分别为129、100、72根，组成钢架，。其他应用有配料问题、生产工艺优化问题、有配套约束的资源优化问题、多周期动态生产计划问题、投资问题、运输问题及运输问题的扩展等。5、几点说明：（1）问题最优解的判定，问题的

15、标准形矩阵形式的约束条件中，对矩阵，不妨假设，即约束条件的个数小于决策变量的个数，且，称为满秩矩阵，即中至少有一个阶子式不为零，不妨假设前列组成的列向量组线性无关，令为一分块矩阵，又令，由，二边左乘得：，再令目标函数中的价值系数，则，由，当时，目标函数取得最大值，称为检验数矩阵，其坐标形式为，当检验数满足时，问题得最优解。（2）问题求 0，的对偶问题求 0。的理论性较强，对偶理论深刻揭示了原问题与对偶问题的内在联系，由对偶问题引伸出来的对偶解有着重要的经济意义，对偶理论有七个定理，在此不一一叙述，对偶解在对问题可作灵敏度分析，即价值系数、资源约束和投入产出矩阵中投入量的变化对最优解及最优值的影

16、响。（3）问题主要解决一个目标函数的最优化问题，但在实际问题中往往要考虑多个目标，如设计一个新产品的工艺过程，不仅希望利润大，而且希望产量高、消耗低、质量好、污染小、投入少等，由于需要同时考虑多个目标，则引入了目标规划，线性目标规划的图解法既难作而且仅限于二个决策变量，可将原多目标规划分解成一系列的传统的单目标线性规划，并引入正、负偏差变量，然后依次求解，最后按优先级别、综合评价决策出最优解和最优值，称之为线性目标规划的序贯式算法。（4）对于非线性规划，由无约束问题的最优解的必要条件，梯度是一个非线性方程组，求解非常困难，甚至根本无法得到解析解，因此求解非线性规划问题一般都采用数值计算的最速下

17、降法、牛顿法、共軛梯度法，非线性规划中对于有约束问题的最优性条件要用到库恩塔克条件、可行方向法、近似规划法及制约函数法，非线性规划的数学基础要求很深，求解规划问题的关健在于建立数学模型，非线性规划求解可用软件完成。第二章 运输问题（物流问题）1、问题的提出，设某种物质有个产地 、，其产量分别为，有个销地，、，其销量分别为，先讨论产销平衡问题，（总产量）（总需求量）表从第个产地运输该物质到第个销地的单位运价，在满足供需平衡条件下，如何组织运输可使总运费达到最省？2. 数学模型设ij表从第个产地运输该物质到第个销地的运输量，目标函数是使得其总运费达最省，即求： 表个产地运输该物质到第个销地的运量之

18、和等于第销地的需求量， 表第个产地运输该物质到个销地的运量之和等于第个产地的产量 （供需平衡）共个约束，ij0 ， ， 3.运输问题也是一个线性规划问题，由运输问题的特殊性，该问题一定有最优调运，由于中有一部分取零，可用表上作业法求最优解，以举例说明。例：某地区有三个煤矿，其年产量分别为=112，=164，=154（单位：万吨），有三个电厂，每年需求量分别为=144，=204，=82（单位：万吨），供需平衡。分别为4、8、8，16、24、16，8、16、24单位：万元/万吨。如何调运既要满足供需平衡又要使总运费最省。解：用表上作用法求最优调运。<1>用最小元素法求解初始调运方案，=

19、 =4（就近运输），并划去所在行的格子，用×表示，余下中最小元素为8。并划去所在列的格子，用×表示，余下中最小元素为16。并划去所在列，称表格中填数字的格子为有效数字格，恰为个，其余为空格，且满足供需平衡，初始总运费=4112+2482+1682+832+16122=5936万元。 销地产地产量4 × 1128 112 ×8 ×1120 016×24 8216 8216412 168 144 3216 10 12224 ×1544 8销量144204824304 012 840<2>检验是否为最优调运。1

20、6;首先对有效数字格建立位势方程组、分别表产销地的位势= + ，= 4 = + =4=24= + =12=16= + =4= 8 = + =4=16= + =125个方程6个未知数，有无穷多组解。令=0（规定），可表上作业。2°对空格的检验数，定义为= -（+ ），若所有0（求），则得最优调运。由= -（+ ）=8-（0+12）=-40初始调运不是最优的。（注意对有效数字格的检验数为零）。<3>调整。1°从检验数小于零的空格出发作水平或铅直线，若遇空格则只能按原方向画线。若遇上有效数字格可按原方向或转90°画线，回到原空格处形成一条闭曲线。（注意闭曲线

21、的顶点除起点在空格处，其余都在有效数字格内。）2°以闭曲线空格顶点为1，依次为2、3、4，令偶数顶点的运量（112，122）=112，作调整，奇数顶点格+（=112），偶数顶点格-，仍保持供需平衡。<4>再检验是否为最优调运。仍对有效数字格，建立位势方程组=+ ，令=0，产销地位势如表，且有=4-（0+0）=40 =8-（0+0）=80=16-（16+0）=0 =24-（8+0）=160最优调运： ，最省总运费：=8112+2482+1682+8114+1610=5488万元，节省了=448万元。4几点说明<1>若空格的检验数0，则最优调运唯一，若存在空格检验

22、数=0，则最优调运不唯一。<2>最小元素法有一个缺点，在按最小元素实施调运时，可能造成另一处调运的单价较高，总运费也较高。伏格尔给出最小元素法的改进。给出每一个产销地次小元素与最小元素的差异，分别称为行、列差。按行、列差中最大者的所在行，列中的最小元素先行调运。 以下用伏格尔法求最优调运：产销地的行、列差如表所示，其中最大者为8，一般取行、列标较小的先实施调运。，调整行、列差，仍选第2列的列差为8，调整行、列差； 有效数字格为=3+3-1=5个，对有效数字建立位势方程组： =+，令=0。产销地的位势如表：=4-（0+0）=40，=8-（0+0）=80，=24-（16+8）=0，最优

23、调运不唯一=24-（8+0）=160，以上调运为最优。 最小的总运费：=8112+1682+1682+862+1692=5488万元。 销地产地产量行差4×8 1128×11240168224×1682164016862169224×1548，168销差4， 888080<3>对与产销不平衡问题，可化为产销平衡问题求最优调运。1°若产大于销，供过于求。即。可虚设一个销地其销量=-，=0，若第列中有有效数字，表明产量仍在原产地，没有运出。2°若产小于销，供不应求，即，可虚拟一个产地，其产量=-，充分

24、大，第个产地没有有效数字。第三章 整数规划 若规划问题的决策变量取整数则称之为整数规划1、整数规划引例、消防站最佳布点问题设某市有6个行政区，每个行政区都可布消防站，当发生紧急情况时，要求15分钟内赶到出事地点，由于布消防站有较大费用，市政府希望布点以少为好，下表给出6个行政区相互到达的时间，给出最佳布点方案。123456101016282720210024321710316240121721428321201525527171715014620102125140上表为一对称矩阵，其中0表示在同一个行政区内，当发生紧急情况时，15分钟可赶到出事地点。解：引入决策变量： 设目标函数是使布点以少为

25、好，即求 + 1（1,2行政区至少有1个布点）， + +1（对第二行政区）， + 1（对第三行政区）， + 1（对第四行政区）， +1（对第五行政区）， +1（对第六行政区），或1，最优解=1，=1，=0 ， =1、3、5、6。第2个行政区布点可兼顾1、6行政区，第4个行政区布点可兼顾3、5行政区。例2最优投资方案问题。美国公司有资金1100万，拟向四个项目投资，可调动研发人员22人。四个项目需投资额分别为650、500、550、400（万），研发人员分别为16、8、7、5（人），净现值分别为900、700、650、600（万），且要求1、4项目不能同时研发，给出最优投资方案，使公司收益最大。

26、解：<1>建立数学模型 设 目标函数是使公司收益最大，即求 650+500+550+4001100 16+8+7+522 +1 =0或1，<2>求解：决策变量4个，每个仅取2个值，共有变量组合数为=2=16种。.隐枚举法：任取一个可行解：如，则，可增加一个约束条件，900+700+650+600900称之为过滤条件，凡目标函数值不超过900的不予考虑，又得可行解，修改过滤条件900+700+650+6001350，其余不是可行解。最优投资方案为：=0，=1，=1，=0 Z*=13502巴拉斯改进算法 首先作变换使目标函数中的价值系数全部变为正数，即若0，令，当=0时，=

27、1，又当=1时，=0，仍是0-1变量。其次将目标函数按价值系数（已全部为正数）的大小重新排序，可从大到小。然后按目标函数值从大到小取变量组合，都不是可行解。其目标函数值逐渐下降，按此取法，一旦是可行解，一定是最优解，本例中是可行解，一定是最优解，一般隐枚举法可节省40%以上的计算，改进算法，可节省60%以上计算。2、最优指派问题(考试要求)<1>问题的提出，个人（个工程队）被指派去完成项工作，规定每个人仅能承担项工作中的一项工作，每一项工作必须由一人承担，由于每一个人完成项工作的效率不同，则有效率矩阵其中表第个人完成第项工作的效率（用时最短，费用最省，收益最大，利润最高等）如何指派

28、可使效率最高。<2> 数学模型，引入决策变量 1 第个人被指派去完成第项工作令=0 第个人不被指派去完成第项工作目标函数是求 =1，2，表对第项工作个人仅有一个人被指派去承担。 =1，2，表第个人对项工作仅能承担一项。=0或1，=1，2，最优指派一定存在，由于指派方式有！种，但仅有个取1，其余全部取0，可用矩阵变换法求解。例1.某公司开发一种新产品，拟推向国际市场，需将产品说明书译成英、法、德、俄四种语言。公司派四名工程师，承担该项任务，每位工程师翻译一种语言，下表给出译文的用时，给出最优指派，以使总用时最短。 min min 0 0 4 2（1）求效率矩阵C中每一行每一列最小元素

29、，使每一行（列）所有元素减去对应的最小元素，使得每一行（列）至少出现一个零元素。（2）从零元素最少的行（列）圈零用表示。并划去圈零所在列（行）其余零元素用表示。（3）若圈零的零元素恰有个（=4），令其为1，其余元素令其为0得最优指派矩阵。表工程师，=1,2,3,4表英、法、德、俄四种语言，j=1,2,3,4 Z=4+4+9+11=28例2.某公司有四个环保项目拟由四个工程队承建，每个工程队仅能承建一个项目，给出最优指派，使总费用最省。效率矩阵单位：万元。 min min0 2 0 0 minC=2 或minC=4 ，为最优指派矩阵。解： 1 第个工程队被指派承建第个项目设0 第个工程队不被指派

30、承建第个项目求： =1，=1,2,3,4表对第个项目4个工程队仅有一个工程队被指派去承担。 =1，=1,2,3,4 表第个工程队对4个项目仅能承担一项。=0或1表第个工程队 =1,2,3,4表第项项目 =1,2,3,4以下用矩阵变换法，前3个步骤与例1相同，（4）若圈零的零元素个数小于（=4），则要增加零元素。首先求覆盖所有零元素的最少直线数，1°对未圈零的行打2°对打的行含零元素的列打3°对打列中含圈零的所在行打4°对未打的行及打的列画直线即为覆盖所有零元素的最少直线数其次，求出未被直线覆盖元素中最小元素，将打行所有元素减去该最小元素及打列中元素加上该

31、最小元素，重复以上过程，直至得最优指派矩阵。 最省总费用Z=140万 为最优指派矩阵 Z=140万元<3>求 =1 =1，2，n =1 =1，2，n =0或1可转化为最小值题求最优指派取（表个元素中取最大者）令构造一个新的效率矩阵= Z=欲求，即求 用作矩阵变换。3、整数规划问题的分支定界法例5.某房开公司在某时段内拥有土地30000m2，拟开发两种商品房，甲种每栋占地2500m2，获利10000万，乙种每栋占地4000 m2，获利20000万，由市场需求甲种住房不超过8栋，乙种住房不超过4栋，给出最优决策，使公司获利最大。解 （1）建立数学模型 设甲、乙两种住房分别修建、栋，求M

32、axZ=10000+20000 2500+400030000 8 ， 4， 0 0 且为整数 （2） 称整数规划问题为A，其最优值为Z*,去掉整数约束为一个LP问题，称为规划，图解，、求解，=0最优解=5.6, =4Z0*=10000×5.6+20000×4=136000定界 0=13600020 分支，任取一个非整数解： 5 =5.66 （1）附加一个约束条件5,称为问题，求解 最优解： =5 , =4， 最优值为 =10000×5+20000×4=130000 ，已是一个整数解， 修改下界： 130000136000 并剪支； （2）附加约束条件6，

33、称之为问题，求解， 最优解： =6 , =3.75， 最优值为 =10000×6+20000×3.75=135000， 修改上界：130000135000， 上述分支不损失任何一个整数可行解；30 分支 ， 3 =3.754（1）附加3,称之为问题，求解最优解： =7.2 , =3 最优值为=10000×7.2+20000×3=132000 修改上界： 130000132000 （2）附加4，称之为问题，无可行解，剪支40 分支， 7=7.28 （1）附加7,称为问题，求解， 最优解： =7 , =3 最优值为=10000×7+20000

34、15;3=130000，剪支， (2)附加8，称之为问题，求解， 最优解：=8 , =2.5 最优值为=10000×8+20000×2.5=130000，剪支50 两组最优解 =5 =7=4 =3 =130000万分析占地面积，（I）2500×5+4000×4=28500m（最优解） （II）2500×7+4000×3=29500m2 以上过程可用框图示意B0x1*=5.6, x2*=4Z0*=136000 x15x16B2x1*=6, x2*=3.75Z2*=135000B1x1*=5, x2*=4Z1*=130000剪支13000

35、0136000X24X23B4无可行解B3x1*=7.2, x2*=3Z3*=132000剪支130000132000X18X17B5x1*=7, x2*=3Z5*=130000B6x1*=8, x2*=2.5Z6*=130000剪支剪支分析两种最优解，最优决策为=5 =4 =130000万第四章 网络最短路及应用1. 给定一个图，个顶点集，条连结顶点的边集。每一条边赋权（路长、费用），称为赋权图，规定图的方向，称为有向图，每一个顶点有边关联，称为连通图，有向赋权连通图称为网络。2. 给定一个有向赋权连通图，从任一顶点出发到各顶点，求其最短路，用标号，给一个顶点以标号，为临时性标号，在标号过程

36、中可以修改。给一个顶点以标号，为永久性标号，标号过程中不予修改，若图的每一个顶点得以标号，则可给出起点到各顶点的最短路线和路长。例1、 单行线交通网络图的最短路问题，如图示边旁的数字表路长，求到各点的最短路线和路长。用标号法求最短路问题。（1） 令=0，等式右边的数表路长， （2） 是刚获得标号的点，检查图G中与的关联边，修改相应标号的点，检查， 改=min（+,）= min（0+6,+）=6 ， 表从第i个顶点到第j个顶点的路长（边权），查，改=2，查，改=1，比较所有标号的点，取min 令（3） 查，改=min（+,）=11， 比较标号的点取min令（4） 查，改= min（2+3,6）=

37、5， 不查，因V4 已得标号，不再改变， 比较标号的点取min，令（5） 查，改=6， 比较标号的点取min，令（6） 查，改= min（6+4,11)=10， 查，改=11，查，改=12， 查，改=18， 比较标号的点取min，令（7）查改=11， 比较取min，令（8）查，改=12， 比较取min,令（9）查，改=15 ， 令 用逆推算法给出最短路线。如 132 589最短路长为15例2、网络最短路的应用：设备更新问题。某公司第一年年初购置一台设备，每年年初作出决定，继续使用旧设备，要支付维修使用费，若更新一台设备要支付购置费，作一个五年更新计划，使总费用最省。单位：万元。年限第一年第二年

38、第三年第四年第五年役龄（年）0-11-22-33-44-5维修使用5681118购置费1112131414残值43210解：把这个问题化为最短路问题。用点表示第年年初购进一台新设备，虚设一个点，表示第五年年底。边表示第年初购进一台新设备，一直使用到第年年初所需支付的购买、维修使用的全部费用，用边上的数字表示，即：，构成有向赋权连通图。用标号法求最短问题（使总费用最省）。（1）令=0，等式右边的数表费用，（2） 查，改，查，改，查，改，查，改，查，改，比较所有标号的点，取min，令（3）查，改，查，改，查，改，查，改，比较所有标号的点，取min，令（4）查，改，查，改，查，改，比较所有标号的点，

39、取min，令（5）查，改，查，改，比较所有标号的点，取min，令（6）查，改，令计算结果表明：最短路为，最短路长为49，即在第一年、第三年初各购买一台新设备为最优决策，总费用为49万元。3、最小生成树问题：（其广泛用于电线、电话线，天然气管道、水管、工厂生产流水线等），给定一个图，个顶点集，条连结顶点的边集。每一条边赋权（路长、费用），在赋权图如何去掉某些边，使得任意两个顶点仅有一条道路可通，即由图生成一个树，使得总的树权之和达到最小，即求最小生成树。由是一个树的充分必要条件是中没有圈，任意两个顶点仅有一条道路可连，且中的边数等于顶点数减1，即为，最小生成树是从图出发，用破圈法或避圈法去掉某些

40、边权最大的边，形成一个树，且使总的树权和达到最小值。例3、用破圈法求下图的最小生成树。5V2V8422V44V65V13214V10V5V763573V38V9解：如图中有10个顶点，任取一个圈去掉边权最大的边，使形成一个树不含圈，每二个顶点间有路相连，且边数=9=101=顶点数减1，最小生成树的树权和为26.V2V8422V44V65V1321V10V5V773V3V94、用避圈法求下图的最小生成树。52V5V2V82644625V933V343V66V1V117584411V43V72V10解：如图中有11个顶点，取边权最小的生成树枝，避开生成圈，使每二个顶点间有路相连，且边数=10=11

41、1=顶点数减1，最小生成树的树权和为22.2V5V2V822V3V633V93V1V1111V43V72V104、最大流问题：（其广泛用于交通运输网络中的人流、车流、货物流、供水网络中的水流、天燃气中的供气流、金融系统中的现金流、通讯网络中的信息流及大数据流等）。（1）设有向连通图，的每条边上有非负数称为边的容量，这样的网络称为容量网络，记为（2）对任一中的边有流量，称集合为网络上的一个流，流为可行流，满足：，容量限制条件：对中的每条边，有，平衡条件：对中间点，有，即中间点的物资的输入量与输出量相等，且对收、发点，有 ， 为网络流的总流量。，对容量网络，若为网络中从到的一条链，给定向从到，对上

42、的边凡与同向的称为前向边，其集合用表示，凡与反向的称为后向边，其集合用表示，若在上满足，则满足上方表达式中为非饱和边（弧），满足下方表达式中为非零流边（弧），若在上满足上方表达式或满足下方表达式，则称是中的从到的（关于的）可增广链或可扩流路。（3）割集和最小割集，将顶点集分为二个子集，（补集），且有，称是的一个割集，以中的顶点为起点，以中的顶点为终点的边集的容量之和称为这个割集的割量，所有割集中割量最小的割集称为最小割，其对应的边称为网络的咽喉或瓶颈。最大流问题是对给定的一个容量网络，先找出一个初始可行流（可以是零流）求该网络的最大流，且满足最大流量等于最小割量，并找到该网络的咽喉或瓶颈。例5

43、、求容量网络的最大流及最小割。（4,4）（4,3）V11111V3（5,4）（3,3）(5,3)(1,1)(1,1)（1,0）(3,0)（1,0）VsVt（5,2）（4,2）(4,1)（5,1）V2(2,2)V4解：该容量网络中有6个顶点，、分别是起点、终点，边旁的数=（容量，流量），若令，则划分的割量=4+2=6，初始流为=3+1=4，（1）标号过程：从起点开始，尽快找到一条可扩流路，即给终点标号，、给起点标号，0表示起点，表可扩流量，、不能标号，因为饱和边，标号，表的前一个顶点为，表该条边可扩4个流，、对标号，其中表逆向边的前一个顶点为，为非零流边， ，、对标号，表的前一个顶点为，、对标号

44、，表的前一个顶点为，1表可扩流量，得一条可扩流路：，或：，及，（2）调整过程：、调整量，即对终点标号的第2个坐标，、将前（顺）向边流量加，后（逆）向边流量减， 图中边旁的红色数字表调整后的流量。（3）标号过程：、对起点标号，、对标号，不能标号（零流边），不能标号（饱和流边），标号过程结束，。对最后的标号过程中已标号的顶点集合为，其余顶点集合为，得最小割集，且有：最小割量=3+2=5=最大流量。例6、求容量网络的最大流及最小割。（5,2）V111（5,4）（4,4）V4（3,1）(3,3)（5,5）(4,2)(4,2)V2V5（4,4）VsVt（4,3） （3，2）（3，0）（3，3）（3,2）

45、（5,5）(2,2)(5,4)（4,2）（3,3）V3(3,2)V6解：该容量网络中有8个顶点，、分别是起点、终点，边旁的数=（容量，流量），若令，则该割集划分的割量为=5+3+3+2+4=17，初始流=5+2+2=9，（1）标号过程：从起点开始，尽快找到一条可扩流路，标号，标号，标号，标号，得一条可扩流路：，（2）调整过程：、调整量，即对终点标号的第2个坐标，、将前（顺）向边流量加，得，（3）又进入标号过程：标号，标号，标号，标号，标号，标号，得一条可扩流路：，（4）调整过程：（图中边旁的红色数字表调整后的流量）、调整量，即对终点标号的第2个坐标，、将前（顺）向边流量加，得，后（逆）向边流量

46、减，（5）再进入标号过程：标号，标号，不能标号（饱和流边），标号过程结束。最大流。对最后的标号过程中已标号的顶点集合为，其余顶点集合为，得最小割集，且有：最小割量=5+4+3=12=最大流量。第五章 动态规划动态规划是解决互相联系的多阶段决策问题，如最短路问题，最优采购与销售决策问题，最优生产与存贮问题，复合系统可靠性最优设计问题等等，求解动态规划是用贝尔曼原理，即整个过程发展到某一个阶段，不论该过程的初始条件如何，也不论该过程在某一个阶段是如何形成的，从该阶段开始，以后每一个决策都是最优决策，即一个全过程的最优决策是由每一个子过程的最优决策组成的。例1最短路问题如图求A点到G点（各点）的最短路线和路程。（1）用逆序标号法给出各点到G点的最短路线和路程。（2）用顺序标号法给出A点到各点的最短路线和路程。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G536786316835338411222336625533418051317313610810101297117138131397131