凸多边形切割方法

本文讨论了二维平面上给定区域内的凸多边形切割问题 .按“顶点度数”该问题可以分为两种类型 .在两种类型下并给出了凸多边形的简单切割方法 .     

关于拓扑流形到某些欧氏空间的拓扑嵌入

本文研究了拓扑流形的拓扑嵌入问题,得出了边界为(k—1)-连通的n维k-连通紧带边拓扑流形能局部平坦地整齐嵌入D^2n-h,局部平坦地嵌入S^2n-h-1的一个充分性条件(0≤h≤2k),且给出了它的一些应用。     

冲裁件有约束最优剪切方式的设计

本文讨论冲裁件有约束最优剪切方式的设计问题 .阐明最优剪切排样方式的规范结构 ;采用分支定界法求解冲裁件无约束排样问题 ;将有约束排样问题转换为求解一系列的无约束排样问题 ,并通过对解的性质分析提高算法效率 .实验计算结果说明本文算法十分有效 .最后给出一例题的最优排样方式 .     

一个切割问题的再讨论

文 [1 ]提出了这样一个问题 :图 1某工艺品厂要从一块矩形的大理石板中用截断切割方式割出一块各边与原矩形平行的较小的矩形石板 (如图 1 ) .1 )设切割的成本与切割长度成正比 ,当ｍ ,ｎ ,ｐ ,ｑ互不相同时 ,共有多少种成本不同的切割顺序 ?2 )请从如图 1 (ｍ >ｎ >ｐ >ｑ >0 )所示的一般情况下 ,推证使总成本达到最小的切割顺序 ;3)假定切割成本是 0 .2 0元 /ｃｍ ,ａ =70ｃｍ ,ｂ =1 0 0ｃｍ ,ｍ =30ｃｍ ,ｎ =2 0ｃｍ ,ｐ =1 0ｃｍ,ｑ =5ｃｍ时 ,求最小的切割成本 .对于这个问题 ,文 [1 ]的答案是 :1 )共有 1 4种成本不同的切割顺序 ;2 …     

凸多边形的最优切割策略

本文研究的是在一个平面区域内切割出一个预定的凸多边形的最优策略问题 .首先应用动态规划建立模型 ,然后 ,证明了优化变换的两个准则 ,最后 ,我们对极先切割边进行了讨论 ,得出了简明的最优切割策略     

紧带边流形的整齐嵌入和内浸

本文研究了n维紧带边流形到圆盘D^n+k的整齐嵌入和内浸问题^1-6。给出了在亚稳定范围内整齐嵌入和内浸的充分性条件及整齐嵌入的整齐同痕类集合和内浸正则同伦类集合的表示形式。     

关于“截断切割”的最优设计

针对 1 997年全国大学生数学建模竟赛 B题 ,对于换刀费用 e=0的情况 ,本文设计了一种异常简捷的切割厚度排序法来寻找最优切割方案 ,同时在数学上给出了严格的证明 .对于换刀费用 e≠ 0的情况 ,以 e=0时得到的最优切割方案为基础 ,先通过简单的调整原则寻找出限定不同换刀次数时各自的最优切割方案 ,再通过费用比较便可简捷地得到随 e值的大小而变化的最优切割方案 .本文构造的模型在求解时无须用计算机编程 ,只用手算即可简捷地得到答案     

多角形柱体扭转的裂纹切割解法

使用奇异积分方程方法及裂纹切割技巧,在精确满足问题的边界条件和角点条件下,对含有角点的多角形柱的扭转,提出了一种全新的严格求解方法;给出了若干算例,证明方法是正确的。     

关于多项式映射自同构恒等集的一个注记

本文给出了判定一个仿射代数集是否是一个自同构恒等集的充分条件.作为一个推论,我们给出了Mckay-Wang的一个问题的一个新证明.我们也给出了一些具体的例子来说明主要的定理.     

互补问题的一个修改算法

本文给出了一个修改的路径跟踪预测校正非内点算法 ,同时给出了一个新的中心路邻域的表示 .并在此基础上给出了全局和局部收敛性 ,最后给出的数值结果验证了其有效性     

An approximation algorithm for cutting out convex polygons

We provide an O(logn)-approximation algorithm for the following problem. Given a convex n-gon P, drawn on a convex piece of paper, cut P out of the piece of paper in the cheapest possible way. No polynomial-time approximation algorithm was known for this problem posed in 1985.     

Cutting-plane proofs in polynomial space

Following Chvátal, cutting planes may be viewed as a proof system for establishing that a given system of linear inequalities has no integral solution. We show that such proofs may be carried out in polynomial workspace.Research supported by Sonderforschungsbereich 303 (DFG), Institut für Operations Research, Universität Bonn, FR Germany and by NSF grant ECS-8611841.     

二维实用下料问题的数学模型及较优解

二维下料问题是2004年首届全国部分高校研究生数学建模竞赛B题.建立了二维下料问题的数学模型,找到了用料451块,下料方式数为37的较优解,并证明了此问题总用料的下界是449块.     

Embedding optimisation algorithms with Mosel

Algebraic modelling languages allow models to be implemented in such a way that they can easily be understood and modified. They are therefore a working environment commonly used by practitioners in Operations Research. Having once developed models, they need to be integrated inside the company information system. This step often involves embedding a model into a programming language environment: many existing algebraic modelling languages make possible to run parameterised models and subsequently retrieve their results, but without any facility for interacting with the model during the model generation or solution process.In this paper we show how to use the Mosel environment to implement complex algorithms directly in the modelling language.The Office cleaning problem is solved by a branch-and-cut algorithm, implemented entirely in the modelling language (including the definition of the callback function for the solver). Secondly, a cutting stock problem is solved by column generation, also implemented in the modelling language.AMS classification: 90Cxx, 65K05, 68N15     

“Miniaturized” Linearizations for Quadratic 0/1 Problems

In order to solve a quadratic 0/1 problem, some techniques, consisting in deriving a linear integer formulation, are used. Those techniques, called “linearization”, usually involve a huge number of additional variables. As a consequence, the exact resolution of the linear model is, in general, very difficult. Our aim, in this paper, is to propose “economical” linear models. Starting from an existing linearization (typically the so-called “classical linearization”), we find a new linearization with fewer variables. The resulting model is called “Miniaturized” linearization. Based on this approach, we propose a new linearization scheme for which numerical tests have been performed.     

A near equitable 2-person cake cutting algorithm

Let the cake be represented by the unit interval of reals, with two players having possibly different valuations. We propose a finite algorithm that produces contiguous pieces for both players such that their values differ by at most ?, where ??>?0 is a given small number. Players are not required to reveal their complete value functions, they only have to announce the bisection points of a sequence of intervals. If both utility functions are everywhere positive then the algorithm converges to the unique equitable point.     

An algorithm for the two-dimensional assortment problem

In this paper we consider the two-dimensional assortment problem. This is the problem of choosing from a set of stock rectangles a subset which can be used for cutting into a number of smaller rectangular pieces. Constraints are imposed upon the number of such pieces which result from the cutting.A heuristic algorithm for the guillotine cutting version of the problem is developed based on a greedy procedure for generating two-dimensional cutting patterns, a linear program for choosing the cutting patterns to use and an interchange procedure to decide the best subset of stock rectangles to cut.Computational results are presented for a number of test problems which indicate that the algorithm developed produces good quality results both for assortment problems and for two-dimensional cutting problems.