第二章对偶理论与灵敏度分析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
矩阵单纯形法计算的描述线性规划问题ZCXmaxAX≤bS.t.X0≥化为标准型，引入松弛变量Xmax z = CX + 0XAX +IX.=bS.t.X≥0,X.≥0
矩阵单纯形法计算的描述 线性规划问题 0 . . max X AX b s t Z CX 化为标准型，引入松弛变量 Xs 0, 0 . . max 0 s s s X X AX IX b s t Z CX X
初始单纯形表初始基变量基变量非基变量XB XnX.0bN1BX.0CnCBCj-zj
初始单纯形表 0 0 j j B N s B N s c z C C X b B N I X X X 非基变量 基变量 初始基变量
基变量在单纯形表中对，其检应一个单位矩阵，验数永远为零B-I B=IB-II=B-1.形表当基变量为XB时，新基变量非基变量XXNXBIB'NB'bSXBCB!0Cv-CB'NCi-zj当前基解当前检验数0-CβB-IICB-CβB-IB=0
当基变量为 时，新的单纯形表 XB 当前基解 当前检验数 1 1 1 1 1 0 c z C C B N C B C X B b I B N B X X X j j N B B B B B N s 基变量 非基变量 B-1B=I CB -CB B-1B=0 B-1I=B-1 0-CB B-1I 基变量在单纯形表中对 应一个单位矩阵，其检 验数永远为零
单纯形法的矩阵描述结束
单纯形法的矩阵描述
第二节对偶问题的提出(立(问题）对偶是指对同一事物从不同角度场）观察，有两种对立的表述引例：某公司现有三条生产线来生产两种新产品，其主要数据见下表（时间单位为小时，利润单位为干元）。请问如何生产以使公司利润最大？产品1产品2每周可用时间014生产线I2012生产线Ⅱ2318生产线IⅢI利润 (干元)35
引例：某公司现有三条生产线来生产两种新产品，其 主要数据见下表（时间单位为小时，利润单位 为千元）。请问如何生产以使公司利润最大？ 生产线Ⅰ 生产线Ⅱ 生产线Ⅲ 利润（千元） 1 0 3 3 0 2 2 5 4 12 18 产品 1 产品 2 每周可用时间 对偶是指对同一事物（问题）从不同角度（立 场）观察，有两种对立的表述。 第二节 对偶问题的提出