对偶单纯性法精品课件

1、对偶单纯性法第1页，共25页，2022年，5月20日，1点56分，星期三可知：第2页，共25页，2022年，5月20日，1点56分，星期三单纯形方法：从初始基可行解出发，保证解一直是可行的，进行迭代。通过检验数进行判别，可得最优解，或得出结论，不存在最优解。由前面分析，现在考虑：能否从一检验数大于等于0的基解（对偶规划的可行解）出发，保证检验数都大于等于0，迭代，直至得到一基可行解。该解自然是基最优解。第3页，共25页，2022年，5月20日，1点56分，星期三二、对偶单纯形法定义1 对偶可行基：若B是线性规划（LP）的一个基，并且满足第4页，共25页，2022年，5月20日，1点56分，星期

2、三考虑如下形式的线性规划xBxNxBI0第5页，共25页，2022年，5月20日，1点56分，星期三作代换，由对偶可行基B变成B。第6页，共25页，2022年，5月20日，1点56分，星期三第7页，共25页，2022年，5月20日，1点56分，星期三第8页，共25页，2022年，5月20日，1点56分，星期三第9页，共25页，2022年，5月20日，1点56分，星期三无界，所以原规划无可行解。第10页，共25页，2022年，5月20日，1点56分，星期三结论：1、利用单纯形方法求解线性规划时，若得到最优解，同时可得对偶问题的最优解。反之亦然。2、求解线性规划时，写出其对偶规划，可以从一对对偶问

3、题中选一个较简单进行求解。第11页，共25页，2022年，5月20日，1点56分，星期三例如，给定线性规划约束条件都是小于等于的不等式约束，通过添加松弛变量，系数矩阵中可得一单位子阵，利用单纯形方法求解即可。给定线性规划约束条件都是大于等于的不等式约束，目标函数中系数为正。通过添加剩余变量，系数矩阵中可得一负单位子阵，方程组两边同乘以1，利用对偶单纯形方法求解。第12页，共25页，2022年，5月20日，1点56分，星期三给定线性规划约束条件是混合的，通过添加剩余变量、松弛变量以及最少的人工变量，用大M法或两阶段法进行求解。第13页，共25页，2022年，5月20日，1点56分，星期三例：求解

4、线性规划第14页，共25页，2022年，5月20日，1点56分，星期三解：显然（P1，P2）是一对偶可行基，应用对偶单纯形方法，代入单纯形表：0011100 x1x21001-1-11-1-11-21检验数001 1 1第15页，共25页，2022年，5月20日，1点56分，星期三迭代，得：0011110 x3x2-1-10110-1-21223检验数100 2 0最优解为（0，3，2，0，0）T，最优值为2。第16页，共25页，2022年，5月20日，1点56分，星期三该问题的对偶问题为第17页，共25页，2022年，5月20日，1点56分，星期三上例中对偶变量的解为（1，0）T。第18页，

5、共25页，2022年，5月20日，1点56分，星期三迭代步骤：得到初始对偶基可行解。置s:=0判别常数项是否大于等于0。若是，停止迭代，所得解为最优解。若否，转3。确定若第19页，共25页，2022年，5月20日，1点56分，星期三确定迭代置s：=s+1,转2。注：l，k的选取是为了避免循环的出现。第20页，共25页，2022年，5月20日，1点56分，星期三21例2 用对偶单纯形法求解下列线性规划 min z=5x1+2x2+6x32x1 +4x2 +8x3 244x1 + x2 + 4x38x1、x2，x30解 将问题改写成如下形式 min z=5x1+2x2+6x32x1 4x2 8x3

6、 + x4 =244x1 x2 4x3 +x5 =8x1、x2，x3，x4，x50显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正则基。第21页，共25页，2022年，5月20日，1点56分，星期三22Cj52600bCBXBx1x2x3x4x50 x4-2-4-810-240 x5-4-1-401-8526000-5/-2-2/-4-6/-8002x21/212-1/4060 x5-7/20-2-1/41-24021/20-120-4/(-7/2)0-2/-2(-1/2)/(-1/4)02x2-310-1/2146x37/4011

7、/8-1/211/2001/40-32第22页，共25页，2022年，5月20日，1点56分，星期三23最后一个单纯形表中，已得到一个可行的正则解，因而得到问题的最优解为 X*=（0，4，1）T最优值为z*=14对于形如min z=CX，AXb，X0，且C0的线性规划问题。因为将其改写为max (z) =CX，AX+XS=b，X0，则立即可以得到初始正则解； 对偶单纯形法在以下情况下较为方便。第23页，共25页，2022年，5月20日，1点56分，星期三思考题判断下列结论是否正确.1）任何线性规划都存在一个对应的对偶线性规划.2）原问题第i个约束是“”约束，则对偶变量yi0.3）互为对偶问题，或者同时都有最优解，或者同时都无最优解.4）对偶问题有可行解，则原问题也有可行解.5）原问题有多重解，对偶问题也有多重解.6）对偶问题有可行解，原问题无可行解，则对偶问题具有无界解.7）原问题无最优解，则对偶问题无可行解.8）对偶问题不可行，原问题可能无界解.9）原问题与对偶问题都可行，则都有最优解.10）原问题具有无界解，则对偶问题不可行.11）对偶问题具有无界解，则原问题无最优解.12）若X*、Y*是原问题与对偶问题的最优解，则X*=Y*.第24页，共25页，2022年，5月20日，1点56分，星期三