第二章对偶理论与灵敏度分析.pptVIP

表2.8此时基本解为X=(3/2,0,0,0,-1/2,0),不可行，转第二步。因为-1/20,所以x5为换出变量，又因为Min{-4/(-5/2),{-4/(-5/2),{-9/(-5/2),{-1/(-1/2)}=8/5,所以x2和x3都可以作为换入变量。任选其中一个x2，做线性变换得到新的单纯形表2.9第91页，共133页，星期日，2025年，2月5日表2.9得到一个基本解为X=(8/5,1/5,0,0,0,0)T,因解是可行的，所以满足最优检验下的基本可行解因而也是最优解。第92页，共133页，星期日，2025年，2月5日Chapter2从以上求解过程中我们可以看到，对偶单纯形法有以下的优点：1)初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。2)当变量多于约束条件，对于这样的线性规划问题，用对偶单纯形法计算可以减少计算工作量，因此对于变量较少，而约束条件很多的线性规划问题，可以首先将它变换成为对偶问题，然后用对偶单纯形法来求解。第93页，共133页，星期日，2025年，2月5日3)在灵敏度分析中，有时需要使用对偶单纯形法，这样可以使问题处理简化。对偶单纯形法的局限在于：对于大多数的线性规划问题，很难找到一个初始可行基，因而这个方法在求解线性规划问题时很少单独应用。第94页，共133页，星期日，2025年，2月5日例2.7：判断下例说法是否正确，为什么？A如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解B如果线性规划的对偶问题无可行解，则原问题也一定无可行解。C在互为对偶的一对原问题和对偶问题中，不管原问题是求极大或者极小，原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数值。第59页，共133页，星期日，2025年，2月5日解：A不对。因为原问题为无界解时（它当然有可行解），其对偶问题无可行解。B此句为A的逆否命题，所以也不对。C不对。因为哪个问题是原问题，哪个问题是对偶问题是相对而言的。第60页，共133页，星期日，2025年，2月5日例2.8已知线性规划问题

试用对偶理论证明上述线性规划问题有无界解（即有可行解但无最优解）。第61页，共133页，星期日，2025年，2月5日证明：所给问题的对偶问题为第62页，共133页，星期日，2025年，2月5日显然约束条件中与矛盾，即此对偶问题无可行解，因此所给原问题无最优解，它只可以是无界解或者无可行解。然而X=（0，0，0）显然是它的可行解，因此它必定有无界解。第63页，共133页，星期日，2025年，2月5日补充例题给出线性规划（1）写出对偶问题（2）用对偶理论证明上述线性规划目标函数值无界第64页，共133页，星期日，2025年，2月5日解：（1）对偶问题为第65页，共133页，星期日，2025年，2月5日上述对偶问题中,则与对偶问题的第一个约束条件矛盾，所以对偶问题无可行解，因而原问题无最优解，它只可以是无界解或者无可行解，然而x=(10,4,2)显然是他的可行解，因而它必定有无界解。第66页，共133页，星期日，2025年，2月5日例2.9已知线性规划问题已知其对偶问题的最优解为试用对偶理论找出原问题的最优解。第67页，共133页，星期日，2025年，2月5日解：先写出它的对偶问题

第68页，共133页，星期日，2025年，2月5日将的值代入约束条件，得到(2),(3),(4)为严格不等式;由互补松弛性得到因为;原问题的两个约束条件的松弛变量由互补松弛性得到为0，因此两个约束条件应该取等式,所以有第69页，共133页，星期日，2025年，2月5日求解后得到所以原问题的最优解为X=(1,0,0,0,1)T第70页，共133页，星期日，2025年，2月5日

补充例题:

已知原问题的最优解为X*=（0,0,4），Z=12,试求对偶问题的最优解。第71页，共133页，星期日，2025年，2月5日解:对偶问题为将X*=（0,0,4）代入原问题中，有下式：第72页，共133页，星期日，2025年，2月5日Chapter2灵敏度分析所以，根据互补松弛条件，必有y*1=y*2=0，代入对偶问题约