Sensitivity Analysis

Question: What is Sensitivity Analysis?

Answer: The investigation that deals with changes in the optimal solution due to changes in the
parameters (𝑎𝑖 , 𝑏𝑖 , 𝑐𝑖 ) is called Sensitivity Analysis (SA).
Question: Why is sensitivity analysis important in linear programming?
Answer: The target of sensitivity analysis is to discover new optimal solution for a LP and to
perceive how sensitive these changes are to the optimal solution. In LP, the parameters of the
model can change inside specific limits without making the optimal solution change.
Question: Why is a sensitivity analysis necessary for linear programming problems?
Answer: Sensitivity analysis allows the analyst to assess the effects of changes in the data values, to
detect outliers or wrong data, to define testing strategies, to increase the reliability, to optimize
resources, reduce costs, etc.
Question: What type of changes happen in sensitivity analysis?
Answer: There are five types of changes happen in sensitivity analysis as follows:
1. Changes in the requirement vector 𝑏.
2. Changes in the cost vector 𝐶.
3. Changes in the element of coefficient matrix 𝐴.
4. Structural Changes due to the addition and deletion of some variables.
5. Structural Changes due to the addition and deletion of some Constraints.
Question: What are the uses of sensitivity analysis?
Answer: There are several uses for sensitivity analysis across many careers and industries. Various
situations require the use of sensitivity analysis for forecasting, predicting, identifying areas of
improvement or making adjustments. Here are some common applications of sensitivity analysis:
 Understanding how input variables relate to output variables
 Creating a hypothesis for testing certain scenarios
 Making recommendations.
 Communicating data and outcomes.
 Identifying break-even points, critical values and optimal strategy changes.
 Feasibility testing for an ideal solution.
 Estimating requirements for output and input variables.
 Quantifying parameters
 Making assumptions to allow decision making
 Assessing the amount of risk for a scenario or strategy
 Identifying sensitive variables.

Md. Syful Islam, Assistant Professor, Dept. of Statistics, Chittagong College (01718558010) 1
  Developing recommendations.
Question: Describe the discrete changes in the requirement vector 𝒃.
Answer: Let us consider the L.p.p.
Maximize Z = cX
Subject to AX = b , 𝑋 ≥ 𝑜 , 𝑏 ≥ 𝑜
If 𝑋𝐵 is the optimum basic feasible solution with the optimum basis B then 𝑋𝐵 = 𝐵 −1 𝑏
Now let the component 𝑏𝑘 ∈ 𝑏 be changed to 𝑏𝑘 + ∆𝑏𝑘 , sothat the new requirement vector is 𝑏 ∗ .
Then 𝑏 ∗ = [ 𝑏1, 𝑏1 ,…… 𝑏1 + ∆𝑏𝑘 , 𝑏𝑘+1 ……………… 𝑏𝑚 ]. Since no other changes are made, therefore
the current basic variables 𝑋B1 …….. XBm continue to constitute a set of basic variables in the new
solution. Let XB be the new basic feasible solution.
𝑚 𝑚
⃗⃗⃗⃗𝑘 = 𝑋𝐵 + ∑ ∆𝑏𝑘 ⃗⃗⃗⃗
𝑋𝐵∗ = 𝐵 −1 𝑏 ∗ = 𝐵 −1 𝑏 + ∑ ∆𝑏𝑘 𝛽 𝛽𝑘
𝑘=1 𝑘=1

If the new solution 𝑋𝐵𝑖 is feasible then

𝑚
∗
𝑋𝐵𝑖 ≥ 0 ⇒ 𝑋𝐵𝑖 + ∑ ∆𝑏𝑘 ⃗⃗⃗⃗⃗
𝛽𝑘 ≥ 0
𝑘=1

⃗⃗⃗⃗𝑘 is the k-th column vector of 𝐵 −1

Where 𝛽
Thus when only one component of b. say 𝑏𝑘 is changed then
𝑋𝐵𝑖 + 𝑏𝑖𝑘 ∆𝑏𝑘 ≥ 0, 𝑖 = 1,2, … … … 𝑚
Where 𝑏𝑖𝑘 is the (i , k) th element of 𝐵 −1
𝑥
⇒ ∆𝑏𝑘 ≥ − 𝑏𝐵𝑖 if 𝑏𝑖𝑘 > 0 … … … … (1)
𝑖𝑘
𝑥
and ∆𝑏𝑘 ≤ − 𝑏𝐵𝑖 𝑖𝑓 𝑏𝑖𝑘 < 0 … . . (2)
𝑖𝑘

Combining (1) and (2), we can say that the optimality remains unaffected if ∆𝑏𝑘 lies in the interval
𝑥 𝑥
Max (− 𝑏𝐵𝑖 ; 𝑏𝑖𝑘 > 0) ≤ ∆𝑏𝑘 ≤ 𝑀𝑖𝑛( − 𝑏𝐵𝑖 ; 𝑏𝑖𝑘 < 0 )
𝑖𝑘 𝑖𝑘

Here if no 𝑏𝑖𝑘 < 0 there is no upper bound.

∗
If 𝑏𝑖𝑘 = 0 for some i then 𝑋𝐵𝑖 = 𝑋𝐵𝑖 ≥ 0.
[N.B: If the problem is minimization type then the problem will be converted to maximization
type by multiplying −𝟏 then the procedure above will be continue for sensitivity analysis.]
Problem: Solve the following L.P.P. and discuss the effect of discrete changes in the
requirement vector b.
Maximize 𝒁 = 𝟑𝒙𝟏 + 𝟒𝒙𝟐 + 𝒙𝟑 + 𝟕𝒙𝟒
𝑺/𝒕 ∶ 𝟖𝒙𝟏 + 𝟑𝒙𝟐 + 𝟒𝒙𝟑 + 𝒙𝟒 ≤ 𝟕
𝟐𝒙𝟏 + 𝟔𝒙𝟐 + 𝒙𝟑 + 𝟓𝒙𝟒 ≤ 𝟑
𝒙𝟏 + 𝟒𝒙𝟐 + 𝟓𝒙𝟑 + 𝟐𝒙𝟒 ≤ 𝟖

