Introduction to Operations Research - COR@L

1 IntroductiontoOperationsResearchMatthew IndustrialandSystemsEngineering,LehighUn iversityServiceParts Solutions, IBMC orporationIntroductionto OperationsResearch OperationsResearch?OptimizationProblemsa ndApplicationsPersonalExamplesIntroducti onto OperationsResearch OperationsReseach?OperationsResearch(OR) startedjustbeforeWorld WarII in Britainwiththeestablishmentof teamsof scientiststo studythestrategicandtacticalproblemsinvo lvedin military Operations . Theobjective wasto findthemosteffective utilizationof limitedmilitary resourcesby theuseofquantitative , numerouspeacetimeapplicationsemerged,lea dingtotheuseof ORandmanagementsciencein many OperationsResearch :A schematicdescriptionof a system,theory, orphenomenonthataccountsforitsknownorinf erredpropertiesandmay beusedforfurtherstudyof :A functionallyrelatedgroupof elements, especially:Thehumanbodyregardedasa whole, groupof physiologicallyoranatomicallycomplementa ry organsorparts:thenervoussystem.

2 Groupof network of structuresandchannels, asforcommunication,travel, network of relatedcomputersoftware, hardware, OperationsResearch (OR)is thestudyof mathematicalmodelsforcomplex a branchof ORwhichusesmathematicaltechniquessuchasl inearandnonlinearprogrammingto derive valuesforsystemvariablesthatwilloptimize OperationsResearch , a singleobjective function,representingeithera profittobemaximizedora costtobeminimized,anda setofconstraintsthatcircumscribethedecis ionvariables. Theobjective capable of solvingproblemscontainingmillionsof variablesandtensofthousandsof Flow ProgrammingA specialcaseof themoregeneral ,theassignmentproblem,theshortestpathpro blem,themaximumflow problem,andtheminimumcostflow efficientalgorithmsexistwhicharemany timesmoreefficientthanlinearprogrammingi n OperationsResearch thevariablesarerequiredto take :Mostproblemsof practicalsize arevery difficultorimpossible and/orany constraintis ,muchmoredifficulttosolve (if notall)realworld applicationsrequirea theproblemstractable, we OperationsResearch DPmodeldescribesa processin termsofstates, decisions, transitionsandreturns.

3 Theprocessbeginsin someinitialstatewherea decisionis transitiontoa new state. Basedonthestartingstate,endingstateandde cisiona return is sequenceof statesuntilfinallya to general functionalformsmay behandledanda globaloptimalsolutionis alwaysobtained."Curseofdimensionality"- thenumberof statesgrowsexponentiallywiththenumberof OperationsResearch practicalsituationstheattributesofa customersin a checkoutline, congestionona highway, thenumberof itemsin a warehouse, andthepriceof a financialsecurityto namea describedin part by enumeratingthestatesin like a snapshotof thesystemat a pointin timethatdescribestheattributesof (ATM) thenumberof customersat orwaitingforthemachine. Timeis thelinearmeasurethroughwhichthesystemmov es. OperationsResearch ChainsA stochasticprocessthatcanbeobservedat regularintervalssuchaseveryday orevery weekcanbedescribedby a matrix whichgivestheprobabilitiesofmovingto eachstatefromevery otherstatein is unchangingwithtime, theprocessis calleda to computea varietyof systemmeasuresthatcanbeusedto analyze andevaluatea Markov ProcessesA continuoustimestochasticprocessin whichthedurationof a entirelydescribedby a matrix showingtherateof transitionfromeachstateto every otherstate.

4 Theratesaretheparametersof theassociatedexponentialdistributions. Theanalyticalresultsarevery similartothoseof a Markov OperationsResearch is oftendifficultto obtaina closedform a very general techniqueforestimatingstatisticalmeasure sofcomplex systemis modeledasif thesystemresponse. Bysimulatinga systemin thisfashionformany replicationsandrecordingtheresponses,one cancomputestatisticsconcerningtheresults . OperationsResearch timeseriesis a sequenceof observationsof a inventory modelrequiresestimatesof a courseschedulingandstaffingmodelfortheun iversitydepartmentrequiresestimatesof A modelforprovidingwarningsto thepopulationin a OperationsResearch TheoryInventoriesarematerialsstored,wait ingforprocessing, muchraw materialshouldbeordered?Whenshoulda productionordershouldbereleasedtotheplan t?Whatlevel of safetystock shouldbemaintainedat a retailoutlet?

