《运筹学导论》第四版-胡运权-第1章-Introduction

1OperationsResearch_1ChonghuiGuoSchoolofManagementScienceandEngineeringRoom315,Tel.84708007password:2008orms

2ReferenceBooksIntroductiontoOperationsResearch(8thEdition)FrederickS.HillierandGeraldJ.Lieberman〔Passedawayin1999〕3

Nothingspecialbutthefollowingsareexpected:Prerequisiteforthecourse

experienceofcomputeruse

**

basisofmathematics***

programmingskills

*4Grading

FinalExam(80%)PresenceandProblemSets(20%)5

TheOriginsofOperationsResearchTheNatureofOperationsResearchTheImpactofOperationsResearch

1Introduction6Oneproblemsisatendencyforthemanycomponentsofanorganizationtogrowintorelativelyautonomousempireswiththeirowngoalsandvaluesystems,therebylosingsightofhowtheiractivitiesandobjectivesmeshwiththoseoftheoverallorganization.Arelatedproblemisthatasthecomplexityandspecializationincrease,itbecomesmoreandmoredifficulttoallocatetheavailableresourcestothevariousactivitiesinawaythatismosteffectivefortheorganizationasawhole.1.1

TheOriginsofOperationsResearch1Introduction7TherootofORcanbetracedbackmanydecades,whenearlyattemptsweremadetouseascientificapproachinthemanagementoforganizations.Thebeginningoftheactivitycalledoperationsresearchhas,however,generallybeenattributedtothemilitaryservicesearlyinWorldWarⅡ.Bytheearly1950s,agrowingnumberofpeoplehadintroducedtheuseofORtoavarietyoforganizationsinbusiness,industry,andgovernment.TherapidspreadofORsoonfollowed.1.1

TheOriginsofOperationsResearch8

TwofactorsthatplayedakeyroleintherapidgrowthofOROnewasthesubstantialprogressthatwasmadeearlyinimprovingthetechniquestoOR.Aprimeexampleisthesimplexmethodforsolvinglinearprogrammingproblems,developedbyGeorgeDantzigin1947.ManyofthestandardtoolsofOR,suchaslinearprogramming,dynamicprogramming,queuingtheory,andinventorytheory,wererelativelywelldevelopedbeforetheendofthe1950s.Asecondfactorthatgavegreatimpetustothegrowthofthefieldwastheonslaughtofthecomputerrevolution.1.1

TheOriginsofOperationsResearch9Top10Algorithmof20thcentury1946:JohnvonNeumann,StanUlam,andNickMetropolis,allattheLosAlamosScientificLaboratory,cookuptheMetropolisalgorithm,alsoknownastheMonteCarlomethod.Throughtheuseofrandomprocesses,thisalgorithmoffersanefficientwaytostumbletowardanswerstoproblemsthataretoocomplicatedtosolveexactly.

1947:GeorgeDantzig,attheRANDCorporation,createsthesimplexmethodforlinearprogramming.Anelegantsolutiontoacommonprobleminplanninganddecision-making.

ForDetailsSeeSIAMNews,Volume33,Number4,BarryA.Cipra,"TheBestofthe20thCentury:EditorsNameTop10Algorithms"

1.1

TheOriginsofOperationsResearch10China:AncientcountrymakesORhistory

Xiang-sunZhangandKanCheng,China:AncientcountrymakesORhistory,OR/MSToday,October,pp32-35,1998.

Chinaisintheprocessoftransferringfromaplannedeconomytoamarket-drivenone,creatingopportunitiesandchallengesforthemassivenation'sactiveoperationsresearchcommunity.

1.1

TheOriginsofOperationsResearch11ThefirstORgroupinChinaModernoperationsresearchactivitiesinChinawereinitiatedinthelate1950s.ThefirstORgroupwasfoundedattheInstituteofMechanics,ChineseAcademyofSciences(CAS),in1956,promotedbyprofessorsH.S.TsienandK.C.Hsu.Tsienreceivedhismaster'sdegreefromMITandhisPh.D.fromtheCaliforniaInstituteofTechnology,andwentontobecomeCalTech'sfirstGoddardProfessor.HsuearnedhisPh.D.attheUniversityofKansas,andwasaresearchassociateintheInstituteofFluidMechanicsandAppliedMathematicsattheUniversityofMaryland.TsienandHsureturnedtoChinain1955.1.1

TheOriginsofOperationsResearch12ThesecondORdivisioninChinaIn1959,asecondORdivisionwassetupattheInstituteofMathematics,CAS.Thesetwodivisionsmergedintoonedivisionin1960asapartoftheInstituteofMathematics.In1963,thedivisionorganizedaseriesofspecializedcoursesinORattheChineseUniversityofScienceandTechnology,markingthefirsttimeinChinathatauniversityofferedasystematiceducationinOR.1.1

TheOriginsofOperationsResearch13EarlyORapplicationactivitiesEarlyORapplicationactivities(late1950s)inChinafocusedontransportationproblems.Onesuchexamplewastheallocationdesignofthreshinggroundstosavetimeandmanpower.TheclassicChinesePostmanProblemmodelwaspresentedbyProfessorM.G.Guaninthesameperiod.Postmendeliverlettersdownroads.TheChinesePostmanProblemistofindtheshortestrouteinanetworkthatuseseveryarc(directededge)andgetsbacktowheretheystarted(closedproblem)ordoesn'tgoback(openproblem).

