Statistic Help

undiscoveredpromise

wk_7_stat_file.ppt

Home >Mathematics homework help >Statistic Help

Spreadsheet Modeling
& Decision Analysis

A Practical Introduction to Management Science

5th edition

Cliff T. Ragsdale

Modeling and Solving LP Problems in a Spreadsheet

Chapter 3

Introduction

Solving LP problems graphically is only possible when there are two decision variables
Few real-world LP have only two decision variables
Fortunately, we can now use spreadsheets to solve LP problems

Spreadsheet Solvers

The company that makes the Solver in Excel, Lotus 1-2-3, and Quattro Pro is Frontline Systems, Inc.

Check out their web site:

http://www.solver.com

Other packages for solving MP problems:

AMPL LINDO

CPLEX MPSX

The Steps in Implementing an LP Model in a Spreadsheet

1. Organize the data for the model on the spreadsheet.

2. Reserve separate cells in the spreadsheet for each decision variable in the model.

3. Create a formula in a cell in the spreadsheet that corresponds to the objective function.

4. For each constraint, create a formula in a separate cell in the spreadsheet that corresponds to the left-hand side (LHS) of the constraint.

Let’s Implement a Model for the
Blue Ridge Hot Tubs Example...

MAX: 350X1 + 300X2 } profit

S.T.: 1X1 + 1X2 <= 200 } pumps

9X1 + 6X2 <= 1566 } labor

12X1 + 16X2 <= 2880 } tubing

X1, X2 >= 0 } nonnegativity

Implementing the Model

See file Fig3-1.xls

How Solver Views the Model

Target cell - the cell in the spreadsheet that represents the objective function
Changing cells - the cells in the spreadsheet representing the decision variables
Constraint cells - the cells in the spreadsheet representing the LHS formulas on the constraints

Let’s go back to Excel and see how Solver works...

Goals For Spreadsheet Design

Communication - A spreadsheet's primary business purpose is communicating information to managers.
Reliability - The output a spreadsheet generates should be correct and consistent.
Auditability - A manager should be able to retrace the steps followed to generate the different outputs from the model in order to understand and verify results.
Modifiability - A well-designed spreadsheet should be easy to change or enhance in order to meet dynamic user requirements.

Spreadsheet Design Guidelines - I

Organize the data, then build the model around the data.
Do not embed numeric constants in formulas.
Things which are logically related should be physically related.
Use formulas that can be copied.
Column/rows totals should be close to the columns/rows being totaled.

Spreadsheet Design Guidelines - II

The English-reading eye scans left to right, top to bottom.
Use color, shading, borders and protection to distinguish changeable parameters from other model elements.
Use text boxes and cell notes to document various elements of the model.

Make vs. Buy Decisions:
The Electro-Poly Corporation

Electro-Poly is a leading maker of slip-rings.
A $750,000 order has just been received.

The company has 10,000 hours of wiring capacity and 5,000 hours of harnessing capacity.

Model 1 Model 2 Model 3

Number ordered 3,000 2,000 900

Hours of wiring/unit 2 1.5 3

Hours of harnessing/unit 1 2 1

Cost to Make $50 $83 $130

Cost to Buy $61 $97 $145

Defining the Decision Variables

M1 = Number of model 1 slip rings to make in-house

M2 = Number of model 2 slip rings to make in-house

M3 = Number of model 3 slip rings to make in-house

B1 = Number of model 1 slip rings to buy from competitor

B2 = Number of model 2 slip rings to buy from competitor

B3 = Number of model 3 slip rings to buy from competitor

Defining the Objective Function

Minimize the total cost of filling the order.

MIN: 50M1+ 83M2+ 130M3+ 61B1+ 97B2+ 145B3

Defining the Constraints

Demand Constraints

M1 + B1 = 3,000 } model 1

M2 + B2 = 2,000 } model 2

M3 + B3 = 900 } model 3

Resource Constraints

2M1 + 1.5M2 + 3M3 <= 10,000 } wiring

1M1 + 2.0M2 + 1M3 <= 5,000 } harnessing

Nonnegativity Conditions

M1, M2, M3, B1, B2, B3 >= 0

Implementing the Model

See file Fig3-17.xls

An Investment Problem:
Retirement Planning Services, Inc.

A client wishes to invest $750,000 in the following bonds.

Years to

Company Return Maturity Rating

Acme Chemical 8.65% 11 1-Excellent

DynaStar 9.50% 10 3-Good

Eagle Vision 10.00% 6 4-Fair

Micro Modeling 8.75% 10 1-Excellent

OptiPro 9.25% 7 3-Good

Sabre Systems 9.00% 13 2-Very Good

Investment Restrictions

No more than 25% can be invested in any single company.
At least 50% should be invested in long-term bonds (maturing in 10+ years).
No more than 35% can be invested in DynaStar, Eagle Vision, and OptiPro.

