此课程是为影响转变数据成为更好的决定的想法而设计。最近在数据采集技术上的显著提升改变了公司进行有效决定的方式。

Loading...

来自 University of Pennsylvania 的课程

运营分析

个评分

此课程是为影响转变数据成为更好的决定的想法而设计。最近在数据采集技术上的显著提升改变了公司进行有效决定的方式。

从本节课中

Prescriptive Analytics, Low Uncertainty

In this module, you'll learn how to identify the best decisions in settings with low uncertainty by building optimization models and applying them to specific business challenges. During the week, you’ll use algebraic formulations to concisely express optimization problems, look at how algebraic models should be converted into a spreadsheet format, and learn how to use spreadsheet Solvers as tools for identifying the best course of action.

- Senthil VeeraraghavanAssociate Professor of Operations, Information and Decisions

The Wharton School - Sergei SavinAssociate Professor of Operations, Information and Decisions

The Wharton School - Noah GansAnheuser-Busch Professor of Management Science, Professor of Operations, Information and Decisions

The Wharton School

Hi, I'm Sergei Sav and

we're starting session two of the second week of Operations and Litics course.

In session one, we have looked at the Zooter example,

a resource allocation problem in which limited resources

must be allocated among two competing products in the most profitable way.

We have identified the three main components of the optimization model.

Decision variables, an objective function, and constraints.

We have also written down an algebraic formulation of this other problem.

In this session, we'll create a spreadsheet formulation of the model, and

find the best decision using the Solver Optimization tool.

Okay, in session two,

we will take an algebraic model we put together in session one.

Express it in the spreadsheet terms, and we'll use Solver to optimize it.

As a reminder, here's the algebraic model of the Zooter problem.

We have the decision variables, R,

the number of razor scooters to produce, and N, the number of scooters to produce.

The objective function which is the profit, 150 x R + 160 x N, that we want

to maximize any constraints on available resources and on our decision variables.

As I mentioned Solver will be our weapon of choice.

So what is Solver?

Solver is a standard Excel editing Windows and

it is available on later versions of Excel for Mac.

If you use Mac, we have a link that explains the details for you.

If you use Google Sheets,

a version of the Solver is available as the so-called add-on.

Okay, this is my Excel template Zooter_0.

It is posted on our site, so you can open it now and

follow the steps I'm going through.

Here in the zero version, we have put in the problem data,

and also pasted in a copy of the algebraic model so it'll be easier

to make comparisons between the algebraic and the spreadsheet formulations.

We will do the model step by step and

then we will use the solver to find the best production plan for Zooter.

To go over this example, we will use Excel 2013 on the Windows platform.

If you're using Mac or Google Sheets instead,

you should still look at the steps we're following here first.

Before we build the model, let's figure out where to find the Solver.

The Solver's is called Excel add in.

We're not in Excel 2013 and in this version of Excel, the Solver's located

under the tab called Data in the portion of the tab called Analysis.

Here's my Solver button.

If your setup is just like mine and

you see the silver button there, you're good to go.

If you do not see the silver button,

then you should go to File > Options > Add Ins.

And here at the bottom where it says Manage Excel Add Ins, you click Go,

and you wanna make sure that the Solver Add In is checked.

You click OK, and the Solver should appear here on the Data tab.

In the early versions of Excel, the steps you need to take may be different but

in any case just keep in mind the Solver is an Excel add in.

Find where the add ins are in your version of Excel and

make sure that the Solver is selected.

Okay we're now ready to set up our model.

For this first example we will proceed in a very detailed manner to make sure that

we cover every important aspect of the model setup, and

of the solver functionality.

Now we need to translate our algebraic model into a spreadsheet formulation.

In other words, we need to describe on the spreadsheet

three key components of an optimization model.

Decision variables, an objective function, and constraints.

Let's start with the decision variables.

In the Zooter problem we have two products, Razor and Navajo scooters.

So let's create cells that will hold the values for

each type of scooter to be produced.

Let's say we select cell C10 and D10 for this purpose.

C10 will hold the value of the number of Razor scooters to be produced,

that is the value of the decision variable R.

And D10 will be reserved for the number of Navajo scooters.

That is, the value of the decision variable N.

Let us put the header in cell A10, units to make,

and let's add some trial values In cells C10 and

T10 to make sure that those cells are not empty.

