范文一：烙饼计算方法

“烙饼”的计算方法

我的教育随笔 2009-12-20 21:55:23 阅读67 评论0 字号:大中小

《数学广角》中的“烙饼问题”一直以来都是困惑我们的一个内容，尤其是最佳方法的计算方法。听过很多老师的课，都只是通过动手操作理解三个饼的最佳节省时间的方法。最后通过表格让学生发现用“一面的烙饼时间*饼的张数=一共得最少的烙饼时间”。但是接触了一些实际问题过后我发现这种方法只能解决

一个锅最多烙2个饼的情况，要是能找到通用的算式就好了。

为了解决这个问题我首先考虑烙饼过程能节省时间就是每次保证锅的容量，只要尽可能保证每次

烙饼的面数就可以了，比如:

1、一个锅最多可以烙2个饼，饼的两面都要烙，每面的时间是3分钟，如果烙5张饼最少用多少分钟就

可以了,

我们可以这样解决:5张饼*2面=10个面 10个面/2(一次可以同时烙2个饼的一面)=5次

5次*3分钟=15分钟

2、一个锅最多可以烙3个饼，饼的两面都要烙，每面的时间是3分钟，如果烙5张饼最少用多少分钟就

可以了,

我们同样可以这样解决:5张饼*2面=10个面 10个面/3(一次可以同时烙3个饼的一面)=3次……1

面

3+1=4次 4次*3分钟=12分钟

3、一个锅最多可以烙5个饼，饼的两面都要烙，每面的时间是3分钟，如果烙5张饼最少用多少分钟就

可以了,

我们同样可以这样解决:5张饼*2面=10个面 10个面/5(一次可以同时烙5个饼的一面)=2次

2次*3分钟=6分钟

4、 一个锅最多可以煮10个玉米，每个玉米煮熟的时间是3分钟，如果煮10个玉米最少用多少分钟就可

以了,

我们同样可以这样解决:10个玉米*1面=10个面 10个面/10(一次可以同时煮10玉米)=1次

1次*3分钟=3分钟

如果是煮7个玉米，7/10 约1次，时间还是1次*3分钟=3分钟 《数学广角》中的“烙饼问题”一直以来都是困惑我们的一个内容，尤其是最佳方法的计算方法。听过很多老师的课，都只是通过动手操作理解三个饼的最佳节省时间的方法。最后通过表格让学生发现用“一面的烙

饼时间*饼的张数=一共得最少的烙饼时间”。但是接触了一些实际问题过后我发现这种方法只能解决一个锅

最多烙2个饼的情况，要是能找到通用的算式就好了。

为了解决这个问题我首先考虑烙饼过程能节省时间就是每次保证锅的容量，只要尽可能保证每次

烙饼的面数就可以了，比如:

1、一个锅最多可以烙2个饼，饼的两面都要烙，每面的时间是3分钟，如果烙5张饼最少用多少分钟就

可以了,

我们可以这样解决:5张饼*2面=10个面 10个面/2(一次可以同时烙2个饼的一面)=5次

5次*3分钟=15分钟

2、一个锅最多可以烙3个饼，饼的两面都要烙，每面的时间是3分钟，如果烙5张饼最少用多少分钟就

可以了,

我们同样可以这样解决:5张饼*2面=10个面 10个面/3(一次可以同时烙3个饼的一面)=3次……1

面

3+1=4次 4次*3分钟=12分钟

3、一个锅最多可以烙5个饼，饼的两面都要烙，每面的时间是3分钟，如果烙5张饼最少用多少分钟就

可以了,

我们同样可以这样解决:5张饼*2面=10个面 10个面/5(一次可以同时烙5个饼的一面)=2次

2次*3分钟=6分钟

4、 一个锅最多可以煮10个玉米，每个玉米煮熟的时间是3分钟，如果煮10个玉米最少用多少分钟就可

以了,

我们同样可以这样解决:10个玉米*1面=10个面 10个面/10(一次可以同时煮10玉米)=1次

1次*3分钟=3分钟

说明:

这样的方法对一个锅里同时能烙的饼数一样或者更多的饼数是适用的。比如一个平底锅一次最多能烙5个饼，那这种方法适用5个饼以上的最少时间计算。而对一次最多能烙的饼数5个以下的就按烙一个饼的时间计算。因为没有达到锅里最多能容纳的饼数，那这些面分别在正面与反面是不能同时放在锅里同

时烙的。

范文二：接触问题的计算方法

这是接触问题的计算方法。

接触问题的关键在于接触体间的相互关系（废话

），此关系又可分为在接触前后的法向关系与切向关系。

法向关系：

在法向，必须实现两点：1）接触力的传递。2）两接触面间没有穿透。 ANSYS 通过两种算法来实现此法向接触关系：罚函数法和拉格朗日乘子法。

1．罚函数法

是通过接触刚度在接触力与接触面间的穿透值（接触位移）间建立力与位移的线性关系：

接触刚度*接触位移=法向接触力

