Transcription
OPERATIONS RESEARCHLECTURE NOTESY. İlker Topcu, Prof. Dr.Acknowledgements:We would like to acknowledge Prof. W.L. Winston's "Operations Research: Applications andAlgorithms" and Prof. J.E. Beasley's lecture notes which greatly influence these notes.We retain responsibility for all errors and would love to hear from visitors of this site!Istanbul Technical University OR/MS teamY. İlker Topcu, Ph.D. (www.ilkertopcu.info)
CONTENTSOPERATIONS RESEARCH . 11.INTRODUCTION TO OR. 11.1TERMINOLOGY . 11.2THE METHODOLOGY OF OR . 11.3HISTORY OF OR . 22.BASIC OR CONCEPTS . 63.LINEAR PROGRAMMING . 113.1FORMULATING LP . 133.1.1Giapetto Example . 133.1.2Advertisement Example . 143.1.3Diet Example . 153.1.4Post Office Example. 163.1.5Sailco Example . 163.1.6Customer Service Level Example . 173.2SOLVING LP . 193.2.1LP Solutions: Four Cases. 193.2.2The Graphical Solution . 193.2.3The Simplex Algorithm. 243.2.4The Big M Method . 303.2.5Unrestricted in Sign Variables . 333.3DUALITY . 353.3.1Primal – Dual . 353.3.2Finding the Dual of an LP . 353.3.3The Dual Theorem. 363.3.4Economic Interpretation. 393.4SENSITIVITY ANALYSIS . 413.4.1Reduced Cost. 413.4.2Shadow Price . 413.4.3Conceptualization . 413.4.4Utilizing Lindo Output for Sensitivity . 423.4.5Some important equations . 433.4.6Utilizing Simplex for Sensitivity. 44Y. İlker Topcu, Ph.D. (www.ilkertopcu.info)i
4.3.4.7Interpretation of Dual Prices . 463.4.8Duality and Sensitivity Analysis . 473.4.9The 100% Rule . 49TRANSPORTATION PROBLEMS . 554.14.1.1Formulating Balanced Transportation Problem . 564.1.2Balancing an Unbalanced Transportation Problem . 574.25.FORMULATING TRANSPORTATION PROBLEMS . 55FINDING BFS FOR TRANSPORT’N PROBLEMS . 584.2.1Northwest Corner Method . 594.2.2Minimum Cost Method . 614.2.3Vogel’s Method . 624.3THE TRANSPORTATION SIMPLEX METHOD . 644.4TRANSSHIPMENT PROBLEMS . 674.5ASSIGNMENT PROBLEMS . 704.5.1LP Representation . 704.5.2Hungarian Method . 70INTEGER PROGRAMMING . 745.1FORMULATING IP . 755.1.1Budgeting Problems . 755.1.2Knapsack Problems . 775.1.3Fixed Charge Problems . 775.1.4Membership in Specified Subsets. 815.1.5Either-Or Constraints . 845.1.6If-Then Constraints . 855.1.7Traveling Salesperson Problems . 855.2SOLVING IP . 875.2.1Categorization . 875.2.2LP Relaxation . 885.2.3Enumeration . 895.2.4The Branch-and-Bound Method . 905.2.5Cutting Planes . 106Y. İlker Topcu, Ph.D. (www.ilkertopcu.info)ii
1.INTRODUCTION TO OR1.1TERMINOLOGYThe British/Europeans refer to "operational research", the Americans to "operationsresearch" - but both are often shortened to just "OR" (which is the term we will use).Another term which is used for this field is "management science" ("MS"). TheAmericans sometimes combine the terms OR and MS together and say "OR/MS" or"ORMS".Yet other terms sometimes used are "industrial engineering" ("IE"), "decisionscience" ("DS"), and “problem solving”.In recent years there has been a move towards a standardization upon a single termfor the field, namely the term "OR".“Operations Research (Management Science) is a scientific approach to decisionmaking that seeks to best design and operate a system, usually under conditionsrequiring the allocation of scarce resources.”A system is an organization of interdependent components that work together toaccomplish the goal of the system.1.2THE METHODOLOGY OF ORWhen OR is used to solve a problem of an organization, the following seven stepprocedure should be followed:Step 1. Formulate the ProblemOR analyst first defines the organization's problem. Defining the problem includesspecifying the organization's objectives and the parts of the organization (or system)that must be studied before the problem can be solved.Step 2. Observe the SystemNext, the analyst collects data to estimate the values of parameters that affect theorganization's problem. These estimates are used to develop (in Step 3) andevaluate (in Step 4) a mathematical model of the organization's problem.Y. İlker Topcu, Ph.D. (www.ilkertopcu.info)1
Step 3. Formulate a Mathematical Model of the ProblemThe analyst, then, develops a mathematical model (in other words an idealizedrepresentation) of the problem. In this class, we describe many mathematicaltechniques that can be used to model systems.Step 4. Verify the Model and Use the Model for PredictionThe analyst now tries to determine if the mathematical model developed in Step 3 isan accurate representation of reality. To determine how well the model fits reality,one determines how valid the model is for the current situation.Step 5. Select a Suitable AlternativeGiven a model and a set of alternatives, the analyst chooses the alternative (if thereis one) that best meets the organization's objectives.Sometimes the set of alternatives is subject to certain restrictions and constraints. Inmany situations, the best alternative may be impossible or too costly to determine.Step 6. Present the Results and Conclusions of the StudyIn this step, the analyst presents the model and the recommendations from Step 5 tothe decision making individual or group. In some situations, one might presentseveral alternatives and let the organization choose the decision maker(s) choosethe one that best meets her/his/their needs.After presenting the results of the OR study to the decision maker(s), the analyst mayfind that s/he does not (or they do not) approve of the recommendations. This mayresult from incorrect definition of the problem on hand or from failure to involvedecision maker(s) from the start of the project. In this case, the analyst should returnto Step 1, 2, or 3.Step 7. Implement and Evaluate RecommendationIf the decision maker(s) has accepted the study, the analyst aids in implementing therecommendations. The system must be constantly monitored (and updateddynamically as the environment changes) to ensure that the recommendations areenabling decision maker(s) to meet her/his/their objectives.1.3HISTORY OF OR(Prof. Beasley’s lecture notes)OR is a relatively new discipline. Whereas 70 years ago it would have been possibleto study mathematics, physics or engineering (for example) at university it would nothave been possible to study OR, indeed the term OR did not exist then. It was onlyY. İlker Topcu, Ph.D. (www.ilkertopcu.info)2
really in the late 1930's that operational research began in a systematic fashion, andit started in the UK.Early in 1936 the British Air Ministry established Bawdsey Research Station, on theeast coast, near Felixstowe, Suffolk, as the centre where all pre-war radarexperiments for both the Air Force and the Army would be carried out. Experimentalradar equipment was brought up to a high state of reliability and ranges of over 100miles on aircraft were obtained.It was also in 1936 that Royal Air Force (RAF) Fighter Command, chargedspecifically with the air defense of Britain, was first created. It lacked however anyeffective fighter aircraft - no Hurricanes or Spitfires had come into service - and noradar data was yet fed into its very elementary warning and control system.It had become clear that radar would create a whole new series of problems in fighterdirection and control so in late 1936 some experiments started at Biggin Hill in Kentinto the effective use of such data. This early work, attempting to integrate radar datawith ground based observer data for fighter interception, was the start of OR.The first of three major pre-war air-defense exercises was carried out in the summerof 1937. The experimental radar station at Bawdsey Research Station was broughtinto operation and the information derived from it was fed into the general air-defensewarning and control system. From the early warning point of view this exercise wasencouraging, but the tracking information obtained from radar, after filtering andtransmission through the control and display network, was not very satisfactory.In July 1938 a second major air-defense exercise was carried out. Four additionalradar stations had been installed along the coast and it was hoped that Britain nowhad an aircraft location and control system greatly improved both in coverage andeffectiveness. Not so! The exercise revealed, rather, that a new and serious problemhad arisen. This was the need to coordinate and correlate the additional, and oftenconflicting, information received from the additional radar stations. With the out-breakof war apparently imminent, it was obvious that something new - drastic if necessary- had to be attempted. Some new approach was needed.Accordingly, on the termination of the exercise, the Superintendent of BawdseyResearch Station, A.P. Rowe, announced that although the exercise had againdemonstrated the technical feasibility of the radar system for detecting aircraft, itsoperational achievements still fell far short of requirements. He therefore proposedthat a crash program of research into the operational - as opposed to the technical Y. İl
“Operations Research (Management Science) is a scientific approach to decision making that seeks to best design and operate a system, usually under conditions requiring the allocation of scarce resources.” A system is an organization of interdependent components that work together to accomplish the goal of the system. 1.2 THE METHODOLOGY OF ORFile Size: 1MBPage Count: 101