Say let's consider producing 500 units of each scooter type.

One last thing, let's highlight the decision variable cells by

using the blue color and bold font, and by putting a frame around them.

[SOUND] Of course whether you do this embellishment or

not is completely up to you.

It will not effect the optimization but if you do,

the decision variables will be easily recognizable as soon as

the Excel file is opened and this will make you're file easier to navigate.

We have to find results to hold our decision variable values.

Later, we'll point the cells out to Solver and ask the Solver to chang

the values in cell C10 and D10 to identify the best possible production plan.

Okay, we're done with the decision variables and are now ready for

the objective function.

The objective in this model is the total profit.

So we should be able to calculate how much profit Zooter will be making for

any values of the decision variables.

Now, let's calculate and record the profit value

corresponding to our production plan of 500 units of each model.

Let's select the cell F10 to hold the value of the objective function,

that is the total profit value.

In the cell F10 we will be writing a formula

that calculates the value of the total profit.

We'll start with the equality sign to tell Excel that we have a formula in this cell.

Now, for each of 500 Razor scooters, Zooter gets $150.00.

So we multiply 150 by 500.

And to that value we must add the profit earned from the Navajo scooters.

That is 160 x 500.

So the total is $155,000.

So we have a formula for the objective function cell.

This formula will calculate the total profit value for

any choice of the decision variables.

For example, if we try a production plan of say,

600 units of Razors, and 600 units of Navajos.

The number in F10 immediately changes to reflect the new profit value.

So let's go back and change it to 500 and 500.

By the way, if you would like to see the formula inside a particular cell or

edit that formula you can use a Windows shortcut F2.

So we are in cell F10 and here we see the formula for the objective function.

In this problem we have two decision variables.

And the calculation of the profit value involves studying two products.

The product of the number of Razor scooters and the profit contribution for

each Razor scooter and the product of the number of Navajo scooters and

the profit contribution for each Navajo scooter.

But what if our problem contained 1,000 of decision variables,

do we still have to write the profit formula as a sum of 1,000 of products,

one for each decision variable?

Fortunately not.

The Excel function sum product allows us to use a kind of

shorthand notation in such cases.

Here's how the sum product works for the case of two scooter models.

We are in the cell left hand.

And let's replace the current profit formula by its

equivalent using some product function.

So we type SUMPRODUCT Of, C9 and

D9 are profit contributions.

And C10 and D10 are decision variables.

The sum product function uses two areas of cells of equal size.

And multiplies the numbers in the first area by the corresponding numbers in

the second area.

First number in the first array is multiplied by the first number in

the second array.

Second number in the first array is multiplied by the second number in

the second array, and so on.

After that the SUMPRODUCT simply sums all of these products.

So, the formula SUMPRODUCT C9:D9, C10:D10 is exactly the same

as the formula C9 x C10, + D9, x D10,

and you'll get the same optimization result no matter which one you use.

However, the sum product formula is a lot more convenient when working with

the models with large numbers of variables and large numbers of constraints.

You can find more information about the sum product function in the Excel Help.

Okay, one last thing about the objective function cell.

Just like we did for the decision variable cells,,

let's highlight the objective function cell to make sure it stands out visually.

Let's change the font color to red and make the font bold.

So we're going to change the color to red, make the font bold.

And put the thick border.

Now every time we open the file, we see the decision variable cells in blue and

the objective function cell in red.

So those cells have visually distinguishable from other cells.

Later on we will instruct the solver to change the values in our blue cells,

C10 and D10, our decision variable values,

to maximize the value in the red cell F10, our objective function value.

Of course, we can not just use any values in the blue cells, but

only those who require more resources to produce, than what we have.

Now that we're done with the decision variables in the objective function,

it is time to move on to the constraints.

The main constraints in our model express the limited developability of

free production resources.

Frame manufacturing hours, wheel and deck assembly hours, and

QA and packaging hours.

Let's look first at the frame manufacturing hours.

We need to make sure that whatever production plan we consider,

the number of frame manufacturing hours used by this plan

does not exceed the number of frame manufacturing hours available.

In the algebraic formulation, the number of frame manufacturing hours used by

a production plan described by decision variables are NN,

is equal to 4*R + 5*N,

and the number of available hours is 5610.

In our spreadsheet formulation, cell G14 holds

