2017年深圳杯建模挑战赛C题决赛论文（独家）
本人2017年入选了深圳杯建模决赛，这是正式答辩时的论文。仅供各位建模的同学学习参考。基于问趣二中的预测结果,计算得出未来十年的总成本数量及各模式下各分项成本(涵盖直接业务成本、经济技术成本、问接的当下和远期社会成本)比例,分析其变化趋势,并通过作图直观反映。考虑到目前深圳已经开始建立生活垃吸强制分类制度,本文详细分析了家庭分类与专业分类两种前端分流模式对总成本的影响。问题三的分析基于较为完善的模型,对远期效益成木比进行估算,从深圳市具休情况岀发,设计一套生活垃圾处理的优选模式,以供参考。符号说明变量含义生活垃圾处理社会总成本直接成本直接业务成本收集成本第种收集方式的成本第种收集方式中的第种成本运输成木第种运输方式的成本第种运输方式中的第种成本处理成本第种处理方式成本绎济技术成本固定成本第种固定成本可变成本第种可变成本税收减免第种税收减免间接的当下和远期社会成本,即环境损失成本第种环境损失成本年度垃圾处理量湿垃圾占垃圾总量的比例垃圾分类中的干垃圾总量垃圾分类中的湿垃圾总量模型假设假设在估算时间内国家及深圳市相关政策不变。假设在估算时间内折现※为假设在佔算时间内政府对源头分类的补贴保持不变倀设在估算时间内填埋、焚烧、生物处理三种方式下的基准地价的季度增长率分别为模型建立与求解问题一的模型建立模型的准备针对问题一,将生活垃圾处理的社会总成本分为直接业务成本、经济技术成本、问接的当下和远期社会成本,如图生活垃圾处理社会总成本直接业务成本D经济技术成本E间接的当下和远期社会成本图生活垃圾处理社会总成本构成直接业务成本分析在直接业务成木中,我们又将其细化分成了垃圾收集成木、运输成木和处理成本三个部分,如图直接业务成本D收集成本D处理成本D匚运输成本D图直接业务成本构成4()收集成本分析由附件一可知,在不同的垃圾处理模式中,收集方式分别对应混合收集、源头分类收集和混合收集末端分类。即收集成本可划分为混合收集成本源头分类收集成本及混合收集木端分类成本而且每一种收集方式的成本又涵盖了公用垃圾桶成本(分别对应)和运输成本(分别对应),值得注意的是,源头分类收集方式会有额外的政府补贴,而混合收集末端分类方式在末端分类时会占用额外的土地、人力、设备等,因此会产生额外的成本和,如图收集成本De混合收集源头分类成本收集成本集,末端分类成本D公用福政府Dcg成本图收集成本构成()运输成本分析运输成本分为混合运输成本和分类运输成本两类,其中每一种运输成本都包括转运站成本(表示从各公用桶运输到转运站进行进一步处理所需成本,分别对应)和运输成本(分别对应),如图:运输成本Dt混合分类运输运输成本成本转运站成运输站成运输本成本DtD图运输成本构成5()处理成本分析由于处理模式的不同,处理成本可分为焚烧处理成本、填埋处理成本以及生物处理成本,如图处理成本D。焚烧填埋生物处理处理处理成本成本成本DstD图处理成本构成经济技术成本分析经济技术成本包括固定成本、可变成本和税收减免。固定成本分为土地成本和建设成本可变成本包括飞灰补贴、底灰补贴电价补贴、渗沥液补贴以及其他补贴;税收减笕分为増值税减笕、营业税减免和企业所得税减免,如图:经济技术成本E税收减免可变成本定成本E稅减税减税减其他补赎二c5EC2填埋场生物处理厂图经济技术成本构成间接的当下和远期社会成本分析问接的当下和远期成本涵盖了由于环保标准提高所花费的成本、水污染造成的损失、大气污染造成的损失以及固体废弁物污染造成的损失如图6问接的当下和远期社会成本L水污染损失气污染固体废物污染损失L4业损幻1匚人体健康损失[林损头「其他损类图间接的当下和远期社会成本构成模型的建立考虑到不同情况下,决策者会选择不同的模式组合方式。因此,在计算社会总成本时,本文选用各个模式下不同环节所需成本的叠加,从而求得深圳市生活垃圾处理的社会总成木。直接业务成本的计算直接业务成本包括收集成本、运输成本、处理成本直接业务成本的计算公式为:()收集成本的计算公式为=∑∑++代表混合收集成本,代表源头分类收集成本,代表源头混合收集,末端分类成木;代表第种收集方式的公用桶成木,代表第种收集方式的运输成本,代表单位垃圾消耗的公用桶成本,代表生活垃圾年产量,此成本仅包括垃圾桶至小型转运站的成本,如果决策者选择源头混合收集,末端分类方式收集垃圾,则应该加上额外的土地、设各、人工等成本(后面统称为额外成本),如果选择源头分类,则应加上政府补贴;代表单位吨数单位公里运输价格(是一个与距离有关的分段函数),代表距离;代表单位湿垃圾政府补贴成木;代表单位土地、设备、人工等的成木代表湿垃圾占总垃圾量的比重。()运输成本包括混合运输成本、分类运输成本运输成本的计算公式为7代表第种运输方式的转运站成本,包括转运站人工费,以及设备维护费等,代表第科运输方式的运输成本,此成本仅包括小型转运站至末端垃圾处理站的成本,代表单位转运站成本。()处理成本包括焚烧成本、填埋成本和生物处理成本处理成木的计算公式为代表单位垃圾焚烧处理成本;代表单位垃圾填埋处理成木;代表单位垃圾生物处理成本。经济技术成本的计算经济技术成本包括固定成本、可变成本、税收减免经济技术成木的计算公式为固定成本包括焚烧垃圾的十地成本、填埋的十地成本、建设成木。固定成木的计算公式为:代表当年地价,代表十地面积,代表折现率,代表工业用地年;十地机会成本为;代表年地价,代表季度地价增长率,代表时间:代表填哩高度;ρ代表填埋密度代表十地机会成本;代表建设补贴。可变成本包括飞灰补贴、底灰补贴、电价补贴渗沥液补可变成本的计算公式为8=代表单位底灰处理补贴,代表底灰量,代表单位飞灰处理补贴,代表K灰量;代表上网电价补贴,代表超额供电补贴;代表单位污水处理补贴,代表污水处理量税收减免包括增值税减免、营业税减免企业所得税减免税收减免的计算公式为:间接的当下和远期社会成本的计算间接的当下和远期社会成本包括环保标准提高后所需成本(远期环境标准提髙后垃圾处理费升高所需成本)、水污染导致的健康损失、空气污染健康损失、固体废弃物污染损失。水污染导致的健康损失包括早逝引起的健康损失、疾病治疗费用和误工损失;由于垃圾厂排放的气休中对人体造成巨大损失的气体为二嵁英,故将空气污染健康损失考虑为二嗯英造成的健康损失;在计算固休废弃物污染时,采用市场价值法对生活垃圾固休废弃物造成的人工管理费、设备费和运输费等费用进行计算不管对生活垃圾使用哪种处理方式,在计算生活垃圾堆存造成的经济损失时,以需按填埋量来进行计算间接的当下和远期社会成本为:∑∑总数总数指标评价和危险特征阐述,结合国际组织的研究成果,对水污染健康损伤的不良影响进行定量评{,代表年人均收入,代表就诊人数,代表人均治疗费用,代表日均收入,代表住院病例,代表每患病者入住天数;代表不同浓度区域的编码,代表不同浓度区域的二惡英致癌风险代表每平方公里人口密度,代表不同浓度区域所占的面积,代表个体生命价值代表治疗费用;代表生活垃圾堆存损失系数,代表生活垃圾堆存量。综上,由上述各式可得生活垃圾的社会总成本为:+十问题二模型建立及解决各模式的直接成本估算方案完善深圳市生活垃圾直接成木包括直接业务成木和经济技术成木,由式()至式()可知,城市生活垃圾直接成本为:当期社会总成本估算由已知数据代入问题一模型中可知年的社会总成本为:+十元日前仅得到年深圳市生活垃圾年产量数据,如图:s0047544069406图年深圳市生活垃圾年产量无法直接计算出当期以及未来十年各模式下直接成本,故基于灰色预测方法,根捃此数据,估算得出年的生活垃圾年产量如表
- 2020-12-05下载
- 积分：1
浙江大学计算理论复习总结
计算理论复习总结,但是考试快要结束了，估计大家也没有什么需要了。28.文法是CFG的推广,任何CFG都是文法。G=(V,∑,R,S)29.语言被文法生成ⅲ它是re的。30.所有数值函数都是原始递归的31.原始递归函数集是递归可枚举的。32.特殊语言/问题H={"M"w":M在w上停机}lH={"M"w":M是一台在"w"上不停机的TM}H1={"M":M在“M”上停机}H1={w:要么w不是一台TM的编码,要么w是M的编码,M是一台在"M"上不停机的TM}H:re.;H1:re.;-H,-H1:非r.e.;2-SAT∈P;SAT∈NPThe world as We Dont Know itreAsumming P≠APCo『eHrecursiveSATSATCO-A伊II Asumming P=Npr, eCo-r.erecursiveNP= cO-Np= p33没有算法的问题称作不可判定的or不可解的,如TM的停机问题34.证明不可判定通用图灵机U通过递归函数归约到L如果L是递归的则U是递归的ic若L1非递归,并存在L1到L2的归约,则L2也非递归。递归函数是 Turing Computable的35.语言是图灵可枚举的,证存在枚举它的图灵机。(M通过空格代开始,周期性的经过特殊状态q来枚举L,任意顺序且可重复)6.不可判定语言与递归语言互为补集,与rc语言有交集。37语言是re.,if它是图灵可枚举的;语言是递归的,i它是以字典序 turing可枚举的。8.P在并交连接和补运算下封闭NP在并、连接运算下封闭。若NP在补下封闭则NP=P39.H={M"wM在最多2w步后停机}唾P40.所有正则语言和所有CFL都属于P41.NPA.机器角度去定义:被多项式界限非确定型图灵机判定的所有语言的类。B.基于 verifier的定义:NP问题上建立的非确定机包含两步1)非确定地猜一个解2〕用一个确定的算法判定该解是否为可行解判定一个给定猜测值是否满足该问题(可满足性)的算法称作 verifier,一个问题称作NP问题当且仅当存在一个多项式时间的 verifier这两个定义是不矛盾的,因为如果一台非确定TM在多项式时间内可以判定一个非确定选择的翰入是否满足,就是基于 verifier的定义。P和NP的区别a problem is in P if we can decide them in polynomial time. It is in NP if we candecide them in polynomial time, if we are given the right certificate42.若存在计算函数f的多项式界限的图灵机M,则f称为多项式时间可计算的43.若τ1是L1->l2的多项式归约,τ2是L2->I3的多项式归约,则τ1τ2是L1->l3的多项式归约44.证明NP完全法一、按定义:LΣ*,若(a)L∈NP,且(b)对每个语言L∈NP,存在从L到L的多项式归约则L称为NP完全的。法二、归约,对于语言L,(a)若L∈NP(b)一个NP完全问题可以在多项式时间规约到L,ie. SAT 0 is context-free but not regular49.L=L1L2,L是CFL,则L1一定是CFL(x50. Regular-CFL不一定是CFL,如a*b*c*-anbn包含 anben51. 2-way PDalie PDa whose input heads can move both left and right] are more powerfulthan 1-way pda52. Given a PDa M1 and an fa M2, the problem l(M1)cl(M2)is decidable53.DFA/NFA识别的是 exactly正则语言54.Re.只在补和差下不封闭,CFL在交下也不封闭55.非正则语言的可能是正则语言。比如A:[W=w}及所有回文,A=*,为正则语言56.典型非正则:w=wR57.正则语言的子集可能非正则,如 anben是a*b*c*的子集;又如Σ*是正则语言,H≌Σ*58.归约:X到Y的归约可以理解为X到Y问题的映射, reduction可以解释为 at least asdifficult as….比如ⅹ可以被Y的算法解决,则 X is no more difficult than yⅩ可以约到Y,记X≤Y。e.gx2可以归约到任意两数的乘积。若有A≤B,A是不可判定问题>B不可判定A不递归->B不递归B可判定>A可判定B是递归的->A是递归的59.若X多项式时间归约到Y,Y多项式时间可解,则X多项式时间可解若X多项式时间归约到Y,Ⅹ多项式时间不可解,则Y多项式时间不可解60.X多项式时间归约到Y,Y多项式时间归约到Z,则X多项式时间归约到Z61.PRME( COMPOSITE)多项式时间归约到 Factor,但是 Factor多项式时间不能归约到PRIME COMPOSITE )o62.若A≤PB,B∈NP,则A∈NP。证明A≤PB→存在确定图灵机X,可将A归约到B。B∈NP→存在一个非确定图灵机N可判定B。我们希望构造一个新的TM(ⅹN)是的ⅹ*N非确定多项式时间求解A,则A∈NPRunning time of X*N≤1+p(mB>+qp(m)(B多项式时间非确定判定是多项式时间所以A∈NP63若AsPB,B∈P,则A∈P64.若X是NPC的,则X在多项式时间内可解ifP=NP65.SAT多项式时间归约到3SA(3AT是NPC的)66.证明语言L是R/Re, Non rea) Intuitively想想有没有半判定(判定)的TM,有则Rc、(R)。若非R执行下一步。b)用能否由Re.( Non re.)语言归约到该语言,能则Re而非R( Non re)严格用归约函数定义f:A≤B,r1∈A当且仅当r1∈Beg1∈H,M∈L证明Recg2∈非H,iM∈L证明 Non rc注意方向:是从A的实例经过递归函数推向B的实例。详细介绍http://www.cs.rice.edu/nakhleh/comp481/finalreviewsp06sol.pdf67.递归与μ递归等价68.PDA中,若每一个格局至多有一个格局接在它后面,则为确定型的。确定型CF在补下封闭69.M半判定L:w∈L,ifM在w上停机,注意半判定图灵机中不存在“拒绝”状态。只要不接受w,就不停机。70. Chomsky hierarchyElements of the Chomsky HierarchyRecursively enumerable languagesRecursive languageContext sensitive languagesContext ee languageseterministccontext free languagesRegularanguages71.俩证明7.6证明P在并、交、 Kleene*连接和补运算下封闭(1)并:对任意L,LEP,遴n时间图灵机M1和nb时间图灵机M2判定它们且c=max{ab}对L1L2构造判定器MM=“对于输入字符串w1)在W上运行M1,在w上运行M22)若有一个接受则接受,否则拒绝。时间复杂度:设M1为0(n)M2为0(m)。令c=max{ab}第一步用时0(n+n),因此总时间为Oma+n)=0(n9所以L1L2属于P类,即P在并的运算下封闭。(2)连接对任意L1,L2属于P类,设有n时间图灵机M1和m时间图灵机M2判定它们,且c=max{ab}。对L1l2构造判定器MM=“对于输入字符串w=w2灬,Wn对k=0,1,21…,n重复下列步骤。在wW2…wk上运行M1,在wk1wk+2…n上运行M若都接受,则接受。否则继续。若对所有分法都不接受则拒绝。时间复杂度:(n+1x0(n+0m-0(m+4)+0(nb+4=0(nc+),F以L1oL2属于P类,即P在连接的运算下封闭。对任意L属于P类,设有时间0(n)判定器M判定它,对构造判定器MM=“对于输入字符串〔1)在w上运行M12)若M1接受则拒绝,若M1拒绝则接受。时间复杂度为:0(m)。所以属于P类,即P在补的运算下封闭。77证明NP在并和连接运算下封闭。1)并对任意L1,L2∈NP,设分别有n时间非确定图灵机M1和n时间非确定图灵机M2判定它们,且c=max{a,b}。构造判定LL2的非确定图灵机M:M=“对于输入字符串w1)在W上运行M1,在w上运行M2。2)若有一个接受则接受,否则拒绝。对于每一个非确定计算分支,第一步用时为O(n-)+O(n),因此总时间为On+n)=0(n。所以LLz∈NP,即NP在并的运算下封闭2)连接对任意L,L2∈NP设分别有na时间非确定图灵机M1和m时间非确定图灵机M2判定它们,且c=max{ab}。构造判定L1oL2的非确定图灵机M:M=“对于输入字符串w:1〕非确定地将分成两段xy,使得w=xy。2)在x上运行M1,在y上运行M23)若都接受则接受,否则拒绝。对于每一个非确定计算分支,第一步用时O(n,第二步用时为0(n)+0(m),因此总时间为o(n+m)=0(n。所以L1oL2∈NP,即NP在连接运算下封闭。专题一一图灵机可判定性问题判定以下问题是否可判定:声明:思路—想证明B问题不可解,1.从一个不可解问题A入手(如停机问题)2.创建B的—个实例,从中推出如果能解决B,A也就可以解决了3.所以B是不可解的1.一个图灵机有至少481个状态。我们可以给出这样一个TMN进行cnc(M)a)数M中状态数,直到481b)如果达到了481,N就接受,否则拒绝2.给定图灵机在空串上走了481步还没停机。构造2带图灵机N,a)2a带:写481个0b)1s带在空串上模拟M,每走一步,第2带就删掉一个0c)如果M在所有0都删掉之后停机,则N接受,否则不接受给定图灵机,判定它是否在一些输入上经过481步还没停机?a)按字典序找出所有 length
- 2020-12-01下载
- 积分：1
|
联系客服（QQ：3324461878）
