INOPER1

– study of the effects of the changes in parameter

values on the present basic optimal solution
Parameters: OFC C
Constraint Coefficients A
RHS b

Present Basic Optimal Solution XB

-refers to the basic variables themselves, not the
values of the BV’s that make up the optimal
solution.
 the marginal worth of resource i
 the change in profit (Z) per unit change in a
resource
 A company manufactures three products A,
B, and C. Each product must be machine-
processed in three departments, as shown
below.
Machine Time Required (hr) Per unit Profit
Product Dept. 1 Dept. 2 Dept. 3 Contribution
A 1 1 2 Php 30
B 2 1 1 Php 25
C 1 2 1 Php 35
 Formulated LP model is as follows:
Let x1 = units of product A
x2 = units of product B
x3 = units of product C
S1 = Dept. 1 Slack, in hours
S2 = Dept. 2 Slack, in hours
S3 = Dept. 3 slack, in hours
Z = profit
c N  25 0 0

c N  25 0 0

Max Z  30 x1  25 x2  35 x3
s.t. x1  2 x2  x3  S1  800
x1  x2  2 x3  S2  1000
2 x1  x2  x3  S3  2000
x1 , x2 , x3 , S1 , S 2 , S3  0
The optimal solution is given as follows:
 x1   x2 
   
x B   x3  x N   S1 
S  S 
 3  2

c B  30 35 0 c N  25 0 0 
  2  1 0  800   600 
    
x B  B 1b    1 1 0  1000    200 
  3 1 1  2000   600 
    

c B B 1 N  c N  30 25 5

 3 2  1
 
B 1 N    1  1 1 
 4  3 1 
 

Prepare a sensitivity analysis for this problem.

1. Consider Department 1
 
SPDep’t 1 = Z Present b1 value = 800
b1 Assume b1 = 1
 
present = CBXB = ( 30 35 0 ) 600 = P25,000
200
600
 
If b1 is changed or increased from 800 to 801, XB is affected
New XB = B-1  b
 

New XB = 2 -1 0 801 602

-1 1 0 1000 = 199
-3 1 3 2000 597
 
 new = ( CB ) ( new XB ) = ( 30 35 0 ) 600 = P25,025
199
597
 
Conclusion: If b1 is increased by 1 unit, the profit (Z) increases by P25.
Therefore SPDep’t 1 = 25,025 – 25,000 = 25/hr
1
1. The shadow price for resources whose
associated slack variables are non-basic at
optimum is equal to the corresponding
element in the optimum CBB-1N – CN

2. The shadow price for resources whose

associated slack variables are basic at
optimum is equal to zero.
 Resource i Associated Slack Category Shadow Price
Variable

Dept 1 1 S1 Non-basic P25/hr

Source Dept 2 2 S2 Non-basic 5/hr

resource
Dept 3 3 S3 Basic 0

Abundant CBB-1N – CN = ( 30 25 5 )
resource X 2 S1 S2
 The concept of shadow price becomes the
basis of making decisions as to whether
resources should be added or not.
Consider Dep’t 3: S3 = 600 , b3 = 2,000

This means that only 1,400 hrs were

utilized in Dep’t 3 or there is a slack time of
600 hrs in Dep’t 3. Since there are still “hours”
that are unutilized, increasing the available
hrs of Dep’t 3 by 1 hr would not have any
worth to the company. This explains why the
shadow price is equal to zero.
1. Suppose that the firm can add more hours to
Dep’t 1 by renting a machine at an additional
cost of P20/hr, what should the firm do?

Net benefit = Profit - Cost = P25 – P20 = P5/hr

 Rent the machine.
2. Suppose that an additional 1,200 hrs of
machine time can be added to Dep’t 1, what
should be done?
Check first if optimal sol’n has
changed:
800 + 1,200
XB = 2 -1 0 2,000 3,000
-1 1 0 1,000 = -1,000
-3 1 1 2,000 -3,000
 Since XB became infeasible with the addition
of 1,200 hrs in Dep’t 1, we conclude that the
present basic optimal sol’n has changed. The
SP of P25/hr for Dep’t 1 is therefore no longer
valid.
Compute Z by getting Zold and Znew.

To get Znew. Find the new optimal sol’n (XB) first

and then multiply by CB

C = ( 20/hr ) ( 1,200 hrs ) = P24,000

If Z > C, rent the machine. Otherwise, do
not rent the machine.
– range of values of bI for
which the present basic
optimal solution remains
unchanged; hence, the
shadow price remains valid.
XB  0 null vector
B-1b  0
 
2 -1 0 800 + b1 0
-1 1 0 1,000  0
-3 1 1 2,000 0
 