对面面接触单元17*，接触刚度由实常数FKN 来定义。 穿透值在程序中通过分离的接触体上节点间的距离来计算。接触刚度越大，则穿透就越小，理论上在接触刚度为无穷大时，可以实现完全的接触状态，使穿透值等于零。但是显而易见，在程序计算中，接触刚度不可能为无穷大（否则病态），穿透也就不可能真实达到零，而只能是个接近于零的有限值。

以上力与位移的接触关系可以很容易地合并入整个结构的平衡方程组K*X=F中去。并不改变总刚K 的大小。这种罚函数法有以下几个问题必须解决：

1）接触刚度FKN 应该取多大？

2）接触刚度FKN 取大些可以减少虚假穿透，但是会使刚度矩阵成为

病态。

3）既然与实际情况不符合的虚假穿透既然是不可避免的，那么可以允许有多大为合适？

因此，在ANSYS 程序里，通常输入FKN 实常数不是直接定义接触刚度的数值，而是接触体下单元刚度的一个因子，这使得用户可以方便地定义接触刚度了，一般FKN 取0.1到1中间的值。当然，在需要时，也可以把接触刚度直接定义，FKN 输入为负数，则程序将其值理解为直接输入的接触刚度值。

对于接近病态的刚度阵，不要使用迭代求解器，例如PCG 等。它们会需要更多的迭代次数，并有可能不收敛。可以使用直接法求解器，例如稀疏求解器等。这些求解器可以有效求解病态问题。

穿透的大小影响结果的精度。用户可以用PLESOL,CONT ,PENE 来在后处理中查看穿透的数值大小。如果使用的是罚函数法求解接触问题，用户一般需要试用多个FKN 值进行计算，可以先用一个较小的FKN 值开始计算，例如0.1。因为较小的FKN 有助于收敛，然后再逐步增加FKN 值进行一系列计算，最后得到一个满意的穿透值。 FKN 的收敛性要求和穿透太大产生的计算误差总会是一对矛盾。解决此矛盾的办法是在接触算法中采用扩展拉格朗日乘子法。此方法在接触问题的求解控制中可以有更多更灵活的控制。可以更快的实现一个需要的穿透极限。

2．拉格朗日乘子法与扩展拉格朗日乘子法

拉格朗日乘子法与罚函数法不同，不是采用力与位移的关系来求接触

力，而是把接触力作为一个独立自由度。因此这里不需要进行迭代，而是在方程里直接求出接触力（接触压力）来。

Kx=F+Fcontact

从而，拉格朗日乘子法不需要定义人为的接触刚度去满足接触面间不可穿透的条件，可以直接实现穿透为零的真实接触条件，这是罚函数法所不可能实现的。使用拉格朗日乘子法有下列注意事项：

1）刚度矩阵中将有零对角元，使有些求解器不克使用。只能使用直接法求解器，例如波前法或系数求解器。而PCG 之类迭代求解器是不能用于有零主元问题的。

2）由于增加了额外的自由度，刚度阵变大了。

3）一个可能发生的严重问题，就是在接触状态发生变化时，例如从接触到分离，从分离到接触，此时接触力有个突变，产生chattering （接触状态的振动式交替改变）。如何控制这种chattering ，是纯粹拉格朗日法所难以解决的。

因此，为控制chattering ，ANSYS 采用的是罚函数法与拉格朗日法混合的扩展拉格朗日乘子法。在扩展拉格朗日法中，可以采用实常数TOLN 来控制最大允许穿透值。还有最大允许拉力FTOL 。这两个参数只对扩展拉格朗日乘子法有效。

在扩展拉格朗日乘子法里，程序按照罚函数法开始，与纯粹拉格朗日法类似，用TOLN 来控制最大允许穿透值。如果迭代中发现穿透大于允许的TOLN 值，（对178单元是TOLN ，而对面面接触单元171-174则是FTOLN ）则将各个接触单元的接触刚度加上接触力乘以拉格朗

日乘子的数值。因此，这种扩展拉格朗日法是不停更新接触刚度的罚函数法，这种更新不断重复，直到计算的穿透值小于允许值为止。 尽管与拉格朗日法相比，扩展拉格朗日法的穿透并不是零，与罚函数法相比，可能迭带次数会更多。扩展拉格朗日法有下列优点：

1）较少病态，个接触单元的接触刚度取值可能更合理。

2）与罚函数法相比较少病态，与单纯的拉格朗日法相比，没有刚度阵零对角元。因此在选择求解器上没有限制，PCG 等迭代求解器都可以应用。

3）用户可以自由控制允许的穿透值TOLN 。（如果输入了TOLN ，而使用罚函数法，则程序忽略它）

依我的个人理解：解的结果会随着接触刚度，穿透容忍度的不同而有所不同。但对于穿透容忍度足够小的情况下，解的结果将随接触刚度影响不会很大。不过，在穿透容忍度小特别小的时候当然不容易收敛。因此在穿透容忍度一定的情况下，当然是接触刚度大穿透小的解更加准确。

