Sensitivity analysis

and Duality of LP problems

Ha Thi Xuan Chi, PhD

Sensitivity Analysis in LP
How do changes in an LPs parameters (objective function
coefficients, right-hand sides, and technological coefficients)
change the optimal solution?
Types of Sensitivity Analysis

Changes in the objective function coefficients

Changes in Right-hand-side values (RHS)

Changes in the constraint coefficients
Addition of a new constraint

Addition of a new decision variable

Often involves a series of what-if question

NOTATIONS
S*=B-1
A*= B-1. A=S*.A

Basic
varia
ble

xB

y* =cB B

-1

z* =cB B-1 A = y*.A

z*-c =cB B-1 A-c= y*.Ac
Z* 3= cB B-1 b= y*.b

RHS

Coefficient of:

Original
variable

Slack
variable

cB .B-1 .A - c
=
z*-c

cB .B-1
=y*

cB .B-1 .b
=Z*

B-1 .A
=A*

B-1
=S*

B-1 .b
=b*

Consider the following example:

Maximize Profit = $50 X1 + $120 X2
Subject to:
2 X1 + 4 X2 80
3 X1 + X2 60
X1, X2 0

Optimal solution at point A

Profit = 2400
Basic variables: X2=20 , S2 = 40

Non-basic: X1= S1=0.

60

20

50 X1 + 120 X2 =2400

20

40
4

50

Changing in the objective function coefficients, c

Changing in the objective function coefficients, c

(cont.)

Changing in the objective function coefficients, c (cont.)

Final simplex table:
Cj
120
0

Basic
Z
X2
S2

Eq.
(0)
(1)
(2)

Z
1
0
0

50

120

X1

X2

S1

S2

10
0.5
2.5

0
1
0

30
0.25
-0.25

0
0
1

a. Change coefficients of Nonbasic variables: x1

z *1 c1 z *1 c1 (c1 c1 )
2
y *. A c1 30 0 50 c1
3
10 c1 0
c1 10
c1 60
The optimal does not change if

c1 60
7

RHS
2400
20
40

b. Changing in coefficient of the basic variable

Changing in coefficient of the basic variable

Basic
Z
C(X2) X2
0
S2

Eq.
(0)
(1)
(2)

Z
1
0
0

50

C(X2)

X1

X2

S1

S2

10
0.5
2.5

0
1
0

30
0.25
-0.25

0
0
1

The optimality will be unchanged if and only if Zj Cj 0.

With X1: 0.5 C2 + 0 2.5 50 0 => C2 100.
With S1: 0.25 C2+ 0 (-0.25) 0 0 => C2 0.
Combine both conditions, we have 100 C2
9

RHS
2400
20
40

Changing in coefficient of the basic variable

Basic
Z
C(X2) X2
0
S2

Eq.
(0)
(1)
(2)

Z
1
0
0

50

C(X2)

X1

X2

S1

S2

10
0.5
2.5

0
1
0

30
0.25
-0.25

0
0
1

RHS
2400
20
40

Consider the optimal simplex tableau

Row 0 : 10 0 30 0

Change c2 120 to c2 120 c2

New row 0 : 10 0-c2

30 0

For x 2 to stay a basic z 2 *-c2 must be equal to 0.

Gaussian elimination:
Row 0: 10 0-c2

30 0

c2 Row 1: 0.5c2

10 0.5c2

c2

0 0.25c2 30 0

The optimal does not change if

10

0.25c2

0 =

10 0.5c2 0
c2 20

c2 20 c2 100

0.25c2 30 0 c2 120

Changing the right hand side, b i

RHS ranging: the process which determining number of resources
needed to add or to reduce so that we still have the same shadow
price.
Take Quantity divide to corresponding columns in the final tableau,
get:
For S1: The smallest positive ratio is 80. This is how many hours of
resource 1 can be
reduced without changing the current
solution. Hence, we can decrease RHS as much as 80, make
minimum RHS will be (80-80) = 0.

S1

RHS

Ratio

1/4

20

80

- 1/4

40

- 160

The smallest negative ratio is -160. This is how many hours of

resource 1 can be added without changing the current solution.
Maximum value of RHS will be 80-(-160) =240
So, range of RHS of resource 1: (0, 240)
11

Changing the right hand side, b i (cont.)

Shadow Price: The shadow price is the change in objective function

value from increasing of one unit of a scare resource. Where we can find
shadow price? Look at the positive values at Z-row of slack variables,
these values are called shadow prices or duals. If we look at the
nonbasic real variable (X1), we have (10), 10 is so called reduced cost.
The reduced costs are the values those we can reduce in coefficients of
objective function so that the associated variable become basic
variables. Look at the final tableau:

120
0

Basic
Z
X2
S2

Eq.
(0)
(1)
(2)

Z
1
0
0

50

120

X1

X2

S1

S2

10
0.5
2.5

0
1
0

30
0.25
-0.25

0
0
1

Obj. function value will increase

30 when increasing one unit of
resource associated with S1

12

RHS
2400
20
40

Changing the right hand side, bi(cont.)

13

Changing the right hand side, bi (cont.)

TheonlyrevisioninthemodelisthechangesinRHS.

RHSoffinalrow0:z*=y*b

RHSatfinalrows1,...,m=S*b

Basic
Z
C(X2) X2
0
S2

Eq.
(0)
(1)
(2)

Z
1
0
0

X1

X2

S1

S2

10
0.5
2.5

0
1
0

30
0.25
-0.25

0
0
1

RHS
2400
20
40

0.25 0
b1 *
20
1
1
1
b * B b B b B (b b ) 40 0.25 1


2
if b1 change to b1 b1 b1
0.25 0 b1
b1 *
20
b * 40 0.25 1

0
2
14

20 0.25 b1