= 2 -1 0 800 b1 0
-1 1 0 1,000 + 0  0
-3 1 1 2,000 0 0
  = 600 2b1 0
200 + -b1  0
600 -3b1 0
 
2b1 -600
-b1  -200
-3b1 -600
 

2b1  -600 -b1  -200 -3b1  -600

b1  -300 b1  200 b1  200

 -300  b1  200

800 –300  b1  800 + 200 Range of b1for which present basic
RHS Ranging for Dep’t 1: 500  b1  1,000 optimal sol’n will not change
 1.) Let e1 present optimal sol’n = XB
e2


em
 

Ci1
Ci2 = ith column of B-1


Cim where I = ith resource
3. Compute for the extreme values of b1
-e1 ; -e2 ;  -em
Ci1 Ci2 Cim

4. Let x – least negative ratio

y – least positive ratio
 
RHS Range for bi = bio + x  bi  bio + y
 
5. If all ratios are negative – no upper limit
If all ratios are positive – no lower limit
 
Note: Treat all divisions by zero as + before determining y
 800  b2  1,600

e C Ratio
600 2 -300 =x
200 -1 200
=y
600 -3 200

e C Ratio
600 -1 600 =y
200 1 -200 =x
600 1 -600

800  b2  1,600
1. If the firm can lease its available time for
Dep’t 2 to another company for P8/hr., for
200 hours, what should the company do?

2. Answer the same question if 500 hrs. will be

leased.
 – process of determining a range for the
objective function coefficients for which the
present basic optimal solution remains the
same.

Criterion for maximization problems: CBB-1N – CN  0

Criterion for minimization problems: CBB-1N – CN  0
Consider x1: CBB-1N – CN  0
 

+3 2 -1
( 30+C1 35 0 ) -1 -1 1 - ( 25 0 0 )  ( 0 0 0 )
-4 -3 1
 

[( 30 35 0 ) + ( C1 0 0 )] 3 2 -1
-1 -1 1 - ( 25 0 0 )  ( 0 0 0 )
-4 -3 1
( 30 25 5 ) + ( 3C1 2C1 -C1 )  ( 0 0 0 )
( 3C1 2C1 -C1 )  ( -30 -25 -5 )

3C1  -30 2C1  -25 -C1  -5

C1  -10 C1  -12.5 C1  5
 
-10  C1  5
30 – 10  C1  30 + 5
 

20  C1  35 OFC Ranging for C1

1. Let ( g1, g2,  gn ) = optimal CBB-1N - CN
( hk1, hk2,  hkn ) = kth row of optimal B-1N
where k = denoted by the position of Xj in XB
 
2. Determine the extreme values of Cj­
-g1 , -g2 ,  -gn
hk1 hk2 hkn
 
3. Let u = least negative ratio
V = least positive ratio
 
OFC Range for Cj : cjo + u  Cj  cjo + v
4.  If all ratios are negative – no upper limit
If all ratios are positive – no lower limit
 
5. If there is a 0 ratio:
If the divisor hk is negative for maximization
(minimization) then v=0 (u=0). If the
divisor is positive for maximization
(minimization), then u=0 (v=0).
Consider X2: CBB-1N – CN  0
 
( 30 35 0 ) 3 2 -1
-1 -1 1 - ( 25+C2 0 0 )  ( 0 0 0 )
-4 -3 1
 
( 55 25 5 ) – ( 25+C2 0 0 )  ( 0 0 0 )
-( 25+C2 0 0 )  ( -55 -25 -5 )
-25 - C2  -55
25 + C2  55
C2  30
-  C2  25 + 30

-  C2  55
For Max.: -   Cj  Cjo + gi
where: Cjo = original value of Cj

For Min.: Cjo + gi  Cj  

gi = corresponding element in the
Optimal CBB-1N - CN
i = denoted by the position of xj in xN
1. Reuse CB or CN correspondingly to reflect the
new value of Cj
2. Determine CBB-1N - CN
3. Determine entering and leaving variables.
4. Proceed with the necessary iterations until the
solution is optimal
 Note: In the above procedure, there is no need
to solve the entire system or problem again.
The optimal solution becomes the starting
point of the succeeding iterations.
 X2 S 1 S2

X2 S 1 S2

CBB-1N – CN = ( 30 25 5 )
C1: OFC of a basic variable X1 B-1Nk = ( 3 2 -1 )

g h Ratio
1st row of
B-1N since 30 3 -30/3 = - 10 = u
X1 is in the
1st row of XB

25 2 -25/2 = -12.5

5 -1 -5/-1 = 5 = v

Range: 30 – 10  C1  30 + 5

