经典一维装箱问题近似算法的研究进展

自20世纪70年代开始,随着计算复杂性理论的建立,近似算法逐渐成为组合优化的重要研究方向。作为第一批研究对象,装箱问题引起了组合优化领域学者的极大关注。装箱问题模型简单、拓展性强,广泛出现在各种带容量约束的资源分配问题中。除了在物流装载和材料切割等方面愈来愈重要的应用外,装箱算法的任何理论突破都关乎到整个组合优化领域的发展。直到今天,对装箱问题近似算法的研究仍如火如荼。本文主要针对一维模型,简述若干经典Fit算法的发展历程,分析基于线性规划松弛的近似方案的主要思路,总结当前的研究现状并对未来的研究提供一些参考建议。     

经典一维装箱问题近似算法的研究进展

自20世纪70年代开始,随着计算复杂性理论的建立,近似算法逐渐成为组合优化的重要研究方向。作为第一批研究对象,装箱问题引起了组合优化领域学者的极大关注。装箱问题模型简单、拓展性强,广泛出现在各种带容量约束的资源分配问题中。除了在物流装载和材料切割等方面愈来愈重要的应用外,装箱算法的任何理论突破都关乎到整个组合优化领域的发展。直到今天,对装箱问题近似算法的研究仍如火如荼。本文主要针对一维模型,简述若干经典Fit算法的发展历程,分析基于线性规划松弛的近似方案的主要思路,总结当前的研究现状并对未来的研究提供一些参考建议。     

拓扑余维数不超过2的(D4, S1)等变分歧问题的分类

