最短路问讲义题应用

截断切割B题截断切割题目某些工业部门（如贵重石材加工等）采用截断切割的加工方式。

这里“截断切割”是指将物体沿某个切割平面分成两部分。

从一个长方体中加工出一个已知尺寸、位置预定的长方体（这两个长主体的对应表面是平行的）通常要经过6次截断切割。

设水平切割单位面积的费用是垂直切割单位面积费用的r倍，且当先后两次垂直切割的平面（不管它们之间是否穿插水平切割）不平行时，因调整刀具需额外费用e.试为这些部门设计一种安排各面加工次序（称“切割方式”）的方法，使加工费用最少。

（由工艺要求，与水平工作台接触的长方体底面是事先指定的）详细要求如下：1、需考虑的不同切割方式的总数2、给出上述问题的数学模型和求解方法。

1、试对某部门用的如下准则作出评价：每次选择一个加工费用最少的待切割面进行切割。

2、对于e=0的情形有无简明的优化准则。

3、用以下实例验证你的方法：待加工长方体和成品长方体的长、宽、高分别为10、14.5、19和3、2、4，二者左侧面、正面、底面之间的距离分别为6、7、9（单位均为厘米）。

垂直切割费用为每平方厘米1元，r和e的数据有以下4组：a.r=1 e=0 ;b.r=1.5 e=0 ;c.r=8 ,e=0 ;d.r=1.5;2≤e≤15对最后一组数据应给出所有最优解，并进行讨论。

B题截断切割参考答案（1）需考虑的不同切割方式的总数V中共有6!=720个不同的元素，因此有720种不同的切割方式，注意到相继二次切割一对平行的平面时，交换这二次切割的先后次序不影响对应切割方式的费用，将费用相同的切割方式归成一类，每类取一种切割方式作不代表，此时仅需考虑加工费用可能不同的切割方式426种。

（2）问题归结为求一个定义在6个切割面排列次序的全体或它的一个子集上的函数的最小值。

目标函数应尽量用显式写出。

求解可用枚举法，分支定界法或其它方法，从尽可能简便有效作为评价标准：（3）一种作法如下：在直角坐标系中，表面平行于坐标平面的长方体可表示为{（x,y,z）,(a,b,c)},其中（x,y,z）为长方体某指定角点的坐标，a,b,c分别为它的长、宽、高。