大家看看这个吧！我想对大家的理解可能有帮助

摘自 ansys 中文网站 用户专区。（我记得我曾经贴出过）

在有限元分析中，接触单元通常用来描述两物体相互接触或滑动的界面。近年来，ANSYS 开发了一系列的接触单元。刚开始有节点对节点单元CONTAC12和CONTAC52，接着有节点对地单元CONTAC26，然后有节点对面单元CONTAC48和CONTAC49。最近几年，我们引入一类面对面接触单元CONTA169和CONTA174，同时还有一种新的节点对节点单元CONTA178。

虽然接触单元的参数具有多样性，但我们在使用他们时可谨记重要的一点，他们具有一个共同的特点，即除了CONTA178的KEYOPT （2）=0或1外，所有的接触单元都有接触刚度。在现实中实际上相邻结构之间只是一种空隙，但在有限元分析中，这种空隙是一带有刚度的接触单元，这是因为通过刚度矩阵来实现接触算法的。一些接触单元要求使用者输入刚度值，同时另外的接触单元若没有输入则使用缺省值。分析工程师所面对的问题就是针对给定的条件确定一个合理的刚度值。如果过高，问题将会不收敛，如果过低，可能得到错误的结果。那么我们所面对的问题是怎样才能找到一个正确的刚度值？

我认为唯一的方法就是我们必须试用不同的值直到找到正确的值。也

就是刚开始我们应该使用一个较小的值，然后稳步的增加直到分析的结果不再有什么变化。那么对于我们这一特定分析的问题，这一点就是我们所想要的合适值。

我们可举例说明，如图1所示，平行放置两个悬臂梁，并有少许的交迭，下面的左边固支，上面的右边固支，当在上面梁的自由端施加一个向下位移时，梁变形弯曲并接触下面的梁，然后一起向下运动。用SOLID45单元划分梁，用TARGE170和CONTA174面面接触单元来描述相互作用。在此基础上，把CONTA174单元的刚度从非常低变到非常高，从而来观察它对结果的影响和收敛的迭代次数。图2说明了下梁自由端的偏移随接触单元刚度的变化情况，当刚度增加时，偏移量接近一个常数值（我们可以假定它是一个" 正确" 的结果。）图3说明求解所需的迭代次数，当接触单元刚度增加时，求解所需的迭代次数也是增加的，并服从指数关系。如果刚度过高，问题很有可能根本就不收敛。图4说明在上梁自由端接触单元的渗透量，当刚度增加时，渗透量降低。

从这些图可知，当接触单元的刚度为10e6时，可获得合理精确的结果。任何大于该值的刚度对下梁的偏移量没有什么影响，而求解所需的迭代数却显著的增加。对于这个题目，10e6的刚度是很适合的。但是，如果改变边界条件、网格密度、两梁之间的相对位置、材料特性或梁的几何形状，能获得满意结果的接触刚度值将是不同的。比如，如果网格密度增加，则接触单元数将增加，每一个单元上的载荷将降

低。如果接触单元数增加两倍，一个合适的接触单元刚度值应为原来的一半。

由于每个题目都是不一样的，所以在求解之前并没有通用的方法来确定接触单元刚度的最佳值。我们不得不试算一个我们认为合适的值然后查看计算结果。一个有经验的分析工程师可能只查看一个计算结果来判定所取值的合适度，但对于大多数情况而言，最好用一个合理而不过度精确的刚度值进行第一次求解，然后用10倍于该值的刚度进行第二次求解，如果两者结果相差很小，而迭代数增加很多，那么我们则正好取得了曲线上的突变点，从而获得相当好的结果。

接触单元刚度问题仅仅是一个例子，即对于分析工程师来说，总是置疑于分析结果的正确与否是非常重要的，并要意识到数值仿真的局限性和潜在的假设及他们怎样影响所分析问题的结果。

图1

范文三：B样条曲面方向投影问题的几何计算方法

第 21 卷 第 6 期Vol . 21 , No . 6 计算机辅助设计与图形学学报

2009 年 6 月 J O U RN AL O F CO M PU T ER2A ID ED D ESI GN & CO M PU T ER GRA P H ICS J une , 2009 B 样条曲面方向投影问题的几何计算方法

))))1 ,2 1 1 3 陈小雕王毅刚徐 岗雍俊海 ) 1( )杭州电子科技大学图形图像研究所 杭州 310018 ) 2( ) 浙江大学 CAD & C G 国家重点实验室 杭州 310058

) 3( ) 清华大学软件学院 北京 100084

( )xiao diao @hdu . edu . cn

摘 要 B 样条曲面方向投影问题可以通过求解方程组的方法来解决 . 由于方程组所有根中往往只有一个或甚至没

有根与待求解的最近点对应 ,因而绝大多数的求根计算量是不必要的 . 为此讨论了 B 样条曲面的方向投影问题 ,提

