动态规划的表格结构(Ⅰ)

在这系列性文章中,提出了一个统一表格,用以解算动态规划中许多数值问题。本文讨论阶段数确定、有限的情形。     

动态规划的表格结构(Ⅱ)——关于网络中第一类最短路问题

本文讨论阶段数不确定、有限的情形。首先提出了三个有关代数结构的算法定理,使熟知的 Ford 算法,Gauss-Seidel 算法,Yen 第一、第二算法都是它们的特例。由于我们提出了 Yen 第三、第四算法,使得无回路网络中的问题,以及正网络中的 Dijkstra 算法的论证联成一线。而且,它们都可在前文(Ⅰ)所提出的表格上作数值计算。     

关于初等概率计算的一点注记

初等概率理论与计算问题是成熟的内容。许多书藉介绍这部份时,几乎都是沿习常规,变化不大。本文建议在讨论它们时,一方面,系统地运用多阶段有向图作为分析问题的辅助工具;另一方面,引进矩阵作为计算的手段。这样做,将是有益的:一些基本定理得到直观的解释和推广,而在解算一些计算题时,头绪要清晰得多。这样的想法,在一些书中,可以零星见到,但很少系统运用。自Romanovsky开始,用矩阵描述有限MarkoV链取得了很好的效果。如果在初等概率中也使用短阵这一工具(再加上有向图),这还将取得前后一致的效果。     

h阶关键路算法

ｈ阶关键路算法秦裕瑗（武汉钢铁学院４３００８１）ＡｎＡｌｇｏｒｉｔｈｍｆｏｒＦｉｎｄｉｎｇＣｒｉｔｉｃａｌＰａｔｈｏｆｔｈｅｋ－ｔｈＯｒｄｅｒＱｉｎＹｕｙｕａｎ（ＷｕｈａｎＩｒｏｎａｎｄＳｔｅｅｌＵｎｉｖｅｒｓｉｔｙ４３００８１）ＡｂｓｔｒａｃｔＢａ...     

组合优化（Ⅱ）——对称差分解法的又一应用

本文先讨论函数的增量与微分对于连续型最优化问题的作用，析出有益的启发。用之于组合优化，得到了求解问题的一个方法——对称差（的）分解法。文献［２］对它作了讨论并得到不少应用。本文提出两个赋权凸锥独立集合问题。它们是典型的组合优化问题，分别与线性规划中两个互为对偶模型等价；用对称差分解法进行求解，得到的算法就是线性规划中的改进单纯形算法     

发现产品结构优化问题的一般过程

本文通过一个实例，即对心血管疾病高发人群的食用油的合理配比问题，来讨论发现产品结构优化问题的社会背景、科学技术的必要基础以及正确对待通过线性规划求得的答案。这些问题对各级管理者和工程技术人员来说是异常重要的。本文所得的几个配比方案可以供人们参考     

一个排序問題

本文讨论n个另件在m台机床上加工的排序问题。以T.C.Hu引入的(H)矩阵为工具,讨论了Nabeshima充分条件与Johnson—越—韩充分条件之间的关系。在引入PX条作之后,得到了另一个充分条件(定理6)。它在验算的手续上比Johnson—越—韩的要简单些,但在要求的前提上,比后者略微强一些。     

对动态规划的再认识

本文分两部分:第一部分,回顾规划论简史之后,讨论动态规划的最优性原理与递推公式。认为原理本身存在多方面不严密之处,并举出了反例;还证明了(定理1)当第一、第二两类最优策略集合相等时,原理与公式等价。第二部分,作者抛开上述原理与公式,另行建立嘉量原理以及与之等价的求解代数公式。它们不仅可以用来求解常义的最优策略,而且可以用来求解N阶最优策略,多目标非劣解以及其他问题,而这些是最优性原理不能概括、递推公式解决不了的。从代数的观点,作者讨论了摹方阵乘幂问题,得到了定理3。它说明可以代数地构造任意多个有效的算法求解网络上两类最优路问题;还讨论了摹多项式及其应用。本文目的是概述作者对动态规划的某些基本看法以及作者长期从事研究上述问题的基本思路与主要结果。     

摹矩阵与线路寻优问题

在有向图中,找出两个顶点间最长线路和最短线路的问题,叫做最优线路问题;找出仅短于最长线路的线路(即次长线路)和仅长于最短线路的线路(即亚短线路)的问题,叫做次优线路问题。这些合称为线路寻优问题。三十年来的发展,这方面已经取得种种成果,例如,有E.W.Dijkstra最短线路的算法,对于多阶段有向图,问题简单得多,通常的算法也不难,关于次优线路,象W.Hoffman与A.Pavley及S.E.Dreyfus都提出过     

论组合优化（Ⅰ）──一个公理系统

组合优化是一门讨论某些离散型最优化问题的学问．但是众多问题之间，迄今所得结果和方法尚未“组合”起来，显得过分“离散”了一些．近几年，作者把组合最优化作了一定的推广，称为组合优化。致力于；它的定义的形式化；经验命题“整体的最优解在局部也最优“的形式化；以及导数定义的模拟。本系列文章将对它们作进一步的整理、发展，努力完善这一公理框架，以寻求其有效范围的边界，探讨它们所能起的作用。本文用一个公理系统（定义４）定义第一类优化问题；讨论它的一些基本性质和优化原理；还引进了解带概念，讨论在解带中的某些几何性质。