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

第二章对偶理论与灵敏度分析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 每周可用时间 对偶是指对同一事物（问题）从不同角度（立 场）观察，有两种对立的表述。 第二节 对偶问题的提出