离散数学在数学系教学计划中应占什么地位

我国数学系教学计划自五十年代制定以来,虽经多次修改,但是总起来说变化不大。分析系统的课程,包括数学分析,微分方程,实函、复函、泛函等,在整个教学计划中占的比例很大,代数、几何,概率等各占一个小部分,而离散数学(如图论、组合论、逻辑代数等)则几乎没有。     

线性不等式组的消去法

线性不等式组的理论是线性规划、对策论等运筹学分枝的理论基础。近几十年来,由于线性规划、对策论等在生产实践中获得了广泛的应用,线性不等式组的理论也就引起了人们的很大注意。线性不等式组与线性方程组有很多相似的地方。本文的目的就是介绍线性不等式组中的消去法,并且利用它来证明一个判别线性不等式组是否有解的判别法则。 (一) 基本概念首先声明一下,我们是在实数范围内进行讨论,以下提到的数指的都是实数。形如的不等式为线性(或一次)不等式。而称形如的不等式组为线性不等式组。上面(1)和(Ⅰ)中的d_(ij),d,a_(ij),b_i等都是数,x_j是未知数。由于用不等号“≤”连结的不等式可以通过在不等式的两边乘-1而化为用“≥”连结的不等式,故我们只要研究用“≥”连结的不等式就够了。     

由渠道设计问题引出的有向图上最小树形图问题的解法

在[1]中首先提出求一般有向图的最小树形图的计算方法。以后,在[2]中,对于一类特殊的有向图,即等双回路图,指出了[1]中的方法可以改进,使得计算的速度可以加快。 在最小树形图的实际应用中,渠道设计问题是一个重要的方面,[1]与[2]中都以此问题作为最小树形图问题的实际背景之一。本文将指出,对于由渠道设计问题引出的有向图上求最小树形图问题,可以用一种更简单的、推广起来也可能是更容易的方法来解决。     

中国投递员问题综述

§1 引言 中国投递员问题(Chinese Postman Problem)是1960年我们从生产实际中提出的一个数学问题,它是从下述实际问题中抽象出来的:“一个投递员应该怎样选择一条路线,才能既把所有由他负责送的信都送到,而所走的路程又最短。” 在我们开始研究中国投递员问题以前,国外有人研究过所谓旅行售货员问题     

图上作业法的改进

这篇文章利用表上作业法来说明图上作业法的被检查圈可以大大减少,实际上,图上作业法与表上作业法是等价的,作者所获得的结论也可由图上作业法的性质直接证明.和本文相反,我们也可以一切从图上作业法出发,然后再引出表上作业法的性质来.一般说来,从图形出发证明较简,因为有较多的几何直观性.     

分枝与定界(Branch and Bound)方法简介

1引言不少组合最优化问题可以归结为下面的形式:max f (x)或min f(x),这里s是一个有限集合。让我们看几个例子。[例1]分配问题(Assignment Problem,以下简称为AP)设有n个人A_1,A_2,…,A_n,另外有n件工作B_1,B_2m,…;B_n,又设A_i做工作B_j可以生产的价值为C_(ij),现在要分配每一个人A_i做一件工作B_j,规定每一个人都恰好     

关于一类带风向的投递员问题

E.Minieka在[1]中提出了所谓带风向的投递员问题(Windy Postman Problem),其提法是:设G=[V,E]是一个连通无向图,又设对于E的每一条以s、t为端点的边来说,从s走向t和从t走向s的距离不一定相同,要求在这种情况下,找出G的最短投递路线。当考虑到道路有上下坡以及有顺逆风时,上述模型就更接近于实际情况。上述问题也可以提成下述形式:构造一个有向图G_1=(V,A),这里顶点集合V与G中     

求最小树的破圈法

§1.引言 最小树问题是图论中一个有较广泛实际应用的问题,它的提法如下: 设G-(X,U)是一个有限无向图,这里X表示图G的顶点的集合,U表示G的边的集合.我们设G是连通的,即对于G的任意两个不同的点x_i与x_j,都存在一条由U的边组成的链把x_i与x_j连接起来(关于图论的一些基本概念的较详细的叙述,可以参看[1]).     

关于旅行售货员问题

§1.引言旅行售货员问题(Travelling Salesman Problem,以下简称TSP)是运筹学中一个著名的问题,它的提法是:设有一个售货员从城市1出发,到城市2,3,…,n去推销货物,最后回到城市1.假定任意两个城市i,j之间的距离     

关于中国邮递员问题研究和发展的历史回顾

中国邮递员问题是运筹学研究的基本问题之一. 回顾了中国邮递员问题提出和解决的历史,同时,介绍了对此问题研究的发展概况.