[理学]运筹学 对偶理论.ppt

* 单纯形法计算的矩阵描述 maxz=CX AX≤ b X?0 maxz=CX+0XS AX+IXS =b X, XS?0 原问题的矩阵表达： 标准化 初始基 (m×m) 基变量 * 单纯形法计算的矩阵描述 以Xs为基变量，并标记成XB ，决策变量分为： 2.将系数矩阵（A，I）分为（B，N）两块。B 是基变量的系数矩阵，N是非基变量的系数矩 阵。 3.将目标函数的系数C分为CB，CN ,分别对应于基 变量XB和非基变量XN，并且记作C=(CB, CN)。 基变量 非基变量 * 单纯形法计算的矩阵描述 5x2 ? 15 6x1+2x2?24 x1+x2 ? 5 x1 , x2 ?0 例1. max z=2x1 +x2 maxz=CX AX≤ b X?0 矩阵 * 单纯形法计算的矩阵描述 max z=2x1 +x2 +0 x3 +0x4 +0x5 5x2+x3 = 15 6x1+2x2 +x4 =24 x1+x2 +x5=5 x1 , … ,x5 ?0 标准化 maxz=CX+0XS AX+IXS= b X?0, XS ?0 矩阵 * 单纯形法计算的矩阵描述 列出初始单纯形表 cj 2 1 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 15 0 5 1 0 0 0 x4 24 6 2 0 1 0 0 x5 5 1 1 0 0 1 cj-zj σ 2 1 0 0 0 * 单纯形法计算的矩阵描述 cj 2 1 0 0 0 θ CB XB b x1 x2 x3 x4 x5 0 x3 15 0 5 1 0 0 — 0 x4 24 6 2 0 1 0 4 0 x5 5 1 1 0 0 1 5 cj-zj σ 2 1 0 0 0 [ ] 确定主元 * 单纯形法计算的矩阵描述 b B N I 15 24 5 x3 x1 x5 1 0 0 0 6 0 0 1 1 x4 x2 0 5 1 2 0 1 x3 x4 x5 1 0 0 0 1 0 0 0 1 XB XN XS (用x1替换x4) * 单纯形法计算的矩阵描述 （初始单纯形表） 决策变量 基变量 XB XN XS 0 XS b B N I σ CB CN 0 表 1 初等行变换之前的单纯形表(变量重排) * 单纯形法计算的矩阵描述 cj 2 1 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 15 0 5 1 0 0 2 x1 4 1 2/6 0 1/6 0 0 x5 1 0 4/6 0 -1/6 1 cj-zj σ 0 1/3 0 -1/3 0 新的基变量x3 ,x1 ,x5对应的基为单位阵: * 单纯形法计算的矩阵描述 b B N I 15 24 5 x3 x1 x5 1 0 0 0 6 0 0 1 1 x4 x2 0 5 1 2 0 1 x3 x4 x5 1 0 0 0 1 0 0 0 1 XB XN XS B-1b B-1B=I B-1N B-1I=B-1 对“增广”矩阵做初等行变换 cj-zj CB-CBI=0 CN-CBB-1N 0-CBB-1 * （迭代中的单纯形表） 基变量 非基变量 XB XN XS CB XB B-1 b I B-1 N B-1 σ 0 CN- CB B-1 N - CB B-1 单纯形法计算的矩阵描述 表 2 * 单纯形法计算的矩阵描述 结论 XB XN XS b B N I B-1b B-1B=I B-1N B-1I=B-1 对“增广”矩阵做初等行变换 cj-zj CB-CBI=0 CN-CBB-1N 0-CBB-1 迭代前 迭代后 * 单纯形法计算的矩阵描述 检验数 YT=CBB-1 单纯形乘子 CB-CBI=0 ATY≥CT Y?0 将检验数-CBB-1 取相反数，即为其对偶问题的一个可行解 w=YTb= CBB-1b=z 当原问题为最优解时，对偶问题为可行解，且两者具有相同的目标函数值。（为最优解） * 单纯形法计算的矩阵描述 矩阵形式： max z=CX AX≤ b X?0 min w=YTb ATY≥CT Y?0 原问题： 对偶问题： * 第二节 对偶问题的基本性质 一、单纯形法计算的矩阵描述 二、对偶 问题的基本性质 * 1.对称性：对偶问题的对偶问题是原问题 2.定理1 (弱