论文部分内容阅读
积和式是定义在矩阵上的一类特殊函数。在数学,特别是线性代数中,积和式是一个与行列式类似的多项式。积和式在概率论、组合数学、分子化学、无线通信、统计物理及计算机科学,特别是图论和计算复杂性理论中有重要的地位,比如一个二分图的完美匹配的数目可以表示为对应的积和式的值。Valiant于1979年给出了积和式的计算是#-P难问题,由于积和式的计算十分困难,所以它的应用受到了一定的限制。到目前为止,关于积和式的通用精确算法是基于斥容原理的Ryser算法,但该算法只对低阶矩阵有效。对于高阶矩阵,近似算法仍缺乏实用性;若矩阵具有特殊的结构特征,则可以根据其结构特征构造出相应的算法以提高计算效率。 本文介绍了积和式的基本性质和常见的精确算法,并研究了使用次序统计量表述集装箱优化过程中遇到的计算问题。堆场空间的分配是集装箱码头优化的一个主要方面,通过对提交箱拖车到港时间的分析,来统筹集装箱在堆场中的堆存,以减少提箱过程中的倒箱率,从而更有效地利用堆场空间。在本文模型中,我们将提交箱拖车到港时间视为不同分布的相互独立的统计量,并针对A箱早于B箱提交的概率展开相关的讨论。本文根据次序统计量与积和式的相关性质,给出了基于预约机制的广义提交箱次序的表达式。由于该表达式的计算涉及到积和式计算,而积和式的计算复杂性使得直接计算该问题无法满足效率要求。因此,本文通过分析该问题中矩阵所具有的分块特征,给出了具有该结构特征的矩阵积和式的计算方法,并分析了该方法的复杂性进而得到了原问题的计算解决方案。