Defining the Decision Variables

X1 = amount of money to invest in Acme Chemical

X2 = amount of money to invest in DynaStar

X3 = amount of money to invest in Eagle Vision

X4 = amount of money to invest in MicroModeling

X5 = amount of money to invest in OptiPro

X6 = amount of money to invest in Sabre Systems

Defining the Objective Function

Maximize the total

annual investment return:

MAX: .0865X1+ .095X2+ .10X3+ .0875X4+ .0925X5+ .09X6

Defining the Constraints

Total amount is invested

X1 + X2 + X3 + X4 + X5 + X6 = 750,000

No more than 25% in any one investment

Xi <= 187,500, for all i

50% long term investment restriction.

X1 + X2 + X4 + X6 >= 375,000

35% Restriction on DynaStar, Eagle Vision, and OptiPro.

X2 + X3 + X5 <= 262,500

Nonnegativity conditions

Xi >= 0 for all i

Implementing the Model

See file Fig3-20.xls

A Transportation Problem: Tropicsun

Mt. Dora

Eustis

Clermont

Ocala

Orlando

Leesburg

Distances (in miles)

Capacity

Supply

275,000

400,000

300,000

225,000

600,000

200,000

Groves

Processing

Plants

Defining the Decision Variables

Xij = # of bushels shipped from node i to node j

Specifically, the nine decision variables are:

X14 = # of bushels shipped from Mt. Dora (node 1) to Ocala (node 4)

X15 = # of bushels shipped from Mt. Dora (node 1) to Orlando (node 5)

X16 = # of bushels shipped from Mt. Dora (node 1) to Leesburg (node 6)

X24 = # of bushels shipped from Eustis (node 2) to Ocala (node 4)

X25 = # of bushels shipped from Eustis (node 2) to Orlando (node 5)

X26 = # of bushels shipped from Eustis (node 2) to Leesburg (node 6)

X34 = # of bushels shipped from Clermont (node 3) to Ocala (node 4)

X35 = # of bushels shipped from Clermont (node 3) to Orlando (node 5)

X36 = # of bushels shipped from Clermont (node 3) to Leesburg (node 6)

Defining the Objective Function

Minimize the total number of bushel-miles.

MIN: 21X14 + 50X15 + 40X16 +

35X24 + 30X25 + 22X26 +

55X34 + 20X35 + 25X36

Defining the Constraints

Capacity constraints

X14 + X24 + X34 <= 200,000 } Ocala

X15 + X25 + X35 <= 600,000 } Orlando

X16 + X26 + X36 <= 225,000 } Leesburg

Supply constraints

X14 + X15 + X16 = 275,000 } Mt. Dora

X24 + X25 + X26 = 400,000 } Eustis

X34 + X35 + X36 = 300,000 } Clermont

Nonnegativity conditions

Xij >= 0 for all i and j

Implementing the Model

See file Fig3-24.xls

A Blending Problem:
The Agri-Pro Company

Agri-Pro has received an order for 8,000 pounds of chicken feed to be mixed from the following feeds.

The order must contain at least 20% corn, 15% grain, and 15% minerals.

Nutrient Feed 1 Feed 2 Feed 3 Feed 4

Corn 30% 5% 20% 10%

Grain 10% 3% 15% 10%

Minerals 20% 20% 20% 30%

Cost per pound $0.25 $0.30 $0.32 $0.15

Percent of Nutrient in

Defining the Decision Variables

X1 = pounds of feed 1 to use in the mix

X2 = pounds of feed 2 to use in the mix

X3 = pounds of feed 3 to use in the mix

X4 = pounds of feed 4 to use in the mix

Defining the Objective Function

Minimize the total cost of filling the order.

MIN: 0.25X1 + 0.30X2 + 0.32X3 + 0.15X4

Defining the Constraints

Produce 8,000 pounds of feed

X1 + X2 + X3 + X4 = 8,000

Mix consists of at least 20% corn

(0.3X1 + 0.5X2 + 0.2X3 + 0.1X4)/8000 >= 0.2

Mix consists of at least 15% grain

(0.1X1 + 0.3X2 + 0.15X3 + 0.1X4)/8000 >= 0.15

Mix consists of at least 15% minerals

(0.2X1 + 0.2X2 + 0.2X3 + 0.3X4)/8000 >= 0.15

Nonnegativity conditions

X1, X2, X3, X4 >= 0

A Comment About Scaling

Notice the coefficient for X2 in the ‘corn’ constraint is 0.05/8000 = 0.00000625
As Solver runs, intermediate calculations are made that make coefficients larger or smaller.
Storage problems may force the computer to use approximations of the actual numbers.
Such ‘scaling’ problems sometimes prevents Solver from being able to solve the problem accurately.
Most problems can be formulated in a way to minimize scaling errors...

