文档介绍：Session 6 运筹学Operations Research 6-1
运筹学运筹学
Operations Research Operations Research 6 Dual theory and sensitivity analysis
¾ Important discoveries
6 Dual theory and sensitivity analysis
One of the most important discoveries in the early
development of linear programming was the concept of duality
¾ Dual theory revealed that every linear
and its many important ramifications. This discovery revealed
programming problem has associated with it that every linear programming problem has associated with it
another linear programming problem called the dual. The
another linear programming called the dual . so
relationships between the dual problem and the original
the duality theory and Sensitivity analysis are just problem prove to be extremely useful in a variety of ways.
starting from the relationship between the dual and ¾ Significance
prime Problems. One of the key uses of duality theory lies in the
interpretation and implementation of sensitivity analysis.
江西财经大学信息管理学院©2006 江西财经大学信息管理学院©2006
School of Information Technology, JiangXi University of Finance & Economics©2006 1 School of Information Technology, JiangXi University of Finance & Economics©2006 2
运筹学运筹学
Operations Research 6 Dual theory and sensitivity analysis Operations Research 6 Dual theory and sensitivity analysis
Contents The Essence of Duality Theory
¾ The essence of duality theory Primal problem Dual problem
¾ Economic interpretation of duality
n m
¾ Primal-dual relationships max Z = ∑ c j x j min y = b y
j =1 0 ∑ i i
i=1
n
¾ Adapting to other primal forms ⎧ m
⎪∑ aij x j ≤ bi ⎧
. j =1 ⎪ aij yi ≥ c j
¾ The role of duality theory in sensitivity analysis ⎨ . ∑
⎪ x ≥ 0 ⎨ i=1
⎩ j ⎪
¾ The essence of sensitivity analysis ⎩yi ≥ 0
max Z = CX
¾ Applying sensitivity analysis min y0 = yb
¾ Conclusions ⎧AX ≤ b ⎧yA ≥ c
.⎨ .⎨
⎩X ≥ 0 ⎩y ≥ 0
江西财经大学信息管理学院©2006 江西财经大学信息管理学院©2006
Sch