Stochastic Linear Programming for Supply Chain

PlanningStephen C. Graves and Sean P. Willems

December 2018

The purpose of this note is to do a brief introduction into stochastic linear

programming(SLP). Traditional linear programs assume that all inputs are
deterministic, in terms of the parameters for specifying the constraints and the
objective function. With a SLP, werelax this assumption and will allow for some
uncertainty in these parameters; the typical application of SLP will allow for the
limits of some constraints to be uncertain.

Furthermore, the common structure of the SLP assumes a two-stage decision

process: Inthe first stage there are a set of decisions that are made under
uncertainty; that is the first-stage decisions are made before we know (say) the
supply of a key raw material or the actual demand for our products. The second-
stage decisions are then made after the uncertainty is resolved or removed; for
instance, in the second stage we will know the first stage decisions as well as what
the raw material supply is and/or what the demand is. The complexity of the SLP is
due to the fact that we want to make the first stage decisions accounting for what
we will do in the second stage – which is uncertain at the time we make the first
stage decisions.

We will introduce and illustrate SLP with an example, based on the following
teachingcase.

Wilson, R. B. "Red Brand Canners." Management Science and the Manager. Prentice-
Hall, Englewood Cliffs, NJ (1980): 105-108.

We first describe the planning problem with no uncertainty. After we review this
1
planning problem, then we will extend it to account for uncertainty.

Example: Product mix planning problem, with no uncertainty

We have a supply of 3,000,000 pounds of tomatoes. Of this supply, 20% is grade A

quality (600,000 pounds), and 80% is grade B quality. We need to decide what to do
with these tomatoes, where our options are as follows:
 Process them into Tomato Paste
 Process them into Tomato Juice
 Process them into Whole Canned Tomatoes

We have following information for each possible product:

Maximum demand Minimum % of Profit contribution

(1000 pounds) Grade A ($ per 1000 pounds)
Whole Canned Tomatoes 75% 82.22
Tomato Juice 1000 25% 66.00
Tomato Paste 2000 74.00

That is there are limits on how much Juice and Paste can be sold in the coming season.
And we have a quality constraint for both Canned Tomatoes and for Juice: to satisfy the
quality constraint for Canned tomatoes, we need at least 3 pounds of Grade A tomatoes
for every pound of Grade B tomatoes; and for Juice, we need at least 1 pound of Grade A
tomatoes for every 3 pounds of Grade B tomatoes.

To decide the product mix, we can now formulate a linear optimization problem given as
follows:

2
MAX 82.22 AC + 82.22 BC + 66 AJ + 66 BJ + 74 AP + 74 BP

SUBJECT TO
(A Supply) AC + AJ + AP <= 600
(B Supply) BC + BJ + BP <= 2400
(Juice Dem) AJ + BJ <= 1000
(Paste Dem) AP + BP <= 2000
(Can Qual) - AC + 3 BC <= 0
(Juice Qual) - 3 AJ + BJ <= 0

AC, BC, AJ, BJ, AP, BP >= 0

The decision variables are AC, BC, AJ, BJ, AP, BP and represent how the tomatoes are to
be processed or used. “AC” is the amount of Grade A tomatoes (in 1000 pounds) that go
into Canned Tomatoes; “BP” is the amount of grade B tomatoes that go into Paste.

The supply constraints just reflect the given limits on Grade A and on Grade B tomatoes.
The quality constraints assure the minimal proportions required for Canned Tomatoes
and for Juice. Note that we could have written the quality constraint for Canned
Tomatoes as:
AC/(AC + BC) > = 0.75.
But our solution algorithms want our constraints to be linear functions of the decision
variables; so we re-express the constraint in an equivalent and linear form, as shown
above.

This optimization is easy to set up and solve; Do it in [Link] optimal solution is:

3
AC = 525; BC = 175
AJ = 75; BJ = 225
AP = 0; BP = 2000

Total profit contribution is $225,354

Example: Product mix planning problem, with uncertainty

Now we’ll add some complexity to this problem by considering the decision of how
many pounds of tomatoes should we contract for?

Suppose that decisions on the purchasing contract are to be made in April, before we
know the demand and before we know the quality of the crop.

In particular we will assume the following timeline of decisions and events:

 We determine how many tomatoes to purchase in April. At this time, we only
have a probabilistic forecast for the maximum demand of Paste. Also, in April we
also only have a probabilistic forecast for the quality of the crop.

 In August we learn the quality of the crop, and we learn the maximum demand
for Paste.

 In September, we make the product mix decisions.

This is a good example of a two-stage decision problem with constraints - we have

decisions to make now (stage 1), and decisions to be made later (stage 2). The decisions
we make now will affect the decisions we will make later; the amount of tomatoes for
which we contract (stage 1) clearly impacts our ultimate choice of product mix (stage 2).

4
But the later decision is also impacted by other environmental elements or variables,
which are uncertain now. The product mix decision depends on the quality of the crop
and on the latest market forecasts. But these elements are uncertain at the time we
must make the first-stage decision, namely the amount of tomatoes to purchase.

To solve this type of problem, one approach is to identify a set of scenarios that covers
the range of outcomes for the uncertain elements in the problem. We then formulate a
large linear program that will optimize the first-stage decision over the entire set of
scenarios, where each scenario is weighted by its probability of occurrence. The linear
program will also determine the optimal second-stage decisions for each scenario.

The size of the linear program is N times the size of the linear program for a single
scenario, where N is the number of scenarios.

With this approach, our first step is to determine the scenarios; we suppose that in April
we have the following information:

 We can purchase upto 5,000,000 pounds of tomatoes at a price of $ 0.065 per

pound, for delivery in September.
 The tomato crop can be either good (30% grade A's) or bad (20% grade A's),