the value of number of frame manufacturing hours available 5610.

Let us use the cell E14, to calculate the number of

frame manufacturing hours required by the production plan in cells C10 and D10.

For convenience, let us put the header Required (hours) in cell E13, above E14.

Okay, we have two more constraints to convert into a spreadsheet format.

The constraint on the number of wheels and deck assembly hours and

the constraint on the number of Q&A and packaging hours.

If you look at the algebraic formulation of each of those constraints, you

will notice that both have a very similar structure to that of the constraint we

already dealt with, the constraint on the number of frame manufacturing hours.

All three constraints have the full instructure, expression on the left-hand

side of the constraint, the number of required hours, cannot exceed the number

on the right-hand side of the constraint, the number of available hours.

Let's go to the cell E15 and

put in the formula that will calculate the number of wheels and

deck assembly hours required for any pair of decision variables in cell C10 and D10.

Just like in the similar calculation for the number of required frame manufacturing

hours, we need to multiply each decision variable by the number of wheels and deck

assembly hours that a respective scooter model uses and add the resulting products.

In other words, the formula that we put in the cell

E15 is =SUMPRODUCT(C10:D10,C15:D15).

For the production plan we're currently considering,

500 scooters of each scooter model,

we have the number of required wheels and deck manufacturing hours as 1750.

Similarly, if we use cell E16 to calculate the number of Q&A and

packaging hours required by the production plan in cells C10 and D10,

we will put in the formula =SUMPRODUCT,

(C10:D10, C16:D16).

As we see, the current production plan we're considering requires 900 hours of

this resource.

Okay, but what if we have thousands of different resources to keep track of?

Do we have to keep going into cells in the E column one by one and

type the sum product formula?

Fortunately, Excel provides a way of avoiding this by using copy and

paste and the so-called absolute cell referencing or cell anchoring.

Let's compare the formula in the cell E14 to the formulas in the cells E15 and

E16 one more time.

All three formulas use the SUMPRODUCT of the decision variable cells, C10 and D10.

Here's the formula in the cell E14.

And the consumption amounts of each respective resource.

C14 and D14 for this cell E14.

C15 and D15 for the cell E15.

And C16 and D16 for the cell E16.

So if we would take a formula in the cell E14 and

copy and paste it into the cells E15 and

E16, we would need to instruct Excel to leave C10 and

D10 unchanged during this copy and paste operation, and

to change C14 and D14 into C15 and D15 and into C16 and D16.

The way to accomplish this is to use the absolute cell referencing, or

cell anchoring, for the cells C10 and

D10 before doing the regular Excel copy and paste operation.

Here's how we accomplish this.

We go into the cell E14, we highlight cells C10 and D10,

and we use a Windows shortcut, F4 to put the dollar signs

around the addresses for sales C10 and D10.

Those dollar signs instruct Excel not to change the addresses of the cells

when doing copy and paste.

If I now just copy and paste the formula in E14 into E15 and

E16, I get the correct formulas in those cells.

So, I am doing copy and paste.

For example if I now look at the cell E16,

I see the formula =SUMPRODUCT(C10:D10,

C16:D16) and that is the correct formula.

Clearly using this anchoring technique, I can simply type a formula for

the resource consumption of one resource And curve what ever cells I want,

in this case decision variable cells.

And then just copy and paste the formula to

all cells that calculate consumption amounts of all other resources.

And it does not really matter if I have hundreds of those.

I can still do it all in one copy and paste operation.

You can learn more about the absolute cell referencing using Excel Help.

Let's also use a visual cue to indicate that what we want in the optimization,

is that the values in the cells E14, E15, and E16, to be less than or

equal to the values in the cells G14, G15, and G16.

So we put less or equal signs here.

This is just a visual embellishment to make sure that we can

read our file in an easy manner.

Okay, we have created cells that hold values of the decision variables.

The objective function and the resource consumption values.

How will we go about finding the best production plan?

In short, we want to find the values in the cells C0 and D10, our decision

variable cells, that make the value in the cell F10, our objective function cell,

as large as possible while making sure that the values in E14, E15, and

E16 do not exceed the values in G14, G15, and G16, respectively.

Those are resource constraints.

For example if we produce 500 units of each model,

we earn the profit of $155,000 as Excel tells us.

And all of our resource consumption values stay within allowable ranges.

