Each student is required to design an efficient portfolio frontier consisting of at least four companies (each from a different S &P 500 sector) using historical annual return data over the last fifteen years. A brief discussion of why the student selected the specific sectors and a specific company within that sector must be included in the assignment. Chapter 8 of Ragsdale shows a step by step approach for building the portfolio and drawing the efficient frontier diagram using Excel Solver.

Each student must only a single Word document for this assignment.

The attached file is the PDF of the reference book and the link will help you to learn about S&P sectors

https://corporatefinanceinstitute.com/resources/kn…

; and you can find historical annual return data from

https://finance.yahoo.com/quote/AAPL/history

; and the analysis template for AAPL is shown in the screenshot.

Cliff T.

Ragsdale

Spreadsheet Modeling

& Decision Analysis 5e

REVISED

A Practical Introduction to Management Science

Contents

1. Introduction to Modeling and Decision Analysis 1

Introduction 1

The Modeling Approach to Decision Making 3

Characteristics and Benefits of Modeling 3

Mathematical Models 4

Categories of Mathematical Models 6

The Problem-Solving Process 7

Anchoring and Framing Effects 9

Good Decisions vs. Good Outcomes 11

Summary 11

References 12

The World of Management Science 12

Questions and Problems 14

Case 14

2. Introduction to Optimization and Linear Programming 17

Introduction 17

Applications of Mathematical Optimization 17

Characteristics of Optimization Problems 18

Expressing Optimization Problems Mathematically 19

Decisions 19

Constraints 19

Objective 20

Mathematical Programming Techniques 20

An Example LP Problem 21

Formulating LP Models 21

Steps in Formulating an LP Model 21

Summary of the LP Model for the Example Problem 23

The General Form of an LP Model 23

Solving LP Problems: An Intuitive Approach 24

Solving LP Problems: A Graphical Approach 25

Plotting the First Constraint 26 Plotting the Second Constraint 26 Plotting the Third

Constraint 27 The Feasible Region 28 Plotting the Objective Function 29 Finding the

Optimal Solution Using Level Curves 30 Finding the Optimal Solution by Enumerating

the Corner Points 32 Summary of Graphical Solution to LP Problems 32

Understanding How Things Change 33

Special Conditions in LP Models 34

Alternate Optimal Solutions 34

Infeasibility 38

Summary 39

viii

Redundant Constraints 35

Unbounded Solutions 37

Contents

ix

References 39

Questions and Problems 39

Case 44

3. Modeling and Solving LP Problems in a Spreadsheet 45

Introduction 45

Spreadsheet Solvers 45

Solving LP Problems in a Spreadsheet 46

The Steps in Implementing an LP Model in a Spreadsheet 46

A Spreadsheet Model for the Blue Ridge Hot Tubs Problem 48

Organizing the Data 49 Representing the Decision Variables 49 Representing the

Objective Function 49 Representing the Constraints 50 Representing the Bounds on the

Decision Variables 50

How Solver Views the Model 51

Using Solver 53

Deï¬ning the Set (or Target) Cell 54 Deï¬ning the Variable Cells 56 Deï¬ning the

Constraint Cells 56 Deï¬ning the Nonnegativity Conditions 58 Reviewing the Model 59

Options 59 Solving the Model 59

Goals and Guidelines for Spreadsheet Design 61

Make vs. Buy Decisions 63

Deï¬ning the Decision Variables 63 Deï¬ning the Objective Function 64 Deï¬ning the

Constraints 64 Implementing the Model 64 Solving the Model 66 Analyzing the

Solution 66

An Investment Problem 67

Deï¬ning the Decision Variables 68 Deï¬ning the Objective Function 68 Deï¬ning the

Constraints 69 Implementing the Model 69 Solving the Model 71 Analyzing the

Solution 72

A Transportation Problem 72

Deï¬ning the Decision Variables 72 Deï¬ning the Objective Function 73 Deï¬ning the

Constraints 73 Implementing the Model 74 Heuristic Solution for the Model 76

Solving the Model 76 Analyzing the Solution 77

A Blending Problem 78

Deï¬ning the Decision Variables 79 Deï¬ning the Objective Function 79 Deï¬ning the

Constraints 79 Some Observations About Constraints, Reporting, and Scaling 80

Rescaling the Model 81 Implementing the Model 82 Solving the Model 83 Analyzing

the Solution 84

A Production and Inventory Planning Problem 85

Deï¬ning the Decision Variables 85 Deï¬ning the Objective Function 86 Deï¬ning the

Constraints 86 Implementing the Model 87 Solving the Model 89 Analyzing the

Solution 90

A Multi-Period Cash Flow Problem 91

Deï¬ning the Decision Variables 91 Deï¬ning the Objective Function 92 Deï¬ning the

Constraints 92 Implementing the Model 94 Solving the Model 96 Analyzing the

Solution 96 Modifying The Taco-Viva Problem to Account for Risk (Optional) 98

Implementing the Risk Constraints 100 Solving the Model 101 Analyzing the

Solution 102

x

Contents

Data Envelopment Analysis 102

Deï¬ning the Decision Variables 103 Deï¬ning the Objective 103 Deï¬ning the constraints

103 Implementing the Model 104 Solving the Model 106 Analyzing the Solution 111

Summary 112

References 113

The World of Management Science 113

Questions and Problems 114

Cases 130

4. Sensitivity Analysis and the Simplex Method 136

Introduction 136

The Purpose of Sensitivity Analysis 136

Approaches to Sensitivity Analysis 137

An Example Problem 137

The Answer Report 138

The Sensitivity Report 140

Changes in the Objective Function Coefï¬cients 140

A Note About Constancy 142 Alternate Optimal Solutions 143 Changes in the RHS

Values 143 Shadow Prices for Nonbinding Constraints 144 A Note About Shadow

Prices 144 Shadow Prices and the Value of Additional Resources 146 Other Uses of

Shadow Prices 146 The Meaning of the Reduced Costs 147 Analyzing Changes in

Constraint Coefï¬cients 149 Simultaneous Changes in Objective Function Coefï¬cients 150

A Warning About Degeneracy 151

The Limits Report 151

The Sensitivity Assistant Add-in (Optional) 152

Creating Spider Tables and Plots 153

Creating a Solver Table 155

Comments 158

The Simplex Method (Optional) 158

Creating Equality Constraints Using Slack Variables 158

Finding the Best Solution 162

Basic Feasible Solutions 159

Summary 162

References 162

The World of Management Science 163

Questions and Problems 164

Cases 171

5. Network Modeling 177

Introduction 177

The Transshipment Problem 177

Characteristics of Network Flow Problems 177 The Decision Variables for Network Flow

Problems 179 The Objective Function for Network Flow Problems 179 The Constraints

for Network Flow Problems 180 Implementing the Model in a Spreadsheet 181

Analyzing the Solution 182

The Shortest Path Problem 184

An LP Model for the Example Problem 186 The Spreadsheet Model and Solution 186

Network Flow Models and Integer Solutions 188

Contents

The Equipment Replacement Problem 189

The Spreadsheet Model and Solution 190

Transportation/Assignment Problems 193

Generalized Network Flow Problems 194

Formulating an LP Model for the Recycling Problem 195 Implementing the Model 196

Analyzing the Solution 198 Generalized Network Flow Problems and Feasibility 199

Maximal Flow Problems 201

An Example of a Maximal Flow Problem 201

The Spreadsheet Model and Solution 203

Special Modeling Considerations 205

Minimal Spanning Tree Problems 208

An Algorithm for the Minimal Spanning Tree Problem 209

Problem 209

Solving the Example

Summary 210

References 210

The World of Management Science 211

Questions and Problems 212

Cases 227

6. Integer Linear Programming 232

Introduction 232

Integrality Conditions 232

Relaxation 233

Solving the Relaxed Problem 233

Bounds 235

Rounding 236

Stopping Rules 239

Solving ILP Problems Using Solver 240

Other ILP Problems 243

An Employee Scheduling Problem 243

Deï¬ning the Decision Variables 244 Deï¬ning the Objective Function 245 Deï¬ning the

Constraints 245 A Note About the Constraints 245 Implementing the Model 246

Solving the Model 247 Analyzing the Solution 247

Binary Variables 248

A Capital Budgeting Problem 249

Deï¬ning the Decision Variables 249 Deï¬ning the Objective Function 250 Deï¬ning the

Constraints 250 Setting Up the Binary Variables 250 Implementing the Model 250

Solving the Model 251 Comparing the Optimal Solution to a Heuristic Solution 253

Binary Variables and Logical Conditions 253

The Fixed-Charge Problem 254

Deï¬ning the Decision Variables 255 Deï¬ning the Objective Function 255 Deï¬ning the

Constraints 256 Determining Values for â€œBig Mâ€ 256 Implementing the Model 257

Solving the Model 259 Analyzing the Solution 260

Minimum Order/Purchase Size 261

Quantity Discounts 261

Formulating the Model 262

The Missing Constraints 262

xi

xii

Contents

A Contract Award Problem 262

Formulating the Model: The Objective Function and Transportation Constraints 263

Implementing the Transportation Constraints 264 Formulating the Model: The Side

Constraints 265 Implementing the Side Constraints 266 Solving the Model 267

Analyzing the Solution 268

The Branch-and-Bound Algorithm (Optional) 268

Branching 269 Bounding 272

of B&B Example 274

Branching Again 272

Bounding Again 272

Summary

Summary 274

References 275

The World of Management Science 276

Questions and Problems 276

Cases 291

7. Goal Programming and Multiple Objective Optimization 296

Introduction 296

Goal Programming 296

A Goal Programming Example 297

Deï¬ning the Decision Variables 298 Deï¬ning the Goals 298 Deï¬ning the Goal

Constraints 298 Deï¬ning the Hard Constraints 299 GP Objective Functions 300

Deï¬ning the Objective 301 Implementing the Model 302 Solving the Model 303

Analyzing the Solution 303 Revising the Model 304 Trade-offs: The Nature of GP 305

Comments about Goal Programming 307

Multiple Objective Optimization 307

An MOLP Example 309

Deï¬ning the Decision Variables 309 Deï¬ning the Objectives 310 Deï¬ning the

Constraints 310 Implementing the Model 310 Determining Target Values for the

Objectives 311 Summarizing the Target Solutions 313 Determining a GP Objective 314

The MINIMAX Objective 316 Implementing the Revised Model 317

Solving the Model 318

Comments on MOLP 320

Summary 321

References 321

The World of Management Science 321

Questions and Problems 322

Cases 334

8. Nonlinear Programming & Evolutionary Optimization 339

Introduction 339

The Nature of NLP Problems 339

Solution Strategies for NLP Problems 341

Local vs. Global Optimal Solutions 342

Economic Order Quantity Models 344

Contents

Implementing the Model 347 Solving the Model 348

Comments on the EOQ Model 349

xiii

Analyzing the Solution 349

Location Problems 350

Deï¬ning the Decision Variables 351 Deï¬ning the Objective 351 Deï¬ning the

Constraints 352 Implementing the Model 352 Solving the Model and Analyzing the

