线性规划4-对偶单纯形.ppt

对偶的线性规划问题的解原始规划的最优性对偶规划的可行性定理6.4设B是问题的一个基矩阵,对应的基解满足最优性条件则对偶线性规划问题有可行解在上述条件下,(LP)的基解的目标函数值等于(DP)的解的目标函数值.如果xB是可行解,则显然是(LP)的最优解.此时对应的y是(DP)的最优解.对偶的线性规划问题的解定理6.5若原始线性规划问题与对偶线性规划问题之一有最优解,则另一个也有最优解,并且它们目标函数的最优值相等.证明:考虑到对合性,只需选取两个规划中的任一个证明.设有最优解x0,且其为基可行解再设基矩阵为B,x0为最优解,判别数非负,有y0可行,且y0是对偶规划最优解.二、对偶性质定理6.6强对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。推论4：（LP）与（DP）要么两者都有最优解，要么都无最优解。两个互为对偶的线性规划的解的情况(3)一个有可行解,无最优解(目标函数无界),则另一个无可行解.两个都有可行解,两个都有最优解,且最优值相等.(2)两个都无最优解.(4)一个有可行解，另一个无可行解，则可行的一个目标函数无界.判断下列结论是否正确？3）互为对偶问题，或者同时都有最优解，或者同时都无最优解.1）任何线性规划都存在一个对应的对偶线性规划.2）原问题第i个约束是“≤”约束，则对偶变量yi≥0.4）对偶问题有可行解，则原问题也有可行解.5）原问题有多重解，对偶问题也有多重解.6）对偶问题有可行解，原问题无可行解，则对偶问题具有无界解.√×√××√7）原问题无最优解，则对偶问题无可行解.8）对偶问题不可行，原问题可能有无界解.9）原问题与对偶问题都可行，则都有最优解.10）原问题具有无界解，则对偶问题不可行.11）对偶问题具有无界解，则原问题无最优解.12）若X*、Y*是原问题与对偶问题的最优解，则X*=Y*.×√√√√×分别求解下列2个互为对偶关系的线性规划问题分别用单纯形法求解上述2个规划问题，得到最终单纯形表如下表：0102二、对偶性质对偶性质原问题最优表对偶问题最优表对偶性质原问题与其对偶问题的变量与解的对应关系：在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。对偶定理定理6.7互补松弛性：设X0和Y0分别是(LP)问题和(DP)问题的可行解，则它们分别是最优解的充要条件是：其中：Xs为松弛变量、Ys为剩余变量.互补松弛条件证：由定理所设，可知有分别以Y0T左乘(1)式，以X0右乘(2)式后，两式相减，即得由可行性及最优性条件，可知有反之亦然。证毕。定理6.7*互补松弛性：设X0和Y0分别是(LP)问题和(DP)问题的可行解，则它们分别是最优解的充要条件是：互补松弛条件可写为：定理6.7的应用：该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y*求X*或已知X*求Y*由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：若Y*≠0，则Xs必为0；若X*≠0，则Ys必为0利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。对偶性质标准化3124例2.4已知线性规划的最优解是X*=(6,2,0)T,求其对偶问题的最优解Y*。解：写出原问题的对偶问题，即对偶性质01设对偶问题最优解为Y*＝(y1，y2),由互补松弛性定理可知，X*和Y*满足：02即：03因为x1≠0，x2≠0，所以对偶问题的第一、二个约束的松弛变量等于零，即y3＝0，y4＝0，带入方程中：04解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为：Y*=(1,1)，最优值w=26。对偶性质对偶性质例2.5已知线性规划的对偶问题的最优解为Y*=(0,-2)，求原问题的最优解。解:对偶问题是标准化010304020506设对偶问题最优解为X*＝(x1，x2，x3)T,由互补松弛性定理可知，X*和Y*满足：将Y*带入由方程可知，y3＝y5＝0，y4＝1。∵y2=-2≠0∴x5＝0又∵y4=1≠0∴x2＝0将x2，x5分别带入原问题约束方程中，得：解方程组得：x1=-5,x3=-1,所以原问题的最优解为X*=(-5,0,-1)，最优值z=-12对偶性质用单纯形方法求解线性规划时,x的可行性是满足的,但是最优性条件不