出一种简单且高效稳定的几何计算方法 . 该方法充分利用了 B 样条函数的凸包性 ,同时结合 B 样条函数稳定可靠的

分裂算法给出了相应的几何剪枝方法 . 与传统的求解非线性方程组的计算方法相比 ,文中方法可以剪除绝大部分非

线性方程组对应的根 ,且不需要 Newto n 迭代 ,可以应用于平面ΠB 样条曲面间的求交测试问题及 B 样条曲面包围盒

的计算问题 . 实例结果表明 ,该方法具有比传统的相关方法更高的计算效率和更好的稳定性 .

关键词 方向投影 ;B 样条曲面 ;几何剪枝方法

中图法分类号 T P391 . 72

Geometric Method f or t he Direct ional Project ion Problem of B2Spl ine Surfaces

))))1 ,2113Che n Xiao diao Wa ng Yi ga ng Xu Ga ng Yo ng J un hai 1) ( )I nst i t ute of Gra p hics an d I m a ge , H an g z hou D i anz i U ni ve rsi t y , H an g z hou 310018 2) ( )S t ate Ke y L aborat or y of CA D & CG , Z he j i an g U ni ve rsi t y , H an g z hou 310058

3) ( )S c hool of S of t w a re , Tsi n g h u a U ni ve rsi t y , B ei j i n g 100084

The di rectio nal p rojectio n p ro ble m of B 2sp li ne surf ace s ca n be sol ve d by co mp uti ng t he Abstract

roo t s of a no n2li nea r equatio n syst e m . U suall y o ne o r no ne of t he roo t s of t he equatio n syst e m i s mappi ng to t he clo se st poi nt w he re t he mi ni mum di st a nce occ ur s , a nd mo st of t he co mp ut atio n o n fi ndi ng t he roo t s of t he equatio n syst e m i s unnece ssa r y. A si mp le but efficie nt geo met ric p r uni ng met ho d i s p re se nt ed fo r t he di rectio nal p rojectio n p ro ble m of B 2sp li ne surf ace s. It utilize s t he co nve x p rop er t y of t he B 2sp li ne ba si s f u nctio n s a nd t he ro b u st subdivi sio n al go rit h m of B 2sp li ne surf ace , a nd it i s a ble to di rect l y det ect w het her t he mi ni mu m di rectio nal di st a nce occur s at a co r ner poi nt o r at a bo unda r y c ur ve of t he B 2sp li ne surf ace . Co mp a re d wit h co nve ntio nal roo t2fi ndi ng met ho ds of a no n2 li nea r equatio n sy st e m , it ca n e xcl ude mo st of t he roo t s a nd needs no n umerical it e rative met ho d suc h a s t he Newto n met ho d. The p ropo sed al go rit h m ca n be app lie d i n t he i nt e r sectio n t e sti ng p ro ble m bet wee n a p la ne a nd a B 2sp li ne surf ace , a nd t he e ncap sulatio n bo x co mp ut atio n p ro ble m of B 2sp li ne surf ace s. Exa mp le s a re give n to sho w bo t h efficie ncy a nd ro b u st ne ss of t he new met ho d . Key words di rectio nal p rojectio n ; B 2sp li ne surf ace ; geo met ric p r uni ng met ho d

- - - - ( ) 收稿日期 :2008 07 12 ;修回日期 :2008 09 01 . 基金项目 : 国家“九七三”重点基础研究发展计划项目 2004 CB318000; 国家自然科学基 ( ) ( ) ( ) 金 60803076 ,60773179 ,60625202; 霍英东教育基金会基金 111070; 浙江大学 CAD &C G 国家重点实验室开放基金 A0804. 陈小雕 ,男 ,

1976 年生 ,博士 ,副教授 ,主要研究方向为 CA GD , CAD &C G. 王毅刚 , 男 , 1971 年生 , 博士 , 教授 , 主要研究方向为虚拟现实 、计算机图形学.徐 岗 ,男 ,1981 年生 ,博士 ,主要研究方向为几何设计与计算 、数字几何处理与图像处理. 雍俊海 ,男 ,1973 年生 ,博士 ,教授 ,博士生导师 ,主要 研究方向为 CA GD ,CAD 等.

简单地说 ,曲线曲面的方向投影问题就是计算. 本文以最小投影距离和最大投影距离的求解问题 曲线曲面在某方向上的投影距 离的 最大 值和 最 小 投影距离的求解为例 ,首先给出简单的判断条件 ,用

来判定最小点是否在曲面片的角点上 ; 然后给出判 值 . 它 是 CADΠCA GD 领 域 中 的 一 个 基 本 问 题 , 在

[ 122 ] 定子曲面片上是否不包含最小点的判断条件 ; 最后 CA GD 和机械制 造等 领域 有 着 广 泛 的 应 用. 在