Well, can we make more money by increasing the production?

Let's try producing 500 Razor scooters.

That's 750 Navajo scooters.

Our profit jumps to $195,000 but unfortunately we ran out of

frame manufacturing and wheels and deck assembly resources.

So we cannot simply implement this production plan.

Now, let's tone it down to say, 600 Navajo scooters, so

our profit goes down to $171,000,

and our required number of hours stay within the allowable limits.

So we can keep checking different values of decision variables,

trying to improve the profit while staying within the resource limits.

The problem is, if we're trying to do it manually,

then we spend a tremendous amount of time checking out various possibilities.

And even then we might not find the best production plan,

especially if we have to deal with many decision variables.

This is where the solver comes in.

It would be impossible any human to check all possible alternatives,

just because there could be so many of those alternatives.

The solver, though, does a much faster, and much more through job

of checking those alternatives in trying to come up with the best.

So let's bring in a solver.

Let's go to Data, click on Solver.

The solver parameter's dialog comes up here in the set objective part.

We click on the cell selection tool and

choose the cell F10 to represent our objective.

As you can see, the solver can maximize or minimize the objective.

Minimization could be helpful if you are dealing with minimization of the cost, or

it could select a values of decision variables to

produce a desired value of the objective function.

In a scooter problem we maximize profits, so recheck max option.

Next, we use by changing variable cells to specify where our decision variables are.

So we use the cell selection tool again to point to the cells C10 and D10, and we go

back and we see that Excel now understands where our decision variables are.

Finally, we need to specify to sole where the constraints are.

We use Subject to Constraints, a part, and click Add.

The dialog Add Constraint appears.

In this dialogue, we use Cell Reference to select cells E14,

E15, and E16 on the left-hand side of the constraint.

We also use constraint part to select the values G14,

G15, and G16 on the right-hand side of that constraint.

So, now we instructing this over to make sure that E14 does not exceed G14,

E15 does not exceed G15, and E16 does not exceed G16.

Know that we can also specify constraint of equal type or

greater equal type, and there are other choices here.

We'll use one of them later.

So let's select our less or equal than sign.

Let's click OK.

And we see that this constraint is added.

What is left is adding constraints that tell the solver that our decision

variables must be integer and non-negative.

Let's add the integer constraint first.

We can click on Add, select our decision variable, C10 and D10, and

then in the drop down menu select INT options, which means integer.

So now when we click OK, the Excel solver understands that

it must only use integer values in the cells C10 and

D10 when it searches for the best production plant.

Okay, the last constraint is a non-negativity constraint and

the solver offers a convenient way of introducing this constraint for

all decision variables at the same time.

All we need to do is to check the box make all unconstrained variables non-negative.

Next we need to select a solving method.

Solver offers several choices here with a default being GRG Nonlinear.

One of the choices is LP Simplex.

This is a solving method that can only be applied to linear models, in other words,

the models where the objective function and

the constraints are linear functions of decision variables.

So if you are sure that your model is built as a linear model,

use this option since it solves linear models very efficiently.

If your model is not linear however, and

you're trying to use the LP Simplex option, the solver will complain.

Now in this discussion I would like to focus on the details of the modeling

process rather than on distinctions between linear and nonlinear models.

So I would leave the solving method at GRG Nonlinear.

This solution method is very general and will allow you to work with

many different kinds of models, both linear and nonlinear.

And a word of caution, if you select the GRG nonlinear method, you do not have to

worry about whether your model is linear or nonlinear, which is the good thing.

Since it is a general method of solving optimization problems,

it will try to find the solution for any model that you formulate.

However, it may not always be able to guarantee that what it finds, it gives you

as a solution, is actually the best possible alternative in every case.

In addition the output of optimization using the GRG nonlinear method

may depend on the trial values of the decision variables.

So when optimizing using this method,

run it several times with different trial values of the decision variables to see if

you can improve the objective function value.

Okay, the last stop before optimizing.

Let's go to Options, and

make sure that the Ignore Exchange Constraints is unchecked.

This way, we're really making sure that the solver will

not try to produce something like 54.6 scooters.

We're ready to find the best production plan.

Let's click solve button, and

make sure that solver found is solution is displayed in the dialogue that appears.

And it does.

Let's click okay and look at the spreadsheet.

Solver recommends producing 840 unit of razor scooters and