Solution 353 Another Solution to the Problem 354 Some Comments About the Solution

to Location Problems 354

Nonlinear Network Flow Problem 355

Deï¬ning the Decision Variables 356 Deï¬ning the Objective 356 Deï¬ning the

Constraints 357 Implementing the Model 357 Solving the Model and Analyzing

the Solution 360

Project Selection Problems 360

Deï¬ning the Decision Variables 361 Deï¬ning the Objective Function 361 Deï¬ning

the Constraints 362 Implementing the Model 362 Solving the Model 364

Optimizing Existing Financial Spreadsheet Models 365

Implementing the Model 365 Optimizing the Spreadsheet Model 367 Analyzing

the Solution 368 Comments on Optimizing Existing Spreadsheets 368

The Portfolio Selection Problem 368

Deï¬ning the Decision Variables 370 Deï¬ning the Objective 370 Deï¬ning the

Constraints 371 Implementing the Model 371 Analyzing the Solution 373

Handling Conï¬‚icting Objectives in Portfolio Problems 374

Sensitivity Analysis 376

Lagrange Multipliers 378

Reduced Gradients 379

Solver Options for Solving NLPs 379

Evolutionary Algorithms 380

Beating the Market 382

A Spreadsheet Model for the Problem 382

Solution 384

Solving the Model 383

Analyzing the

The Traveling Salesperson Problem 385

A Spreadsheet Model for the Problem 386

Solution 387

Solving the Model 387

Summary 389

References 389

The World of Management Science 389

Questions and Problems 390

Cases 404

9. Regression Analysis 409

Introduction 409

An Example 409

Regression Models 411

Simple Linear Regression Analysis 412

Defining â€œBest Fitâ€ 413

Solving the Problem Using Solver 414

Solving the Problem Using the Regression Tool 417

Evaluating the Fit 419

Analyzing the

xiv

Contents

The R2 Statistic 421

Making Predictions 422

The Standard Error 423 Prediction Intervals for New Values of Y 423

Intervals for Mean Values of Y 425 A Note About Extrapolation 426

Conï¬dence

Statistical Tests for Population Parameters 426

Analysis of Variance 427

Statistical Tests 430

Assumptions for the Statistical Tests 427

A Note About

Introduction to Multiple Regression 430

A Multiple Regression Example 431

Selecting the Model 433

Models with One Independent Variable 433 Models with Two Independent Variables

434 Inï¬‚ating R2 436 The Adjusted-R2 Statistic 437 The Best Model with Two

Independent Variables 437 Multicollinearity 437 The Model with Three Independent

Variables 438

Making Predictions 439

Binary Independent Variables 440

Statistical Tests for the Population Parameters 440

Polynomial Regression 441

Expressing Nonlinear Relationships Using Linear Models 442

Regression 446

Summary of Nonlinear

Summary 446

References 447

The World of Management Science 447

Questions and Problems 448

Cases 454

10. Discriminant Analysis 459

Introduction 459

The Two-Group DA Problem 460

Group Locations and Centroids 460 Calculating Discriminant Scores 461 The

Classiï¬cation Rule 465 Reï¬ning the Cutoff Value 466 Classiï¬cation Accuracy 467

Classifying New Employees 468

The k-Group DA Problem 469

Multiple Discriminant Analysis 471

Distance Measures 472

Summary 477

References 477

The World of Management Science 478

Questions and Problems 478

Cases 481

11. Time Series Forecasting 485

Introduction 485

Time Series Methods 486

Measuring Accuracy 486

Stationary Models 487

MDA Classiï¬cation 474

Contents

Moving Averages 488

Forecasting with the Moving Average Model 490

Weighted Moving Averages 492

Forecasting with the Weighted Moving Average Model 493

Exponential Smoothing 494

Forecasting with the Exponential Smoothing Model 496

Seasonality 498

Stationary Data with Additive Seasonal Effects 500

Forecasting with the Model 502

Stationary Data with Multiplicative Seasonal Effects 504

Forecasting with the Model 507

Trend Models 507

An Example 507

Double Moving Average 508

Forecasting with the Model 510

Double Exponential Smoothing (Holtâ€™s Method) 511

Forecasting with Holtâ€™s Method 513

Holt-Winterâ€™s Method for Additive Seasonal Effects 514

Forecasting with Holt-Winterâ€™s Additive Method 517

Holt-Winterâ€™s Method for Multiplicative Seasonal Effects 518

Forecasting with Holt-Winterâ€™s Multiplicative Method 521

Modeling Time Series Trends Using Regression 522

Linear Trend Model 523

Forecasting with the Linear Trend Model 525

Quadratic Trend Model 526

Forecasting with the Quadratic Trend Model 528

Modeling Seasonality with Regression Models 528

Adjusting Trend Predictions with Seasonal Indices 529

Computing Seasonal Indices 530

Seasonal Indices 532

Forecasting with Seasonal Indices 531

Reï¬ning the

Seasonal Regression Models 534

The Seasonal Model 535

Forecasting with the Seasonal Regression Model 536

Crystal Ball Predictor 538

Using CB Predictor 538

Combining Forecasts 544

Summary 544

References 545

The World of Management Science 545

Questions and Problems 546

Cases 554

12. Introduction to Simulation Using Crystal Ball 559

Introduction 559

Random Variables and Risk 559

xv

xvi

Contents

Why Analyze Risk? 560

Methods of Risk Analysis 560

Best-Case/Worst-Case Analysis 561

What-If Analysis 562

Simulation 562

A Corporate Health Insurance Example 563

A Critique of the Base Case Model 565

Spreadsheet Simulation Using Crystal Ball 565

Starting Crystal Ball 566

Random Number Generators 566

Discrete vs. Continuous Random Variables 569

Preparing the Model for Simulation 570

Deï¬ning Assumptions for the Number of Covered Employees 572 Deï¬ning

Assumptions for the Average Monthly Claim per Employee 574 Deï¬ning Assumptions

for the Average Monthly Claim per Employee 575

Running the Simulation 576

Selecting the Output Cells to Track 576 Selecting the Number of Iterations 577

Determining the Sample Size 577 Running the Simulation 578

Data Analysis 578

The Best Case and the Worst Case 579 The Distribution of the Output Cell 579 Viewing

the Cumulative Distribution of the Output Cells 580 Obtaining Other Cumulative

Probabilities 581

Incorporating Graphs and Statistics into a Spreadsheet 581

The Uncertainty of Sampling 581

Constructing a Conï¬dence Interval for the True Population Mean 583 Constructing a

Conï¬dence Interval for a Population Proportion 584 Sample Sizes and Conï¬dence

Interval Widths 585

The Benefits of Simulation 585

Additional Uses of Simulation 586

A Reservation Management Example 587

Implementing the Model 587

Using the Decision Table Tool 589

An Inventory Control Example 595

Implementing the Model 596 Replicating the Model 600 Optimizing the Model 601

Comparing the Original and Optimal Ordering Policies 603

A Project Selection Example 604

A Spreadsheet Model 605

Solutions 609

Solving the Problem with OptQuest 607

A Portfolio Optimization Example 611

A Spreadsheet Model 612

Solving the Problem with OptQuest 615

Summary 616

References 617

The World of Management Science 617

Questions and Problems 618

Cases 632

Considering Other

Contents

xvii

13. Queuing Theory 641

Introduction 641

The Purpose of Queuing Models 641

Queuing System Configurations 642

Characteristics of Queuing Systems 643

Arrival Rate 644

Service Rate 645

Kendall Notation 647

Queuing Models 647

The M/M/s Model 648

An Example 649 The Current Situation 650 Adding a Server 650 Economic

Analysis 651

The M/M/s Model with Finite Queue Length 652

The Current Situation 653

Adding a Server 653

The M/M/s Model with Finite Population 654

An Example 655

The Current Situation 655

Adding Servers 657

The M/G/1 Model 658

The Current Situation 659

Adding the Automated Dispensing Device 659

The M/D/1 Model 661

Simulating Queues and the Steady-state Assumption 662

Summary 663

References 663

The World of Management Science 663

Questions and Problems 665

Cases 671

14. Project Management 673

Introduction 673

An Example 673

Creating the Project Network 674

A Note on Start and Finish Points 676

CPM: An Overview 677

The Forward Pass 678

The Backward Pass 680

Determining the Critical Path 682

A Note on Slack 683

Project Management Using Spreadsheets 684

Important Implementation Issue 688

Gantt Charts 688

Project Crashing 691

An LP Approach to Crashing 691 Determining the Earliest Crash Completion Time 693

Implementing the Model 694 Solving the Model 695 Determining a Least Costly Crash

Schedule 696 Crashing as an MOLP 698

xviii

Contents

PERT: An Overview 699

The Problems with PERT 700

Implications 702

Simulating Project Networks 702

An Example 702 Generating Random Activity Times 702

Running the Simulation 704 Analyzing the Results 706

Implementing the Model 704

Microsoft Project 707

Summary 710

References 710

The World of Management Science 710

Questions and Problems 711

Cases 720

15. Decision Analysis 724

Introduction 724

Good Decisions vs. Good Outcomes 724

Characteristics of Decision Problems 725

An Example 725

The Payoff Matrix 726

Decision Alternatives 727

States of Nature 727

The Payoff Values 727

Decision Rules 728

Nonprobabilistic Methods 729

The Maximax Decision Rule 729

Decision Rule 731

The Maximin Decision Rule 730

The Minimax Regret

Probabilistic Methods 733

Expected Monetary Value 733

Expected Regret 735

Sensitivity Analysis 736

The Expected Value of Perfect Information 738

Decision Trees 739

Rolling Back a Decision Tree 740

Using TreePlan 742

Adding Branches 743 Adding Event Nodes 744 Adding the Cash Flows 748

Determining the Payoffs and EMVs 748 Other Features 749

Multistage Decision Problems 750

A Multistage Decision Tree 751

Developing A Risk Proï¬le 753

Sensitivity Analysis 754

Spider Charts and Tornado Charts 755

Strategy Tables 758

Using Sample Information in Decision Making 760

Conditional Probabilities 761

The Expected Value of Sample Information 762

Computing Conditional Probabilities 763

Bayesâ€™s Theorem 765

Utility Theory 766

Utility Functions 766 Constructing Utility Functions 767 Using Utilities to Make

Decisions 770 The Exponential Utility Function 770 Incorporating Utilities

in TreePlan 771

Multicriteria Decision Making 772

Contents

The Multicriteria Scoring Model 773

The Analytic Hierarchy Process 777

Pairwise Comparisons 777 Normalizing the Comparisons 779 Consistency 780

Obtaining Scores for the Remaining Criteria 781 Obtaining Criterion Weights 782

Implementing the Scoring Model 783

Summary 783

References 784

The World of Management Science 785

Questions and Problems 786

Cases 796

Index 801

xix

This page intentionally left blank

Chapter 1

Introduction to Modeling

and Decision Analysis

1.0 Introduction

This book is titled Spreadsheet Modeling and Decision Analysis: A Practical Introduction to

Management Science, so letâ€™s begin by discussing exactly what this title means. By the

very nature of life, all of us must continually make decisions that we hope will solve

