积和式的性质及其在集装箱优化中的一个应用

《积和式的性质及其在集装箱优化中的一个应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文积和式的性质及其在集装箱优化中的一个应用ThePropertiesofPermanentanditsApplicationinContainerOptimization作者姓名：学科、专业：学号：指导教师：完成日期：张伟杰运筹学与控制论21001064张宏伟教授2013年4月26日大连理工大学DalianUniversityofTechnology大连理工大学学位论文独创性声明作者郑重声明：所呈交的学位论文。是本人在导师的指导下进行研究工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外，本论文不包含其他个人或集体已经发表的研究成果，也不包

2、含其他已申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。若有不实之处，本人愿意承担相关法律责任。学位论文题目：积和式的性质及其在集装箱优化中的一个应用作者签名大连理工大学硕士学位论文摘要积和式是定义在矩阵上的一类特殊函数。在数学，特别是线性代数中，积和式是一个与行列式类似的多项式。积和式在概率论、组合数学、分子化学、无线通信、统计物理及计算机科学，特别是图论和计算复杂性理论中有重要的地位，比如一个二分图的，完美匹配的数目可以表示为对应的积和式的值。Valiant于1979年给出了积和式的计算是#-P难问题

3、，由于积和式的计算十分困难，所以它的应用受到了一定的限制。到目前为止，关于积和式的通用精确算法是基于斥容原理的Ryser算法，但该算法只对低阶矩阵有效。对于高阶矩阵，近似算法仍缺乏实用性；若矩阵具有特殊的结构特征，则可以根据其结构特征构造出相应的算法以提高计算效率。本文介绍了积和式的基本性质和常见的精确算法，并研究了使用次序统计量表述集装箱优化过程中遇到的计算问题。堆场空间的分配是集装箱码头优化的一个主要方面，通过对提交箱拖车到港时间的分析，来统筹集装箱在堆场中的堆存，以减少提箱过程中的倒箱率，从而更有效地利用堆场空间。在本文模型中，我们将提交箱拖车到港时间视为不

4、同分布的相互独立的统计量，并针对A箱早于B箱提交的概率展开相关的讨论。本文根据次序统计量与积和式的相关性质，给出了基于预约机制的广义提交箱次序的表达式。由于该表达式的计算涉及到积和式计算，而积和式的计算复杂性使得直接计算该问题无法满足效率要求。因此，本文通过分析该问题中矩阵所具有的分块特征，给出了具有该结构特征的矩阵积和式的计算方法，并分析了该方法的复杂性进而得到了原问题的计算解决方案。关键词：积和式；不同分布：次序统计量：分块矩阵大连理工大学硕士学位论文ThePropertiesofPermanentanditsApplicationinContainerOpt

5、imizationAbstractPermanentiSaspecialfunctionofamatrix．Inmathematics，especiallyinlinearalgebraitisapolynomialsimilartothedeterminant．Itplaysanimportantroleinprobabilitytheory,combina-torialmathematics，molecularchemistry，wirelesscommunication，statisticalphysics，computerscienceespecially

6、ingraphtheoryandcomputationalcomplexitytheory．ItisprovedbyValiantthatthecomputationofpermanentisa#P-hardproblem．Theapplicationofpermanentisrestrict—edbecauseofthecomplexityofitscomputation．ThebestalgorithmforprecisecomputationistheRysermethod，butitisonlyusefullforlow-ordermatrix．Forth

7、ehigh-ordermatrixonewayistochangethealgorithmaccordingtothestructureofthematrix．Thepaperintroducesthepropertiesandseveralexactalgorithmsofpermanentandfocousonthecomputingproblemincontaineroptimizationusingorderstatistics．Theoptimizationofstoragespaceincontainerstorageyardisoneofthemai

8、naspe