Re-Defining the Decision Variables

X1 = thousands of pounds of feed 1 to use in the mix

X2 = thousands of pounds of feed 2 to use in the mix

X3 = thousands of pounds of feed 3 to use in the mix

X4 = thousands of pounds of feed 4 to use in the mix

Re-Defining the
Objective Function

Minimize the total cost of filling the order.

MIN: 250X1 + 300X2 + 320X3 + 150X4

Re-Defining the Constraints

Produce 8,000 pounds of feed

X1 + X2 + X3 + X4 = 8

Mix consists of at least 20% corn

(0.3X1 + 0.5X2 + 0.2X3 + 0.1X4)/8 >= 0.2

Mix consists of at least 15% grain

(0.1X1 + 0.3X2 + 0.15X3 + 0.1X4)/8 >= 0.15

Mix consists of at least 15% minerals

(0.2X1 + 0.2X2 + 0.2X3 + 0.3X4)/8 >= 0.15

Nonnegativity conditions

X1, X2, X3, X4 >= 0

Scaling: Before and After

Before:

Largest constraint coefficient was 8,000

Smallest constraint coefficient was

0.05/8 = 0.00000625.

After:

Largest constraint coefficient is 8

Smallest constraint coefficient is

0.05/8 = 0.00625.

The problem is now more evenly scaled!

The Assume Linear Model Option

The Solver Options dialog box has an option labeled “Assume Linear Model”.
This option makes Solver perform some tests to verify that your model is in fact linear.
These test are not 100% accurate & may fail as a result of a poorly scaled model.
If Solver tells you a model isn’t linear when you know it is, try solving it again. If that doesn’t work, try re-scaling your model.

Implementing the Model

See file Fig3-28.xls

A Production Planning Problem:
The Upton Corporation

Upton is planning the production of their heavy-duty air compressors for the next 6 months.

Beginning inventory = 2,750 units

Safety stock = 1,500 units

Unit carrying cost = 1.5% of unit production cost

Maximum warehouse capacity = 6,000 units

1 2 3 4 5 6

Unit Production Cost $240 $250 $265 $285 $280 $260

Units Demanded 1,000 4,500 6,000 5,500 3,500 4,000

Maximum Production 4,000 3,500 4,000 4,500 4,000 3,500

Minimum Production 2,000 1,750 2,000 2,250 2,000 1,750

Month

Defining the Decision Variables

Pi = number of units to produce in month i, i=1 to 6

Bi = beginning inventory month i, i=1 to 6

Defining the Objective Function

Minimize the total cost production

& inventory costs.

MIN: 240P1+250P2+265P3+285P4+280P5+260P6

+ 3.6(B1+B2)/2 + 3.75(B2+B3)/2 + 3.98(B3+B4)/2

+ 4.28(B4+B5)/2 + 4.20(B5+ B6)/2 + 3.9(B6+B7)/2

Note: The beginning inventory in any month is the same as the ending inventory in the previous month.

Defining the Constraints - I

Production levels

2,000 <= P1 <= 4,000 } month 1

1,750 <= P2 <= 3,500 } month 2

2,000 <= P3 <= 4,000 } month 3

2,250 <= P4 <= 4,500 } month 4

2,000 <= P5 <= 4,000 } month 5

1,750 <= P6 <= 3,500 } month 6

Defining the Constraints - II

Ending Inventory (EI = BI + P - D)

1,500 < B1 + P1 - 1,000 < 6,000 } month 1

1,500 < B2 + P2 - 4,500 < 6,000 } month 2

1,500 < B3 + P3 - 6,000 < 6,000 } month 3

1,500 < B4 + P4 - 5,500 < 6,000 } month 4

1,500 < B5 + P5 - 3,500 < 6,000 } month 5

1,500 < B6 + P6 - 4,000 < 6,000 } month 6

Defining the Constraints - III

Beginning Balances

B1 = 2750

B2 = B1 + P1 - 1,000

B3 = B2 + P2 - 4,500

B4 = B3 + P3 - 6,000

B5 = B4 + P4 - 5,500

B6 = B5 + P5 - 3,500

B7 = B6 + P6 - 4,000

Notice that the Bi can be computed directly from the Pi. Therefore, only the Pi need to be identified as changing cells.

Implementing the Model

See file Fig3-31.xls

A Multi-Period Cash Flow Problem:
The Taco-Viva Sinking Fund - I

Taco-Viva needs a sinking fund to pay $800,000 in building costs for a new restaurant in the next 6 months.
Payments of $250,000 are due at the end of months 2 and 4, and a final payment of $300,000 is due at the end of month 6.
The following investments may be used.

Investment Available in Month Months to Maturity Yield at Maturity

A 1, 2, 3, 4, 5, 6 1 1.8%

B 1, 3, 5 2 3.5%

C 1, 4 3 5.8%

