Sensitivity Analysis and Duality in Linear Programming

Chapter 5

Simplex-Based Sensitivity Analysis and Duality

n

Sensitivity Analysis with the Simplex Tableau

n

Duality

Objective Function Coefficients

and Range of Optimality

n

The 

range of optimality

 for an objective function

coefficient is the range of that coefficient for which

the current optimal solution will remain optimal

(keeping all other coefficients constant).

n

The objective function value might change in this

range.

n

Given an optimal tableau, the range of optimality for

c

k

 can be calculated as follows:

•

Change the objective function coefficient to 

c

k

 in

the 

c

j 

row.

•

If 

x

k

 is basic, then also change the objective

function coefficient to 

c

k

 in the 

c

B

 column and

recalculate the 

z

j

 row in terms of 

c

k

.

•

Recalculate the 

c

j

 - 

z

j

 row in terms of 

c

k

.  Determine

the range of values for 

c

k

 that keep all entries in

the 

c

j

 - 

z

j

 row less than or equal to 0.

Objective Function Coefficients

and Range of Optimality

n

If 

c

k

 changes to values outside the range of optimality,

a new 

c

j

 - 

z

j

 row may be generated.  The simplex

method may then be continued to determine a new

optimal solution.

Objective Function Coefficients

and Range of Optimality

Shadow Price

n

A 

shadow price

 for a constraint is the increase in the

objective function value resulting from a one unit

increase in its right-hand side value.

n

Shadow prices and 

dual prices

 on 

The Management

Scientist 

output are the same thing for maximization

problems and negative of each other for

minimization problems.

Shadow Price

n

Shadow prices are found in the optimal tableau as

follows:

•

"less than or equal to" constraint  -- 

z

j

 value of the

corresponding slack variable for the constraint

•

"greater than or equal to" constraint -- negative of

the 

z

j

 value of the corresponding surplus variable

for the constraint

•

"equal to" constraint -- 

z

j

 value of the

corresponding artificial variable for the constraint.

Right-Hand Side Values

and Range of Feasibility

n

The 

range of feasibility

 for a right hand side

coefficient is the range of that coefficient for which

the shadow price remains unchanged.

n

The 

range of feasibility

 is also the range for which the

current set of basic variables remains the optimal set

of basic variables (although their values change.)

Right-Hand Side Values

and Range of Feasibility

n

The range of feasibility for a right-hand side

coefficient of a "less than or equal to" constraint, 

b

k

, is

calculated as follows:

•

Express the right-hand side in terms of 



b

k

 by

adding 



b

k

 times the column of the 

k

-th slack

variable to the current optimal right hand side.

•

Determine the range of 



b

k

 that keeps the right-

hand side greater than or equal to 0.

•

Add the original right-hand side value 

b

k

 (from

the original tableau) to these limits for  



b

k

 to

determine the range of feasibility for 

b

k

.

Right-Hand Side Values

and Range of Feasibility

n

The range of feasibility for "greater than or equal to"

constraints is similarly found except one subtracts 



b

k

times the current column of the 

k

-th surplus variable

from the current right hand side.

n

For equality constraints this range is similarly found by

adding  



b

k

 times the current column of the 

k

-th

artificial variable to the current right hand side.

Otherwise the procedure is the same.

Simultaneous Changes

n

For simultaneous changes of two or more objective

function coefficients the 100% rule  provides a

guide to whether the optimal solution changes.

n

It states that as long as the sum of the percent

changes in the coefficients from their current value

to their maximum allowable increase or decrease

does not exceed 100%, the solution will not change.

n

Similarly, for shadow prices, the 100% rule can be

applied to changes in the the right hand side

coefficients.

Canonical Form

n

A maximization linear program is said to be in

canonical form

 if all constraints are "less than or

equal to" constraints and the variables are non-

negative.

n

A minimization linear program is said to be in

canonical form

 if all constraints are "greater than or

equal to" constraints and the variables are non-

