第02章 对偶问题与灵敏度分析.ppt

《第02章 对偶问题与灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《第02章 对偶问题与灵敏度分析.ppt（142页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1计算机学院 陈丰 运筹学2力学中有对偶，数学规划论中也有对偶。力学中有对偶，数学规划论中也有对偶。20世纪世纪50年年代，运筹学界发现每个线性规划问题都有一个相对应的代，运筹学界发现每个线性规划问题都有一个相对应的“影影像像”，称之为，称之为LP问题的对偶问题（问题的对偶问题（Dual Programming，DP）。它们都是研究同一对象，出于同一目的，但研究的角度它们都是研究同一对象，出于同一目的，但研究的角度不同，它们密切联系又有区别，相辅相成，互为对偶。不同，它们密切联系又有区别，相辅相成，互为对偶。第2章 线性规划的对偶理论与灵敏度分析3提提 纲纲1 线性规划的对偶线性规划的对偶问题

2、问题2 对偶问题的基本性质对偶问题的基本性质3 影子价格影子价格4 对偶单纯形法对偶单纯形法5 灵敏度分析灵敏度分析4学习目标：学习目标：1 掌握原问题与其对偶问题的对应关系掌握原问题与其对偶问题的对应关系2 能熟练准确地写出一般形式的线性规划的对偶问题能熟练准确地写出一般形式的线性规划的对偶问题1 线性规划的对偶问题线性规划的对偶问题51 线性规划的对偶问题线性规划的对偶问题1.1 对偶问题的提出对偶问题的提出1.2 对称形式下对偶问题的一般形式对称形式下对偶问题的一般形式1.3 非对称形式下对偶问题的一般形非对称形式下对偶问题的一般形 式式61.1 对偶问题的提出对偶问题的提出在第在第1章

3、例章例1中讨论了工厂生产计划模型及其解法，中讨论了工厂生产计划模型及其解法，该问题站在该问题站在工厂管理者的角度追求利润最大工厂管理者的角度追求利润最大。我们记为。我们记为LP1：项目项目每天可用能力每天可用能力设备设备A（h）设备设备B（h）调试工序（调试工序（h）06152115245利润（元）利润（元）21max z 2x1x2 5x2 156x1 2x2 24 x1 x2 5 x1，x2 0st.（LP1）7现从另一角度来讨论这个问题。假定该厂的决策者决定现从另一角度来讨论这个问题。假定该厂的决策者决定不生产产品不生产产品、，而，而将其所有资源出租或外售将其所有资源出租或外售。这时工。

4、这时工厂的决策者就要考虑厂的决策者就要考虑给各种资源如何定价的问题给各种资源如何定价的问题。项目项目每天可用能力每天可用能力设备设备A（h）设备设备B（h）调试工序（调试工序（h）06152115245利润（元）利润（元）218设分别用设分别用y1、y2和和y3表示单位时间（表示单位时间（h）设备）设备A、设备、设备B和调试和调试工序的工序的出让价格出让价格。则。则该厂的决策者进行定价决策时，将作如下比该厂的决策者进行定价决策时，将作如下比较：较：若用若用6h设备设备B和和1h调试工序可生产一件调试工序可生产一件产品产品，利润为，利润为2元，那么将生产每件产品元，那么将生产每件产品的设备台时和

5、调试工序的设备台时和调试工序出租和出让的出租和出让的所有收入应不低于生产一件产品所有收入应不低于生产一件产品的利润的利润，这就有，这就有 6y2y32项目项目每天可用能力每天可用能力设备设备A（h）设备设备B（h）调试工序（调试工序（h）06152115245利润（元）利润（元）219同理将生产一件产品同理将生产一件产品的设备台时和调试工序的设备台时和调试工序出租和出出租和出让的所有收入应不低于生产一件产品让的所有收入应不低于生产一件产品的利润的利润，这就有，这就有 5y12y2y31项目项目每天可用能力每天可用能力设备设备A（h）设备设备B（h）调试工序（调试工序（h）06152115245

6、利润（元）利润（元）21将工厂所有设备台时和调试工序都出租和出让，将工厂所有设备台时和调试工序都出租和出让，其总的收入为其总的收入为 w15y124y25y3从从工厂的决策者来看当然工厂的决策者来看当然w愈大愈好，但从接受者来看他的支愈大愈好，但从接受者来看他的支付愈少愈好，所以工厂的决策者付愈少愈好，所以工厂的决策者只能在满足只能在满足所有产品的利润条所有产品的利润条件下，使其总收入尽可能地小件下，使其总收入尽可能地小，他才能实现其意愿，为此可得到，他才能实现其意愿，为此可得到如下的线性规划问题：如下的线性规划问题：min w15y124y25y3 6y2y325y12y2y31y1，y2，

