线性规划对偶问题.ppt

原规划的检验数对应于对偶规划的一个解；对偶规划的检验数对应于原规划的一个解。特别地，若原问题的最优基为B，则其对偶问题的最优解为Y*=CBTB-1互补松驰定理：设原问题和对偶问题的标准型分别为：01若X*，Y*分别是原问题和对偶问题的可行解，那么Y*TXs=0和YsTX*=0当且仅当X*、Y*为最优解。02证明：原问题对偶问题MaxZ=CXMinW=YbAX+Xs=bYA-Ys=CX,Xs?0Y,Ys?0Z=CX=(YA-Ys)X=YAX-YsXW=Yb=Y(AX+Xs)=YAX+YXs充分性：P58必要性：P58该定理的隐含结论：当一对对偶规划达到最优时，若一个问题的某个变量为正数，则相应的另一个问题的约束必取等式；或者一个问题中的约束条件取不等式，则相应的另一个问题的变量必为零。理由：由于X*,Y*为最优，故YsTX*=0，Y*TXs=0。如果Xi*0，所以有Ysi=0，也就有对偶问题相应的约束条件为等式约束（因为X,Y都是非负的）；如果Y*j0，所以有Xsj=0，也就有对偶问题相应的约束条件为等式约束。设原问题是：maxZ=CX;AX+Xs=b;X,Xs?0对偶问题是：minW=Yb;YA-Ys=C;Y,Ys?0则原问题单纯形表的检验数行对应于其对偶问题的一个基解，其对应关系为：XBXNXS0CN-CBB-1N-CBB-1YS1YS2-Y已知线性规划问题的最优解为X*=(0,0,4,4)T，最优值Z*＝28。试用互补松驰性找出其对偶问题的最优解。解：写出该问题的对偶问题：MinW=20y1+20y2S.t.y1+2y2?12y1+y2?22y1+3y2?33y1+2y2?4yi?0,i=1,2,3,4根据互补松驰性，可得：x3*=40,则2y1+3y2=3x4*=40,则3y1+2y2=4解得：y1=6/5,y2=1/5满足对偶问题的前两个约束条件，所以它是对偶问题的可行解。其对应的目标函数W*=28=Z*，从而y1=6/5,y2=1/5为对偶问题的最优解。已知线性规划问题试用对偶理论证明上述线性规划问题无最优解。证明：首先看到该问题存在可行解，如X=(0,0,0)，而上述问题的对偶问题为：由第一个约束条件可知对偶问题无可行解，因原问题有可行解，故无最优解（若原问题有最优解，则对偶问题也有最优解）。对偶单纯形法对偶单纯形法是运用对偶原理求解原问题的一种方法，而不是求解对偶问题的单纯形法。正则解：检验数全部为非负的基本解，叫正则解。正则解一般不可行。如果可行，即为最优解。原理：从一个正则解出发，用单纯形法进行迭代，迭代过程中始终保持解的正则性不变，使解的不可行性逐渐消失，所得第一个可行解即为最优解。单纯形法在整个迭代的过程中，始终保持原问题的可行性，即常数列非负，而检验数由有负分量逐步变为全部非负，即同时得到原问题和对偶问题的最优解。对偶单纯形法在整个迭代过程中，始终保持对偶问题的可行性，即全部检验数非负，而常数列由有负分量逐步变为全部非负，即同时得到原问题和对偶问题的最优解。其与单纯形法的区别在于：单纯形法对偶单纯形法从一个初始基可行解出发从一个初始正则解出发检验数可正可负保持右边常数非负（即解的可行性）右边常数可正可负保持检验数非负（即解的正则性）检验数均非负，则为最优解常数均非负，则为最优解对偶单纯形法的步骤1确定换出变量：在负的基变量中选择最小的基变量为换出变量；2确定换入变量：用换出变量的那一行具有负值的系数分别去除同列的检验数，取绝对值最小者所对应的变量为换入变量；3进行迭代变换（分别进行行、列变换）；4进行最优性检验：如果所得的基本解都是非负的，则此解即为最优解，反之继续迭代，直至所有基变量为非负的数值为止。第2章对偶理论线性规划续知识点掌握对偶规划的理论和性质，如可逆性、弱对偶性、对偶定理、互补松驰定理等；掌握对偶单纯形法；了解对偶问题的特点，熟悉互为对偶的问题之间的关系；主要内容一、对偶问题的基本概念二、对称的对偶线性规划三、对偶的基本性质四、对偶单纯形法载重汽车大轿车资源限制钢材劳动力座椅22.5025116002500400利润