Each morning, the newsvendor must decide how many copies u ∈{1, 2,…,u♯} of the
day’s paper to order. The variable u is called control.
During the day, the newsvendor will meet an unknown demand .
The variable w is called uncertainty.
The newsvendor faces an economic tradeoff:
he pays the unitary purchasing cost c per copy, when he orders stock;
he sells a copy at price p;
if he remains with an unsold copy, it is worthless (perishable good).
Therefore, the newsvendor’s costs are (where w ∈{1, 2,…,w♯} is a possible value of the
demand)
(1)
The newsvendor’s payoff is −j(u,w).
Now, we introduce a random variableW, where W : Ω →{1, 2,…,w♯}. Here, Ω is an underlying
probability space, equipped with a probability ℙ. We suppose that the newsvendor knows the
probability distribution ℙW of the demand W.
Thus equipped, we consider the stochastic optimization problem of expected costs
minimization:
(2)
// demand wsharp=100;// no larger, else the Poisson distribution cannot be computed wflat=1; demand=[wflat:wsharp]; // control control=[demand,1+demand($)]; // Criterion / costs cc=1;pp=10*cc; // cc=1 ; pp=1.1*cc ; // avoid that cc/pp is the inverse of an integer // when the distribution of demand is uniform costs=cc*control'*ones(demand)-pp*mini(ones(control')*demand,control'*ones(demand)); // one row by control, one column by demand
We will consider different demand distributions.
1.1 The demand distribution is uniform
First, we suppose that the demand distribution ℙW is uniform as follows.
probab=ones(demand); probab=probab/sum(probab);
Question 1
a)
[1] Draw a histogram of the random demand W.
b)
[1+1] In the scilab code above, what does the matrix costs represent? (What doyou find at the intersection of a row and of a column?) Explain in detail why we have thatcriterion = probab*costs’ is a row vector made of the values offor u ∈{1, 2,…,u♯}?
c)
[1+1] Draw the mapping u ∈ {1, 2,…,u♯}J(u). Thanks to the scicoslab macromini (that provides the minimum and the argmin index of a vector), give the numericalvalue of the decisionu⋆(optimal order) that minimizesuJ(u).
d)
[1+1] What does the vector decumprobab=1-cumsum(probab) represent? Explainyour answer. Check that, in agreement with the theory, we numerically have that
e)
[2+1] For a given value ofu, explain why the random variablecan atmost take the values. Give, for each of the u elementsof this list, the corresponding probability thattakes this value in the list. Inthe end, you will provide an expression of the probability distribution of, usingprobab and decumprobab.
f)
[1+2] Draw histograms of the probability distribution of the random payoff (theopposite of the costs)for u = u⋆(the optimal decision) and for u = 𝔼ℙ[W]
(the naive deterministic solution consisting in ordering the mean demand𝔼ℙ[W]). Drawthe two histograms on the same picture, so that they have the same scale. Comment onthe differences between the two histograms.
g)
[1+1+1+2] The vectorgrand(365,"markov",ones(probab’)*probab,1) represents a sequence of realizationsof 365 i.i.d. random variables having the same distribution than the demandW. Simulateand draw the trajectory of the cumulated payoffs of the newsvendor during one year if,every day, he orders the optimal quantityu = u⋆. Do the same for u = 𝔼ℙ[W] and drawit on the same picture. In what sense does the the optimal decisionu = u⋆does betterthan u = 𝔼ℙ[W]? Justify in detail why the two trajectories are approximately straightlines; to what correspond the slopes?
h)
Now, we study if the results are robusts to changes in the the ratio between the unitarypurchasing costc and the selling pricep.
1)
[2] Take c < p with c ≈ p. Find the optimal decisionu⋆. Draw histograms ofthe probability distribution of the random payofffor u = u⋆and foru = 𝔼ℙ[W]. Simulate and draw trajectories of the corresponding cumulated payoffs.
2)
[2] Same question with c << p.
3)
[2] Discuss. In particular, how does the optimal solution u⋆vary with the ratioc∕p?
//exec('newsvendor_data.sce');exec('newsvendor_uniform.sce');exec('newsvendor_main.sce') xset("window",1);clf();plot2d2(demand,probab) xtitle("Histogram of the demand") // Criterion / expected costs criterion=probab*costs'; // a row vector xset("window",3);clf();plot2d2(control,criterion) xtitle("The expected costs as function of the decision") // Optimal decision [lhs,optcont]=mini(criterion); disp("The optimal decision is "+string(optcont)) // Naive deterministic solution meandemand=probab*demand'; disp("The expected demand is "+string(round(meandemand))) // Check that the optimal decision satisfies the optimality condition cumprobab=cumsum(probab); decumprobab=1-cumprobab; xset("window",4);clf();plot2d2(demand,decumprobab,rect = [demand(1)-1,0,demand($),1]); plot2d(demand,cc/pp*ones(decumprobab),style =5); xtitle("The decumulative distribution of the demand") disp("Is it true that "+string(cc/pp)+" lies between "+string(decumprobab(optcont))+ ... " and "+string(decumprobab(optcont-1))+"?") NS=365; // simulated demands DD=grand(NS,'markov',ones(probab')*probab,1); time=[1:NS]; xset("window",8);clf(); plot2d2(time,cumsum(-costs(round(meandemand),DD)),style =3); plot2d2(time,cumsum(-costs(optcont,DD)),style =5); legends(["optimal solution "+string(optcont); "naive deterministic solution "+string(round(meandemand))],[5,3],"lr"); xtitle("The cumulated payoffs as function of the number of days","time","payoff") xset("window",10);clf(); uu=optcont; ss=5; plot2d2([costs(uu,[wflat:(uu-1)]),costs(uu,uu)], ... [probab([wflat:(uu-1)]),decumprobab(uu-1)],style = ss, ... rect = [mini(costs),0,maxi(costs),1]); // uu=round(meandemand); ss=3; plot2d2([costs(uu,[wflat:(uu-1)]),costs(uu,uu)], ... [probab([wflat:(uu-1)]),decumprobab(uu-1)],style = ss, ... rect = [mini(costs),0,maxi(costs),1]); // legends(["optimal solution "+string(optcont); "naive deterministic solution "+string(round(meandemand))],[5,3],"ur"); xtitle("Histograms of the costs")
1.2 The demand distribution is a mixture of two truncated Poisson distributions
Second, we suppose that the demand distribution ℙW is a mixture of two truncated Poisson
distributions as follows:
(3)
Question 2[6] Same questions as in Question??when the demandW follows amixture of two truncated Poisson distributions.
Question 3[6] Same questions as in Question1when the demandW follows atriangular distribution over {1, 2,…,w♯}.
// Triangular distribution lambda=floor(wflat+0.3*(wsharp-wflat)); // probab=[cumsum(ones([wflat:lambda]))/sum(ones([wflat:lambda])), ... 1-cumsum(ones([(lambda+1):wsharp]))/sum(ones([(lambda+1):wsharp]))]; probab=probab/sum(probab);
2 The newsvendor problem (continuous formulation)
Here, we consider that the decision can take continuous values: .
We also adopt new notations. We suppose that the demand W can take a finite number S of
possible values Ds, where s denotes a scenario in the finite set 𝕊 (S=card(𝕊)). We denote πs the
probability of scenario s ∈ 𝕊, with
(4)
Notice that we do not consider scenarios with zero probability.
We consider the stochastic optimization problem
(5)
We now show how to rewrite this problem as a linear program. First, we write:
Second, we deduce
Third, we conclude
This is a linear program.
Question 4Suppose that W follows a uniform distribution over {1, 2,…,w♯}.
a)
[2] Write the linear program (8) under the form adapted to the scicoslab macrolinpro.
b)
[1] Solve (8) with linpro and obtain the solution to the stochastic optimizationproblem (5).
c)
[1] Compare with the optimal solution of Question1.
d)
[2] Increase the numberw♯of values taken by the demandW. When can you nolonger solve numerically? Compare with the result of Question1.
3 The newsvendor problem with risk (continuous formulation)
Let λ ∈]0, 1[, that plays the role of a risk level. The Value at Risk of the cost X at level λ ∈]0, 1[
is
The Tail Value at Risk of the cost X at level λ ∈]0, 1[ is
We have the limit cases:
The Rockafellar-Uryasev formula establishes that
We consider the risk averse stochastic optimization problem
(9)
We rewrite this problem as a linear program.
Question 5Suppose that W follows a uniform distribution over {1, 2,…,w♯}.
a)
[2] Write the linear program (10) under the form adapted to the scicoslab macrolinpro.
b)
[1] Solve (10) with linpro and obtain the solution to the stochastic optimizationproblem (9).
c)
[1] Compare with the optimal solution of Question4.
4 The newsvendor problem with backorder (continuous formulation)
Now, we suppose that the newsvendor
pays the unitary purchasing cost c per copy, when he orders stock;
sells a copy at price p; we have that c > p;
can buy extra copies at the unitary backorder cost b, after he observes a demand w
larger than the initial order u; we have that b > c
pays the unitary holding cost h for each unsold copy, when the demand w is less than
the initial order u.
Therefore, the newsvendor’s costs are
(11)
where we recall that .
cc=0.1;pp=10*cc;bb=10*cc;hh=10*cc;
Question 6We suppose that the demandW follows a uniform distribution over {1, 2,…,w♯}.
a)
[1] Write a row vector criterion made of the values offoru ∈{1, 2,…,u♯}.
b)
[1+1] Draw the mapping u ∈ {1, 2,…,u♯}J(u). Thanks to the scicoslab macromini (that provides the minimum and the argmin index of a vector), give the numericalvalue of the decisionu⋆(optimal order) that minimizesuJ(u).
c)
[1] Check that, in agreement with the theory, we numerically have that
d)
[1+1] For a given value ofu, what is the set of values taken by the random variable? Give a scicoslab formula for the probability distribution of, usingprobab and decumprobab.
e)
[1+1] Draw a histogram of the probability distribution of the random payoff (theopposite of the costs)for u = u⋆(the optimal decision) and for u = 𝔼ℙ[W]
(the naive deterministic solution consisting in ordering the mean demand𝔼ℙ[W]). Drawthe two histograms on the same picture, so that they have the same scale. Comment onthe differences between the two histograms.
f)
[1+1+1] Simulate the trajectory of the cumulated payoffs of the newsvendor duringone year if, every day, he orders the optimal quantityu = u⋆. Do the same for u = 𝔼ℙ[W].Compare.
g)
[4] Multiply the unitary holding cost h by a factor 5. Comment on the changes thatyou observe.
h)
[4] As in Section2, write the new optimization problem as a linear program. Then,write this latter under the form adapted to the scicoslab macro linpro. Solve with linproand compare with the optimal solution found above by the direct method.
i)
[4] Increase the numberw♯of values taken by the demandW. When can you nolonger solve numerically? Compare with the direct method.