Md. Syful Islam, Assistant Professor, Dept. of Statistics, Chittagong College (01718558010) 2
 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 , 𝒙𝟒 ≥ 𝟎
Solution: Introducing slack variables𝑥5 ≥ 0, 𝑥6 ≥ 0 𝑎𝑛𝑑 𝑥7 ≥ 0 one to each constraint, we get
Maximize 𝑧 = 3𝑥1 + 4𝑥2 + 𝑥3 + 7𝑥4 + 0. 𝑥5 + 0. 𝑥6 + 0. 𝑥7
S/t : 8𝑥1 + 3𝑥2 + 4𝑥3 + 𝑥4 + 𝑥5 + 0. 𝑥6 + 0. 𝑥7 = 7
2𝑥1 + 6𝑥2 + 𝑥3 + 5𝑥4 + 0. 𝑥5 + 𝑥6 + 0. 𝑥7 = 3
𝑥1 + 4𝑥2 + 5𝑥3 + 2𝑥4 + 0. 𝑥5 + 0. 𝑥6 + 𝑥7 = 8
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 , 𝑥7 ≥ 0
𝑐𝑗 3 4 1 7 0 0 0 Const. Min
𝑐𝐵 Basis 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥6 𝑥7 b ratio

0 x5 8 3 4 1 1 0 0 7 7
0 x6 2 6 1 5* 0 1 0 3 3/5*
0 x7 1 4 5 2 0 0 1 8 4

𝑧𝑗 − 𝑐𝑗 -3 -4 -1 -7 0 0 0 Z=0
0 x5 38/5* 9/5 19/5 0 1 -1/5 0 32/5 16/19*
7 x4 2/5 6/5 1/5 1 0 1/5 0 3/5 3/2
0 x7 1/5 8/5 23/5 0 0 -2/5 1 34/5 34

𝑧𝑗 − 𝑐𝑗 -1/5 22/5 2/5 0 0 7/5 0 Z= 21/5

3 x1 1 9/88 1/2 0 5/38 -1/38 0 16/19
7 x4 0 21/19 0 1 -1/19 3/38 0 5/19
0 x7 0 59/38 9/2 0 -1/38 -15/38 1 126/1
9
𝑧𝑗 − 𝑐𝑗 0 160/38 1/2 0 1/38 53/38 0 Z=83/19

Since all 𝑧𝑗 − 𝑐𝑗 ≥ 0, the optimality conditions are satisfied and optimum solution
16 5
𝑥1 = , 𝑥2 = 0, 𝑥3 = 0 , 𝑥4 = 19 and Max z =83/19
9
16 5 126
∴ 𝑥𝐵 = [19 , 19 , ] 𝑎𝑛𝑑 𝑏 = [7, 3, 8 ]
19
5 1
− 38 0
38
1 3
And 𝐵 −1 = − 19 38
0 , 𝑎𝑙𝑠𝑜 𝑏 = [𝑏1 , 𝑏2 , 𝑏3 ] (let)
1 15
− 38 − 38 1
( )
Let changes of 𝑏 be ∆𝑏𝑘
𝑀𝑎𝑥 −𝑥𝑏𝑖 𝑀𝑖𝑛 −𝑥𝑏𝑖
∴ ( 𝑏 ; 𝑏𝑖𝑘 > 0) ≤ ∆𝑏𝑘 ≤ ( 𝑏 ; 𝑏𝑖𝑘 < 0)
𝑖 𝑖𝑘 𝑖 𝑖𝑘

Where 𝑏𝑖𝑘 is the (𝑖, 𝑘) the element of 𝐵 −1

Md. Syful Islam, Assistant Professor, Dept. of Statistics, Chittagong College (01718558010) 3
∴ The individual range of changes in b1, b2, and b3 such that the optimality of new basic feasible
solution is not violated are given by
16 5 126
− −
− 19
5 ≤ ∆𝑏1 ≤ 𝑀𝑖𝑛 ( 19
1 , 19
1 ) [Since k=1 i.e 1st column of 𝐵 −1 gives bik]
− −
38 19 38

31
⇒− ≤ ∆𝑏1 ≤ 5
5
5 16 126
−
− 19
8 ≤ ∆𝑏2 ≤ 𝑀𝑖𝑛 (−
19
1 , 19
1 ) [Since k=2 i.e 2nd column of 𝐵 −1 gives bik]
− −
38 38 38

5
⇒ − 4 ≤ ∆𝑏2 ≤ 84/5
126
− 19
≤ ∆𝑏3 [Since k=3 i.e 3rd column of 𝐵 −1 gives bik]
1
126
⇒− ≤ ∆𝑏3
19
31
Range of change of b1 is − ≤ ∆𝑏1 ≤ 5
5
5
Range of change of b2 is − 4 ≤ ∆𝑏2 ≤ 84/5
126
Range of change of b3 is − ≤ ∆𝑏3
19