problems and lead to increased opportunities for ourselves or the organizations for

which we work. But making good decisions is rarely an easy task. The problems faced

by decision makers in todayâ€™s competitive, fast-paced business environment are often

extremely complex and can be addressed by numerous possible courses of action. Evaluating these alternatives and choosing the best course of action represents the essence of

decision analysis.

During the past decade, millions of business people discovered that one of the most

effective ways to analyze and evaluate decision alternatives involves using electronic

spreadsheets to build computer models of the decision problems they face. A computer

model is a set of mathematical relationships and logical assumptions implemented in a

computer as a representation of some real-world decision problem or phenomenon.

Today, electronic spreadsheets provide the most convenient and useful way for business

people to implement and analyze computer models. Indeed, most business people

probably would rate the electronic spreadsheet as their most important analytical tool

apart from their brain! Using a spreadsheet model (a computer model implemented via

a spreadsheet), a business person can analyze decision alternatives before having to

choose a speciï¬c plan for implementation.

This book introduces you to a variety of techniques from the ï¬eld of management science that can be applied in spreadsheet models to assist in the decision-analysis process.

For our purposes, we will deï¬ne management science as a ï¬eld of study that uses computers, statistics, and mathematics to solve business problems. It involves applying the

methods and tools of science to management and decision making. It is the science of

making better decisions. Management science is also sometimes referred to as operations research or decision science. See Figure 1.1 for a summary of how management science has been applied successfully in several real-world situations.

In the not too distant past, management science was a highly specialized ï¬eld that

generally could be practiced only by those who had access to mainframe computers and

who possessed an advanced knowledge of mathematics and computer programming

languages. However, the proliferation of powerful personal computers (PCs) and the

development of easy-to-use electronic spreadsheets have made the tools of management science far more practical and available to a much larger audience. Virtually

1

2

Chapter 1

Introduction to Modeling and Decision Analysis

FIGURE 1.1

Examples of

successful

management

science

applications

Home Runs in Management Science

Over the past decade, scores of operations research and management science

projects saved companies millions of dollars. Each year, the Institute For Operations Research and the Management Sciences (INFORMS) sponsors the Franz

Edelman Awards competition to recognize some of the most outstanding OR/MS

projects during the past year. Here are some of the â€œhome runsâ€ from the 2004

Edelman Awards (described in Interfaces, Vol. 31, No. 1, Januaryâ€“February, 2005).

â€¢ At the turn of the century, Motorola faced a crisis due to economic conditions

in its marketplaces; the company needed to reduce costs dramatically and

quickly. A natural target was its purchases of goods and services, as these expenses account for more than half of Motorolaâ€™s costs. Motorola decided to create an Internet-based system to conduct multi-step negotiations and auctions

for supplier negotiation. The system can handle complex bids and constraints,

such as bundled bids, volume-based discounts, and capacity limits. In addition, it can optimize multi-product, multi-vendor awards subject to these constraints and nonlinear price schedules. Beneï¬ts: In 2003, Motorola used this

system to source 56 percent of its total spending, with 600 users and a total savings exceeding $600 million.

â€¢ Waste Management is the leading company in North America in the wastecollection industry. The company has a ï¬‚eet of over 26,000 vehicles for collecting

waste from nearly 20 million residential customers, plus another two million

commercial customers. To improve trash collection and make its operations more

efï¬cient, Waste Management implemented a vehicle-routing application to optimize its collection routes. Beneï¬ts: The successful deployment of this system

brought beneï¬ts including the elimination of nearly 1,000 routes within one year

of implementation and an estimated annual savings of $44 million.

â€¢ Hong Kong has the worldâ€™s busiest port. Its largest terminal operator, Hong

Kong International Terminals (HIT), has the busiest container terminal in the

world serving over 125 ships per week, with 10 berths at which container ships

dock, and 122 yard cranes to move containers around the 227 acres of storage

yard. Thousands of trucks move containers into and out of the storage yard

each day. HIT implemented a decision-support system (with several embedded decision models and algorithms) to guide its operational decisions concerning the number and deployment of trucks for moving containers, the assignment of yard cranes, and the storage locations for containers. Beneï¬ts: The

cumulative effect of this system has led to a 35 percent reduction in container

handling costs, a 50 percent increase in throughput, and a 30 percent improvement in vessel turnaround time.

â€¢ The John Deere Company sells lawn equipment, residential and commercial

mowers, and utility tractors through a network of 2,500 dealers, supported by ï¬ve

Deere warehouses. Each dealer stocks about 100 products, leading to approximately 250,000 product-stocking locations. Furthermore, demand is quite seasonal

and stochastic. Deere implemented a system designed to optimize large-scale

multi-echelon, non-stationary stochastic inventory systems. Deere runs the

system each week to obtain recommended stocking levels for each product for

each stocking location for each week over a 26-week planning horizon. Beneï¬ts:

The impact of the application has been remarkable, leading to an inventory reduction of nearly one billion dollars and improving customer-service levels.

Characteristics and Benefits of Modeling

3

everyone who uses a spreadsheet today for model building and decision making is a

practitioner of management scienceâ€”whether they realize it or not.

1.1 The Modeling Approach

to Decision Making

The idea of using models in problem solving and decision analysis is really not new, and

certainly is not tied to the use of computers. At some point, all of us have used a modeling approach to make a decision. For example, if you ever have moved into a dormitory,

apartment, or house, you undoubtedly faced a decision about how to arrange the furniture in your new dwelling. There probably were several different arrangements to consider. One arrangement might give you the most open space but require that you build

a loft. Another might give you less space but allow you to avoid the hassle and expense

of building a loft. To analyze these different arrangements and make a decision, you did

not build the loft. You more likely built a mental model of the two arrangements, picturing what each looked like in your mindâ€™s eye. Thus, a simple mental model is sometimes all that is required to analyze a problem and make a decision.

For more complex decision problems, a mental model might be impossible or insufï¬cient, and other types of models might be required. For example, a set of drawings or

blueprints for a house or building provides a visual model of the real-world structure.

These drawings help illustrate how the various parts of the structure will ï¬t together

when it is completed. A road map is another type of visual model because it assists a driver in analyzing the various routes from one location to another.

You probably also have seen car commercials on television showing automotive engineers using physical models or scale models to study the aerodynamics of various

car designs, to ï¬nd the shape that creates the least wind resistance and maximizes fuel

economy. Similarly, aeronautical engineers use scale models of airplanes to study the

ï¬‚ight characteristics of various fuselage and wing designs. And civil engineers might

use scale models of buildings and bridges to study the strengths of different construction techniques.

Another common type of model is a mathematical model, which uses mathematical

relationships to describe or represent an object or decision problem. Throughout this

book we will study how various mathematical models can be implemented and analyzed on computers using spreadsheet software. But before we move to an in-depth

discussion of spreadsheet models, letâ€™s look at some of the more general characteristics

and beneï¬ts of modeling.

1.2 Characteristics and Benefits

of Modeling

Although this book focuses on mathematical models implemented in computers via

spreadsheets, the examples of non-mathematical models given earlier are worth discussing a bit more because they help illustrate several important characteristics and

beneï¬ts of modeling in general. First, the models mentioned earlier are usually simpliï¬ed versions of the object or decision problem they represent. To study the aerodynamics

of a car design, we do not need to build the entire car complete with engine and stereo.

Such components have little or no effect on aerodynamics. So, although a model is often

4

Chapter 1

Introduction to Modeling and Decision Analysis

a simpliï¬ed representation of reality, the model is useful as long as it is valid. A valid

model is one that accurately represents the relevant characteristics of the object or decision problem being studied.

Second, it is often less expensive to analyze decision problems using a model. This is

especially easy to understand with respect to scale models of big-ticket items such as

cars and planes. Besides the lower ï¬nancial cost of building a model, the analysis of a

model can help avoid costly mistakes that might result from poor decision making. For

example, it is far less costly to discover a ï¬‚awed wing design using a scale model of an

aircraft than after the crash of a fully loaded jetliner.

Frank Brock, former executive vice president of the Brock Candy Company, related

the following story about blueprints his company prepared for a new production facility. After months of careful design work he proudly showed the plans to several of his

production workers. When he asked for their comments, one worker responded, â€œItâ€™s a

ï¬ne looking building, Mr. Brock, but that sugar valve looks like itâ€™s about twenty feet

away from the steam valve.â€ â€œWhatâ€™s wrong with that?â€ asked Brock. â€œWell, nothing,â€

said the worker, â€œexcept that I have to have my hands on both valves at the same time!â€1

Needless to say, it was far less expensive to discover and correct this â€œlittleâ€ problem

using a visual model before pouring the concrete and laying the pipes as originally

planned.

Third, models often deliver needed information on a more timely basis. Again, it is

relatively easy to see that scale models of cars or airplanes can be created and analyzed

more quickly than their real-world counterparts. Timeliness is also an issue when vital

data will not become available until later. In these cases, we might create a model to help

predict the missing data to assist in current decision making.

Fourth, models are frequently helpful in examining things that would be impossible

to do in reality. For example, human models (crash dummies) are used in crash tests to

see what might happen to an actual person if a car were to hit a brick wall at a high

speed. Likewise, models of DNA can be used to visualize how molecules ï¬t together.

Both of these are difï¬cult, if not impossible, to do without the use of models.

Finally, and probably most important, models allow us to gain insight and understanding about the object or decision problem under investigation. The ultimate purpose of using models is to improve decision making. As you will see, the process of

building a model can shed important light and understanding on a problem. In some

cases, a decision might be made while building the model as a previously misunderstood element of the problem is discovered or eliminated. In other cases, a careful analysis of a completed model might be required to â€œget a handleâ€ on a problem and gain the

insights needed to make a decision. In any event, the insight gained from the modeling

process ultimately leads to better decision making.

1.3 Mathematical Models

As mentioned earlier, the modeling techniques in this book differ quite a bit from scale

models of cars and planes, or visual models of production plants. The models we will

build use mathematics to describe a decision problem. We use the term â€œmathematicsâ€

in its broadest sense, encompassing not only the most familiar elements of math, such as

algebra, but also the related topic of logic.

1

Colson, Charles and Jack Eckerd, Why America Doesnâ€™t Work (Denver, Colorado: Word Publishing, 1991), 146â€“147.

Mathematical Models

5

Now, letâ€™s consider a simple example of a mathematical model:

PROFIT = REVENUE âˆ’ EXPENSES

1.1

Equation 1.1 describes a simple relationship between revenue, expenses, and proï¬t.

It is a mathematical relationship that describes the operation of determining proï¬tâ€”or

a mathematical model of proï¬t. Of course, not all models are this simple, but taken piece

by piece, the models we will discuss are not much more complex than this one.

Frequently, mathematical models describe functional relationships. For example, the

mathematical model in equation 1.1 describes a functional relationship between revenue, expenses, and proï¬t. Using the symbols of mathematics, this functional relationship is represented as:

PROFIT = f(REVENUE, EXPENSES)

1.2

In words, the previous expression means â€œproï¬t is a function of revenue and

