z Introduction to Optimization z Handouts: – Lecture Notes – Info Sheet – 1-page subject description Goals for this Lecture z Course Administration Background on Operations Research (Management Science) and Optimization Course Themes and Goals z Linear Programming Examples z z – MSR Marketing – DTC z Some time to choose a homework partner and fill in a info sheet Grading Policy z Homework assignments (25%) z Midterm Exams (40%: 20% each) – March 10th, 7:30 to 9:30 PM – April 21st, 7:30 to 9:30 PM z Final Exam (20%) – During Finals week z Recitation quizzes (16%) z Extra credit mini-project (5%) “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. 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 What is Management Science (Operations Research)? Operations Research (O.R.) is the discipline of applying advanced analytical methods to help make better decisions. It is the “Science of Better” Voices from the past Waste neither time nor money, but make the best use of both. -- Benjamin Franklin Obviously, the highest type of efficiency is that which can utilize existing material to the best advantage. -- Jawaharlal Nehru It is more probable that the average man could, with no injury to his health, increase his efficiency fifty percent. -- Walter Scott Operations Research Over the Years z 1947 – Project Scoop (Scientific Computation of Optimum Programs) with George Dantzig and others. Developed the simplex method for linear programs. z 1950's – Lots of excitement, mathematical developments, queuing theory, mathematical programming. z 1960's – More excitement, more development and grand plans. Operations Research Over the Years z 1970's – Disappointment, and a settling down. NPcompleteness. More realistic expectations. z 1980's – Widespread availability of personal computers. Increasingly easy access to data. Widespread willingness of managers to use models. z 1990's – Improved use of O.R. systems. Further inroads of O.R. technology, e.g., optimization and simulation add-ins to spreadsheets, modeling languages, large scale optimization. More intermixing of A.I. and O.R. Operations Research in the 2000’s z LOTS of opportunities for OR as a field z Data, data, data – E-business data (click stream, purchases, other transactional data, E-mail and more) – Sensor data – The human genome project and its outgrowth z Need for more automated decision making z Need for increased coordination for efficient use of resources (Supply chain management) Some Skills for Operations Researchers z Modeling Skills – Take a real world situation, and model it using mathematics z Methodological Toolkit – Optimization – Probabilistic Models Optimization As ageless as time Optimization in Nature Heron of Alexandria b’ Angle of Incidence Angle of Angle of Incidence b Reflection a First Century A.D FERMAT Angle α1 of Angle α2 of Incidence Refraction 1628-29 Calculus Maximum Minimum Fermat, Newton, Euler, Lagrange, Gauss, and more 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 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 …) “Optimize the ….” or “optimal ….” American Airlines Optimal crew scheduling saves $20 million/year Optimal yield management contributes $500 million per year Revenue management saves National Car rental $56 million in one year Better truck dispatching at Reynolds Metals improves on-time delivery and reduces annual freight costs by $7 million Improved shipment routing saves Yellow freight over $17.3 million/year GTE local access capacity expansion saves $30 million per year Optimizing its global supply chains saves Digital Equipment over $300 million Restructuring North America operations, Proctor and Gamble reduces plants by 20%, saving $200 million/year Taha Steel (India) maximizes production in response to power shortages contributing $73 million Improved production planning at Sadia (Brazil) saves $50 million over three years Production optimization at Harris Corporation improves on-time deliveries from 75% to 90% Optimal traffic control of the Hanshin Expressway in Osaka saves 17 million driver hours with benefits of $320 million Better scheduling of hydro and thermal generating units saves Southern Company $140 million From Google Search Search phrase “optimize the supply chain” “optimize (the) return” “optimal experience” “optimal investment” “optimal system” “optimal decision” “optimize your PC” “optimal choice” “optimal design” “optimal health” number of hits 12,000 16,490 39,800 57,000 63,800 66,000 81,000 163,000 285,000 382,000 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 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 z Let x be the number of tortes eaten by Max. z Let y be the number of pies eaten by Max. 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. 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 MSR Marketing Inc. adapted from Frontline Systems •Need to choose ads to reach at least 1.5 million people •Minimize Cost •Upper bound on number of ads of each type Audience Size Cost/Impression Max # of ads TV Radio Mail Newspaper 50,000 25,000 20,000 15,000 $500 $200 $250 $125 15 10 15 20 Formulating as a math model Work with your partner 1. The decisions are how many ads of each type to choose. Let x1 be the number of TV ads selected. Let x2, x3, x4 denote the number of radio, mail, and newspaper ads. These are the “decision variables.” 2. What is the objective? Express the objective in terms of the decision variables. 3. What are the constraints? Express these in terms of the decision variables. 4. If you have time, try to find the best solution. 2 minutes write on the board the decision variables the objective function and the constraints David’s Tool Corporation (DTC) z Motto: “We may be no Goliath, but we think big.” z Manufacturer of slingshots kits and stone shields. 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 To do with your partner z Take two minutes to work with your partner to formulate the DTC problem as a linear program. z Let K = number of slingshot kits made Let S = number of stone shields made z 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 The Formulation Continued Step 3: Determine Constraints Stone gathering: Smoothing: Delivery: Slingshot demand: Shield demand: 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 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. z New technique used: write an “algebraic version of the model” An Algebraic Formulation z n = number of items that are manufactured – e.g., in the previous example, n = 2; z m = number of resource constraints – e.g., m = 3, {gathering, smoothing, and delivery.} Decision Variables z xj = number of units of item j manufactured z pj = unit profit from item j, e.g., p1 = 3; z dj = maximum demand for item j; e.g., z bi = amount of resource i available z aij = amount of resource i used in making item j Data for objective function Data for constraints An Algebraic formulation n Maximize ∑p x j =1 n subject to ∑a j =1 j ij j x j ≤ bi for i = 1 to m x j ≤ d j for j = 1 to n x j ≥ 0 for j = 1 to n 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. 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 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 Linear Programming Assumptions Maximize 4K+3S 2K+ 3S ≤ …. 10 Proportionality Assumption Contribution from K is proportional to K Additivity Assumption Contribution to objective function from K is independent of S. Divisibility Assumption Each variable is allowed to assume fractional values. Certainty Assumption. Each linear coefficient of the objective function and constraints is known (and is not a random variable). Some Success Stories z Optimal crew scheduling saves American Airlines $20 million/yr. z Improved shipment routing saves Yellow Freight over $17.3 million/yr. z Improved truck dispatching at Reynolds Metals improves on-time delivery and reduces freight cost by $7 million/yr. z GTE local capacity expansion saves $30 million/yr. Mention Cindy Barnhart’s success at United Airlines: her fleet routing models are estimated to save United $100,000,000 per year. Our solutions have an estimated savings of $25 million per year. Mention our work with CSX Mention Interfaces. Other Success Stories (cont.) z Optimizing global supply chains saves Digital Equipment over $300 million. z Restructuring North America Operations, Proctor and Gamble reduces plants by 20%, saving $200 million/yr. z Optimal traffic control of Hanshin Expressway in Osaka saves 17 million driver hours/yr. z Better scheduling of hydro and thermal generating units saves southern company $140 million. Success Stories (cont.) z Improved production planning at Sadia (Brazil) saves $50 million over three years. z Production Optimization at Harris Corporation improves on-time deliveries from 75% to 90%. z Tata Steel (India) optimizes response to power shortage contributing $73 million. z Optimizing police patrol officer scheduling saves police department $11 million/yr. z Gasoline blending at Texaco results in saving of over $30 million/yr. Summary z Answered the question: What is Operations Research & Management Science? and provided some historical perspective. z Introduced the terminology of linear programming z Two Examples: 1. 2. MSR Marketing David’s Tool Company z “Lecture check” problems.