For which optimum solution remain unchanged. Here ∆𝑏3 has no upper bound.
Problem: Solve the following L.P.P. and discuss the effect of discrete changes in the
requirement vector b.
Maximize 𝒁 = 𝟐𝒙𝟏 + 𝒙𝟐
𝑺/𝒕 ∶ 𝟑𝒙𝟏 + 𝟓𝒙𝟐 ≤ 𝟏𝟓
𝟔𝒙𝟏 + 𝟐𝒙𝟐 ≤ 𝟐𝟒
𝒙𝟏 , 𝒙𝟐 ≥ 𝟎
Solution: Introducing slack variables 𝑥3 ≥ 0, 𝑎𝑛𝑑 𝑥4 ≥ 0 one to each constraint, we get
Maximize 𝑧 = 3𝑥1 + 4𝑥2 + 0. 𝑥3 + 0. 𝑥4
S/t : 3𝑥1 + 5𝑥2 + 𝑥3 + 0. 𝑥4 = 15
6𝑥1 + 2𝑥2 + 0. 𝑥3 + 𝑥4 = 24
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0
𝑐𝑗 2 1 0 0 Const. Min
𝑐𝐵 Basis 𝑥1 𝑥2 𝑥3 𝑥4 b ratio
0 𝑥3 3 5 1 0 15 5
0 𝑥4 (6) 2 0 1 24 4*

𝑧𝑗 − 𝑐𝑗 −2 ↑ -1 0 0 Z=0
0 𝑥2 0 (4) 1 −1/2 3 3/4 ∗
𝑥1 1/3 1/6

Md. Syful Islam, Assistant Professor, Dept. of Statistics, Chittagong College (01718558010) 4
 2 1 0 4 12

𝑧𝑗 − 𝑐𝑗 0 −1/3 ↑ 0 1/3 Z= 8
1 𝑥2 0 1 1/4 -1/8 3\4
2 𝑥1 1 0 -1/12 5/24 15/4

𝑧𝑗 − 𝑐𝑗 0 0 1/3 7/24 𝑍 = 33/4

15
Since all 𝑧𝑗 − 𝑐𝑗 ≥ 0. Thus the optimality conditions are satisfied. The optimum solution 𝑥1 = ,
4
3 33
𝑥2 = 4 and Max 𝑧 = 4
15 3
∴ 𝑥𝐵 = [𝑥2 , 𝑥1 ] = [ 4 , 4] 𝑎𝑛𝑑 𝑏 = [15, 24 ]
1/4 −1/8
And 𝐵 −1 = ( ) , 𝑎𝑙𝑠𝑜 𝑏 = [𝑏1 , 𝑏2 , ] (let)
−1/12 5/24
Let changes of 𝑏 be ∆𝑏𝑘
𝑀𝑎𝑥 −𝑥𝑏𝑖 𝑀𝑖𝑛 −𝑥𝑏𝑖
∴ ( 𝑏 ; 𝑏𝑖𝑘 > 0) ≤ ∆𝑏𝑘 ≤ ( 𝑏 ; 𝑏𝑖𝑘 < 0)
𝑖 𝑖𝑘 𝑖 𝑖𝑘

Where 𝑏𝑖𝑘 is the (𝑖, 𝑘) the element of 𝐵 −1

∴ The individual range of changes in 𝑏1 and 𝑏2 such that the optimality of new basic feasible
solution is not violated are given by
15
−3/4 −
For 𝑘 = 1 ⇒ max ( 1/4 ) ≤ ∆𝑏1 ≤ 𝑀𝑖𝑛 ( 4
1 ) [Since k=1 i.e 1st column of 𝐵 −1 gives bik]
−
12

⇒ −3 ≤ ∆𝑏1 ≤ 45
15 3
− −
For 𝑘 = 2 ⇒ 𝑀𝑎𝑥 ( 5
4
) ≤ ∆𝑏2 ≤ 𝑀𝑖𝑛 ( ) [Since k=2 i.e 2nd column of 𝐵 −1 gives bik]
4
1
−
24 8

⇒ −18 ≤ ∆𝑏2 ≤ 6
Range of change of b1 is −3 ≤ ∆𝑏1 ≤ 45
Range of change of b2 is −18 ≤ ∆𝑏2 ≤ 6
∴ The required range of variation of 𝑏1 is 15 − 3 ≤ 𝑏1 ≤ 15 + 45 |𝑠𝑖𝑛𝑐𝑒 𝑏1 = 15
⇒ 12 ≤ 𝑏1 ≤ 60
∴ The required range of variation of 𝑏2 is 24 − 18 ≤ 𝑏2 ≤ 24 + 6 |𝑠𝑖𝑛𝑐𝑒 𝑏2 = 24
⇒ 6 ≤ 𝑏1 ≤ 30
Question: Describe the discrete changes in the cost vector 𝒄.
Answer: Let us consider the L.P.P.
Maximize 𝑧 = 𝑐𝑥
Subject to 𝐴𝑥 = 𝑏 , 𝑋 ≥ 𝑜 , 𝑏 ≥ 𝑜
If 𝑥𝐵 is the optimum basic feasible solution with the optimum basis B then 𝑥𝐵 = 𝐵 −1 𝑏

