ECE 307

Linear Programming under Uncertainty

Department of Electrical and Computer

Engineering
University of Illinois at Urbana-Champaign

ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

LP UNDER UNCERTAINTY

The formulation of a LP problem is based on the

knowledge of all the parameters and constraints

with certainty, i.e., all aspects of the problem are

deterministic

However, uncertainty and inexactness of data

and outcomes pervade many aspects of the real

world
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

1
 LP UNDER UNCERTAINTY

Uncertainty in a LP problem may be caused by:

incomplete information of the constraints of
interest and the parameter values
fluctuations inherent to the problem
unpredictability of future developments
To make the LP problem valid in an environment
of uncertainty, the explicit incorporation of
uncertainty is required
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

LP STRUCTURE

max c T x

s.t.

Ax b

x0

x \ n , A \ mn , b \ m
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

2
 LP STRUCTURE UNDER
UNCERTAINTY
Now, assume that c and b are random with
associated probabilities as illustrated in the
decision tree with 2 possible values for each
state prob.
c 1 , b1 p1
b1
c 1 , b2 p2
c1 b2
c 2, b1 p3
c2 b1
c 2, b2 p4
b2
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

PARAMETER UNCERTAINTY

While c and b have uncertain values with

specified probabilities, there may also exist one

or more completely unknown parameters

Each unknown parameter may be treated as an

additional decision variable as long as the linear

model structure is maintained

ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

3
 EXAMPLE : DAILY STEEL SUPPLY
PLANNING
A plant produces wrenches and pliers

They are made from steel, and the process

involves molding the tools on a molding machine
and then assembling the tools using an
assembly machine

The problem is to determine the number of

wrenches and pliers the plant produces each day
in order to maximize the contributions to
earnings
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

DAILY STEEL SUPPLY PLANNING:

AVAILABLE DATA
resource / parameter wrenches pliers daily availability

steel (k lb) 1.5 1.0 27

molding machine
1.0 1.0 21
(k h)
assembly machine
0.3 0.5 9
(k h)
daily demand
15 16
(k units)
contribution to
130 100
earnings ($/k units)
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

4
 DAILY STEEL SUPPLY PLANNING :
DECISION VARIABLES
We define

W = daily number of wrenches produced

(k units)

P = daily number of pliers produced

(k units)

In terms of the specified data, we can formulate

the LP problem as the deterministic problem
given by:
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

DAILY STEEL SUPPLY PLANNING :

LP FORMULATION

max 130 W + 100 P =

s.t. =
1.5 W + 1.0 P 27 available steel
1.0 W + 1.0 P 21 available molding
0.3 W + 0.5 P 9 available assembly
W 15 wrench demand
P 16 plier demand
W ,P 0 nonnegativity

ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

5
 DAILY STEEL SUPPLY PLANNING :
NEXT QUARTER
For the current quarter, the plant had contracted
with a steel supplier for the delivery of 27 k lb of
steel each day leading to the steel availability
constraint
1.5 W + 1.0 P 27
Now, suppose that the plant manager is planning
the next quarter daily steel supply and that he
needs to determine how much steel to contract
for each day without imposing a constraint on
the available level
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

DAILY STEEL SUPPLY PLANNING :

NEXT QUARTER
The steel market price is $ 58/k lb

The daily demand of steel supply is, then, an

additional decision variable and must be
determined together with the production levels of
the wrenches and the pliers

The problem formulation adds the new decision

variable
S = the daily amount of steel to contract for
next quarter (k lb)
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

6
 DAILY STEEL SUPPLY PLANNING :
REVISED LP FORMULATION
max 130 W + 100 P 58 S
s.t.
1.5 W + 1.0 P S 0 available steel
1.0 W + 1.0 P 21 available molding
0.3 W + 0.5 P 9 available assembly
W 15 wrench demand
P 16 plier demand
W ,P , S 0 nonnegativity
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

DAILY STEEL SUPPLY PLANNING :

COMPARISON OF THE LP PROBLEMS
Commonalities:
the two LP s have similar structures
first LP is, in fact, a special case of the
revised LP with the value of S = 27
Differences:
there is one more decision variable in the
revised LP
objective function in the revised LP includes
an additional term
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

7
 DAILY STEEL SUPPLY PLANNING:
SOURCES OF UNCERTAINTY
The assembly machine capacity for next quarter
is uncertain since the plant has ordered new
assembly machines
these machines serve to replace, as well as
to augment, the existing assembly machines,
but it is unknown whether these new
machines will be delivered in time to be used
during the next quarter
there are two distinct daily capacities of the
assembly machine with the associated
probabilities that are considered
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

DAILY STEEL SUPPLY PLANNING:

SOURCES OF UNCERTAINTY

availability probability
existing
8 k hours 0.7
machines

new
machines 10 k hours 0.3

ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

8
 DAILY STEEL SUPPLY PLANNING:
SOURCES OF UNCERTAINTY
The unit contribution to earnings of each
wrench next quarter is also uncertain due to
fluctuations in the market competition for
wrenches, with two possible outcomes:
contribution
probability
low to earnings
$ 160/k units 0.6
competition

high
competition $ 90/k units 0.4
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

DAILY STEEL SUPPLY PLANNING:

SOURCES OF UNCERTAINTY
resource / parameter wrenches pliers daily availability

S
steel (k lb) 1.5 1.0
(unconstrained)
molding machine
1.0 1.0 21
(k h)
assembly machine P{8} = 0.7
0.3 0.5
(k h) P{10} = 0.3
daily demand
15 16
(k units)
contribution to P{160} = 0.6
100
earnings ($/k units) P{90} = 0.4
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

9
 DAILY STEEL SUPPLY PLANNING
