Transcription
Decision ModelingDavid M. TulettVersion 1.1The current version of this document is available for free download from:https://linney.mun.ca/pages/view.php?ref 36808
This page is intentionally left blank.
iVersion History1. Preliminary versions were developed over the period 2011-2018 for use inthe Faculty of Business Administration at Memorial University of Newfoundland.2. Version 1. The first version advertised through INFORMS and CORS wasmade in June 2018. Minor changes were made as follows:(a) Version 1.0.1. November 14, 2018.(b) Version 1.0.2. November 29, 2018.(c) Version 1.0.3. February 5, 2019.(d) Version 1.0.4. March 1, 2019.3. Version 1.1. Content on doing sensitivity analysis using LINGO was addedto Appendix A, the front-end of this document was re-designed, and someminor changes were made. This revision, compiled on July 24, 2019, is thecurrent version.
iiCC Licence, Trademarks, and AcknowledgementsCC LicenceThis work, created by David M. Tulett, is licensed to Memorial University ofNewfoundland, and is licensed to everyone else under the Creative CommonsAttribution-NonCommercial-NoDerivatives 4.0 International Licence. To view acopy of this licence, visit Registered TrademarksThe following trademarks are used in this document. Beyond this page, thesymbol is not shown.R1. Adobe R Acrobat R are registered trademarks of Adobe Systems Inc.2. Excel R and Windows R are registered trademarks of Microsoft.https://www.microsoft.com3. LINDO R and LINGO R are registered trademarks of LINDO Systems Inc.http://www.lindo.com4. Mac R and Macintosh R are registered trademarks of Apple Inc.https://www.apple.com/Acknowledgements1. This document was written using the very versatile LATEX and PSTricksprograms, which are open-source software. LATEX is particulary good at
iiiwriting mathematical expressions, and PSTricks produces excellent graphics. Both can be downloaded for free from the TEX Users Group (TUG) athttp://www.tug.org.2. A feature of Excel that is heavily used in this document is the Solver. TheSolver is made by Frontline Systems, Inc., https://www.solver.com.3. The author acknowledges suggestions and comments from many studentsand colleagues based on earlier editions of this document, which began in2011.4. The author wishes to thank retired professor Austin Redlack, Ph.D, withwhom he worked on materials for courses that were developed in the period1987-1997, and which continued to be used in courses that were offered upto 2011. In a few cases, examples from those works have been maintainedin this document.5. Since June of 2018 this document has been hosted on Memorial’s Linney.System. The author wishes to thank Ms Vanessa Mackey of Memorial University’s Centre for Innovation in Teaching and Learning (CITL) for uploading the numerous updates.6. The author thanks his wife Mary for her proofreading and support for thewriting of this document.AuthorDavid M. Tulett obtained a B.Sc. in mining engineering and a Ph.D in management (dual major in operational research and finance) from Queen’s University(Canada). He is member of the Faculty of Business Administration at MemorialUniversity, St. John’s, NL, Canada.
ivPrefaceThis e-book was developed for Business 2400 at Memorial University of Newfoundland, Canada. In June of 2018, this document was made available to theentire world through Memorial’s Linney system. From time to time changes tothis document will be made. These versions are listed on page i. This version wasmade on July 24, 2019.In this e-book, a word, phrase, or page number in red indicates a link to somewhere else in this document; a word or phrase in pink indicates a link to the web.In particular, both the Table of Contents and the Index are linked to the appropriateplaces in the main body of the material.The reader needs to have learnt, or be prepared to learn, the basics of spreadsheets. A quick overview of the basics of spreadsheet operations using the syntaxof Excel is provided in Chapter One. This e-book should be read in conjunctionwith any other materials which have been required for your course.A great deal of care has gone into the preparation of this document, but theremay well be some errors lurking somewhere. Readers who spot such errors, orwho simply want to offer suggestions for improvement, are encouraged to contactthe author by email.Each of the nine chapters ends with a section called Problems for StudentCompletion. The solutions for these problems (nine pdf files) may be obtainedfrom the author.David M. TulettEmail: dtulett@mun.ca
ContentsTitle Page . . . . . . . . . . . . . . . . . . . . .Version History . . . . . . . . . . . . . . . . . .CC Licence, Trademarks, and AcknowledgementsPreface . . . . . . . . . . . . . . . . . . . . . . .Contents . . . . . . . . . . . . . . . . . . . . . .1.Introduction1.1 A Paradigm for Problem Solving . . . . . . . . . . .1.2 Spreadsheets . . . . . . . . . . . . . . . . . . . . .1.2.1 Introduction . . . . . . . . . . . . . . . . . .1.2.2 Example – Calculating Students’ Final Marks1.2.3 Putting Excel files into other Documents . .1.2.4 Further Excel Functions . . . . . . . . . . .1.2.5 Excel Array Formulas . . . . . . . . . . . .1.3 Example – Mobile Telephone Plans . . . . . . . . .1.3.1 Problem Identification . . . . . . . . . . . .1.3.2 Model Solution . . . . . . . . . . . . . . . .1.4 Break-Even Analysis . . . . . . . . . . . . . . . . .1.5 Why Decision Modeling is Important . . . . . . . .1.5.1 Using Resources Efficiently . . . . . . . . .1.5.2 Professional Societies . . . . . . . . . . . .1.5.3 OR Applications and Awards . . . . . . . . .1.6 Problems for Student Completion . . . . . . . . . .1.6.1 Spreadsheet Formula Exercises . . . . . . .1.6.2 Phone Plans . . . . . . . . . . . . . . . . . .1.6.3 Cargo Plane Loading Problem . . . . . . . .v. 0.i. ii. v. xiv.11225101113171719232626282929293030.
vi2CONTENTSElementary Modeling2.1 Example – Cement Problem . . . . . . . . . . . . . . . . . . . .2.1.1 Problem Description . . . . . . . . . . . . . . . . . . . .2.1.2 Making a Model . . . . . . . . . . . . . . . . . . . . . .2.1.3 Plotting the Constraints . . . . . . . . . . . . . . . . . . .2.1.4 Finding the Feasible Region . . . . . . . . . . . . . . . .2.1.5 Plotting a Trial Isovalue Line . . . . . . . . . . . . . . . .2.1.6 Finding the Optimal Solution . . . . . . . . . . . . . . .2.1.7 Finding the Exact Solution . . . . . . . . . . . . . . . . .2.2 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2.1 General Form . . . . . . . . . . . . . . . . . . . . . . . .2.2.2 A Right-Hand Side Value of 0 . . . . . . . . . . . . . . .2.3 Cement Model with a Proportion Constraint . . . . . . . . . . . .2.3.1 A Revised Model . . . . . . . . . . . . . . . . . . . . . .2.3.2 A Right-Hand-Side Value of 0 . . . . . . . . . . . . . . .2.3.3 The Feasible Region . . . . . . . . . . . . . . . . . . . .2.3.4 Finding the Exact Solution . . . . . . . . . . . . . . . . .2.4 Example – Diet Problem . . . . . . . . . . . . . . . . . . . . . .2.4.1 Problem Description . . . . . . . . . . . . . . . . . . . .2.4.2 Formulation . . . . . . . . . . . . . . . . . . . . . . . . .2.4.3 Plotting the Constraints . . . . . . . . . . . . . . . . . . .2.4.4 Feasible Region, Isovalue Lines, and the Optimal Solution2.4.5 Finding the Exact Solution . . . . . . . . . . . . . . . . .2.5 Solution by Using the Excel Solver . . . . . . . . . . . . . . . . .2.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . .2.5.2 Optimization using Spreadsheets . . . . . . . . . . . . . .2.5.3 Slack and Surplus . . . . . . . . . . . . . . . . . . . . . .2.6 Model Variations with Three Variables (Optional) . . . . . . . . .2.6.1 Cement Problem . . . . . . . . . . . . . . . . . . . . . .2.6.2 Diet Model . . . . . . . . . . . . . . . . . . . . . . . . .2.7 Problems for Student Completion . . . . . . . . . . . . . . . . .2.7.1 Garment Problem . . . . . . . . . . . . . . . . . . . . . .2.7.2 Baseball Bat Problem . . . . . . . . . . . . . . . . . . . .2.7.3 Car-Assembly . . . . . . . . . . . . . . . . . . . . . . .2.7.4 Quarry Problem . . . . . . . . . . . . . . . . . . . . . . .2.7.5 Office Rental . . . . . . . . . . . . . . . . . . . . . . . .2.7.6 Diet Problem . . . . . . . . . . . . . . . . . . . . . . . 9697980808183838384848585
CONTENTS34Applications of Linear Models3.1 Blending . . . . . . . . . . . . . . . . . . . . .3.1.1 Background Information . . . . . . . .3.1.2 Problem Description . . . . . . . . . .3.1.3 Formulation . . . . . . . . . . . . . . .3.1.4 Solution Using the Excel Solver . . . .3.2 Scheduling . . . . . . . . . . . . . . . . . . .3.2.1 Scheduling of Police Constables . . . .3.2.2 Telephone Operator Problem (Optional)3.3 Production Planning Models . . . . . . . . . .3.3.1 A Simple Inventory Model . . . . . . .3.3.2 Formulation . . . . . . . . . . . . . . .3.3.3 Shortage Model . . . . . . . . . . . . .3.3.4 Production Level Change Model . . . .3.4 Cutting Stock Models . . . . . . . . . . . . . .3.4.1 Example 1 – Description . . . . . . . .3.4.2 Example 2 (Optional) . . . . . . . . . .3.5 Some Special Situations . . . . . . . . . . . .3.6 Summary . . . . . . . . . . . . . . . . . . . .3.7 Problems for Student Completion . . . . . . .3.7.1 Blending Gasoline . . . . . . . . . . .3.7.2 Blending Oil . . . . . . . . . . . . . .3.7.3 Scheduling of Restaurant Workers . . .3.7.4 An Irrigation Problem . . . . . . . . .3.7.5 Blending of Coffee . . . . . . . . . . .3.7.6 Scheduling of Bus Drivers . . . . . . .3.7.7 Production Planning 1 . . . . . . . . .3.7.8 Production Planning 2 . . . . . . . . .3.7.9 Production Planning 3 . . . . . . . . .3.7.10 Cutting Stock 1 . . . . . . . . . . . . .3.7.11 Cutting Stock 2 . . . . . . . . . . . . .3.8 More Difficult Problems . . . . . . . . . . . .3.8.1 Cutting Stock . . . . . . . . . . . . . .3.8.2 Production Planning . . . . . . . . . 1Sensitivity Analysis1534.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1534.2 Graphical Approach to Sensitivity Analysis . . . . . . . . . . . . 154
Problem Description . . . . . . . . . . . . . . . . . . . . 154Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154Graphical Solution . . . . . . . . . . . . . . . . . . . . . 155Changes to the Objective Function Coefficients . . . . . . 158Changes to the Right-Hand Side Values of the Non-BindingConstraints . . . . . . . . . . . . . . . . . . . . . . . . . 1614.2.6 Changes to the Right-Hand Side Values of the BindingConstraints . . . . . . . . . . . . . . . . . . . . . . . . . 163The Solver Sensitivity Report . . . . . . . . . . . . . . . . . . . . 1704.3.1 Wood Products Example . . . . . . . . . . . . . . . . . . 1704.3.2 Using the Sensitivity Report . . . . . . . . . . . . . . . . 1744.3.3 Example 1: Maximization . . . . . . . . . . . . . . . . . 1764.3.4 Example 2: Minimization . . . . . . . . . . . . . . . . . 181Two or More Changes . . . . . . . . . . . . . . . . . . . . . . . . 1874.4.1 Two Special Cases . . . . . . . . . . . . . . . . . . . . . 1874.4.2 General Case (Based on the Answer and Sensitivity Reports)1884.4.3 Using the 100% Rules – An Example . . . . . . . . . . . 190Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193Problems for Student Completion . . . . . . . . . . . . . . . . . 1944.6.1 Sensitivity Analysis by Graphing . . . . . . . . . . . . . 1944.6.2 A Maximization Problem . . . . . . . . . . . . . . . . . . 1954.6.3 A Minimization Problem . . . . . . . . . . . . . . . . . . 1964.6.4 Parametric Analysis . . . . . . . . . . . . . . . . . . . . 197Network Models5.1 Assignment Problem . . . . . . . . . . . . . . .5.1.1 Example: Assigning 3 Jobs to 3 Machines5.1.2 Assigning n Jobs to n Machines . . . . .5.1.3 Special Cases . . . . . . . . . . . . . . .5.2 Transportation Problem . . . . . . . . . . . . . .5.2.1 Transportation Example . . . . . . . . .5.2.2 Model Formulation . . . . . . . . . . . .5.2.3 General Model . . . . . . . . . . . . . .5.2.4 Solution . . . . . . . . . . . . . . . . . .5.2.5 A Modification to the Example . . . . . .5.3 Transshipment Problem . . . . . . . . . . . . . .5.4 Networks . . . . . . . . . . . . . . . . . . . . .5.4.1 Definition of Terms . . . . . . . . . . . .199199199203204205205205207208210211213214
CONTENTS5.55.65.75.85.96Minimum Spanning Tree Problem . . . . . . .5.5.1 An Example With Seven Nodes . . . .The Maximum Flow Problem . . . . . . . . . .5.6.1 The Algebraic Model . . . . . . . . . .5.6.2 Excel Model . . . . . . . . . . . . . .The Shortest Path Problem . . . . . . . . . . .5.7.1 LP Model and Excel Solution . . . . .Summary . . . . . . . . . . . . . . . . . . . .Problems for Student Completion . . . . . . .5.9.1 Assignment Problem . . . . . . . . . .5.9.2 Transportation/Transshipment Problem5.9.3 Minimum Spanning Tree . . . . . . . .5.9.4 Maximal Flow Problem . . . . . . . .5.9.5 Shortest Path Problem . . . . . . . . .ix.I
Content on doing sensitivity analysis using LINGO was added to Appendix A, the front-end of this document was re-designed, and some minor changes were made. This revision, compiled on July 24, 2019, is the current version. ii CC Licence, Trademarks, and Acknowledgements CC Licence This work, created by David M. Tulett, is licensed to Memorial University of Newfoundland, and is licensed to .