Md. Syful Islam, Assistant Professor, Dept. of Statistics, Chittagong College (01718558010) 5
Now let the cost vector 𝐶 be replaced by a new cost vector 𝐶 ∗ then the problem
Maximize 𝑍 ∗ = 𝑐 ∗ 𝑥
Subject to 𝐴𝑥 = 𝑏 , 𝑥 ≥ 𝑜 , 𝑏 ≥ 𝑜
We observe that the constraint set is not affected at all by such a change in 𝑐 and thus the current
basic solution 𝑥𝐵 remains at least feasible.
Let ∆𝑐𝑗 be the amount which is added to the jth component 𝑐𝑗 of 𝑐 = [𝑐1 , 𝑐2 , … … . 𝑐𝑛 ] so that the
new value of the jth cost component becomes 𝑐𝑗∗ = 𝑐𝑗 + ∆𝑐𝑗
There are two cases may arise
(i) 𝑐𝑗 is the cost component corresponding to a non-basic variable i.e 𝑐𝑗 ∉ 𝑐𝐵
(ii) 𝑐𝑗 is he cost component corresponding to an optimal basic variable i.e 𝑐𝑗 ∈ 𝑐𝐵 .
Case –I: At the optimal stages 𝑧𝑗∗ − 𝑐𝑗∗ = 𝑧𝑗 − (𝑐𝑗 + ∆𝑐𝑗 )
Thus the current solution will remain optimum if
𝑧𝑗∗ − 𝑐𝑗∗ ≥ 0
𝑧𝑗 − (𝑐𝑗 + ∆𝑐𝑗 ) ≥ 0
⇒ 𝑧𝑗 − 𝑐𝑗 ≥ ∆𝑐𝑗
⇒ ∆𝑐𝑗 ≤ 𝑧𝑗 − 𝑐𝑗 … … … (𝑖)
We can say that there is no lower bound of ∆𝑐𝑗 and any change of 𝑐𝑗 does not change the value of
the objective function. Since 𝑥𝑗 = 0 (non-basic) variable.
Case II: Let 𝑥𝑘 = 𝑥𝐵𝑟 be the r-th component of basic variable [𝑟 = 1, 2, … . 𝑚] and the cost
component 𝑐𝑘 = 𝑐𝐵𝑟 corresponding to 𝑋𝑘 changes to 𝑐𝐵𝑟 + ∆𝑐𝐵𝑟 .
Now the change of 𝑐𝑘 affects all 𝑧𝑗 for all 𝑗 in the basis.
𝑧𝑗∗ − 𝑐𝑗∗ = 𝑐𝐵 𝑦𝑗 − 𝑐𝑗
= ∑𝑚
𝑖=1 𝑐𝐵𝑖 𝑦𝑖𝑗 − 𝑐𝑗 + (𝑐𝐵𝑟 + ∆𝑐𝐵𝑟 )𝑦𝑟𝑗
𝑖≠𝑟

= ∑𝑚 𝑚
𝑖=1 𝑐𝐵𝑖 𝑦𝑖𝑗 + ∆𝑐𝐵𝑟 𝑦𝑟𝑗 − 𝑐𝑗 + ∆𝑐𝐵𝑟𝑦𝑟𝑗 = 𝑧𝑗 − 𝑐𝑗 + ∆𝑐𝐵𝑟 𝑦𝑟𝑗 |𝑧𝑗 = ∑𝑖=1 𝑐𝐵𝑟 𝑦𝑟𝑗
𝑖≠𝑘

Now the current solution will remain optimum if

𝑧𝑗∗ − 𝑐𝑗∗ ≥ 0 ; ∀ 𝑗 ∉ 𝐵
⇒ 𝑧𝑗 − 𝑐𝑗 + ∆𝑐𝐵𝑟 𝑦𝑟𝑗 ≥ 0 … … … . (𝑖𝑖)
If 𝑦𝑟𝑗 = 0 for some 𝑗 then 𝑧𝑗 − 𝑐𝑗 + ∆𝑐𝐵𝑟 𝑦𝑟𝑗 ≥ 0
−(𝑧𝑗 −𝑐𝑗 )
If 𝑦𝑟𝑗 < 0 then (ii) ⇒ ∆𝑐𝐵𝑟 ≤ … . . (𝑖𝑖𝑖)
𝑦𝑟𝑗

−(𝑧𝑗 −𝑐𝑗 )
If 𝑦𝑟𝑗 > 0 then (ii) ⇒ ∆𝑐𝐵𝑟 ≥ … . . (𝑖𝑣)
𝑦𝑟𝑗

Combining (iii) and (iv) we have

Md. Syful Islam, Assistant Professor, Dept. of Statistics, Chittagong College (01718558010) 6
𝑀𝑎𝑥 −(𝑧𝑗−𝑐𝑗) 𝑀𝑖𝑛 −(𝑧𝑗−𝑐𝑗)
( ; 𝑦𝑟𝑗 > 0) ≤ ∆𝑐𝐵𝑟 = ∆𝑐𝑘 ≤ ( ; 𝑦𝑟𝑗 < 0 )
𝑗 𝑦𝑟𝑗 𝑗 𝑦𝑟𝑗

⇒ 𝑀𝑎𝑥 −(𝑧𝑗−𝑐𝑗) 𝑀𝑖𝑛 −(𝑧𝑗−𝑐𝑗)

( 𝑦 ; 𝑦𝑟𝑗 > 0) ≤ ∆𝑐𝑘 ≤ ( 𝑦 ; 𝑦𝑟𝑗 < 0 )
𝑗 𝑟𝑗 𝑗 𝑟𝑗