depending on the weather. The crop is good in 2/3 of the years, and bad in 1/3
of the years.
 The maximum demand for Juice is 5,000,000 pounds; there is no demand limit on
Canned Tomatoes.
 Paste demand is highly uncertain as of the forecast made in April. Based on past
demand, we suppose there are five possible demand outcomes with
probabilities given below:

5
 demand probability
1350 0.2
1700 0.2
1950 0.2
2250 0.2
2700 0.2

Now if we assume that Paste demand is independent of the quality of the crop, then we
have ten scenarios, where each scenario is a combination of the quality of the crop
(good or bad) and one of the five demand outcomes for Paste; we will denote the
scenarios as G1, G2, G3, G4, G5, B1, B2, B3, B4, B5 (where G1 denotes a good crop and
paste demand of 1350).

In April, at the time of the purchase decision, the probability for each scenario is either
2/15 or 1/15, depending upon whether the crop is good or bad.

Now to formulate the linear program we need to define the decision variables, the
constraints, and the objective function.

Decision variables:

We have two sets of decisions, the decisions made in April (stage one), and the
decisions made in September (stage two).

Stage one: "now decisions" - the amount of tomatoes to purchase, which we term as P.

Stage two: "later decisions" - the product mix decisions.

6
Here the product mix decisions will depend not only on the purchase quantity but also
on the scenario. Thus, we need to define a set of variables for the product mix for each
scenario. The generic product mix variables are as follows (all units are 1000 pounds):

AC amount of grade A tomatoes used for cans

BC amount of grade B tomatoes used for cans
AJ amount of grade A tomatoes used for juice
BJ amount of grade B tomatoes used for juice
AP amount of grade A tomatoes used for paste
BP amount of grade B tomatoes used for paste

Now we define a set of decision variables for each scenario.

For instance, we can denote the set of decision variables for scenario 1 as: AC-G1, BC-
G1, AJ-G1, BJ-G1, AP-G1, BP-G1 ; this is the scenario of a good crop and paste demand
equals 1350.

In total there is 60 product-mix decision variables, six for each of ten scenarios.

Constraints:

Similar to the decision variables, there is a constraint set for each scenario. Also, there
are constraints on the stage-one (now) decisions.

Constraints on "now" decisions: (The most we can purchase is 5,000,000 pounds).

0  P  5000

Constraints on each scenario:

7
For each scenario we have the same constraints for a product mix LP, just like for the
case with no uncertainty. However, the constraints will differ for different scenarios due
to the different outcomes of the uncertain elements. To wit, for the G1 scenario the
constraints are:

AC-G1  AJ -G1  AP-G1  0.3P

BC-G1  BJ -G1  BP-G1  0.7P
AJ -G1  BJ -G1  5000
AP-G1  BP-G1  1350
 AC-G1  3  BC-G1  0
3  AJ -G1  BJ -G1  0

The first two constraints are for the supply of Grade A and Grade B tomatoes, reflecting
the fact that in scenario 1 30% of tomatoes are Grade A.

The next two constraints are the maximum demand for Juice and for Paste, where the
maximum demand for Paste is 1350 in scenario 1. The maximum demand for Juice is
assumed to be 5000, independent of the scenario,

The last two constraints are the quality constraints for Canned Tomatoes and for Juice.

Thus there are six constraints for each scenario, for a total of 60 over the ten scenarios.
In addition all variables are non-negative.

Objective Function:

The objective is to maximize the expected net revenue for the year. As of April, since
the tomatoes have not yet been purchased, the objective will include the cost of the
tomatoes. It also includes the revenue from the product mix decisions. But since the

8
revenue from the product mix depends on the scenario, the objective function must
combine the scenarios by weighting each of them by its probability. Thus, the objective
function can be written as follows:

(probability of scenario G1) *(revenue from G1) +

(probability of scenario G2) *(revenue from G2) +
......... +
(probability of scenario B5) *(revenue from B5) -
(cost of purchasing P tomatoes)

Note that the probability of each of the “good” scenarios is 2/15, while the probability of
each of the “bad” scenarios is 1/15.

On the class web page you will find an Excel Spreadsheet with the model. You should
review the spreadsheet to see how the linear program has been developed using the
Solver option; you should check out how the constraints and the objective function have
been built into the spreadsheet.
When you solve the LP, you should get the following optimal solution:
P = 5000
Expected Revenue = $39,763

9
 Scenario AC AJ AP BC BJ BP
G1 881.25 618.75 0.00 293.75 1856.25 1350.00
G2 1012.50 487.50 0.00 337.50 1462.50 1700.00
G3 1106.25 393.75 0.00 368.75 1181.25 1950.00
G4 1218.75 281.25 0.00 406.25 843.75 2250.00
G5 1387.50 112.50 0.00 462.50 337.50 2700.00
B1 131.25 868.75 0.00 43.75 2606.25 1350.00
B2 262.50 737.50 0.00 87.50 2212.50 1700.00
B3 356.25 643.75 0.00 118.75 1931.25 1950.00
B4 468.75 531.25 0.00 156.25 1593.75 2250.00
B5 637.50 362.50 0.00 212.50 1087.50 2700.00

What the optimal solution tells us, is that in April you should contract to purchase
5,000,000 pounds. As of April the expected profit, net of the cost of Tomatoes, is
$39,763.

And then in September, the product mix decisions are given, conditioned on what
scenario emerges. For instance, if the scenario is B2 (bad crop, and Paste demand =
1700), then the best decisions are to make 350,000 pounds of Canned Tomatoes,
2,950,000 pounds of Juice and 1,700,000 pounds of Paste. As of September, if B2 is the
scenario, then the expected revenue is now $24,277.

10