[第二章对偶理论和灵敏度分析.ppt

第2章 对偶理论和灵敏度分析 预备知识 矩阵的加法 相加的两个矩阵必须具有相同的行数和列数 预备知识 矩阵的数量乘法 用数乘一个矩阵，需要把矩阵中的每个元素都乘上k 预备知识 矩阵的乘法 左矩阵A的列数必须等于右矩阵B的行数 不满足交换律 预备知识 矩阵的转置 可逆矩阵 A-1A=AA-1=I 2.1 单纯形法的矩阵描述 对于线性规划问题： 2.1 单纯形法的矩阵描述 将原问题化为标准型（加入松弛变量），得 2.1 单纯形法的矩阵描述 得到初始的单纯形表： 此时前m列可以凑成一个基，用B表示： 2.1 单纯形法的矩阵描述 得到初始的单纯形表： 第m+1列至n列为非基变量，用N表示： 2.1 单纯形法的矩阵描述 得到初始的单纯形表： 第n+1列至n+m列为松弛变量，用S表示： 2.1 单纯形法的矩阵描述 因此，原单纯形表可分解为： 2.2 改进单纯形法 用矩阵运算的方法也可以求解线性规划问题，其本质与单纯形法一样，非基变量检验数的判断方法也与单纯形法相同。 用矩阵运算的方法求解例1： 2.2 改进单纯形法 2.2 改进单纯形法 由于 p3 , p4 , p2 为基向量 而 p1 , p5 为非基向量 则原单纯形表变为 2.2 改进单纯形法 2.2 改进单纯形法 由于 p1 , p4 , p2 为基向量 而 p3 , p5 为非基向量 则原单纯形表变为 2.2 改进单纯形法 2.2 改进单纯形法 求出最终的单纯形表为： 练习题 2.3 对偶问题的提出 对偶是指同一事物（问题）从不同的角度（立场）观察，有两种相对的表述。 每一个线性规划问题，都存在一个与它密切相关的另一个线性规划问题，我们称其中任意一个为原问题，另一个则称为它的对偶问题。 2.4 对偶问题的基本性质 对于线性规划问题： 基B对应的单纯形表如下： 当非基变量的检验数均小于或等于0的时候，该线性规划问题可以得到最优解，即 2.4 对偶问题的基本性质 上式中均含有乘子 CBB-1 ,称它为单纯形乘子，并令 则有 Y≥0 包括基变量在内的所有检验数可以表示为： 原先性规划问题的最优值为 2.4 对偶问题的基本性质 这样，即可得到原线性规划的对偶问题: 2.4 对偶问题的基本性质-1 对称性 对偶问题的对偶是原问题 2.4 对偶问题的基本性质-2 弱对偶性 若 X0 是原问题的可行解，Y0 是对偶问题的可行解，则存在 CX0≤Y0b。 2.4 对偶问题的基本性质-3 无界性 若原问题存在无界解，则其对偶问题无可行解。 反证法：若对偶问题存在可行解 Y0，根据弱对偶性，可知 CX≤Y0b 而 Y0b 是一个定数，这与原问题无界相矛盾。 推论：若对偶问题存在无界解，则其原问题无可行解。 2.4 对偶问题的基本性质-4 若 X0 是原问题的可行解，Y0 是对偶问题的可行解，当 CX0=Y0b 时，X0 ，Y0 分别是原问题和其对偶问题的最优解。 根据弱对偶性可知，对原问题的任一可行解 X，均有 CX≤Y0b 由于 CX0=Y0b，可知 CX≤CX0 从而可知 X0 是原问题的最优解。 同理，可证 Y0 是其对偶问题的最优解。 2.4 对偶问题的基本性质-5 对偶定理 若原问题有最优解，则对偶问题也有最优解，且目标函数值相等。 令 X* 为原问题的最优解，则 同时，检验数要满足 令 可知 Y* 是其对偶问题的一个可行解。 又 根据性质4，可知 Y* 是其对偶问题的最优解。 2.4 对偶问题的基本性质-6 互补松弛性 若 X* 和 Y* 分别为原问题和对偶问题的可行解，那么 其中 Xs* 和 Ys* 分别为松弛变量和剩余变量解的集合。 2.4 对偶问题的基本性质-6 例题：已知线性规划问题： 已知其对偶问题的最优解为 y1*= 4/5， y2*= 3/5；z=5。 试用对偶理论找出原问题的最优解 。 2.4 对偶问题的基本性质-7 基解的互补性 原问题的一个基解，对应其对偶问题的一个基解，并且该对互补基解的目标函数值相等； 当求得原问题在基 B 下的单纯形表后，表中检验数行相反的数（即－σ），就是其对偶问题的一个基解。 2.5 对偶问题的经济解释—影子价格 将下列线性规划模型（例1）