WIXLIB

Optimization Modelingwith Spreadsheets

OptimizationModeling withSpreadsheetsThird EditionKenneth R. Baker

Copyright 2016 by John Wiley & Sons, Inc. All rights reservedPublished by John Wiley & Sons, Inc., Hoboken, New JerseyPublished simultaneously in CanadaNo part of this publication may be reproduced, stored in a retrieval system, or transmitted in any formor by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except aspermitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the priorwritten permission of the Publisher, or authorization through payment of the appropriate per‐copy fee tothe Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750‐8400, fax(978) 750‐4470, or on the web at www.copyright.com. Requests to the Publisher for permission shouldbe addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken,NJ 07030, (201) 748‐6011, fax (201) 748‐6008, or online at http://www.wiley.com/go/permissions.Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their bestefforts in preparing this book, they make no representations or warranties with respect to the accuracyor completeness of the contents of this book and specifically disclaim any implied warranties ofmerchantability or fitness for a particular purpose. No warranty may be created or extended by salesrepresentatives or written sales materials. The advice and strategies contained herein may not be suitablefor your situation. You should consult with a professional where appropriate. Neither the publisher norauthor shall be liable for any loss of profit or any other commercial damages, including but not limited tospecial, incidental, consequential, or other damages.For general information on our other products and services or for technical support, please contactour Customer Care Department within the United States at (800) 762‐2974, outside the United Statesat (317) 572‐3993 or fax (317) 572‐4002.Wiley also publishes its books in a variety of electronic formats. Some content that appears in print maynot be available in electronic formats. For more information about Wiley products, visit our web site atwww.wiley.com.Library of Congress Cataloging‐in‐Publication Data:Baker, Kenneth R., 1943–Optimization modeling with spreadsheets / Kenneth R. Baker. – Third Edition.pages cmIncludes bibliographical references and index.ISBN 978-1-118-93769-3 (hardback)1. Mathematical optimization. 2. Managerial economics–Mathematical models.3. Electronic spreadsheets. 4. Programming (Mathematics) I. Title.HB143.7.B35 2015005.54–dc232015011069Cover image courtesy of Kenneth R. BakerSet in 10/12pt Times by SPi Global, Pondicherry, IndiaPrinted in the United States of America1093201687654321

ContentsPreface ix12Introduction to Spreadsheet Models for Optimization11.1 Elements of a Model1.2 Spreadsheet Models1.3 A Hierarchy for Analysis1.4 Optimization Software1.5 Using SolverSummaryExercises2478101617Linear Programming: Allocation, Covering, and Blending 5Linear Models2.1.1 Linear Constraints2.1.2 Formulation2.1.3 Layout2.1.4 ResultsAllocation Models2.2.1 The Product Mix ProblemCovering Models2.3.1 The Staff-Scheduling ProblemBlending ModelsModeling Errors in Linear Programming2.5.1 Exceptions2.5.2 Debugging2.5.3 Logic

vi Contents3SummaryExercises5657Linear Programming: Network Models653.13.23.33.43.53.6The Transportation Model66The Assignment Model71The Transshipment Model75Features of Special Network Models78Building Network Models with Balance Equations79General Network Models with Yields843.6.1 Models with Yield Losses843.6.2 Models with Yield Gains863.7 General Network Models with Transformed Flows91Summary96Exercises 964 Sensitivity Analysis in Linear Programs1084.14.24.34.44.54.6Parameter Analysis in the Transportation Example109Parameter Analysis in the Allocation Example116The Sensitivity Report and the Transportation Example123The Sensitivity Report and the Allocation Example127Degeneracy and Alternative Optima129Patterns in Linear Programming Solutions1334.6.1 The Transportation Model1344.6.2 The Product Portfolio Model1384.6.3 The Investment Model1424.6.4 The Allocation Model1444.6.5 The Refinery Model145Summary149Exercises 1515Linear Programming: Data Envelopment Analysis1605.1 A Graphical Perspective on DEA1625.2 An Algebraic Perspective on DEA1665.3 A Spreadsheet Model for DEA1685.4 Indexing1735.5 Reference Sets and HCUs1745.6 Assumptions and Limitations of DEA178Summary181Exercises 1816Integer Programming: Binary‐Choice Models1916.1 Using Solver with Integer Requirements6.2 The Capital Budgeting Problem193198