20  C1  35
C2: OFC of a NBV X2
Since problem is maximization: Range: -  C2  25 + 30
-  C2  55

C3: OFC of a basic variable X3

g h Ratio
30 -1 -30/-1 = 30
25 -1 -25/-1 = 25 = v
5 1 -5/1 = -5 = u

2nd row of B-1N since X3 is in

the 2nd row of X`B
Suppose C1 is changed to 40
CBB-1N – CN = ( 40 35 0 ) 3 2 -1
-1 -1 1 - ( 25 0 0 )
-4 -3 1
= ( 85 45 -5 ) – ( 25 0 0 )
= ( 60 45 -5 )

EV = S2
Ratio: 600 , 200 , 600 = { - , 200 , 600 }
-1 1 1 LV = X3
Proceed until solution is optimal
1. Assume that the new variable is non basic.
2. Add the new coefficient into CN , N & XN
3. Solve for CBB-1N - CN
4. If CBB-1N – CN  0 for max. problems (CBB-1N
– CN  0 for min problems), then the new
product or activity added to the model is not
profitable. Otherwise, proceed with a few
more iterations until the solution is optimal.
Product D
Profit/unit = Php40
Machine Time/unit: (D1) 2, (D2) 1, (D3) 1
Should Product D be produced?
 Solution:
 Let x4 = no. of units to product D to produce
 x2 
 
 S1 
xN 
S2 
 
x 
 4
  2  1 0  2 1 0 2
  
c B B N  c N  30 35 0   1 1 0  1 0
1
1 1   25 0 0 40
  3 1 1  1 0 0 1 
 
 3 2 1 3 
 
 30 35 0   1  1 1  1   25 0 0 40
  4  3 1  4
 
 55 25 5 55  25 0 0 40
 30 25 5 15

 Therefore, Product D should not be

produced! Product D is attractive to produce
if its profit/unit is more than 55.
 Occurswhen a constraint was overlooked or
new considerations have arisen.

 Also occurs when a previous constraint was

deleted to decrease computational effort and
it will now be checked with the optimal
solution actually obtained.
1. Check directly whether the optimal solution satisfies
constraint.
2. If it satisfies the constraint, then the current optimal
solution would still be the best feasible solution. If
the new constraint does eliminate the current
optimal solution, then find a new solution.
3. In finding the new solution, the new constraint will
be added to the final tableau. The new slack or
artificial variable will be introduced as basic variable.
4. Convert the coefficients of the basic variables in the
added constraint to zero using gauss jordan
elimination. Perform Dual Simplex until a new
optimal solution is achieved.
a) Fourth constraint: 2x1+2x2+x3<1500 is
added to the problem. Find the optimal
solution.

b) Fourth constraint: 2x1+x2<1000 is added to

the problem. Find the optimal solution.
A. Constraint is added to the problem
Substitute the values of decision variables to
the constraint:
x1 = 600, x2 = 0, x3 = 200
2(600) + 2(0) + 200 = 1400

The fourth constraint is not violated given the current

optimal solution. Therefore, optimal solution will not
changed.
B. Constraint is added to the problem
Substitute the values of decision
variables to the constraint:
x1 = 600, x2 = 0, x3 = 200
2(600) + 1(0) = 1200

The fourth constraint is violated given the

current optimal solution. A new solution should be
found!
Basic X1 X2 X3 S1 S2 S3 S4 Soln.

Z 0 30 0 25 5 0 0 25000

X1 1 3 0 2 -1 0 0 600

X3 0 -1 1 -1 1 0 0 200

S3 0 -4 0 -3 1 1 0 600

S4 2 1 0 0 0 0 1 1000

 Convert the coefficient of x1 of the added constraint to

zero using Gauss-Jordan Elimination.
 Basic X1 X2 X3 S1 S2 S3 S4 Soln.

Z 0 30 0 25 5 0 0 25000

X1 1 3 0 2 -1 0 0 600

X3 0 -1 1 -1 1 0 0 200

S3 0 -4 0 -3 1 1 0 600

S4 0 -5 0 -4 2 0 1 -200

 Perform dual simplex since the current solution is

super-optimal!
LV = S4 and EV = X2
  Th
e solutio
 As n is optim
signmen al! 
t: Proble
m Set #
’ s 1 a nd2

Basic X1 X2 X3 S1 S2 S3 S4 Soln.

Z 0 0 0 1 17 0 6 23800

X1 1 0 0 -2/5 1/5 0 3/5 480

X3 0 0 1 -1/5 3/5 0 -1/5 240

S3 0 0 0 1/5 -3/5 1 -4/5 760

X2 0 1 0 4/5 -2/5 0 -1/5 40