40 0.25 b

b1
b
2

Changing the right hand side, bi (cont.)

0.25 0
b1 *
20
b * 40 0.25 1

2
20 0.25b1 0 b1

40 0.25b1 0 b1
80 b1 160

b1
0

80
160

80 80 80 b1 160 80
0 120 b1 240
0 b1 240

15

20 0.25 b1

40 0.25 b

The duality in LP

Two of the most important topics in linear

programming are sensitivity analysis and duality.

Every linear programming problem has associated

with it another linear programming problem called
the dual.

16

Primal problem
n

Dual problem
m

Maximize Z= c j x j

Minimize W= b j y j

subject to :

subject to :

j 1

a
j 1

ij

x j b, for i 1, 2,..., m

and x j 0, for j 1, 2,..., n

17

i 1

a
i 1

ij

yi c, for j 1, 2,..., n

and yi 0, for i 1, 2,..., m

Primal problem

Maximize Z=cx
subject to :

18

Dual problem

Maximize W=yb

Ax b

subject to :
yA c

and x 0

and y 0

WYNDOR GLASS CO. PROBLEM

Glass products : windows and glass doors.

Plant 1: Aluminum frames and hardware : Product 1
Plant 2: Wood frame: Product 2
Plant 3: The glass and assembles the products: Product
1 & 2.
Product 1: An 8-foot glass door with aluminum framing
Product 2: A 4x6 foot double-hung wood-framed window
WYNDOR GLASS CO problem: Determine what the
production rates should be for the two products in order
to maximize their total profit
19

WYNDOR GLASS COData

20

Tuesday, September 09,

2014

Primal problem

Maximize Z = 3x1 + 5x2

Subject to
x1
4
2x2 12
3x1 + 2x2 18
x1 0
x2
0.

21

Dual problem

Minimize W = 4y1 + 12y2

+18y3
Subject to
y1
+3y3 3
2y2 +2y3
5
y1 0
y2
0
y3
0

Table 5.1. Row 0 and corresponding dual solution for each iteration for the
Wyndor Glass Co. example

22

The Dual

An alternate formulation of a linear programming

problem as either the original problem or its mirror
image, the dual, which can be solved to obtain the
optimal solution.

Its variables have a different economic interpretation

than the original formulation of the linear
programming problem (the primal).

It can be easily used to determine if the addition of

another variable to a problem will change the optimal.

23

Dual

The number of decision variables in the primal is equal

to the number of constraints in the dual.

The number of decision variables in the dual is equal

to the number of constraints in the primal.

Since it is computationally easier to solve problems

with less constraints in comparison to solving problems
with less variables, the dual gives us the flexibility to
choose which problem to solve.

24

The Duality in LP

Primal (Dual)

Dual (Primal)

Maximization Profit

Minimization Opportunity Cost

Constraints type

Constraints type

Constraints: resources

Constraints: Product profits

Max. Profit = $50 X1 + $120 X2

Min. Opportunity Cost = 80 U1 + 60 U2

Subject to:

Subject to:

2 X1 + 4 X2 80 ( U1)
3 X1 +

X2 60 ( U2)

X1, X2 0

25

2 U1 + 3 U2 50
4 U1 + 1 U2 120
U1, U2 0

( X1)
( X2)

The Duality in LP (contd.)

Steps to form a Dual:

If the primal is maximization, the dual is a minimization, and vice versa

The RHS values of the primal (dual) constraints become the duals
(primals) objective function coefficients.
The transpose of the primal constraint coefficients become the dual
constraint coefficients.
Constraints inequality signs are reversed.

Example:
Primal

Standard primal

Dual

Max Z = 5x1 + 12 x2 + 4x3

Max Z = 5x1 + 12 x2 + 4x3 + 0x4

Min Y = 10 U1+8U2

St.

St.

x1 + 2x2 + x3 10

St.
x1 + 2x2 + x3 + x4 = 10 (U1)

2x1 1x2 + 3x3 = 8

2x1 1x2 + 3x3 + 0x4 = 8 (U2)

x1,x2, x3 0

x1, x2, x3, x4 0

1U1 + 2U2 5
2U1 - 1U2 12
1U1 + 3U2 4
U1

U2 unrestricted
26

Solving Dual problem

Primal (Dual)

Dual (Primal)

Max. Profit = $50 X1 + $120 X2

Min. Opportunity Cost = 80 U1 + 60 U2

Subject to:

Subject to:

2 X1 + 4 X2 80
3 X1 +

2 U1 + 3 U2 50

X2 60

4 U1 + 1 U2 120

Primal optimal solution

Dual optimal solution

Cj

Soluti
on

X1

X2

S1

S2

Quan-tity

Cj

Soluti
on

U1

U2

S1

S2

A1

A2

Quantity

120

X2

1/2

1/4

20

80

U1

1/4

-1/4

1/2

30

S2

5/2

-1/4

40

S1

-5/2

-1/2

-1

10

Zj

60

120

30

2400

Zj

80

20

-20

40

2400

Cj-Zj

-10

-30

Cj-Zj

40

20

M-40

X1=0; X2= 20; S1=0; S2 = 40

U1= 30; U2= 0; S1= 10; S2= 0

- Absolute values of number in the (Cj-Zj) row under slack variables are the solutions of the dual (U is). These are shadow prices.
- Optimal value of objective functions of both problems are equal. Always we have Obj. value of max. problem Obj. value of
min.problem.

27

Z -4x1 -3x2 = 0
Z = 4x1+ 3x2

Thus, an increase of q units in x1 results in an increase of 4q units in the objective function or

equivalently a decrease of -4q units
The implications of this observation can be summarised as follows:
If you maximize, look for non-basic variables with negative reduced costs
If you minimize, look for non-basic variables with positive reduced costs

28

29