资源描述：
《Analysis of algorithms》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、CS445Analysisofalgorithms2LinearprogrammingEricSchost´eschost@uwo.ca1Top10algorithmsAccordingtoSIAM(societyforindustrialandappliedmath)•...•Simplexalgorithmforlinearprogramming•FastFourierTransform•Quicksort•...Ifonewouldtakestatisticsaboutwhichmathematicalproblemisusingupmostofthecomputertimeinthew
2、orld,then...theanswerwouldprobablybelinearprogramming.2SetupLinearprogrammingdealswithsatisfiabilityandoptimizationproblemsforlinearconstraints.•Alinearconstraintisarelationoftheforma1x1+···+anxn=b,ora1x1+···+anxn≤bora1x1+···+anxn≥b,wheretheaiandbareconstantsandthexiaretheunknowns.•satisfiability:give
3、nseverallinearconstraints,isthereavalue(x1,...,xn)thatsatisfiesthemall?•optimization:givenseverallinearconstraints,assumingthereisavalue(x1,...,xn)thatsatisfiesthemall,findonewhichmaximizesc1x1+···+cnxn.3AbabyexampleYouareallowedtoshareyourtimebetweentwocompanies.•companyC1pays1dollarperhour;•companyC2
4、pays10dollarsperhour.Knowingthatyoucanonlyworkupto8hoursperday,whatscheduleshouldyougofor?Ofcourse,workfull-timeatcompanyC2.•Linearformulation:x1isthetimespentatC1andx2thetimespentatC2.•Constraints:x1≥0,x2≥0,x1+x2≤8.•Objectivefunction:maximizex1+10x2.•Solution:x1=0,x2=8.4Moreexamples5AdietproblemNut
5、ritionfactscarbsproteinfatironpricesliceofbread3051.51030cupofyogurt1092.5080tspofbutter6818620minimum3005070100Goal:Minimize30x1+80x2+20x3.Constraints:30x1+10x2+6x3≥3005x1+9x2+8x3≥501.5x1+2.5x2+18x3≥7010x1+6x3≥1006MaximalflowInput:•agraphG,•acapacityfunctioncontheedges,•asourcesandasinkt,findamaximal
6、flowfromstot.Solution:•Createavariablefu,vforeachedge(u,v)andthelinearconstraintsXXfu,v≥0,fu,v≤c(u,v),fu,v=fv,w(u,v)edge(v,w)edge•MaximizeXfs,v.(s,v)edge7ShortestpathInput:•agraphG,•alengthfunction`ontheedges,•asourcesandatargett,findashortestpathfromstot.Solution:•Createavariabledvforeachvertexvandth
7、elinearconstraintsds=0anddv≤du+`(u,v),whenever(u,v)isanedge.•Minimizedt.8MinimumcostflowInput:•agraphG,•acapacityfunctioncontheedges,•acostfunctionaontheedges,•asourcesandasinkt.PThecostofaflowisa(e)f(e
