管理运筹学LP问题教案.pptVIP

OR1 * 3.1.2对偶规则 原问题一般模型： 对偶问题一般模型： maxZ=CX min ω=Yb AX ≤b YA ≥C X ≥0 Y ≥0 OR1 * 对偶规则 原问题有m个约束条件，对偶问题有m个变量 原问题有n个变量，对偶问题有n个约束条件 原问题的价值系数对应对偶问题的右端项 原问题的右端项对应对偶问题的价值系数 原问题的技术系数矩阵转置后为对偶问题系数矩阵 原问题与对偶问题优化方向相反 OR1 * 对偶规则 . 原问题 对偶问题 目标函数 max min 目标函数 约束条件 ≤ ≥ = ≥ 变量 ≤ 无约束 ≥ 变量符号 ≤ 无约束 ≥ ≤ 约束条件 = OR1 * 对偶规则简捷记法 原问题标准则对偶问题标准 原问题不标准则对偶问题不标准 例题2 max ω=7y1+4y2-2y3 minZ=3x1+2x2-6x3+x5 2y1+ y2- y3 ≤3 2x1+x2-4x3+x4+3x5 ≥7 y1 +3y3 ≤2 x1+ 2x3 -x4 ≤ 4 -4y1+ 2y2 ≤-6 -x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 ≥ 0 x1，x2，x3 ≥0; 3y1 +y3=1 x4 ≤ 0;x5无限制 y1≥0;y2≤0;y3无约束 OR1 * 补充知识：单纯形法的矩阵描述 将系数矩阵A分解为两部分，即A=B+N，则maxZ=CBXB+CNXN BXB+NXN=b XB，XN ≥ 0 约束条件移项： BXB=b －NXN 左乘B-1 ： XB= B-1 b － B-1 NXN 代入目标函数： Z=CB B-1 b － CB B-1 NXN +CNXN = CB B-1 b +（CN － CB B-1 N）XN ＝ CB B-1 b + σNXN 基变量检验数： σB＝ CB － CB B-1 B=0 松弛变量检验数: σS= 0-CB B-1 I= -CB B-1 =-Y OR1 * 3.1.3对偶问题的基本性质 1.对称性：对偶问题的对偶问题是原问题 2.弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值 (鞍型图) 3.无界性：原问题无界，对偶问题无可行解 OR1 * 对偶问题的基本性质 4.强对偶性：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。 证明：设X*是原问题最优解，则必有σ ≤0 即 C－ CB B-1 A ≤0 设Y* ＝ CB B-1 则Y*A ≥C，表示Y*是对偶问题的可行解 代入其目标函数ω=Y*b＝ CB B-1 b 因X*是原问题最优解，原问题Z=C X*= CB B-1 b 故有：C X*= CB B-1 b =Y*b 证毕 OR1 * 对偶问题的基本性质 5.互补松弛性：原问题和对偶问题的可行解 X*、Y*为最优解的充要条件是Y*XS=0,YSX*=0 证明：原问题maxZ=CX； 对偶问题min ω=Yb AX+XS=b YA－YS=C X，XS≥ 0 Y,YS ≥ 0 将YA－Y