Excel solver objective cell values do not converge

Chapter 13: Linear Optimization – Part 2

Lan Wang

CSU East Bay

Linear Programming (LP) Problems

MAX (or MIN): c1X1 + c2X2 + … + cnXn

Subject to: a11X1 + a12X2 + … + a1nXn <= b1

:

ak1X1 + ak2X2 + … + aknXn >=bk

:

am1X1 + am2X2 + … + amnXn = bm

Developing an Optimization Model (Formulation)

Formulation in plain business language:

1. Understand the problem.

2. Identify the decision variables.

3. Identify the objective that need to be minimized or maximized

4. Identify/list the constraints

5. Organize the data required to make decisions

Writing the model in Mathematical form:

6. Write the objective function as a linear combination of the decision variables and the data.

7. Write the constraint functions as a linear combination of the decision variables and the data.

Example: Sklenka Ski Company

Sklenka Ski Company (SSC) is a small manufacturer of two types of popular all-terrain snow skis, the Jordanelle and Deercrest models.

The manufacturing process consists of two principal departments: fabrication and finishing. The fabrication department has 12 skilled workers, each of whom works 7 hours per day. The finishing department has three workers, who also work a 7-hour shift.

Each pair of Jordanelle skis requires 3.5 labor hours in the fabricating department and one labor hour in finishing. The Deercrest model requires four labor hours in fabricating and 1.5 labor hours in finishing. The company operates five days per week.

SSC makes a net profit of $50 on the Jordanelle model, and $65 on the Deercrest model. In anticipation of the next ski sale season, SSC must plan its production of these two models. Because of the popularity of its products and limited production capacity, its products are in high demand and SSC can sell all it can produce each season. The company anticipates that the demand of Deercrest models is at least twice of the demand of Jordanelle models. The company wants to determine how many of each model should be produced on a daily basis to maximize net profit.

Optimization Model

What are the decisions that need to be made here?

How many of each model should be produced on a daily basis

What is the objective?

Maximize Total Profit = 50 Jordanelle + 65 Deercrest

What are the constraints?

Total labor used ≤ the amount of labor available

3.5 Jordanelle + 4 Deercrest ≤ 84 (fabrication)

1 Jordanelle + 1.5 Deercrest ≤ 21 (finishing)

Number of pairs of Deercrest skis must be at least twice the number of Jordanelle skis

Deercrest - 2 Jordanelle ≥ 0

Nonnegativity

Deercrest ≥ 0, Jordanelle ≥ 0

Define X1 as Jordanelle, X2 as Deercrest

The mathematical model:

Maximize Total Profit = 50 X1 + 65 X2

Subject to

3.5 X1 + 4 X2 ≤ 84 (fabrication)

1 X1 + 1.5 X2 ≤ 21 (finishing)

X2 - 2 X1 ≥ 0

X2 ≥ 0, X1 ≥ 0

Challenge question A Transportation Problem: Tropicsun

Mt. Dora

1

Eustis

2

Clermont

3

Ocala

4

Orlando

5

Leesburg

6

Distances (in miles)

Capacity

Supply

275,000

Bushels of citrus

400,000

300,000

225,000

600,000

200,000

Groves

Processing

Plants

21

50

40

35

30

22

55

25

20

7

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)

8

Defining the Objective Function

Minimize the total number of bushel-miles.

MIN: 21X14 + 50X15 + 40X16 +

35X24 + 30X25 + 22X26 +

55X34 + 20X35 + 25X36

9

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

Non-negativity conditions

Xij >= 0 for all i and j

10

Solver in Excel

Build-in Solvers in Excel is enough for us. Resources are provided just for your reference. 

http://www.meiss.com/download/Spreadsheet-Optimization-Solver.pdf

Mac User

http://www.solver.com/welcome-mac-users-solver-now-included-excel-2011

Tool -> Addins-> Solver

Then, Solver under Data tab.

PC Users

https://support.office.com/en-us/article/Load-the-Solver-Add-in-612926fc-d53b-46b4-872c-e24772f078ca?CorrelationId=506e24a9-65be-478b-b61d-3c906a543eff&ui=en-US&rs=en-US&ad=US

Excel Options-> Addins->Solver

11

The Steps in Implementing an LP Model in a Spreadsheet

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

Maintain primary data and use formulas to calculate coefficients that are needed for LP formulation.

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.

12

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.

13

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.

14

Example: Sklenka Ski Company

Sklenka Ski Company (SSC) is a small manufacturer of two types of popular all-terrain snow skis, the Jordanelle and Deercrest models.

The manufacturing process consists of two principal departments: fabrication and finishing. The fabrication department has 12 skilled workers, each of whom works 7 hours per day. The finishing department has three workers, who also work a 7-hour shift.