5 How is in-processinventory maintainedin a productionprocess?ReliabilityTheoryAttem ptsto assignnumbersto thepropensityof essentiallya problemin OperationsResearch mathematicalmodelconsistsof:DecisionVari ables, Constraints, Objective Function,ParametersandDataThegeneral form of amathprogrammingmodelis:minormaxf(x1; : : : ; xn)s:t:gi(x1; : : : ; xn) = bix2 XLinearprogram(LP):allfunctionsfandgiare linearandXis (IP):Xis OperationsResearch anassignmentof valuesto solutionis anassignmentof valuesto functionvalueof a solutionis obtainedby evaluatingtheobjective functionat (assumingminimization)is onewhoseobjectivefunctionvalueis lessthanorequalto thatof allotherfeasible OperationsResearch OperationsResearch?OptimizationProblemsa ndApplicationsPersonalExamplesIntroducti onto OperationsResearch :Two CrudePetroleumTwo CrudePetroleumdistillscrudefromtwo sources:SaudiArabia,VenezuelaThey have threemainproducts:Gasoline,JetFuel, $20/barrelVenezuela6000barrels$15/barrel Introductionto OperationsResearch :Two CrudePetroleumProductionRequirements(per day)GasolineJetfuelLubricants2000barrels 1500barrels500barrelsObjective:Minimize :min20x1+ 15x2s:t:0:3x1+ 0:4x2 2:00:4x1+ 0:2x2 1:50:2x1+ 0:3x2 0:50 x1 90 x2 6 GraphicalDemoIntroductionto OperationsResearch MethodThesimplex methodgeneratesa sequenceof feasible iteratesbyrepeatedlymovingfromonevertex of thefeasible setto anadjacentvertex witha lowervalueof theobjective function.

6 Whenit is notpossibleto findanadjoiningvertex witha lowervalue, thecurrentvertex mustbeoptimal, (worstcase)runtime;in practice, runsvery OperationsResearch LinearProgrammingSimplex (Dantzig1947)Ellipsoid(Khachian1979)- the"first"polynomial-timealgorithmInteri orPoint- the"first"practicalpolynomial-timealgori thmProjective Method(Karmarkar1984)AffineMethod(Dikin1 967)LogarithmicBarrierMethod(Frisch1955, Fiacco1968, )Introductionto OperationsResearch discreteset(integers).Convex hull of integer solutionsLinear programming relaxationIntroductionto OperationsResearch notjustsolve theLPandround?max1:00x1+ 0:64x2s:t:50x1+ 31x2 2503x1 2x2 4x1 0x2 0 Introductionto OperationsResearch andBoundConsiderproblemP:mincTxs:t:Ax bxi2Z8i2 Iwhere(A; b)2Rm n+1; :Ax b; OperationsResearch ,Cut,andPriceWeyl-Minkowski9( A; b)2R m n+ : Ax bgWe wantthesolutiontominfcTx: Ax tpractical(ornecessary).

7 BCPA pproachFormLPrelaxationsusingsubmatrices of setsV [1::n]andC [1:: m].Forming/managingtheserelaxationseffic ientlyis oneof theprimarychallengeof OperationsResearch ) ^xintegral) ^ ) OperationsResearch andCutMethodsIf thecuttingplaneapproachfails, thenwe divideandconquer(branch).Introductionto OperationsResearch ofBCPT heefficiencyof BCPdependsheavilyonthesize(numberof rowsandcolumns)andtightnessof ) ) to mustbeable to easilymove constraintsandvariablesin OperationsResearch OperationsResearch?OptimizationProblemsa ndApplicationsPersonalExamplesIntroducti onto OperationsResearch ,Packing,PartitioningLetSbea setof objectsand a setofsubsetsofS. Letaij= 1, ifi2 janddefinevariablexj= 1, if thejthmemberof is :minx2f0;1gfi2 cixi:jaijxj 1;8i2 SgSetPacking:maxx2f0;1gfi2 cixi:jaijxj 1;8i2 SgSetPartitioning:minx2f0;1gormaxx2f0;1g fi2 cixi:jaijxj= 1;8i2 SgAirCrew Scheduling(Covering):ConsiderSto bea setof "legs"thattheairlinehastocoverandthememb ersof arepossible OperationsResearch setsof objectsSandTwherejSj=jTj, eachmemberofSmustbeassignedtoexactlyonem emberofT, ;1gfi;k2Sk>ij;l2 Ttikdjlxijxkl:j2 Txij= 1;8i2S;i2 Sxij= 1;8j2 TgFacilityLocation:ConsiderSto bea setofnfactoriesandTto bea setofncities.

