运筹学(第四版)清华大学出版社《运筹学》教材编写组-第3章

清华大学出版社1二线性规划与目标规划第1章线性规划与单纯形法第2章对偶理论与灵敏度分析第3章运输问题第4章目标规划清华大学出版社2第3章对偶理论和灵敏度分析第1节单纯形法的矩阵描述第2节改进单纯形法第3节对偶问题的提出第4节线性规划的对偶理论第5节对偶问题的经济解释——影子价格第6节对偶单纯形法第7节灵敏度分析第8节*参数线性规划清华大学出版社3第1节单纯形法的矩阵描述设线性规划问题可以用如下矩阵形式表示：目标函数maxz=CX约束条件AX≤b非负条件X≥0清华大学出版社4第1节单纯形法的矩阵描述将该线性规划问题的约束条件加入松弛变量后，得到标准型：maxz=CX+0XsAX+IXs=bX，Xs≥0其中I是m×m单位矩阵。清华大学出版社5第1节单纯形法的矩阵描述若以Xs为基变量，并标记成XB，可将系数矩阵（A，I）分为（B，N）两块。B是基变量的系数矩阵，N是非基变量的系数矩阵。并同时将决策变量也分为两部分：相应地可将目标函数系数C分为两部分：CB和CN，分别对应于基变量XB和非基变量XN，并且记作C=（CB,CN）NBXXX清华大学出版社6第1节单纯形法的矩阵描述若经过迭代运算后，可表示为：相应有;XXXXXXSNNSBB2111非基变量：变量可包含原基变量和松弛基变量非基变量基变量松弛变量：其中系数矩阵2121SSSXXX;SNN;NBA清华大学出版社7第1节单纯形法的矩阵描述线性规划问题可表示为：)(X,)(bXSXNBXNX)(XCXCXCXCXNSNBNSSNNBBNNB230X22BX12CzmaxB21BB212211非负条件约束条件目标函数清华大学出版社8第1节单纯形法的矩阵描述将（2-2）式移项及整理后得到：SBSNBNBsNBSNBX)IBCC(X)NBCC(bBCz;XSBXNBbBX;XSXNbBX111121111212112121目标函数：清华大学出版社9第1节单纯形法的矩阵描述令非基变量=0，由上式得到：bB;bBX)(1B11Cz0目标函数的值基可行解清华大学出版社10第1节单纯形法的矩阵描述（1）非基变量的系数表示为：1B1Bj11C-C-C21c1BAB)n,,,j(z)NBCC(jBN与检验数也可表示为：对应已用的检验数符号清华大学出版社11第1节单纯形法的矩阵描述（2）θ规则表示为：RHS值表示选用0的分量换入变量的系数向量ijiijiji)PB()bB()PB()PB()bB(min111110清华大学出版社12第1节单纯形法的矩阵描述（3）单纯形表与矩阵表示的关系)(bBCbBXXXzBCNBCCBNBBNNBBBN7201101111111121清华大学出版社13第1节单纯形法的矩阵描述单纯形表中的数据基变量非基变量等式右边系数矩阵检验数011BBXBbBCBCNBCCbBBNBRHSXXBBBNsN111111111清华大学出版社14小结1）掌握矩阵的运算；2）理解基矩阵的作用；3）了解矩阵运算与单纯表的关系。清华大学出版社15第2节改进单纯形法求解线性规划问题的关键是计算B-1，以下介绍一种比较简便的计算B-1的方法。清华大学出版社16第2节改进单纯形法设mn系数矩阵为A，求其逆矩阵时，可先从第1列开始。mmmmmmaaaaaaaaaA212222111211清华大学出版社17第2节改进单纯形法以a11为主元素,进行变换)(a/aa/aa/aaaPmm111111121111112111主元素清华大学出版社18第2节改进单纯形法然后构造含有（1）列，而其他列都是单位列的矩阵1/1/00/11111121111aaaaaEm清华大学出版社19第2节改进单纯形法可得到)(mm)(m)(m)()(m)(aaaaaaAE;PE11212122111121110010011121122211211121aaaaaaaa清华大学出版社20第2节改进单纯形法)(a122而后以第2列的为主元素，进行变换)(a/aa/a/aP)()(m)()()()(2112212122122112212清华大学出版社21第2节改进单纯形法1001001122121221221122)()(m)()()(a/aa/a/aE然后构造含有（2）列，而其他列都是单位列的矩阵可得到)(mm)(m)(m)(m)()(aaaaaaAEE222212322321312001001清华大学出版社22第2节改进单纯形法重复以上的步骤，直到获得112111AAEEEm可见En…E2E1=A-1。用这方法可以求得单纯形法的基矩阵B的逆矩阵B-1清华大学出版社23第2节改进单纯形法以例1为例进行计算。1241648200032524132154321xxxxxxxxxxxxzmax清华大学出版社24第2节改进单纯形法第1步：确定初始基，初始基变量;确定换入，换出变量（1）确定初始基和初始基变量：（2）计算非基变量的检验数，确定换入变量。54354300111xxxX;P,P,PBB换入变量对应注意：212100103240204110001000100032000x,x,),,(,)P,PN(NBCCBNN清华大学出版社25第2节改进单纯形法(3)确定换出变量510102102min0812min,,324iiiBbBPBPx对应表示选择0的元素清华大学出版社26第2节改进单纯形法（4）基变换计算将新的基单位矩阵。计算：243P,P,P410121141021402112//E//P；构造主元素4101211111410121110111////BEB清华大学出版社27第2节改进单纯形法（5）计算非基变量的系数矩阵（6）计算RHS410214114141012111411111////NBN316212168410121111//bB清华大学出版社28第2节改进单纯形法第1步计算结束后的结果),(),,,(C,CC;x,xX;x,x,xX;P,P,PBNBTNTB023001111512432431价值系数非基变量基变量基清华大学出版社29第2节改进单纯形法计算非基变量的检验数，确定换入变量换入变量对应注意：515111114321000414100010210130002111x,x/,//),,(,)P,PN(NBCCBNN清华大学出版社30第2节改进单纯形法确定换出变量311111111min0216min,,214iiiBbBPBPx对应清华大学出版社31第2节改进单纯形法由此得到新的基410021421014100010210110001400110001400104104111212212412////BEBEPP,P,PB2主元素清华大学出版社32第2节改进单纯形法计算RHS382121684100214210112//bB清华大学出版社33第2节改进单纯形法第2步计算结束后的结果),(),,,(C,CC;x,xX;x,x,xX;P,P,PBNBTNTB003022222532412412价值系数非基变量基变量基清华大学出版社34第2节改进单纯形法第3步：计算非基变量（x3,x5）的检验数换入变量正检验数对应注意：535322124121000014100314210130200222x,x/,//),,(,)P,PN(NBCCBNN清华大学出版社35第2节改进单纯形法确定换出变量412125125min083min,,421/4iiiBbBPBPx对应清华大学出版社36第2节改进单纯形法新的基主元素的系数向量是换入变量4/122/11004/1002142/101;,,51252513PBxPPPB清华大学出版社37第2节改进单纯形法计算B的逆矩阵18100210041181214133///E///构造08121121204104100214210118100210041112313/////////BEB清华大学出版社38第2节改进单纯形法计算非基变量的检验数已无正检验数注意：8123010001081211212041030200433313333/,/////),,(,P,PNNBCCBNN清华大学出版社39第2节改进单纯形法得到最优解：1*153201/40821/21161/21/8012442xXxBbx1424430213,,bBCzB*目标函数的最优值为：P873.1的（1)作业清华大学出版社41第3节对偶问题的提出什么是对偶？对同一事物（或问题），从不同的角度（或立场）提出相对的两种不同的表述。例如：在平面内，矩形的面积与其周长之间的关系，有两种不同的表述方法。周长一定，面积最大的矩形是正方形。面积一定，周长最短的矩形是正方形。这种表述有利于加深对事物的认识和理解。线性规划问题也有对偶关系。清华大学出版社42第3节对偶问题的提出对第1章例1从对偶的角度进行表述。假设该工厂的决策者决定不生产产品Ⅰ、Ⅱ，而将其所有资源出租或外售。这时工厂的决策者就要考虑给每种资源如何定价的问题。设用y1，y2，y3分别表示出租单位设备台时的租金和出让单位原材料A，B的附加额。他在做定价决策时，做如下比较：若用1个单位设备台时和4个单位原材料A可以生产一件产品Ⅰ，可获利2元，那么生产每件产品Ⅰ的设备台时和原材料出租或出让的所有收入应