expenses.â€ We also could say that proï¬t depends on (or is dependent on) revenue and

expenses. Thus, the term PROFIT in equation 1.2 represents a dependent variable,

whereas REVENUE and EXPENSES are independent variables. Frequently, compact

symbols (such as A, B, and C) are used to represent variables in an equation such as 1.2.

For instance, if we let Y, X1, and X2 represent PROFIT, REVENUE, and EXPENSES, respectively, we could rewrite equation 1.2 as follows:

Y = f(X1, X2 )

1.3

The notation f(.) represents the function that deï¬nes the relationship between the dependent variable Y and the independent variables X1 and X2. In the case of determining

PROFIT from REVENUE and EXPENSES, the mathematical form of the function f(.) is

quite simple: f(X1, X2 ) = X1 âˆ’ X2. However, in many other situations we will model, the

form of f(.) is quite complex and might involve many independent variables. But regardless of the complexity of f(.) or the number of independent variables involved,

many of the decision problems encountered in business can be represented by models

that assume the general form,

Y = f(X1, X2, . . . , Xk)

1.4

In equation 1.4, the dependent variable Y represents some bottom-line performance

measure of the problem we are modeling. The terms X1, X2, . . . , Xk represent the different independent variables that play some role or have some effect in determining the

value of Y. Again, f(.) is the function (possibly quite complex) that speciï¬es or describes

the relationship between the dependent and independent variables.

The relationship expressed in equation 1.4 is very similar to what occurs in most

spreadsheet models. Consider a simple spreadsheet model to calculate the monthly

payment for a car loan, as shown in Figure 1.2.

The spreadsheet in Figure 1.2 contains a variety of input cells (for example, purchase

price, down payment, trade-in, term of loan, annual interest rate) that correspond

conceptually to the independent variables X1, X2, . . . , Xk in equation 1.4. Similarly, a

variety of mathematical operations are performed using these input cells in a manner

analogous to the function f(.) in equation 1.4. The results of these mathematical operations determine the value of some output cell in the spreadsheet (for example, monthly

payment) that corresponds to the dependent variable Y in equation 1.4. Thus, there is a

direct correspondence between equation 1.4 and the spreadsheet in Figure 1.2. This type

of correspondence exists for most of the spreadsheet models in this book.

6

Chapter 1

Introduction to Modeling and Decision Analysis

FIGURE 1.2

Example of a

simple spreadsheet

model

1.4 Categories of Mathematical Models

Not only does equation 1.4 describe the major elements of mathematical or spreadsheet

models, but it also provides a convenient means for comparing and contrasting the

three categories of modeling techniques presented in this bookâ€”Prescriptive Models,

Predictive Models, and Descriptive Models. Figure 1.3 summarizes the characteristics

and techniques associated with each of these categories.

In some situations, a manager might face a decision problem involving a very precise,

well-deï¬ned functional relationship f(.) between the independent variables X1, X2, . . . ,

Xk and the dependent variable Y. If the values for the independent variables are under

FIGURE 1.3

Categories and

characteristics of

management

science modeling

techniques

Model Characteristics

Category

Form of f (.)

Values of Independent

Variables

Management Science

Techniques

Prescriptive

Models

known,

well-deï¬ned

known or under decision

makerâ€™s control

Predictive

Models

unknown,

ill-deï¬ned

known or under decision

makerâ€™s control

Descriptive

Models

known,

well-deï¬ned

unknown or uncertain

Linear Programming,

Networks, Integer

Programming, CPM,

Goal Programming,

EOQ, Nonlinear

Programming

Regression Analysis,

Time Series Analysis,

Discriminant Analysis

Simulation, Queuing,

PERT, Inventory Models

The Problem-Solving Process

7

the decision makerâ€™s control, the decision problem in these types of situations boils

down to determining the values of the independent variables X1, X2, . . ., Xk that produce

the best possible value for the dependent variable Y. These types of models are called

Prescriptive Models because their solutions tell the decision maker what actions to

take. For example, you might be interested in determining how a given sum of money

should be allocated to different investments (represented by the independent variables)

to maximize the return on a portfolio without exceeding a certain level of risk.

A second category of decision problems is one in which the objective is to predict or

estimate what value the dependent variable Y will take on when the independent variables X1, X2, . . ., Xk take on speciï¬c values. If the function f(.) relating the dependent and

independent variables is known, this is a very simple taskâ€”simply enter the speciï¬ed

values for X1, X2, . . ., Xk into the function f(.) and compute Y. In some cases, however, the

functional form of f(.) might be unknown and must be estimated for the decision maker

to make predictions about the dependent variable Y. These types of models are called

Predictive Models. For example, a real estate appraiser might know that the value of a

commercial property (Y) is inï¬‚uenced by its total square footage (X1) and age (X2),

among other things. However, the functional relationship f(.) that relates these variables

to one another might be unknown. By analyzing the relationship between the selling

price, total square footage, and age of other commercial properties, the appraiser might

be able to identify a function f(.) that relates these two variables in a reasonably accurate

manner.

The third category of models you are likely to encounter in the business world is

called Descriptive Models. In these situations, a manager might face a decision problem that has a very precise, well-deï¬ned functional relationship f(.) between the independent variables X1, X2, . . ., Xk and the dependent variable Y. However, there might

be great uncertainty as to the exact values that will be assumed by one or more of the

independent variables X1, X2, . . ., Xk. In these types of problems, the objective is to

describe the outcome or behavior of a given operation or system. For example, suppose

a company is building a new manufacturing facility and has several choices about the

type of machines to put in the new plant, and also various options for arranging the

machines. Management might be interested in studying how the various plant conï¬gurations would affect on-time shipments of orders (Y), given the uncertain number of

orders that might be received (X1) and the uncertain due dates (X2) that might be required by these orders.

1.5 The Problem-Solving Process

Throughout our discussion, we have said that the ultimate goal in building models is to

help managers make decisions that solve problems. The modeling techniques we will

study represent a small but important part of the total problem-solving process. To become an effective modeler, it is important to understand how modeling ï¬ts into the

entire problem-solving process.

Because a model can be used to represent a decision problem or phenomenon, we

might be able to create a visual model of the phenomenon that occurs when people

solve problemsâ€”what we call the problem-solving process. Although a variety of models could be equally valid, the one in Figure 1.4 summarizes the key elements of the

problem-solving process and is sufï¬cient for our purposes.

The ï¬rst step of the problem-solving process, identifying the problem, is also the

most important. If we do not identify the correct problem, all the work that follows will

amount to nothing more than wasted effort, time, and money. Unfortunately, identifying

8

FIGURE 1.4

Chapter 1

Identify

Problem

A visual model of

the problemsolving process

Introduction to Modeling and Decision Analysis

Formulate and

Implement Model

Analyze

Model

Test

Results

Implement

Solution

Unsatisfactory Results

the problem to solve is often not as easy as it seems. We know that a problem exists

when there is a gap or disparity between the present situation and some desired state of

affairs. However, we usually are not faced with a neat, well-deï¬ned problem. Instead,

we often ï¬nd ourselves facing a â€œmessâ€!2 Identifying the real problem involves gathering a lot of information and talking with many people to increase our understanding of

the mess. We must then sift through all this information and try to identify the root

problem or problems causing the mess. Thus, identifying the real problem (and not just

the symptoms of the problem) requires insight, some imagination, time, and a good bit

of detective work.

The end result of the problem-identiï¬cation step is a well-deï¬ned statement of the

problem. Simply deï¬ning a problem well will often make it much easier to solve.

Having identiï¬ed the problem, we turn our attention to creating or formulating a model

of the problem. Depending on the nature of the problem, we might use a mental model,

a visual model, a scale model, or a mathematical model. Although this book focuses on

mathematical models, this does not mean that mathematical models are always applicable or best. In most situations, the best model is the simplest model that accurately

reï¬‚ects the relevant characteristic or essence of the problem being studied.

We will discuss several different management science modeling techniques in this

book. It is important that you not develop too strong a preference for any one technique.

Some people have a tendency to want to formulate every problem they face as a model

that can be solved by their favorite management science technique. This simply will not

work.

As indicated in Figure 1.3, there are fundamental differences in the types of problems

a manager might face. Sometimes, the values of the independent variables affecting a

problem are under the managerâ€™s control; sometimes they are not. Sometimes, the form

of the functional relationship f(.) relating the dependent and independent variables is

well-deï¬ned, and sometimes it is not. These fundamental characteristics of the problem

should guide your selection of an appropriate management science modeling technique. Your goal at the model-formulation stage is to select a modeling technique that

ï¬ts your problem, rather than trying to ï¬t your problem into the required format of a

pre-selected modeling technique.

After you select an appropriate representation or formulation of your problem, the

next step is to implement this formulation as a spreadsheet model. We will not dwell on

the implementation process now because that is the focus of the remainder of this book.

After you verify that your spreadsheet model has been implemented accurately, the next

step in the problem-solving process is to use the model to analyze the problem it represents. The main focus of this step is to generate and evaluate alternatives that might lead

to a solution. This often involves playing out a number of scenarios or asking several

â€œWhat if?â€ questions. Spreadsheets are particularly helpful in analyzing mathematical

models in this manner. In a well-designed spreadsheet model, it should be fairly simple

to change some of the assumptions in the model to see what might happen in different

2

This characterization is borrowed from Chapter 5, James R. Evans, Creative Thinking in the Decision and Management Sciences (Cincinnati, Ohio: South-Western Publishing, 1991), 89â€“115.

Anchoring and Framing Effects

9

situations. As we proceed, we will highlight some techniques for designing spreadsheet

models that facilitate this type of â€œwhat if?â€ analysis. â€œWhat if?â€ analysis is also very appropriate and useful when working with nonmathematical models.

The end result of analyzing a model does not always provide a solution to the actual

problem being studied. As we analyze a model by asking various â€œWhat if?â€ questions,

it is important to test the feasibility and quality of each potential solution. The blueprints

that Frank Brock showed to his production employees represented the end result of his

analysis of the problem he faced. He wisely tested the feasibility and quality of this alternative before implementing it, and discovered an important ï¬‚aw in his plans. Thus, the

testing process can give important new insights into the nature of a problem. The testing

process is also important because it provides the opportunity to double-check the validity of the model. At times, we might discover an alternative that appears to be too good

to be true. This could lead us to ï¬nd that some important assumption has been left out of

the model. Testing the results of the model against known results (and simple common

sense) helps ensure the structural integrity and validity of the model. After analyzing the

model, we might discover that we need to go back and modify the model.

The last step of the problem-solving process, implementation, is often the most difï¬cult. By their very nature, solutions to problems involve people and change. For better

or for worse, most people resist change. However, there are ways to minimize the seemingly inevitable resistance to change. For example, it is wise, if possible, to involve anyone who will be affected by the decision in all steps of the problem-solving process. This

not only helps develop a sense of ownership and understanding of the ultimate solution, but it also can be the source of important information throughout the problemsolving process. As the Brock Candy story illustrates, even if it is impossible to include

those affected by the solution in all steps, their input should be solicited and considered

before a solution is accepted for implementation. Resistance to change and new systems