negative.

Canonical Form

n

Convert any linear program to a maximization problem

in canonical form as follows:

•

minimization objective function:

   multiply it by -1

•

"less than or equal to" constraint:

   leave it alone

•

"greater than or equal to" constraint:

   multiply it by -1

•

"equal to" constraint:

   form two constraints, one "less than or equal to",

   the other "greater or equal to"; then multiply this

   "greater than or equal to" constraint by -1.

Primal and Dual Problems

n

Every linear program (called the 

primal

) has

associated with it another linear program called the

dual

.

n

The dual of a maximization problem in canonical

form is a minimization problem in canonical form.

n

The rows and columns of the two programs are

interchanged and hence the objective function

coefficients of one are the right hand side values of

the other and vice versa.

Primal and Dual Problems

n

The optimal value of the objective function of the

primal problem equals the optimal value of the

objective function of the dual problem.

n

Solving the dual might be computationally more

efficient when the primal has numerous constraints

and few variables.

Primal and Dual Variables

n

The dual variables are the "value per unit" of the

corresponding primal resource, i.e. the shadow prices.

Thus, they are found in the 

z

j

 row of the optimal

simplex tableau.

n

If the dual is solved, the optimal primal solution is

found in 

z

j

 row of the corresponding surplus variable

in the optimal dual tableau.

n

The optimal value of the primal's slack variables are

the negative of the 

c

j

 - 

z

j

 entries in the optimal dual

tableau for the dual variables.

Example:  Jonni’s Toy Co.

Jonni's Toy Co. produces stuffed toy animals and

is gearing up for the Christmas rush by

hiring temporary workers giving it a total

production crew of 30 workers.  Jonni's

makes two sizes of stuffed animals.

The profit, the production time and

the material used per toy animal is

summarized on the next slide.  Workers

work 8 hours per day and there are up to 2000 pounds

of material available daily.

What is the optimal daily production mix?

Example:  Jonni’s Toy Co.

  Toy       Unit       Production      Material Used

Size

Profit

Time (hrs.)

Per Unit (lbs.)

 Small       $3             

   .10                         1

 Large       $8                 .30                         2

Example:  Jonni’s Toy Co.

n

LP Formulation

LP Formulation

  x

  x

1

1

 = number of small stuffed animals produced daily

 = number of small stuffed animals produced daily

x

x

2

2

 = number of large stuffed animals produced daily

 = number of large stuffed animals produced daily

     Max     3

     Max     3

x

x

1

1

 +  8

 +  8

x

x

2

2

     s.t.       .1

     s.t.       .1

x

x

1

1

 + .3

 + .3

x

x

2

2

<

<

    240

    240

x

x

1

1

 +  2

 +  2

x

x

2

2

<

<

   2000

   2000

x

x

1

1

, 

, 

x

x

2

2

>

>

   0

   0

Example:  Jonni’s Toy Co.

n

Simplex Method:  First Tableau

Simplex Method:  First Tableau

x

x

1

1

x

x

2

2

s

s

1

1

s

s

2

2

       Basis  

       Basis  

c

c

B

B

       3        8       0       0

       3        8       0       0

s

s

1

1

    0       .1       .3       1       0        240

    0       .1       .3       1       0        240

s

s

2

2

     0        1        2       0       1      2000

     0        1        2       0       1      2000

z

z

j

j

           0        0       0       0         0

           0        0       0       0         0

c

c

j

j

 - 

 - 

z

z

j

j

        3        8       0       0

        3        8       0       0

Example:  Jonni’s Toy Co.

n

Simplex Method:  Second Tableau

Simplex Method:  Second Tableau

x

x

1

1

x

x

2

2

s

s

1

1

s

s

2

2

       Basis  

       Basis  

c

c

B

B

       3        8       0       0

       3        8       0       0

x

x

2

2

    8      1/3      1    10/3    0      800

    8      1/3      1    10/3    0      800

s

s

2

