平面上的點(diǎn)-線選址問(wèn)題.pdf

1、鄭州大學(xué)碩士學(xué)位論文平面上的點(diǎn)線選址問(wèn)題姓名：尚松蒲申請(qǐng)學(xué)位級(jí)別：碩士專(zhuān)業(yè)：運(yùn)籌學(xué)與控制論指導(dǎo)教師：林詒勛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