运筹学之对偶单纯形法

第二章线性规划的对偶理论2.1对偶线性规划模型2.2对偶问题的性质2.3对偶单纯形法2.4灵敏度分析与参数分析一.对偶单纯形法与单纯形法的区别：相同之处：对偶单纯形法与单纯形法都是对单纯形表进行迭代计算。当常数列，而检验数行都时，单纯形表是最优表。00检验数3x4x5x1x2x常数00最优表12412312412512345min22566221,,,,0Zxxxxxxxxxxxxxxxxx一.对偶单纯形法与单纯形法的区别：检验数3x4x5x1x2x常数00最优表12412312412512345min22566221,,,,0Zxxxxxxxxxxxxxxxxx不同之处：单纯形法：在迭代过程中，始终保持常数列，而00检验数行由有负检验数逐步变为全部对偶单纯形法：在迭代过程中，始终保持检验数行，而常数列由有负分量逐步变为全部00二.对偶单纯形法的迭代步骤：123min43Zxxx1235xxx123,,0xxx12343xxx求解例2-8标准形式约束都的问题。注：对偶单纯形法适用于目标函数系数都，不等00123min43Zxxx12345xxxx12345,,,,0xxxxx123543xxxx123min43Zxxx12345xxxx12345,,,,0xxxxx123543xxxx不是典式，可用两阶段法求解，麻烦！否则不能用。二.对偶单纯形法的迭代步骤：例2-81.建立初始单纯形表单纯形表检验数3x4x5x1x2x常数列-1-1-110-5-11401-34x5x4130000有负分量注：检验数行，因此可以用对偶单纯形法求解，0123min43Zxxx12345xxxx12345,,,,0xxxxx123543xxxx41300001BjjjcCBp1BCBbjcBC二.对偶单纯形法的迭代步骤：例2-8单纯形表检验数3x4x5x1x2x常数列-1-1-110-5-11401-34x5x4130000有负分量123min43Zxxx12345xxxx12345,,,,0xxxxx123543xxxx2.最优性检验：若当前常数列，则得到最优表。否则转下一步。0二.对偶单纯形法的迭代步骤：例2-8单纯形表检验数3x4x5x1x2x常数列-1-1-110-5-11401-34x5x4130000有负分量123min43Zxxx12345xxxx12345,,,,0xxxxx123543xxxx3.确定出基变量：将常数列中最负分量所在的行相应的基变量出基。min{5,3}54x为出基变量二.对偶单纯形法的迭代步骤：例2-8单纯形表检验数3x4x5x1x2x常数列-1-1-110-5-11401-34x5x4130000123min43Zxxx12345xxxx12345,,,,0xxxxx123543xxxx所有元素都，则原问题无可行解。停止计算。4.确定进基变量：4131min{,,}11112x为进基变量。在出基变量所在的行中，找出非基变量列中的负系数，用相应的检验数分别除以这些负系数，再取绝对值，所得正比值中最小者相应的非基变量进基。若出基变量所在的行中，0-1-1-1二.对偶单纯形法的迭代步骤：例2-8单纯形表检验数3x4x5x1x2x常数列10-5-11401-34x5x4130000123min43Zxxx12345xxxx12345,,,,0xxxxx123543xxxx5.换基运算：2x111010(1)11-151111二.对偶单纯形法的迭代步骤：例2-8单纯形表检验数3x4x5x1x2x常数列-105-11401-35x4130000123min43Zxxx12345xxxx12345,,,,0xxxxx123543xxxx5.换基运算：1110102x(1)-2031-8111二.对偶单纯形法的迭代步骤：例2-8单纯形表检验数3x4x5x1x2x常数列-105-20311-85x413000123min43Zxxx12345xxxx12345,,,,0xxxxx123543xxxx5.换基运算：1110102x(1)3021-5111二.对偶单纯形法的迭代步骤：例2-8单纯形表检验数3x4x5x1x2x常数列-105-20311-85x30210-5123min43Zxxx12345xxxx12345,,,,0xxxxx123543xxxx2x0换基运算完成。得到新的单纯形表。2.最优性检验：若当前常数列，则得到最优表。否则转下一步。0111二.对偶单纯形法的迭代步骤：例2-8单纯形表检验数3x4x5x1x2x常数列-105-20311-85x30210-5123min43Zxxx12345xxxx12345,,,,0xxxxx123543xxxx2x03.确定出基变量：将常数列中最负分量所在的行相应的出变量离基。85x为出基变量111二.对偶单纯形法的迭代步骤：例2-8单纯形表检验数3x4x5x1x2x常数列-105-20311-85x30210-5123min43Zxxx12345xxxx12345,,,,0xxxxx123543xxxx2x04.确定进基变量：在出基变量所在的行中，找出非基变量列中的负系数，用相应的检验数分别除以这些负系数，再取绝对值，所得正比值中最小者相应的非基变量进基。33min{}221x为进基变量。111二.对偶单纯形法的迭代步骤：例2-8单纯形表检验数3x4x5x1x2x常数列-105-20311-85x30210-5123min43Zxxx12345xxxx12345,,,,0xxxxx123543xxxx2x05.换基运算：1021301x(12)1-3/2-1/2-1/241111二.对偶单纯形法的迭代步骤：例2-8单纯形表检验数3x4x5x1x2x常数列-1050-3/2-1/2-1/2430210-5123min43Zxxx12345xxxx12345,,,,0xxxxx123543xxxx2x5.换基运算：1021301x(3)013/25/23/2-171111二.对偶单纯形法的迭代步骤：例2-8单纯形表检验数3x4x5x1x2x常数列-1050-3/2-1/2-1/240013/25/23/2-17123min43Zxxx12345xxxx12345,,,,0xxxxx123543xxxx2x5.换基运算：1021301x(1)05/2-1/21/21换基运算完成。得到新的单纯形表。01111二.对偶单纯形法的迭代步骤：例2-8单纯形表检验数3x4x5x1x2x常数列-1050-3/2-1/2-1/240013/25/23/2-17123min43Zxxx12345xxxx12345,,,,0xxxxx123543xxxx2x1x05/2-1/21/2102.最优性检验：若当前常数列，则得到最优表。00最优表(4,1,000,,)TX17Z123min43Zxxx1235xxx123,,0xxx12343xxx第二章线性规划的对偶理论2.1对偶线性规划模型2.2对偶问题的性质2.3对偶单纯形法2.4灵敏度分析与参数分析作业：P696(1),(3)123min345Zxxx532321xxx622321xxx0,,321xxx标准形123min345Zxxx5324321xxxx6225321xxxx0,,,,54321xxxxx5324321xxxx6225321xxxx0,,,,54321xxxxx123min345Zxxx作业1用对偶单纯形法求解：与2.6(1)类似单纯形表一检验数3x4x5x1x2x常数列-1-2-310-5-2-2-101-64x5x003450000有负分量注：检验数行，因此可以用对偶单纯形法求解。05324321xxxx6225321xxxx0,,,,54321xxxxx123min345Zxxx单纯形表一检验数3x4x5x1x2x常数列-1-2-310-5-2-2-101-64x5x345000单纯形表二检验数3x4x5x1x2x常数列0-1-310-211-10134x1x01-500-9521272121232单纯形表三检验数3x4x5x1x2x常数列01-1210-112x1x001-115212-111-2最优表(1,2,0,0,0)TX11Z12min34Zxx124xx1222xx12,0xx标准形作业2用对偶单纯形法求解：2.6(2)12min34Zxx1234xxx12422xxx1234,,,0xxxx12min34Zxx1234xxx12422xxx1234,,,0xxxx单纯形表一检验数3x4x1x2x常数列-1-110-4210123x4x00340000有负分量注：检验数行，因此可以用对偶单纯形法求解。012min34Zxx1234xxx12422xxx1234,,,0xxxx单纯形表一检验数3x4x1x2x常数列-1-110-4210123x4x34000单纯形表二检验数3x4x1x2x常数列11-10单纯形表三检验数3x4x1x2x常数列2x1x最优表40-121-60130-124x1x1011-201-2-160051-18单纯形表一检验数3x4x1x2x常数列2x1x1011-201-2-160051-18确定进基变量：在出基变量所在的行中，找出非基变量列中的负系数，用相应的检验数分别除以这些负系数，再取绝对值，所得正比值中最小者相应的非基变量进基。在出基变量所在的行中，若非基变量列中没有负系数，则原问题无解（因为这是矛盾方程）。12min24Zxx122324xx12210xx12,0xx12315xx标准形作业3用对偶单纯形法求解：2.6(3)12min24Zxx1232324xxx124210xxx12345,,,,0xxxxx125315xxx12min24Zxx1232324xxx124210xxx12345,,,,0xxxxx125315xxx单纯形表一检验数3x4x5x1x2x常数列2310024-1-2010-104x5x002400003x-1-3-1500100有负分量注：检验数行，因此可以用对偶单纯形法求解。012min24Zxx1232324xxx124210xxx12345,,,,0xxxxx125315xxx检验数3x4x5x1x2x常数列表一2310024-1-2010-104x5x2400003x1/31500-1/3-2/3检验数3x4x