计算机图形学 、CADΠCA M 领域中 ,基于 n 组平行平 给出了最小点位于曲面片的边 界曲 线上 的 判定 条 面的层次包围盒技术需要计算 相应 的方 向投 影 问 件 . 利用这些判定条件可以剪除绝大部分方程组的 题 ,而且它在计算机视觉以及机器人运动学等方面 根 . 同时 ,我们在曲面片分裂的过程中使用了启发式[ 124 ] 也有着重要的地位. 此外 ,B 样条曲面构成的物 的方法 ,进一步提高了本文方法的计算效率 .体的包装盒设计和计算也需要求解对应 B 样条曲

面的方向投影问题 ,紧凑的包围盒在材料的节省和

1 几何剪枝方法货物的安全运输等方面有着较重要的意义 . B 样条

( ) 曲面 S u , v沿方向向量 V 的投影问题可以简单地

描述为曲面参数表达式和投影方向作点积的目标函 设给定 B 样条曲面

( ) 数 f u , v的极值求解问题 , 同时返回极值点对应于 n m

( ) ( ) B uB vP,( )i , p j , q i , j S u , v ( ) ( ) = 曲面 S u , v上的参数 ; 分别作 f u , v关于 u 和 v ?? i = 0 j = 0 的偏导 , 可以将原方向投影问题转化为一个非线性 u ? [ u0 , ur ] , v ?[ v0 , vk ] ; [ 4 29 ] 方程组的求根问 题. 对这 些 非线 性方 程组 求 根 其中 , u 和 v 是 2 个参数 , p 和 q 分别为曲面在 u 和) 的过程主要有两步 :1排除不含有实根的区域 , 若无 ( ) ( ) v 方向对应的次数 , { B u} 和{ B v} 分别为由i , p j , q ) 法排除 , 则继续分裂后再尝试排除. 2对于剩余无法

节点向量 U = { u,} 和 V =, u, u, u, , u, 0 r 0 1 r 最后排除的区域 , 利用诸如牛顿法等的数值方法来 [ 7 , 9 ] 求解方程组的根. 一般来说 , 第一步是这类代数 p + 1 p + 1 求解方法的关键 , 其中代表性的方法有投影多边形 , v} 确 定 的 B 样 条 基 函, v ,{ v,, v, v,k k 0 0 1 [ 7 , 9 ] [ 6 ] 以及线性规划相结合的求解方法、切向锥方法q + 1 q + 1 [ 5 ] 以及基于样条函数的求解方法等 . ( )) ( 数 . 曲面 S u , v的 V 方向投影问题 , 即求解 S u , v J o h n so n 等指出 , 非线性 方 程组 求根 方法 的 计 在 V 方向上的最大Π最小投影距离 , 可以归结为目标 [ 6 ] ) 算效率是低下的. 其主要表现为以下 2 点 :1代数 函数 上判断某参数区域内有无根的方法一般不如几何判 n m ) 断方法来得直观 、简单 ;2不是对应方程组中的所有 ( ( ) ( ) ) ( )f u , v= B uB vf 1 i , p j , q i , j?? i = 0 j = 0 实根都需要计算 ,最坏情况下 ,最小和最大投影距离

的极值求解问题 , 其中 f = P?V . 不失一般性 ,i , j i , j 的点均不对应于方程组的任何实根 ,因而所有的用

( ) 本文仅仅讨论目标函数 f u , v最小值的求解过程 . 于求解方程组实根的计算都是不必要的. 对于点投

影问题的研究表明 ,一类几何意义明显的方法可以 ( ) 可以用类似的方法来求解目标函数 f u , v的最大 减少求根过程中不必要的计算 ,从而具有更高的计 ( ) 值 将方法中的“ ?”替换成“ ?”即可. [ 4 ,10212 ] 算效率. 这类 方法 直接 分 析点 与曲 面之 间 的 利用 B 样条基函数的凸包性 , 可以得到如下 3位臵关系 ,显得更加直观 、鲁棒 . Piegl 等根据事先设 个性质.定的容差直接将原始曲面分裂成若干个四边形 ,然 ( [ 4 ] 性质 1 . 若 存在 f , f , f 或 f 不妨 用0 , 0 0 , m n , 0 n , m 后再分析点和这些四边形的关系,该方法可以用 3 3 ) f 统一表示, 如果对所有的 i 和 j , 都有 f ?f i , j 于求解方向投影问题 . 这种直接分裂成四边形的计 3 ( ) 成立 , 则 f 是目标函数 f u , v的最小值 ; 相应的角 [ 11 ] 算是非常耗时的. 文献 [ 11212 ] 中 的方 法不 能 直 点 P, P, P或 P为对应的最小点 .0 , 0 0 , m n , 0 n , m 接用于方向投影问题的求解.

( α本文讨论 B 样条曲面的方向投影问题 ,并提出 性质 2 .若对于所有的 i 和 j , 都有 f i , j ?, 其

α) ( ) α一种几何剪枝方法 . 方向投影问题可以分解为最小 中是实数, 则有 f u , v?.

性质 3 . 若存在整数 k = 0 或 k = n , 使得对于