For all 𝑐𝑗 ∉ 𝑐𝐵 .
If no 𝑦𝑟𝑗 ≥ 0, there is no lower bound of ∆𝑐𝑘 and if no 𝑦𝑟𝑗 < 0, there is no upper bound of ∆𝑐𝑘 .
Here the value of objective function changes by
∆𝑐𝐵𝑟 𝑋𝐵𝑟 = ∆𝑐𝑘 𝑋𝑘
Problem: Solve the following L.P.P. and discuss the variation is 𝒄𝒋 (𝒋 = 𝟏, 𝟐) for which optimal
solution does not change
𝑴𝒂𝒙𝒊𝒎𝒊𝒛𝒆 𝒛 = 𝟑𝒙𝟏 + 𝟓𝒙𝟐
Subject to: 𝒙𝟏 + 𝒙𝟐 ≤ 𝟏
𝟐𝒙𝟏 + 𝟑𝒙𝟐 ≤ 𝟏
𝒙𝟏 , 𝒙𝟐 ≥ 𝟎.
Solution: Introducing slack variables 𝑥3 ≥ 0, 𝑎𝑛𝑑 𝑥4 ≥ 0 one to each constraint, we get
Maximize 𝑧 = 3𝑥1 + 5𝑥2 + 0. 𝑥3 + 0. 𝑥4
S/t : 𝑥1 + 𝑥2 + 𝑥3 + 0. 𝑥4 = 1
2𝑥1 + 3𝑥2 + 0. 𝑥3 + 𝑥4 = 1
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0
𝑐𝑗 3 5 0 0 Const. Min
𝑐𝐵 Basis 𝑥1 𝑥2 𝑥3 𝑥4 b ratio

0 𝑥3 1 1 1 0 1 1
0 𝑥4 2 (3) 0 1 1 1/3*

𝑧𝑗 − 𝑐𝑗 −3 −5 ↑ 0 0 Z=0
0 𝑥3 1/3 0 1 −1/3 2/3
2 𝑥2 2/3 1/3 0 1/6 1/3

𝑧𝑗 − 𝑐𝑗 1/3 0 0 5/3 Z= 5/3

Since all 𝑧𝑗 − 𝑐𝑗 ≥ 0. Thus the optimality conditions are satisfied. The optimum solution 𝑥1 = 0,
1 5
𝑥2 = 3 and Max 𝑧 = 3.

Since 𝑐1 ∉ 𝑐𝐵 , the change ∆𝑐1 in 𝑐1 . Sothat solution is optimum, is given by

1
∆𝑐1 ≤ 𝑧1 − 𝑐1 ⇒ ∆𝑐1 ≤ 3

There is no lower bound.

Md. Syful Islam, Assistant Professor, Dept. of Statistics, Chittagong College (01718558010) 7
 1 10
∴ variation of 𝑐1is 𝑐1 ≤ 3 + 3 ⇒ 𝑐1 ≤ 3
10
∴ 𝑐1 ≤ , has no lower bound.
3

Since 𝑐2 ∈ 𝑐𝐵 , The range of change ∆𝑐2 in 𝑐2 is given by

𝑀𝑎𝑥 −(𝑧𝑗−𝑐𝑗) 𝑀𝑖𝑛 −(𝑧𝑗−𝑐𝑗)
∴ ( 𝑦 ; 𝑦2𝑗 > 0) ≤ ∆𝑐2 ≤ ( 𝑦 ; 𝑦2𝑗 < 0)
𝑗 2𝑗 𝑗 2𝑗

𝑀𝑎𝑥 −1/3 −5/3

⇒ ( 2/3 , 1/3 ) ≤ ∆𝑐2 | 𝑁𝑜 𝑦2𝑗 < 0
𝑗
1
⇒ − 2 ≤ ∆𝑐2 . There is no lower bound of ∆𝑐2.
1 9
∴ Variation of 𝑐2 is 5 − 2 ≤ 𝑐2 ⇒ 2 ≤ 𝑐2
9
∴ 2 ≤ 𝑐2 and there is no lower bound of 𝑐2

[N.B. there are two cases may arise

(i) 𝒄𝒋 is the cost component corresponding to a non-basic variable i.e 𝒄𝒋 ∉ 𝒄𝑩 .
(ii) 𝒄𝒋 is the cost component corresponding to a optimal basic variable i.e 𝒄𝒋 ∈ 𝒄𝑩 .
Components Case I: There is no lower bound of ∆𝒄𝒋 and any change of 𝒄𝒋 does not change the
value of the objective function.
𝑴𝒂𝒙 −(𝒛𝒋 −𝒄𝒋 ) 𝑴𝒊𝒏 −(𝒛𝒋−𝒄𝒋)
Case II: ( 𝒚 ; 𝒚𝒓𝒋 > 𝟎) ≤ ∆𝒄𝒌 ≤ ( 𝒚 ; 𝒚𝒓𝒋 < 𝟎).
𝒋 𝒓𝒋 𝒋 𝒓𝒋

If no 𝒚𝒓𝒋 ≥ 𝟎, there is no lower bound of ∆𝒄𝒌 and if no 𝒚𝒓𝒋 < 𝟎 there is no upper bound of
∆𝒄𝒌 . ]
Problem: Given the following L.P.P.
Maximize 𝒁 = 𝒙𝟏 + 𝟒𝒙𝟐 − 𝟐𝒙𝟑 + 𝟑𝒙𝟒 − 𝒙𝟓
𝑺/𝒕 ∶ 𝒙𝟏 − 𝟑𝒙𝟐 + 𝒙𝟑 + 𝟐𝒙𝟒 + 𝟔𝒙𝟓 ≤ 𝟑
𝟐𝒙𝟏 + 𝒙𝟐 + 𝟑𝒙𝟒 + 𝟐𝒙𝟓 ≤ 𝟔
𝟒𝒙𝟏 + 𝒙𝟐 − 𝒙𝟒 + 𝒙𝟓 ≤ 𝟐
𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 , 𝒙𝟒 , 𝒙𝟓 ≥ 𝟎
Find the ranges over which 𝒄𝟏 , 𝒄𝟐 , 𝒄𝟑 , 𝒄𝟒 and 𝒄𝟓 can be changed so that the optimality of the
current solution remains undisturbed.
Solution: Introducing slack variables𝑥6 ≥ 0, 𝑥7 ≥ 0 𝑎𝑛𝑑 𝑥8 ≥ 0 one to each constraint, we get
Maximize 𝑧 = 𝑥1 + 4𝑥2 − 2𝑥3 + 3𝑥4 − 𝑥5 + 0. 𝑥6 + 0. 𝑥7 + 0𝑥8
S/t : 𝑥1 − 3𝑥2 + 𝑥3 + 2𝑥4 + 6𝑥5 + 𝑥6 + 0. 𝑥7 + 0. 𝑥8 = 3
2𝑥1 + 𝑥2 + 0. 𝑥3 + 3𝑥4 + 2𝑥5 + 0𝑥6 + 𝑥7 + 0. 𝑥8 = 6
4𝑥1 + 𝑥2 + 0. 𝑥3 − 𝑥4 + 𝑥5 + 0. 𝑥6 + 0. 𝑥7 + 𝑥8 = 2
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 , 𝑥6 , 𝑥7 , 𝑥8 ≥ 0
𝑐𝑗 1 4 -2 3 -1 0 0 0 Const. Min