2

     0      1/3      0  -20/3    1       400

     0      1/3      0  -20/3    1       400

z

z

j

j

         8/3      8    80/3    0     6400

         8/3      8    80/3    0     6400

c

c

j

j

 - 

 - 

z

z

j

j

      1/3      0   -80/3    0

      1/3      0   -80/3    0

Example:  Jonni’s Toy Co.

n

Simplex Method:  Third Tableau

Simplex Method:  Third Tableau

x

x

1

1

x

x

2

2

s

s

1

1

s

s

2

2

       Basis  

       Basis  

c

c

B

B

       3        8       0       0

       3        8       0       0

x

x

2

2

    8        0        1      10     -1       400

    8        0        1      10     -1       400

x

x

1

1

     3        1        0    -20       3     1200

     3        1        0    -20       3     1200

z

z

j

j

           3        8      20      1      6800

           3        8      20      1      6800

c

c

j

j

 - 

 - 

z

z

j

j

        0        0     -20     -1

        0        0     -20     -1

Example:  Jonni’s Toy Co.

n

Optimal Solution

Optimal Solution

•

Question:

Question:

How many animals of each size should be

How many animals of each size should be

produced daily and what is the resulting daily

produced daily and what is the resulting daily

profit?

profit?

•

Answer:

Answer:

Produce 1200 small animals and 400 large animals

Produce 1200 small animals and 400 large animals

daily for a total profit of $6,800.

daily for a total profit of $6,800.

n

Range of Optimality for 

Range of Optimality for 

c

c

1

1

 (small animals)

 (small animals)

Replace 3 by 

Replace 3 by 

c

c

1

1

 in the objective function row and

 in the objective function row and

c

c

B

B

 column.  Then recalculate 

 column.  Then recalculate 

z

z

j

j

 and 

 and 

c

c

j

j

 - 

 - 

z

z

j  

j  

rows.

rows.

z

z

j

j

c

c

1

1

    8     80   -20

    8     80   -20

c

c

1

1

   -8   +3

   -8   +3

c

c

1

1

    3200 + 1200

    3200 + 1200

c

c

1

1

c

c

j

j

 - 

 - 

z

z

j

j

     0    0    -80  +20

     0    0    -80  +20

c

c

1

1

    8    -3

    8    -3

c

c

1

1

For the 

For the 

c

c

j

j

 - 

 - 

z

z

j

j

 row to remain non-positive, 8/3 

 row to remain non-positive, 8/3 

<

<

c

c

1

1

<

<

 4

 4

Example:  Jonni’s Toy Co.

n

Range of Optimality for 

Range of Optimality for 

c

c

2

2

 (large animals)

 (large animals)

Replace 8 by 

Replace 8 by 

c

c

2

2

 in the objective function row and 

 in the objective function row and 

c

c

B

B

column.  Then recalculate 

column.  Then recalculate 

z

z

j

j

 and 

 and 

c

c

j

j

 - 

 - 

z

z

j  

j  

rows.

rows.

z

z

j

j

        3   

        3   

c

c

2

2

    -60   +10

    -60   +10

c

c

2

2

    9    -

    9    -

c

c

2

2

      3600 + 400

      3600 + 400

c

c

2

2

c

c

j

j

 - 

 - 

z

z

j

j

     0    0     60    -10

     0    0     60    -10

c

c

2

2

    -9   +

    -9   +

c

c

2

2

For the 

For the 

c

c

j

j

 - 

 - 

z

z

j

j

 row to remain non-positive, 6 

 row to remain non-positive, 6 

<

<

c

c

2

2

<

<

 9

 9

Example:  Jonni’s Toy Co.

Example:  Jonni’s Toy Co.

n

Range of Optimality

Range of Optimality

•

Question:

Question:

Will the solution change if the profit on

Will the solution change if the profit on

small

small

 animals is increased by $.75?  Will the

 animals is increased by $.75?  Will the

objective function value change?

objective function value change?

•

Answer:

