Optimization Methods in Management Science Introduction to Operations Research

Optimization Methods in Management Science z Handouts: – Lecture Notes – Information Sheet – Class syllabus plus more – Sign up sheet – Homework set 1 1 Introductions James Orlin – Professor of Operations Research at Sloan Administrative Assistant: Anna Piccolo 2 Required Materials z Course notes – Assignment 1 will be due next Thursday 3 No laptops are permitted in class. Grading Policy z Midterm 1 (15%) z Midterm 2 (15%) z Final Exam (20%) z Recitation quizzes (20%) z Homework (except Excel) (15%) z Excel Homework and Project (15%) z Extra Credit (up to 5%) 4 Homework Policy z Approximately 1 homework set per week, due on Thursdays. – Students may work in groups of 2 – non-linear grading scheme per assignment (similar to converting scores to A, B, C, D, F) • 85% correct leads to a grade of 5/5 • < 50% correct leads to a grade of 0/5 • lowest score is dropped z Excel Solver “Case study” – around 8 assignments on a “diet problem.” – illustrates many different concepts in 15.053 – individual work (but students can discuss with others) 5 The Excel case study is new this year. In the past, we have had Excel as part of the regular homework; because homework was done in teams, many students deferred the Excel to their partner. Moreover, the Excel assignments were very time consuming. This year, we have a continuing case study. By using a single example throughout the term, we can better illustrate the way that Excel can be used in practice to solve optimization problems. In addition, having a running example makes it more efficient for students to carry out the assignment. Class Requirements z “Required” Lecture Attendance - 4% for missing more than 10 lectures -2% points for missing between 7 and 10 lectures + 2% points for missing at most 2 lectures z Required Recitation Attendance – weekly quizzes (15% of the grade) – attendance (5% of the grade) – There is recitation this week. – sections will be posted on line on Wednesday. 6 We have given the requirements of class attendance and recitation attendance a lot of thought. Ironically, it is also typical of what is expected of MBA students, and it is expected of job performance in most any job. It is a relatively short phase of one’s life (undergraduate education), where attendance is usually optional. Most classes expect students to keep up with the material by preparing in advance of class and then participating in class discussions. In 15.053, we provide incentives for students to keep up with the materials through required class and recitation attendance and through quizzes. We have found that this is very effective. Since requiring recitations, students have mastered the material far better, and their grades have reflected it. Moreover, we have set the grading policy in the past, and we do not adjust it upwards as students are learning more. So, if every student learns the material well, it is possible for every student to get an A. “Active Learning” z Occasionally I will introduce a break in the lecture for you to work on your own or with an in-class partner. “Cognitive balancing.” z Please identify your “partner” now. z Those on aisle ends may be in a group of size 3. 7 Even very intelligent people have difficulty absorbing new information for an extended period of time without being able to reflect on that material. The breaks in class are sometimes used for reflection, and sometimes used for a mental break between different subjects. An optimization problem z Given a collection of numbers, partition them into two groups such that the difference in the sums is as small as possible. z Example: 7, 10, 13, 17, 20, 22 These numbers sum to 89 I can split them into {7, 10, 13, 17} {20, 22} Difference sum is 47 sum is 42 = 5. Can we do better? 8 The amazing thing about this Excel example is that it typically leads to solutions that are under 10, often 0 or 1. This would be extremely hard to achieve without formal optimization. What is Operations Research? What is Management Science? z World War II : British military leaders asked scientists and engineers to analyze several military problems – Deployment of radar – Management of convoy, bombing, antisubmarine, and mining operations. z The result was called Operations Research z MIT was one of the birthplaces of OR – Professor Morse at MIT was a pioneer in the US – Founded MIT OR Center and helped to found ORSA 9 For a book on the history of OR, see Professor Morse’s autobiography In at the Beginnings: A Physicist's Life. Also, there is a book by Gass and Assad entitled “An Annotated Timeline of Operations Research: and Informal History. (The only event listed for 1993 was the awarding of the Lanchester Prize to the book Network Flows, co-authored by Ravi Ahuja, Tom Magnanti, and Jim Orlin). What is Management Science (Operations Research)? Operations Research (O.R.) is the discipline of applying advanced analytical methods to help make better decisions. 10 There is a promotional activity in our society which says that OR is the “science of better.” The hope of this promotion was that it would encourage a dialogue about what OR really is, with the “science of better” being its starting point. Unfortunately, it often leads to questions such as “If OR is really the science of better, why couldn’t they come up with a better slogan?” And I do not have an answer for this. Examples of OR/MS in Practice Airline fleet management Moldavian Airlines Budapest Chisinau Timisoara Figure by MIT OCW. Revenue management and pricing Image removed due to copyright restrictions 11 Examples of OR/MS in Practice Supply chain management Travelocity Image removed due to copyright restrictions Image removed due to copyright restrictions 12 Some Skills for Operations Researchers z Modeling Skills – Take a real world situation, and model it using mathematics z Methodological Toolkit – Optimization – Probabilistic Models Image removed due to copyright restrictions Not this Image removed due to copyright restrictions 13 Some of the themes z z z Optimization is everywhere Models, Models, Models The goal of models is “insight” not numbers – paraphrase of Richard Hamming z Algorithms, Algorithms, Algorithms 14 Check out the course information for more on these themes. Optimization is Everywhere z It is embedded in language, and part of the way we think. – – – – – firms want to maximize value to shareholders people want to make the best choices We want the highest quality at the lowest price When playing games, we want the best strategy When we have too much to do, we want to optimize the use of our time – etc. Take 3 minutes with your partner to brainstorm on where optimization might be used. (business, or sports, or personal uses, or politics, or …) 15 Usually when people brainstorm, they come up with a wide range of places where optimization occurs. Within sports, anyone who has read “Moneyball” knows that baseball General Managers try to develop an optimum team by carefully analyzing each players statistics. And, each manager is trying to win each game, which is a form of optimization. Usually several students have worked with firms that are interested in “supply chain management.” This involves optimizing the obtaining of materials for manufacturing, and also involves the optimum distribution of delivered products. Within politics, optimizing the use of TV advertising is becoming a crucial skill. Countless other applications of optimization can come to mind with more thought. 16 I left this page blank to write in places where optimization occurs. From Google Search z We searched Google for the number of pages with the expression “optimal X” z So, let us guess what was in the top 8 by playing the 15.053 version of family feud. 17 On the internet, what is the last word in the phrase “optimal _”. Performance 1 1.24 Design 5 .88 Control 2 1.12 Time 6 .63 Health 3 1.01 Choice 7 .60 Solution 4 .96 Growth 8 .56 Hide answers Totals are in millions 18 It took me a long time to find out how to do the effects on this slide. Click on a number and the answer is revealed. Click on a red rectangle and the number of Google hits (in millions) is revealed. Click on “hide answers” and all the answers are hidden again. Optimization Tools z Some goals: – Present a variety of tools for optimization – Illustrate applications in manufacturing, finance, ebusiness, marketing and more. – Prepare students to recognize opportunities for mathematical optimization as they arise 19 Linear Programming z z minimize or maximize a linear objective subject to linear equalities and inequalities Example. Max is in a pie eating contest that lasts 1 hour. Each torte that he eats takes 2 minutes. Each apple pie that he eats takes 3 minutes. He receives 4 points for each torte and 5 points for each pie. What should Max eat so as to get the most points? Step 1. Determine the decision variables Let x be the number of tortes eaten by Max. z Let y be the number of pies eaten by Max. z 20 The decision variables are the variables whose specification describes the solution for the problem. It typically comprises the set of decisions to be made. Max’s linear program Step 2. Determine the objective function Step 3. Determine the constraints Maximize z = 4x + 5y subject to 2x + 3y ≤ 60 (objective function) (constraint) x ≥ 0 ; y ≥ 0 (non-negativity constraints) A feasible solution satisfies all of the constraints. x = 10, y = 10 is feasible; x = 10, y = 15 is infeasible. An optimal solution is the best feasible solution. The optimal solution is x = 30, y = 0, z = 120. 21 The objective function for a linear program is a linear function that we want to maximize or minimize. A linear function of x and y is of the form ax + by for some real numbers a and b. The constraints provide limits on what choices of decision variables are permissible. Terminology z Decision variables: e.g., x and y. – In general, these are quantities you can control to improve your objective which should completely describe the set of decisions to be made. z Constraints: e.g., 2x + 3y ≤ 24 , x ≥ 0 , y ≥ 0 – Limitations on the values of the decision variables. z Objective Function. e.g., 4x + 5y – Value measure used to rank alternatives – Seek to maximize or minimize this objective – examples: maximize NPV, minimize cost 22 A geometrical portrayal y 10 8 2x + 3y ≤ 24 6 The optimal solution 4 2 Feasible Region x 2 4 6 8 10 12 23 In order to get insight into properties of linear programs, it helps to consider the geometry. In Lectures 3 and 4, we will consider geometrical properties of linear programs in detail. David’s Tool Corporation (DTC) z Motto: “We may be no Goliath, but we think big.” z Manufacturer of slingshots kits and stone shields. 24 David’s tool Corporation is a fanciful and ahistorical application of linear programming. But it is also representative of “product mix” applications of linear programs, that is, what is a mix of products to manufacture that satisfies resource constraints and maximizes net revenue. Data for the DTC Problem Resources Slingshot Kits Stone Shields Stone Gathering time 2 hours 3 hours 100 hours Stone Smoothing 1 hour 2 hours 60 hours Delivery time 1 hour 1 hour 50 hours Demand 40 30 3 shekels 5 shekels Profit 25 Formulating the DTC Problem as an LP Step 1: Determine Decision Variables K = number of slingshot kits manufactured S = number of stone shields manufactured Step 2: Write the Objective Function as a linear function of the decision variables Maximize Profit = Step 3: Write the constraints as linear functions of the decision variables subject to 26 When formulating a linear program, one typically chooses the decision variables first. Then one writes the objectives and constraints. If it is too difficult to express the constraints, then one may want to reconsider the choice of decision variables. On this slide, we start to formulate the problem. The Formulation Continued Step 3: Determine Constraints Stone gathering: Smoothing: Delivery: Slingshot demand: Shield demand: We will show how to solve this in Lecture 3. 27 maximize 3K + 5S 2K + 3S <= 100 K + 2S <= 60 K + S <= 50 K <= 40 S <= 50 K >= 0 and S >= 0. We ignore integrality constraints. Addressing managerial problems: A management science framework 1. Determine the problem to be solved 2. Observe the system and gather data 3. Formulate a mathematical model of the problem and any important subproblems 4. Verify the model and use the model for prediction or analysis 5. Select a suitable alternative 6. Present the results to the organization 7. Implement and evaluate 28 This framework is one of many on how to solve a managerial problem using Operations Research techniques. Steps 3 and 5 are highlighted (underlined) because we will focus on them during the semester. How problems get large, and what to do. z Suppose that there are 10,000 products and 100 raw materials and processes that lead to constraints. Then use an algebraic description of the problem, as described in the tutorial. 29 In practice, problems can get very large, much too large to consider for Excel Solver. This slide illustates how the simple DTC problem can get very large if one has lots of products and raw materials. 10,000 products seems like a lot, but there are more than 10,000 different types of screwdrivers. It is easy to imagine that there can be lots of products for more complex applications. Linear Programs z A linear function is a function of the form: f(x1, x2, . . . , xn) = c1x1 + c2x2 + . . . + cnxn = ∑i=1 to n cixi e.g., z 3x1 + 4x2 - 3x4. A mathematical program is a linear program (LP) if the objective is a linear function and the constraints are linear equalities or inequalities. e.g., 3x1 + 4x2 - 3x4 ≥ 7 x1 - 2x5 = 7 z Typically, an LP has non-negativity constraints. 30 We usually use cj to denote the cost coefficient for variable xj. It really helps to understand abstract formulations if a similar notation is used from problem to problem. More on Linear Programs z A linear program must have linear objectives and linear equalities and inequalities to be considered a linear program. Maximize x1 subject to 3x1 + 4x2 ≥ 7 x1 - 2x5 = 7 |x1| ≥ 0 Maximize x2 subject to x = 3 Not a linear program. Not a linear program. 31 It’s also not a linear program if the inequality constraints are strict, as in x > 0. A non-linear program is permitted to have a non-linear objective and constraints. z z maximize f(x,y) = xy subject to x - y2/2 ≤ 10 3x – 4y ≥ 2 x ≥ 0, y ≥ 0 Minimize x subject to x ≥ 3 Both a linear and a non-linear program. 32 It’s weird that a special case of “nonlinear programming” is linear programming. But this is because nonlinear programming permits a nonlinear objective and nonlinear constraints, but it does not require them. An integer program is a linear program plus constraints that some or all of the variables are integer valued. z Maximize 3x1 + 4x2 - 3x3 3x1 + 2x2 - x3 ≥ 17 3x2 - x3 = 14 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 and x1 , x2, x3 are all integers 33 Preview of Some Examples Applying LP and NLP to optimal radiation therapy. How to price in a fair manner. 34 We will talk about radiation therapy in Lecture 2. We will discuss pricing issues when we talk about linear programming duality. Preview Continued Image removed due to copyright restrictions Find the shortest path in a network 35 More preview 2-person zero sum games. How to solve puzzles 36 More on these examples later. Summary z Answered the question: What is Operations Research & Management Science? and provided some historical perspective. z Introduced the terminology of linear programming z An Examples: David’s Tool Company 37