所需积分/C币:9 2019-09-16 07:56:46 2.76MB PDF
收藏 收藏

Contents Chapter 1: Introduction mmmm RBRRRRREERREERIRIE 1. 1 What is this book about? 1.2 Features of the text 1.2.1 Running the Models 1.2.2 A Note on notation 113566 1.3 Getting Our Feet Wet: Amphibian Coexistence Chapter 2: Linear Continuous Models mmmammammmmmmmmmmmmmmma 19 2.1 Mixing…..,,,,,,,,………20 2.1.1 Constructing a model 2 2.1.2 Variati0nS…26 2.1.3 Structure of the problems Under consideration n28 2.2 Blending 30 2.2.1 Constructing a Model 32 2.2.2 Variations…136 2.3 Project Management. 2.3.1 Constructing a model 2.3.2 Variations…43 2.4 Multi-Stage Models 45 2.4.1 Problem Instance 2.4.2 Constructing a Model 48 24.3 Variations 54 2.5 Pattern Classification mmmmmmmm. 57 25.1 Constructing a Model....…………58 2.5.2 Executable Model. m.m.m....m.60 Chapter 3: Hidden Linear continuous Models.amma mama. 63 3.1 Piecewise linear 65 3.1. 1 Constructing a Model mamnammnmnannamnnnannnmn 66 3.1.2 Variations, mm,70 3.2 Curve Fittingmmmm. 3.2. 1 Constructing a Model 78 3.2.2 Variati0nS…84 3.3 Pattern Classification Revisited mmm. 85 3.3.1 Executable Model 87 Chapter 4: Linear Network Models mmaa 89 4.1 Maximum flow 90 41.1 Constructing a Model….,.,…91 4.1.2 Decision variables m...m. 92 4.1.3 Variations mm 98 42 Minimum cost flow,…99 4.2.1 Constructing a Model.mmmmmmmmmmmmmmmmmm.100 4.2.2 Variations 105 4.3 Transshipment.mmmemmmnannmmmmnmemmmmmmmmmmnmmmmnnnn 106 4.3. 1 Constructing a Model 4.3.2 Variations… 112 4. 4 Shortest paths, 4.4.1 Constructing a Model mmmmmmmmmmmmmmmmmm. 114 4.4.2 Alternate Algorithms 118 4.4.3 Variations 118 Chapter5: Classic Discrete models…m,,,,,,,…,…,,,125 5.1 Minimum set covers. 126 5.1. 1 Constructing a Model 5.1.2 Variati0nS灬…133 5.2 Set Packing 134 5.2.1 Constructing a Model mn 135 5.2.2 Variations…137 53 Bin Packing…,,,137 5. 3. 1 Constructing a Model 139 5.4TSP,,, …150 5.4.1 Constructing a Model mmmmmmannnnannnmnn 151 5.4.2 Variations… ,157 Chapter 6: Classic Mixed Models mmmmaammmmmmmmmmammn 161 6. 1 Facility Location 161 6.1.1 Constructing a Model.. 163 6.1.2 Variations 167 6.2 Multi-Commodity Flow 168 6.2. 1 Constructing a Model..m. 169 6.2.2 Variation. 6.2.3 Instances 176 6.3 Staffing Level.….......,..176 6.3. 1 Constructing a model ,179 6.3.2 Variations 184 6.4 Job Shop Scheduling 6.4.1 Constructing a Model .mmmmmmmmm...mmmmmmm. 185 Chapter 7: Advanced Techniques. ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■口■■■■■■■■■■■口■■■■■口m 191 7.1 Cutting stock 191 7.1.1 Constructing a Model...mmmmmmm 193 7.1.2 Pre-Allocate Cutting Patterns. 7.2Non- Convex Trickery…… 205 7.2.1 Selecting k Variables Out of n to Be Non-Zero............ 208 7.2.2 Selecting k Adjacent Variables Out of n to Be 7.2.3 Selecting k Constraints Out of n.……………215 7.2.4MaxmaXandMinmn…221 7. 3 Staff Scheduling 7.3. 1 Constructing a Model 227 7.3.2 Variations……233 7. 4 Sports Timetabling . mnanmnmmmnnmemmemmeanmmmnmmmmnmnmammnn 234 7.4.1 Constructing a Model 234 7.4.2 Variations. .245 7.5 Puzzles…245 7.5.1 Pseudo-Chess problems. m246 7.5.2 Sudoku 251 7.5.3 Send More Money!…,… 254 7.5.4 Ladies and tigers ....mmm...mmmmmmmmmmmmmmmmm. 257 7.6 Quick Reference for OR-Tools MPSolver in python.mee..s. 263 Index…u271 Introduction 1.1 What is this book about? Artificial intelligence is a wide field covering diverse techniques objectives, and measures of success. One branch is concerned with finding provably optimal solutions to some well-defined problems This book is an introduction to the art and science of implementing mathematical models of optimization problems An optimization problem is almost any problem that is, or can be formulated as a question starting with"What is the best. For instance What is the best route to get from home to work? What is the best way to produce cars to maximize p ofit? What is the best way to carry groceries home: paper or plastic? Which is the best school for my kid? Which is the best fuel to use in rocket boosters What is the best placement of transistors on a chip? What is the best nba schedule? CHAPTER 1 NTRODUCTION These questions are rather vague and can be interpreted in a multitude of ways. Consider the first: by"best"do we mean fastest, shortest, most pleasant to ride, least bumpy, or least fuel-guzzling Besides, the question is incomplete. Are we walking, riding, driving, or snowboarding? Are we alone or accompanied by a screaming toddler? To help us formulate solutions to optimization problems, optimizers have established a frame into which we mould the questions; it's called a model. The most crucial aspect of a model is that it has an objective and it has constraints. Roughly, the objective is what we want and the constraints are the obstacles in our way. If we can reformulate the question to clearly identify both the objective and the constraints we are closer to a model Let's consider in more detail the"best route" problem but with an eve to clarify objective and constraints. We could formulate it as Given a map of the city, my home address, and the address of the daycare of my two-year-old son, what is the best route to take on my bike to bring him to daycare as fast as possible? The goal is to find among all the solutions that satisfy the requirements (that is, paths following either streets or bike lanes, also known as the constraints)one path that minimizes the time it takes to get there(the objective) Objectives are always quantities we want to maximize or minimize (time, distance, money, surface area, etc. ) although you will see examples where we want to maximize something and minimize something else this is easily accommodated. Sometimes there are no objectives. We say I use the term"optimizers"to name the mathematicians, theoreticians, and practitioners, who, since the nineteen-fifties, have worked in the fields of linear programming(Lp) and integer programming(Ip). There are others who could make valid claims to the moniker, chiefly among them researchers in constraint programming but my focus will be mostly in LP andIP models, hence my restricted definition CHAPTER 1 INTRODUCTION that the problem is one of feasibility (i. e. we are looking for any solution satisfying the requirements). From the point of view of the modeler, the difference is minimal. Especially since, in most practical cases, a feasibility model is usually a first step. After noticing a solution, one usually wants to optimize something and the model is modified to include an objective function 1.2 Features of the text As this text is an introduction, I do not expect the reader to be already well versed in the art of modeling I will start at the beginning, assuming only that the reader understands the definition of a variable (both in the mathematical sense and in the programming sense), an equation, an inequality and a function i will also assume that the reader knows some programming language, preferably Python, although knowing any other imperative language is enough to be able to read the python code displayed in the text Note that the code in this book is an essential component To get the full value, the reader must, slowly and attentively, read the code. This book is not a text of recipes described from a birds-eye view, using mathematical notation,with all the nitty-gritty details "left as an exercise for the reader This is implemented, functional, tested, optimization code that the reader can use and moreover is encouraged to modify to fully understand The mathematics in the book has been reviewed by mathematicians like any mathematical paper. But the code has been subjected to a much more stringent set of reviewers with names Intel, AMD, Motorola, and IBM. 2 My doctoral advisor used to say"There are error-free mathematical papers. But we only have found an existence proof of that theorem. I will not claim that the code is error-free, but I am certain that it has fewer errors than any mathematical paper I ever wrote. CHAPTER 1 INTRODUCTION The book is the fruit of decades of consulting and of years teaching both an introductory modeling class(MOr242 Intro to Operation Research Models)and a graduate class(APM568 Mathematical Modeling in Industry)at Oakland University. I start at the undergraduate level and proceed up to the graduate level in terms of modeling itself, without delving much into the attendant theory Every model is expressed in Python using Google OR-Tools3 and can be executed as stated. In fact, the code presented in the book is automatically extracted, executed, and the output inserted into the text without manual intervention; even the graphs are produced automatically (thanks to Emacs and org-mode) My intention is to help the reader become a proficient modeler, not a theoretician. Therefore, little of the fascinating mathematical theory related to optimization is covered. It is nevertheless used profitably to create simple yet efficient models The associated web site provides all the code presented in the book along with a random generator for many of the problems and variations. The author uses this as a personalized homework generator. It can also be used as a self-guided learning tool s leoneandonlyeditor 5

试读 127P Practical-Python-AI-Projects-Mathematical-Models-of-Optimization-Problems-with-Google-OR-Tools.pdf.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    • 至尊王者


    关注 私信 TA的资源

    Practical-Python-AI-Projects-Mathematical-Models-of-Optimization-Problems-with-Google-OR-Tools.pdf.pdf 9积分/C币 立即下载


    9积分/C币 立即下载 >