Limited Offer Get 25% off — use code BESTW25
No AI No Plagiarism On-Time Delivery Free Revisions
Claim Now
Prices start at $5 per page · plagiarism-free papers · free revisions for 14 days 24/7 support: support@bestwriters.com
Uncategorized

The Dual Problem and Sensitivity Analysis

  • Posted
  • Authoradmin
  • Length4,479 words
  • Reading time20 min
Write My Assignment FREE

THE DUAL PROBLEM
Dual Problem: Contents
• The dual problem and sensitivity analysis
• The optimal dual solution in simplex tableau
• Economic interpretation of dual variables
• Dual simplex method
• Post optimality or sensitivity analysis
2/26/2017 2
The Dual Problem and Sensitivity Analysis
• Primal LPP & dual LPP.
2/26/2017 3
The Dual Problem and Sensitivity Analysis
Definition of the Dual Problem:
1. Dual problem when Primal is in canonical form:-
– Consider the canonical form of LPP:
Maximize x
o = cj xj
Subject to:
a
ij xj ≤ bi , I = 1, 2, …, m
x
j ≥ 0, j = 1, 2, …, n
2/26/2017 4
The Dual Problem and Sensitivity Analysis
• It’s associated dual is given by:
Minimize yo = bi yi
Subject to:

a
ij yi ≥ cj,
j = 1, 2, …, n
yi ≥ 0, i = 1, 2, …, m