Answer:

If the profit on small stuffed animals is

If the profit on small stuffed animals is

changed to $3.75, this is within the range of

changed to $3.75, this is within the range of

optimality and the optimal solution will not

optimality and the optimal solution will not

change.  However, since 

change.  However, since 

x

x

1

1

 is a basic variable at

 is a basic variable at

positive value, changing its objective function

positive value, changing its objective function

coefficient will change the value of the objective

coefficient will change the value of the objective

function to 3200 + 1200(3.75) = 7700.

function to 3200 + 1200(3.75) = 7700.

Example:  Jonni’s Toy Co.

n

Range of Optimality

Range of Optimality

•

Question:

Question:

Will the solution change if the profit on

Will the solution change if the profit on

large

large

 animals is increased by $.75?  Will the

 animals is increased by $.75?  Will the

objective function value change?

objective function value change?

•

Answer:

Answer:

If the profit on large stuffed animals is

If the profit on large stuffed animals is

changed to $8.75, this is within the range of

changed to $8.75, this is within the range of

optimality and the optimal solution will not

optimality and the optimal solution will not

change.  However, since 

change.  However, since 

x

x

2

2

 is a basic variable at

 is a basic variable at

positive value, changing its objective function

positive value, changing its objective function

coefficient will change the value of the objective

coefficient will change the value of the objective

function to 3600 + 400(8.75) = 7100.

function to 3600 + 400(8.75) = 7100.

Example:  Jonni’s Toy Co.

n

Range of Optimality and 100% Rule

Range of Optimality and 100% Rule

•

Question:

Question:

Will the solution change if the profits on

Will the solution change if the profits on

both large and small animals are increased by $.75?

both large and small animals are increased by $.75?

Will the value of the objective function change?

Will the value of the objective function change?

•

Answer:

Answer:

If both the profits change by $.75, since

If both the profits change by $.75, since

the maximum increase for 

the maximum increase for 

c

c

1

1

 is $1 (from $3 to $4)

 is $1 (from $3 to $4)

and the maximum increase in 

and the maximum increase in 

c

c

2

2

 is $1 (from $8 to

 is $1 (from $8 to

$9), the overall sum of the percent changes is

$9), the overall sum of the percent changes is

(.75/1) + (.75/1) = 75% + 75% = 150%.  This total is

(.75/1) + (.75/1) = 75% + 75% = 150%.  This total is

greater than 100%; both the optimal solution and

greater than 100%; both the optimal solution and

the value of the objective function change.

the value of the objective function change.

Example:  Jonni’s Toy Co.

n

Shadow Price

Shadow Price

•

Question:

Question:

The unit profits do not include a per

The unit profits do not include a per

unit labor cost.  Given this, what is the maximum

unit labor cost.  Given this, what is the maximum

wage Jonni should pay for overtime?

wage Jonni should pay for overtime?

•

Answer:

Answer:

Since the unit profits do not include a per

Since the unit profits do not include a per

unit labor cost, man-hours is a sunk cost.  Thus the

unit labor cost, man-hours is a sunk cost.  Thus the

shadow price for man-hours gives the maximum

shadow price for man-hours gives the maximum

worth of man-hours (overtime).  This is found in

worth of man-hours (overtime).  This is found in

the 

the 

z

z

j

j

 row in the 

 row in the 

s

s

1

1

 column (since 

 column (since 

s

s

1

1

 is the slack for

 is the slack for

man-hours) and is $20.

man-hours) and is $20.

Example:  Prime the Cannons!

n

LP Formulation

LP Formulation

                              Max    2

                              Max    2

x

x

1

1

 +  

 +  

x

x

2

2

 + 3

 + 3

x

x

3

3

                              s.t.         

                              s.t.         

x

x

1

1

 + 2

 + 2

x

x

2

2

 + 3

 + 3

x

x

3

3

<

<

  15

  15

                                          3

                                          3

x

x

1

1

 + 4

 + 4

