运筹学基础-对偶线性规划-1课件.pptVIP

第二章 线性规划的对偶理论 一、对偶线性规划问题 练习：试求下列线性规划问题的对偶问题 练习：试求下列线性规划问题的对偶问题 练习：试求下列线性规划问题的对偶问题 变换单纯形表 又例：用单纯形法同时求解原问题和对偶问题 定理7 结论：用单纯形法求解线性规划时，迭代的每一步在得到原问题一个基本可行解的同时，其： 线性规划原问题及其对偶问题之间存在一对互补的基解，其中原问题的松驰变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这两个解代入各自的目标数中有 z=w。 注：证明过程参见教材60页性质6证明 检验数行的-(cj-zj)值是其对偶问题的一个基本解yi ； 用单纯形法同时求解原问题和对偶问题 原问题是： maxZ=2x1 +x2 5x2 ≤15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1 , x2 ≥0 原问题的标准型是： maxZ=2x1 +x2+0x3+0x4 +0x5 5x2 +x3 =15 6x1 + 2x2 +x4 = 24 x1 + x2 +x5 = 5 xi ≥0 检验数?j b XB CB 比 值 Cj x5 x4 x3 x2 x1 0 0 0 1 2 0 0 1 5 0 15 0 1 0 2 6 24 1 0 0 1 1 5 x5 x4 x3 0 0 0 0 0 0 1 2 0 maxZ=2x1 +x2+0x3+0x4 +0x5 5x2 +x3 =15 6x1 + 2x2 +x4 = 24 x1 + x2 +x5 = 5 xi ≥0 5/1=5 24/6=4 - 原问题变量 原问题松驰变量 对偶问题剩余变量 y4、y5 对偶问题变量 y1、y2 、y3 得原问题可行解:X=(0,0,15,24,5)T 对偶问题解:Y*=(0,0,0,-2,-1)T 检验数行的－ (cj-zj)值是其对偶问题的一个基本解yi ； 检验数?j 0 0 1 5 0 15 0 1/6 0 1/3 1 4 1 -1/6 0 2/3 0 1 x5 x1 x3 0 2 0 0 -1/3 0 1/3 0 -8 1.5 12 3 得原问题可行解:X=(4,0,15,0,1)T，此时Z=8 同时得对偶问题基础解:Y*=(0,1/3,0, 0,-1/3)T，W=8 对偶问题剩余变量 y4、y5 对偶问题变量 y1、y2 、y3 原问题变量 原问题松驰变量 检验数行的-(cj-zj)值是其对偶问题的一个基本解yi ； 检验数?j= cj-zj b XB CB 比 值 Cj x5 x4 x3 x2 x1 0 0 0 1 2 -15/2 5/4 1 0 0 15/2 -1/2 1/4 0 0 1 7/2 3/2 -1/4 0 1 0 3/2 x2 x1 x3 1 2 0 -1/2 -1/4 0 0 0 -17/2 此时得原问题最优解:X*=(7/2,3/2,15/2,0,0)T，Z*=17/2 原问题变量 原问题松驰变量 对偶问题剩余变量 y4、y5 对偶问题变量 y1、y2 、y3 则对偶问题最优解:Y*=(0,1/4,1/2,0,0)T，S*=17/2 检验数行的-(cj-zj)值是其对偶问题的一个基本解yi ； maxZ= 100 x1 + 80 x2 2 x1+4 x2≤ 80 3 x1+ x2≤ 60 x1, x2 ≥0 将线性规划问题标准化 maxZ= 100 x1 + 80 x2 + 0 x3 + 0 x4 2 x1+4 x2 + x3 = 80 3 x1+ x2 + x4 =60 x1, x2 x3 x4 ≥0 0 0 0 80 100 -Z 60 1 0 1 3 0 80 0 1 4 2 0 此时得原问题的最优解：X0=(16,12,0,0)T , maxZ=2560 初等变换 -2000