Where y1, y2, …, ym are the dual variables.
2/26/2017 5
The Dual Problem and Sensitivity Analysis
• Construction of dual problem from the primal
(or vice versa) is carried out as follows:
– Each constraint in one problem (i) corresponds to
a variable (j) in the other problem, i.e. n variables
and m constraints vs m variables and n
constraints.
– Elements of R.H.S. of the constraints in one
problem are equal to the respective coefficients of
the objective function in the other problem.
2/26/2017 6
The Dual Problem and Sensitivity Analysis
– One problem seeks maximization and the other
seeks minimization.
– The maximization problem has ≤ constraints and
the minimization problem has ≥ constraints.
– The variables in both problems are nonnegative.
2/26/2017 7
The Dual Problem and Sensitivity Analysis
Example:
Consider
Maximize x
o = 5×1 + 6×2
Subject to:
x
1 + 9×2 ≤ 60 ← y1
2x
1 + 3×2 ≤ 45 ← y2
5x
1 – 2×2 ≤ 20 ← y3
x
2 ≤ 30 ← y4
x
1 , x2 ≥ 0
2/26/2017 8
The Dual Problem and Sensitivity Analysis
• Let y1, y2, y3, and y4 be the dual variables associated
with the first, second, third, and fourth primal
constraints, then the dual problem is given by:
Minimize yo = 60y1 + 45y2 + 20y3 + 30y4
Subject to:
y1 + 2y2 + 5y3 ≥ 5
9y1 + 3y2 – 2y3 + y4 ≥ 6
y1, y2, y3, y4 ≥ 0
2/26/2017 9
The Dual Problem and Sensitivity Analysis
• Since the optimal solution of one problem can be
obtained from the optimal solution of the other, it is
computationally more efficient to solve the dual in
this case.
• This is because computational difficulty in LP mainly
depends on the number of constraints rather than
variables.
2/26/2017 10
The Dual Problem and Sensitivity Analysis
2. Dual Problem when primal is in standard form:
– An equality (=) constrained in the primal (dual)
corresponds to an unconstrained variable in the
dual (primal).
– Consider the problem
Maximize x
o = c1x1 + c2x2
Subject to:
a
11×1 + a12x2 = b1
a
21×1 + a22x2 ≤ b2
x
1, x2 ≥ 0
2/26/2017 11
The Dual Problem and Sensitivity Analysis
• In canonical form, the first constraint is replaced by:
a
11×1 + a12x2 ≤ b1 and –a11x1 – a12x2 ≤ -b1
• Let y+1, y-1, and y2 be the dual variable corresponding
to the canonical form, thus the dual problem is:
Minimize yo = b1(y+1 – y-1) + b2y2
Subject to:
a
11(y+1 – y-1) + a21y2 ≥ c1
a
12(y+1 – y-1) + a22y2 ≥ c2
y+1 , y-1 , y2 ≥ 0
2/26/2017 12
The Dual Problem and Sensitivity Analysis
• Let y1 = y+1 – y-1:– the difference between two
nonnegative variables, becomes unrestricted in sign
and the dual problem reduces to:
Minimize yo = b1y1 + b2y2
Subject to
a
11y1 + a21y1 ≥ c1
a
12y1 + a22y2 ≥ c2
y1 unrestricted in sign
y2 ≥ 0
2/26/2017 13
The Dual Problem and Sensitivity Analysis
• The dual variable corresponding to an equality
constraint in the primal (-) must be unrestricted in sign,
conversely, when a primal variable is unrestricted in
sign, its dual constraint must be in equation form.
• We conclude from the above that the dual variables
corresponding to a primal in standard from must all be
unrestricted in sign. However, this is true only for the
primal constraints that are initially in equation form
since the dual problems should be equivalent for both
the canonical and standard forms.
2/26/2017 14
The Dual Problem and Sensitivity Analysis
• In general given the primal in standard from:
Maximize x
o = cjxj
Subject to:
a
ijxj = bi , i = 1, 2, …, m
x
j ≥ 0, j = 1, 2, …, n
• The dual becomes:
Minimize yo = biyi
Subject to:
a
ijyi ≥ cj, j = 1, 2, …, n
yi unrestricted in sign for all i.
2/26/2017 15
The Dual Problem and Sensitivity Analysis
• On the other hand, consider the primal problem:
Maximize x
o = cjxj
Subject to:
a
ijxj ≤ bi , i = 1, 2, …, m
x
j, unrestricted in sign
• The dual is given by:
Minimize yo = biyi
Subject to:
a
ijyi = cj, j = 1, 2, …, n
yi ≥ 0, i = 1, 2, …, m
• Note: the dual problem is in standard form.
2/26/2017 16
The Dual Problem and Sensitivity Analysis
Example:
Maximize x
o = 5×1 + 12×2 + 4×3
Subject to:
x
1 + 2×2 + x3 ≤ 5
2x
1 – x2 + 3×3 = 2
x
1, x2, x3 ≥ 0
2/26/2017 17
The Dual Problem and Sensitivity Analysis
• In standard form:
Maximize x
o = 5×1 + 12×2 + 4×3 + 0S1
Subject to:
x
1 + 2×2 + x3 + S1 = 5
2x
1– x2 + 3×3 + 0S1 = 2
x
1, x2, x3, S1 ≥ 0
2/26/2017 18
The Dual Problem and Sensitivity Analysis
• The dual is given by:
Minimize yo = 5y1 + 2y2
Subject to:
y1 + 2y2 ≥ 5
2y1 – y2 ≥ 12
y1 + 3y2 ≥ 4
y1 ≥ 0
y2 unrestricted in sign.
2/26/2017 19
The Optimal Dual Solution in Simplex
Tableau
1. Relationship between objective values of primal
and dual
• Property:
– Assume the primal-dual problem are either in
canonical or standard forms and the two problems
have finite optimal solutions.
– Let x
o and yo be the values of the objective
function in the maximization and minimization
problems.
2/26/2017 20
The Optimal Dual Solution in Simplex
Tableau
– For any two feasible (not necessary basic) solutions
of the primal and the dual, xo ≤ yo.
– Moreover, at the optimal solutions of both
problems, min yo = max xo.
– Thus, for any two feasible solutions the value of yo
(min. problem) acts as an upper bound on the value
of x
o (max. problem).
– The property xo ≤ yo reveals that the optimal value
lies between x
o and yo.
2/26/2017 21
The Optimal Dual Solution in Simplex
Tableau
2. Relationship between optimal values of variables in
primal and dual.
• Consider the following example
Example:
Maximize x
o = 5×1 + 12×2 + 4×3
Subject to:
x
1 + 2×2 + x3 ≤ 5
2x
1 – x2 + 3×3 = 2
x
1, x2, x3 ≥ 0
2/26/2017 22
The Optimal Dual Solution in Simplex
Tableau
• The standard form is:
Maximize x
o = 5×1 + 12×2 + 4×3 + 0s1 – MR1
Subject to:
x
1 + 2×2 + x3 + s1 = 5
2x
1 – x2 + 3×3 + 0s1 = 2
x
1, x2, x3, S1 ≥ 0
2/26/2017 23
The Optimal Dual Solution in Simplex
Tableau
• The dual is given by:
Minimize yo = 5y1 + 2y2
Subject to
y1 + 2y2 ≥ 5
2y1 – y2 ≥ 12
y1 + 3y2 ≥ 4
y1 ≥ 0
y2 unrestricted in sign.
2/26/2017 24
The Optimal Dual Solution in Simplex
Tableau
2/26/2017 25
Solution of primal:
Basic xo x1 x2 x3 S1 R1 Solution
xo 1 0 0 3/5 29/5 -2/5+M 28 1/5
x2 0 0 1 -1/5 2/5 -1/5 8/5
x1 0 1 0 7/5 1/5 2/5 9/5
Solution of dual:
Basic yo y1 y+2 y-2 S1 S2 S3 R1 R2 R3 Solution
yo 1 0 0 0 -2/5 -8/5 0 9/5-M 8/5-M -M 28½
S3 0 0 0 0 -7/5 1/5 1 7/5 -1/5 -1 3/5
y2
– 0 0 -1 1 2/5 -1/5 0 -2/5 1/5 0 2/5
y1 0 1 0 0 -1/5 -2/5 0 1/5 2/5 0 29/5
The Optimal Dual Solution in Simplex
Tableau
• Consider the basic variables of the starting solution
in the primal of the above example. These are S1 &
R
1. The dual variables y1 and y2 correspond to the
primal constraint equations containing S1 and R1
respectively.
2/26/2017 26
The Optimal Dual Solution in Simplex
Tableau
2/26/2017 27
– Consider the coefficients of S1 and R1 in the x0 – equation
of the optimal primal tableau:
Starting solution variables (Primal) S1 R1
x0 – equation coefficient 29/5 (-2/5)+M
Corresponding dual variables y1 y2
Ignoring constant M, the coefficient 29/5 and -2/5 give
directly the optimal solution of the dual.
The Optimal Dual Solution in Simplex
Tableau
2/26/2017 28
– Consider the coefficients of the starting variables R1, R2, and
R3 in the y0 – equation of the optimal dual tableau:
Starting solution variables (dual) R1 R2 R3
yo– equation coefficients 9/5-M 8/5-M 0-M
Corresponding primal variables x1 x2 x3
Again ignoring constant M the coefficients give directly the
optimal solution, x1 =9/5, x2 = 8/5, x3 = 0.
– Conclusion: The optimal solution to the primal (dual) gives
directly the optimal solution to the (primal).
Economic Interpretation of Dual Variables
• Interpretation of the dual variables can be
recognized from the definition of the objective
function:
yo = bi yi
Where b
i represents the availability of ith scare
resource.
• Since at optimal solution, max xo = min yo, the dual
variables yi may be interpreted as the per unit
contribution of the ith resource to the value of
objective function.
2/26/2017 29
Economic Interpretation of Dual Variables
• Consider the solution of Example 1.
• The objective function of the dual problem is:
yo = 5y1 + 2y2
• And the optimal dual values are y1 = 29/5 and y2 = –
2/5. Each unit of the first resource (b1=5) contributes
29/5 in the objective function, while each unit of the
second resource (b2 = 2) contributes -2/5.
2/26/2017 30
Economic Interpretation of Dual Variables
• This shows that it does not pay to increase the
second resource since each additional unit will
decrease yo (and hence xo) by 2/5. An increase in the
first resource is promising since each unit increases
the value of the objective function by 29/5.
• This conclusion is true so long as the current primal
(dual) solution is optimal and feasible.
2/26/2017 31
Economic Interpretation of Dual Variables
Primal – Dual Properties:
• The following properties are developed based on a dual
problem obtained from the standard form of the primal.
Property I:
• At any iteration of the simplex solution of either the
primal or the dual, the matrix under the basic variables
of the starting solution (A) (not including the objective
equation row) can be used to generate the objective
equation coefficients corresponding to the basic
variables of the starting solution.
2/26/2017 32
Economic Interpretation of Dual Variables
• Step 1: Identify the original coefficients of the
objective function corresponding to the basic
variables of the current iteration and arrange them in
a row-vector in the same order of their respective
rows in the tableau (BVV).
• Consider the solution tableau of Example 1; i.e. final
iteration:

BVV = (x2, x1)
B. variables of solution
= (12 5)
original coefficients of B.V.

2/26/2017 33
Economic Interpretation of Dual Variables
• Step 2: Multiply the resulting vector (BVV) by the
matrix defined above (A). For the final iteration:
= (12 5) 2/5 -1/5 = (29/5 -2/5)
1/5 2/5
2/26/2017 34
Economic Interpretation of Dual Variables
• Step 3: Subtract the original coefficients of the objective
function corresponding to the basic variables of the
starting solution from the respective coefficients
obtained in step 2. This gives the result indicated by the
property:
Coeff. of S
1 = 29/5 – 0 = 29/5
Coeff. of R
1 = -2/5 – (-M) = -2/5 +M
• As shown these are the optimal solution to the other
problem, i.e. the simplex multipliers of the optimal
iteration give the optimal solution of the dual (primal)
problem.
2/26/2017 35
Economic Interpretation of Dual Variables
Property II:
• At any iteration of the simplex solution, by
substituting the corresponding simplex multipliers
for the respective variables in the dual constraints,
the coefficients of the x
o-equation in the primal are
given by the differences between the left-hand and
the right-hand sides of the corresponding dual
constraints.
• The property can also be used to generate the
coefficients of the yo-equation from the primal
constraints.
2/26/2017 36
Economic Interpretation of Dual Variables
2/26/2017 37
– Consider the 2nd iteration of the primal of example 1. The
corresponding simplex multipliers are .
– The dual constraint corresponding to is ≥ 5.
– Substituting the values of the multipliers for and and
taking the difference between the LHS & RHS of the
constrain, then which is the
coefficients of in the – equation.
– Similarly, the coefficients of can be obtained.
Economic Interpretation of Dual Variables
Result:
• A –ve coefficient in the x
0– equation of the primal implies
that the solution is not optimal. Since this coefficient
represents the difference between the LHS & RHS of the
dual constraints, it is seen from the direction of the
inequality that a –ve coefficient indicates that the
corresponding dual constraint is not satisfied.
• This leads to the conclusion that when the primal is nonoptimal the dual is infeasible and vice versa.
• Since the coefficient of every basic variable in the x0–
equation is always zero, the difference between the LHS
& RHS of the associated dual constraint must be zero.
2/26/2017 38
Economic Interpretation of Dual Variables
2/26/2017 39
Property III:
– At any iteration of the primal or the dual, the
corresponding values of the basic variables can be
obtained by multiplying the matrix defined in property I
(A) by the column vector comprising the original elements
of the RHS of the constraints.
– Consider the optimal iteration of primal:
Economic Interpretation of Dual Variables
2/26/2017 40
Property IV:
– At any iteration of the primal or the dual, the constraint
coefficients under any variable can be obtained by multiplying
the matrix defined in property I (A) by the column-vector
comprising the original elements of the constraints coefficients
under the designated variable.
– Consider the primal problem, the column-vectors
corresponding to the original coefficients of the constraints are:
Economic Interpretation of Dual Variables
2/26/2017 41
Hence, the corresponding coefficient of in the final
iteration:
=
= =
= =
Economic Interpretation of Dual Variables
2/26/2017 42
Summary of the Primal-Dual Properties
ith iteration:
Basic Non-basic Basic* RHS
r
o-equation Prop. II Prop. I£
Constrains Prop. IV [A] Prop. III
* Basic variables of the starting solution.
£ simplex multipliers.
Economic Interpretation of Dual Variables
• The properties show that the primal problem starts
feasible until the optimal solution reached. The dual
problem starts infeasible but better-than optimal and
continues to be infeasible until the true optimal
solution is reached.
• In other words, while the primal problem is seeking
optimality the dual problem is automatically seeking
feasibility.
2/26/2017 43
Economic Interpretation of Dual Variables
• The “dual simplex method” is similar to the simplex
method. It starts optimal (or actually better than
optimal) and infeasible and remains infeasible until
the true optimal is reached, at which point the
solution becomes feasible.
2/26/2017 44
Dual Simplex Method
• The method applies to problems which start dual
feasible (i.e. optimal but infeasible).
– Express constraints as ≤ as in canonical form.
– Objective function may be in either maximization or
minimization form.
– Add slack variables and obtain the initial tableau form.
– If any right-hand side element is –ve and if the optimality
condition is satisfied, the problem can be solved by the
dual simplex method.
2/26/2017 45
Dual Simplex Method
• A –ve R.H.S. element signifies that the corresponding
slack variable is –ve which means that the problem
starts optimal but infeasible as required by the dual
simplex method.
2/26/2017 46
Dual Simplex Method
2/26/2017 47
Example 2
Subject to:
– The initial tableau is obtained by having the constraints in
the form (≤) and adding the slack variables.
Dual Simplex Method
2/26/2017 48
Basic Solution
1 -2 -1 0 0 0 0
0 -3 -1 1 – – -3
0 -4 -3 0 1 0 -6
0 1 2 0 0 1 3
The starting solution is infeasible
since at least one basic variable is –ve. In the meantime, the
is optimal since all its coefficients are non-positive.
Thus, the problem can be handled with the dual simplex method.
Dual Simplex Method
• As in regular simplex method, the solution is based
on optimality and feasibility conditions. The
optimality condition guarantees that the solution
remains always optimal, while the feasibility
condition forces the basic solution toward the
feasible space.
• Feasibility condition: The leaving variable is the
basic variable having the most –ve value. If all basic
variables are non- negative the process ends.
2/26/2017 49
Dual Simplex Method
• Optimality condition: The entering variable is selected
from among the non-basic variables as follows.
– Take the ratios of the L.H.S. coefficients of the x
0– equation
to the corresponding coefficients in the equation
associated with the leaving variable.
– Ignore the ratios associated with +ve or zero
denominators.
– The entering variable is the one with the smallest ratio if
the problem is minimization, or the smallest absolute
value of the ratios if the problem is maximization.
– If all the denominators are zero or positive, the problem
has no feasible solution.
2/26/2017 50
Dual Simplex Method
2/26/2017 51
– After selecting the entering and leaving variables, row
operations are applied to obtain the next iteration.
– The leaving variable in the above tableau is . For the
entering variable, the ratios are given by
Variable
-2 -1 0 0 0
-4 -3 0 1 0
Ratios ½ – – –
The entering variable is
Dual Simplex Method
2/26/2017 52
– Applying row operations as usual:
Basic Solution
1 0 0 0 2
0 0 1 0 -1
0 1 0 0 2
0 0 0 1 -1
– The new solution is still optimal but infeasible
Dual Simplex Method
2/26/2017 53
– If is arbitrarily selected to leave the solution,
becomes the entering variable.
Basic Solution
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 -1 1 1 0
– Which is now optimal and feasible.
Dual Simplex Method
• The application of the dual simplex method is
especially useful in sensitivity analysis.
• For example, when a new constraint is added to the
problem after the optimal solution is obtained. If
this constraint is not satisfied by the optimal
solution, the problem remains optimal but it
becomes infeasible.
• The dual simplex method is then used to clear the
infeasibility in the problem.
2/26/2017 54
Post Optimality or Sensitivity Analysis
• It is often desirable to study the effect of discrete
changes in the different coefficients of the problem
on the current optimal solution.
• One way to accomplish this is to solve the problem
anew, but this may be computationally inefficient.
• Use of the properties of the simplex solution reduces
computations considerably.
2/26/2017 55
Post Optimality or Sensitivity Analysis
• Changes in LPP usually studied by post optimality
analysis include (Fig. 4-1):
– Tightness of the constraints, i.e. change in RHS of the
constraints
– Coefficients of the objectives function (profit or cost)
– coefficient of decision variables
– Addition of new variables to the problem
– Addition of new (or secondary) constraints.
2/26/2017 56
Post Optimality or Sensitivity Analysis
2/26/2017 57
Post Optimality or Sensitivity Analysis
• These changes may result in one of three cases:
– Optimal solution (basic variables & their values)
remains unchanged.
– Basic variables remain the same but their values
change.
– The basic solution changes completely.
2/26/2017 58
Post Optimality or Sensitivity Analysis
• Detection of these cases is based on the primal-dual
properties:
1. Changes in the tightness of constraints in the primal
(dual) can only affect the feasibility of the primal (dual) or
equivalently the optimality of the dual (primal) (property
III). Because they represent the function coefficient of
dual.
2. Changes in the coefficients of the objective function in
primal (dual) can only affect the optimality of primal
(dual) or equivalently the feasibility of dual (primal)
(properties I & II).
2/26/2017 59
Post Optimality or Sensitivity Analysis
3. Changes in the technological coefficients of nonbasic variables of the primal (dual) can only affect
the optimality of primal (dual), or equivalently the
feasibility of dual (primal) (property II).
2/26/2017 60
Post Optimality or Sensitivity Analysis
2/26/2017 61
(1) Changes in tightness of constraints:
 Consider that R H S of the primal constraints of
