Parametric Linear Programming

1. Parametric Linear Programming

Parametric Linear
Programming-1

2. Systematic Changes in cj

n
Objective function
Z = å c j x j is replaced by
j =1
n
Z ( q ) = å ( c j + a jq ) x j
j =1
Find the optimal solution as a function of θ
Z*(θ)
0
θ1
θ2
θ
Parametric Linear
Programming-2

3. Example: Wyndor Glass Problem

• Z(θ) = (3 + 2θ) x1+(5 - θ) x2
Parametric Linear
Programming-3

4. Example: Wyndor Glass Problem

Range
of θ
0 ≤ θ ≤ 9/7
Basic
Var.
Z
x1
x2
x3
x4
x5
RHS
Z(θ)
1
0
0
0
(9-7θ)/6
(3+2θ)/3
36-2θ
x3
0
0
0
1
1/3
-1/3
2
x2
0
0
1
0
1/2
0
6
x1
0
1
0
0
-1/3
1/3
2
Parametric Linear
Programming-4

5. Example: Wyndor Glass Problem

Range
of θ
9/7 ≤ θ ≤ 5
Basic
Var.
Z
x1
x2
x3
x4
x5
RHS
Z(θ)
1
0
0
(-9+7θ)/2
0
(5-θ)/2
27+5θ
x4
0
0
0
3
1
-1
6
x2
0
0
1
-3/2
0
1/2
3
x1
0
1
0
1
0
0
4
Parametric Linear
Programming-5

6. Example: Wyndor Glass Problem

Range
of θ
θ≥5
Basic
Var.
Z
x1
x2
x3
x4
x5
RHS
Z(θ)
1
0
-5+θ
3+2θ
0
0
12+8θ
x4
0
0
2
0
1
0
12
x5
0
0
2
-3
0
1
6
x1
0
1
0
1
0
0
4
Parametric Linear
Programming-6

7. Procedure Summary for Systematic Changes in cj

1. Solve the problem with θ = 0 by the simplex method.
2. Use the sensitivity analysis procedure to introduce the
Δcj = αjθ changes into Eq.(0).
3. Increase θ until one of the nonbasic variables has its
coefficient in Eq.(0) go negative (or until θ has been
increased as far as desired).
4. Use this variable as the entering basic variable for an
iteration of the simplex method to find the new optimal
solution. Return to Step 3.
Parametric Linear
Programming-7

8. Systematic Changes in bi

n
Constraints
åa x
j
£ bi for i = 1, 2,K , m
åa x
j
£ bi + aiq for i = 1, 2,K , m
j =1
n
j =1
ij
ij
are replaced by
Find the optimal solution as a function of θ
Z*(θ)
0
θ1
θ2
θ
Parametric Linear
Programming-8

9. Example: Wyndor Glass Problem

• y1
+ 3y3 ≥ 3 + 2θ
2y2 + 2y3 ≥ 5 - θ
Parametric Linear
Programming-9

10. Example: Wyndor Glass Problem

Range
of θ
0 ≤ θ ≤ 9/7
Basic
Var.
Z
y1
y2
y3
y4
y5
RHS
Z(θ)
1
2
0
0
2
6
-36+2θ
y3
0
1/3
0
1
-1/3
0
(3+2θ)/3
y2
0
-1/3
1
0
1/3
-1/2
(9-7θ)/6
Parametric Linear
Programming-10

11. Example: Wyndor Glass Problem

Range
of θ
9/7 ≤ θ ≤ 5
Basic
Var.
Z
y1
y2
y3
y4
y5
RHS
Z(θ)
1
0
6
0
4
3
-27-5θ
y3
0
0
1
1
0
-1/2
(5-θ)/2
y1
0
1
-3
0
-1
3/2
(-9+7θ)/2
Parametric Linear
Programming-11

12. Example: Wyndor Glass Problem

Range
of θ
θ≥5
Basic
Var.
Z
y1
y2
y3
y4
y5
RHS
Z(θ)
1
0
12
6
4
0
-12-8θ
y5
0
0
-2
-2
0
1
-5+θ
y1
0
1
0
3
-1
0
3+2θ
Parametric Linear
Programming-12

13. Procedure Summary for Systematic Changes in bi

1. Solve the problem with θ = 0 by the simplex method.
2. Use the sensitivity analysis procedure to introduce the
Δbi = αiθ changes to the right side column.
3. Increase θ until one of the basic variables has its value
in the right side column go negative (or until θ has been
increased as far as desired).
4. Use this variable as the leaving basic variable for an
iteration of the dual simplex method to find the new
optimal solution. Return to Step 3.
Parametric Linear
Programming-13