D 1 6 11.0%

Summary of Possible Cash Flows

Investment 1 2 3 4 5 6 7

A1 -1 1.018

B1 -1 <_____> 1.035

C1 -1 <_____> <_____> 1.058

D1 -1 <_____> <_____> <_____> <_____> <_____> 1.11

A2 -1 1.018

A3 -1 1.018

B3 -1 <_____> 1.035

A4 -1 1.018

C4 -1 <_____> <_____> 1.058

A5 -1 1.018

B5 -1 <_____> 1.035

A6 -1 1.018

Req’d Payments $0 $0 $250 $0 $250 $0 $300

(in $1,000s)

Cash Inflow/Outflow at the Beginning of Month

Defining the Decision Variables

Ai = amount (in $1,000s) placed in investment A at the beginning of month i=1, 2, 3, 4, 5, 6

Bi = amount (in $1,000s) placed in investment B at the beginning of month i=1, 3, 5

Ci = amount (in $1,000s) placed in investment C at the beginning of month i=1, 4

Di = amount (in $1,000s) placed in investment D at the beginning of month i=1

Defining the Objective Function

Minimize the total cash invested in month 1.

MIN: A1 + B1 + C1 + D1

Defining the Constraints

Cash Flow Constraints

1.018A1 – 1A2 = 0 } month 2

1.035B1 + 1.018A2 – 1A3 – 1B3 = 250 } month 3

1.058C1 + 1.018A3 – 1A4 – 1C4 = 0 } month 4

1.035B3 + 1.018A4 – 1A5 – 1B5 = 250 } month 5

1.018A5 –1A6 = 0 } month 6

1.11D1 + 1.058C4 + 1.035B5 + 1.018A6 = 300 } month 7

Nonnegativity Conditions

Ai, Bi, Ci, Di >= 0, for all i

Implementing the Model

See file Fig3-35.xls

Risk Management:
The Taco-Viva Sinking Fund - II

Assume the CFO has assigned the following risk ratings to each investment on a scale from 1 to 10 (10 = max risk)

Investment Risk Rating

A 1

B 3

C 8

D 6

The CFO wants the weighted average risk to not exceed 5.

Defining the Constraints

Risk Constraints

1A1 + 3B1 + 8C1 + 6D1

< 5

A1 + B1 + C1 + D1

} month 1

1A2 + 3B1 + 8C1 + 6D1

< 5

A2 + B1 + C1 + D1

} month 2

1A3 + 3B3 + 8C1 + 6D1

< 5

A3 + B3 + C1 + D1

} month 3

1A4 + 3B3 + 8C4 + 6D1

< 5

A4 + B3 + C4 + D1

} month 4

1A5 + 3B5 + 8C4 + 6D1

< 5

A5 + B5 + C4 + D1

} month 5

1A6 + 3B5 + 8C4 + 6D1

< 5

A6 + B5 + C4 + D1

} month 6

An Alternate Version of the Risk Constraints

Equivalent Risk Constraints

-4A1 – 2B1 + 3C1 + 1D1 < 0 } month 1

-2B1 + 3C1 + 1D1 – 4A2 < 0 } month 2

3C1 + 1D1 – 4A3 – 2B3 < 0 } month 3

1D1 – 2B3 – 4A4 + 3C4 < 0 } month 4

1D1 + 3C4 – 4A5 – 2B5 < 0 } month 5

1D1 + 3C4 – 2B5 – 4A6 < 0 } month 6

Note that each coefficient is equal to the risk factor for the investment minus 5 (the max. allowable weighted average risk).

Implementing the Model

See file Fig3-38.xls

Data Envelopment Analysis (DEA):
Steak & Burger

Steak & Burger needs to evaluate the performance (efficiency) of 12 units.
Outputs for each unit (Oij) include measures of: Profit, Customer Satisfaction, and Cleanliness
Inputs for each unit (Iij) include: Labor Hours, and Operating Costs
The “Efficiency” of unit i is defined as follows:

Weighted sum of unit i’s outputs

Weighted sum of unit i’s inputs

Defining the Decision Variables

wj = weight assigned to output j

vj = weight assigned to input j

A separate LP is solved for each unit, allowing each unit to select the best possible weights for itself.

Defining the Objective Function

Maximize the weighted output for unit i :

MAX:

Defining the Constraints

Efficiency cannot exceed 100% for any unit

Sum of weighted inputs for unit i must equal 1

Nonnegativity Conditions

wj, vj >= 0, for all j

Important Point

When using DEA, output variables should be expressed on a scale where “more is better” and input variables should be expressed on a scale where “less is better”.

Implementing the Model

See file Fig3-41.xls

Analyzing The Solution

See file Fig3-48.xls

End of Chapter 3





jij





jij

units ofnumber the to1 ,

1 1



 

 

kvIwO

jkjjkj







jij