《对偶理论和灵敏度分析》由会员分享，可在线阅读，更多相关《对偶理论和灵敏度分析（128页珍藏版）》请在金锄头文库上搜索。
1、福州大学公共管理学院第二章 对偶理论和灵敏度分析一、单纯形法的矩阵描述CjC1 C2 Cj. CnCBXBbx1 x2 xj xnxB1 xB2 xBnb1 b2. bna11 a12 a1j a1n a21 a22 a2j a2n an1 an2 anj ann 检验数 j1福州大学公共管理学院设线性规划问题 : 目标函数 max z=CX; 约束条件 AXb; 非负条件 X02福州大学公共管理学院给这线性规划问题的约约束条件加入松 弛变量以后，得到标准型：max z=CX+0Xs; AX+IXs=b; X，X s0 这里I 是mm单位矩阵。 3福州大学公共管理学院第二章 对偶理论和灵敏度分
2、析初始单纯形表和最终单纯形矩阵表示如下:CjCN CB 0 0XSbXN XB XSXSbN B I 检验数jCjCN CB 0 CBXBbXN XB XSXBB-1bB-1N BB-1 B-1 检验数 jCN -CB B-1N - CB B-14福州大学公共管理学院令非基变量=0；由上式得到：5福州大学公共管理学院二、改进单纯形法 求解线性规划问题的关键是计算 以下介绍一种比较简便的计算方法设mm系数矩阵A，求其逆矩阵。6福州大学公共管理学院可以先从第1列开始以 为主元素, 进行变换7福州大学公共管理学院8福州大学公共管理学院然后构造含有（1）列，而其他列都是 单位列的矩阵 9福州大学公共管
3、理学院可得到：10福州大学公共管理学院而后以第2列的 为主元素，进行变 换11福州大学公共管理学院然后构造含有（2）列，而其他列都是 单位列的矩阵12福州大学公共管理学院可得到13福州大学公共管理学院重复以上的步骤，直到获得14福州大学公共管理学院 求单纯形表的基矩阵的逆矩阵也可以用 这方法例：用改进单纯形法求解线性规划问题：15福州大学公共管理学院第1步：确定初始基，初始基变量;确定换入 ，换出变量。 （1）确定初始基和初始基变量：16福州大学公共管理学院（2）计算非基变量的检验数，确定换入 变量。17福州大学公共管理学院(3) 确定换出变量计算： 表示选择0的元素18福州大学公共管理学院（
4、4）基变换计算将新的基 单位矩阵。计算：19福州大学公共管理学院（5）计算非基变量的系数矩阵20福州大学公共管理学院（6）计算RHS21福州大学公共管理学院第1步计算结束后的结果22福州大学公共管理学院第2步 重复第1步的计算步骤从新的基，基变量开始。23福州大学公共管理学院计算非基变量的检验数，确定换入变 量。24福州大学公共管理学院(3) 确定换出变量计算： 表示选择0的元素25福州大学公共管理学院26福州大学公共管理学院计算RHS27福州大学公共管理学院第2步计算结束后的结果28福州大学公共管理学院第3步 从新的基，基变量开始,重复第1步的计算步骤.29福州大学公共管理学院计算非基变量检
5、验数，检查检验数，确 定换入变量30福州大学公共管理学院(3) 确定换出变量计算： 表示选择0的进行计算31福州大学公共管理学院新的基32福州大学公共管理学院计算B逆矩阵33福州大学公共管理学院34福州大学公共管理学院计算非基变量的检验数35福州大学公共管理学院最优解36福州大学公共管理学院目标函数的值37福州大学公共管理学院第二章 对偶理论和灵敏度分析 若第一章中例一关于某厂的生产计划问题，现有另 一企业想租赁其设备。厂方为了在谈判时心中有数 ，需掌握设备台时费用的最低价码，以便衡量对方 出价，对出租与否做出抉择。 在这个问题上厂长面临着两种选择：自行生产或出 租设备。首先要弄清两个问题：
6、合理安排生产能取得多大利润? 为保持利润水平不降低，资源转让的最低价格是多少？ 问题 的最优解：x1=4，x2=2，Z*=14。三、对偶问题的提出 38福州大学公共管理学院第二章 对偶理论和灵敏度分析第二个问题：出让定价 假设出租单位设备台时的租金和出让单位原材料A、B所得利 润分别为y1、y2、y3 原本用于生产I产品的设备台时，如若出让，不应低于自行生 产带来的利润，否则宁愿自己生产。于是有y1+4y2 2 同理，对产品而言，则有2y1+4y33 设备台时出让的收益（希望出让的收益最少值）min =8y1+16y2+12y3 显然还有 y1，y2，y3039福州大学公共管理学院第二章 对偶
7、理论和灵敏度分析 对偶问题的最优解： y1=3/2，y2=1/8，y3=0，W* =14 两个问题的目标函数值相等，这不是偶然的，上述两个问题 实际上是一个问题的两个方面，如果把前者称为线性规划原 问题，则后者便是它的对偶问题，反之亦然。 对偶问题的最优解对应于原问题最优单纯型法表中，初始基 变量的检验数的负值。例1的对偶问题的数学模型 min =8y1+16y2+12y3 y1+4y2 22y1 + 4y3 5y1，y2，y30 S.t.Max Z= 2x1 +3 x2x1 +2 x2 84x1 164 x2 12x1 , x2 0S.t.40福州大学公共管理学院第二章 对偶理论和灵敏度分析
8、原问题与对偶问题的表达形式41福州大学公共管理学院第二章 对偶理论和灵敏度分析四 线性规划的对偶理论 （一）原问题与对偶问题的关系 1、标准(max,)型的对偶变换 目标函数由 max 型变为 min 型 对应原问题每个约束行有一个对偶变量 yi， i=1,2,m 对偶问题约束为 型，有 n 行 原问题的价值系数 C 变换为对偶问题的右端项 原问题的右端项 b 变换为对偶问题的价值系数 原问题的技术系数矩阵 A 转置后成为对偶问题的技 术系数矩阵42福州大学公共管理学院原问题与对偶问题的关系这两个式子之间的变换 关系称为“对对称形式的对偶称形式的对偶 关系关系”。 43福州大学公共管理学院例：
9、写出下面线性规划的对偶问题：44福州大学公共管理学院第二章 对偶理论和灵敏度分析2、非标准型的对偶变换含等式约束时，将等式约束分解为两个不等式 约束条件。45福州大学公共管理学院第二章 对偶理论和灵敏度分析按对称形式变换关系可写出它的对偶问题，如上所示 。46福州大学公共管理学院原问题与对偶问题的关系，归纳如下：（原始对偶表）原问题（或对偶问 题）对偶问题 （或原问题 ）目标函数max z 变量 n个00无约束目标函数 min w 约束条件 n个 约束条件 m个 约束条件右端项 目标函数变量的系 数变量 m个0 0无约束目标函数变量的系数约束条件右端项47福州大学公共管理学院第二章 对偶理论和
10、灵敏度分析怎样写出非对称形式的对偶问题？把一个等式约束写成两个不等式约束，再根据对称形式的把一个等式约束写成两个不等式约束，再根据对称形式的 对偶关系定义写出；对偶关系定义写出；按照按照原始原始- -对偶表对偶表直接写出直接写出 。48福州大学公共管理学院第二章 对偶理论和灵敏度分析例：试述下列线性规划问题分对偶问题 min z =2x1+3x2-5x3 +x4x1+ x2-3x3 +x4 52 x1 + 2x3-x4 4x2+x3 +x4 =6x10; x2,x3 0; x4 无约束Max z5y14y26y3y12y2 2 y1 y333y12y2 y3 5y1 y2 y3 1 y1 0，
11、y2 0， y3 无约束 49福州大学公共管理学院第二章 对偶理论和灵敏度分析练习：练习：写出下面线性规划的对偶规划50福州大学公共管理学院哪一个正确？前一个。原问题是极小化问题，因此应从原始对偶表的右边往左 边查！51福州大学公共管理学院（二）对偶问题的基本性质 1、对称性：对偶问题的对偶是原问题。 2、弱对偶性若一对对称形式的对偶线性规划一对对称形式的对偶线性规划（L ） 和 （D ） 均有可行解，分别为 和 ，则C b。52福州大学公共管理学院证明思路：弱对偶性推论：极大化问题极大化问题的任意一个可行解所对应的目标函数值的任意一个可行解所对应的目标函数值 是其是其对偶问题对偶问题最优目标
12、函数值的一个最优目标函数值的一个下界下界。极小化。极小化 问题的任意一个可行解所对应的目标函数值是其对问题的任意一个可行解所对应的目标函数值是其对 偶问题最优目标函数值的一个偶问题最优目标函数值的一个上界上界。由（L ） 左乘 ，得 由（D ） 右乘 ，得 53福州大学公共管理学院第二章 对偶理论和灵敏度分析如果原max(min)问题为无界解，则其对偶 min (max) 问题无可行解如果原max(min)问题有可行解，其对偶 min (max)问 题无可行解，则原问题为无界解注：有可能存在原问题和对偶问题同时无可行解的 情况。3、最优性准则定理最优性准则定理 若若 、 分别为对称形式对偶线性
13、规划的可行解，分别为对称形式对偶线性规划的可行解， 且两者目标函数的相应值相等，即且两者目标函数的相应值相等，即C C b b ，则，则 ， 分别为原始问题和对偶问题的最优解。分别为原始问题和对偶问题的最优解。54福州大学公共管理学院第二章 对偶理论和灵敏度分析证明思路：由弱对偶性和已知条件易证。 4、主对偶定理如果原问题和对偶问题都有可行解，则它们都有最优 解，且它们的最优解的目标函数值相等。 证明要点： 第一部分第一部分证明两者均有最优解。证明两者均有最优解。 由于原始问题和对偶问题均可行均可行，根据弱对偶定理知 两者均有界均有界，于是均有最优解均有最优解。第二部分第二部分证明在达到最优时
14、，两个问题的目标函证明在达到最优时，两个问题的目标函数值相等。数值相等。55福州大学公共管理学院第二章 对偶理论和灵敏度分析设 X0 为原问题的最优解，它所对应的基矩阵是 B， X0= B1 b，则其检验数满足 C CBB1A 0。 令 Y0= CBB1，则有 Y0 A C ；而对原问题松弛变量的 检验数有 0 CBB1I 0，即 Y0 0 。显然Y0为对偶问题的可行解。因此有对偶问题目 标函数值， g(Y0)=Y0b= CBB1 b而原问题最优解的目标函数值为f(X0)=CX0= CBB1 b 故由最优解判别定理可知Y0 为对偶问题的最优解。证 毕。56福州大学公共管理学院第二章 对偶理论和灵敏度分析该定理的证明告诉我们一个非常重要的概念：对偶变量 的最优解等于原问题松弛变量的机会成本 即对偶变量的最优解是原问题资源的影子价格5、互补松弛定理 若X0, Y0分别是原问题和对偶问题的可行解。那么 Y0Xs0和X0Ys0，当且仅当X0, Y0为最优解。证明： 1） Y0Xs0和X0Ys0时， X0, Y0为最优解 2） 当X0, Y0为最优解时， Y0Xs0，X0Ys057福州大学公共管理学院第二章 对偶理论和灵敏度分析例4：已知线性规划问题试用对偶理论证明上述线性规划问题无最优解。 证明：上述问题的对偶问题是： 由约束条件可知对偶问题无可行 解，而原问题有可行解