8 Locateonefactory in eachcityandminimize thetotalcommunicationcostbetweenfactorie s. Interprettikasthefrequencyof :ConsiderSto bea setofnelectronicmodulesandTto beasetofnpredeterminedpositionsona backplate. Themoduleshave tobeconnectedto eachotherby a seriesof wires. Interprettikasthenumberofwireswhichmustc onnectmoduleito OperationsResearch Findinga pathorcyclein a theshortestpath;a hardoneis , withmany variations, is graphornetwork, thisis a pathfromonenodeto anotherwhosetotalcostis theleastamongallsuchpaths. The"cost"is usuallythesumofthearccosts, butit couldbeanotherfunction( ,theproductforareliabilityproblem,ormaxf ora fuzzymeasureof risk).Vehicleroutingproblem(VRP).Findopt imaldelivery routesfromoneormoredepotsto a setof geographicallyscatteredpoints( ,populationcenters).Initsmostcomplex form,theVRPis a generalizationoftheTSP, asit canincludeadditionaltimeandcapacityconst raints, precedenceconstraints, OperationsResearch determinelevelsofproductionovertime.

9 Constraintsincludedemandrequirements(pos sibly withbackordering),capacitylimits(includi ngwarehousespaceforinventory),andresourc elimits. Definext= level of productionin periodt(beforedemand);yt= level of inventory attheendofperiodt;Ut= productioncapacityin periodt;Wt= warehousecapacityin periodt;ht= holdingcost(perunitof inventory);pt= productioncost(perunitofproduction);Dt= ;yfpx+hy:yt+1=yt+xt Dt;8t;0 x U;0 y WgIntroductionto OperationsResearch is to minimize thevarianceonreturns. Letxjbethepercentofcapitalinvestedin thejthopportunity( ,stock orbond),soxmustsatisfyx 0and jxj= 1. Letvjbetheexpectedreturn perunitof investmentinthejthopportunity, sothatvxis thesumtotalrateof return perunitof is requiredto have a lowerlimitonthisrate:vx b(wherebisbetweenminvjandmaxvj). Subjectto thisrateof return constraint,theobjective is thequadraticform,xTQx, whereQis thevariance-covariancematrix associatedwiththeinvestments( , if theactualreturn rateisVj, thenQij=E[(Vi vi)(Vj vj)] tominxcx+ jxjlogxj:x >0; jxj=M; Ax=b,wheretheobjective is theGibbsfreeenergyfunctionforxj= numberof molesofspeciesj,bi= atomicweightof atomof typei, andaij= numberofatomsoftypeiin onemoleof speciesj.)

10 Theequation,Ax=b, is OperationsResearch OperationsResearch?OptimizationProblemsa ndApplicationsPersonalExamplesIntroducti onto OperationsResearch (Trucksto Loads)Parametric Multi-Criteria ObjectiveEarly/LateDelivery, Early/LatePickupReductionin EmptyTravel,VehicleMaintenanceScheduleDr iverVacation,DriverHoursBalancing(UnionL abor)GUII nterfaceforLoadPlanners(RealTimeDispatch )Lessonin Industry - SystemsDevelopmentParadoxInordertocreate thesystemcorrectlywe neededtheknowledgebaseof OperationsResearch Industry StandardRigidStructuredEchelonStocking/ PerformanceBasedonParts AvailabilityNotime/distancecomponentlink edto "Point-of-Demand"Stock Network LocationsIndependentlyNot Allowed ! (formally) Not Allowed ! (formally) Not Allowed ! (formally) Customer Base Request for Emergency Order Customer Base Request for Emergency Order 85% 75% 95% 90% Introductionto OperationsResearch serve "pooledrisk".