Stochastic Programming


Stochastic Programming


1. Consider a following network design problem. Denote by S, C, D the respective sets of
suppliers, customers and potential locations for distribution centers. The union of these sets
can be viewed as a set of nodes defining a fully-connected graph G = (S U C’ U D, E), where E
is a set of edges connecting the nodes to model a flow of the products. Let P denote a set of
products produced by the suppliers. Demand of the customer (3 e C’ for the product p E P is
d? (all demand should be satisfied). Each supplier s e S can provide up to 3? units of product
p. Our goal is to build a network of distribution centers by selecting a subset of locations
from D (you might select all centers in D if that is optimal). The cost of selecting location
i is given by 0;. Per-unit cost of processing product It at the location i and/ or transporting
product I: on are (i, j) is given by qu. Using a network flow model, the operational decisions
consist of routing the flow of product k e K from the suppliers to the customers through a
set of selected distribution locations (customers can only receive products though distribution

(a) Provide a mathematical formulation for this problem.

(b) Suggest a two-stage stochastic programming formulation for minimizing expected costs
if the demand is not known until we choose the locations for distribution centers. To
account for uncertainty introduce a set of potential scenarios.

Referring to your answer to (a), which of the variables are first-stage variables, and
which of the variables are second-stage variables.

(c) Formulate and solve using the following 11 by 11 instance of your model:

1, 6, 9,12,17, 21,19,19,17,14,12
7, 6,1, 5,10,16,14,15,11, 7, 7
11, 8, 6,1, 7,12,10,11,11, 7, 9
16,12,11, 7,1,13, 7,10,10,10,13
Q; {Qij} = 21,19,17, 14, 14,1,15,11,9, 9,11
18,15,13,10, 7, 12, 1, 9,12,11,13
20,17,15,12,12,11, 8,1,10,10,13
17,15,12,10,10, 9,11, 9,1, 4, 6
14,11, 7, 6,10, 9,10,12, 4,1, 5
12,11, 7, 8,12,10,13,12, 5, 5,1
0 c=[500, 50, 500, 50, 500, 50, 50, 50, 50, 50, 50] (location costs),
0 s:[300,0,400,0,0_,400,0.0,0.0,0] (supply),
0 S=C= D: {0,1,…,10},
0 there is a single product and the demands are uniformly distributed “(20, 100) for
each location.

0 100 scenarios (generate from “(20, 100))
((1) Include your solution and source code in the final submission.
(e) What is the Expected Value of Perfect Information (EVPI) for this example (consider

your sample average 100-scenario problem to be exact model)?
(f) What is the Value of the Stochastic Solution for this example (consider your sample
average IOU-scenario problem to be exact model)?
2. Let 1‘, n E IR”. Consider the function
Q(r, 7)) = min {nT’yll’V’y = h – TIE}
(a) For fixed 5:, is Q(;if, 17) convex or concave?
(b) For fixed 7), is Q(.r, 7)) convex or concave?
(c) Is Q(.1′, n) convex or concave?
3. Consider the stochastic problem with a following second stage:
Q(I.£) == myin 2311 + 312
Sllbject to 111 +112 21- 11,311 2 5 -1’1 -:L’2,y1,y2 Z 0
Suppose 1’1, 1:2 E [0.1] and E C R+.

(a) Show that if E has finite expectation, then this program has complete recourse.
(b) Show that E [Q(:r,£)] is convex in .1: and E.





find the cost of your paper