example 1 is changed from
How this affect the current optimal solution given by
x0 = 141/5, x1= 9/5, x2 = 8/5, and x3 = 0 ?
Post Optimality or Sensitivity Analysis
2/26/2017 62
– By property III, such change can only affect the RHS of
the tableau and hence the feasibility of the problem. The
new values of current basic variables are:
Since both & are nonnegative, the current basic
solution remains feasible and optimal .
x0 = 5(11/5) + 12(12/5) + 4(0) = 199/5
Post Optimality or Sensitivity Analysis
2/26/2017 63
 Consider another case where RHS of the primal constraint is
.
Then,
(correction 10 not 0)
x2 becomes infeasible ( 0). Thus, the first constraint is not
satisfied and the change leaves the current optimal solution
infeasible.
Post Optimality or Sensitivity Analysis
2/26/2017 64
– Dual simplex method is used to restore feasibility. The RHS
of the optimal tableau is change to the new values of
Basic Solution
Other elements remain unchanged.
– Since x0-equation is optimal and the basic solution is
infeasible (x2<0), the dual simplex method is used to clear
infeasibility with x2 as leaving variable and as the
entering variable.
Post Optimality or Sensitivity Analysis
2/26/2017 65
– Which resource should be increased in order to achieve the
best marginal increase in the value of objective function?
The answer calls for considering the dual objective
function
are dual optimal values.
– The first resource should be increased since each
additional unit increases the objective function by
Post Optimality or Sensitivity Analysis
2/26/2017 66
– How much can one increase the first resource while
maintaining the property that each additional unit
contributes will remain correct as long as the primal
problem remains feasible.
– Let represents the increase in first resource, the max
value of can be determined from:
– This shows that x1 & x2 will remain feasible for any ,
indicating that the first resource can be increased
indefinitely while maintaining the mentioned property.
Post Optimality or Sensitivity Analysis
(2) Changes in the Coefficients of the objective
function:
– Such changes only affect the optimality of the
problem.
– Two types of changes:
• Changes in the basic variables coefficients lead to
change in the simplex multipliers (dual values).
• Changes in the non-basic variables where simplex
multipliers remain unchanged and optimality can be
checked directly.
2/26/2017 67
Post Optimality or Sensitivity Analysis
2/26/2017 68
Basic coefficients
 Suppose the coefficients of x1 & x2 in the objective
