重庆工商大学：《管理运筹学》课程教学课件（讲稿）第二章 对偶理论与灵敏度分析

第二章对偶理论与灵敏度分析1单纯形法的矩阵描述2。对偶问题的提出3.线性规划的对偶理论4.影子价格5。对偶单纯形法6.灵敏度分析

第二章 对偶理论与灵敏度分析 • 1. 单纯形法的矩阵描述 • 2. 对偶问题的提出 • 3. 线性规划的对偶理论 • 4. 影子价格 • 5. 对偶单纯形法 • 6. 灵敏度分析

第一节单纯形法的矩阵描述设线性规划问题Z = CXmaxAX = bs.tX≥0不妨设基为B=(P P ... Pm)A=(PP ... P)=(B,NM)则[XBC=(CB,CN)XN基变量非基变量

不妨设基为   B P P Pm .  1 2 基变量 非基变量 0 . max    X s t AX b Z CX 设线性规划问题 ( , ) ( . ) ( , ) 1 2 B N N B n C C C X X X A P P P B N           则 第一节 单纯形法的矩阵描述

约束条件为：XB= BX+NX= bAX= b=(B,N)X=Xβ= B'(b-NX)= B-"b- B"NX今XN=0得当前的基解为：当前基解

B N N B N N B X B b NX B b B NX BX NX b X X AX b B N 1 1 1 ( ) - ( , )                     约束条件为： 令 得当前的基解为： X N  0 X B b 1 B   当前基解

目标函数Xb= CBX +CXZ =(CB,Cn)XnZ=C,B"b+(C-C,B'M)XN今X~=0得当前基可行解及目标函数值分别为：(B-"b(XB)X()这里 b=B-bXN0Z。=C,B-lb=C,b

B B N N N B B N C X C X X X Z C C            ( , ) 目标函数 Z C B b C b B B 1 ~ 0    令 得当前基可行解及目标函数值分别为： X 0 N  Z CBB b CN CBB N XN ( ) 1 1                      0 1 (1) B b X X X N B 这里 b B b ~ 1 

这里 N=B-IN检验数ON=C-C,N(..,)(.....)Om+ = Cm+1 -Cg,Pm+!当前检验数On =C, -C,P其中P, = B-'P,当前x对应的系数列

n n B n m m B m m n m m n N N B c C P c C P c c c c P P C C N ~ . ~ ) ~ . ~ ( . ) ( . )( ~ 1 1 1 1 1 1                  当前检验数 检验数 其中 j 1 P j B P   ~ 当前 对应的系数列 j x 这里 N B N ~ 1 