Md. Syful Islam, Assistant Professor, Dept. of Statistics, Chittagong College (01718558010) 8
 𝑐𝐵 Basis 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝑥6 𝑥7 𝑥8 b ratio
0 x5 1 -3 1 2 6 1 0 0 3
0 x6 2 1 0 3 2 0 1 0 6 6
0 x7 4 (1) 0 -1 0 0 1 2 2∗
1

𝑧𝑗 − 𝑐𝑗 -1 −4 ↑ 2 -3 1 0 0 0 Z=0
0 x5 13 0 1 -1 9 1 0 3 9
7 x4 -2 0 0 (4) 1 0 1 -1 4 1∗
0 x7 4 1 0 -1 0 0 1 2
1

𝑧𝑗 − 𝑐𝑗 15 0 2 −7 5 0 0 4 Z= 8
↑
3 x1 25/2 0 1 0 37/4 1 1/4 11/4 10
7 x4 -1/2 0 0 1 1/4 0 1/4 -1/4 1
0 x7 7/2 1 0 0 0 1 3/4 3
3/2

𝑧𝑗 − 𝑐𝑗 23/2 1 2 0 27/4 0 9/4 7/4 Z=15

Since all 𝑧𝑗 − 𝑐𝑗 ≥ 0, the optimality conditions are satisfied and optimum solution are
𝑥1 = 0, 𝑥2 = 3, 𝑥3 = 0 , 𝑥4 = 1, 𝑥5 = 0 and Max 𝑧 = 15
Variation of 𝑐𝑗 , 𝑗 = 1, 2, 3, 4, 5.
Here 𝑐1 , 𝑐3 and 𝑐5 are not basic cost i.e. 𝑐1, 𝑐3, 𝑐5 ∉ 𝑐𝐵 ,
1
∆𝑐1 ≤ 𝑧1 − 𝑐1 ⇒ ∆𝑐1 ≤ 3

∆𝑐3 ≤ 𝑧3 − 𝑐3 ⇒ ∆𝑐3 ≤ 2
27
∆𝑐5 ≤ 𝑧5 − 𝑐5 ⇒ ∆𝑐5 ≤ 4
23 25
∴ Variation of 𝑐1is 𝑐1 ≤ 1 + ⇒ 𝑐1 ≤
2 2

∴ Variation of 𝑐3 is 𝑐3 ≤ −2 + 2 ⇒ 𝑐3 ≤ 0
27 23
∴ Variation of 𝑐5 is 𝑐5 ≤ −1 + ⇒ 𝑐5 ≤
4 4

𝑐1 , 𝑐2 and 𝑐5 have no lower bound.

𝑐2 and 𝑐4 are basic cost i.e.𝑐2, 𝑐4 ∈ 𝑐𝐵 .
Here 𝑐2 = 𝑐𝐵3
The range of change ∆𝑐2 in 𝑐2 is given by
𝑀𝑎𝑥 −(𝑧𝑗−𝑐𝑗) 𝑀𝑖𝑛 −(𝑧𝑗−𝑐𝑗)
∴ ( 𝑦 ; 𝑦3𝑗 > 0) ≤ ∆𝑐2 ≤ ( 𝑦 ; 𝑦3𝑗 < 0)
𝑗 3𝑗 𝑗 3𝑗

𝑀𝑎𝑥 −23/2 −27/4 −7/4 −9/4

⇒ ( 7/2 , 3/2 , 1 , 3/4 ) ≤ ∆𝑐2 | 𝑁𝑜 𝑦3𝑗 < 0
𝑗

Md. Syful Islam, Assistant Professor, Dept. of Statistics, Chittagong College (01718558010) 9
 7
⇒ − 4 ≤ ∆𝑐2 . There is no upper bound of ∆𝑐2.
7 9
∴ Variation of 𝑐2 is 4 − 4 ≤ 𝑐2 ⇒ 4 ≤ 𝑐2
9
∴ 4 ≤ 𝑐2 and there is no upper bound of 𝑐2 .

Here 𝑐4 = 𝑐𝐵2
The range of change ∆𝑐4 in 𝑐4 is given by
𝑀𝑎𝑥 −(𝑧𝑗−𝑐𝑗) 𝑀𝑖𝑛 −(𝑧𝑗−𝑐𝑗)
∴ ( 𝑦 ; 𝑦2𝑗 > 0) ≤ ∆𝑐4 ≤ ( 𝑦 ; 𝑦2𝑗 < 0)
𝑗 2𝑗 𝑗 2𝑗

𝑀𝑎𝑥 −27/4 −7/4 𝑀𝑖𝑛 −23/2 −23/2 −9/4

⇒ ( , ) ≤ ∆𝑐4 ≤ ( , , )
𝑗 1/4 1/4 𝑗 −1/2 −1/2 −1/4