7、y3 0st.（LP2）项目项目每天可用能力每天可用能力设备设备A（h）设备设备B（h）调试工序（调试工序（h）06152115245利润（元）利润（元）2111min w15y124y25y3 6y2y325y12y2y31y1，y2，y3 0st.（LP2）我们称这个线性规划问题为例我们称这个线性规划问题为例1线性规划问题（这里称为线性规划问题（这里称为原问原问题题）的）的对偶问题对偶问题。联系：联系：都都 是关于工厂的模型并且使用相同的数据，目的都是是关于工厂的模型并且使用相同的数据，目的都是为了提高工厂的效益。为了提高工厂的效益。区别：区别：模型反映的角度不同，前者为充分利用资源问题，

8、后者模型反映的角度不同，前者为充分利用资源问题，后者为资源恰当估价问题。为资源恰当估价问题。max z 2x1x2 5x2 156x1 2x2 24 x1 x2 5 x1，x2 0st.（LP1）任何线性规划问题都有对偶任何线性规划问题都有对偶问题，而且都有相应的意义。问题，而且都有相应的意义。121 线性规划的对偶问题线性规划的对偶问题1.1 对偶问题的提出对偶问题的提出1.2 对称形式下对偶问题的一般形式对称形式下对偶问题的一般形式1.3 非对称形式下对偶问题的一般形非对称形式下对偶问题的一般形 式式131.2 对称形式下对偶问题的一般形式对称形式下对偶问题的一般形式定义：定义：满足下列条

9、件的线性规划问题称为满足下列条件的线性规划问题称为具有对称形式具有对称形式：变量均具有非负约束变量均具有非负约束 约束条件当目标函数求极大时取约束条件当目标函数求极大时取“”号，当目标函数号，当目标函数 求极小时均取求极小时均取“”号。号。max z 2x1x2 5x2 156x1 2x2 24 x1 x2 5 x1，x2 0st.（LP1）LP1具有对称形式具有对称形式min w15y124y25y3 6y2y325y12y2y31y1，y2，y3 0st.（LP2）LP2为为LP1的对偶问题，的对偶问题，LP2也也具有对称形式具有对称形式max z 2x1x2 5x2 156x1 2x2

10、24 x1 x2 5 x1，x2 0st.min w15y124y25y3 6y2y325y12y2y31y1，y2，y3 0st.（LP2）（LP1）项目项目原问题原问题对偶问题对偶问题目标函数目标函数maxmin决策变量个数决策变量个数 n=2n=2 个约束条件个约束条件nm约束条件个数约束条件个数 m=3m=3 个决策变量个决策变量C目标函数变量的系数目标函数变量的系数C=(2,1)约束条件右端项约束条件右端项b=(2,1)Tb约束条件右端项约束条件右端项b=(15,24,5)T目标函数变量的系数目标函数变量的系数C=(15,24,5)决策变量决策变量X=(x1,x2)T 0Y=(y1,

11、y2,y3)T 015max z 2x1x2 5x2 156x1 2x2 24 x1 x2 5 x1，x2 0st.min w15y124y25y3 6y2y325y12y2y31y1，y2，y3 0st.（LP2）（LP1）0 5 6 21 1系数矩阵系数矩阵 A0 6 1 5 2 1项目项目原问题原问题对偶问题对偶问题A约束系数矩阵约束系数矩阵约束系数矩阵的转置约束系数矩阵的转置系数矩阵的系数矩阵的转置转置 ATaij=aji16下面是对称形式下线性规划下面是对称形式下线性规划原问题的一般形式原问题的一般形式：max z c1x1c2x2 cnxnst.a11x1a12x2 a1n xn

12、b1a21x1a22x2 a2n xn b2 am1x1am2x2 amn xnbmx1，x2，xn0用用yi(i=1,.,m)代表第代表第i种资源的估价，则其种资源的估价，则其对偶问题的一般形式对偶问题的一般形式为为min w b1y1b2y2 bmymst.a11y1a21y2 am1ymc1a12y1a22y2 am2ymc2 a1ny1a2ny2amnymcny1，y2，ym0矩阵表示矩阵表示max z=CXAXbX0st.min w=YTbATYCTY0st.17nATCbminmAbCmaxmnmin w=YTbATYCTY0st.max z=CXAXbX0st.原原问问题题对对偶