应用奇点理论方法研究参数具有某种对称性的等变分歧问题. 给出了分歧参数具有S¹对称性、状态变量具有D₄对称性的等变分歧问题f:(R²×R²,(0,0)®R² 在拓扑余维数不超过2的条件下的分类, 并建立了相应的识别条件.     

直径不超过2的2连通无爪图是哈密顿图

不包含2K_2的图是指不包含一对独立边作为导出子图的图.Kriesell证明了所有4连通的无爪图的线图是哈密顿连通的.本文证明了如果图G不包含2K_2并且不同构与K_2,P_3和双星图,那么线图L(G)是哈密顿图,进一步应用由Ryjá(?)ek引入的闭包的概念,给出了直径不超过2的2连通无爪图是哈密顿图这个定理的新的证明方法.     

余维数不超过2的奇点定位的一类迭代方法

余维数不超过２的奇点定位的一类迭代方法朱正佑，丛玉豪（上海大学力学所，兰州大学数学系）ＡＣＬＡＳＳＯＦＩＴＥＲＡＴＩＧＶＥＭＥＴＨＯＤＦＯＲＬＯＣＡＴＩＮＧＴＨＥＳＩＮＧＵＬＡＲＰＯＩＮＴＳＷＩＴＨＣＯＤＩＭＥＮＳＩＯＮ≤２￥ＺｈｕＺｈｅｎｇ－ｙｏｕ...     

点数不超过20的旗传递非对称2-设计

本文研究了旗传递点数不大于20的2-(v,k,λ)设计的分类,证明了当(r,λ)=1时,在同构意义下只存在18个这样的设计.     

层状不均匀介质的一维地球模型物性参数反演

本文建立了层状不均匀非吸收介质的反问题模型，与已有的模型相比，它更切合实际，讨论了这种模型下介质的物性参数和几何参数的反演问题，它包括特性阻抗Ｋ（ｘ）间断状态参数Ｃ１，Ｘｉ，ｎ。借助于行波传播算子Ｋ１和有间断系数的方程的弱Ｒｉｅｍａｎｎ函数，得出每一层上波场正问题的表达式，供助于此表达式把反演物性参数的问题，转化为确定Ｍ＾ｋ（ｘ，ｙ，０）的问题，而关于Ｍ＾ｋ（ｘ，ｙ，０）我们得到的是一个第二类ＦＲ     

三维装箱问题的模型与改进遗传算法

三维装箱问题是一类NP-hard的组合优化问题,构建一个适当的数学模型并设计高效快速的算法具有重要的理论和现实意义.该文将箱子空间划分为立方体单元,依此构建三维装箱问题的混合整数规划模型,并通过改进遗传算法求解,剔除大量不可行解提高了收敛速度.实验结果表明此算法运算过程及结果稳定,具有较强的实际应用价值,能有效解决复杂的三维装箱问题.     

f(x_1 x_2/2)与(f(x_1) f(x_2))/2比大小

自变量平均值的函数值∫(x_1 x_2)/2与对应自变量函数值的平均值f(x_1) (x_2)/2 的大小关系,视具体函数而定。以下四组值比大小,固然可用解析式完成,但观看对应图象,可做到一望而解。     

从X~(1/2)±y~(1/2)不叫共轭根式谈起

在一次听课中,听到一位初二代数老师在讲解根式除法运算时,提到x~(1/2)+y~(1/2)和x~(1/2)-y~(1/2)是一对共扼根式的说法。当时感到此说法似有不妥,因为x~(1/2)±y~(1/2)本来就不应叫做根式,而应叫做无理式。后来又偶尔从一本《中学数学复习资料》(江苏人民出版社,1979年5月版)中,看到对“根式”有这样一个定义:“根式(无理式)含有开方运算的代数式叫做根式。”以上这两个例子有个相同的观点,即“根式”和“无理式”是同一概念。既如此,那么它们的外延应该完全重合。事实并     

利用1/V~2=1/V_1~2 1/V_2~2求旋转体体积

大家知道:分别以直角三角形的斜边、两直角边所在直线为轴,旋转这个直角三角形所得的三个旋转体的体积为V、V_1、V_2,则 1/V~2=1/V_1~2 1/V_2~2·这是高中《立体几何》(甲种本)P_(146)第13题的结论.用它来解1988年高考第四题是件有趣的事: 如下图,正三棱锥S-ABC的侧面是边长为α的正三角形,D是S.4的中点,E是BC的中点,求△SDE绕直线SE旋转一周所得到的旋转体的体积(一九八八年全国高考理工类第四大题)。     

关于不等式链√a2+b2/2≥a+b/2≥√ab≥2/1/a+1/b 的函数与几何模型

在新课程高中数学教材(必修5)中,对基本不等式a+b/2≥√ab (a,b>0)的教学,提出了"探索并了解基本不等式的证明过程"的要求.几种版本的教材(如北师大版,苏教版)对这个不等式都给出了形象的几何模型.     

基于对角转轮样式的托盘装箱优化模型

针对托盘装箱问题(PLP),建立了对角转轮样式下具有托盘柔性的整数规划模型,设计了求解模型的启发式算法,并利用VB程序对模型的最优解及装箱图谱进行了讨论分析,结果表明:对角转轮样式就提高具有较大长、宽比箱子的装载效率以及解决装箱压缝问题方面具有明显的优势;而柔性也是影响托盘装载效率的重要因素之一,具有较大的回报率.     

近似计算有效位数的增长不超过几何级数

假定我们要用加、减、乘、除开方等运算去计算任何一个实数或复数,并且假定每次运算都是绝对精确的。我们证明了:不论用什么方法,如果不能在有限步之内达到绝对精确的值,则要精确到n位小数,至少需要正比于logn的运算次数。换言之,若不能在常数步之内求得精确解,则计算的有效位数的增长不能超过一个几何级数,中间的情况是不存在的。如果只许可使用四则运算,那末逼近一个无理数的最高速度是平方收敛。     

从1/2+1/3=2/5引发的思考

我国的一位学者有一次到国外去考察,听了一堂洋教师的分数加法课.在课堂上,老师首先提问学生21 13等于多少?不一会儿,许多学生纷纷站起来回答:12 31=25.然后,老师又问其余的学生,你们有不同意见吗?其余学生都说没有.这时老师便说:“那好!就让21 13等于52吧!这就是分数的加法,…     

1/x_3=1/x_1+1/x_2

春耕一片田地,甲队单独进行a天可以完成,乙队单独进行b天可以完成。甲、乙两队合耕几天可以完成? 设甲、乙两队合耕x天可以完成,那末 1/x=1/a+1/b 两根导线的电阻分别是R_1和R_2,则其总电阻R满足等式 1/R=1/R_1+1/R_2。物体、象和焦点到透镜的距离这三个量之间有下列关系: 1/f+1/q=1/h。以上三个实际问题反映到数学中来,就是研究x_1,x_2,x_3这三个正量之间的下列关系: 1/x_3=1/x_1+1/x_2。(*) 在等式(*)中,如果x_1,x_2两个量已知,那么我们可以用解分式方程的方法,解得 x=x_1x_2/(x_1+x_2)。(*′)     

公式2(S_0)1/2=S1/2 (S′)1/2的推广与应用

在高一《立体几何》中 ,关于台体 (棱台、圆台 )的中截面有这样的一个性质 :2Ｓ0 =Ｓ Ｓ′(《立体几何》Ｐ64 例 2及Ｐ80 习题十第 1 1题 ) .换句话说 ,台体 (棱台、圆台 )的上底面面积Ｓ′、中截面面积Ｓ0 、下底面面积Ｓ的算术平方根Ｓ′、Ｓ0 、Ｓ组成了一个等差数列 ,公差ｄ =12 Ｓ -Ｓ′ .是不是只有中截面与上、下底面的面积具有这种性质 ?其它截面与上、下底面的面积是否具有类似的性质 ?我们不仿看一下 .设台体 (棱台、圆台 )的上、下底面面积分别是Ｓ′、Ｓ ,台体 (棱台、圆台 )的高为ｎｈ ,设Ｓ1 、Ｓ2 …Ｓｎ- 1 分别是过台体 (…     

S_n=na_1 n(n-1)d/2的组合模型

1　问题的提出在学习组合数公式时 ,王老师提出了一个很有趣的问题 :等差数列求和公式Ｓｎ=ｎａ1 ｎ(ｎ - 1 )2 ｄ ,还可以写成Ｓｎ=Ｃ1ｎａ1 Ｃ2 ｎｄ ,那么 ,等差数列前ｎ项和Ｓｎ 与组合到底有什么联系呢 ?2　思维的过程很自然地 ,我先从等差数列方面着手 ,可是怎么也找不到它与组合的联系 .于是我就反过来想 ,从组合中找等差数列 .注意到Ｃ2 ｎ好像与握手问题有关 .我就想方设法从中构造出等差数列 ,如何构造呢 ?同时考察ｎ个人握手很难与等差数列相联系 ,那么我就把ｎ个人一个一个分开讨论 .先看单独的一个人 ,这时没有人与之握手 ,故…     

基于图着色模型的冲突装箱问题启发式算法

带有冲突关系装箱问题的优化目标是在满足货物冲突关系的前提下,使用数量最少的货箱完成货物装箱的目的。本文分析了冲突装箱问题的数学模型,提出了基于图着色模型的启发式算法进行求解。首先,使用冲突图来描述货物之间的冲突关系;其次,基于冲突图,采取图着色的方式将货物进行分组,并且组内的货物之间不存在冲突关系;最后,采取改进FFD算法对每组的货物进行装箱操作。实验表明,本文提出的启发式算法能够快速有效地找到问题的可行解,为此类装箱问题的求解提供了新思路。     

条形装箱问题的优化模型和增广Lagrange算法

This paper formulates a two-dimensional strip packing problem as a non-linear programming(NLP)problem and establishes the first-order optimality con-ditions for the NLP problem.A numerical algorithm for solving this NLP problemis given to find exact solutions to strip-packing problems involving up to 10 items.Approximate solutions can be found for big-sized problems by decomposing the setof items into small-sized blocks of which each block adopts the proposed numericalalgorithm.Numerical results show that the approximate solutions to big-sized prob-lems obtained by this method are superior to those by NFDH,FFDH and BFDHapproaches.