UNDER UNCERTAINTY
Basic assumption: independence of the random
events of the assembly machine availability and
the per unit contribution to earnings of wrenches

The uncertainty results in an uncertain

optimization problem; we use a decision tree to
help in its solution

We also need to have a deterministic rather than

a probabilistic objective in the optimization
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

DAILY STEEL SUPPLY PLANNING :

DECISION TREE STRUCTURE
contribution to assembly
earnings of machine probability
wrenches availability
($/k units) (k hours)

0.7 160 8 0.42

0.6
160 10 0.18
S 0.3
0.7 90 8 0.28
0.4
0.3 90 10 0.12

ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

10
 DAILY STEEL SUPPLY PLANNING :
DECISION VARIABLES
decision variables
(k units)

0.7 W1 P1

0.6
W2 P2
0.3
S
0.7 W3 P3
0.4
0.3 W4 P4

ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

DAILY STEEL SUPPLY PLANNING :

UNCERTAIN LP FORMULATION
The uncertainty in the assembly machine

availability and the contribution to earnings of

wrenches gives rise to 4 possible states

The decision is to determine the optimum values

of the decision variables S, W1, P1, W2, P2, W3, P3,

W4, P4 under all possible states in the next

quarter under an appropriate objective

ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

11
 DAILY STEEL SUPPLY PLANNING :
UNCERTAIN LP FORMULATION
However, to use a LP formulation, we change the
objective to that of the expected value of the
possible realizations of the objective under
uncertainty
In this way, we have to find the solution again a
deterministic LP problem but with
multiple states to represent the uncertain
outcomes
maximization of the expected value of all the
possible outcomes
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

DAILY STEEL SUPPLY PLANNING:

UNCERTAIN LP FORMULATION
max 0.42 (160W1 + 100 P1 ) + 0.18 (160W2 + 100 P2 ) +
0.28 (90W3 + 100 P3 ) + 0.12 (90W4 + 100 P4 ) 58 S
s.t.
1.5W1 + 1.0 P1 S 0
1.0W1 + 1.0 P1 21
0.3W1 + 0.5 P1 8
state 1 constraints
W1 15
P1 16
W1 , P1 0
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

12
DAILY STEEL SUPPLY PLANNING:
UNCERTAIN LP FORMULATION

1.5W2 + 1.0 P2 S 0
1.0W2 + 1.0 P2 21
0.3W2 + 0.5 P2 10
state 2 constraints
W2 15
P2 16
W2 , P2 0

ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

DAILY STEEL SUPPLY PLANNING:

UNCERTAIN LP FORMULATION

1.5W3 + 1.0 P3 S 0
1.0W3 + 1.0 P3 21
0.3W3 + 0.5 P3 8
state 3 constraints
W3 15
P3 16
W3 , P3 0

ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

13
DAILY STEEL SUPPLY PLANNING:
UNCERTAIN LP FORMULATION

1.5W4 + 1.0 P4 S 0
1.0W4 + 1.0 P4 21
0.3W4 + 0.5 P4 10
state 4 constraints
W4 15
P4 16
W4 , P4 0
S0
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

DAILY STEEL SUPPLY PLANNING :

OPTIMAL SOLUTION
decision variable optimal solution value
S 28.50
W1 15.00
P1 6.00
W2 15.00
P2 6.00
W3 12.50
P3 8.50
W4 5.00
P4 16.00
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

14
 DAILY STEEL SUPPLY PLANNING :
INTERPRETATION OF THE SOLUTION
Under the specified uncertainty, the plant should
contract for a daily 28.5 k lb of steel for the next
quarter
With this steel supply, the optimal production
level under any of the 4 states is assured and the
mean value of the objective function is
maximized
However, different production levels result for
each of the 4 possible states as summarized in
the next table
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

DAILY STEEL SUPPLY PLANNING :

INTERPRETATION OF THE SOLUTION
assembly contribution number of number of
machine to earnings wrenches pliers
state
availability of wrenches produced produced
(k h) ($/k units) (k units) (k units)

1 8 160 15 6

2 10 160 15 6

3 8 90 12.5 8.5

4 10 90 5 16
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

15
 SENSITIVITY CASE

Suppose that the following probabilities hold

for the steel supply planning example:

existing 0.2 low

0.5
machines competition

new high
0.5 0.8
machines competition

In this case, the decision tree of probabilities

becomes
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

SENSITIVITY CASE
contribution to assembly
earnings of machine probability
wrenches availability
($/k units) (k h)

0.5 160 8 0.10

0.2
160 10 0.10
S 0.5
0.5 90 8 0.40
0.8
0.5 90 10 0.40

ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

16
 ANOTHER SENSITIVITY CASE

Suppose that instead of replacing the existing

assembly machine, different measures can be

taken to result in 7 possible capacity levels

In addition, due to an increase in the nature of

uncertainty in the wrench market competition,

there are 6 possible earnings contribution levels

ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

ANOTHER SENSITIVITY CASE

To solve the deterministic LP in which the mean

value is also maximized, the weighted sum of the

objective in each of the 42 possible states is

evaluated and optimized

In this case, the decision tree results in 42 sets of

constraints, one for each state

The decision tree becomes more complicated

ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

17
 ANOTHER SENSITIVITY CASE: DECISION
TREE
W1, P1
W2, P2

S 42 different
states

W42, P42

ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

LP MODEL
UNDER UNCERTAINTY
In order to formulate an effective LP model, we

need a reasonably accurate estimate of the

probabilities

For numerical tractability, it is necessary to limit

the description to a reasonably low number of

states
ECE 307 2006 George Gross, University of Illinois at Urbana-Champaign, All Rights Reserved.

18