x

x

2

2

 + 6

 + 6

x

x

3

3

>

>

  24

  24

x

x

1

1

 +   

 +   

x

x

2

2

 +   

 +   

x

x

3

3

  =  10

  =  10

x

x

1

1

, 

, 

x

x

2

2

, 

, 

x

x

3

3

>

>

  0

  0

Example:  Prime the Cannons!

n

Primal in Canonical Form

Primal in Canonical Form

•

Constraint (1) is a "

Constraint (1) is a "

<

<

" constraint.  Leave it alone.

" constraint.  Leave it alone.

•

Constraint (2) is a "

Constraint (2) is a "

>

>

" constraint.  Multiply it by -1.

" constraint.  Multiply it by -1.

•

Constraint (3) is an "=" constraint.  Rewrite this as

Constraint (3) is an "=" constraint.  Rewrite this as

two constraints, one a "

two constraints, one a "

<

<

", the other a "

", the other a "

>

>

"

"

constraint.  Then multiply the "

constraint.  Then multiply the "

>

>

" constraint by -1.

" constraint by -1.

(result on next slide)

(result on next slide)

Example:  Prime the Cannons!

n

Primal in Canonical Form (continued)

Primal in Canonical Form (continued)

     Max    2

     Max    2

x

x

1

1

 +  

 +  

x

x

2

2

 + 3

 + 3

x

x

3

3

                             s.t.        

                             s.t.        

x

x

1

1

 + 2

 + 2

x

x

2

2

 + 3

 + 3

x

x

3

3

<

<

   15

   15

                                       -3

                                       -3

x

x

1

1

 -  4

 -  4

x

x

2

2

 -  6

 -  6

x

x

3

3

<

<

  -24

  -24

x

x

1

1

 +   

 +   

x

x

2

2

 +   

 +   

x

x

3

3

<

<

   10

   10

                                         -

                                         -

x

x

1

1

 -    

 -    

x

x

2

2

 -    

 -    

x

x

3

3

<

<

  -10

  -10

x

x

1

1

, 

, 

x

x

2

2

, 

, 

x

x

3

3

>

>

 0

 0

Example:  Prime the Cannons!

n

Dual of the Canonical Primal

Dual of the Canonical Primal

•

There are four dual variables, 

There are four dual variables, 

U

U

1

1

, 

, 

U

U

2

2

, 

, 

U

U

3

3

', 

', 

U

U

3

3

".

".

•

 The objective function coefficients of the dual are

 The objective function coefficients of the dual are

the RHS of the primal.

the RHS of the primal.

•

The RHS of the dual is the objective function

The RHS of the dual is the objective function

coefficients of the primal.

coefficients of the primal.

•

The rows of the dual are the columns of the primal.

The rows of the dual are the columns of the primal.

(result on next slide)

(result on next slide)

Example:  Prime the Cannons!

n

Dual of the Canonical Primal (continued)

Dual of the Canonical Primal (continued)

     Min     15

     Min     15

U

U

1

1

 - 24

 - 24

U

U

2

2

 + 10

 + 10

U

U

3

3

' - 10

' - 10

U

U

3

3

"

"

                 s.t.            

                 s.t.            

U

U

1

1

 -   3

 -   3

U

U

2

2

 +    

 +    

U

U

3

3

' -     

' -     

U

U

3

3

"  

"  

>

>

   2

   2

                                2

                                2

U

U

1

1

 -   4

 -   4

U

U

2

2

 +    

 +    

U

U

3

3

' -     

' -     

U

U

3

3

"  

"  

>

>

   1

   1

                                3

                                3

U

U

1

1

 -   6

 -   6

U

U

2

2

 +    

 +    

U

U

3

3

' -     

' -     

U

U

3

3

"  

"  

>

>

   3

   3

U

U

1

1

, 

, 

U

U

2

2

, 

, 

U

U

3

3

', 

', 

U

U

3

3

" 

" 

>

>

 0

 0