带优先级的救援问题及其解法

《带优先级的救援问题及其解法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、扉页：独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人或集体已经发表或撰写过的研究成果，对本文的研究做出贡献的集体和个人均已在论文中作了明确的说明并表示了谢意。研究生签名：论文使用和授权说明本人完全了解云南大学有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交学位论文和论文电子版；允许论文被查阅或借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。(保密的论文在解密后应遵循此规定)研究生签名：导师签名本人及导

2、师同意将学位论文提交至清华大学“中国学术期刊(光盘版)电子杂志社”进行电子和网络出版，并编入CNKI系列数据库，传播本学位论文的全部或部分内容，同意按《中国优秀博硕士学位论文全文数据库出版章程》规定享受相关权益。研究生签名：——导师签名：——日期：摘要当某地发生自然灾害之后，我们就需要根据受灾地的受灾轻重对其进行救援，受灾越重的地方其优先级越高，本文根据受灾地和目标函数的不同，建立了三个数学模型，对这三个数学模型设计了近似算法，并对算法的正确性进行了证明。对模型一设计了一个2一近似算法，并加以改进之后得到了一个；4一近似算法；对模型二设计了一个3

3、一近似算法；对模型三设计了一个2一近似算法，并分别对算法的正确性和近似值予以证明。本文由以下四个章节构成。在第一章中，回顾了问题的由来，给出了到目前为止的一些研究成果；在第二章中，给出本文所涉及的定义，概念和符号；在第三章中，给出解决装箱问题和最小时间跨度排序问题的算法和相关定理；在第四章中，讨论带优先级的救援问题的三个数学模型，并给出相应算法，对算法的正确性及近似值进行证明；最后，本文给出相关结论以及未来的研究方向。关键词：优先级；最小时间跨度排序；装箱；近似算法AbstractWhennaturaldisastershitsomeplace，

4、Weneedtorescuethisaffecteddisasteraccordingtotheseverityoftheaffecteddisaster，Theheavieraffecteddisasterhasthehigherpriority，ThisthesisaccordingtothedifferentoftheaffecteddisasterandthedifferentobjectivefunctionestablishsthreemathematicalmodelsandWedesginopproximationalgorith

5、mtowardstothesethreemathmaticalmodels，Andprovedthecorrectnessofthealgorithm；Wedesigna2-approximationalgorithmforthemodelI，andmakeaimprovement，Wedesigna；-approximatealgorithm，anddesigna3-approximatealgorithmforthemodelII，anddesigna2-approximatealgorithmforthemodelIII，andprovei

6、tscorrectnessofthealgorithmandthedegreeofapproximation．Thisthesisconsistsofthefollowingfourchapters．InChapterone，wewillreviewtheoriginoftheproblemandcomeupwithsomeresearchresultsSOfar；InChaptertwo，wewillgivesomedefinitions，conceptionsandsymbolsinvolvedinthisarticle；InChaptert

7、hree，wewillgivethealgorithmsandtheoremofthebin—packingproblemandtheminimizingmakespanscheduling；InChapterfour，wewilldiscusstherescueproblemswithprioritiesandpresenttheapproximationalgorithm；Finally,thispaperpresentstheconclusionsandfutureresearchdirections．Keywords：Priority；T

8、heminimizingmakespanscheduling；Binpacking；Approximationalgorithm1lAb