Lecture 5
Linear Programming
Bruce F. Wollenberg, University of Minnesota
LP Problem
Maximize Production of 2 Plants
x1 is the output from plant 1
x2 is the output from plant 2
Benefit Of Product Plant 1, c1 = 3 [ $/MWh]
Benefit Of Product Plant 2, c2 = 5 [ $/MWh]
The Objective Function expresses the overall benefit
to be optimized, our objective function is:
Maximize: 3 x1 + 5 x2
Plant maximum output constraints:
Maximum Production of Plant 1, b1 = 4
Maximum Production of Plant 2, b2 = 6
Plants Must Meet an additional inequality constraint:
3 x1 + 2 x2 18
Bruce F. Wollenberg, University of Minnesota
Mathematical statement of the LP
Bruce F. Wollenberg, University of Minnesota
The feasible region for the LP
X2
x2 6
8
7
(2,6)
6
5
x1 0
3x1 + 2x2 18
(0,6)
FEASIBLE
REGION
(4,3)
x1 4
2
1
(0,0)
(4,0)
X1
x2 0
Bruce F. Wollenberg, University of Minnesota
Summary of the LP
Bruce F. Wollenberg, University of Minnesota
LP objective function
Bruce F. Wollenberg, University of Minnesota
LP in canonical form with slack
variables
Bruce F. Wollenberg, University of Minnesota
Basic feasible solutions
Bruce F. Wollenberg, University of Minnesota
All basic feasible solutions
1 0 1 0 0
A= 0 1 0 1 0
3 2 0 0 1
4
b= 6
18
1
x1 1 0 1 4 2
Set 1: x2 =0 1 0 6 = 6 z =36 ()
x3 3 2 0 18 2
x4 = 0
x5 = 0
x1 1 0 0 4 4
Set 2: x2 =0 1 1 6 = 3 z =27
x4 3 2 0 18 3
Bruce F. Wollenberg, University of Minnesota
x3 = 0
x5 = 0
x1
Set 3: =
x
2
x5
1 0 0 4
0 1 0 =
3 2 1 18
4
6 OUT
6
x3 = 0
fails condition that all x are 0
x4 = 0
x1 1 1 0 4 6
Set 4: x3 =0 0 1 6 = 2 OUT
x4 3 0 0 18 6
x2 = 0
fails condition that all x are 0
x5 = 0
x1 1 1 0 4
Set 5: x3 = 0 0 0 6 = OUT
x5 3 0 1 18
x2 = 0
A matrix singular
x4 = 0
x1 1 0 0 4 4
Set 6: x4 =0 1 0 6 = 6 z =12
x5 3 0 1 18 6
x2 = 0
x3 = 0
Bruce F. Wollenberg, University of Minnesota
10
x2
Set 7: =
x
3
x4
0 1 0 4
1 0 1 =
2 0 0 18
9
4 NO
3
x1 = 0
x5 = 0
fails condition that all x are 0
x2 0 1 0 4 6
Set 8: x3 =1 0 0 6 = 4 z =30
x5 2 0 1 18 6
x1 = 0
x4 = 0
x2 0 0 0 4
Set 9: x4 = 1 1 0 6 = OUT
x5 2 0 1 18
x3
Set 10: x4 =
x5
1 0 0 4
0 1 0 6 =
0 0 1 18
4
6=
z 0
18
x1 = 0
x3 = 0
A matrix singular
x1 = 0
x2 = 0
Bruce F. Wollenberg, University of Minnesota
11
The Simplex Method
Starting with our basic LP problem:
Minimize z = cT
Subject to
A
x
x = b
x 0
We partition the A matrix and the x and c vectors into basic and non-basic parts:
=
z
Minimize
Subject to
cBT
B
xB
xB
xB
+ cTN
+ N
xN
xN
xN
Bruce F. Wollenberg, University of Minnesota
=
b
0
0
12
The Simplex Method
Last of all we carry out the following matrix multiplys:
=
xB B 1b B 1 NxN
z=
cBT B 1b cBT B 1 NxN + cTN xN
Now we will observe:
b B 1b
T cBT B 1
Y B 1 N
where is a vector called the Dual variable vector.
Bruce F. Wollenberg, University of Minnesota
13
The Simplex Method
This leads to a reformulation of our standard form of the LP:
Minimize
Subject to x B
= cTB
T N cTN x N
Y
xN
xB
xN
0
0
We will now define d T T N cTN as the reduced cost vector, and this allows us to write the new
standard form as:
Minimize
Subject to x B
xB
= cTB
=
b - d T
b - Y
xN
xN
xN
Bruce F. Wollenberg, University of Minnesota
0
0
14
Pivoting
Bruce F. Wollenberg, University of Minnesota
15
Simplex Mechanism
If d j is positive, the objective function decreases if the non- basic variable
If the non-basic variable
If some Y 's are positive, the corresponding basic variables
xNj
The non-basic variable
the value of
is positive
xBi s decrease if the non-
xNj increases
that is, until b Y
xNj increases, the basic variable xBi decreases if Yij
ij
basic variable
xNj increases
xNj
ij Nj
can be increased until the first basic variable becomes zero,
becomes 0 for the first i
Minimum bi
becomes
:Yij >0
1 i m Yij
Figure 2.1 the value of
xBi becomes 0
Bruce F. Wollenberg, University of Minnesota
16
Simplex Pseudo Code
1. get a basic feasible solution (see next page)
2. find out if the current solution is the minimizer: if all d < 0 stop, the current solution is the
minimizer; otherwise go on
3. find out which non-basic variable enters the basis,
xNj
(most positive d j )
Minimum bi
4. find out which basic variable x leaves the basis,
:Yij >0
Bi
1 i m Yij
5. build the new basis
6. get a new basic feasible solution
3.07. go to 2
Bruce F. Wollenberg, University of Minnesota
17
Steps to LP solution
Bruce F. Wollenberg, University of Minnesota
18
LP features
Upper and Lower bounding: A feature of many LP algorithms
available today (for example the LP in the Matlab Optimization
Toolbox) is to directly give vectors of upper and lower bounds
on each LP variable instead of explicitly building constraints for
each limit. Most of the LP problems we have encountered in
power system operation have upper and lower bounds on
variables.
Sensitivity analysis: The Matlab LP allows students to see the
lambda values for all constraints including all variable upper
bound constraints, all variable lower bound constraints, all
linear equality constraints and all linear inequality constraints.
Initial value of the variables: For some problems this may make
a difference in run time, if not specified the algorithm will find
an initial basis by itself and
then proceed to the optimum.
Bruce F. Wollenberg, University of Minnesota
19
THANK YOU
Bruce F. Wollenberg, University of Minnesota
20