13、偶问问题题对称形式对称形式下线性规划的原问题与对偶问题的下线性规划的原问题与对偶问题的对应关系对应关系：P43 例1 写出下述线性规划问题的对偶问题（写出下述线性规划问题的对偶问题（即第即第1章章 例例1）max z 2x1x2 2x2156x12x224 x1 x25 x1，x2 0st.y1y2y3min w 15y124y25y3目标函数目标函数转转置置 0 6 1 2 2 1 AT =y1 y2 y3st.0 2 6 21 1A=y1，y2，y3 021 6y2 y3 2y12y2y3 约束条件约束条件191 线性规划的对偶问题线性规划的对偶问题1.1 对偶问题的提出对偶问题的提出1.

14、2 对称形式下对偶问题的一般形式对称形式下对偶问题的一般形式1.3 非对称形式下对偶问题的一般形非对称形式下对偶问题的一般形 式式20并非所有线性规划问题具有对称形式并非所有线性规划问题具有对称形式，故下面讨论一般情况，故下面讨论一般情况下线性规划问题如何写出其对偶问题。下线性规划问题如何写出其对偶问题。1.3 非对称形式的原非对称形式的原-对偶问题关系对偶问题关系项目项目原问题原问题对偶问题对偶问题A约束系数矩阵约束系数矩阵其约束系数矩阵的转置其约束系数矩阵的转置b约束条件的右端项向量约束条件的右端项向量目标函数中的价格系数向量目标函数中的价格系数向量C目标函数中的价格系数目标函数中的价格系

15、数向量向量约束条件的右端项向量约束条件的右端项向量目标函数目标函数max z=CXmin w=YTb无论对称或非对称无论对称或非对称的线性规划问题在写出其对偶问题时，下的线性规划问题在写出其对偶问题时，下表的对应关系都适用。表的对应关系都适用。21原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max目标函数目标函数 minn个个n个个00无约束无约束=m个个m个个00=无约束无约束由于前面四个对应关系与对称形式下的对应关系一致，故我由于前面四个对应关系与对称形式下的对应关系一致，故我们只需讨论们只需讨论约束类型与变量类型之间约束类型与变量类型

16、之间的对应关系的对应关系:约约束束条条件件约约束束条条件件变变量量变变量量符号相同符号相同符号相反符号相反符号相同符号相同符号相反符号相反转转置置 1 -1 4-1 5 -1 4 7 3AT =P64 2.1(b)写出下述线性规划问题的对偶问题写出下述线性规划问题的对偶问题max z 5x16x23x3 x12x22x3 =5x15x2 x3 3 4x17x23x3 8x1无约束无约束，x2 0，x3 0st.y1y2y3min w 5y13y28y3目标函数目标函数同同号号 1 2 2 -1 5 -1 4 7 3A=y1 ，y2 ，y3 y1y24y3 y15y2y3 4y17y23y3 s

17、t.y1 y2 y3约束条件约束条件563=00反号反号无约束无约束转转置置-4 -3 5 2 -6 0 -6 -4 3AT =P44 例例3 写出下述线性规划问题的对偶问题写出下述线性规划问题的对偶问题min z 7x14x24x34x12x26x3243x16x24x315 5x1 3x330 x10,x2无无约束约束,x30st.y1y2y3max w24y115y230y3目标函数目标函数-4 2 -6 -3 -6 -4 5 0 3A=y1 ，y2 ，y3 4y13y25y3 2y16y2 6y14y23y3 st.y1 y2 y3约束条件约束条件74-4 0同同号号0无约束无约束反号

18、反号24学习目标：学习目标：1 掌握单纯形法的矩阵描述，它是灵敏度分析的基础掌握单纯形法的矩阵描述，它是灵敏度分析的基础2 理解对偶问题的基本性质理解对偶问题的基本性质2 对偶问题的基本性质对偶问题的基本性质25max z cjxjj=1nst.aij xjbi （i=1，m）j=1n xj0 （j=1，n）本节的讨论先假定本节的讨论先假定原问题及对偶问题为对称形式原问题及对偶问题为对称形式线性规划问线性规划问题（题（结论同样适用于非对称形式结论同样适用于非对称形式），原问题为：），原问题为：2 对偶问题的基本性质对偶问题的基本性质其对偶问题为：其对偶问题为：min w bi yii=1mst

19、.aij yici （j=1，n）i=1m yi0 （i=1，m）（2.9）（2.10）max z=CXAXbX0st.min w=YTbATYCTY0st.262 对偶问题的基本性质对偶问题的基本性质2.1 单纯形法计算的矩阵描述单纯形法计算的矩阵描述2.2 对偶问题的基本性质对偶问题的基本性质27 cj 3 -1 2 0 0 CBxBb x1 x2 x3 x4 x5 0 0 x4x561 2 4 -2 1 0-1 3 2 0 1j 3 -1 2 0 0 max z 3x1x22x32x14x22x36x13x22x31x1，x2，x30st.例例4 用单纯形法求解用单纯形法求解 max z

