运筹学第5讲 线性规划的对偶理论和灵敏度分析1

1、运 筹 学（Operations Research）上 海 海 事 大 学 20131009任课教师：邓 伟邮 箱：单纯形法的矩阵表示单纯形法的矩阵表示考虑线性规划问题(LP) 为松弛变量， ， 为m阶单位矩阵。max0max00,00SSSSzCXXzCXXAXIXbAXbXXX SX12(,)TSnnn mXxxxI 单纯形法计算时，总选取 为初始基，对应的基变量为 。,BBXXSX设迭代若干步后，基变量为 在初始单纯形表中的系数矩阵为B。将B在初始单纯形表中单独列出，而A中去掉B的若干列后剩下的列组成的矩阵为N。A=（B，N）。I单纯形法的矩阵表示单纯形法的矩阵表示初始单纯形表其中，检验

2、数1,1,2, .mjjjjiijiczccajn（这里 显然成立。1,1, .mjjjjiijiczcc ajmn当 时， ）1,2,jm10.mjjjjiijiczcc a单纯形法的矩阵表示单纯形法的矩阵表示 当迭代若干步后，基变量为XB，则该步的单纯形表中由XB系数组成的矩阵为I，又因为单纯形法的迭代是对于约束增广矩阵进行的初等行变换，对应XS的系数矩阵在新表中为B-1. 故当基变量为XB时，新的单纯形表为 单纯形法的矩阵表示单纯形法的矩阵表示由上述表格可以看出，当迭代后基变量为XB时，其在初始单纯形表中的系数矩阵为B，则有：(1) 对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B

3、-1.(2) 初始单纯形表中基变量XS=b，迭代后表中XB=B-1b。(3) 初始单纯形表中约束系数矩阵为（A,I）=（B,N,I）,迭代后的表中约束系数矩阵为（B-1A，B-1I）=B-1(B，N，I)=(I，B-1N，B-1). 单纯形法的矩阵表示单纯形法的矩阵表示(4) 当初始矩阵中变量xj的系数向量为Pj时，迭代后为Pj ,则有Pj =B-1Pj.(5) 当B为最优基是，在表中应有 CN-CBB-1N 0 -CBB-1 0注：1.因为基变量的检验数XB可写成CB-B*I=0 C-CBB-1A 0 -CBB-1 0 2.CBB-1称为单纯形乘子。 单纯形法的矩阵表示单纯形法的矩阵表示(6

4、) 最小比值规则的矩阵表示形式11111()()min|()0()()iijiijijiB bB bB PB PB P其中(B-1b)i表示（B-1b）中的第i个元素，(B-1Pj)i 表示向量（B-1Pj）中的第i个元素。 单纯形法的矩阵表示单纯形法的矩阵表示2.若迭代若干步后，在基变量中还存在松弛变量，记其中B，N，S分别表示对应基变量，非基变量，松弛变量的系数矩阵。1111121222,;,(,).BNSBNSNSSSSXXXNBXXXANCNCCXXXSN12112212max,0BBNNSSBNBNSBNzC XCXCXBXNXBXN XS XbXX将基变量用非基变量表示代入目标函数

5、中12111112112211111222()()()BNSNNSSBNBNSBSzCB bB N XB S XCXCXC B bCC B N XCC B SX即规划形式为： 单纯形法的矩阵表示单纯形法的矩阵表示其对应的初始单纯形表为即约束和目标为1211211111111()BNSNBNBSBXB N XB XB bzCC B N XC B XC B b 约束目标矩阵表示为1211111111010BNNBBBSzXIB NBB bXCC B NC BC B bX 单纯形法的矩阵表示单纯形法的矩阵表示1.从上面的单纯形表可以看出，基变量的检验数为0，非基变量的检验数为CN1-CBB-1N1和

6、-CBB-1。由单纯形法的最优性判别定理可知： 当 CN1-CBB-1N1 0 -CBB-1 0时，当前解为最优解。注：2.迭代后的单纯形计算表中，各部分的数字都用B-1乘来计算，因此，如何计算B-1是单纯形方法计算复杂性的主要体现。 对偶理论对偶理论 线性规划有一个有趣的特性，就是对于一个求极大的规划都存在一个与其匹配的求极小的规划，并且这一对规划的解之间还存在密切的关系。线性规划的这个特性称为对偶性，者不仅仅是数学上具有的理论问题，也是实际问题在线性规划中的必然反映。 在这一节里，将从经济意义上研究线性规划的对偶问题，通过对对偶问题的研究，从不同角度对线性规划问题进行分析，从而利用有限的数

7、据，得出更广泛的结果，间接地获得更多的有用信息，为企业经营决策提供更多的科学依据。另外，还将利用对偶性质给出求解线性规划的新方法对偶单纯形方法。 对偶理论对偶理论 生产计划问题例5.1 某工厂计划在下一个生产周期生产3种产品A1、A2、A3，这些产品都要在甲、乙、丙、丁4种设备上加工，根据设备性能和以往的生产情况，知道产品在设备上的加工工时、各种设备的最大工时限制，以及每种产品的单位利润（单位：千元），如下表所示。问如何制定生产计划，才能使工厂得到最大利润？ 对偶理论对偶理论解 设 分别为产品A1、A2、A3的产量，构造此问题的线性规划模型为123,xxx1231231231312123max