13.4 课题学习最短路径问题基础知识臺本技能1 .最短路径问题(1)求直线异侧的两点与直线上一点所连线段的和最小的问题，只要连接这两点，与直线的交点即为所求.如图所示，点A，B分别是直线I异侧的两个点，在I上找一个点C,使CA + CB最短，这时点C是直线I与AB的交点.(2)求直线同侧的两点与直线上一点所连线段的和最小的问题，只要找到其中一个点关于这条直线的对称点，连接对称点与另一个点，则与该直线的交点即为所求.如图所示，点A, B分别是直线I同侧的两个点，在I上找一个点C,使CA + CB最短，这时先作点B关于直线I的对称点B'贝山点C是直线I与AB '的交点.B r为了证明点C的位置即为所求，我们不妨在直线上另外任取一点C',连接AC',BC',B'C‘，证明AC+ CB V AC’t’B•如下：证明：由作图可知，点B和B'关于直线对称，所以直线I是线段BB'的垂直平分线.因为点C与C'在直线上，所以BC= B'C,BC'=B C.在△ABC '中,AB 'iAC'+C',所以AC+ B 'C<AC ' + C ',所以AC+ BC v AC ' -C B.【例1 ］在图中直线I上找到一点M ,使它到A, B两点的距离和最小.分析：先确定其中一个点关于直线I的对称点，然后连接对称点和另一个点，与直线I的交点M即为所求的点.解：如图所示：(1)作点B关于直线I的对称点B ';(2)连接AB '交直线于点M .(3)则点M即为所求的点.点拨：运用轴对称变换及性质将不在一条直线上的两条线段转化到一条直线上，然后用“两点之间线段最短”解决问题.基本方法塘本縮力J JI IK M F .4 \ f® F A J P J扌K uV X !■? M E ■ J. J2.运用轴对称解决距离最短问题运用轴对称及两点之间线段最短的性质，将所求线段之和转化为一条线段的长，是解决距离之和最小问题的基本思路，不论题目如何变化，运用时要抓住直线同旁有两点，这两点到直线上某点的距离和最小这个核心，所有作法都相同.警误区利用轴对称解决最值问题应注意题目要求根据轴对称的性质、利用三角形的三边关系，通过比较来说明最值问题是常用的一种方法.解决这类最值问题时，要认真审题，不要只注意图形而忽略题意要求，审题不清导致答非所问.3.利用平移确定最短路径选址选址问题的关键是把各条线段转化到一条线段上.如果两点在一条直线的同侧时，过两点的直线与原直线的交点处构成线段的差最大，如果两点在一条直线的异侧时，过两点的直线与原直线的交点处构成的线段的和最小，都可以用三角形三边关系来推理说明，通常根据最大值或最小值的情况取其中一个点的对称点来解决.解决连接河两岸的两个点的最短路径问题时，可以通过平移河岸的方法使河的宽度变为零，转化为求直线异侧的两点到直线上一点所连线段的和最小的问题.在解决最短路径问题时，我们通常利用轴对称、平移等变换把不在一条直线上的两条线段转化到一条直线上，从而作出最短路径的方法来解决问题.【例2］如图，小河边有两个村庄A, B,要在河边建一自来水厂向A 村与B村供水.E F(1)若要使厂部到A, B村的距离相等，贝S应选择在哪建厂？(2)若要使厂部到A, B两村的水管最短，应建在什么地方？分析：(1)到A, B两点距离相等，可联想到“线段垂直平分线上的点到线段两端点的距离相等”，又要在河边，所以作AB的垂直平分线，与EF的交点即为符合条件的点.(2)要使厂部到A村、B村的距离之和最短，可联想到“两点之间线段最短”，作A(或B)点关于EF的对称点，连接对称点与B点，与EF的交点即为所求.解：(1)如图1，取线段AB的中点G,过中点G画AB的垂线，交EF 于P,贝S P到A, B的距离相等.也可分别以A、B为圆心，1以大于2AB为半径画弧，两弧交于两点，过这两点作直线，与EF的交点P即为所求.⑵如图2,画出点A关于河岸EF的对称点A'，连接A'B交EF于P，则P到A, B的距离和最短.【例3】如图，从A地到B地经过一条小河（河岸平行），今欲在河上建一座与两岸垂直的桥，应如何选择桥的位置才能使从A地到B地的路程最短?思路导引：从A到B要走的路线是A—M —N —B,如图所示，而MN是定值，于是要使路程最短，只要AM + BN最短即可.此时两线段应在同一平行方向上，平移MN到AC,从C到B应是余下的路程，连接BC的线段即为最短的，此时不难说明点N即为建桥位置，MN即为所建的桥.解：（1）如图2，过点A作AC垂直于河岸，且使AC等于河宽.⑵连接BC与河岸的一边交于点N.（3）过点N作河岸的垂线交另一条河岸于点M •则MN为所建的桥的位置.思维拓展無斯应用K：Jl > / —- - *. . ........................................................................ .................. ~…• •--------------- ■ ■ ■ ....... ■■ ■: ■n iin 'ozi11 ：i n' i x i x Y I Yf i \ r;4 .生活中的距离最短问题由两点之间线段最短（或三角形两边之和大于第三边）可知，求距离之和最小问题，就是运用等量代换的方式，把几条线段的和想办法转化在一条线段上，从而解决这个问题，运用轴对称性质，能将两条线段通过类似于镜面反射的方式转化成一条线段，如图，AO + BO = AC的长.所以作已知点关于某直线的对称点是解决这类问题的基本方法.【例4】（实际应用题）茅坪民族中学八⑵班举行文艺晚会，桌子摆成如图a所示两直排（图中的AO, BO）, A0桌面上摆满了橘子, 0B桌面上摆满了糖果，站在C处的学生小明先拿橘子再拿糖果，然后到D处座位上，请你帮助他设计一条行走路线，使其所走的总路程最短？A---------- 0C・irB图a解：如图b.(1)作C点关于OA的对称点C i，作D点关于OB的对称点D i, ⑵连接C iD i，分别交OA, OB于P, Q,那么小明沿C-P-Q-D 的路线行走，所走的总路程最短.5.运用轴对称解决距离之差最大问题利用轴对称和三角形的三边关系是解决几何中的最大值问题的关键.先做出其中一点关于对称轴的对称点，然后连接对称点和另一个点，所得直线与对称轴的交点，即为所求.根据垂直平分线的性质和三角形中两边之差小于第三边易证明这就是最大值.破疑点解决距离的最值问题的关键运用轴对称变换及三角形三边关系是解决一些距离的最值问题的有效方法.【例5］如图所示，A, B两点在直线I的两侧，在I上找一点C,使点C到点A、B的距离之差最大.分析：此题的突破点是作点A（或B）关于直线I的对称点A'（或B）,Ci作直线A 'B（AB'）与直线I交于点C,把问题转化为三角形任意两边之差小于第三边来解决.解：如图所示，以直线I为对称轴，作点A关于直线I的对称点A',AB 的连线交I于点C,则点C即为所求.理由：在直线I上任找一点C（异于点C），连接CA, CA, CA',CB.因为点A, A'关于直线I对称，所以I为线段AA '的垂直平分线，则有CA= CA',所以CA—CB=CA ' -CB= A B.又因为点C'在上，所以C 'A = C 'A '•在8 ' BC '中,C 'A—C B= C A' -C B v A B,所以C 'A ' -C B v CA —CB.点拨：根据轴对称的性质、利用三角形的三边关系，通过比较来说明最值问题是常用的一种方法.。