《数学建模与数学应用》由会员分享，可在线阅读，更多相关《数学建模与数学应用（162页珍藏版）》请在金锄头文库上搜索。
1、 第一课第一课 数学建模与数学应用数学建模与数学应用 数学建模的含意n n数学模型：由实际问题归结为的数学问题n n数学建模：对实际问题加以简化、抽象，提出假设，归结为数学问题，解决，并加以检验的全过程数学建模的一般步骤n n准备准备n n假设假设n n建模建模n n解模解模n n验证和讨论验证和讨论n n应用应用数学建模是不同层次数学教学的重要内容 n n大学普遍开设数学建模课程n n中国大学生数模竞赛和美国大学生数模竞赛n n上海市的中学生数学知识应用竞赛n n高中数学课程标准：数学学习的一种新的方式 n n自主学习自主学习n n体验知识的联系，增强数学应用意识体验知识的联系，增强数学应用
2、意识n n培养学习数学的兴趣培养学习数学的兴趣n n提高应用、创新能力、综合能力、团队精神提高应用、创新能力、综合能力、团队精神数学建模与解应用题的不同处n n假设是数学建模的一部分n n由实际检验数学建模的结论n n数学建模教学的功能更多n n综合性应用知识综合性应用知识n n创新意识的培养创新意识的培养n n团队精神的培养团队精神的培养数学建模的简单例子n n冲洗蔬菜上残留农药的方法n n太阳系行星位置的数学模型冲洗蔬菜上残留农药的方法n n刚从田里采摘下来的蔬菜上有残留的农药，需要刚从田里采摘下来的蔬菜上有残留的农药，需要用水清洗用水清洗n n现在有现在有4 4公斤的水，要冲洗一袋蔬菜公
3、斤的水，要冲洗一袋蔬菜n n有两种冲洗方案：一种是将有两种冲洗方案：一种是将4 4公斤的水一次冲洗；公斤的水一次冲洗；另一种是分两次冲洗，每次冲洗用水另一种是分两次冲洗，每次冲洗用水2 2公斤公斤n n已知已知1 1公斤的水冲洗一次，可使蔬菜上残留农药为公斤的水冲洗一次，可使蔬菜上残留农药为原来的原来的1/21/2n n问哪种冲洗方案可使蔬菜上残留农药量比较少？问哪种冲洗方案可使蔬菜上残留农药量比较少？问哪种冲洗方案可使蔬菜上残留农药量比较少？问哪种冲洗方案可使蔬菜上残留农药量比较少？ 分析n n用于冲洗的水越多，洗掉的农药也越多，但总还有残留农药在蔬菜上n n冲洗次数越多，洗掉的农药也越多
4、n n关键所在：残留农药与冲洗用水量之间的函数关系 残留农药y与冲洗用水量x的关系 pp y是冲洗前后农药残留量之比 pp y随x增大而减小pp y（1）=0.5， y（0）=1pp已知的信息还不足以确定残留农药与冲洗用水量之间的函数关系 pp可以假设某些函数关系加以讨论取两种函数形式讨论n n函数形式不同函数形式不同n n满足函数要求满足函数要求n n结轮相同结轮相同讨论n n函数相同，自变量范围不同可能结轮不同函数相同，自变量范围不同可能结轮不同n n不排除其他形式的函数可能有不同的结轮不排除其他形式的函数可能有不同的结轮n n要通过实践检验要通过实践检验太阳系行星位置的数学模型行星行星行
5、星行星水星水星水星水星金星金星金星金星地球地球地球地球火星火星火星火星木星木星木星木星土星土星土星土星距离距离距离距离3.93.97.27.210.010.015.215.252.052.095.395.3分析上述数据，你会得到什么结论？分析上述数据，你会得到什么结论？动画动画假设假设n n在太阳系中尚有未发现的行星在太阳系中尚有未发现的行星n n太阳系的行星离太阳的距离可以用简单的太阳系的行星离太阳的距离可以用简单的数列表示数列表示博德公式（1766年）理论公式和实际对比行星行星行星行星n n理论距离理论距离理论距离理论距离实际距离实际距离实际距离实际距离水星水星水星水星例外例外例外例外4
6、43.93.9金星金星金星金星2 27 77.27.2地球地球地球地球3 3101010.010.0火星火星火星火星4 4161615.215.2小行星小行星小行星小行星5 5282827.627.6木星木星木星木星6 6525252.052.0土星土星土星土星7 710010095.395.3天王星天王星天王星天王星8 8192192192192海王星海王星海王星海王星9 9388388301301冥王星冥王星冥王星冥王星10107727723963961782年1801年1846年1903年太阳系八大行星太阳系八大行星曾经作为太阳系第九大行星冥王星，曾经作为太阳系第九大行星冥王星，在在20
7、06年年8月月24日于布拉格举行的日于布拉格举行的第第26 届国际天文联会中通过的第届国际天文联会中通过的第 5 号决议中被划为矮行星，并命名为小号决议中被划为矮行星，并命名为小行星行星134340号，号， 从太阳系九大行从太阳系九大行星中被除名。现在太阳系只有八大行星中被除名。现在太阳系只有八大行星。所有涉及星。所有涉及“九大行星九大行星”的内容应的内容应改为改为“八大行星八大行星”。第二课第二课 足球最佳射门位足球最佳射门位置置问题的提出张角的概念张角公式的推导，。求射门的最佳位置n n q q的表达式含有反三的表达式含有反三角函数，直接求最值角函数，直接求最值有困难有困难n n tant
8、anq q 是是 q q 的增函数的增函数n n求求tantanq q 的最大值的最大值求tanq 的最大值讨论讨论1n n当球员在沿平行于边线且离边线距离为 d 的直线上向对方球门进攻时，他最佳的射门位置在何处?。讨论讨论2n n如果足球运动员是沿一条和球门中心连线成某一个角度的斜线进攻，他在何处射门最有利?第三课 家具进屋问题例例1. 1. 商店一辆送货推车商店一辆送货推车, , 长长2.22.2米米, , 宽宽1 1米米, ,能否能否拐进居民大楼拐进居民大楼1.51.5米宽米宽的直角走廊的直角走廊? ?问题例例2. 2. 一条直角走廊宽一条直角走廊宽1.31.3米米, , 一件水平截一件
9、水平截面如右图所示的直面如右图所示的直角家具角家具ABCDE, ABCDE, 是是否能拐进这条直角否能拐进这条直角走廊走廊? ?家具移动问题的假设n n家具可以连续移动：平行移动、旋转；n n家具不能折卸、翻转，即不能改变家具的外形推车问题分析（动画）关键点是：在推车转弯过程中点关键点是：在推车转弯过程中点M到直线到直线AB的距离的距离是否始终大于推车的宽度是否始终大于推车的宽度1m？写出M点到直线AB的距离公式求M点到直线AB的距离的极值直角家具问题分析（动画）关键点是：在家具转弯过程中点关键点是：在家具转弯过程中点M到直线到直线BE的距离的距离是否始终大于线段是否始终大于线段CG的长度？的
10、长度？写出点M到直线BE的距离家具问题小结n n家具连续移动，尽可能地化为比较简单的移动；家具连续移动，尽可能地化为比较简单的移动；n n表示这样的移动可以引进参数；表示这样的移动可以引进参数；n n要找出移动中的关键位置；要找出移动中的关键位置；n n能否顺利移动到指定的位置，往往取决于某些点能否顺利移动到指定的位置，往往取决于某些点到家具特定边的距离的大小；到家具特定边的距离的大小；n n在实际问题中借助于数值计算，也可以得到正确在实际问题中借助于数值计算，也可以得到正确的结论。的结论。思考题第四课第四课 喷灌头的间距喷灌头的间距问题背景n n喷洒灌溉系统和喷漆设备：被喷洒的物体面要求喷洒
11、灌溉系统和喷漆设备：被喷洒的物体面要求受液均匀受液均匀n n假设单个喷头喷洒均匀，范围是一个圆域假设单个喷头喷洒均匀，范围是一个圆域 n n要求确定喷头间距，使地块各点受水最均匀要求确定喷头间距，使地块各点受水最均匀要求确定喷头间距，使地块各点受水最均匀要求确定喷头间距，使地块各点受水最均匀假设n n喷头圆内洒水均匀喷头圆内洒水均匀n n没有一个点同时受到三个或三个以上喷头的喷洒没有一个点同时受到三个或三个以上喷头的喷洒怎样刻画地块点的受水量？ n n设想地块平移，喷水管不动的情况设想地块平移，喷水管不动的情况n n原先在原先在( (x,yx,y) )处的一点只有当该点移动到喷头的喷洒圆内处的
12、一点只有当该点移动到喷头的喷洒圆内时受到喷灌时受到喷灌n n该点受水量与过该点且平行于该点受水量与过该点且平行于y y轴的直线与喷洒圆所交的轴的直线与喷洒圆所交的弦长成正比弦长成正比n n在这条直线上的各点受水量相同在这条直线上的各点受水量相同怎样刻画地块的受水量的均匀性？ n n一点受水量可用弦长表示，该函数只是变量一点受水量可用弦长表示，该函数只是变量x x的函数的函数C(xC(x) )n n求求C(xC(x) )的最值的最值n n用最大值与最小值之差表示受水不均匀度，该指标与两个用最大值与最小值之差表示受水不均匀度，该指标与两个喷头的间距喷头的间距d d有关，记为有关，记为f(df(d)
13、 )n n选择选择d d使使f(df(d) )达到最小达到最小受水量C(x)的表达式n n视视 d d 为常数为常数n n由对称性，只考虑由对称性，只考虑x x的的范围在范围在0 0到到d/2d/2之间之间n nC(C(x x) )是一个以是一个以d-Rd-R为界为界的分段函数的分段函数C(x)的最值n n先求先求C(C(x x) )在两个小区间在两个小区间最值最值n n比较大小后可得比较大小后可得C(C(x x) )在在0,0,d d/2/2上的最值上的最值在0,d-R上C(x)的最值n n是是 x x 的减函数：弦长单调减小的减函数：弦长单调减小在d-R，d/2上C(x)的最值n n是是
14、x x 的增函数：二条弦长之和，增多减少的增函数：二条弦长之和，增多减少在整个区间上0，d/2上C(x)的最值n n比较两个小区间上最值大小比较两个小区间上最值大小n n最值与最值与 d d 有关，此时有关，此时d d为变量为变量M(d)的讨论n nMM( (d d) )的值是的值是AD(AD(2R)2R)的长度与的长度与2|ST|2|ST|长度中长度中大者大者n n先看先看|ST|ST|R R的情况的情况n n此时此时ADAD2ST2STn n由此位置两圆圆心相由此位置两圆圆心相离时离时( (即即d d增大增大),AD2ST),AD2STn n由此位置两圆圆心相由此位置两圆圆心相近时近时(
15、(即即d d 减小减小),AD2ST),AD2STn nMM( (d d) ) 是一个分段函数是一个分段函数M(d)和f(d)的表达式求f(d)在R,2R内的最小值结论第五课 降低成本的装箱方法降低成本的装箱方法 学生应用数学论文问题提出n n问题实际背景n n装箱方法引起疑问：看来装满，为什么实际数目不多？研究的问题n n不同的装箱方法怎样影响草莓总数？n n有没有节约装箱成本的方法已知信息和假设n n纸箱的长、宽、高的规格有下列三种36cmX36cmX36cm、54cmX24cmX36cm、72cmX18cmX36cm n n假设草莓为球形，大小一样，平均3cm观察果农装箱方法n n层与层
16、之间：层与层之间：“迭装迭装”和和“错装错装”n n每层草莓数：类型每层草莓数：类型1和类型和类型2装两层草莓的高度n n“ “迭装迭装” ”方法：方法：2d2dn n“ “错装错装” ”方法：方法：两种类型每层的草莓总数n n将纸箱的尺寸表示为：adXbdXcdn n纸箱的底面为矩形：adXbdn n 一层类型1草莓的总数为aXb个n n一层类型2草莓的总数为（a-1）X（b-1）个计算草莓总数n n调整相对位置，使得若干层类型调整相对位置，使得若干层类型1 1的装法集中在的装法集中在底层，以后往上类型底层，以后往上类型1 1和类型和类型2 2交错出现。这样交错出现。这样调整后草莓层数不变，
17、总数不变调整后草莓层数不变，总数不变草莓总数计算n n1n1n层为类型层为类型1 1装法装法n n往上类型往上类型1 1和类型和类型2 2装法交错出现。装法交错出现。n n从类型从类型2 2开始出现（含）以上设总有开始出现（含）以上设总有mm层层装满箱时草莓总数和箱高cd的关系计算草莓总数公式计算草莓总数步骤n n取取n n为不大于为不大于c c的整数的整数n n求满足不等式的最大整数求满足不等式的最大整数mmn n按公式计算草莓总数按公式计算草莓总数具体计算结果解释对装箱数目的疑惑对纸箱尺寸的建议n n在相同的周长条件下，底越接近正方形，可装的在相同的周长条件下，底越接近正方形，可装的草莓越
18、多草莓越多第六课 那契印地安人婚配制度用数学模型研究历史事实的案例探索那契印第安人婚配制度崩溃探索那契印第安人婚配制度崩溃原因原因n n数学模型帮助探索历史n n假设是数学模型成功与否的关键n n假设要合理、繁简恰当，与建立模型相呼应那契印第安人婚配制度那契印第安人婚配制度这种婚配制度为什么会崩溃？这种婚配制度为什么会崩溃？能否用数学模型方法来解释？能否用数学模型方法来解释？对问题的思考n n等级人数发生问题n n定性不能解决的疑惑假设假设n n男女人数相等（全族、各等级）男女人数相等（全族、各等级）男女人数相等（全族、各等级）男女人数相等（全族、各等级）n n一对夫妻育有一对子女，男女各一一
19、对夫妻育有一对子女，男女各一一对夫妻育有一对子女，男女各一一对夫妻育有一对子女，男女各一n n只和同代人结婚，一夫一妻制、只结婚一次只和同代人结婚，一夫一妻制、只结婚一次只和同代人结婚，一夫一妻制、只结婚一次只和同代人结婚，一夫一妻制、只结婚一次问题归结为差分方程组结论n n总人数不变，上等人的人数随世代更替而无限增加，必然因下等人数不能符合婚配制度的要求导致这种婚配制度的崩溃第七课第七课 概率和数学期望的应用概率和数学期望的应用一、这为什么是骗局？一、这为什么是骗局？n n有人在街角设赌：有人在街角设赌：2020枚签（其中枚签（其中1010枚标有枚标有5 5分分分分值、值、1010枚标有枚标
20、有1010分分值）让过路人从中抽出分分值）让过路人从中抽出1010枚，枚，以以1010枚签的分值总和为奖、罚依据。枚签的分值总和为奖、罚依据。n n具体奖罚金额见下表：具体奖罚金额见下表：分值分值分值分值奖罚金额奖罚金额奖罚金额奖罚金额50 ,10050 ,100奖奖100100元元55,9555,95奖奖1010元元60,65,85,9060,65,85,90不奖不罚不奖不罚70,75,8070,75,80罚罚1 1元元用概率分析n n输赢值是随机的n n记一次奖罚额为Xn nX取值：100，10，0，1n nX为离散的随机变量n n求X的分布列计算X的分布列n n这是古典概型，基本事件是从
21、20枚签中取出10枚n n基本事件总数：从20个事物取10个的组合数“X1”的概率n nX=-1时对应的分值：时对应的分值：70，75，80n n包含的基本事件：包含的基本事件：6X5分和分和4X10分，分， 5X5分和分和5X10分，分， 4X5分和分和6X10分分n n基本事件数：基本事件数：n n绝大多数被罚绝大多数被罚“X100”的概率n nX=100时包含的基本事件：全时包含的基本事件：全10或全或全5n n基本事件数：基本事件数：2n n比一年全国自行车遇车祸的概率还小比一年全国自行车遇车祸的概率还小(1/5000)1/5000) “X10”的概率n nX=10时对应的分值：时对应
22、的分值：55，95n n包含的基本事件：包含的基本事件：9X5分和分和1X10分，分， 9X5分和分和1X10分分n n基本事件数：基本事件数：n n平均平均1000人只有一个人得人只有一个人得10元元“X0”的概率n nX=0时对应的分值：时对应的分值：60，65，85，90n n包含的基本事件：包含的基本事件：8X58X5分和分和分和分和2X102X10分，分，分，分， 7X57X5分和分和分和分和3X103X10分，分，分，分， 3X53X5分和分和分和分和7X107X10分，分，分，分，2X52X5分和分和分和分和8X108X10分分分分n n基本事件数：基本事件数：n n平均约平均约
23、1/5的无奖罚的无奖罚X的分布列计算X的数学期望n n按公式计算n n结果为0.81元n n这种赌博不公正n n用数学期望的含义解释结果：平均每个参赌的人要付给设赌局者0.81元，参赌的人越多，结论越准确二、如何减少验血次数？二、如何减少验血次数？n n1500名同学参加验血n n分组检验法：按k个人一组进行分组，对k个人的血混合在一起进行检验。n n如果混合血液呈阴性，可得如果混合血液呈阴性，可得k k个人的血都呈阴个人的血都呈阴性性n n若呈阳性，则再对这若呈阳性，则再对这k k个人的血分别进行化验个人的血分别进行化验n n是否可以减少总检验次数？是否可以减少总检验次数？n nk等于多少时
24、，可以使检验次数最少？等于多少时，可以使检验次数最少？ 建立模型确立随机变量n n以X表示一个学生平均验血的次数n n不分组X1 :常数n n分组：X=1/k或x=1+1/k n nX X是随机变量是随机变量n n计算计算X X的分布列：取两种值的概率的分布列：取两种值的概率n n计算计算X X的期望值的期望值EXEX，若，若EX1EX1，说明分组验血有，说明分组验血有成效成效分组时X的分布列n n设检出血液阳性率为pX的概率分布列X的数学期望EXn nEX1EX1的条件的条件n n取取 p=0.1, p=0.1, 对对k k取不同数值计算取不同数值计算计算结果和结论（p=0.1）第八课 风险
25、决策的数学模型风险决策的数学模型 面对不确定性的决策方法风险决策的应用n n面对不确定性的情况n n例子n n渔船是否要出海渔船是否要出海n n是否要投资房地产是否要投资房地产n n学生如何填报高考志愿学生如何填报高考志愿几个概念n n决策：先于行动前的选择n n风险决策：面对不确定性的决策风险决策解决问题的思路n n最优：在均值的意义下追求最优n n基础：随机变量的数学期望n n步骤：n n选择目标函数选择目标函数n n确定随机变量、随机空间、概率等确定随机变量、随机空间、概率等n n确定目标依赖于随机因素的表达式确定目标依赖于随机因素的表达式n n计算在各种决策下目标函数的数学期望计算在各
26、种决策下目标函数的数学期望n n选择达到最大期望值的那个决策选择达到最大期望值的那个决策例子n n面包房进货量的问题n n填报志愿的问题面包房进货量的问题n n每只面包的进货价为2.50元，售价为4元。n n当天下午6：00以后开始打折，以每只2元的价格处理完剩下的面包n n面包房每天面包在下午6：00以前售出100、150、200、250、300只的概率分别为0.2、0.25、0.3、0.15和0.1n n生产厂家每天供货数必须是50的倍数n n问面包房每天应该进多少货问面包房每天应该进多少货？引进变量n n以X表示在下午6:00以前卖出的面包数：这是一个随机变量n n以L表示利润：目标函数
27、n n以y表示进货量：这是决策变量n nL依赖于X和y计算的步骤n n写出L依赖于X和y的表达式n n计算y取不同数值时的期望值n n选择利润达到最大期望值的进货数yL的表达式 有关信息n nX X取值：取值：100100，150150，200200，250250，300300n n分别列如下表所示分别列如下表所示n n只考虑只考虑 y y取值：取值：100100，150150，200200，250250，300300 y=100时L的期望值n n全部面包都能以正常价格出售全部面包都能以正常价格出售 y=150时L的期望值 y=200时L的期望值 y=250时L的期望值 y=300时L的期望值
28、决策n n当y=200或250时L的期望值最大，每天可以进200只或250只面包n n平均利润为每天235元学生填报志愿的问题n n填报的志愿不能重复填报的志愿不能重复n n希望喜好程度的期望值最大希望喜好程度的期望值最大分析n n对个人来说填报的效果有偶然性n n对一群学生来说，按风险决策的方法可以求得最佳的决策：使学生的喜好得分期望值最高n n先不考虑学校不能重复的限制，如结果有重复，再作调整；否则就是最佳先考虑第三志愿n n第三志愿应该选第三志愿应该选D Dn n学生进入第三志愿的喜好程度得分期望值为学生进入第三志愿的喜好程度得分期望值为4.24.2先考虑第二志愿n n第二志愿应该选第二
29、志愿应该选C Cn n学生进入第二志愿的喜好程度得分期望值为学生进入第二志愿的喜好程度得分期望值为6.16.1最后考虑第一志愿最终决策n n依次选B、C、Dn n喜好程度得分期望值为7.26第九课第九课 指派问题指派问题合理利用资源、人力的合理利用资源、人力的方法方法典型问题n n有有 n 件工作要完成件工作要完成n n有有 n 个人可以调用个人可以调用n n每件工作可以指派任何人做，但效率不同；每件工作可以指派任何人做，但效率不同；效率用效率表表示效率用效率表表示n n一件工作只能由一个人做一件工作只能由一个人做n n一个人只能做一件工作一个人只能做一件工作n n如何指派可使效率最高（和最小
30、）如何指派可使效率最高（和最小）指派的要求-通过表格表示n n每行取每行取一个数且只取一个数一个数且只取一个数（一（一个人做一件工作且只做一件工作）个人做一件工作且只做一件工作）n n每列取一个数且只取一个数每列取一个数且只取一个数（每（每件工作必须有人做且只由一个人）件工作必须有人做且只由一个人）n n在表中共取出五个数，分别在不在表中共取出五个数，分别在不同行不同列上同行不同列上（指派工作的一种（指派工作的一种方案）方案）n n这五个数的和表示该方案的效率这五个数的和表示该方案的效率在在所所有有的的方方案案中中找找到到和和为为最最小小（效效率率最最好好）的的方方案案一切可能方案的总数n!
31、工作工作工作工作人员人员人员人员1 12 23 3A A4 45 57 7B B1 13 35 5C C2 26 65 5如果某件工作由任何人完成都要增加（或减少）相如果某件工作由任何人完成都要增加（或减少）相同的时间，则最优方案不变同的时间，则最优方案不变 工作工作工作工作人员人员人员人员1 12 23 3A A4 45 57 7B B1 13 35 5C C2 26 65 5如果某个人完成任何工作都要增加（或减少）相同如果某个人完成任何工作都要增加（或减少）相同的时间，则最优方案不变的时间，则最优方案不变 1 12 23 3A A4 45 57 7B B1 13 35 5C C2 26 6
32、5 5 1 12 23 3A A0 01 13 3B B0 02 24 4C C0 04 43 3 1 12 23 3A A0 00 00 0B B0 01 11 1C C0 03 30 0 1 12 23 3A A0 00 00 0B B0 01 11 1C C0 03 30 0A 做第做第 2 件工作，件工作，B 做第做第 1 件工作，件工作，C 做第做第 3 件工作件工作在不同行、不同列上有三个零，总和为零，在不同行、不同列上有三个零，总和为零，对应最佳方案对应最佳方案 工作工作人员人员人员人员1 12 23 3A A2 26 65 5B B3 35 56 6C C9 93 34 42
33、20 03 31 10 02 20 01 10 02 20 03 31 10 02 20 01 10 0 工作工作人员人员人员人员1 12 23 3A A3 31 14 4B B6 65 57 7C C2 23 32 22 20 03 31 10 02 20 01 10 01 10 02 20 00 01 10 02 20 0 1 12 23 3A A0 00 00 0B B0 01 11 1C C0 03 30 02 20 03 31 10 02 20 01 10 0如何判别效率表中在不同的行、不同的列有三个零更复杂的情况 工作工作工作工作人员人员人员人员1 12 23 34 45 5A A
34、4 45 57 73 36 6B B1 13 35 58 84 4C C2 26 65 57 72 2D D3 35 56 63 36 6E E9 93 34 43 34 44 45 57 73 36 61 13 35 58 84 42 26 65 57 72 23 35 56 63 36 69 93 34 43 34 41 12 24 40 03 30 02 24 47 73 30 04 43 35 50 00 02 23 30 03 36 60 01 10 01 11 12 23 30 03 30 02 23 37 73 30 04 42 25 50 00 02 22 20 03 36 6
35、0 00 00 01 11 12 23 30 03 30 02 23 37 73 30 04 42 25 50 00 02 22 20 03 36 60 00 00 01 1表中每表中每行、每列都有零行、每列都有零但是没有不在同一行、同但是没有不在同一行、同一列的五个零一列的五个零1 12 23 30 03 30 02 23 37 73 30 04 42 25 50 00 02 22 20 03 36 60 00 00 01 11 12 23 30 03 30 02 23 37 73 30 04 42 25 50 00 00 02 20 03 36 62 20 00 01 1要划去表中所有的零
36、，至要划去表中所有的零，至少要五条直线段（横线或少要五条直线段（横线或竖线）竖线）1 12 23 30 03 30 02 23 37 73 30 04 42 25 50 00 02 22 20 03 36 60 00 00 01 1表中有五个在不同行、不表中有五个在不同行、不同列的零同列的零划去划去所有零的最少线段数：所有零的最少线段数：41 12 23 30 03 30 02 23 37 73 30 04 42 25 50 00 02 22 20 03 36 60 00 00 01 11 10 01 10 01 10 00 01 17 71 12 24 42 27 70 00 00 00 0
37、0 01 18 80 00 02 21 1未划去的数减去未划去的数减去2在交叉点上的数加上在交叉点上的数加上2划去的数但不在交叉点上的数不划去的数但不在交叉点上的数不变变把方法应用到更多的问题中去n n人数和工作数不相等人数和工作数不相等n n求最大值（不是求最小值）求最大值（不是求最小值）人数和工作数不相等 待卸车待卸车待卸车待卸车装卸组装卸组装卸组装卸组1 12 23 34 45 5A A4 45 57 73 36 6B B1 13 35 58 84 4C C2 26 65 57 72 2D D3 35 56 63 36 6人数和工作数不相等 工作工作工作工作人员人员人员人员1 12 23
38、 34 45 5A A4 45 57 73 36 6B B1 13 35 58 84 4C C2 26 65 57 72 2D D3 35 56 63 36 6E E0 00 00 00 00 0求最大值（招聘翻译、文书、项目经理、广告策划） 成绩成绩成绩成绩人员人员人员人员外语外语外语外语计算机计算机计算机计算机 管理学管理学管理学管理学 传媒学传媒学传媒学传媒学A A8484818177778383B B8383828285858585C C7878767675757777D D8686858587878686 成绩成绩成绩成绩人员人员人员人员外语外语外语外语 计算计算计算计算机机机机管理
39、管理管理管理学学学学传媒传媒传媒传媒学学学学A A1616191923231717B B1717181815151515C C2222242425252323D D1414151513131414 成绩成绩成绩成绩人员人员人员人员外语外语外语外语 计算计算计算计算机机机机管理管理管理管理学学学学传媒传媒传媒传媒学学学学A A8484818177778383B B8383828285858585C C7878767675757777D D8686858587878686 成绩成绩成绩成绩人员人员人员人员外语外语外语外语 计算计算计算计算机机机机管理管理管理管理学学学学传媒传媒传媒传媒学学学学A
40、A1616191923231717B B1717181815151515C C2222242425252323D D1414151513131414 成绩成绩成绩成绩人员人员人员人员外语外语外语外语 计算计算计算计算机机机机管理管理管理管理学学学学传媒传媒传媒传媒学学学学A A0 01 17 71 1B B2 21 10 00 0C C0 00 03 31 1D D1 10 00 01 1第十课 最短路模型问题提出最短路算法（狄克斯特拉算法）在设备更新问题中的应用问题提出：最短路：问题提出：最短路： 求下图从求下图从求下图从求下图从 1 1 到到到到 8 8 的最短路的最短路的最短路的最短路方法：方法：1.枚举法枚举法 2.Dijkstra 方法方法枚举法的局限性枚举法的局限性适合于编程计算的一般算法适合于编程计算的一般算法以例子介绍狄克斯特拉算法以例子介绍狄克斯特拉算法最短路最短路1最短路最短路2 最短路最短路3最短路最短路4最短路最短路5最短路最短路6最短路最短路7最短路最短路8最短路应用n n设备更新计划设备更新问题归结为最短路问题n n每一条从都表示一种相应的设备更新方案；n n每条路的长度都表示该方案的费用；n n问题变为在图中求一条从V1到V6的最短路；n n该问题可以用 Dijkstra 方法求解。方法求解。