8、81022370422803152250,0zxxxxxxxxxxxxxx x x增加松弛变量 ，化为标准型求解，得到最优单纯形表如下：4567,x x x x 对偶理论对偶理论最优方案是生产产品A2和A3，产量分别为25件和15件，企业的最大利润为280千元。 对偶理论对偶理论现从另一角度讨论这一问题。假设工厂考虑不安排生产，而准备将所有设备出租，收取租费，于是，需要为每种设备的台时进行估价。设y1,y2,y3,y4分别表示甲、乙、丙、丁4种设备的台时估价。由题设的表格可以看出，生产一件产品A1，需用各设备台时分别为2、4、3、2，如果将2、4、3、2不用于生产产品A1，而是用于出租，那么将

9、得到租费当然，工厂为了不至于折本，在为设备定价时，应保证用于生产产品A1的各设备台时得到的租费，不能低于产品A1的单位利润8(否则不如自己组织生产)，即 2y1+4y2+3y3+2y42y1+4y2+3y3+2y48 对偶理论对偶理论按照同样分析，用于生产产品A2的各设备台时1、2、0、2所得的租费，不能低于产品A2的单位利润10，即企业拥有的总时数为70,80,15,50，如果将这些台时都用于出租，企业的总收入为 y1+2y2+ +2y410同理，还有 3y1+2y2+y3 2另外，价格显然不能为负值，所以yi0，i=1,2,3,4. f= 70y1+80y2+15y3+50y4 。 对偶理

10、论对偶理论企业为了能够得到租用设备的用户，使出租设备的计划成交，在价格满足上述约束的条件下，应将设备价格定的尽可能低，因此取f的最小值，综合上述分析，可得到一个与原问题相对应的线性规划，即Min f = 70y1+80y2+15y3+50y4s.t. 2y1+4y2+3y3+2y48 y1+2y2+ +2y4 10 3y1+2y2+y3 2 yi0，i=1,2,3,4. 称后一个规划为前一个规划的对偶规划，反之，也称前一个规划为后一个规划的对偶规划。对后一个规划，可得到最优解 y1=2/3, y2=y3=0,y4=14/3. 对偶理论对偶理论因此，甲、乙、丙、丁4种设备的台时估价分别为2/3,

11、0,0,14/3(单位：千元)。从上面的分析可知，新得到的对偶规划是一个很重要的线性规划，它对问题的分析又深入了一步，对减少管理工作的盲目性，提供了更多的科学依据。原规划与对偶规划是互相对应的，它们从不同的角度对企业的经营管理问题进行分析研究。它们之间存在着密切的关系，这些关系将在下面体现出来。 对偶理论对偶理论上面从一个生产计划问题引出了对设备的估价问题，得到了对偶规划，实际上对于一般的线性规划模型可以直接给出其对偶规划模型，并不需要像上面那样经过一番讨论，对偶规划的形式分为对称形式和非对称形式。1.对称形式的对偶规划一般称具有下面形式的一对规划是对称形式的对偶规划其中， 对偶理论对偶理论事

12、实上，一对对称形式的对偶规划具有下面的对应关系：(1) 若一个模型的目标为求极大，约束为小于等于的不等式，则它的对偶规划为目标求极小，约束为大于等于的不等式。即“max，”和“min，”相对应。(2) 从约束系数矩阵来看：一个模型为A，则另一个模型为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3) 从数据b，C的位置看：在两个规划模型中，b与C的位置对换。(4) 两个规划模型中的变量皆非负。 对偶理论对偶理论mincccbaaaybaaaybaaayxxxyxmnmmnmmmnnnijmaxzmaxzmin21212222212111211121对偶关系原关系根据

13、这些关系，可以由规划（P）直接写出规划（D），也可以由规划（D）直接写出规划（P）。 对偶理论对偶理论解 先将原规划改写成矩阵表示形式，例5.2 写出下面线性规划的对偶规划模型1234123412341234max3752256403250232200,1,2,3,4jzxxxxxxxxxxxxxxxxxj1234max(3,75,2,1)xxzxx1234256140321150123220 xxxx 对偶理论对偶理论即对偶规划模型为按照对称形式的对偶关系，写出对偶模型为123min(40,50,20)yfyy12323135227561321121yyy123123123123123min

14、40502023352275632210,1,2,3jfyyyyyyyyyyyyyyyyj 对偶理论对偶理论2.非对称形式的对偶规划 一般称不具有对称形式的一对规划为非对称形式的对偶规划。 对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。将模型统一为“max，”或“min，”的形式，对于其中的等式约束按下面方法处理： 若原规划的某个约束条件为等式约束，则在对偶规划中 与此约束对应的那个变量没有非负限制； 若原规划的某个变量没有非负限制，则在对偶规划中与 此变量对应的那个约束为等式约束。 对偶理论对偶理论下面举例说明上面的关系。设原规划的第1个约束为等式约束，这个等式与下面两个不