⇒ −7 ≤ ∆𝑐4 ≤ 9.
∴ Variation of 𝑐4 is 3 − 7 ≤ 𝑐4 ≤ 3 + 9 ⇒ −4 ≤ 𝑐4 ≤ 12.
Question: Describe the structural change in a L.P.P. due to addition of non-negative new
variable.
Answer: Let us consider the L.P.P.
Maximize 𝑧 = 𝑐𝑥
Subject to 𝐴𝑥 = 𝑏 , 𝑋 ≥ 𝑜 , 𝑏 ≥ 𝑜
Let a non-negative new variable 𝑥𝑛+1 with a cost 𝑐𝑛+1 be added in this L.P.P. This will add an
extra column 𝑎𝑛+1 to the coefficient matrix 𝐴. To observed the effect of this addition on the current
optimum solution, we compute the net evaluation
𝑧𝑛+1 − 𝑐𝑛+1 = 𝑐𝐵 𝑦𝑛+1 − 𝑐𝑛+1 Where 𝑦𝑛+1 = 𝐵 −1 𝑎𝑛+1

(i) If 𝑧𝑛+1 − 𝑐𝑛+1 ≥ 0, then the current solution remains optimum.

(ii) If 𝑧𝑛+1 − 𝑐𝑛+1 < 0, then the current optimum solution can be improved by introducing
𝑎𝑛+1 in to the basis.
Apply simplex method to find the new optimum solution taking the optimum table of the original
problem as a starting table.
Addition of any non-negative variable can no disturbed the feasibility of the current solution.
If 𝑥𝐵 is the optimum basic feasible solution with the optimum basis B then 𝑥𝐵 = 𝐵 −1 𝑏
Now let the cost vector 𝐶 be replaced by a new cost vector 𝐶 ∗ then the problem
Maximize 𝑍 ∗ = 𝑐 ∗ 𝑥
Subject to 𝐴𝑥 = 𝑏 , 𝑥 ≥ 𝑜 , 𝑏 ≥ 𝑜
We observe that the constraint set is not affected at all by such a change in 𝑐 and thus the current
basic solution 𝑥𝐵 remains at least feasible.
Let ∆𝑐𝑗 be the amount which is added to the jth component 𝑐𝑗 of 𝑐 = [𝑐1 , 𝑐2 , … … . 𝑐𝑛 ] so that the
new value of the jth cost component becomes 𝑐𝑗∗ = 𝑐𝑗 + ∆𝑐𝑗

Md. Syful Islam, Assistant Professor, Dept. of Statistics, Chittagong College (01718558010) 10
Problem: Solve the following L.P.P.
𝑴𝒂𝒙𝒊𝒎𝒊𝒛𝒆 𝒛 = 𝟑𝒙𝟏 + 𝟓𝒙𝟐
Subject to: 𝒙𝟏 + 𝒙𝟐 ≤ 𝟏
𝟐𝒙𝟏 + 𝟑𝒙𝟐 ≤ 𝟏
𝒙𝟏 , 𝒙𝟐 ≥ 𝟎.
and discuss the effect of adding a new non-negative variable 𝒙𝟓 as follows:
𝑴𝒂𝒙𝒊𝒎𝒊𝒛𝒆 z=𝟑𝒙𝟏 + 𝟓𝒙𝟐 + 𝟐𝒙𝟓
Subject to: 𝒙𝟏 + 𝒙𝟐 + 𝒙𝟓 ≤ 𝟏
𝟐𝒙𝟏 + 𝟑𝒙𝟐 − 𝒙𝟓 ≤ 𝟏
𝒙𝟏 , 𝒙𝟐 , 𝒙𝟓 ≥ 𝟎.
Solution: Introducing slack variables 𝑥3 ≥ 0, 𝑎𝑛𝑑 𝑥4 ≥ 0 one to each constraint, we get
Maximize 𝑧 = 3𝑥1 + 5𝑥2 + 0. 𝑥3 + 0. 𝑥4
S/t : 𝑥1 + 𝑥2 + 𝑥3 + 0. 𝑥4 = 1
2𝑥1 + 3𝑥2 + 0. 𝑥3 + 𝑥4 = 1
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0
𝑐𝑗 3 5 0 0 Const. Min
𝑐𝐵 Basis 𝑥1 𝑥2 𝑥3 𝑥4 b ratio

0 𝑥3 1 1 1 0 1 1
0 𝑥4 2 (3) 0 1 1 1/3*

𝑧𝑗 − 𝑐𝑗 −3 −5 ↑ 0 0 Z=0
0 𝑥3 1/3 0 1 −1/3 2/3
2 𝑥2 2/3 1/3 0 1/6 1/3

𝑧𝑗 − 𝑐𝑗 1/3 0 0 5/3 Z= 5/3

Since all 𝑧𝑗 − 𝑐𝑗 ≥ 0. Thus the optimality conditions are satisfied. The optimum solution 𝑥1 = 0,
1 5
𝑥2 = 3 and Max 𝑧 = 3.

After addition a new variable 𝑥5 we have

1
𝑎5 = ( ) and 𝑐5 = 2
−1
From final table of original problem, we get
1 −1/3
𝐵 −1 = ( ) and 𝑐𝐵 = (0 5)
0 1/3
1 −1/3 1 4/3
∴ 𝑦5 = 𝐵 −1 𝑎5 = ( )( ) = ( )
0 1/3 −1 −1/3

Md. Syful Islam, Assistant Professor, Dept. of Statistics, Chittagong College (01718558010) 11
 4
3 5 11
∴ 𝑧5 − 𝑐5 = 𝑐𝐵 𝑦5 − 𝑐5 = (0 5) ( 1) − 2 = −3 −2 = − < 0.
3
−3