also can be eased by creating ï¬‚exible, user-friendly interfaces for the mathematical models that often are developed in the problem-solving process.

Throughout this book, we focus mostly on the model formulation, implementation,

analysis, and testing steps of the problem-solving process, summarized in Figure 1.4.

Again, this does not imply that these steps are more important than the others. If we do

not identify the correct problem, the best we can hope for from our modeling effort is

â€œthe right answer to the wrong question,â€ which does not solve the real problem. Similarly, even if we do identify the problem correctly and design a model that leads to a perfect solution, if we cannot implement the solution, then we still have not solved the

problem. Developing the interpersonal and investigative skills required to work with

people in deï¬ning the problem and implementing the solution are as important as the

mathematical modeling skills you will develop by working through this book.

1.6 Anchoring and Framing Effects

At this point, some of you reading this book are probably thinking it is better to rely on

subjective judgment and intuition rather than models when making decisions. Indeed,

most nontrivial decision problems involve some issues that are difï¬cult or impossible to

structure and analyze in the form of a mathematical model. These unstructurable aspects of a decision problem might require the use of judgment and intuition. However,

it is important to realize that human cognition is often ï¬‚awed and can lead to incorrect

judgments and irrational decisions. Errors in human judgment often arise because of

what psychologists term anchoring and framing effects associated with decision

problems.

10

Chapter 1

Introduction to Modeling and Decision Analysis

Anchoring effects arise when a seemingly trivial factor serves as a starting point (or

anchor) for estimations in a decision-making problem. Decision makers adjust their

estimates from this anchor but nevertheless remain too close to the anchor and usually

under-adjust. In a classic psychological study on this issue, one group of subjects were

asked to individually estimate the value of 1 2 3 4 5 6 7 8 (without using

a calculator). Another group of subjects were each asked to estimate the value of 8 7

6 5 4 3 2 1. The researchers hypothesized that the ï¬rst number presented (or

perhaps the product of the ï¬rst three or four numbers) would serve as a mental anchor.

The results supported the hypothesis. The median estimate of subjects shown the numbers in ascending sequence (1 2 3 . . .) was 512, whereas the median estimate of subjects shown the sequence in descending order (8 7 6 . . .) was 2,250. Of course, the

order of multiplication for these numbers is irrelevant and the product of both series is

the same: 40,320.

Framing effects refer to how a decision maker views or perceives the alternatives in a

decision problemâ€”often involving a win/loss perspective. The way a problem is

framed often inï¬‚uences the choices made by a decision maker and can lead to irrational

behavior. For example, suppose you have just been given $1,000 but must choose one of

the following alternatives: (A1) Receive an additional $500 with certainty, or (B1) Flip a

fair coin and receive an additional $1,000 if heads occurs or $0 additional is tails occurs.

Here, alternative A1 is a â€œsure winâ€ and is the alternative most people prefer. Now suppose you have been given $2,000 and must choose one of the following alternatives: (A2)

Give back $500 immediately, or (B2) Flip a fair coin and give back $0 if heads occurs or

$1,000 if tails occurs. When the problem is framed this way, alternative A2 is a â€œsure

lossâ€ and many people who previously preferred alternative A1 now opt for alternative B2 (because it holds a chance of avoiding a loss). However, Figure 1.5 shows a single decision tree for these two scenarios making it clear that, in both cases, the â€œAâ€

alternative guarantees a total payoff of $1,500, whereas the â€œBâ€ alternative offers a 50%

chance of a $2,000 total payoff and a 50% chance of a $1,000 total payoff. (Decision trees

will be covered in greater detail in a later chapter.) A purely rational decision maker

should focus on the consequences of his or her choices and consistently select the same

alternative, regardless of how the problem is framed.

Whether we want to admit it or not, we are all prone to make errors in estimation due

to anchoring effects and may exhibit irrationality in decision making due to framing

effects. As a result, it is best to use computer models to do what they are best at (i.e.,

modeling structurable portions of a decision problem) and let the human brain do what

it is best at (i.e., dealing with the unstructurable portion of a decision problem).

FIGURE 1.5

Payoffs

$1,500

Alternative A

Decision tree for

framing effects

Initial state

Heads (50%)

$2,000

Alternative B

(Flip coin)

Tails (50%)

$1,000

Summary

11

1.7 Good Decisions vs. Good Outcomes

The goal of the modeling approach to problem solving is to help individuals make good

decisions. But good decisions do not always result in good outcomes. For example, suppose the weather report on the evening news predicts a warm, dry, sunny day tomorrow. When you get up and look out the window tomorrow morning, suppose there is

not a cloud in sight. If you decide to leave your umbrella at home and subsequently get

soaked in an unexpected afternoon thundershower, did you make a bad decision? Certainly not. Unforeseeable circumstances beyond your control caused you to experience

a bad outcome, but it would be unfair to say that you made a bad decision. Good decisions sometimes result in bad outcomes. See Figure 1.6 for the story of another good decision having a bad outcome.

The modeling techniques presented in this book can help you make good decisions,

but cannot guarantee that good outcomes will always occur as a result of those decisions. Even when a good decision is made, luck often plays a role in determining

whether a good or bad outcome occurs. However, using a structured, modeling approach to decision making should produce good outcomes more frequently than making decisions in a more haphazard manner.

1.8 Summary

This book introduces you to a variety of techniques from the ï¬eld of management science that can be applied in spreadsheet models to assist in decision analysis and problem solving. This chapter discussed how spreadsheet models of decision problems can

be used to analyze the consequences of possible courses of action before a particular

alternative is selected for implementation. It described how models of decision problems differ in several important characteristics and how you should select a modeling

technique that is most appropriate for the type of problem being faced. Finally, it discussed how spreadsheet modeling and analysis ï¬t into the problem-solving process.

FIGURE 1.6

Andre-Francois Raffray thought he had a great deal in 1965 when he agreed to

pay a 90-year-old woman named Jeanne Calment $500 a month until she died to

acquire her grand apartment in Arles, northwest of Marseilles in the south of

Franceâ€”a town Vincent Van Gogh once roamed. Buying apartments â€œfor lifeâ€ is

common in France. The elderly owner gets to enjoy a monthly income from the

buyer who gambles on getting a real estate bargainâ€”betting the owner doesnâ€™t

live too long. Upon the ownerâ€™s death, the buyer inherits the apartment regardless

of how much was paid. But in December of 1995, Raffray died at age 77, having

paid more than $180,000 for an apartment he never got to live in.

On the same day, Calment, then the worldâ€™s oldest living person at 120, dined

on foie gras, duck thighs, cheese, and chocolate cake at her nursing home near the

sought-after apartment. And she does not need to worry about losing her $500

monthly income. Although the amount Raffray already paid is twice the

apartmentâ€™s current market value, his widow is obligated to keep sending the

monthly check to Calment. If Calment also outlives her, then the Raffray children

will have to pay. â€œIn life, one sometimes makes bad deals,â€ said Calment of the

outcome of Raffrayâ€™s decision. (Source: The Savannah Morning News, 12/29/95.)

A good decision

with a bad

outcome

12

Chapter 1

Introduction to Modeling and Decision Analysis

1.9 References

Edwards, J., P. Finlay, and J. Wilson. â€œThe role of the OR specialist in â€˜do it yourselfâ€™ spreadsheet development.â€ European Journal of Operational Research, vol. 127, no. 1, 2000.

Forgione, G. â€œCorporate MS Activities: An Update.â€ Interfaces, vol. 13, no. 1, 1983.

Hall, R. â€œWhatâ€™s So Scientiï¬c about MS/OR?â€ Interfaces, vol. 15, 1985.

Hastie, R. and R. M. Dawes. Rational Choice in an Uncertain World, Sage Publications, 2001.

Schrage, M. Serious Play, Harvard Business School Press, 2000.

Sonntag, C. and Grossman, T. â€œEnd-User Modeling Improves R&D Management at AgrEvo Canada, Inc.â€

Interfaces, vol. 29, no. 5, 1999.

THE WORLD OF MANAGEMENT SCIENCE

â€Business Analysts Trained in Management Science Can Be

a Secret Weapon in a CIOâ€™s Quest for Bottom-Line Results.â€

Efï¬ciency nuts. These are the people you see at cocktail parties explaining how the

host could disperse that crowd around the popular shrimp dip if he would divide

it into three bowls and place them around the room. As she draws the improved

trafï¬c ï¬‚ow on a paper napkin, you notice that her favorite word is â€œoptimizeâ€â€”a

tell-tale sign that she has studied the ï¬eld of â€œoperations researchâ€ or â€œmanagement scienceâ€ (also known as OR/MS).

OR/MS professionals are driven to solve logistics problems. This trait might

not make them the most popular people at parties, but it is exactly what todayâ€™s information systems (IS) departments need to deliver more business value. Experts

say that smart IS executives will learn to exploit the talents of these mathematical

wizards in their quest to boost a companyâ€™s bottom line.

According to Ron J. Ponder, chief information ofï¬cer (CIO) at Sprint Corp. in

Kansas City, Mo., and former CIO at Federal Express Corp., â€œIf IS departments had

more participation from operations research analysts, they would be building

much better, richer IS solutions.â€ As someone who has a Ph.D. in operations research and who built the renowned package-tracking systems at Federal Express,

Ponder is a true believer in OR/MS. Ponder and others say analysts trained in

OR/MS can turn ordinary information systems into money-saving, decisionsupport systems, and are ideally suited to be members of the business process

reengineering team. â€œIâ€™ve always had an operations research department reporting

to me, and itâ€™s been invaluable. Now Iâ€™m building one at Sprint,â€ says Ponder.

The Beginnings

OR/MS got its start in World War II, when the military had to make important decisions about allocating scarce resources to various military operations. One of the ï¬rst

business applications for computers in the 1950s was to solve operations research

problems for the petroleum industry. A technique called linear programming was

used to ï¬gure out how to blend gasoline for the right ï¬‚ash point, viscosity, and octane

in the most economical way. Since then, OR/MS has spread throughout business and

government, from designing efï¬cient drive-thru window operations for Burger King

Corp. to creating ultrasophisticated computerized stock trading systems.

A classic OR/MS example is the crew scheduling problem faced by all major airlines. How do you plan the itineraries of 8,000 pilots and 17,000 ï¬‚ight attendants

The World of Management Science

when there is an astronomical number of combinations of planes, crews, and cities?

The OR/MS analysts at United Airlines came up with a scheduling system called

Paragon that attempts to minimize the amount of paid time that crews spend waiting for ï¬‚ights. Their model factors in constraints such as labor agreement provisions and Federal Aviation Administration regulations, and is projected to save the

airline at least $1 million a year.

OR/MS and IS

Somewhere in the 1970s, the OR/MS and IS disciplines went in separate directions.

â€œThe IS profession has had less and less contact with the operations research

folks . . . and IS lost a powerful intellectual driver,â€ says Peter G. W. Keen, executive

director of the International Center for Information Technologies in Washington,

D.C. However, many feel that now is an ideal time for the two disciplines to rebuild

some bridges.