( ) 所有的 i 和 j , 都有 f?fi , j k , j 成立 , 则 f u , v必定在

曲面边界 u = u或 u = u处取到最小值.0 r

利用性质 1,3 , 可以剪除绝大部分不包含最小

点的子曲面片 . 我们发现 , 在曲面分裂的过程中 , 使

6 期陈小雕等 :B 样条曲面方向投影问题的几何计算方法 723

用启发式的方法选择分裂方向可以进一步提高本文

方法 的 计 算 效 率. 具 体 做 法 如 下 : 设f a , b 是 所 有 例子和结论2

( ) ( { f i , j } 中的最小值 , 则曲面 f u , v将在 u = ua 若为

( ) Bézie r 形式 , 则 u = aΠn或 v = v若为 Bzéie r 形式 ,b 本节将本文方法和文献 [ 6 27 ] 的非线性方程组

) 求根方法进行比较. 1在传统的求根方法中 , 每次分 ) 则 v = bΠm处分裂. 如图 1 所示 , 分裂方向的选取将

( ) ( ) 裂过程需要同时处理 f u , v和 f u , v, 而本文方u v ( ) 使得 f u , v的 4 个角点中的 2 个相邻的 、值最小的

( ) 法中仅需处理 f u , v, 故本文方法对应的每次分裂 ( 角点 A 和 B 落在同一子曲面片上 类似的启发式方

) 所需的计算量约为传统求根方法的一半. 2本文的 ) 法见文献 [ 12 ].

几何剪枝方法具有较好的剪除效果 , 包括直接检测

出最小Π最大投影距离的点是否位于曲面的角点上 ,

) 或是否位于曲面的边界曲线上等. 3本文方法在分

裂过程中使用启发式方法进一步提高了计算效率 .

本文方法可以直接检测出最小Π最大投影距离

对应的点在曲面的角点 , 从而节省了求根方法中所

有用于求解方程组的计算量. 下面再给出 2 个实例 .

如图 2 所示的 2 个实例中 , 最小投影点分别位 于曲1 分裂过程的启发式方法示意图图

面的边界和曲面的内部 . 表 1 所示为传统的求 根方算法 1 . 计算 B 样条曲面的最小投影距离的算法 法和本文方法关于总的计算时间和分裂次数的 ( ) 输入 . B 样条曲面 S u , v以及投影方向向量 V.比较. 这 2 个例子中 , 本文方法的计算时间和分裂次

( ) 输出 . 曲面 S u , v上的投影距离最小值对应 数均大大小于传统的求根方法.

( ) 的点 , 以及点在 S u , v上对应的参数 .

( ) ( ) Step1 . 利用式 1直接计算目标函数 f u , v. 我们可以1 ( ) 认为 f u , v定义了 R中的一个 B 样条曲面 S, 将曲面 S放 f f

ψ入集合 中 .

Step3 . ψStep2 . 若集合 为空 , 转 Step7 ; 否则 , 执行下一步 .

ψ取出集合 中的任意一个曲面 , 不妨记为 S. Step4 . 若 0

S相应的参数区域满足事先给定的容差 , 则0

计算相应的最小点并将它保存到集合 < 中="" ,="" 转="" step2="" ;="" 否则="" ,="">

执行下一步 .

Step5 . 利用性质 1,3 对曲面 S进行验证检测 . 若该曲 0 2 方向投影的计算实例图 面明显不包含最小点 , 转 Step2 ; 若该曲面的最小点在曲面的

边界曲线上 , 则利用文献 [ 12 ]中的算法直接求解出对应的最 表 1 传统求根方法和本文方法计算时间和分裂次数比较 ( ) 小点 , 并记录它在曲面 S u , v上对应的参数 , 将这些信息保 传统的求根方法 本文方法 实例 存在集合 <中 ,="" 转="" step="" 2="" ;="" 否则="" ,="" 执行下一步="" .="" 分裂次数π次="" 计算时间πms="" 分裂次数π次="" 计算时间πms="" step6="" .="" 将曲面="" s分裂成="" 2="" 个子曲面片="" ,="" 并将其放入集="" 0="" 35="" 0="" .="" 694="" 4="" 0="" .="" 035="" 图="" 2="" a="" ψ合="" 中="" ;="" 转="" step="" 2="" .="" 图="" 2="" b="" 156="" 4="" .="" 067="" 26="" 0="" .="" 342="" step7="" .="" 在集合=""><的所有最小点中寻找对应投影距离的>

( ) 值最小的点 , 返回该点及其在曲面 S u , v上对应的参数 .

传统的求根方法均使用 Newto n 迭代法来提高 Step8 . 结束 .

计算效率 . 在某些情况下 , New to n 迭代法可能会给 我们可以利用类似的方法求解出最大投影距离

出错误的结果 . 在图 3 所示的实例中 , 本文方法得到 ( ) 对应的点及其在曲面 S u , v上对应的参数 , 最后的