Since 𝑧5 − 𝑐5 < 0 the current solution is not optimal for the new L.P.P. we shall enter 𝑎5 in to the
basis by usual simplex method.
𝑐𝑗 3 5 0 0 2 Const. Min
𝑐𝐵 Basis 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 b ratio

0 𝑥3 1/3 0 1 -1/3 (4/3) 2/3 1/2∗

5 𝑥2 2/3 1 0 1/3 -1/3 1/3

𝑧𝑗 − 𝑐𝑗 1/3 0 0 5/3 −1/3 ↑ Z= 5/3

2 𝑥5 1/4 0 3/4 −1/4 1 1/2
5 𝑥2 5/9 1 1/4 1/4 0 5/9

𝑧𝑗 − 𝑐𝑗 5/18 0 11/4 3/4 0 Z= 34/9

Since all 𝑧𝑗 − 𝑐𝑗 ≥ 0. Thus the optimality conditions are satisfied. The new optimum solution is
5 1 34
𝑥1 = 0, 𝑥2 = 9 , 𝑥5 = 2 and Max 𝑧 = .
9

Problem: Solve the following L.P.P.

𝑴𝒂𝒙𝒊𝒎𝒊𝒛𝒆 𝒛 = 𝟑𝒙𝟏 + 𝟓𝒙𝟐
Subject to: 𝒙𝟏 ≤ 𝟒
𝟑𝒙𝟏 + 𝟑𝟐 ≤ 𝟏𝟖
𝒙𝟏 , 𝒙𝟐 ≥ 𝟎.
If a new variable 𝒙𝟓 is introduced after the optimum solution is obtained with 𝒄𝟓 = 𝟕 and
𝟏
𝒂𝟓 = ( ) i.e the new L.P.P. is
𝟐
𝑴𝒂𝒙𝒊𝒎𝒊𝒛𝒆 z=𝟑𝒙𝟏 + 𝟓𝒙𝟐 + 𝟕𝒙𝟓
Subject to: 𝒙𝟏 + 𝒙𝟓 ≤ 𝟒
𝟑𝒙𝟏 + 𝟐𝒙𝟐 + 𝟐𝒙𝟓 ≤ 𝟏𝟖
𝒙𝟏 , 𝒙𝟐 , 𝒙𝟓 ≥ 𝟎.
Discuss the effect of adding a new variable and obtain the revised solution if any.
Solution: Introducing slack variables 𝑥3 ≥ 0, 𝑎𝑛𝑑 𝑥4 ≥ 0 one to each constraint, we get
Maximize 𝑧 = 3𝑥1 + 5𝑥2 + 0. 𝑥3 + 0. 𝑥4
S/t : 𝑥1 + 0. 𝑥2 + 𝑥3 + 0. 𝑥4 = 4
3𝑥1 + 2𝑥2 + 0. 𝑥3 + 𝑥4 = 16
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0

Md. Syful Islam, Assistant Professor, Dept. of Statistics, Chittagong College (01718558010) 12
 𝑐𝑗 3 5 0 0 Const. Min
𝑐𝐵 Basis 𝑥1 𝑥2 𝑥3 𝑥4 b ratio
0 𝑥3 1 0 1 0 4
0 𝑥4 3 (2) 0 1 18 9*

𝑧𝑗 − 𝑐𝑗 −3 −5 ↑ 0 0 Z=0
0 𝑥3 1 0 1 0 4
5 𝑥2 3/2 0 0 1/2 9

𝑧𝑗 − 𝑐𝑗 9/2 0 0 5/2 Z= 45
Since all 𝑧𝑗 − 𝑐𝑗 ≥ 0. Thus the optimality conditions are satisfied. The optimum solution 𝑥1 = 0,
𝑥2 = 9 and Max 𝑧 = 45.
Discussion of adding a new variable:
4
Here 𝐶𝐵 = (0 5), 𝑥𝐵 = ( ) and
9
1 0 1
𝐵 −1 = ( ) and given that 𝑐5 = 7 And 𝑎5 = ( ) 2
0 1/2 2
1 0 1 1
∴ 𝑦4 = 𝐵 −1 𝑎5 = ( )( ) = ( )
0 1/2 2 1
1
∴ 𝑧5 − 𝑐5 = 𝑐𝐵 𝑦5 − 𝑐5 = (0 5) ( ) − 7 = 5 − 7 = −2 < 0.
1
Since 𝑧5 − 𝑐5 < 0 the current solution is not optimal for the new L.P.P. We shall enter 𝑎5 in to the
basis by apply usual simplex method.
𝑐𝑗 3 5 0 0 7 Const. Min
𝑐𝐵 Basis 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 b ratio
0 𝑥3 1 0 1 0 (1) 4 1
5 𝑥2 3/2 1 0 1/2 1 9 1/3*

𝑧𝑗 − 𝑐𝑗 9/2 0 0 5/2 −2 ↑ Z= 45
7 𝑥5 1 0 1 0 1 4
5 𝑥2 1/2 1 -1 1/2 0 5

𝑧𝑗 − 𝑐𝑗 13/2 0 2 5/2 0 Z= 53

Md. Syful Islam, Assistant Professor, Dept. of Statistics, Chittagong College (01718558010) 13
Since all 𝑧𝑗 − 𝑐𝑗 ≥ 0. Thus the optimality conditions are satisfied. The new optimum solution is
𝑥1 = 0, 𝑥2 = 5, 𝑥5 = 4 and Max 𝑧 = 53.

Md. Syful Islam, Assistant Professor, Dept. of Statistics, Chittagong College (01718558010) 14