20、3x1x22x30 x40 x52x14x22x3x4 6x13x22x3 x51x1，x2，x3，x4，x50st.列出初始列出初始单纯形表单纯形表283-1200CBXBbx1x2x3x4x50 x4624-2100 x51-13201j3-12003x1312-11/200 x540511/21j0-75-3/203x17170112x340511/21j0-320-4-5 6 2 4-2 1 01 -1 3 2 0 13 1 2-1 1/2 01 -1 3 2 0 1(1/2)3 1 2-1 1/2 04 0 5 1 1/2 117 1 7 0 1 14 0 5 1 1/2 11单纯行

21、单纯行法的迭代法的迭代过程实际过程实际上是对上是对增增广矩阵广矩阵进进行的行的初等初等行变换行变换。A1A2A3A429矩阵的矩阵的初等变换初等变换不只是可用语言表述，而且不只是可用语言表述，而且可用矩阵的乘法运可用矩阵的乘法运算来表示算来表示。为此要引入。为此要引入初等矩阵初等矩阵的概念。的概念。初等矩阵初等矩阵：将将单位矩阵单位矩阵作一次作一次初等（行初等（行/列）变换列）变换所得的矩阵所得的矩阵称为称为初等矩阵初等矩阵。以非以非0常数常数 c 乘以矩阵的某一行（列）乘以矩阵的某一行（列）Ei(c)将矩阵的某一行（列）乘以常数将矩阵的某一行（列）乘以常数 c 并加到另一行（列）并加到另一行

22、（列）Eij(c)将矩阵的某两行（列）对换位置将矩阵的某两行（列）对换位置 Eij复习初等变换和初等矩阵复习初等变换和初等矩阵1 00 11/2 0 0 1(1/2)单位矩阵单位矩阵初等矩阵初等矩阵即上述结果可表示为：即上述结果可表示为：E1(1/2)30由线性代数可知，对矩阵进行的由线性代数可知，对矩阵进行的初等行变换初等行变换，相当于，相当于用相应的用相应的初等矩阵初等矩阵左乘左乘矩阵矩阵。6 2 4-2 1 01 -1 3 2 0 13 1 2-1 1/2 01 -1 3 2 0 1(1/2)A1A2E1(1/2)A1=1/2 0 0 16 2 4-2 1 01 -1 3 2 0 13

23、1 2-1 1/2 01 -1 3 2 0 1=A2313-1200CBXBbx1x2x3x4x50 x4624-2100 x51-13201j3-12003x1312-11/200 x540511/21j0-75-3/203x17170112x340511/21j0-320-4-5 6 2 4-2 1 01 -1 3 2 0 13 1 2-1 1/2 01 -1 3 2 0 1(1/2)3 1 2-1 1/2 04 0 5 1 1/2 117 1 7 0 1 14 0 5 1 1/2 11单纯行单纯行法的迭代法的迭代过程实际过程实际上是对上是对增增广矩阵广矩阵进进行的行的初等初等行变换行变换

24、。A1A2A3A4这就相当于这就相当于用有限多个用有限多个初等矩阵初等矩阵E1，E2，Ek依次依次左乘增广矩阵左乘增广矩阵。A43-1200CBXBbx1x2x3x4x50 x4624-2100 x51-13201j3-12003x1312-11/200 x540511/21j0-75-3/203x17170112x340511/21j0-320-4-5 6 2 4-2 1 01 -1 3 2 0 13 1 2-1 1/2 01 -1 3 2 0 1(1/2)3 1 2-1 1/2 04 0 5 1 1/2 117 1 7 0 1 14 0 5 1 1/2 11A1A2A3E1(1/2)E12

25、(1)E21(1)E1(1/2)A1=A2E12(1)A2=A3E21(1)A3=A4即即 E1(1/2)E12(1)E21(1)A1=A4令令 D=E1(1/2)E12(1)E21(1)，则有，则有 DA1=A433对于矩阵对于矩阵A，如果存在一个矩阵，如果存在一个矩阵B，使得，使得 AB=BA=I（单位矩阵）（单位矩阵）成立，则称成立，则称A是是可逆矩阵可逆矩阵，并称，并称B是是A的的逆矩阵逆矩阵。记作记作 A-1，即，即A-1=B。当然，也可称。当然，也可称A是是B的的逆矩阵逆矩阵。复习逆矩阵的概念复习逆矩阵的概念346 2 4-2 1 01 -1 3 2 0 1A17 1 7 0 1