的最小投影点为实心圆表示的点 P , 若分裂精度为 B 样条曲面的投影算法则同时返回最小Π最大投影 - 3 - 4 ( ) 10 , 10 的情况下 , New to n 迭代法会收敛到实心 距离对应的点对及其在曲面 S u , v上对应的参数.

圆所示的点 Q , 结果出现错误 ; 若分裂精 度 提高 到

- 5 10 , 则传统的求根方法也能收敛到实心点 P , 结果

和本文方法一致.

的几何剪枝方法. 该方法能直接检测出最小Π最大投 影距离对应的点是否是曲面的角点 、或是否落在曲 面的边界曲线上 ;在分裂过程中同时使用了启发式 的方法 ,以进一步提高其计算效率. 本文方法不需要

进行 Newto n 迭代 ,从而避免了因迭代初值不当而 可能引发的错误结果 ,具有较高的计算稳定性. 实例 也表明本文方法具有较高的计算效率和稳定性. 我 们今后的工作之一就是将本文方法应用到 N U RB S

曲面中. 图 3 Newto n 迭代法可能收敛到错误结果的例子

参 考 文 献本文方法也可应用于平面ΠB 样条曲面间的求 [ 7 ] 交测试问题. 传统的求交测试方法直接利用曲面

Kay T L , Kajiya J T. Ray t raci ng co mplex scene s [ C ] ΠΠ [ 1 ] 控制网格的信息来求解 . 本文方法有如下 2 个特点 : Proceedi ngs of t he 13t h A nnual Co nf erence o n Co mp ut er ) 1每次分裂过程对应的计算量较小 . 传统的方法是 Grap hics a nd Int eractive Techniques , Dalla s , 1986 : 2692278 ( ) 分裂 S u , v, 对应的维数一般为 3 维 ; 而本文方法 [ 2 ] H u S M , Wall ner J . A seco nd o r der al go rit h m fo r o rt ho go nal ( ) ( ) 是分裂 f u , v, 次数 、节点向量等信息和 S u , v完 p rojectio n o nto cur ve s a nd surf aces [J ] . Co mp ut er Aided

( ) Geo met ric De sign , 2005 , 22 3: 2512260 全相同 , 但对应的维数是 1 维的 , 计算量为传统方法

[ 3 ] J o hn so n D E , Co hen E . A f ra mewo r k fo r efficient mi ni mu m ) 的三分之一 . 2本文方法具有更好的剪枝效果. 它不 di st a nce co mp ut atio n s [ C ] ΠΠProceedi ngs of I E EE 仅能直接检测出最小Π最大投影距离对应的点是否 Int er natio nal Co nf erence o n Ro bo tics & A uto matio n , 在角点上 , 还能检测出最小Π最大投影距离对应的点 L euven , 1998 : 367823684

是否在曲面的边界曲线上 , 从而将曲面的方向投影 [ 4 ] Piegl L A , Tiller W. Pa ra met erizatio n fo r surf ace fit ti ng i n

rever se engi neeri ng [J ] . Co mp ut er 2Aided De sign , 2001 , 33 问题转化为曲线的方向投影问题 , 在一定程度上降

( ) 8: 5932603 低了问题的复杂度. 综合上述 2 个特点 , 本文方法也 [ 5 ] El ber G , Ki m M S . Geo met ric co n st rai nt sol ver u si ng 具有较高的计算效率 . 图 4 所示为方向投影算法应 multiva riat e ratio nal spli ne f unctio ns [ C ] ΠΠProceedi ngs of t he 用在平面ΠB 样条曲面间求交测试的 2 个例子 . 表 2 6t h A CM Sympo si u m o n Solid Mo deli ng and Applicatio n s ,

所示为 2 种方法对应的曲面分裂总次数以及相应的 A nn A r bo r , 2001 : 1210

[ 6 ] 计算时间 , 可以看出 , 本文方法比文献 [ 7 ]方法曲面 J o hn so n D E , Co hen E . Di st a nce ext rema fo r spli ne mo del s

usi ng t a ngent co nes [ C ] ΠΠProceedi ngs of t he Co nf erence o n 分裂次数少 、计算效率高. 本文中的例子均用VC + +Grap hics Int erf ace , Victo ria , 2005 : 1692175 在 1 . 7 GHz C PU ,768MB 内存的 PC 机上实现.[ 7 ] Pat ri kala ki s N M , Maekawa T. Shape i nt er ro gatio n fo r

co mp ut er aided de si gn a nd ma nuf act uri ng [ M ] . Kra ko w ska :

Sp ri nger , 2001

[ 8 ] Seder ber g T W , Ni shit a T. Cur ve i nt er sectio n u si ng Bézier

( ) clippi ng [J ] . Co mp ut er 2Ai ded De si gn , 1990 , 22 9 : 5382

549

[ 9 ] Zho u J M , Sher broo ke E C , Pat ri kala ki s N M . Co mp ut atio n