1.1

TheOriginsofOperationsResearch14L.G.HuaandOROneoftheearlyhighlightsofORapplicationactivitiesinChinawasconductedbytheChinesemathematicianL.G.Hua—amemberofCASandpresidentoftheChineseSocietyofMathematics—duringtheso-calledGreatCulturalRevolution.Sincetheoreticalresearchhadbeenstoppedatthattime,HuaformedhisownsmallgroupandturnedtoteachingbasicoptimizationtechniquesatcountrysidefactoriesinanefforttohelpmanagersandengineersapplyORintheirdailyoperations.Foradecadebeginningin1965,Huavisitedmorethan20provincesandinnumerabletownsandcitieswithhisgroupandplantedtheseedsofORprinciplesandphilosophieswhereverhewent.HisworkpromotedthedevelopmentofORinChinathenandcontinuestothisday,longafterhisdeath.1.1

TheOriginsofOperationsResearch15TheOperationsResearchSocietyofChinaTheOperationsResearchSocietyofChina(ORSC)wasfoundedaftertheGreatCulturalRevolutionin1980whentheFirstNationalConferenceofORwasheldinShandongProvince.HuawaselectedthefirstpresidentofORSC.ORSCbecameamemberofIFORSin1982.ORSChastwoofficialjournals:ORTransactions,aquarterlyjournalthatpublishesoriginalarticlesinORandrelatedfields(thelanguagecanbeinChineseorEnglish);andOR&MS(inChineseonly),abimonthlyaimedatORpractitioners.

1.1

TheOriginsofOperationsResearch161.2TheNatureofOperationsResearchOperationsresearchmeans“researchonoperations”.Thusoperationsresearchisappliedtoproblemsthatconcernhowtoconductandcoordinatetheoperationswithinanorganization.Therefore,thenatureoftheOperationsResearchis:ORisessentiallyimmaterialandthebreadthofapplicationisunusuallywide.(Wuli-Shili-Renli)Thescientificmethodisusedtoinvestigatetheproblemofconcern.1Introduction17GUJi-fa

TANGXi-jin

ZHUZheng-xiang.SurveyonWuli-Shili-RenliSystemApproach.JOURNALOFTRANSPORTATIONSYSTEMSENGINEERINGANDINFORMATIONTECHNOLOGY,2007,No.061.2TheNatureofOperationsResearch18WhatisOperationsresearchOperationsResearch(OR)isaninterdisciplinarybranchofappliedmathematicsandformalsciencethatusesmethodslikemathematicalmodeling,statistics,andalgorithmstoarriveatoptimalornearoptimalsolutionstocomplexproblems.Operationsresearchhelpsmanagementachieveitsgoalsusingthescientificprocess.FromWikipedia,thefreeencyclopedia1.2TheNatureofOperationsResearch19WhatisOperationsresearchInanutshell,operationsresearch(O.R.)isthedisciplineofapplyingadvancedanalyticalmethodstohelpmakebetterdecisions.Toachievetheseresults,O.R.professionalsdrawuponthelatestanalyticaltechnologies,including:SimulationOptimizationProbabilityandStatistics1.2TheNatureofOperationsResearch20ThecharacteristicsofORare:

ORhasitsbroadviewpoint.ORfrequentlyattemptstofindabestsolutionfortheproblemunderconsideration.Wesayabestinsteadofthebestsolutionbecausetheremaybemultiplesolutionstiedasbest.“Searchforoptimality”

isanimportantthemeinOR.ORexpertsareateamtodoallthethings.1.2TheNatureofOperationsResearch21OR:TheScienceofBetterInrecentyearsanumberofapproachestoproblemswhichhavecometobelabeledcollectivelyas"softOR"haveappeared.BycontrasttheclassicalORtechniquessuchaslinearprogramming,integerprogramming,etcarelabeledcollectivelyas"hardOR".HardORisusedhereinthesensethattraditional/classicalORtechniquesare:tangible;easytoexplain;easytouse.SoftOR,bycontrast,is:somewhatintangible;noteasytoexplain;noteasytouse.FromInforms

1.2TheNatureofOperationsResearch221.3TheimpactofOperationsResearchORhashadanimpressiveimpactonimprovingtheefficiencyofnumerousorganizationsaroundtheworld.Ithasmadeasignificantcontributiontoincreasingtheproductivityoftheeconomiesofvariouscountries.Therenowaremorethan30membercountriesintheinternationalfederationofoperationalresearchsocieties(IFORS),witheachcountryhavinganationaloperationsresearchsociety.

1Introduction23ItappearsthattheimpactofORwillcontinuetogrow.Forexample,uponenteringthe1990s,theU.S.BureauofLaborStatisticspredictedthatORwillbethethird-fastest-growingcareerareaforU.S.collegegraduatesfrom1990to2005.Italsopredictedthat100,000peoplewillbeemployedasoperationsresearchanalystsi