AEM412 Computational Methods for Management and Economics Carla P. Gomes Module 1 Introduction Overview of this Lecture • Course Administration • Course Themes, Goals, and Syllabus • Background on Mathematical Programming • The Impact of Information Technology on Business Practice Course Administration AEM412 - Introduction to Mathematical Programming Lectures: Tuesday and Thursday - 11:40 - 12:55 Location: WN 245 Lecturer: Prof. Gomes Office: 448 Warren Hall Phone: 255 1679 or 255 9189 Email: cpg5@cornell.edu or gomes@cs.cornell.edu TA: Vivian Eliza Hoffmann (veh4@cornell.edu) Administrative Assistant: Dawn Vail (dmv9@cornell.edu) 147 Warren Hall, 254-6761 Web Site: http://courseinfo.cit.cornell.edu/courses/aem412/ Office Hours • Prof. Gomes Monday and Wednesday: 3:00p.m – 4:00 p.m. • TA – Vivian Hoffmann Tuesday (WN360) and Wednesday (WN201): 1:30 p.m – 2:30 p.m. Grades Midterm (15%) Homework (35%) Participation (5%) Final (45%) Note: The lowest homework grade will be dropped before the final grade is computed. Required Textbook Introduction to Operations Research by Frederick S. Hillier and Gerald. J. Lieberman, 7th Edition Overview of this Lecture • Course Administration • Course Themes, Goals, and Syllabus • Background on Mathematical Programming • The Impact of Information Technology on Business Practice Course Themes, Goals, and Syllabus What’s Mathematical Programming (MP)? Main focus: Optimization Optimization is pervasive in business and economics and almost all aspects of human endeavor, including science and engineering. Optimization is everywhere: part of our language and 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 –In games, we want the best strategy –We want to optimize the use of our time, –etc Optimization • • • • • • • • • • Financial planning Marketing E-business Telecommunications Manufacturing Operations Management Production Planning Transportation Planning System Design Health Care Some of the themes of 412 • Optimization!!! • Models, Models, Models (insights not numbers) • • • • Applications in business and economics Algorithms, Algorithms, Algorithms Efficient Algorithms --- whenever possible Importance of factoring in computational issues in business and economic applications: computational limits and intractability What’s Mathematical Programming? •Very broad discipline covering a variety of Optimization topics such as: – Linear Programming –Non-linear Programming – Advanced Linear Programming Models – Network Models – Integer Programming –Decision Making under Uncertainty – Dynamic Programming – Heuristic techniques • Simulated Annealing • Genetic Algorithms • Tabu Search • Neural Networks –Decision Making with Multiple Objectives –Game Theory –etc Syllabus 412 • Linear Programming – Introduction – Simplex/Revised Simplex – Duality and Sensitivity Analysis – Other LP Algorithms • Network Models – Transportation Problems – Assignment Problems – Network Optimization Models • Special Topics(*) – Integer Programming – Dynamic Programming – Heuristic techniques • • • • Simulated Annealing Genetic Algorithms Tabu Search Neural Networks – Computational complexity(*) (*)time permitting Goals in 412 – Present a variety of models, algorithms, and tools for optimization – Illustrate applications in business and economics, and other fields. – Prepare students to recognize opportunities for mathematical optimization as they arise – Prepare students to be aware of computational complexity issues: importance of using efficient algorithms whenever possible and the limits of computation that can affect the validity of business and economic models. Background on Mathematical Programming Origins of Operations Research (OR) • The roots of OR can be traced back many decades and even centuries (Newton, Euler, Bernoulli, Bayes, Lagrange, etc). • Beginning of the activity called Operations Research --- attributed to the military services early in the World War II (1937). – Need to allocate scarce resources to the various military operations in an effective manner. – The British first and then the U.S military management called upon a large number of scientists to apply a scientific approach to dealing with several military problems • End of war – scientists understood that OR could be applied outside the military as well. • The industrial boom following the war led to an increasing complexity and specialization of organizations scientific management techniques became more and more crucial. • By the early 1950s, OR techniques were being applied to a variety of organizations in business, industry, and government. Impact of Operations Research Key Factors for Rapid Growth of OR • Substantial progress was made early in improving the techniques in OR – Simplex, Dynamic Programming, Integer Programming, Inventory Theory, Queing Theory, etc • Computer revolution - 1980s the PC further boosted this trend. Timeline Operations Research Over the Years • 1947 – Project Scoop (Scientific Computation of Optimum Programs) with George Dantzig and others. Developed the simplex method for linear programs. • 1950's – Lots of excitement, mathematical developments, queuing theory, mathematical programming. cf. A.I. in the 1960's • 1960's – More excitement, more development and grand plans. cf. A.I. in the 1980's. Source: J. Orlin (MIT) 2003 Operations Research Over the Years • 1970's – Disappointment, and a settling down. NPcompleteness. More realistic expectations. • 1980's – Widespread availability of personal computers. Increasingly easy access to data. Widespread willingness of managers to use models. • 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 00’s • LOTS of opportunities for OR as a field • Data, data, data – E-business data (click stream, purchases, other transactional data, E-mail and more) – The human genome project and its outgrowth • Need for more automated decision making • Need for increased coordination for efficient use of resources (Supply chain management) The Impact of Information Technology on Business Practice Advances in information technology are increasingly impacting on business and business practices. Exciting new opportunities (and some risks). Examples of applications Driving Force Exponential Growth a) Compute power b) Data storage c) Networking Combined with algorithmic advances (software) Compute power: Doubling every 18 months 100,000,000 transistors per processor 4,000 transistors per processor How much can be stored in one Terabyte? Yr ’06, 1 Terabyte for $200. Storage for $200 video 1 Gigabyte/hour 1000 hours scanned color images 1 Megabyte each 1 million images text pages 3300 bytes/page 300 million pages (Library of Congress) Wal-Mart customer data: 200 terabyte --- daily data mining for customer trends Microsoft already working on a PC where nothing is ever deleted. You will have a personal Google on your PC. The Network: The Internet This new level of connectivity allows for much faster, and more substantive interactions between companies/suppliers/customers (e.g. electronic markets) 1981 --- 200 computers 1990 --- 300,000 1995 --- 6.5M 1997 --- 25M 2002 --- 300M Examples of business impact 1) Supply-chain-management 2) Electronic markets 3) Beyond traditional scheduling application Dell premier example of integration of information technology into the business model. Direct business-to-consumer model • 1984 -- Michael Dell founds Dell • 1996 – Dell starts selling computers via Internet at www.dell.com • 1999 – "E-Support Direct from Dell" online technical support • • 2001 – Company sales via Internet exceed $40 M per day Dell ranks No 1 in global market share • 2003 – Revenue – $32.1 Billion Direct business-to-consumer model Power of Virtual Integration Supply Chain Strategy and Processes Reporting Solution DELL manages relationships with over 80% of suppliers through the Internet. Report Users Legacy Systems Over half of Dell customers use Webenabled support (over 40,000 Premier Pages-10,000 in Europe). Factory Planner Users Factory Planner Supply Logistics Center Collaboration Suppliers Supply Chain Planning Supply Chain Planning Users Supplier Collaboration Internet Real-time Access and Transactions Supply Hubs Product configuration tools Efficient supply chain: Online design of made-to-order system. Innovative product design, Constraint-based reasoning tools (knowledge about allowable system configurations) An Internet order-taking process, Customer-to-Knowledge An innovative assembly system, Customers search Dell databases Close cooperation with suppliers. Knowledge content for typical responses Personalization tools Optimization is everywhere Electronic Markets Combinatorial Auctions Why Combinatorial Auctions? More expressive power to bidders In combinatorial auctions bidders have preferences not just for particular items but for sets or bundles of Items due because of complementarities or substitution effects. Example Bids: Airport time slots [(take-off right in NYC @ time slot X ) AND (landing right in LAX @ time slot y)] for $9,750.00 Delivery routes (“lanes”) [(NYC - Miami ) AND [((Miami – Philadelphia) AND (Philadelphia – NYC)) OR ((Miami – Washington) AND (Washington – NYC))]] for $700.00 Procurement Transportation Services on the web. OPTIBID - software for combinatorial auctions Managing over 100,000 trucks a day (June 2002), >$8 billion worth of transportation services. • FCC auctions spectrum licenses ( geographic regions and various frequency bands). •Raised billions of dollars •Currently licenses are sold in separate auctions •USA Congress mandated that the next spectrum auction be made combinatorial. FCC Auction #31 700 MHz Winner Determination Problem $12e6 + $16e6 +$8e6 = Choose among a set of bids such that: • Revenue to the FCC is maximized $22e6 + $8e6 = • Each license is awarded no more than once $30e6 Bid 1 2 3 4 5 6 7 8 Bid amt. $22e6 $12e6 $30e6 $16e6 $8e6 $11e6 $10e6 $7e6 Package ABD B ABC AD C BC A Example: 4 licenses, 8 bids 8 Max x A x1 B x1 + x3 + x2 BidAmt x1 b D Hard Computational Problem xb b 1 + x4 + x7 + x3 x3 C D $36e6 + x5 <= 1 + x6 <= 1 + x6 <= 1 <= 1 + x4 x b 0 ,1 + x8 for all bids (source: Hoffman) Combinatorial Auctions cont. • There exists a combinatorial auction mechanism (“Generalized Vickrey Auction”), which guarantees that the best each bidder can do is bid its true valuation for each bundle of items. (“Truth revealing”). • However, finding the optimal allocation to the bids is a hard computational problem. No guarantees that an optimal solution can be found in reasonable time. • What about a near-optimal solution? Does this matter? • Yes! Problem: if the auctioneer cannot compute the optimal allocation, no guarantee for truthful bidding. Beyond Traditional Scheduling Applications Enforcing Safety Constraints Nuclear Power Plant Outage Management [ Gomes et al, 1996, 1997, 1998 ] ACTIVITY SCHEDULE Activity Name EST LST Duration Predecessors impacts impacts ROME LABORATORY OUTAGE MANAGER (ROMAN) Parameters Parameters Load Load RunRun Gantt Gantt Charts Charts Utilities Utilities Exit Exit Name: D21-1 Affects: ACPLOSS DIV1 Predecessors EST: 65 LST: 65 DURATION: 15 START: 65 FINISH: 80 PECO ROME LABORATORY OUTAGE MANAGER (ROMAN) Parameters Parameters Load Load RunRun Gantt Gantt Charts Charts Utilities Utilities ExitExit Name: D21-1 Affects: ACPLOSS DIV1 Predecessors EST: 65 LST: 65 DURATION: 15 START: 65 FINISH: 80 PECO 0 10 20 30 40 50 60 80 90 100 110 120 D23-3 70 RHRB-1 D23-2 D21BUS-1 DIV4DC-1 0 10 20 30 40 50 60 70 80 90 100 110 RHR D21-1 A-1 D23-3 RHRB-1 D23-2 D21BUS-1 DIV4DC-1 RHRA-1 D21-1 impacts ROME LABORATORY OUTAGE MANAGER (ROMAN) STATE-Of-PLANT Parameters Parameters Load Load RunRun Gantt Gantt Charts Charts Utilities Utilities Exit Exit 31 - 45: ACPOWER? 0 NUM-UNAV-RESS 1 UNAV-RES-MAP (DIV2 D24BUS-3 D24-2 D24-1) (ACPLOSS D24BUS-3 D24-2 D24-1) LIST-AV-RESS (DIV1 DIV3 DIV4 SU10 SU20) 0 10 20 30 40 50 60 70 80 90 100 110 AC-POWER Status AC Power DIV1 DIV2 DIV3 DIV4 SU10 SU20 Given: •activities for refueling and maintenance •resources •technological constraints Find a schedule that minimizes the duration of the outage while safely performing all the activities (up to 45,000 activities). Cost of shutdown - $1M per day. Main risk The residual heat produced by the nuclear materials can melt the fuel and breach the reactor nvessel Examples of Monitored Safety Systems •ac power control system •primary containment system •shutdown cooling system Limitations of Traditional Approaches Rely heavily on manual procedures; Current procedures – PERT/CPM Outage Risk Assessment Methodology, simulation performed to assess the risks inherent to a schedule. Nuclear Power Plant Outage Management Example of decision tree for a safety function for AC-Power Activity with AC Power loss Potential? no 2 Offsite sources available yes Operable emergency Safeguard bus Operable emergency Safeguard bus 1 (…) ROME LABORATORY OUTAGE MANAGER (ROMAN) Parameters Parameters Load Load Run Run GanttGantt Charts ChartsUtilities Utilities ExitExit Name: D21-1 Affects: ACPLOSS DIV1 Predecessors EST: 65 LST: 65 DURATION: 15 START: 65 FINISH: 80 PECO 0 10 20 30 40 50 60 70 80 90 100 110 >3 2 1 0 Safety threshold >3 2 1 Time Roman extends the functionality of traditional project management tools D23-3 RHRB-1 • It incorporates the technological constraints, automatically enforcing safety constraints D23-2 D21BUS-1 DIV4DC-1 RHRA-1 D21-1 ROME LABORATORY OUTAGE MANAGER (ROMAN) Parameters Parameters Load Load Run Run GanttGantt Charts ChartsUtilities Utilities ExitExit 31 - 45: ACPOWER? 0 NUM-UNAV-RESS 1 UNAV-RES-MAP (DIV2 D24BUS-3 D24-2 D24-1) (ACPLOSS D24BUS-3 D24-2 D24-1) LIST-AV-RESS (DIV1 DIV3 DIV4 SU10 SU20) 0 AC-POWER Status AC Power DIV1 DIV2 DIV3 DIV4 SU10 SU20 10 20 30 40 50 60 70 80 90 100 110 • Robust schedules guaranteeing feasibility over time-windows • Fast schedules • Solutions better than manual solutions Syllabus 412 • Linear Programming – Introduction – Simplex/Revised Simplex – Duality and Sensitivity Analysis – Other LP Algorithms • Network Models – Transportation Problems – Assignment Problems – Network Optimization Models • Special Topics(*) – Integer Programming – Dynamic Programming – Heuristic techniques • • • • Simulated Annealing Genetic Algorithms Tabu Search Neural Networks – Computational complexity(*) (*)time permitting Goals in 412 – Present a variety of models, algorithms, and tools for optimization – Illustrate applications in business and economics, and other fields. – Prepare students to recognize opportunities for mathematical optimization as they arise – Prepare students to be aware of computational complexity issues: importance of using efficient algorithms whenever possible and the limits of computation that can affect the validity of business and economic models.

Descargar
# Document