15、等式等价。11 11111 111nnnna xa xba xa xb这样，原规划模型可以写成1 111 11111 1111 1max0,1,2,nnnnnnmmnnmjzc xc xa xa xba xa xba xaxbxjn 对偶理论对偶理论此时已经为对称形式，直接写出对偶规划。设原规划的第1个约束为等式约束，这个等式与下面两个不等式等价。11112211111111121121221111112min,0mmmmmmnnmnmnmfb yb yb yb ya ya ya yca ya yayca ya yaycy y yy令 ，可得到111yyy112211111121221121m

16、in,0,mmmmmmnmnmnmfb yb yb ya ya yca yayca yaycyyy没有非负限制 对偶理论对偶理论例5.3 写出下面线性规划的对偶规划模型。123412341341234123max57322527260224305100,zxxxxxxxxxxxxxxxxxx ，没有非负限制解 先将约束条件变形为“”形式12341234134123441234max57322527260224301050,zxxxxxxxxxxxxxxxxxxxx，没有非负限制 对偶理论对偶理论再根据非对称形式的对应关系，直接写出对偶规划1234512313123124523451min256

17、030105221321274527,0,fyyyyyyyyyyyyyyyyyyyyyy 没有非负限制 对偶理论对偶理论考虑一对对称形式的对偶规划问题min()0TTTwb YA YCDY对偶问题的基本性质：max( )0zCXAXbPX(1)对称性 对偶问题的对偶是原问题。证明： 考虑(D)的对偶，首先将(D)改写成max()0TTTwb YA YCDY 对偶理论对偶理论根据对称形模型的对偶， 的对偶为即也即即为原规划(P)。()Dmin()()()()0TTTTTTzCSASbPS min()0zCSASbPS max()0zCSASbPS 对偶理论对偶理论(2)弱对偶性 若 与 为(P)

18、与(D)的可行解，则 XYTCXb Y推论1 最优性 设X0和Y0分别为(P)与(D)的可行解，当 CX0=bTY0 时，X0,Y0分别是两个问题的最优解。推论2 若(P)有可行解，则(P)有最优解的充要条件为(D) 有可行解。推论3 若(D)有可行解，则(D)有最优解的充要条件为(P) 有可行解。 对偶理论对偶理论例5.4 试用对偶理论判断下列线性规划是否有最优解.12123123123max221,0Zxxxxxxxxx xx解：此规划问题存在可行解：(0,0,0)TX 对偶理论对偶理论其对偶规划为对偶规划无可行解，因此原规划无最优解。1212121212min22110,0fyyyyyy

19、yyyy 对偶理论对偶理论例5.5 用对偶性质判断下面线性规划是否存在最优解。解: 此规划存在可行解1212121212max322332143,0Zxxxxxxxxx x(0,1)TX 对偶理论对偶理论其对偶规划为对偶规划也存在可行解Y0=(0,1,0)T，因此，原规划也存在最优解。123123123123min414333222,0fyyyyyyyyyy yy注: 若原规划无最优解(无界解)，则其对偶问题无可行解。 对偶理论对偶理论(3)强对偶性(对偶定理) 若(P)有最优解，则(D)也有最优解，反之亦然，并且两者的目标函数值相等。证明： 考虑规划问题(P)的标准形( )，设 ( ) 的最

20、优基为B，现证明(D)也有最优解。PP max( )0zCXAXbPX由单纯形法知10BCC B A11,( , )( ,0)BBC B ACC BA IC110BBC B ACC B因此 对偶理论对偶理论令 ，则有因此 为(D)的可行解，其中(D)为：0TTTTY ACA YCY，即1TBYC BYmin()0TTTfb YA YCDY另一方面有1100BTBNXB bY bC B bCXCCX 对偶理论对偶理论X0为原规划(P)的最优解，故 为(D)的最优解。类似证明：若(D)有最优解，则(P)也有最优解。注：对偶定理 若(P)与(D)均有可行解，则(P)与(D)均有最优解，且最优解的目标

21、函数值相等。(4)互补松弛性 若 分别为(P)与(D)的可行解，则对于 松弛变量 ， 当且仅当 为最优解。,X Y,SSXY0,0TTSSX YY X,X Y 对偶理论对偶理论证明：设原规划的标准形为对偶规划为 引入松弛变量变形为max(),0SSzCXAXXbPX Xmin()0TTTwb YA YCDYmin(),0TTTSSwb YA YYCDY Y 对偶理论对偶理论将(D)代入(P)的目标函数中：()TTTTSSzA YYXY AXY X将(P)代入(D)的目标函数中：()TTTTSSwAXXYX A YX Y若 ，则:0,0TTSSX YY XTTTTTTTSSzY AXY XwX A YX YX A Y因此 是最优解。,X Y若 分别为(P)和(D)的最优解，则由对偶定理,X YTTCXY bY AX故0TTSSX YY X 对偶理论对偶理论注: 对偶规划的最优解为(P)的松弛变量对应的检验数的相反数，(P)的检验数对应(D)的一个基本解，对应关系如下:证明: 设(B)为(P)中的一个可行基A=(B,N)max,