of st atio na r y poi nt s of di st a nce f unctio n s [J ] . Engi neeri ng ( ) wit h Co mp ut er s , 1993 , 9 4: 2312246 [ 10 ] Chen X D , Zho u Y , Shu Z Y , et al . Imp ro ved al gebraic 图 4 平面ΠB 样条曲面间的求交测试实例 al go rit h m o n poi nt p rojectio n fo r Bézier cur ve s [ C ] ΠΠ

Proceedi ngs of t he 2 nd Int er natio nal Mul ti sympo si u ms o n 表 2 文献 [ 7 ]方法和本文方法计算时间和分裂次数比较

Co mp ut er and Co mp ut atio nal Science s , Io wa Cit y , 2007 : 文献[ 7 ] 方法 本文方法 1582163 实例 分裂次数Π次 计算时间Πms 分裂次数Π次 计算时间Πms Ma Y L , Hewit t W T. Poi nt i nver sio n a nd p rojectio n fo r [ 11 ] 20 0 . 234 2 0 . 019 图 4 a N U RB S cur ve a nd surf ace : co nt rol pol ygo n app roach [ J ] .

图 4 b ( ) Co mp ut er Aided Geo met ric De si gn , 2003 , 20 2: 79299 68 0 . 784 5 0 . 058

Seli mo vic I . Imp ro ved al go rit h ms fo r t he p rojectio n of poi nt s [ 12 ]

o n N U RBS cur ve s a nd surf ace s [J ] . Co mp ut er Aided 本文结合 B 样条函数的凸包性和稳定的分裂 ( ) Geo met ric De sign , 2006 , 23 5: 4392445 方法 ,提出一种用于求解 B 样条曲面方向投影问题

范文四：对偶单纯形法计算方法存在的问题

摘 要:通过举例说明对偶单纯形法计算方法存在的问题，供相关学习者在使用中借鉴。

中国论文网 http://www.xzbu.com/3/view-8526.htm

关键词:单纯形法;对偶单纯形法;计算方法;改进

作者简介:李小林(1964-)，男，郑州大学西亚斯国际学院商学院副教授，硕士研究生，研究方向:统计学、运筹学。

中图分类号:FO221.1 文献标识码:A doi:10.3969/j.issn.1672-3309(x).2011.11.62 文章编号:1672-3309(2011)11-135-02

一、引言

在线性规划问题数学模型求解时，根据数学模型的不同，本着简化计算的目的，可选择单纯形法或对偶单纯形法。按照对偶单纯形法的计算方法，有些数学模型在求解时会存

1

在一些不必要的转换，使计算量相对增加。例如数学模型:

的求解，可选择用单纯形法或对偶单纯形法计算。

二、单纯形法计算

用单纯形法计算，数学模型的标准形式为:

从表1中可以看出，该数学模型有无界解。

三、对偶单纯形法计算

如果用对偶单纯形法计算，数学模型的标准形式为:

从表1和表2可以看出，两种方法计算的结果完全相同，该数学模型有无界解。

四、结论

按照以上的计算，可以看出，单纯形法计算转换了3次，而对偶单纯形法计算只转换了2次，且计算中用的变量个数也少，因此本例选择对偶单纯形法计算比较简便。但是在对偶单纯形法计算转换的2次中，第一次用x2换x7，第二次用x7换x5，使转换次数多了一次。其实数学模型用对偶单纯形法的简便计算如表3: 从表3计算可以看出，这次转换并没有按照对偶单纯形法的转换原则转换，而是先把基变量中非最小的人工变量转换出来，从而达到一次转换就计算出结果的效果。事实上，本例中，只要b3小于,2，不大

2

于,6，即,6?b3?,2，表3的计算就只转换1次。

类似这样的例子，在计算时经常会遇到，这就要求我们在学习中要灵活掌握知识，而不是死学书本，才能领悟到知识的真谛。

百度搜索“就爱阅读”,专业资料,生活学习,尽在就爱阅读网92to.com,您的在线图书馆

3

范文五：选择合理的计算方法解决问题

三、巩固深化，提升策略

四、课堂总结，知识延伸

件商品的价格再计算。 5. 解决收银员应收多少钱的问题，需要利用哪些信息。

6. 组织学生谈论，收银员收钱需要精确计算么？怎么列式。

7. 组织学生列竖式计算：558+225+166的结果。

8．组织学生谈论：计算时列两个竖式计算简便还是列一个竖式计算简便。

9. 回顾与反思，以后解决实际问题时需要注意些什么。

1. 结合生活中的具体情境，发现并提出一些数学问题，选择合理的策略解决。 2. 完成46页12题。

通过今天学习有哪些收获

学生提取信息，汇报

需要精确计算

独立解答，集体反馈

集体交流，达成共识，列一个竖式计算简便

小结：解决实际问题时，要认真分析具体情况，灵活选择计算的策略。

独立完成，集体交流反馈。

培养学生理解题意的能力

尝试计算，提出质疑， 教师有针对性的指导

练习巩固，形成技能。 ；

转载请注明出处范文大全网 » 烙饼计算方法