function of example 1 were changed from 5 and 12 to 4
and 10. By property I, the new simplex multipliers are:
 Hence, the new coefficients of S1 & R1 in the objective
function are:
Coefficient of S1 = 24/5 – (0) = 24/5 > 0
Coefficient of R1 = –2/5 – (-M) = –2/5 +M > 0
Both satisfy optimality.
Post Optimality or Sensitivity Analysis
2/26/2017 69
 Remaining coefficients of the objective equation will be
checked using property II by checking the feasibility of the
corresponding new dual constraints.
Coeff. of x1= 1(24/5)+2(-2/5)-4=0
Coeff. of x2= 2(24/5)-1(-2/5)-10=0
Coeff. of x3= 1(24/5)+3(-2/5)-4=-2/5(<0)
 Because the coefficient of x3 is –ve, the current optimal
solution is no longer optimal and must be changed. This is
done by applying the regular simplex to the current
optimal tableau after changing its x0 – equation coefficients
to show the new changes including x0.
Post Optimality or Sensitivity Analysis
Non-basic coefficients:
• The simplex multipliers are not affected by the
changes, and they are used directly to check the
objective equation coefficients. This is done by
checking the feasibility of the corresponding dual
constraints with their RHSs changed to the new
values.
2/26/2017 70
Post Optimality or Sensitivity Analysis
2/26/2017 71
– Consider the coefficient of x3 of the objective equation of
Example 1 is changed from 4 to 8, then its corresponding
dual constraint is changed from:
.
The simplex multipliers and give
the new coefficient of x3 in the objective equation:
,
which is not satisfied because it is –ve.
– Hence, it becomes the entering variable.
Post Optimality or Sensitivity Analysis
Basic and Non-basic Coefficients:
• Simultaneous changes in basic and non-basic
coefficients can be dealt with by combining the
above two procedures. Minding that the effect of
separate changes may differ from that of
simultaneous changes.
2/26/2017 72
Post Optimality or Sensitivity Analysis
(3) Changes in the Technological Coefficients
– Property II reveals that changes in the technological
coefficients of the problem can affect the LHS of its dual
constraints and hence the feasibility of the dual (or
equivalently the optimality of the primal).
– Changes in the technological coefficients of a basic
variable will directly affect the elements of the matrix
under the starting solution, which has the important role
in all sensitivity analysis computations. The new changes
may cause the current solution to be infeasible or nonoptimal or it may even cease to be basic at all.
– For this type of changes it is difficult to consider
systematically their effect on the optimal solution. They
will not be investigated here.
2/26/2017 73
Post Optimality or Sensitivity Analysis
2/26/2017 74
– Changes in the technological coefficients of non-basic
variables:
– Consider the technological coefficients of x3 are
changed from: . (correction -5)
– The new dual constraint corresponding to x3 becomes:
– The values of the simplex multipliers remain
unchanged.
– By property II the new coefficient of x3 in the x0 –
equation is:
.
– The current solution is no longer optimal.
Post Optimality or Sensitivity Analysis
2/26/2017 75
– Thus, changes in the coefficients under x3 must be
introduced in the optimal tableau and the regular simplex
method is applied to obtain the new optimal solution.
Basic
x1 x1 x2 x3 Solution
x0
x2
x1
– The new technological coefficients of x3, obtained by using
property IV:
– The new problem has no bounded solution since all the
constraint coefficients are –ve.
Post Optimality or Sensitivity Analysis
(4) Addition of A New Variable:
• This case is similar to the simultaneous changes in the
objective function coefficients and the technological
coefficients of a corresponding non-basic variable.
• It may be regarded as changing the coefficients of a nonbasic variable which initially were all equal to zero.
• Consequently, the addition of a new variable can only affect
the optimality of the problem, and the new variable will
enter the solution iff it improves the value of the objective
function Otherwise, it becomes non-basic at zero level.
2/26/2017 76
Post Optimality or Sensitivity Analysis
• Consider addition of x
4 to Example 1. Let the coeff. of x4
in objective function be 6 and its technological
coefficients in the first and second constraints be 5 and 7.
• The corresponding dual constraint is 5y1+7y2 ≥ 6. The
optimal dual values y1=29/5 and y2= -2/5 satisfy this
constraint and hence x
4 can not improve the current
optimal solution.
• But if the corresponding dual constraint is 5y1+7y2 ≥ 30,
the constraint becomes unsatisfied and x
4 must enter the
solution and x
1 leaves it. Use properties II & IV to make
changes in the tableau.
2/26/2017 77
Post Optimality or Sensitivity Analysis
(5) Addition of A New Constraint:
• A new constraint can affect the feasibility of the
current optimal solution only if it is active.
• Consequently, the first step is to check whether the
new constraint is satisfied by the current optimal
solution.
– If so, the new constraint is redundant and the optimal
solution remains unchanged.
– Otherwise, the new constraint must be added to the
system.
2/26/2017 78
Post Optimality or Sensitivity Analysis
2/26/2017 79
– Consider addition of constraint to
Example 1. Since the optimal solution is:
this constraint is satisfied
and hence it is redundant.
– Consider, instead that the constraint is
then it is not satisfied and the
current solution becomes infeasible.
– To clear the infeasibility, the new constraint is added to the
optimality tableau:
Post Optimality or Sensitivity Analysis
2/26/2017 80
Basic x0 x1 x2 x3 S1 R1 S3 Solution
x0 1 0 0 3/5 29/5 -2/5+M 0 141/5
x2 0 0 1 -1/5 2/5 -1/5 0 8/5
x1 0 1 0 7/5 1/5 2/5 0 9/5
S3 0 5 10 3 0 0 1 10
– Since x1 & x2 are in the basic solution, their corresponding
coefficients in the additional constraint must be zero.
– This is done by row-operations to give:
x0 x1 x2 x3 S1 R1 S3 Solution
x0 1 0 0 3/5 29/5 -2/5+M 0 141/5
x2 0 0 1 -1/5 2/5 -1/5 0 8/5
x1 0 1 0 7/5 1/5 2/5 0 9/5
S3 0 0 0 -2 5 0 1 -15
– The x0 –equation IS OPTIMAL BUT THE CURRENT BASIC
SOLUTON IS INFEASIBLE. The dual simplex method shows
that S3 is the leaving variable and x3 is the entering variable.
Post Optimality or Sensitivity Analysis
• This method can be used to reduce the
computational effort by deleting the secondary
constraints, then after obtaining the optimal
solution, the deleted constraints are checked for
feasibility.
2/26/2017 81
Post Optimality or Sensitivity Analysis
Concluding Remark:
• Effect of simultaneous changes rather than independent
treatment of the changes.
• Example: the case where both the objective and constraint
coefficients of a non-basic variable are modified. This
situation is treated exactly as if a new variable is added to the
problem by checking the feasibility of the new dual constraint.
• Another problem occurs when the changes in the coefficients
take place systematically (rather than in a discrete manner)
according to predetermined linear functions. This is called
“Parametric linear Programming”.
2/26/2017 82
Post Optimality or Sensitivity Analysis
Example 1:
Maximize x
0 = 5×1 + 12×2 + 4×3 – MR2
Subject to:
x
1 + 2×2 + x3 – S1 = 5
2x
1 – x2 + 3×3 + R2= 2
x
1, x2, x3, S1, R2 ≥ 0
2/26/2017 83
Post Optimality or Sensitivity Analysis
2/26/2017 84
ith Iteration
Basic Non-basic variable Basic Variables RHS
Prop. II Prop. I (simplex multiplier)
Prop. IV [A] Prop. III
For any iteration of primal or dual:
Prop. I: Matrix [A] can be used to generate O.E. coefficients
corresponding to the basic variables of the starting solution:
(BVV)[A] = (Simplex multipliers)
Post Optimality or Sensitivity Analysis
2/26/2017 85
For any iteration of primal or dual:
Prop. I: Matrix [A] can be used to generate O.E. coefficients
corresponding to the basic variables of the starting solution:
(BVV)[A] = (Simplex multipliers)
Simplex multipliers
Post Optimality or Sensitivity Analysis
2/26/2017 86
Coeff. of x2 in obj.
function equation of
iteration 2
End
2/26/2017 87

The post The Dual Problem and Sensitivity Analysis appeared first on My Assignment Online.

Plagiarism Free Assignment Help

Expert Help With This Assignment — On Your Terms

✓ Native UK, USA & Australia writers ✓ Deadline from 3 hours ✓ 100% Plagiarism-Free — Turnitin included ✓ Unlimited free revisions ✓ Free to submit — compare quotes

admin

Academic writer and editor at BestWriters.

Get your paper off your plate tonight

Post your instructions for free. Prices start at $5 per page.

Place an order