对偶单纯性法

第四节、对偶单纯形法一、思想考虑问题(LP):TTTCAubumaxmin0TfCXAXbX和问题(D):00011()()0TTTBNTTBTTBxxxCCBAuCB若为原线性规划的基最优解，那么检验数令可知：1.对偶问题的可行解。说明是uCAuTT2.101是对偶问题的最优解。由最优性定理，ubBCxCbBCbuTBTTBT单纯形方法：从初始基可行解出发，保证解一直是可行的，进行迭代。通过检验数进行判别，可得最优解，或得出结论，不存在最优解。由前面分析，现在考虑：能否从一检验数大于等于0的基解（对偶规划的可行解）出发，保证检验数都大于等于0，迭代，直至得到一基可行解。该解自然是基最优解。二、对偶单纯形法定义1对偶可行基：若B是线性规划（LP）的一个基，并且满足规划的一对偶可行基。为线性这时称是对偶问题的可行解，那么令BuBCuABCCTTBTTBT,.011考虑如下形式的线性规划xBxNxBI0NBCCTBTN1NB1bB1优解。，则所得基可行解是最若0.11bB,0min,0,0.20000lkkljljjlklaaaab取且存在若存在作代换，由对偶可行基B变成B'。0-11-11-1'-'TlTTTBlTjBjjluuBcuAccBABAccBABA令检验数为：分量：-1000000101,0;0.jljjljkklkkkkkjmjlBAjlnjmjkczajkczaczzc当且时，＝，所以检验数为零。时，检验数为,大于0。当且时,检验数为：时，检验数为：1-11'TTTBBlubcBbBbcBb目标函数：变换方法同单纯形中的变换方法。03.0,,0,llkbka若存在且可构造一方向，使得对偶目标函数值趋于正无穷，于是由对偶定理，可得线性规划无可行解。0-10-10()()()TTlTjjjjjjjlTuuBcuPczBPczu令=-检验数为：显然是对偶规划的可行解。0-100()--.TTTllububBbubb目标函数：当时上式无界，所以原规划无可行解。结论：1、利用单纯形方法求解线性规划时，若得到最优解，同时可得对偶问题的最优解。反之亦然。2、求解线性规划时，写出其对偶规划，可以从一对对偶问题中选一个较简单进行求解。例如，给定线性规划约束条件都是小于等于的不等式约束，通过添加松弛变量，系数矩阵中可得一单位子阵，利用单纯形方法求解即可。给定线性规划约束条件都是大于等于的不等式约束，目标函数中系数为正。通过添加剩余变量，系数矩阵中可得一负单位子阵，方程组两边同乘以－1，利用对偶单纯形方法求解。给定线性规划约束条件是混合的，通过添加剩余变量、松弛变量以及最少的人工变量，用大M法或两阶段法进行求解。012min54325431543ixxxxxxxxxxxxf例：求解线性规划解：显然（P1，P2）是一对偶可行基，应用对偶单纯形方法，代入单纯形表：0011100x1x21001[-1]-11-1-11-21检验数00111迭代，得：0011110x3x2-1-10110-1-21223检验数10020最优解为（0，3，2，0，0）T，最优值为2。该问题的对偶问题为111002max2121212121uuuuuuuuuu解。于是可求得对偶变量的可得设为对应目标函数中的系数对偶可行基，中的单位子阵，即初始可找对偶问题的解，为最优基）（要求000011',''BTBTBTBTBBBCCCABBC上例中对偶变量的解为（－1，0）T。迭代步骤：得到初始对偶基可行解。置s:=0判别常数项是否大于等于0。若是，停止迭代，所得解为最优解。若否，转3。确定mibiLsi1,0若.,,0,1LiilLlanjsl否则，取那么无最优解。确定njajkslkj1,min迭代置s：=s+1,转2。注：l，k的选取是为了避免循环的出现。21例2用对偶单纯形法求解下列线性规划minz=5x1+2x2+6x32x1+4x2+8x3≥244x1+x2+4x3≥8x1、x2，x3≥0解将问题改写成如下形式minz=5x1+2x2+6x3－2x1－4x2－8x3+x4=－24－4x1－x2－4x3+x5=－8x1、x2，x3，x4，x5≥0显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正则基。22Cj52600bCBXBx1x2x3x4x50x4-2[-4]-810-240x5-4-1-401-8526000θ-5/-2-2/-4-6/-8002x21/212-1/4060x5-7/20[-2]-1/41-24021/20-120θ-4/(-7/2)0-2/-2(-1/2)/(-1/4)02x2-310-1/2146x37/4011/8-1/211/2001/40-3223最后一个单纯形表中，已得到一个可行的正则解，因而得到问题的最优解为X*=（0，4，1）T最优值为z*=14对于形如minz=CX，AX≥b，X≥0，且C≥0的线性规划问题。因为将其改写为max(－z)=－CX，－AX+XS=－b，X≥0，则立即可以得到初始正则解；对偶单纯形法在以下情况下较为方便。思考题判断下列结论是否正确.1）任何线性规划都存在一个对应的对偶线性规划.2）原问题第i个约束是“≤”约束，则对偶变量yi≥0.3）互为对偶问题，或者同时都有最优解，或者同时都无最优解.4）对偶问题有可行解，则原问题也有可行解.5）原问题有多重解，对偶问题也有多重解.6）对偶问题有可行解，原问题无可行解，则对偶问题具有无界解.7）原问题无最优解，则对偶问题无可行解.8）对偶问题不可行，原问题可能无界解.9）原问题与对偶问题都可行，则都有最优解.10）原问题具有无界解，则对偶问题不可行.11）对偶问题具有无界解，则原问题无最优解.12）若X*、Y*是原问题与对偶问题的最优解，则X*=Y*.min(),0TfxCxAxbxnCx和为维向量bm为维向量Amn为阶矩阵mnC个基对于标准形式的线性规划问题：其中，，说明下面论断是否正确，并分别说明理由。（1）、该问题一定有（2）、最优解一定是基本最优解。（3）、基本解一定是基本可行解。（4）、最优基一定是可行基。。