邊覆蓋對策的均衡性及其算法.pdf

1、中國海洋大學碩士學位論文邊覆蓋對策的均衡性及其算法姓名：姚春玲申請學位級別：碩士專業(yè)：運籌學與控制論指導教師：方奇志20080601BalancednessIssuesandalgorithmsOnEdgeCoveringGamesAbstractCombinatorialcooperativegame，alsonamedascombinatorialoptimizationgame，isproposedtomodeltheprofit

2、orcostallocationproblemwhicharisesfromsomecombinatorialoptimizationproblemsCooperativegametheoryconsidershowtodistributethetotalincome(orcost)generatedbyagrouptoitsmembersfairlyandrationallyThecoreisoneofthemostimportant

3、solutionconcepts，whichisdefinedonthebasisofsubgrouprationalityThegameiscalledbalancedffitscoreisnonemptyInthisthesis，wefocusOilsomecooperativegamemodelsarisingfromedgecoveringproblemsongraphsWeconsiderthebalancednessofth

4、egames，anddiscussthealgorithmicissuesontheircoresThemainresultsareasfollows：(1)Tworelatedcooperativegamesarisingfromintegeredgecovetingproblemsongraphs，relaxedandrigid七)一edgecoveringgames，areintroduced；basedonanewprogram

5、formulationforintegeredgecoveringproblemanddualitytheory，acommonnecessaryandsufficientconditionforthebalancednessofbothgamesisobtained；moreover，algorithmicissuesoncoresBrediscussed(2)Twelatedcooperativegamesarisingfromfr

6、actionaledgecovetingproblemsongraphs，relaxedandrigidfractionaledgecoveringgames，arealsointroducedWithdualitytheoryoflinearprogramming，weprovethatbothgamesarebalanced，andgivetherelationshipbetweentheircoresKeywords：edgeco