Todayâ€™s OR/MS professionals are involved in a variety of IS-related ï¬elds, including inventory management, electronic data interchange, supply chain management, IT security, computer-integrated manufacturing, network management,

and practical applications of artiï¬cial intelligence. Furthermore, each side needs

something the other side has: OR/MS analysts need corporate data to plug into

their models, and the IS folks need to plug the OR/MS models into their strategic

information systems. At the same time, CIOs need intelligent applications that

enhance the bottom line and make them heroes with the chief executive ofï¬cer.

OR/MS analysts can develop a model of how a business process works now

and simulate how it could work more efï¬ciently in the future. Therefore, it makes

sense to have an OR/MS analyst on the interdisciplinary team that tackles business process reengineering projects. In essence, OR/MS professionals add more

value to the IS infrastructure by building â€œtools that really help decision makers

analyze complex situations,â€ says Andrew B. Whinston, director of the Center for

Information Systems Management at the University of Texas at Austin.

Although IS departments typically believe their job is done if they deliver accurate and timely information, Thomas M. Cook, president of American Airlines Decision Technologies, Inc. says that adding OR/MS skills to the team can produce

intelligent systems that actually recommend solutions to business problems. One

of the big success stories at Cookâ€™s operations research shop is a â€œyield managementâ€ system that decides how much to overbook and how to set prices for each

seat so that a plane is ï¬lled up and proï¬ts are maximized. The yield management

system deals with more than 250 decision variables and accounts for a signiï¬cant

amount of American Airlinesâ€™ revenue.

Where to Start

So how can the CIO start down the road toward collaboration with OR/MS analysts? If the company already has a group of OR/MS professionals, the IS department can draw on their expertise as internal consultants. Otherwise, the CIO can

simply hire a few OR/MS wizards, throw a problem at them, and see what happens. The payback may come surprisingly quickly. As one former OR/MS professional put it: â€œIf I couldnâ€™t save my employer the equivalent of my own salary in

the ï¬rst month of the year, then I wouldnâ€™t feel like I was doing my job.â€

Adapted from: Mitch Betts, â€œEfï¬ciency Einsteins,â€ ComputerWorld, March 22, 1993, p. 64.

13

14

Chapter 1

Introduction to Modeling and Decision Analysis

Questions and Problems

1. What is meant by the term decision analysis?

2. Deï¬ne the term computer model.

3. What is the difference between a spreadsheet model and a computer model?

4. Deï¬ne the term management science.

5. What is the relationship between management science and spreadsheet modeling?

6. What kinds of spreadsheet applications would not be considered management

science?

7. In what ways do spreadsheet models facilitate the decision-making process?

8. What are the beneï¬ts of using a modeling approach to decision making?

9. What is a dependent variable?

10. What is an independent variable?

11. Can a model have more than one dependent variable?

12. Can a decision problem have more than one dependent variable?

13. In what ways are prescriptive models different from descriptive models?

14. In what ways are prescriptive models different from predictive models?

15. In what ways are descriptive models different from predictive models?

16. How would you deï¬ne the words description, prediction, and prescription?

Carefully consider what is unique about the meaning of each word.

17. Identify one or more mental models you have used. Can any of them be expressed

mathematically? If so, identify the dependent and independent variables in your

model.

18. Consider the spreadsheet model shown in Figure 1.2. Is this model descriptive, predictive, or prescriptive in nature, or does it not fall into any of these categories?

19. What are the steps in the problem-solving process?

20. Which step in the problem-solving process do you think is most important? Why?

21. Must a model accurately represent every detail of a decision situation to be useful?

Why or why not?

22. If you were presented with several different models of a given decision problem,

which would you be most inclined to use? Why?

23. Describe an example in which business or political organizations may use anchoring

effects to inï¬‚uence decision making.

24. Describe an example in which business or political organizations may use framing

effects to inï¬‚uence decision making.

25. Suppose sharks have been spotted along the beach where you are vacationing with

a friend. You and your friend have been informed of the shark sightings and are

aware of the damage a shark attack can inï¬‚ict on human ï¬‚esh. You both decide (individually) to go swimming anyway. You are promptly attacked by a shark while

your friend has a nice time body surï¬ng in the waves. Did you make a good or bad

decision? Did your friend make a good or bad decision? Explain your answer.

26. Describe an example in which a well-known business, political, or military leader

made a good decision that resulted in a bad outcome, or a bad decision that resulted

in a good outcome.

CASE 1.1

Patrickâ€™s Paradox

Patrickâ€™s luck had changed overnightâ€”but not his skill at mathematical reasoning. The

day after graduating from college he used the $20 that his grandmother had given him

Case

15

as a graduation gift to buy a lottery ticket. He knew that his chances of winning the

lottery were extremely low and it probably was not a good way to spend this money.

But he also remembered from the class he took in management science that bad decisions sometimes result in good outcomes. So he said to himself, â€œWhat the heck? Maybe

this bad decision will be the one with a good outcome.â€ And with that thought, he

bought his lottery ticket.

The next day Patrick pulled the crumpled lottery ticket out of the back pocket of his

blue jeans and tried to compare his numbers to the winning numbers printed in the

paper. When his eyes ï¬nally came into focus on the numbers they also just about

popped out of his head. He had a winning ticket! In the ensuing days he learned that

his share of the jackpot would give him a lump sum payout of about $500,000 after

taxes. He knew what he was going to do with part of the money: buy a new car, pay

off his college loans, and send his grandmother on an all-expenses-paid trip to Hawaii.

But he also knew that he couldnâ€™t continue to hope for good outcomes to arise from

more bad decisions. So he decided to take half of his winnings and invest it for his

retirement.

A few days later, Patrick was sitting around with two of his fraternity buddies, Josh

and Peyton, trying to ï¬gure out how much money his new retirement fund might be

worth in 30 years. They were all business majors in college and remembered from their

ï¬nance class that if you invest p dollars for n years at an annual interest rate of i percent

then in n years you would have p(1 + i)n dollars. So they ï¬gure that if Patrick invested

$250,000 for 30 years in an investment with a 10% annual return then in 30 years he

would have $4,362,351 (that is, $250,000(1 + 0.10)30 ).

But after thinking about it a little more, they all agreed that it would be unlikely

for Patrick to find an investment that would produce a return of exactly 10%

each and every year for the next 30 years. If any of this money is invested in stocks

then some years the return might be higher than 10% and some years it would probably be lower. So to help account for the potential variability in the investment

returns Patrick and his friends came up with a plan; they would assume he could

find an investment that would produce an annual return of 17.5% seventy percent

of the time and a return (or actually a loss) of 7.5% thirty percent of the time.

Such an investment should produce an average annual return of 0.7(17.5%)

0.3( 7.5%) = 10%. Josh felt certain that this meant Patrick could still expect his

$250,000 investment to grow to $4,362,351 in 30 years (because $250,000(1 0.10)30

= $4,362,351).

After sitting quietly and thinking about it for a while, Peyton said that he thought

Josh was wrong. The way Peyton looked at it, Patrick should see a 17.5% return in 70%

of the 30 years (or 0.7(30) = 21 years) and a 7.5% return in 30% of the 30 years (or

0.3(30) = 9 years). So, according to Peyton, that would mean Patrick should have

$250,000(1 + 0.175)21(1 0.075)9 = $3,664,467 after 30 years. But thatâ€™s $697,884 less

than what Josh says Patrick should have.

After listening to Peytonâ€™s argument, Josh said he thought Peyton was wrong

because his calculation assumes that the â€œgoodâ€ return of 17.5% would occur in each of

the ï¬rst 21 years and the â€œbadâ€ return of 7.5% would occur in each of the last 9 years.

But Peyton countered this argument by saying that the order of good and bad returns

does not matter. The commutative law of arithmetic says that when you add or multiply

numbers, the order doesnâ€™t matter (that is, X + Y = Y + X and X Y = Y X). So

Peyton says that because Patrick can expect 21 â€œgoodâ€ returns and 9 â€œbadâ€ returns and

it doesnâ€™t matter in what order they occur, then the expected outcome of the investment

should be $3,664,467 after 30 years.

16

Chapter 1

Introduction to Modeling and Decision Analysis

Patrick is now really confused. Both of his friendsâ€™ arguments seem to make perfect

sense logicallyâ€”but they lead to such different answers, and they canâ€™t both be right.

What really worries Patrick is that he is starting his new job as a business analyst in

a couple of weeks. And if he canâ€™t reason his way to the right answer in a relatively

simple problem like this, what is he going to do when he encounters the more difï¬cult

problems awaiting him the business world? Now he really wishes he had paid more

attention in his management sciences class.

So what do you think? Who is right, Josh or Peyton? And more important, why?

Chapter 2

Introduction to Optimization

and Linear Programming

2.0 Introduction

Our world is ï¬lled with limited resources. The amount of oil we can pump out of the

earth is limited. The amount of land available for garbage dumps and hazardous waste is

limited and, in many areas, diminishing rapidly. On a more personal level, each of us has

a limited amount of time in which to accomplish or enjoy the activities we schedule each

day. Most of us have a limited amount of money to spend while pursuing these activities.

Businesses also have limited resources. A manufacturing organization employs a limited

number of workers. A restaurant has a limited amount of space available for seating.

Deciding how best to use the limited resources available to an individual or a business is a universal problem. In todayâ€™s competitive business environment, it is increasingly important to make sure that a companyâ€™s limited resources are used in the most

efï¬cient manner possible. Typically, this involves determining how to allocate the

resources in such a way as to maximize proï¬ts or minimize costs. Mathematical

programming (MP) is a ï¬eld of management science that ï¬nds the optimal, or most efï¬cient, way of using limited resources to achieve the objectives of an individual or a business. For this reason, mathematical programming often is referred to as optimization.

2.1 Applications of

Mathematical Optimization

To help you understand the purpose of optimization and the types of problems for

which it can be used, letâ€™s consider several examples of decision-making situations in

which MP techniques have been applied.

Determining Product Mix. Most manufacturing companies can make a variety of

products. However, each product usually requires different amounts of raw materials

and labor. Similarly, the amount of proï¬t generated by the products varies. The manager

of such a company must decide how many of each product to produce to maximize

proï¬ts or to satisfy demand at minimum cost.

Manufacturing. Printed circuit boards, like those used in most computers, often have

hundreds or thousands of holes drilled in them to accommodate the different electrical

components that must be plugged into them. To manufacture these boards, a computercontrolled drilling machine must be programmed to drill in a given location, then move

17

18

Chapter 2

Introduction to Optimization and Linear Programming

the drill bit to the next location and drill again. This process is repeated hundreds or

thousands of times to complete all the holes on a circuit board. Manufacturers of these

boards would beneï¬t from determining the drilling order that minimizes the total

distance the drill bit must be moved.

Routing and Logistics. Many retail companies have warehouses around the country

that are responsible for keeping stores supplied with merchandise to sell. The amount of

merchandise available at the warehouses and the amount needed at each store tends to

ï¬‚uctuate, as does the cost of shipping or delivering merchandise from the warehouses

to the retail locations. Large amounts of money can be saved by determining the least

costly method of transferring merchandise from the warehouses to the stores.

