平面上的點-線選址問題.pdf

1、鄭州大學碩士學位論文平面上的點線選址問題姓名：尚松蒲申請學位級別：碩士專業(yè)：運籌學與控制論指導教師：林詒勛2003.4.5AbstractLocationproblemsareproblemswithregardtoselectingoptimalsiteswherefacilitiesshouldbelocatedLocationproblemsareoptimalproblemscombinedwithrealityandbefol

2、lowedwithinterestbyoperationresearchers，managers，economists，strategists，urbanplanersandengineerssince1960s’TheresearchonlocationproblemsdevelopsrapidlytheseyearsThetraditionallocationproblemsstudylocationproblemswithdist

3、ancefrompointtopointWeconsiderlocationproblemswithdistancefrompointtolineWemainlydiscussfourpoint—linelocationproblemsintheplane∞foUows：ProblemAistodetermineastraight—linetominimizethetotalweighteddistancesfromngivenpoin

4、ts；ProblemBistodetemlineapointtominimizethetotalweighteddistancesfromngivenstraight—lines；ProblemCistodetermineastraight—linetominimizethemaximumweighteddistancesfromngivenpoints；ProblemDistodetermineapointtominimizethem

5、aximunlweighteddistancesfromngivenstraight—linesProblemAandproblemBamdualTheyhaveadualpropertythatanoptimalsolutionofproblemAcouldbeastraight—lineconnectingtwogivenpointsandanoptimalsolutionofproblemBcouldbeapointofinter

6、sectionoftwogivenstraight—linesProblemCandproblemDarealsodualTheyhaveadualpropertythatthere啪atleastthree“criticalpoints”correspondingtoanoptimalstraight—lineinproblemCandthere啪atleastthree“criticalstraight—lines”corrB—sp

7、ondingtoalloptimalpointinproblemDFromtheseproperties，thesefournon—linearprob—lemscouldbetmnsfornmdintocombinatorialproblemsandcouldbesolvedbyalgorithmswithpolynomial—timeimrafionsWealsoconsidertwoobnoxiouscenterproblemsa