26、14 0 5 1 1/2 1A4即即 DA1=A4即用即用 D=E3E2E1左乘左乘现现A4中基变量为中基变量为x1和和x3，P1和和P3构成单位矩阵，如下构成单位矩阵，如下7 1 7 0 1 14 0 5 1 1/2 1A4互换下第互换下第2列与列与第第3列的位置列的位置7 1 0 7 1 14 0 1 5 1/2 1A4类似，类似，A1中也互换第中也互换第2列与第列与第3列的位置，有列的位置，有6 2 -2 4 1 01 -1 2 3 0 1A135A1A4即即 DA1=A4即用即用 D=E3E2E1左乘左乘7 1 0 7 1 14 0 1 5 1/2 16 2 -2 4 1 01 -1

27、2 3 0 17 1 0 7 1 14 0 1 5 1/2 1下面将下面将A4进行分块处理进行分块处理bBN S即即 A4=()b,B,N,S同理，将同理，将A1进行分块处理进行分块处理6 2 -2 4 1 01 -1 2 3 0 1bBNS即即 A1=()b,B,N,S36有有 DA1=A47 1 0 7 1 14 0 1 5 1/2 1bBN S A4=()b,B,N,S6 2 -2 4 1 01 -1 2 3 0 1bBNS A1=()b,B,N,S有有Db=bDB=BDN=NDS=S由于由于 B=I则有则有 DB=I因此因此 D=B-1即即 D是基是基B的逆矩阵的逆矩阵由于由于 S=I

28、 DS=S因此因此 D=S=B-1B-1即即 D()=()b,B,N,Sb,B,N,S377 1 0 7 1 14 0 1 5 1/2 1bBN S6 2 -2 4 1 01 -1 2 3 0 1bBNSDb=bDB=BDN=NDS=SB-1即即 DA1=A4证实证实6 2 -2 4 1 01 -1 2 3 0 1 1 11/2 17 1 0 7 1 14 0 1 5 1/2 1结论：结论：单纯行法的迭代过程单纯行法的迭代过程相当于用相当于用B-1（基基B的逆矩阵的逆矩阵）左乘左乘增广矩阵。增广矩阵。38线性规划问题（线性规划问题（2.9）的矩阵表达式加上松驰变量）的矩阵表达式加上松驰变量 X

29、s 后为：后为：max z=CX0XsAXIXs bX0，Xs0st.（2.11）上式中：上式中：Xs为松弛变量，为松弛变量，Xs=（xn+1，xn+2，xn+m）I为为mm单位矩阵单位矩阵max z=CXAXbX0st.2.1 单纯形法计算的矩阵描述单纯形法计算的矩阵描述 P2939单纯形法计算时，总选取单纯形法计算时，总选取为初始基，对应基变量为初始基，对应基变量Xs初始单纯形表初始单纯形表可表示成如下形式（表可表示成如下形式（表1）项目项目C0非基变量非基变量基变量基变量XXS0 XS bAj C0max z=CX0XsAXIXs bX0，Xs0st.（2.11）?XB?j?设设迭代若干

30、步后迭代若干步后,基变量变为基变量变为XB，XB在在初始单纯形表初始单纯形表中的系数矩阵为中的系数矩阵为B。项目项目C0XXS0 XS bAj C0将将B在在初始单纯形表初始单纯形表中单独列出，而中单独列出，而A中去掉中去掉B的若干列后剩下的列组成的若干列后剩下的列组成N。于是其于是其初始单纯形表初始单纯形表可表示成如下形式（表可表示成如下形式（表2）。项目项目 CB CN 0非基变量非基变量基变量基变量 XB XNXS0 XS b B N j CB CN041当迭代若干步后当迭代若干步后，基变量为基变量为XB时时，该步的单纯形表中由，该步的单纯形表中由XB系系数组成的矩阵数组成的矩阵B转变为

31、单位矩阵转变为单位矩阵。项目项目非基变量非基变量基变量基变量 XB XNXS0 XS b B N j CB CN0 项目项目基变量基变量非基变量非基变量XB XN XS0 XB?I?j 0?迭代结果使得迭代结果使得B IBI0XSI初始单纯形表初始单纯形表中间中间(最终最终)单纯形表单纯形表 项目项目 CB CN 0 XB XNXS0 XS b B N j CB CN0单纯行法的迭代计算实际上是对增广矩阵进行的单纯行法的迭代计算实际上是对增广矩阵进行的初等行变换初等行变换，由线性代数可知，这就相当于由线性代数可知，这就相当于用有限多个用有限多个初等矩阵初等矩阵E1，E2，Ek依次依次左乘左乘增