Financial Planning. The federal government requires individuals to begin withdrawing

money from individual retirement accounts (IRAs) and other tax-sheltered retirement programs no later than age 70.5. There are various rules that must be followed to avoid paying

penalty taxes on these withdrawals. Most individuals want to withdraw their money in a

manner that minimizes the amount of taxes they must pay while still obeying the tax laws.

Optimization Is Everywhere

Going to Disney World this summer? Optimization will be your ubiquitous companion, scheduling the crews and planes, pricing the airline tickets and hotel

rooms, even helping to set capacities on the theme park rides. If you use Orbitz to

book your ï¬‚ights, an optimization engine sifts through millions of options to ï¬nd

the cheapest fares. If you get directions to your hotel from MapQuest, another optimization engine ï¬gures out the most direct route. If you ship souvenirs home, an

optimization engine tells UPS which truck to put the packages on, exactly where on

the truck the packages should go to make them fastest to load and unload, and

what route the driver should follow to make his deliveries most efï¬ciently.

(Adapted from: V. Postrel, â€œOperation Everything,â€ The Boston Globe, June 27, 2004.)

2.2 Characteristics of

Optimization Problems

These examples represent just a few areas in which MP has been used successfully. We

will consider many other examples throughout this book. However, these examples

give you some idea of the issues involved in optimization. For instance, each example

involves one or more decisions that must be made: How many of each product should

be produced? Which hole should be drilled next? How much of each product should be

shipped from each warehouse to the various retail locations? How much money should

an individual withdraw each year from various retirement accounts?

Also, in each example, restrictions, or constraints, are likely to be placed on the alternatives available to the decision maker. In the ï¬rst example, when determining

the number of products to manufacture, a production manager probably is faced with a

limited amount of raw materials and a limited amount of labor. In the second example,

the drill never should return to a position where a hole has already been drilled. In the

Expressing Optimization Problems Mathematically

19

third example, there is a physical limitation on the amount of merchandise a truck can

carry from one warehouse to the stores on its route. In the fourth example, laws determine the minimum and maximum amounts that can be withdrawn from retirement

accounts without incurring a penalty. There might be many other constraints for these

examples. Indeed, it is not unusual for real-world optimization problems to have hundreds or thousands of constraints.

A ï¬nal common element in each of the examples is the existence of some goal or objective that the decision maker considers when deciding which course of action is best.

In the ï¬rst example, the production manager can decide to produce several different

product mixes given the available resources, but the manager probably will choose the

mix of products that maximizes proï¬ts. In the second example, a large number of possible drilling patterns can be used, but the ideal pattern probably will involve moving the

drill bit the shortest total distance. In the third example, there are numerous ways merchandise can be shipped from the warehouses to supply the stores, but the company

probably will want to identify the routing that minimizes the total transportation cost.

Finally, in the fourth example, individuals can withdraw money from their retirement

accounts in many ways without violating the tax laws, but they probably want to ï¬nd

the method that minimizes their tax liability.

2.3 Expressing Optimization

Problems Mathematically

From the preceding discussion, we know that optimization problems involve three elements: decisions, constraints, and an objective. If we intend to build a mathematical

model of an optimization problem, we will need mathematical terms or symbols to represent each of these three elements.

2.3.1 DECISIONS

The decisions in an optimization problem often are represented in a mathematical

model by the symbols X1, X2, . . . , Xn. We will refer to X1, X2, . . . , Xn as the decision

variables (or simply the variables) in the model. These variables might represent the

quantities of different products the production manager can choose to produce. They

might represent the amount of different pieces of merchandise to ship from a warehouse

to a certain store. They might represent the amount of money to be withdrawn from different retirement accounts.

The exact symbols used to represent the decision variables are not particularly important. You could use Z1, Z2, . . . , Zn or symbols like Dog, Cat, and Monkey to represent

the decision variables in the model. The choice of which symbols to use is largely a matter of personal preference and might vary from one problem to the next.

2.3.2 CONSTRAINTS

The constraints in an optimization problem can be represented in a mathematical model

in several ways. Three general ways of expressing the possible constraint relationships

in an optimization problem are:

A â€œless than or equal toâ€ constraint:

A â€œgreater than or equal toâ€ constraint:

f(X1, X2, . . . , Xn) â‰¤ b

f(X1, X2, . . . , Xn) â‰¥ b

An â€œequal toâ€ constraint:

f(X1, X2, . . . , Xn) = b

20

Chapter 2

Introduction to Optimization and Linear Programming

In each case, the constraint is some function of the decision variables that must be

less than or equal to, greater than or equal to, or equal to some speciï¬c value (represented above by the letter b). We will refer to f(X1, X2, . . . , Xn) as the left-hand-side (LHS)

of the constraint and to b as the right-hand-side (RHS) value of the constraint.

For example, we might use a â€œless than or equal toâ€ constraint to ensure that the total

labor used in producing a given number of products does not exceed the amount of

available labor. We might use a â€œgreater than or equal toâ€ constraint to ensure that the

total amount of money withdrawn from a personâ€™s retirement accounts is at least the

minimum amount required by the IRS. You can use any number of these constraints to

represent a given optimization problem depending on the requirements of the situation.

2.3.3 OBJECTIVE

The objective in an optimization problem is represented mathematically by an objective

function in the general format:

MAX (or MIN):

f(X1, X2, . . . , Xn)

The objective function identiï¬es some function of the decision variables that the decision maker wants to either MAXimize or MINimize. In our earlier examples, this function might be used to describe the total proï¬t associated with a product mix, the total

distance the drill bit must be moved, the total cost of transporting merchandise, or a

retireeâ€™s total tax liability.

The mathematical formulation of an optimization problem can be described in the

general format:

MAX (or MIN):

Subject to:

f0(X1, X2, . . . , Xn)

f1(X1, X2, . . . , Xn) â‰¤ b1

2.1

2.2

:

fk(X1, X2, . . . , Xn) â‰¥ bk

:

2.3

fm(X1, X2, . . . , Xn) = bm

2.4

This representation identiï¬es the objective function (equation 2.1) that will be

maximized (or minimized) and the constraints that must be satisï¬ed (equations 2.2

through 2.4). Subscripts added to the f and b in each equation emphasize that the

functions describing the objective and constraints can all be different. The goal in optimization is to ï¬nd the values of the decision variables that maximize (or minimize) the

objective function without violating any of the constraints.

2.4 Mathematical

Programming Techniques

Our general representation of an MP model is just thatâ€”general. You can use many

kinds of functions to represent the objective function and the constraints in an MP

model. Of course, you always should use functions that accurately describe the objective and constraints of the problem you are trying to solve. Sometimes, the functions in

a model are linear in nature (that is, they form straight lines or ï¬‚at surfaces); other times,

Formulating LP Models

21

they are nonlinear (that is, they form curved lines or curved surfaces). Sometimes, the

optimal values of the decision variables in a model must take on integer values (whole

numbers); other times, the decision variables can assume fractional values.

Given the diversity of MP problems that can be encountered, many techniques have

been developed to solve different types of MP problems. In the next several chapters, we

will look at these MP techniques and develop an understanding of how they differ and

when each should be used. We will begin by examining a technique called linear

programming (LP), which involves creating and solving optimization problems with

linear objective functions and linear constraints. LP is a very powerful tool that can be

applied in many business situations. It also forms a basis for several other techniques

discussed later and is, therefore, a good starting point for our investigation into the ï¬eld

of optimization.

2.5 An Example LP Problem

We will begin our study of LP by considering a simple example. You should not interpret this to mean that LP cannot solve more complex or realistic problems. LP has been

used to solve extremely complicated problems, saving companies millions of dollars.

However, jumping directly into one of these complicated problems would be like starting a marathon without ever having gone out for a jogâ€”you would get winded and

could be left behind very quickly. So weâ€™ll start with something simple.

Blue Ridge Hot Tubs manufactures and sells two models of hot tubs: the Aqua-Spa

and the Hydro-Lux. Howie Jones, the owner and manager of the company, needs to

decide how many of each type of hot tub to produce during his next production

cycle. Howie buys prefabricated ï¬berglass hot tub shells from a local supplier and

adds the pump and tubing to the shells to create his hot tubs. (This supplier has the

capacity to deliver as many hot tub shells as Howie needs.) Howie installs the same

type of pump into both hot tubs. He will have only 200 pumps available during his

next production cycle. From a manufacturing standpoint, the main difference between the two models of hot tubs is the amount of tubing and labor required. Each

Aqua-Spa requires 9 hours of labor and 12 feet of tubing. Each Hydro-Lux requires

6 hours of labor and 16 feet of tubing. Howie expects to have 1,566 production labor

hours and 2,880 feet of tubing available during the next production cycle. Howie

earns a proï¬t of $350 on each Aqua-Spa he sells and $300 on each Hydro-Lux he

sells. He is conï¬dent that he can sell all the hot tubs he produces. The question is,

how many Aqua-Spas and Hydro-Luxes should Howie produce if he wants to maximize his proï¬ts during the next production cycle?

2.6 Formulating LP Models

The process of taking a practical problemâ€”such as determining how many Aqua-Spas

and Hydro-Luxes Howie should produceâ€”and expressing it algebraically in the form

of an LP model is known as formulating the model. Throughout the next several chapters, you will see that formulating an LP model is as much an art as a science.

2.6.1 STEPS IN FORMULATING AN LP MODEL

There are some general steps you can follow to help make sure your formulation of a particular problem is accurate. We will walk through these steps using the hot tub example.

22

Chapter 2

Introduction to Optimization and Linear Programming

1. Understand the problem. This step appears to be so obvious that it hardly seems

worth mentioning. However, many people have a tendency to jump into a problem

and start writing the objective function and constraints before they really understand the problem. If you do not fully understand the problem you face, it is unlikely

that your formulation of the problem will be correct.

The problem in our example is fairly easy to understand: How many Aqua-Spas

and Hydro-Luxes should Howie produce to maximize his proï¬t, while using no

more than 200 pumps, 1,566 labor hours, and 2,880 feet of tubing?

2. Identify the decision variables. After you are sure you understand the problem,

you need to identify the decision variables. That is, what are the fundamental decisions that must be made to solve the problem? The answers to this question often

will help you identify appropriate decision variables for your model. Identifying the

decision variables means determining what the symbols X1, X2, . . . , Xn represent in

your model.

In our example, the fundamental decision Howie faces is this: How many AquaSpas and Hydro-Luxes should be produced? In this problem, we will let X1 represent

the number of Aqua-Spas to produce and X2 represent the number of Hydro-Luxes to

produce.

3. State the objective function as a linear combination of the decision variables.

After determining the decision variables you will use, the next step is to create the

objective function for the model. This function expresses the mathematical relationship between the decision variables in the model to be maximized or minimized.

In our example, Howie earns a proï¬t of $350 on each Aqua-Spa (X1) he sells and

$300 on each Hydro-Lux (X2) he sells. Thus, Howieâ€™s objective of maximizing the

proï¬t he earns is stated mathematically as:

MAX:

350X1 + 300X2

