对偶单纯形法(经典运筹学)ppt课件.ppt

对偶单纯形法是求解对偶规划的一种方法对偶单纯形法：利用对偶理论得到的一个 求解线性规划问题的方法单纯形法（原始单纯形法）的两个条件：1、问题为标准型2、有初始基本可行解0,3263433.2min2121212121xxxxxxxxtsxxZ求0,3263433.2max5432152142132121xxxxxxxxxxxxxxtsxxZ标准型为0,3263433.2max5432152174216321762176xxxxxxxxxxxxxxxxtsMxMxxxZxx ，引进人工变量用单纯形法求解1、不需要人工变量；、不需要人工变量；2、当变量多于约束时，用对偶单、当变量多于约束时，用对偶单纯形法可减少迭代次数；纯形法可减少迭代次数；3、在灵敏度分析中，有时需要用对、在灵敏度分析中，有时需要用对偶单纯形法处理简化。偶单纯形法处理简化。bAX 于是bXXNBNBbNXBXNBB 可逆NBNXBbBX11NBNBXXCCZ且NNBBXCXCNNNBXCNXBbBC)(11NBNBXNBCCbBC)(110,0.maxbXbAXtsCXz对标准型nmmPPPPPA121是可行基设mPPPB21NBA,NBXXX原始单纯形法的基本思路：NBCCC 0.maxXbAXtsCXz对问题mPPPB21取可行基NBNBXNBCCbBCZ)(max11NBNXBbBX110, 0NBXX关于可行基B的典则形式检验数0NX令01bBXB得0 ,11bBX得基本可行解011NBCN、若所有的检验数为最优解则1,X解则存在更好的基本可行分量的列向量中至少有一个且该分量对应中至少有一个分量、若检验数, 0, 031NBCCBN域内无上界则目标函数值在可行解向量中所有的分量且该分量对应的列中存在一个分量、检验数, 0, 021NBCCBN持对应的基本解可行在迭代过程中，始终保做换基迭代 :01bBXB即0011NBCCNBCCBNBN个数越来越少，最终的分量中并使检验数0.maxXbAXtsCXz对问题mPPPB21取可行基NBNBXNBCCbBCZ)(max11NBNXBbBX110, 0NBXXbBCZXNBCCXBNBNB11)(0bBNXBXNB110NX令01bBXB得，若01NBCN为最优解1XXB XN常数项检验行0 CN- CBB-1NZ- CBB-1bXBE B-1NB-1b初始单纯形表：0原始单纯形法的迭代过程：0 ,11bBX得基本可行解0?变量否则，选定入基、出基对该单纯形表做行变换，直至01NBCN得最优单纯形表件：最优单纯形表的充要条，01NBCN0.maxXbAXtsCXz对mPPPB21取基NBNBXNBCCbBCZ)(max11NBNXBbBX110, 0NBXX对偶单纯形法的基本思路：0NX令bBXB1得0 ,11bBX得基本解:01NBCCBN若XB XN常数项检验行 0 CN- CBB-1NZ- CBB-1bXBE B-1NB-1b作对偶单纯形表：00?为最优解1, X否则，换基迭代对该单纯形表做行变换，直至01bB得最优对偶单纯形表01bB若）始终保持0(1NBCN选定入基、出基变量要条件：最优对偶单纯形表的充01bB0,3263433.2min2121212121xxxxxxxxtsxxZ例：求0,3263433.2max5432152142132121xxxxxxxxxxxxxxtsxxZ解：标准型为0,3263433.54321521421321xxxxxxxxxxxxxxt s212maxxxZ即543,PPPB 取基36300，基本解X基B的典则形式X1X2X3X4X5检-2 -1000ZX3-3-1100-3X4-4-3010-6X5120013不可行检验行0分析：若X3或X4所在的行的aij均非负，则问题一定无可行解否则，做换基迭代X1X2X3X4X5检-2 -1000ZX3-3-1100-3X4-4-3010-6X51200131、确定出基变量：设br =minbi | bi 0不可行单纯形法对偶单纯形法？0,028951522312.max654321643218317432154326xxxxxxxxxxxxxxxxxxxxxxxtsxZ，对9x增加人工变量大M法：0,028951522312.max65432164321831743219543296xxxxxxxxxxxxxxxxxxxxxxxxtsMxxZ，求两阶段法0,028951522312.max6543216432183174321954329xxxxxxxxxxxxxxxxxxxxxxxxtsxZ，求单纯形法单纯形法作业：0,7742.max21212121xxxxxxtsxxZ求解下列问题用对偶单纯形法1331*13101321*ZX最优值：），（最优解：