32、广矩阵增广矩阵。CB XB?I?j 0?EkE2E1bBNI43初等行变换的结果初等行变换的结果使初始单纯形表中的使初始单纯形表中的B变成了单位矩阵变成了单位矩阵I，这表明，这表明 EkE2E1BI，故，故EkE2E1B-1（基基B的逆矩阵的逆矩阵）CB XB?I?j 0?EkE2E1bBNI因此，因此，单纯行法的迭代过程单纯行法的迭代过程相当于用相当于用B-1（基基B的逆矩阵的逆矩阵）左乘左乘增广矩阵。增广矩阵。44 项目项目 CB CN 0 XB XNXS0 XS b B N j CB CN0CB XB j bB-1BB-1NB-1IB-1IB-10CNCBB-1NCBB-1结论：结论：单

33、纯行法的迭代过程单纯行法的迭代过程相当于用相当于用B-1（基基B的逆矩阵的逆矩阵）左乘左乘增广矩阵。增广矩阵。45几个结论几个结论（1）对应初始单纯形表中的单位矩阵对应初始单纯形表中的单位矩阵，迭代后的单纯形表中，迭代后的单纯形表中为为B-1。项目项目 CB CN 0 XB XNXS0 XS b B N j CB CN0CB XB j bB-1INB-1B-10CNCBB-1NCBB-146 cj 2 1 0 0 0 CB基基b x1 x2 x3 x4 x5 0 00 x3x4x515245 0 5 1 0 0 6 2 0 1 0 1 1 0 0 1 2 1 0 0 0 j 0 21x3x1x

34、2 0 0 1 5/4-15/2 1 0 0 1/4-1/2 0 1 0 -1/4 3/2 j 0 0 0 -1/4-1/2 15/27/23/2第第1章中的例章中的例1初始单纯形表中的单位矩初始单纯形表中的单位矩阵阵=（P3,P4,P5）可以知道可以知道B-1为为B-1我们知道在迭代后我们知道在迭代后x3,x1和和x2构成了基变量，故构成了基变量，故初始单初始单纯行表纯行表中中B为：为：B=（P3,P1,P2）1 0 50 6 20 1 1=47B=1 0 50 6 20 1 1B-1=1 5/4 -15/20 1/4 -1/20 -1/4 3/2则则B-1 B=1 5/4 -15/20 1

35、/4 -1/20 -1/4 3/21 0 50 6 20 1 1=1 0 00 1 00 0 1=I（单位矩阵单位矩阵）48（2）初始单纯形表中基变量初始单纯形表中基变量 Xs=b，迭代后的单纯形表中为，迭代后的单纯形表中为 XB=B-1b 项目项目 CB CN 0 XB XNXS0 XS b B N j CB CN0CB XB j bB-1INB-1B-10CNCBB-1NCBB-149（3）初始单纯形表中初始单纯形表中约束系数矩阵约束系数矩阵为（为（A,I）=（B,N,I），），迭代后的表中的约束系数矩阵为（迭代后的表中的约束系数矩阵为（B-1A,B-1I）=（B-1B,B-1N,B-1I

36、）=（I,B-1N,B-1）（4）若若初始单纯形表中变量初始单纯形表中变量 xj 的的系数向量系数向量为为Pj，迭代后为迭代后为Pj，则有，则有 Pj=B-1Pj。50P38 1.8 已知某线性规划问题的初始单纯形表（见表已知某线性规划问题的初始单纯形表（见表1.17）和用）和用单纯形法迭代后得到的表（见表单纯形法迭代后得到的表（见表1.18），试求括弧中未知数），试求括弧中未知数al的值。的值。(a)-1200CBXBbx1x2x3x4x50 x46(b)(c)(d)100 x51-13(e)01j(a)-1200(a)x1(f)(g)2-11/200 x54(h)(i)11/21j0-7(

37、j)(k)(l)表表1.17表表1.1851(a)-1200CBXBbx1x2x3x4x50 x46(b)(c)(d)100 x51-13(e)01j(a)-1200(a)x1(f)(g)2-11/200 x54(h)(i)11/21j0-7(j)(k)(l)表表1.17表表1.18当当基变量变为基变量变为XB=（x1,x5）T时，时，XB在在初始单纯形表初始单纯形表中的系数矩中的系数矩阵为阵为B=(P1,P5)=b 0-1 1（1）对应对应初始单纯形初始单纯形表表中的单位矩阵中的单位矩阵，迭代，迭代后的单纯形表中为后的单纯形表中为B-1，即即B-1=1/2 01/2 1B-1I52(a)-1