450 of Navajo scooters,

if Zooter wants to maximize it's profit given the resources the company has.

The corresponding profit value is 100 and $98,000.

Before we leave Excel, a few words about solver messages.

This time the solver came up with the message, solver found a solution.

This is the message we want to see.

I would like to mention two other messages that we do not want to see.

Suppose that we made a mistake in setting up our model and

forgot to include one or more important constraints.

Let's go to our solver dialogue and wipe out all of our constraints,

and then try to optimize our production plan.

So we go here.

I'm going to say delete, and we say delete, so we have no constraints.

Of course, that's silly, but let's try to solve the model and

see what kind of message the solver comes up with.

Well, the solver comes up with a huge red explanation sign,

and the message, objective cell values do not converge.

This means that the profit in this model can grow to infinity.

When you see a message like that when trying to optimize your model, please

remember that it most probably indicates that you forgot an important constraint.

Okay, let's put back our constraints.

So over, add.

This pre-constraints should be less than three,

the other should be lesser or equivalent than this three values.

And let's add integer constraints on our decision variables.

So let's go like this and click I-N-T, integer.

And we're back.

Let's click solver, just to make sure that we get everything right.

Here's the optimal solution.

Okay. Now, let's set a constraint that will

make it impossible for the solver to find the values of the decision variables

that will satisfy all of the constraints in the problem.

For example, right now we want the number of frame manufacturing hours

used by the production and not exceed 5,610.

Suppose with a constraint that also requires the number used manufacturing,

frame manufacturing hours to be at least 6,000.

Of course, these two constraints cannot be set aside at the same time.

But let's see what the software tells us when we are trying to solve the model

with this constraint added.

So we're going to solver, and we're saying, let's add this constraint.

Let's say the number of required hours of freight manufacturing

should be at least greater or equal than 6000.

It's an incompatible constraint with your other constraints,

but let's see what the cell reaction would be.

We click solve and the solver comes up with another red exclamation sign and

a message that it could not find a feasible solution.

In other words, it could not satisfy all the constraints at the same time.

So when we see one of these messages, there's something wrong with our model.

Either, in the case of the first message we are probably missing an important

constraint, given the objective function we're trying to optimize, or

we have some incompatible constraints in the case of the second message.

Let's restore our model to its original state and

solve it one more time to make sure everything is fine.

Let's delete this spurious constraint.

Let's click unsolved.

And here we go, we have our optimal solution.

This final spreadsheet with comments reflecting the formulas we introduced

is posted on our site under the name Zooter.

Okay, here's a picture of the optimized spreadsheet with formulas.

We have the best solution, 840 Razors and 450 Navajos and

the best possible profit, $198,000.

Okay, let's rig up some optimization terms.

A particular combination of decision variable values is called solution.

A feasible solution is the one that satisfies all constraints.

And an in-feasible solution is the one that violates at least one constraint,

no matter which.

The objective function value is a number that you will obtain

if you plug in decision variable values,

corresponding to a particular solution into the objective function.

Finally, the optimal solution is the best feasible solution.

In the Zooter case, it is 840 Razor scooters,

and 450 Navajo scooters.

It is possible to have more than one optimal solution, but

in that case, any optimal solution will produce the same objective function value.

The best one.

In this session, we have used the solver optimization tool to set up and

solve Zooter optimization problem.

While doing this, we have learned two approaches that are often useful in

setting up spreadsheet optimization models in Excel, the use of the sum-product

function and the use of cell anchoring or absolute cell referencing.

While details of solver operation may be slightly different in different platforms,

for example Windows versus Mac,

the main features of the optimization process are pretty much the same.

In particular, we must identify for the solver the three main components of

an optimization model, decision variables, the objective function and constraints.

If you an excel for Mac or google sheets,

have a look at two brief videos we created for you to go over some minor differences,

in how optimization problems are set up and solved.

The Zooter's problem had two decision variables and three resource constraints.

Real resource allocation applications may contain hundreds of thousands of variables

and constraints or more.

Of course, solver will not be able to handle such large problems.

But commercial optimization software packages that are powerful enough to deal

with problems of this size will still operate using decision variables,

objective function and constraints just like the solver.

The Zooter's problem is a resource allocation example.

In the next session, we will look at another popular type of resource problem.

One in which supply must meet demand across the network of locations.

See you next time.