此课程是为影响转变数据成为更好的决定的想法而设计。最近在数据采集技术上的显著提升改变了公司进行有效决定的方式。
(Optional) Advanced Session on Optimization
Loading...
來自 University of Pennsylvania 的課程
运营分析
個評分
從本節課中
Prescriptive Analytics, High Uncertainty
This module introduces decision trees, a useful tool for evaluating decisions made under uncertainty. Using a concrete example, you'll learn how optimization, simulation, and decision trees can be used together to solve more complex business problems with high degrees of uncertainty. You'll also discover how the Newsvendor problem introduced in Week 1 can be solved with the simulation and optimization framework introduced in Weeks 2 and 3.
與講師見面
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
Welcome to week four's Advanced Session on Optimization.
My name is Noah Ganz.
I'm your instructor for week four.
In this advanced session,
we're going to see how to transform an optimization problem that
has a non-linear min statement embedded into it into a linear formulation.
Before we get started, I want to remind you that this is an optional session and
you don't need to look at it.
You only need to look at it if you're curious.
We won't be testing you on this material.
So let's get started.
Here's what we're going to do.
We'll start out by recalling ideas optimization problem for session three.
We'll then implement the optimization problem in Excel using the min formula.
That's exactly what we did in section three.
We'll also look at an algebraic version of the formulation,
that's the mathematical analog of the Excel spreadsheet formulas.
We'll also graph the min statement and
we'll see why that min statement is not linear.
Having graphed the min statement,
we can use the graph to see how we can modify the formulation and make it linear.
And having done that, we'll update the algebraic formulation
to make it linear as well, and we'll implement it in Excel.
So let's remember IDEA's problem from session three.
In session three supplier P allowed IDEA to choose its order quantity, Q.
In particular, IDEA could choose a Q anywhere between 4,000 and 10,000 units.
IDEA had a more complex demand forecast.
For example, if the market were strong, demand would be uniformly distributed from
6,000 to 14,000 units, and in fact we are going to use the strong
part of the demand forecast in our examples today.
IDEA's revenues and costs for supplier P were as follows.
The sales price of the tent was 150 Euros per unit.
The unit cost was 100 Euros.
And supplier P would charge IDEA a fixed contracting fee
of 100,000 Euros if IDEA were to choose supplier P.
If IDEA were to order quantity Q, and demand turned out to be D,
then it would earn revenue of 150 euros price times the number of units sold,
minus 100 euros unit cost times to number of units ordered,
minus 100,000 euro fixed cost.
Putting it all together, IDEA's profit pi would be 150 times the number of units
sold minus- 100, times the number of units ordered, minus 100,000.
And we can go and take this formulation, and implement it in Excel.
And that's what we're gonna do next.
Now we're in Excel.
The name of this file is IDEA Linear Optimization.xlsx and
you can download it from the Coursera website.
And this first worksheet is a template the way that we've had templates earlier
in the week.
And we're gonna fill it out right now to
formulate an Excel version of IDEA's optimization problem.
The first cell we'll look at is the Order Quantity Q, and
right now we have a default of 10,000 units.
That's what IDEA has been ordering before.
This will become the decision variable.
Other problem data are the fixed cost of 100,000 euros,
the unit price of 150 euros, and the unit cost of 100 euros.
The last set of data that we need to fill out are the sample demands and
we'll do that with the Excel random number generator.
Remember, we go to the data tab, and then the data analysis menu item.
We'll double-click the random number generator to
bring up the random number generator.
And we're going to select one random variable and
generate ten samples, or ten random numbers,
and define it as a uniform distribution.
And, it will be defined between 6,000 and
14,000, with a random seat of one, two, three,
four, and an output range that starts in cell B10.
And then we'll click OK.
And we've generated a set of ten random demands that
are distributed uniformly between 6,000 and 14,000.
That's when the market is strong and let me just format this.
We've recall that by definition the uniform distribution
generates fractional numbers.
The other thing I want to show you is just a bigger screenshot of the random number
generator dialog box.
So again, we chose one random variable, ten random numbers,
uniform distribution distributed between 6,000 and 14,000 with a random seed one,
two, three, four, and the first the output range was cell B10.
And we got these ten numbers here.
These are all the data that we need, and now for each of the ten samples,
we're going to define the profits.
The revenues are the unit price of 150,
times the minimum of the demand for
that sample, and the order quantity.
The fixed cost is simply 100,000 euros.
The variable cost is the unit cost of 100 times the order quantity.
And the profit is the revenue,
minus the fixed costs, minus the variable costs.
And you can see for
a demand of 6,993 IDEA is actually losing money if an order is 10,000 units.
It has revenues of about 1,049,000 Euros.
But it's got costs of about 1.1 million euros.
So it's losing about 51,000 euros.
Having filled out the definition of the profit for
this demand sample, we could just copy the cells down.
And you can see in every single case the fixed cost by definition stays the same.
The variable cost stays the same because we're always ordering 10,000 units.
And it's the revenues, and subsequently the profits that change with the demands.
Having defined the profits for each of the ten samples, then we can take the average
of them using the Excel average formula To calculate the average profit.
And you can see for these ten samples, if IDEA had ordered 10,000 units,
it would have earned average profits for the ten samples of about a 162,000 euros.
Of course, if IDEA were to change its order quantities, so for example,
it were to order 9,000 instead of 10,000, you can see, for example,
that the average profits would have been instead about 216,000 euros.
So now we've got the spreadsheet set up, and we need to use Solver.
We're gonna call up Solver and define the decision variable, and the objective, and
the constraints.
So our objective is to maximize the average profit.
Our decision variable is the order quantity and
we need to add a couple of constraints.
We want to make sure that the order quantity is greater than or
equal to 4,000 units.
And also that the order quantity is less than or
equal to 10,000 units.
The last thing I'll point out is that we're going to use
non-linear because it's a non-linear formulation.
If you try to run it with Simplex OP, as if it were linear,
the solver will cough and complain.
Before I solve it, I just want to quickly show you,
the solver dialogue box is slightly larger.
So again, the objective was the average profit that was in cell F21.
We're gonna maximize it by choosing values for
the order quantity that was in cell B3.
And we had a couple of constraints that the order quantity had to be less than or
equal to 10,000 units, and the order quantity had to be greater than or
equal to 4,000 units.
And we're gonna use GRG Nonlinear.
So now let's go back here, and take a look at the Solver,
we're all set we're gonna solve it.
And here we are.
We can see in fact, that the optimal
decision is to order about 7,884 units and
the average profit for those 10 demands was almost 240,000 euros.
So by decreasing the order quantity, IDEA actually had,
I suppose, less leftover inventory and
had bought less inventory for the same kinds of demands,
and was able to increase its profits.
So that's it for Excel spreadsheet one.
Or Excel number one.
So having implemented a spread sheet formulation of the problem we can develop
an algebraic formulation that's the mathematical analog of the spreadsheet.
Before we start I want to remind you that our problem data
are going to include ten samples of simulated demand.
We're gonna call them D1, D2, D3, all the way up to D10.
We generated those with Excel's random number generator and
we're gonna call the generic sample, Di.
With those data, we can now formulate IDEA's decision problem,
it's decision variable is Q that's the order quantity.
And if I do orders Q and the command sample is Di for
the ith sample, then we can calculate IDEA's profit, and we'll call it pi i.
That's calculated just the way we have before,
that's the 150 euro revenue times the quantity sold.
That's the minimum of the demand Di and Q, minus the hundred year unit cost
times the order quantity Q minus the hundred thousand Euro fixed cost.
With each of those ten defined, we can then calculate the average profit.
We're going to call that pi average.
It's the average over all ten samples.
Having defined the pi i's and
pi average, we can now fully formulate the algebraic version of the problem.
IDEA's are going to choose and
order quantity Q to maximize the pi average, subject to some constraints.
The first just defines pi average, that's the arithmetic average of the pi i's.
The second set of constraints, and
there are ten of them, defines each of the pi is.
Finally, there's a pair of constraints that limited ideas order
quantities between 4,000 and 10,000 units,
and that's the complete algebraic formulation of the problem.
And we can see embedded in the middle of it are these definitions of pi
i that have the non-linear min functions.
And we wanna see next, what's the problem with the min functions?
So now, let's plot sales as a function of demand in the order quantity.
Along the horizontal axis, we've plotted demand.
And remember, demand can be anywhere between 6,000 and 14,00 units.
And you can see along the horizontal axis, it moves from 6,000 to 8,000
to 10,000, and we've cut if off a little bit before 14,000.
In this example, we're saying the order quantity Q is 8,000.
You can see that Q = 8,000 up in the middle of the chart.
Along the vertical axis, we've plotted sales, and
sales is just the minimum of the demand and the order quantity.
So S i would be the number of units sold,
if the order quantity were Q, and for demand sample D i.
We can see if demand D i is 6,000, then sales equals 6,000.
If demand D i were 7,000, then sales would be 7,000.
All the way up to 8,000.
But if demand D i were 9,000, then sales would still only be 8,000,
because they're limited by the order quantity, Q equals 8,000.
Remember, S i is the min of D i and Q.
So right at that corner point, and I'll just show you with the cursor or
with the pointer, right at that.
Order quantity Q of 8,000, when demand equals 8,000,
the blue line that plots sales as a function of demand makes a right turn and
it also has a little corner point that's not even smooth.
The fact that it has a corner, is what makes the problem badly behaved.
And we'd like to fix both problems, the fact that it's not linear, it makes
the right turn, and the fact that on top of it, it's got that little corner point.
And we're gonna do that first of all, by extending the algebraic formulation,
then I'll show you what it looks like on the same plot.
And so you get a sense, graphically, of what's going on.
So we can avoid this bad type of non-linearity by extending the algebraic
formulation.
Here's the original formulation.
We're going to maximize the average profits by average, subject to
a definition of pi average, subject to a definition of each of the pi i's, and
subject to limits on the order quantities, between 4,000 and 10,000 units.
It's the definitions of the pi i's that are problematic because they have the min
functions in them.
We'll add 10 decision variables, one for each D i, and
we're going to call them S i.
Each S i is going to be the number of units sold when the demand sample is D i.
And we can rewrite the definitions of the pi is to
use the unit sales rather than the min function.
So now you can see that those pi i's are linear functions of the S is and the Q.
We'll add two constraints for each S i to make sure that each Si is less than or
equal to the minimum of D i or Q.
We'll have a constraint that S i is less than or equal to D i, and
we'll have a constraint, S i is less than or equal to Q.
So we've added 10 decision variables, one S i for
each D i, and 20 constraints, two constraints for each S i.
Notice that those constraints are going to be forcing each S i
to be less than or equal to the minimum of D i and Q.
But it would be feasible to have an Si that's strictly less than the minimum
of Di and Q.
So for example, it could be the case that demands were ten,
the order quantity were 20 and sales were five.
That would be feasible.
Nevertheless, when we maximize pi average,
we're going to be maximizing each of the pi i's.
And when we maximize the pi i it's going to force the S i to be as large
as possible until it hits one of those constraints.
So, in the optimal solution,
the S i is going to behave like it actually equals the minimum of D i and Q.
Rather than it just being less then or equal to Di and Q.
We can see how this works graphically as well.
This chart has the same exact axes as we used before.
The horizontal axis plots demand from 6,000 all the way up to about 12,000.
The vertical axis is plotting sales.
And sales, we'd like it to be s i is equal to the minimum of d i and q.
The constraints are only going to insure that s i is less than or
equal to the minimum of d i or q.
So let's plot the two constraints.
The first constraint is s i is less than or equal to d i.
And the boundary of that constraint Is a line of slope one,
you can see when DI 6,000 in the lower left then,
SI less than equal to DI is going to limit SI to be below the line of at 6,000.
Same thing at 8,000.
If di were 8000.
Then si is less than or equal to di, is going to limit si to be 8,000.
If di were to be above 8,000, si.
So, for example, 9,000.
Si less than or equal to di, would force si to be less than or equal to 9000.
For each Si, there is a second constraint, Si is left center equal to Q.
And I'm plotting it here for Q = 8,000.
Again, in this case, no matter what Di is,
Si left center equal to Q is going to limit Si to be less center equal to 8,000.
Now we can see how as di changes,
as the demand for the ith sample differs,
a different constraint is going to end up being binding in the optimal solution.
So for example, if di were 7,000, if that sample were 7,000, Si would live there.
And in maximizing Si, Si less than or equal to Di would be binding.
So Si will be push up to 7,000 and then stop in the optimal solution.
If on the other hand, di were 9,000, if demand for
that sample were 9,000, si will leave over here and
in maximizing si in the optimal solution.
The binding constraint would be si less than or equal to q.
So, as long as Si is less than or equal to both constraints.
As it's maximized in the optimal solution, it's going to be living
exactly on those dash lines, and it's going to behave exactly, as if it were.
Obeying that min function,
even though we've eliminated the min function from the formulation.
So that's how we're eliminating the min function, which is nonlinear and
it's got the little corner point.
And we've changed the optimization problem into a linear optimization problem.
So now we're ready to take a look at the full linear formulation.
Here's the original formulation.
We're maximizing the average profits.
Subject to the average profits being determined
as the arithmetic average of each of the pi i.
Subject to the definition of each of the pi i is that uses that nonlinear
min function.
And subject to limits on the order quantities.
The linear formulation works like this.
Again, we're gonna maximize the average profits.
Subject to the definition of the average profits is the earth medic mean.
Here though we're going to define each of the pi eyes in terms of the s
eyes you can see each pi eye definition is also a linear constraint and
we're going to add twenty extra constraints.
We're going to add a constraint that each si has to be less than or
equal to each Di.
Each Si is less than or equal to the order quantity Q.
And finally the same limits on ideas order quantity between 4,000 and 10,000 units.
Okay, we're back to the Excel spreadsheet.
Again the file name is Idealinearoptimization.xlsx,
and you can find it on the course or website.
We have a template like the first one, although with a little bit of extra space
to allow us the extra decision variables for the linear formulation.
I want to remind you that the default order quantity was 10,000 units.
From supplier p the fix costs is 100,000 euros,
the price is 150 euros per unit and the unit costs is 100 euros per unit.
In this portion of column b we have the ten demand samples from before.
We don't need to generate new ones.
We're going to use an average of the ten profits from these ten demands as before,
but here we've inserted a new column C that is unit sales.
These are our Si's.
And for now just now gonna throw in zeroes for the unit sales.
Okay.
And now we can calculate everything else as we did before,
except that we're not going to use the min function.
So for revenues, we want to say that revenues equal the unit
price of $150 times the sales.
For that sample.
All right, the fixed costs are 100,000 as before.
The variable costs are 100 Euros per unit times
the number of units ordered, as before.
And the profits or simply the revenues
minus the fixed cost minus the variable cost.
Here, because the sales are zero,
you can see the profit is -1.1 million Euros.
Because we're just paying the fixed and variable cost but we're not earning
revenue when we optimize the sales numbers will be pushed to be as large as possible.
So now we're just going to copy.
This is pi one.
Were gonna copy the formula for pi one.
All the way through pi two to pi ten.
And once we have the pie eyes we can calculate the average profit.
And you can see it's blue because it's going to be the objective function.
So now we can go to solver's dialogue box.
And we'll choose the data tab and then the solver menu item.
And we will set the objective function to be the average profit.
We're gonna maximize it.
You can see that.
Here, we now have two sets of decision variables.
We have the Q as before.
That's the order quantity.
And then I'm gonna type a comma
that will let me select another set of decision variables.
And after the comma I'm going to select the entire range of
each of the unit sales, for each of the ten different demand samples.
So, that would be S1 through S10.
And having selected the decision variables, now we can add constraints.
We know for example, that we want to make sure
that the unit sales are less than or equal to.
For demands and we can just do that by selecting entire ranges.
We also want to make sure that the unit sales are all less than or
equal to the order quantity Q.
And as before we some constraints on the order quantity.
We want to make sure that the order quantity is greater than or
equal to 4,000.
And that the order quantity is less than or
equal to 10,000.
Okay?
And we want now to select Simplex LP because we're solving this
as a linear optimization problem.
Let me show you a larger version of the solver dialog box so
you can see a little more clearly what I've done.
So again, you can see that objective in G21 now was the average profit,
we're going to maximize it by choosing values for
the decision variables, D3 was the order quantity, Q.
And C10 through C19 were the sales for each of the demand samples.
The first two constraints just show the upper and
lower limits on the order quantity, Q.
It has to be between 4,000 and 10,000.
The third set of constraints here you can see it's saying that
the SIs, the sales numbers have to be less than or equal to the DIs.
So it's the quantities in column B.
And the last constraint is that the SIs,
the sales quantities have to be less than or equal to Q, that's the quantity in B3.
Finally here at the bottom we've selected Simplex LP rather than
GRG non-linear we are solving the problem as a linear optimization problem.
So now we can go back, now that you've seen that, we'll go back and
actually solve it.
And we get an optimal solution.
And as before you can see that the optimal order quantity in cell B3 is about 7,884,
that's about exactly about what we had before, 7,884.09.
And we have exactly the same profits.
The difference in the spreadsheets is really just that this formulation
Is linear, while the previous formulation was non-linear, and
we just got lucky that we're able to solve it with those min functions.
Here, there's no luck involved on.
This is a very stable formulation and
you see now that we can change a non-linear formulation that has min
functions into a linear one by adding decision variables and extra constraints.
So that's it for the spreadsheet and let's go back to the PowerPoint.
That's all for Advanced Session on Optimization in week 4.
We saw that the min function that was embedded
in IDEA's optimization problem was not linear.
It had a kink where demand equalled order quantity.
So we added extra decision variables in constraints to work around it.
For each demand DI, we added a decision variable SI,
that were the unit sales for that sample.
For each SI, we added a constraint that it would be less than or equal to DI.
So sales would never be more than demand for that sample.
And for each Si we also added the constraint that Si would be less than or
equal to Q, so sales would never be more than the order quantity for that sample.
When solver maximizes average profit, each Si would be maximized.
And even though it would be feasible to have the unit sales be strictly
below the demand or order quantity, in the optimal solution each SI would
be pushed up and it would behave as if it equalled the minimum of demand and
the order quantity just as in the original formulation.
So we've developed a linear formulation that behaves as if SI
equals the min of DI and Q.
And that's just a little example of the art of formulating optimization problems.
That's it, and I'll see you soon.
Thanks.