For whatever values might be assigned to X1 and X2, the previous function calculates the associated total proï¬t that Howie would earn. Obviously, Howie wants to

maximize this value.

4. State the constraints as linear combinations of the decision variables. As mentioned earlier, there are usually some limitations on the values that can be assumed

by the decision variables in an LP model. These restrictions must be identiï¬ed and

stated in the form of constraints.

In our example, Howie faces three major constraints. Because only 200 pumps are

available and each hot tub requires one pump, Howie cannot produce more than a

total of 200 hot tubs. This restriction is stated mathematically as:

1X1 + 1X2 â‰¤ 200

This constraint indicates that each unit of X1 produced (that is, each Aqua-Spa

built) will use one of the 200 pumps availableâ€”as will each unit of X2 produced (that

is, each Hydro-Lux built). The total number of pumps used (represented by 1X1

1X2) must be less than or equal to 200.

Another restriction Howie faces is that he has only 1,566 labor hours available

during the next production cycle. Because each Aqua-Spa he builds (each unit of X1)

requires 9 labor hours and each Hydro-Lux (each unit of X2) requires 6 labor hours,

the constraint on the number of labor hours is stated as:

9X1 6X2 â‰¤ 1,566

The General Form of an LP Model

23

The total number of labor hours used (represented by 9X1 6X2) must be less

than or equal to the total labor hours available, which is 1,566.

The ï¬nal constraint speciï¬es that only 2,880 feet of tubing is available for the next

production cycle. Each Aqua-Spa produced (each unit of X1) requires 12 feet of tubing, and each Hydro-Lux produced (each unit of X2) requires 16 feet of tubing. The

following constraint is necessary to ensure that Howieâ€™s production plan does not

use more tubing than is available:

12X1 16X2 â‰¤ 2,880

The total number of feet of tubing used (represented by 12X1 16X2) must be less

than or equal to the total number of feet of tubing available, which is 2,880.

5. Identify any upper or lower bounds on the decision variables. Often, simple upper

or lower bounds apply to the decision variables. You can view upper and lower

bounds as additional constraints in the problem.

In our example, there are simple lower bounds of zero on the variables X1 and X2

because it is impossible to produce a negative number of hot tubs. Therefore, the

following two constraints also apply to this problem:

X1 â‰¥ 0

X2 â‰¥ 0

Constraints like these are often referred to as nonnegativity conditions and are

quite common in LP problems.

2.7 Summary of the LP Model

for the Example Problem

The complete LP model for Howieâ€™s decision problem can be stated as:

MAX:

Subject to:

350X1 300X2

1X1 1X2 â‰¤ 200

9X1 6X2 â‰¤ 1,566

12X1 16X2 â‰¤ 2,880

1X1

â‰¥

0

1X2 â‰¥

0

2.5

2.6

2.7

2.8

2.9

2.10

In this model, the decision variables X1 and X2 represent the number of Aqua-Spas

and Hydro-Luxes to produce, respectively. Our goal is to determine the values for X1

and X2 that maximize the objective in equation 2.5 while simultaneously satisfying all

the constraints in equations 2.6 through 2.10.

2.8 The General Form of an LP Model

The technique of linear programming is so named because the MP problems to which it

applies are linear in nature. That is, it must be possible to express all the functions in an

24

Chapter 2

Introduction to Optimization and Linear Programming

LP model as some weighted sum (or linear combination) of the decision variables. So,

an LP model takes on the general form:

MAX (or MIN):

Subject to:

c1X1 c2X2 cnXn

a11X1 a12X2 a1nXn â‰¤ b1

:

ak1X1 ak2X2 aknXn â‰¥ bk

:

am1X1 am2X2 amnXn = bm

2.11

2.12

2.13

2.14

Up to this point, we have suggested that the constraints in an LP model represent

some type of limited resource. Although this is frequently the case, in later chapters you

will see examples of LP models in which the constraints represent things other than limited resources. The important point here is that any problem that can be formulated in

the above fashion is an LP problem.

The symbols c1, c2, . . . , cn in equation 2.11 are called objective function coefï¬cients

and might represent the marginal proï¬ts (or costs) associated with the decision variables X1, X2, . . . , Xn, respectively. The symbol aij found throughout equations 2.12

through 2.14 represents the numeric coefï¬cient in the ith constraint for variable Xj. The

objective function and constraints of an LP problem represent different weighted sums

of the decision variables. The bi symbols in the constraints, once again, represent values

that the corresponding linear combination of the decision variables must be less than or

equal to, greater than or equal to, or equal to.

You should now see a direct connection between the LP model we formulated for

Blue Ridge Hot Tubs in equations 2.5 through 2.10 and the general deï¬nition of an LP

model given in equations 2.11 through 2.14. In particular, note that the various symbols

used in equations 2.11 through 2.14 to represent numeric constants (that is, the cj, aij,

and bi) were replaced by actual numeric values in equations 2.5 through 2.10. Also,

note that our formulation of the LP model for Blue Ridge Hot Tubs did not require the

use of â€œequal toâ€ constraints. Different problems require different types of constraints,

and you should use whatever types of constraints are necessary for the problem at

hand.

2.9 Solving LP Problems:

An Intuitive Approach

After an LP model has been formulated, our interest naturally turns to solving it. But before we actually solve our example problem for Blue Ridge Hot Tubs, what do you think

is the optimal solution to the problem? Just by looking at the model, what values for X1

and X2 do you think would give Howie the largest proï¬t?

Following one line of reasoning, it might seem that Howie should produce as many

units of X1 (Aqua-Spas) as possible because each of these generates a proï¬t of $350,

whereas each unit of X2 (Hydro-Luxes) generates a proï¬t of only $300. But what is the

maximum number of Aqua-Spas that Howie could produce?

Howie can produce the maximum number of units of X1 by making no units of X2

and devoting all his resources to the production of X1. Suppose we let X2 = 0 in the

model in equations 2.5 through 2.10 to indicate that no Hydro-Luxes will be produced.

Solving LP Problems: A Graphical Approach

25

What then is the largest possible value of X1? If X2 = 0, then the inequality in equation 2.6 tells us:

X1 â‰¤ 200

2.15

So we know that X1 cannot be any greater than 200 if X2 = 0. However, we also have

to consider the constraints in equations 2.7 and 2.8. If X2 = 0, then the inequality in

equation 2.7 reduces to:

9X1 â‰¤ 1,566

2.16

If we divide both sides of this inequality by 9, we ï¬nd that the previous constraint is

equivalent to:

X1 â‰¤ 174

2.17

Now consider the constraint in equation 2.8. If X2 = 0, then the inequality in equation 2.8 reduces to:

12X1 â‰¤ 2,880

2.18

Again, if we divide both sides of this inequality by 12, we ï¬nd that the previous

constraint is equivalent to:

X1 â‰¤ 240

2.19

So, if X2 = 0, the three constraints in our model imposing upper limits on the value of

X1 reduce to the values shown in equations 2.15, 2.17, and 2.19. The most restrictive of

these constraints is equation 2.17. Therefore, the maximum number of units of X1 that

can be produced is 174. In other words, 174 is the largest value X1 can take on and still

satisfy all the constraints in the model.

If Howie builds 174 units of X1 (Aqua-Spas) and 0 units of X2 (Hydro-Luxes), he will

have used all of the labor that is available for production (9X1 = 1,566 if X1 = 174). However, he will have 26 pumps remaining (200 X1 = 26 if X1 = 174) and 792 feet of tubing remaining (2,880 12X1 = 792 if X1 = 174). Also, notice that the objective function

value (or total proï¬t) associated with this solution is:

$350X1 $300X2 = $350 174 $300 0 = $60,900

From this analysis, we see that the solution X1 = 174, X2 = 0 is a feasible solution to the

problem because it satisï¬es all the constraints of the model. But is it the optimal solution?

In other words, is there any other possible set of values for X1 and X2 that also satisï¬es

all the constraints and results in a higher objective function value? As you will see, the

intuitive approach to solving LP problems that we have taken here cannot be trusted

because there actually is a better solution to Howieâ€™s problem.

2.10 Solving LP Problems:

A Graphical Approach

The constraints of an LP model deï¬ne the set of feasible solutionsâ€”or the feasible

regionâ€”for the problem. The difï¬culty in LP is determining which point or points in

the feasible region correspond to the best possible value of the objective function. For

simple problems with only two decision variables, it is fairly easy to sketch the feasible

region for the LP model and locate the optimal feasible point graphically. Because the

graphical approach can be used only if there are two decision variables, it has limited

practical use. However, it is an extremely good way to develop a basic understanding of

26

Chapter 2

Introduction to Optimization and Linear Programming

the strategy involved in solving LP problems. Therefore, we will use the graphical approach to solve the simple problem faced by Blue Ridge Hot Tubs. Chapter 3 shows how

to solve this and other LP problems using a spreadsheet.

To solve an LP problem graphically, ï¬rst you must plot the constraints for the problem and identify its feasible region. This is done by plotting the boundary lines of the constraints and identifying the points that will satisfy all the constraints. So, how do we do

this for our example problem (repeated below)?

MAX:

Subject to:

350X1 300X2

1X1 1X2 â‰¤ 200

9X1 6X2 â‰¤ 1,566

12X1 16X2 â‰¤ 2,880

1X1

â‰¥

0

1X2 â‰¥

0

2.20

2.21

2.22

2.23

2.24

2.25

2.10.1 PLOTTING THE FIRST CONSTRAINT

The boundary of the ï¬rst constraint in our model, which speciï¬es that no more than

200 pumps can be used, is represented by the straight line deï¬ned by the equation:

X1 X2 = 200

2.26

If we can ï¬nd any two points on this line, the entire line can be plotted easily by

drawing a straight line through these points. If X2 = 0, we can see from equation 2.26

that X1 = 200. Thus, the point (X1, X2) = (200, 0) must fall on this line. If we let X1 = 0,

from equation 2.26, it is easy to see that X2 = 200. So, the point (X1, X2) = (0, 200) also

must fall on this line. These two points are plotted on the graph in Figure 2.1 and connected to form the straight line representing equation 2.26.

Note that the graph of the line associated with equation 2.26 actually extends beyond

the X1 and X2 axes shown in Figure 2.1. However, we can disregard the points beyond

these axes because the values assumed by X1 and X2 cannot be negative (because we also

have the constraints given by X1 â‰¥ 0 and X2 â‰¥ 0).

The line connecting the points (0, 200) and (200, 0) in Figure 2.1 identiï¬es the points

(X1, X2) that satisfy the equality X1 X2 = 200. But recall that the ï¬rst constraint in the

LP model is the inequality X1 X2 â‰¤ 200. Thus, after plotting the boundary line of a constraint, we must determine which area on the graph corresponds to feasible solutions

for the original constraint. This can be done easily by picking an arbitrary point on

either side of (i.e., not on) the boundary line and checking whether it satisï¬es the original constraint. For example, the point (X1, X2) = (0, 0) is not on the boundary line of the

ï¬rst constraint and also satisï¬es the ï¬rst constraint. Therefore, the area of the graph on

the same side of the boundary line as the point (0, 0) c…

Purchase answer to see full

attachment