运筹学教案(胡运权版)

土木工程与建筑学院教师备课纸第．当目标函数变(=2\＊romanii），就是要了解第三优先级中两目标权系数取值对原解的影响。表4—90000013/233/45/4100000010—10001001/21—1/41/4-1/2—11/4—1/41/201/4—1/4-1/20-1/41/4001000—10P1P2P3P4000000001001000000W2/4—101—W2/4100W1—W2/4000W2/40000000W20二。课堂练习(20分钟）三。课堂小结（5分钟）四。布置作业授课题目：第五章整数规划第一节:整数规划的数学模型及解的特点第三节：分支定界法教学目的与要求：1.知识目标:掌握整数规划的概念、类型和作用及其求解方法概述；掌握分支定界法的基本概念与求解思路;2。能力目标：掌握分支定界法的求解步骤；3.素质目标:培养学生良好的职业道德、树立爱岗精神教学重点：1、分支定界法的基本概念；2、分支定界法的操作原理与步骤。教学难点：1、分支与定界的方法；2、图解法在分支定界法中的应用。教学过程：1.举例引入(5分钟）2.新课讲解（80分钟）（1）分支与定界原则与方法(20分钟）（2）分支定界法操作步骤（40分钟）（3）学生操作（20分钟）3.课堂小结（5分钟）5.布置作业《整数规划：定义、类型、求解综述和分支定界法》（2课时）【教学流程图】举例引入整数规划整数规划的定义与分类整数规划的定义、分类与求解综述整数规划的松驰问题整数规划的几种求解方法分支方法定界方法分支定界法的求解过程解的搜索法最优解的确定课堂练习（结合例题讲解进行）课堂小结布置作业【教学方法】本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法,任务是师生活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力,竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助,共同分享劳动果实,从而激发了学生的团队意识，达到理想的教学效果。【教学内容】一、教学过程：举例引入整数规划：（5分钟)（1）整数规划的定义（2）整数规划的分类（3）整数规划的求解综述导入提问：怎样运用分支定界法？（二）新课：第五章整数规划第一节整数规划的数学模型及解的特点一、整数规划的定义与分类二、整数规划的求解方法综述第三节分支定界法主要思路1、要求一部分或全部决策变量必须取整数值的规划问题称为整数规划。不考虑整数条件，其相对应的线性规划问题叫该整数规划的松弛问题。求解整数规划时,首先求解与它相对应的松弛问题，如果它的松弛问题的最优解满足整数要求，则得该整数规划的最优解，否则通过增加新的函数约束来缩小其松弛问题的可行域,将原整数规划模型分为两个子规划模型，并除去可行域中的无整数解的部分，达到分枝的目的。然后对每一个子规划模型的松弛问题再求解，以此类推,并不断定界，最后求得原问题的最优解。2、分枝的方法:选择目标函数中系数绝对值最大的变量先分枝；选择与整数值相差最大的非整数变量先分枝；人为地按变量的相对重要性进行选择.3、定界与剪枝1）定界方法：①求解整数规划时，如果解它的松弛问题得到的不是一个整数解，则最优整数解一定不会优于所得松弛问题的目标函数值,即松弛问题的的解必是整数规划问题的目标函数值的一个界,它对于最大值问题是上界，对于最小值问题是下界。②如果在求解整数规划的松弛问题的过程中已经得到了一个整数解，则最优整数解一定不会劣于该整数解，因此该整数解可构成最优整数解的另一个界，对于最大化问题它为下界，对于最小化问题它为上界。③以上讨论可用不等式表示如下:———松弛问题的解；———目前已找到的整数解,-—-—最优整数解；—--上界，—-—下界.则最优整数解满足：对于最大化问题:；对于最小化问题：。显然如能找到一种方法,或降低上界或提出高下界，最后使得上界等于下界，就可以搜索得到最优整数解.2)求解任何一个问题或子问题都有三种结果：子问题无可行解,此时无须继续向下分枝，将其剪枝；得到一个非整数解，继续向下分枝；如得到一组整数解，则不必继续向下分枝,因该点有整数解而被关闭。二、例题分析例1求解下列整数规划：G(4.81，1.82）G(4.81，1.82）第一步：用图解法求出原整数规划问题的松驰问题的解.对=4.81按和进行分支,得到原整数规划问题的松驰问题的两个子松驰问题如下。然后对原整数规划问题的松驰问题进行定界（上界与下界）。两个子问题由原问题的松驰问题分别加上分支的两个约束条件组成，再用图解法求出它们的解。和54G(4.81，1.82）54G(4.81，1.82）第二步:根据对节点分支的三种情况：剪支、停止分支和继续分支,对上述两个子问题进行继续分支。又分别得到两个子问题。如此下去,是否无穷次分支?需由定界来确定.第三步：最后如果得到一个整数解,即为最优整数解；如得到几个整数解，取目标函数值最大者为最优整数解。问题B问题B1问题B2问题B1问题B2问题B3问题B4问题B5问题B6三、课堂小结四、学生作业，安排下次课内容。授课题目：第五章整数规划第二节：解整数规划的割平面法教学目的与要求：1.知识目标：掌握解整数规划的割平面法的概念与求解思路；2.能力目标：掌握解整数规划的割平面法的求解步骤；3.素质目标：培养学生良好的职业道德、树立爱岗精神教学重点：1、割平面法的概念与求解思路;2、割平面法的操作原理与步骤。教学难点：1、割平面法的概念与求解思路；2．单纯形表的最终表结构；2、割平面法的操作原理与步骤.教学过程:1。举例引入(5分钟）2。新课讲解（80分钟）（1）割平面法的概念（20分钟）（2)割平面法的求解思路(20分钟）（3）割平面法的求解步骤（20分钟）（3）学生操作（20分钟)3。课堂小结（5分钟）5。布置作业《整数规划：割平面法》（2课时）【教学流程图】举例引入整数规划的割平面法解整数规划的割平面法的基本思路单纯形法的最优表的结构割平面方程的确定解整数规划的割平面求解过程插入割平面约束的单纯形表对偶单纯形法用割平面方程求解整数规划时解的收敛性课堂练习（结合例题讲解进行）课堂小结布置作业【教学方法】本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和完成教学内容的主要方法,任务是师生活动内容的核心，在教学过程中，任务驱动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而激发了学生的团队意识，达到理想的教学效果.【教学内容】一、教学过程:举例引入整数规划:(5分钟）（1）整数规划的定义（2）整数规划的分类（3）整数规划的求解综述导入提问：怎样运用分支定界法？（二）新课：一、割平面法（一）基本原理线性规划的任一约束方程是n维空间的一个半平面，故先用单纯形法解它的松弛问题得最优解，若满足整数向量,则的最优解.若不全为整数，则设法给松弛问题增加一个线性约束条件(叫割平面方程)，它将松弛问题的可行域割去一块，且这个非整数解恰恰在被割掉的区域内，但原问题的任何一个可行解都不会被割去。若把原松弛问题的最优单纯形表记为，把增加了割平面方程的问题记为，为原问题的一个改进的松弛问题，用对偶单纯形法求解，若得到的最优解为整数向量，则计算结束，否则对再增加一个割约束，形成问题,…，直到得到最优整数解。(二）例题分析例1用割平面法求解纯整数规划:解1、松弛问题的单纯形表为：目标函数1100常数决策变量基变量最优表11013/41/410—1/41/47/43/400-1/2—1/2-5/22、求割平面方程割平面方程并不惟一,一般取基变量的小数部分具有最大绝对值的变量所在行的约束方程为导出方程,能够更快地得出最优整数解。这里选取第二个约束，写出约束方程:(1)将上式左边的非基变量的系数和右端常数写成一个整数和一个非负真分数之和：（2）把上式系数为真分数的各项移到等式右端，将整数移到左端：（3）因为整数,原整数规划约束条件中各系数和右端常数也为整数，所以也为整数。由于上式左边为整数，右边也应为整数.又，由于从所以3/4减去两个正数必有：（4)得：（因上式左边为整数)（5）为避免引入工变量，将上式改写成：（6）加入松弛变量，化为等式约束：（7）（6）式和（7）式分别为割平面约束条件和割平面约束方程。将（7）式添加到原的约束条件中，得：由灵敏度分析可知，增加一个割平面约束，只需把（7）式加入最优表作为第3行，由于为基变量，它的检验数为0，而原来的各变量的检验数和目标值均保持不变.现用对偶单纯形法求解如下：目标函数11000常数决策变量基变量↓原最优表110013/41/4010—1/41/4000［-3/4]—1/417/43/4—3/4→00—1/2-1/20新最优表110010001001/3-1/30011/3—4/3111000—1/3-2/3二、学生练习（结合例题讲解进行)三、课程小结四．布置下次课的教学内容授课题目：第五章整数规划第四节指派问题教学目的：掌握整数规划的指派问题求解的步骤。教学要求：要求与学生与教师配合能操作上次课的例1。教学重点：掌握整数规划指派问题的求解原则。教学难点:整数规划指派问题求解中匈牙利法的步骤。教学手段与方法:先用实例引入，再采用比较演示方法。实例引入例1有一项说明书要由汉语分别译成英、日、德、俄四种文字，交由甲、乙、丙、丁4个译员去完成。因各人专业不同，因此译成不同文字所需要的时间不同。假设各人完成各项工作的时间如下表，问应如何分配才能完成4项给定任务的总时间最少？工作译员1234（汉译英）（汉译日）（汉译德）（汉译俄）甲乙丙丁3109715414813141611415139解用0—1模型，1分配第i人做第j件工作0不分配第i人做第j件工作那么有：s.t.定理1如果从分配效率矩阵［］的每一行元素分别加（减）一个常数,从每一列元素分别加（减）一个常数,得到新的效率矩阵［］的最优解等价于原效率矩阵的最优解。定理2若某矩阵A中的元素分为零元素和非零元素两部分,则覆盖零元素的最少直线数等于位于不同行不同列的零元素（称为独立零元素）的最大个数。此定理告诉了效率表中有多少独立零元素的辨别方法.二、指派问题的匈牙利解法第一步转换效率矩阵[］,使各行各列都有出现零元素从每行元素减去该行最小元素；再从所得的效率矩阵每列减去该列的最小元素.若某行（列）已有零元素，就不必再减了.上例中：3109707640714=154148=110104=1105413141611235023004151390119501145第二步试求最优解，找出m个独立零元素1、从第一行开始，遇到每行只有一个零元素就用括号括上，记作（0)，然后划去其所在列的其他零元素，用○表示，遇到有两个及其以上零元素的行先跳过去;2、进行列检验，从第一列开始，给只有一个零元素的列中的那个零元素用括号括上，然后划去它所在行中的其它零元素.反复进行1、2步，直到所有零元素被划去或括上为止。3、以上已划去或括上的零元素不算在内。经过第二步以后，会出现三种情况:其一、打上括号的零元素分布在不同的行与列,且其个数等于系数矩阵的阶n，即得最优解。令其对应的1，其余的为0；其二、仍存在未括上与划去的零元素，且同行（列）的零元素至少有两个(即零元素形成闭回路）,这时从含零元素最少的行(列）开始，比较该行（列)各零元素所在列（行)中零元素的个数，选择含零元素最少的那一列（行)的这个零元素加上括号,然后划去与这个零元素同行同列的其它零元素。如此反复进行，直到所有零元素被划去或括上为止.其三、经过以上几步后，若被括上的零元素数目等于系数矩阵的阶n，即得最优解，否则进入第三步.上例：（0）71411(0）5423（0）○○1145第三步增加零元素1、作能覆盖所有零元素（指括上的和划去的零元素）的最少直线，其数目等于加括号的零元素个数.方法：1）对没有(0）的行打√;2)对打√的行上所有○元素所在的列打√；3）再对打√的列上所有（0）元素所在的行打√。重复2)和3)，直到得不出新的打√的行和列。4)对没有打√的行画横直线，对所有打√的列画纵直线，得到能覆盖所有零元素的直线。（0）71411（0)5423（0）○○11452、再对系数矩阵进行变换，以增加零元素对没有被直线覆盖的部分找出最小元素，对没有画直线的行中所有非零元素各减去，对画直线的列中所有非零元素各加上，并保持原来零元素（划去和打括号的）不变，得到新的系数矩阵。第四步对新的系数矩阵又从第二步开始,若能求n个不同行与列的零元素，即得最优解，否则又进入第三步：增加零元素。060306031105412054230033000103401034本例又从第二步开始:○6（0）312（0）5433○（0）（0）1034授课题目：第七章动态规划第一节多阶段决策过程的最优化第二节动态规划的基本概念和基本原理教学目的：掌握动态规划的基本概念、基本思想和模型特点。教学要求:要求与学生与教师配合能操作上次课的例1。教学重点：掌握动态规划的基本思想和模型特点。教学难点:动态规划的逆序解法和顺序解法。教学手段与方法：先用实例引入，再采用比较演示方法。第七章动态规划一、动态规划的基本概念动态规划是解决多阶段决策各过程最优化问题的一种数学规划的方法。二、基本概念1、阶段:按时间/空间分解成若干相互联系的段落,用…表示。2、状态:各阶段开始时的客观条件,用状态变量表示，的取值集合用表示，不具备无后效性的变量不能作状态变量；当某阶段的状态给定以后，这阶段以后过程的发展只受该阶段状态的影响，而与该阶段以前的状态无关，状态的这一性质叫无后效性3、决策和策略当各阶段的状态给定以后，就可以做出不同决定选择，从而确定下一阶段的状态,这种选择决定叫做决策,用表示第阶段的当状态为时的决策变量，其取值在一定范围内,此范围叫允许决策集合，用表示，因此有整个问题的决策序列叫策略。用表示。4、状态转移方程用表示第阶段的状态是第阶段的状态和决策变的函数。5、指标函数用来衡量所选定策略优劣的数量指标.用表示。三、动态规划求解的基本思想把一个多目标决策划分为若干阶段，恰当地选取状态变量和决策变量及定义最优指标函数,从而把整个决策问题分解为一簇同类型的子问题,再从边界条件开始,逆（或顺）过程行进方向，逐段递推求出最优解。顺推法：逆推法：动态规划在经济管理中的应用（一）背包问题1、基本模型一维背包：一位旅行者能承受重量bkg，，现有n种物品供他选择装入背包，第物品的单件重量为,总价值是携带数量的函数，求应如何选择携带物品的件数使总价值最大?二维背包：如增加到两个约束条件,如背包体积限限制为立方米，并假设第i种物品每件体积为立方米，应如何选择携带物品的件数使总价值最大？模型:一维背包二维背包2、求解方法：①阶段序,每时间段装入一种物品，那么共需个时间段。②状态变量表示第第阶段开始时允许装入前种物品的总重量,有，因已知，故用顺序解法.③决策变量种物品的件数。④状态转移方程：⑤允许的决策集合是︱，为整数}，式中为不超过的最大整数。这里的最大值表示只装运第种物品,其余-1种物品的装运量为0.⑥最优指标函数表示在背包中允许装入物品的总重量不超过公斤时背包中允许装入第1-种物品的最大使用权用价值。⑦于是得到动态规划的顺序递推方程：阶段指标为，递推方程为：例1货物装载问题L准备在一艘货船上装载3种货物，每箱重量和单价见下表，货物总载重为7t，求3种货物各装多少箱才使总价值最大？货物编号123每箱重量345每箱价值456解：1、012356789100000101012012012012301230000404048048048048120481200044888121200011222332、012345678910000001010101012012012000005050505051005100510=-012340506172830940105000044040808484012401280+00044545858989101291012131000045589101213000110102021210310320000011012013、0123456789100000001010101010120000006060606060612=-01235506102839410505588101251350+5581012131112130由=13，对应=10,=0;由=-=-0*5=10，此时=1；由=-=10-4*1=6，对应=2。3、总结建立动态规划模型的步骤：1）划分阶段2）确定状态变量及其取值范围:原则是它能描述过程演变的状态，又满足无后效性的要求；3)确定决策变量及其取值范围;4）建立状态转移方程,必须具有递推关系;5）确定阶段效应函数,建立动态规划的函数方程：函数方程是动态规划最优指标的函数形式，一种为加法型，一种为乘法型。阶段效应函数可以为收益函数（利润、产量等)，也可为损失函数(成本）。第阶段的最优指标函数是从第阶段到第n阶段单调递增或递减的总效应。授课题目:第三节动态规划模型的建立与求解教学目的:掌握动态规划中的生产与存贮问题求解的步骤。教学要求：要求与学生与教师配合能操作上次课的例1。教学重点：掌握生产与存贮问题的求解原则.教学难点：生产与存贮问题的求解步骤。教学手段与方法：先用实例引入,再采用比较演示方法。况课后小结：例2某工厂生产并销售某种产品,已知今后四个月的市场需求量预测如下表：阶段（月）1234需求量2324单位生产成本为：03+1·…，6已知该厂最大的库存容量为3单位，每月最大生产能力为6单位，并假设第+1个月的库存量为第个月可销售量（等于第个月库存量与生产量之和）与该月用户需求量之差。每批产品的固定生产成本为3千元，不生产时设固定生产成本为0元,单位产品的生产变动成本为1千元，每月单位产品的库存费用为0。5千元。试制订4个月的生产计划，在满足用户需求条件下实现总费用最小(即从第1月初至第4月末的总生产成本最小)。解：1、分析:阶段为月；状态变量为第月初的库存量，其取值范围为0，1，2，3；决策变量月的生产量:当≥时,可以为0；当时,至少应生产；由于每月最大生产能力为6，故6，而第月末（第月初）的库存为，其小于等于第月最大库存量故有：,。故有允许决策集：（1）状态转移方程逆推基本方程：由于每月的库存量是前一月库存量的函数,故采用逆推,指标函数为第月状态为时，采用最佳生产，从第月初到第4月末的总成本。上式中生产成本+库存成本=+0。50,若各阶段的允许状态集合和允许决策集合:={0,1，2，3},其中=｛0｝，=｛0，1，2，3｝.上式中第4个月因为=0，即。2、逆推表：1)的分布，由公式（1)得下表1:表10123｛3，4，5，6｝｛2，3，4，5｝{1，2，3，4｝{0，1，2，3｝0123{2,3，4，5｝｛1，2,3,4｝｛0，1，2，3｝｛0，1，2｝012343212)=4表2=4递推表状态(期末库存）决策（可能生产量）本期费用总费用生产费用库存费用合计043+4=70。5＊077133+3=60.5＊16.56。5223+2=50。5*266313+1=40.5*35.55.5递推方程为：。3）=3递推方程为：对=0，1，2,3分别求出表3=3递推表状态决策本期费用期末库存=以后各期最小费用总费用生产费用库存费用合计02345567800005678012376.565。5121123445670.50.50.50.54.55。56。57.5012376。565。511。520123045611111567012376.565。5830120451。51.51.51.55。56。51236。56。05.584）=2表3=2递推表状态决策本期费用期末库存=以后各期最小费用总费用生产费用库存费用合计0345667890000678901231211．588161234556780。50。50。50.55．56．57．58．501231211．58815.52123445671111567801231211．588153012304561．51．51．51．51．55．56．57．501231211．58813.55）=1表4=1递推表合计0012323455678000056781615。51513。5567821授课题目第四节动态规划在经济管理中的应用教学目的:掌握动态规划中货郎担问题求解的步骤。教学要求：要求与学生与教师配合能操作上次课的例1。教学重点:掌握货郎担问题的求解原则。教学难点:货郎担问题求解的步骤。教学手段与方法：先用实例引入,再采用比较演示方法。况课后小结:求解方法货郎担问题的一般描述：一个货郎从某村镇出发，经过若干个村镇、，…，一次且仅一次，最后仍回到原出发的村镇，已知从到的距离为，问应如何选择行走路线可使总行程最短？顺推法分析：设S为从到中间所有可能经过的村镇之集合,但S中点的个数要随阶段数而改变。为从到经过中间点的个数，以它来划分阶段。状态变量（,S）表示从出发经过S集合中所有村镇一次最后到达。最优指标函数表示从从出发经过含个村镇的S集合到的最短距离。，S）表示从出发经过含个村镇的S集合到的最短路线上邻接的前一个村镇。那么顺推方程为：，，例1已知四个村镇之间的距离如下表,求从某村镇出发，经过村镇、，一次且仅一次，最后仍回到原出发的村镇,问应如何选择行走路线可使总行程最短？0679809758086550解：（为方便起见，下面均以1，2,3，4代替、、、。）由边界条件，。当=1（表示从出发经过由一个村镇组成的S集合到达的最短距离为：；;；上述计算中，由于S集合中只有一个村镇,无需最小化。当=2（表示从出发经过由二个村镇组成的S集合到达的最短距离为，所以所以所以当=3（表示从出发经过由三个村镇组成的S集合到达的最短距离为所以逆过程递推，——-——，最短距离为23。2、顺推法分析例22004年美国选举活动前一周，位于纽约的候选人WalterGlenn先生必须访问迈阿密、达拉斯和芝加哥三个城市，然后返回纽约.已知这些城市之间的距离如下表。WalterGlenn先生希望最小化他必须经过的总距离，应该以什么顺序访问这些城市？编号城市纽约迈阿密达拉斯芝加哥1234纽约迈阿密达拉斯芝加哥—133415598091334-1343130715591343—9218091397921—解：采用逆推法，按已经访问过的的城市数量来编号阶段；在任意阶段的状态由上一次访问过的城市和已经访问过的城市集组成.因为在任意阶段要确定接下来要访问哪一座城市需知道两个事件：Walter当前所处的位置城市和他已经访问过的城市集C（其中在任意阶段已经访问过的城市集C中有-1座城市),并规定为完成旅程所必须经过的最短距离，为他目前处于城市与下一步将要访问城市之间的距离。1、=4（阶段4),这时这时状态变量，状态集=｛（2，｛2，3,4}）、(3，｛2,3,4}）、(4,｛2，3，4｝）｝。,,。2、=3（阶段3)由于Walter目前位于城市，并且将要到达城市,那么他需经过的距离为.然后他将处于阶段4,已经访问了城市，并且已经访问了中的每一个城市，因此他的剩余行程的距离将为。因此有：（）使用上公式时,注意Walter目前必须访问了｛2，3｝或｛2,4}或{3，4}，并且接下来必须访问不等于1的非城市集C的城市.现用上式计算：一般来说，对于这里。因为如他现位于城市，并且接下来将要访问城市，那么他需经过的距离为。因此他的剩余的行程将从城市开始,，并且已经访问了中的每一个城市，因此剩余的行程距离必定为]。3、=2（阶段2）在阶段2，因为Walter只访问了一个城市，因此唯一可能的状态为（2，｛2｝）、（3,｛3｝）和(4,｛4｝)。4、=1（阶段1）因此时Walter位于纽约，并且还没有访问过任何城市,因此状态为，故有：因此，Walter可以从城市1到2或4，任意地使其选择到4。然后必须选择访问可以得出的城市，这个城市要求Walter接下来访问3。然后必须访问可以得出的城市,这个城市要求Walter接下来访问2.然后必须选取择访问可以得出的城市，这个城市要求Walter接下来访问1。所以最优行程为：1—4-3—2-1,长度为。授课题目：第八章图与网络分析第一节图与网络的基本知识教学目的：掌握图与网络的的基本知识.教学要求：要求学生掌握欧拉图和中国邮递员问题。教学重点：掌握欧拉图和中国邮递员问题。教学难点：中国邮递员问题。教学手段与方法：先用实例引入，再采用比较演示方法。况第八章图与网络分析第一节图与网络的的基本知识一、引入:例1（数学家欧拉与图）欧拉图普瑞拉尔河从古城哥尼斯堡市中心流过，河中有小岛两座,筑有七座古桥，1736年,该市一市民向数学家提出一个问题：从家里出发，对七座桥每桥恰好通过一次,再回到家里，是否可行？分析：欧拉把两岸分别用C、D表示，两岛分别用A、B表示。此问题是寻找一条遍历多重图每条边恰好一次的回路，具有此性质的多重图叫欧拉图，对应的回路叫欧拉回路。AABCABD二、图与网络的基本知识1、图的定义图是由点集和V中元素的无序对的一个集合组成的一个二元组,记为。1）顶点和边2)关联边2、图的分类1）有向图和无向图2）简单图与完全图环和多重边3）二部图3、顶点的次1）孤立点2）悬挂点和悬挂边4、子图、支撑子图和生成子图5、网络1）有向网络和无向网络2）权和最短路问题6、连通图1)点边序列和链、初等链2）圈和初等圈3）道路和回路对于无向图，道路和链、回路和圈的意义相同.7、图的两个定理定理1任何图中顶点次数的总和等于边数的两倍；定理2任何图中次为奇数的顶点必有偶数个；三、图的矩阵表示四、欧拉回路与中国邮路问题1、欧拉回路与欧拉图欧拉注意到哥尼斯堡多重图中每个结点的度都是奇数，因此图中任何结点都不能作为起始结点，因为回路都是从某个结点出发,再回到该结点，然后再从该结点出发，再返回,如此循环,那么这个结点的度应为偶数。欧拉定理：多重图G是欧拉图当且仅当G是连通的且每个结点的度是偶数.定理3无向连通图G是欧拉图，当且仅当G中无奇点。定理4连通有向图G是欧拉图，当且仅当每个顶点的出次等于入次。2、中国邮路问题例2中国邮递员问题：中国邮递员从邮局出发，经过他所投递范围的每一条街道至少一次，完成投递任务后返回邮局，问应如何安排邮递员的行走路线才能使总行程路线最短？解1)、如G是欧拉回路，Euler设计了一条求欧拉回路的算法：2）、对于非欧拉图,邮递员返回邮局必须将图转换成欧拉图，为此需添加重复边以清除奇次顶点，与奇点关联的边应添加奇数条，与偶点关联的边应添加偶数条(含0条），现在的问题是求解使重复边总权重值最小的方案。具体方法；1）、如果在配送范围内，街道拐弯处没有奇点，那么邮递员可以从配送中心出发，走过每条街道一次且仅一次最后回到配送中心，他走的路径为最短路径。2）、对于有奇点的街道图，必须在一些街道重复走一次或多次，这样相当于我们在图中如之间增加几条重复边，令每条重复边的权与原来的边的权相等，于是这条路线就是新图中的欧拉图，它使新图不含奇点，并且重复边的总权最小。这一方案分两步（见下例）:例1一车辆从某配送中心出发，给街道上的7个超市—送货，求使总行程最短的送货方案.第一步:使新图不含奇点而增加重复边由图论,在任何一个连通图中，奇点个数必为偶数,所以如图中有奇点,可把它们配对。又因为图是连通的，故每一对奇点之间必有一条链，我们把这条链的所有边作为重复边加到图中去,新图中必无奇点。这就得出第一可行方案，即把使新图不含奇点而增加的重复边叫可行（重复边）方案.图1未加重复边前的图245336454494图2将连接奇点和之间的一条链路加上重复边245336454494在图1中,将奇点和、和配对。对前者连接两奇点的链路有好多条，任取一条（，，，，,,），把该链路上的每一条边加上重复边(见图2）。同样对和之间的一条链（,,，，，，)也加上重复边（见图3）。在图3中没有奇点，故它为欧拉图。其全部重复边的总权为51.图3对连接和之间的一条链路加上重复边245336454494第二步调整可行方案一般情况下如果在边［］上有两条或两条以上的重复边时，我们可以去掉偶数条，就能得到一个总长度较短的可行方案.现在我们图3进行这种处理,得到图4的最优方案。这种方案调整主要依据下面两个条件：1）在最优方案中，图的每一边最多有一条重复边.2）在最优方案中，图中每个圈上重复边的总权不大于该圈总权的一半.图4对有两条或两条以上重复边的边去掉偶数条245336454494在图4中，重复边的总权下降为21，但我们看到，的图4中某个圈上的重复边去掉,而给原来没有重复边的边上加上重复边，图中仍然没有重复边。因而如果在某个圈上重复边的总权大于这个圈的总权的一半时,按这条原则又做一次调整,使重复边的总长度下降为17，得最优方案(见图5)图5对图4进行调整后得到的可行方案245336454494第三步判断最优的标准从上分析，一个最优方案,一定满足1）和2)的可行方案,反之，一个可行方案若满足1)和2），则一定为最优.因此对上述给定的可行方案图5，检查它是否满足1）和2），否则对该方案继续进调整，直至1)和2)均满足为止。在图5中，圈(，，)中重复边的总权为13，而圈的权为24,不满足条件2），对其再次进行调整得图6,使总权下降为15。图6满足条件1）和2），其中任一个欧拉圈为汽车最优配送路线。图6最优方案245336454494授课题目：第二节树第三节最短路问题教学目的:掌握树的基本概念与最小生成树算法及求某点至某点的Dijkstra算法.教学要求：要求学生用表操作Dijkstra算法。教学重点：掌握用表操作Dijkstra算法。教学难点：用表操作Dijkstra算法。教学手段与方法:先用实例引入，再采用比较演示方法。第二节树一、树的概念和性质1、树的定义：连通且不含圈的无向图叫树。2、定理6（略）二、图的生成树1、若图的生成子图是一棵树,叫该图的生成树。2、找图的生成树的方法①探测法②广探法三、最小生成树问题1、具有最小权的生成树叫最小生成树。2、求最小生成树的算法①避圈法思路：从具有个点的图中的要边中选取条权尽量小的边，并且使之不构成回路，从而构成一棵最小树.方法：将网络中所有边按权的大小由小到大排列起来，每步从未选的边中选取一条权最小的边逐条衔接，但不能连接成圈。在每一步中,若有两条或更多条边都是权最小的边，则从中任选取一条.第一步:挑选边；第二步：若已选定的边为：,则从中选取使:1）所组成的圈为无圈图;2）是满足1）的尽可能小的权.第三步：当第二步不能继续执行时停止。例1某地有五个镇,拟架设电话线连接这五个镇，下图中边上的数字表示架设费用，问应如何架设电话线才能使总费用最小?解:如图,可先连接权为1的-，再连接权为2的—，再连接权为3的—，再连接权为5的—，最后是权为5的—。42681535②破圈法思路：将图每一个圈权最大的一条边去掉，直到图中不含圈为止。方法：在图中选取任何一个圈，从圈中去掉一条权最大的边（如有两条或两条以上的边都是权最大的边，则任意去掉其中的一条。然后在余下的圈中重复这个步骤，直到得到一个不含圈的图为止.这时的图就是最小树。再以上图为例。1)在图中找到一个圈，先去掉最大权8对应的边（，），得图；2）在图中找到一个圈，去掉最大权数为6的边（，)，得图;3）在图中找到一个圈，去掉最大权数4对应的边（，）,得图；4）在图中找到一个圈,去掉最大权数5对应的边(,）或（，），得图或，它们均为图的最小树。第三节最短路问题一、Dijkstra算法适用于所有权数为非负（则一切)的网络.能注出任意一点到各点的最短路径.其其基本思路是：若(,，…，，）是从到的最短路径，则（,，…,)也是从到的最短路径.因此可采用标号的方法，从始点开始,逐步向外收缩从始点到其他各点的最短路径.例1．（6分）运用Dijkstra算法求出下面运输网络中从到的最短路径（不要求写出运算过程,可直接把最短路径填入下面的括号内）。5944745456176设为连通图，图中各边(，)有权。令分别为固定标号集和临时标号集。固定标号最短路权,临时标号的估计最短路权的上界。节点迭代序号1，∞，∞,∞，∞，∞,∞，∞2，4，634，9，846，9，858，13，1469,13,14713，14，17814,15915步骤：1）给以标号，则;其余各点给予标号，则；2）若为刚得到标号的点,考虑这样的点:（，）属于且为标号，则对的标号值进行如下修改:；3）比较所有标号的点的值，把最小者改为标号：。当存在两个最小值时，可同时改为标号；若全部点为标号时则停止，否则用代替，转向2）。以上列表如上。答：从到的最短路径为（）;路长。例2运用Dijkstra算法求出下面运输网络中从A到B的最短路径和最短距离.（不要求在试卷上写出求解过程，可直接把结果写在下面的横线上）●300●200275200●100400100●150●175●●250175150200275●●300●125节点迭代序号B1，∞，∞，∞,∞，∞，∞,∞，∞，∞2100150175310040037541503503254255150325425632572557573505508425550550550650550答：A到B的最短路径为:A-—-——B；最短距离为650。授课题目：第八章第3节某点到各点和某点到某点的距离摹乘法。教学目的：掌握距离摹乘法的操作程序.教学要求：学生能轮流上黑板做题.教学重点：掌握距离摹乘法的操作程序。教学难点:同重点。教学手段与方法：先用实例引入，再采用比较演示方法。况课后小结：二、、逐次逼近算法（距离矩阵摹乘法）适用于一切网络的最短路径的求解（含负权）。它基于这样的事实：从到的最短路径总是沿该路先到，再沿（，）到，。于是若从到为最短路，那么从到也为最短路.用分别表示从到和从到的最短路长，则必有下列方程：。该方程可用迭代式求解：1）令的直接距离作初始解，若它们之间无边，则2）使用迭代法求，当进行到第则停止计算。则为最多经t步到各点的最短路长。（一）求各点到某点的最短路径设距离矩阵为，先从走一步到（），再从走一步到，得到从走两步到的最短路径（）:（1）这里为距离矩阵中的第i行元素，列的元素。它们的对应元素相加再取小，再从各点走一步到，然后走两步到（）:(2）最后得到从走一步到，再从走步到：（3）最后得到的列中各元素是从第i行第个元素加取小而来，设这个元素为从到最短路径上的邻接点,最后按邻接点扒出最短路径.例1求下图中各点到的最短路径。解：第一步:写出网络的距离矩阵如下：其中第6列为各点到的距离。从至2345623456052∞∞∞∞043∞∞∞40∞—3∞∞—2501∞∞∞4204∞∞∞-2∞0-2②④35—24552⑥244⑤②—3第二步:设从先走一步到中间点(）,再从走一步到，得到从走两步到的最短路径（）：，相当于用距离矩阵各行与对应元素相加再取小。052∞∞∞∞∞∞043∞∞∞∞=∞40∞-3∞＊∞1∞-2501∞∞=9∞∞420444∞∞∞—2∞000第三步：设从走一步到中间点（)，再从走两步到：052∞∞∞∞3∞043∞∞∞5=∞40∞-3∞*11∞—2501∞9=6∞∞420444∞∞∞—2∞000如此迭代得351=6迭代终止得从走一步到的最短路径为：40由～05(2）∞∞∞∞0（4）3∞∞∞40∞(-3)∞记为∞(—2）501∞∞∞420（4）∞∞∞—2∞(0）中第4个元素3来自（—2）+5，因0+3表示在原地踏步一次，得不到期最路径,故不予考虑.由上矩阵，知-，—，—，—，—，—在各点到的最短路径上。最短路径最短距离——-3-——5-—1-———3—4—0（二）、求某点到各点的最短路径例1求下图中到各点的最短路径。42—2-3356442-3—17025—3∞∞∞∞∞0—2∞4∞∞∞∞∞0∞∞6∞∞∞∞40∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞-30∞4∞∞∞7∞20∞∞∞∞∞3∞-100025-3∞∞∞∞02∞0-2∞4∞∞∞25∞∞0∞∞6∞∞0-3*∞∞40∞∞∞∞=-3∞∞∞∞∞0∞∞∞6∞∞∞∞∞—30∞411∞∞∞∞7∞20∞∞∞∞∞∞∞3∞—10∞的各列对应元素相加再取最小,得各行的元素.…，当时停止。025-3∞∞∞∞∞0—2∞4∞∞∞06400—3047203—10所以—，—，-,—,-，—,—，-在到各点的最短路径上。最短路径最短距离—0—2——0--3--—-3——-6--———9———-10（三）从各点到各点的最短路径——Floyd算法基本思路:1、输入权矩阵，表示各点不经任何中间点到各点的最短路径长。2、记,其中，表示从最多经一个中间点到达的最短路长。3、一般有若>0，则关于P值的估计为此时给出各点到各点的最短距离.例2求下图中任意两点间的最短路。解：该图有四条无向边，每条均可以化为方向相反的有向边。则0512∞5010∞2230282∞604∞24401）,其中，表示从最多经一个中间点到达的最短路长.按此规则修改得,如.0512∞50（6）（7）2230282（7）（3）04∞24402)0512(7)5067