38、200CBXBbx1x2x3x4x50 x46(b)(c)(d)100 x51-13(e)01j(a)-1200(a)x1(f)(g)2-11/200 x54(h)(i)11/21j0-7(j)(k)(l)表表1.17表表1.18已知，单纯形法的迭代已知，单纯形法的迭代过程相当于过程相当于用用B-1左乘左乘增广增广矩阵。即矩阵。即B-16 b c d 1 01 -1 3 e 0 11/2 01/2 13 b/2 c/2 d/2 1/2 04 b/2-1 c/2+3 d/2+e 1/2 1f g 2 -1 1/2 04 h i 1 1/2 153(a)-1200CBXBbx1x2x3x4x50

39、x46(b)(c)(d)100 x51-13(e)01j(a)-1200(a)x1(f)(g)2-11/200 x54(h)(i)11/21j0-7(j)(k)(l)表表1.17表表1.183 b/2 c/2 d/2 1/2 04 b/2-1 c/2+3 d/2+e 1/2 1f g 2 -1 1/2 04 h i 1 1/2 1f=3b/2=g，b/2-1=h c/2=2 c=4 c/2+3=i i=5d/2=-1 d=-2 d/2+e=1 e=2345-2254单纯形表的格式：单纯形表的格式：cjc1 c2 cm cj cn CB基基bx1 x2 xm xj xn c1 c2cmx1x2x

40、mb1b2bm1 0 0 a1j a1n0 1 0 a2j a2n 0 0 1 amj amn cjciaijmi=1cnciainmi=10 0 0 j 55(a)-1200CBXBbx1x2x3x4x50 x46(b)(c)(d)100 x51-13(e)01j(a)-1200(a)x1(f)(g)2-11/200 x54(h)(i)11/21j0-7(j)(k)(l)表表1.17表表1.18b/2=g，b/2-1=h g=1 h=0 b=2 a、j、k、l?345-221022=-1(2a+05)即即-7=-12a，a=356（5）用单纯形法求解线性规划问题时，迭代的每一步在得到原用单纯

41、形法求解线性规划问题时，迭代的每一步在得到原问题（问题（2.9）的一个基可行解的同时，其）的一个基可行解的同时，其检验数的相反数检验数的相反数是其对是其对偶问题（偶问题（2.10）的一个基解（不一定是基可行解，因为有可能有）的一个基解（不一定是基可行解，因为有可能有负数存在）。负数存在）。P47 第第6个性质个性质当当B为最优基时，为最优基时，其其检验数的相反数检验数的相反数是其对偶问题（是其对偶问题（2.10）的）的一个基可行解（同时一个基可行解（同时也是其对偶问题的最优解也是其对偶问题的最优解），且此时两个），且此时两个问题的目标函数值相等。问题的目标函数值相等。57第1章例1 原问题与对

42、偶问题的变量及解之间的对应关系。原问题与对偶问题的变量及解之间的对应关系。max z 2x1x2 5x2x3 156x12x2 x4 24 x1 x2 x55 x15 0st.min w15y124y25y3 6y2y3y4 25y12y2y3 y51y1 5 0st.原原问问题题对对偶偶问问题题对偶变量对偶变量y1y2y3x1x258用单纯形法求得两个问题的最终单纯形表如下：用单纯形法求得两个问题的最终单纯形表如下：原问题的原问题的最终单纯形表最终单纯形表原问题变量原问题变量原问题松弛变量原问题松弛变量x1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/2

43、1x23/2010-1/43/2 j000-1/4-1/2对偶问题的剩余变量对偶问题的剩余变量对偶问题变量对偶问题变量y4y5y1 y2y3对偶问题的对偶问题的最终单纯形表最终单纯形表对偶问题变量对偶问题变量对偶问题的剩余变量对偶问题的剩余变量y1y2y3y4y524y21/4-5/410-1/41/45y31/215/2011/2-3/2 j-15/200-7/2-3/2原问题松弛变量原问题松弛变量原问题变量原问题变量x3x4x5 x1 x2z=015/2+27/2+13/2=8.5w=241/4+51/2 =8.5当原问题为最优解时，当原问题为最优解时，检验数的相反数检验数的相反数恰好是对

44、恰好是对偶问题的最优解。偶问题的最优解。且此时两个问题的目标且此时两个问题的目标函数值相等。函数值相等。从对偶问题的角度看，结论从对偶问题的角度看，结论和和都同样成立。即都同样成立。即只需求解其中只需求解其中一个问题，从最优的单纯形表中同一个问题，从最优的单纯形表中同时得到另一个问题的最优解。时得到另一个问题的最优解。592 对偶问题的基本性质对偶问题的基本性质2.1 单纯形法计算的矩阵描述单纯形法计算的矩阵描述2.2 对偶问题的基本性质对偶问题的基本性质602.2 对偶问题的基本性质对偶问题的基本性质（1）对称性：对偶问题的对偶是原问题。）对称性：对偶问题的对偶是原问题。由于这个性质，一对对

