原问题、对偶问题、一对对偶问题.ppt

第三章线性规划的对偶理论线性规划问题具有对偶性，即任何一个求极大值的线性规划问题，都有一个求极小值的线性规划问题与之对应，反之亦然．
原问题、对偶问题、一对对偶问题
对偶理论（DualityTheory）
[dju(:)’æliti]
研究对偶问题之间的关系及其解的性质
根据对偶理论，在解原问题的同时，也可以得到对偶问题的解，并且还可以提供影子价格等有价值的信息，在经济管理中有着广泛的应用．为什么研究对偶理论？§1对偶问题的一般概念1.1对偶问题的提出例1问题解决1.2对偶问题的形式1.对称型对偶问题矩阵形式对偶规则例32.非对称型对偶问题例4对偶规则原问题第k个约束为等式，对偶问题第k个变量是自由变量。
原问题第k个变量是自由变量，则对偶问题第k个约束为等式约束。3.混合型对偶问题对偶约束例5例3用矩阵理论讨论对偶问题因为原问题与对偶问题的对应关系§2对偶问题的基本性质产品A，B产量X1，X2，Z为利润X=(8,24)TZ=1843y1+3y25
y1+4y264812000MM
y1y2y3y4y5y6
yB11M48-4M120-7MMM00
My5533-1010
My66140-101
yB180+1/2M18-9/4M0M30-3/4M0-30+7/4M
My51/29/40-13/41-3/4
120y23/21/410-1/401/4
yB18400824M-8M-24
48y12/910-4/91/34/9-1/3
120y213/9011/9-1/3-1/91/3观察结论:对称性弱对偶性推论1无界性推论3例1例2例3最优性强对偶性根据弱对偶性定理，有根据最优性判别定理，Y*也是最优解推论4一对对偶问题的关系互补松弛性互补松弛条件互补松弛条件互补松弛关系（松紧关系）松约束与紧约束结论推论5松紧关系的实际意义w1wiwmwm+1wm+jwn+mmaxz=3x1+4x2-x3
s.t.4x1+2x2+5x3≤38
-x1+3x2-x3≥18
2x1-x2+3x3≤26
3x1+x2-2x3≥10
x1,x2,x3≥0例4先松后紧！！！非对称对偶问题的互补松弛条件对于非对称形式的对偶问题，因为此时
Y*无正负限制，所以只有一个成立
混合型对偶问题例5结论解的对应性推论单纯形乘子定理§3对偶问题的解利用原问题的最优单纯形表求对偶最优解例1为了求得对偶最优解Y*只需将初始基变量（包括人工变量）在原问题的目标函数中相应的系数(如果是人工变量，则系数为－M）减去对应的检验数σj即可例22.利用改进单纯形表求对偶最优解例3结论统一起来！§4对偶问题的经济解释——影子价格4.1影子价格的概念定义2影子价格yi*的经济意义影子价格的理解Lagrange乘子、灵敏度系数影子价格的具体内容影子价格的具体内容例1长线资源4.2影子价格在经济管理中的应用对偶的经济解释对偶问题影子价格能指示企业内部挖潜的方向影子价格能指示企业内部挖潜的方向影子价格在企业经营决策中的作用影子价格在企业经营决策中的作用w1
w2

wm机会成本互补松弛关系的经济解释影子价格在新产品开发决策中的应用例2利用影于价格分析现有产品价格变动对资源紧缺情况的影响利用影子价格分析工艺改变后对资源的影响注意§5对偶单纯形法原始可行性条件
原始最优性条件
原始单纯形法原始单纯形法的基本思路对偶可行性条件结论定义3定义4正则性正则基类推对偶单纯形法对偶单纯形法的定义对偶单纯形法的基本思想对偶单纯形法的优点原始单纯形法
保持解的可行性不变
由σ不小于等于0到小于等于0
对偶问题的解由不可行到可行
对偶单纯形法
始终保持对偶问题解的可行性
原问题的解由不可行到可行
一旦可行，即最优对偶单纯形法的优点对偶单纯形法的局限性对偶单纯形法的基本措施选出基变量选进基变量定理5.2对偶单纯形法的迭代步骤5.2对偶单纯形法的迭代步骤5.2对偶单纯形法的迭代步骤例15.3初始正则解的求法例2Why？