Contents vii6.3 Set Covering2026.4 Set Packing2056.5 Set Partitioning2086.6 Playoff Scheduling2116.7 The Algorithm for Solving Integer Programs215Summary220Exercises 2207Integer Programming: Logical Constraints2277.17.27.37.4Simple Logical Constraints: Exclusivity229Linking Constraints: The Fixed Cost Problem231Linking Constraints: The Threshold Level Problem237Linking Constraints: The Facility Location Model2387.4.1 Capacitated Version2397.4.2 Uncapacitated Version2437.5 Disjunctive Constraints: The Machine‐Sequencing Problem2467.6 Tour Constraints: The Traveling Salesperson Problem251Summary259Exercises 2608 Nonlinear Programming2708.1One‐Variable Models2718.1.1 An Inventory Example2738.1.2 A Quantity Discount Example2758.2 Local Optima and the Search for an Optimum2778.3 Two‐Variable Models2808.3.1 Curve Fitting2808.3.2 Two‐Dimensional Location2838.4 Nonlinear Models with Constraints2858.4.1 A Pricing Example2868.4.2 Sensitivity Analysis for Nonlinear Programs2888.4.3 The Portfolio Optimization Model2908.5 Linearizations2938.5.1 Linearizing the Maximum2948.5.2 Linearizing the Absolute Value296Summary299Exercises 3019Heuristic Solutions with the Evolutionary Solver3079.19.29.39.49.5308309317319322Features of the Evolutionary SolverAn Illustrative Example: Nonlinear RegressionThe Machine‐Sequencing Problem RevisitedThe Traveling Salesperson Problem RevisitedBudget Allocation

viii Contents9.6 Two‐Dimensional Location3249.7 Line Balancing3279.8 Group Assignment331Summary334Exercises 336Appendices1 Supplemental Files and Software348A1.1 Supplemental Microsoft Office Excel FilesA1.2 Analytic Solver Platform for Education SoftwareA1.3 Opensolver Software348348349Graphical Methods for Linear Programming350A2.1 An ExampleA2.2 Generalities3503553 The Simplex Method3572A3.1 An ExampleA3.2 Variations of the Algorithm357362Index 366

PREFACEThis is an introductory textbook on optimization—that is, on mathematicalprogramming—intended for undergraduates and graduate students in managementor in engineering. The principal coverage includes linear programming, nonlinearprogramming, integer programming, and heuristic programming; and the emphasisis on model building using Microsoft Office Excel and Solver.The emphasis on model building (rather than algorithms) is one of the featuresthat make this book distinctive. Most textbooks devote more space to algorithmicdetails than to formulation principles. These days, however, it is not necessary toknow a great deal about algorithms in order to apply optimization tools, especiallywhen relying on the spreadsheet as a solution platform.The emphasis on spreadsheets is another feature that makes this book distinctive.Few textbooks devoted to optimization pay much attention to spreadsheet implementation of optimization principles, and many books that emphasize model buildingignore spreadsheets entirely. Thus, someone looking for a spreadsheet‐based treatmentwould otherwise have to use a textbook that was designed for some other purpose, suchas a survey of management science topics, rather than one devoted to optimization.WHY MODEL BUILDING?The model building emphasis derives from an attempt to be realistic about whatmanagement and engineering students need most when learning about optimization.At an introductory level, the most practical and motivating theme is the wide applicability of optimization tools. To apply optimization effectively, the student needs morethan a brief exposure to a series of numerical examples, which is the way that mostmathematical programming books treat applications. With a systematic modeling

x PREFACEemphasis, the student can begin to see the basic structures that appear in optimizationmodels and, as a result, develop an appreciation for potential applications well beyondthe examples in the text.Formulating optimization models is both an art and a science, and this book paysattention to both. The art can be refined with practice, especially supervised practice,just the way a student would learn sculpture or painting. The science is reflected in thestructure that organizes the topics in this book. For example, there are several distinctproblem types that lend themselves to linear programming formulations, and it makessense to study these types systematically. In that spirit, the book builds a library oftemplates against which new problems can be compared. Analogous structures aredeveloped for the presentation of other topics as well.WHY SPREADSHEETS?Now that optimization tools have been made available with spreadsheets (i.e., withExcel), every spreadsheet user is potentially a practitioner of optimization techniques.No longer do practitioners of optimization constitute an elite, highly trained group ofquantitative specialists who are well versed in computer software. Now, anyone whobuilds a spreadsheet model can call on optimization techniques and can do so withoutany need to learn about specialized software. The basic optimization tool, in the formof Excel’s Standard Solver, is now as readily available as the spell‐checker. So whynot raise modeling ability up to the level of software access? Let’s not pretend thatmost users of optimization tools will be inclined to shop around for algebraic modeling languages and industrial‐strength “solvers” if they want to produce numbers.More likely, they will be drawn to Excel.Students using this book can take advantage of even more powerful softwarepackages (Analytic Solver Platform and OpenSolver) by using the material in theonline appendices. For the instructor who wants students to be working on one ofthese platforms, the book provides sufficient information to get started and to learnthe user interface.WHAT’S SPECIAL?Mathematical programming techniques have been invented and applied for morethan half a century, so by now they represent a relatively mature area of appliedmathematics. There is not much new that can be said in an introductory textbookregarding the underlying concepts. The innovations in this book can instead be foundin the delivery and elaboration of certain topics, making them accessible and understandable to the novice. The most distinctive of these features are as follows: The major topics are not illustrated merely with a series of numerical examples.Instead, the chapters introduce a classification for the problem types. An earlyexample is the organization of basic linear programming models in Chapter 2along the lines of allocation, covering, and blending models. This classification