綫性規划成套生产最大問題的图解法的研究

1.什么是成套生产最大問題及本文的簡介如果有n种机床A_1,A_2,…,A_n,生产某种由m个另件B_1,B_2,…,B_m构成的产品,机床A_j生产B_i种另件的效率为α_(ij)(单位时間內生产另件的个数),α_(ij)≥0,一般說来,对于不同的(ij)α_(ij)不必相同,由于成品需要成套地进行生产,可以视为求零件B_1,B_2,…,B_m的个数相等,这就出現了两个問題: (1)在一定的阶段內,如何分配各种机床加工各     

对中学数学教学联系实际的一些看法——从图上作业法誕生过程談起

图上作业法是由羣众中来的一个优秀的数学方法,数学通报1958年11期已作了介紹,經过了理論上的总結提高后,目前它已經在很多有关物資調运的部門中得到推广,而且国家經委已批轉了中国科学院数学研究所关于推广图上作业法的建議,即又回到羣众中去了,它的誕生及成长过程是这样的丰富多彩,激动人心,因而不能让它默默无聞,必須公之众目,在中国数学会北京分会举办的一次报告会上,我介紹了这一工作,并談了自己的一点体会,同志們认为还不无有益之处,因此我重新把它整理了一下,提出来和大家作进一步的研討。意見很不成熟,希望同志們多加指正,为了避免重复,关于图上作业法的方法和理論証明,請看1958年11期数学通报,这里就不重述了。 (一) “实践-理論-实践”的公式在数学中的应用为什么我从图上作业法談起呢?因为它具有下述的三方面特点:     

具有次限制的最小树问题

F.Glover和D.Klingman在[2]中给出了予先确定的一个点x具有固定次数为k的最小树算法。 本文给出了任意m个互不关联点具有次数限制的最小树问题的算法.算法的基础是线性规划的对偶理论。     

按字典序遍数K分树

本文研究了Ll-限制K分树,文中用叶子的层数表示一个K分树,每个具有n个叶子的K分树对应一个n个正整数组成的序列.首先给出由n个正整数组成的序列代表一个具有n个叶子的Ll-限制K分树的充分必要条件.然后给出一个字典序列出所有具有n个叶子的Ll-限制K分树的算法.     

两类 Hamilton 次序列

无向图中 Hamilton 圈存在的充分条件,虽有一些,但几乎都包含在 Chvátal 的次序列条件和 Bondy 与 Chvátal 的 n-稳定闭包是完全图的条件里.本文提出两类次序列,虽然它们都不满足 Chvátal 条件,并且也有一个不满足闭包是完全图的条件,但是却都保证了图的 Hamilton 圈的存在性.从而为进一步从次序列方面研究图的 Hamilton 性,提供了新的依据.     

过指定点的最小单圈图

本文提出并解决了在无向图上求过两个指定点的最小单圈图问题。它有一定的实际背景,反映了图论中某些结构的内在联系,同时,对Travelling salesman问题,提供了比1-树更好的下界估计。     

学习《人的正确思想是从那里来的?》——谈对有关数学理论联系实际的一种论点的看法

<正> 关于辩证唯物论的认识论,毛主席在《人的正确思想是从那里来的?》一文中,对于物质可以变成精神,精神可以变成物质的两个飞跃现象作了极为精确的概括.文章一开始就指出:“人的正确思想是从那里来的?是从天上掉下来的吗?不是.是自己头脑里固有的吗?不是.人的正确思想,只能从社会实践中来,只能从社会的生产斗争、阶级斗争和科学实验这三项实践中来.”形形色色的唯心主义的认识论,首先就是在认识的来源     

竞赛图具有弧泛回路性的一个充分条件

关于竞赛图的弧泛迴路性问题,Alspach证明了正则竞赛图具有此性质.朱永津、田丰证明了若竞赛图 T 中任意一个弧(v,v_0)都满足条件 d~+(v_0)+d~-(v)≥p-2,这里 p 为 T 的顶点数,则当 p≥7时,T 中过任一弧存在迴路系列 C_4,C_5,…,C_p.本文提出并证明了若 T 满足以下条件:当 d~+(v)<1/2(p-1)时,在 v 的外邻集 O(v)中有一点 u,d~+(u)≥1/2(p-1);当 d~+(v_1),d~+(v_2)<1/2(p-1)时,有 u_1,u_2∈O(v_1)∪O(v_2),d~+(u_1),d~+(u_2)≥1/2(p-1),且对入次亦满足相应的条件,则当 p≥9和最小次数δ≥4时,过 T 的每一个弧存在迴路系列 c_6,c_7,…,c_p.此充分条件不要求顶点次数的正则性和几乎正则性,对 T 的不正则度 q=(?)|d~+(v)-d~-(v)|一般来说也没有限制.     

图的周长的一个度条件

本文用度和给出一个关于图的最长圈的存在性条件.这一结果是N.Dean和P.Fraisse的相应结论的推广.     

线性規划中康-西問題对偶算法的最大迭代步数

<正> 由对偶理論知道这两个問題或者皆无最优解,或者同时有最优解,且取相同的最优值.因此,解这两个問題是等价的. 解問題1是在K的极点上进行迭代的,解問題2是在K′的极軸(定义見后文)上进行迭代的,它們迭代一步的計算量大体相近.M.A.Simonnad和G.F.Hadley給出