运筹学复件 02对偶理论

《运筹学复件 02对偶理论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章对偶理论与灵敏度分析2.1单纯形法的矩阵描述所谓单纯形法的矩阵描述就是用矩阵来描述单纯形法，这样可有助于对对偶问题进行分析。一、标准型线性规划问题单纯形法的矩阵描述设线性规划问题为：Maxz=C1X1+C2X2+……+CnXna11X1+a12X2……+a1nXn=b1a21X1+a22X2+……+a2nXn=b2……am1X1+am2X2+……+amnXn=bmX1，X2，……，Xn≥0在A中任取m个线性无关的列向量组成一个可行基，B—基矩阵，N—非基向量组成的矩阵；XB—基变量组成的列向量

2、，XN—非基变量组成的列向量；CB—基变量价值系数组成的行向量，CN—非基变量价值系数组成的行向量；则A=（B，N），C=（CB，CN），标准形式模型可表示为即标准形式的LP问题变换前模型变换后模型所对应的单纯形表为：CBCNCBXBbXBXNCBXBB-1bIB-1N-Z-CBB-1b0CN-CBB-1N检验数的推广！基变量检验数B=0=CB-CBB-1B，非基变量检验数N=CN-CBB-1N所有变量的检验数可以表示为②任意一个变量检验数的表示方法二、存在松弛变量模型单纯形表的矩阵描述设线性规

3、划问题为：引入松弛变量的模型为：在下面的矩阵描述中，松弛变量独立表示，不归入非基变量。以此模型构造单纯形表如下：CBCN0XBbXBXNXSXBB-1bIB-1NB-1-Z-CBB-1b0CN-CBB-1N-CBB-1表中最关键的就是B-1所在的位置，因此要特别注意松弛变量在矩阵描述的单纯形表中的作用！每张表中,松弛变量对应的系数矩阵就是表中基的逆矩阵例下面的单纯形表中X1X2X3X4X5X62-11000CBXBbX4X1X202-11-1-201/21/20-1/2-1/2X4X5X660102

4、0000111001-1201011-10012-11000…………101550100011½-3/2000-3/2-1/2-3/2B=（P4，P1，P2）13101-1011=B-1=1-1-201/21/20-1/2-1/2X1X2X3X4X523000CBXBbX3X4X500081612140204100010001j230004-3X3X4X2003301001/4164001021010-1/2j2000-3/424-X1X4X2203301001/4800-41221010-1/

5、2j00-201/4B1=（P3,P4,P5）=IB2=（P3,P4,P2）B2-1=10-1/2010001/4B-1=100010001102010004=思考：对照某一单纯形表找出B1-1，B2-1，B3–1用矩阵描述的规则表达式=min（B-1b）i（B-1Pk）i（B-1Pk）i＞0（B-1b）i表示B-1b的第i个分量（B-1Pk）i表示B-1Pk的第i个分量B-1Pk表示进基向量=（B-1b）L（B-1Pk）L例已知LP问题用单纯形法计算的初始表和最终表，请将表中空白处的数字填上

6、计算公式b′=B-1bPj′=B-1PjN=CN-CBB-1Nj=Cj-CBB-1PjX1X2X3X4X5X62-11000CBXBbX4X1X202-11-1-201/21/20-1/2-1/2X4X5X6601020000111001-1201011-10012-11000…………X1X2X3X4X5X62-11000CBXBbX4X1X202-11-1-201/21/20-1/2-1/2X4X5X6601020000111001-1201011-10012-11000…………1015501

7、00011½-3/2000S=（4，5，6）=-CBB-1=（0，-3/2，-1/2）-3/2-1/23=C3-CBB-1P3=-3/2-3/2改进单纯形法1.只需存贮原始数据A，b，C，每步需知B-12.每步必须计算的数据①单纯形因子和检验数Y=CBB-1N=CN-CBB-1N②B为基时进基向量Pm+k′=B-1Pm+k=（a1m+k′，a2m+k′，…amm+k′）T③基变量XB=B-1b=（b1′，b2′，…bm′）T通过由最小比值法则得主元素aLm+k，主元素已知，离基变量确定，

8、新基B1确定，返回2改进单纯形法步骤对MaxZ=CX，AX=b，X≥0，A=（P1，P2…Pn）1.已有初始可行基B，求B-1，初始解XB=B-1b=（b1′，b2′，…bm′）T2.计算N=CN-CBB-1N，若所有N≤0，则计算Zo=CBB-1b，停，否则取m+k=min{j∣j＞0}，Xm+k进基3.计算Pm+k′=B-1Pm+k=(a1m+k′,a2m+k′,…amm+k′)T，若Pm+k′≤0，则为无界解，停止4.最小比值法=minbi′aim