45、偶规划中，由于这个性质，一对对偶规划中，“原问题原问题”与与“对偶问对偶问题题”都是相对而言的，即两个问题中，任意一个都可叫做都是相对而言的，即两个问题中，任意一个都可叫做“原问题原问题”，而另一个就是它的，而另一个就是它的“对偶问题对偶问题”。P43 例例261（2）弱对偶性。）弱对偶性。如果如果 xj (j=1,n)是原问题的可行解，是原问题的可行解，yi (i=1,m)是其是其对对偶问题的可行解，则恒有偶问题的可行解，则恒有cj xj j=1nbi yii=1m即即极大化极大化LP问题问题的任何可行解的目标值的任何可行解的目标值 z，不大于不大于极小极小化化DP问题问题的任何可行解的目标

46、值的任何可行解的目标值 w。P64 2.2(c)62（3）无界性：如果原问题（对偶问题）具有无界解，则其）无界性：如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）必定无可行解。对偶问题（原问题）必定无可行解。反证：设原问题有无界解，若对偶问题有可行解，则由反证：设原问题有无界解，若对偶问题有可行解，则由弱对偶性弱对偶性知道知道原问题有界，和已知矛盾原问题有界，和已知矛盾。注意：此性质的逆命题不成立。事实上，注意：此性质的逆命题不成立。事实上，一对对偶的线性规一对对偶的线性规划问题，若其中一个无可行解，则另一个可能可能无可行解，划问题，若其中一个无可行解，则另一个可能可能无可行解，也可能

47、有无界解。也可能有无界解。P64 2.2(b)，2.3 63P64 2.3 已知线性规划问题已知线性规划问题max z x1x2 x1x2x322x1x2x31x13 0st.试应用对偶理论证明上述线性规划问题最优解为无界。试应用对偶理论证明上述线性规划问题最优解为无界。解：解：先写出上述问题的对偶模型，知上述问题具有对称形式。先写出上述问题的对偶模型，知上述问题具有对称形式。min w 2y1y2y12y21 y1 y2 1 y1 y20y120st.64原问题原问题max z x1x2 x1x2x322x1x2x31x13 0st.对偶问题对偶问题min w 2y1y2y12y21 y1

48、y2 1 y1 y20y120 st.由对偶问题的约束条件由对偶问题的约束条件、，可以知道对偶问题无可行解。，可以知道对偶问题无可行解。则根据则根据无界性无界性，可以确定原问题可能为无可行解，或为无界，可以确定原问题可能为无可行解，或为无界 解。解。容易知道容易知道X=（0，0，0）为原问题的可行解，因此可以确定原）为原问题的可行解，因此可以确定原 问题的最优解为无界解。问题的最优解为无界解。65（4）最优性。）最优性。如果如果 xj(j=1,n)是原问题的可行解，是原问题的可行解，yi (i=1,m)是其是其对偶问题的可行解，且有对偶问题的可行解，且有 则则 xj (j=1,n)是原问题的最

49、优解是原问题的最优解，yi (i=1,m)是其对偶问题的最优解。是其对偶问题的最优解。cj xj j=1nbi yii=1m66（5）强对偶性（对偶定理）。）强对偶性（对偶定理）。若原问题有最优解，则其对偶问题也一定具有最优若原问题有最优解，则其对偶问题也一定具有最优解，且具有解，且具有 max z=min w。67根据以上定理，根据以上定理，一对对偶问题解之间的关系一对对偶问题解之间的关系归纳如下：归纳如下：原问题（对偶问题）原问题（对偶问题）对应关系对应关系对偶问题（原问题）对偶问题（原问题）有最优解有最优解有最优解有最优解无界解无界解无可行解无可行解无可行解无可行解无界解无界解P64 2

50、.2（a）如果线性规划的原问题存在可行解，则其对偶问如果线性规划的原问题存在可行解，则其对偶问 题也一定存在可行解。题也一定存在可行解。P64 2.368（6）互补松弛性。）互补松弛性。在线性规划问题的在线性规划问题的最优解最优解中，如果对应某一约束条件的对偶变中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零，也即：严格不等式，则其对应的对偶变量一定为零，也即：aij xjj=1n若若 yi0，则有，则有bi，即，即 xsi0（松弛变量为（松弛变量为0）若若ai