Each pair of Jordanelle skis requires 3.5 labor hours in the fabricating department and one labor hour in finishing. The Deercrest model requires four labor hours in fabricating and 1.5 labor hours in finishing. The company operates five days per week.

SSC makes a net profit of $50 on the Jordanelle model, and $65 on the Deercrest model. In anticipation of the next ski sale season, SSC must plan its production of these two models. Because of the popularity of its products and limited production capacity, its products are in high demand and SSC can sell all it can produce each season. The company anticipates selling at least twice as many Deercrest models as Jordanelle models. The company wants to determine how many of each model should be produced on a daily basis to maximize net profit.

Optimization Model

What are the decisions that need to be made here?

How many of each model should be produced on a daily basis

What is the objective?

Maximize Total Profit = 50 Jordanelle + 65 Deercrest

What are the constraints?

Total labor used ≤ the amount of labor available

3.5 Jordanelle + 4 Deercrest ≤ 84 (fabrication)

1 Jordanelle + 1.5 Deercrest ≤ 21 (finishing)

Number of pairs of Deercrest skis must be at least twice the number of Jordanelle skis

Deercrest - 2 Jordanelle ≥ 0

Nonnegativity

Deercrest ≥ 0, Jordanelle ≥ 0

Define X1 as Jordanelle, X2 as Deercrest

The mathematical model:

Maximize Total Profit = 50 X1 + 65 X2

Subject to

3.5 X1 + 4 X2 ≤ 84 (fabrication)

1 X1 + 1.5 X2 ≤ 21 (finishing)

X2 - 2 X1 ≥ 0

X2 ≥ 0, X1 ≥ 0

Let’s Implement a Model for this Example...

Steps in Implementing an LP Model in a Spreadsheet

1. Set up a logical format and 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.

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

Avoid Excel functions ABS, MIN, MAX, INT, ROUND, IF, COUNT

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

Spreadsheet Design Guidelines

Organize the data, then build the model around the data.

Try not to embed numeric constants in formulas.

Things which are logically related should be physically related.

Use formulas that can be copied.

Column/row totals should be close to the columns/rows being totaled.

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.

Sklenka Skis

Using Standard Solver

Add Constraint Dialog

Solver Results Dialog

Select reports to save

Solver Solution

Video demo

The following is a video link showing how to use Solver in Excel to solve the Linear Programing problem (ski example).

http://youtu.be/2tt7mPb-kgg

Definitions

Feasible solution: any solution that satisfies all constraints

A problem that has no feasible solutions is called infeasible.

Possible Outcomes

Unique optimal solution

Alternate optimal solution

Unbounded problem

“The Set Cell values do not converge”

Infeasible problem

“Solver could not find a feasible solution”

In-class practice Happy Pet Example

The Happy Pet pet food company produces dog and cat food. Each food is comprised of meat, soybeans and fillers. The company earns a profit on each product but there is a limited demand for them.

The pounds of ingredients required and available, profits and demand are summarized in the following table. The company wants to plan their product mix in order to maximize profit .

27

Product Profit per Bag ($) Demand for product Pounds of Meat per bag Pounds of Soybeans per bag Pounds of Filler per bag
Dog food 4 40 4 6 4
Cat food 5 30 5 3 10
Material available (pounds) 100 120 160
28

Mathematical Problem

X1 = bags of Dog food to produce

X2 = bags of Cat food to produce

MAX: 4 X1 + 5 X2

Subject to: 4 X1 + 5 X2 ≤100 (meat)

6 X1 + 3 X2 ≤120 (soybeans)

4 X1 + 10 X2 ≤ 160 (filler)

X1 ≤ 40 (Dog food demand)

X2 ≤ 30 (Cat food demand)

X1,X2 (nonnegativity)

29

Team Project

1. please formulate this problem. Show the definition of decision variables, objective functions, and constraints.

2. please using Solver to solve this problem.

3. what is the optimal solution?

Innis Investments manages funds for a number of companies and wealthy clients. The investment strategy is tailored to each client’s needs. For a new client, Innis has been authorized to invest up to $1.2 million in two investment funds: a stock fund and a money market fund. Each unit of the stock fund costs $50 and provides an annual rate of return of 10%; each unit of the money market fund costs $100 and provides an annual rate of return of 4%.

The client wants to minimize risk subject to the requirement that the annual income from the investment be at least $60,000. According to Innis’s risk measurement system, each unit invested in the stock fund has a risk index of 8, and each unit invested in the money market fund has a risk index of 3; the higher risk index associated with the stock fund simply indicates that it is the riskier investment. Innis’s client has also specified that at least $300,000 be invested in the money market fund.

Challenging Questions LP Model Formulation & Solution Innis Investment

31