3对偶理论

nullnull对 偶 理 论 (Duality Theory)对偶问题的提出线性规划的对偶理论对偶问题的经济解释----影子价格 对 偶 单 纯 形 法 灵 敏 度 分 析一、问 题 的 提 出一、问 题 的 提 出 对偶性是线性规划问题的最重要的内容之一。每一个线性规划（ LP ）必然有与之相伴而生的另一个线性规划问题，即任何一个求 maxZ 的LP都有一个求 minZ 的LP。其中的一个问题叫“原问题”，记为“P”，另一个称为“对偶问题”，记为“D”。 例一、资源的合理利用问题 已知资料如表所示，问应如何安排生产 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 使得既能充分利用现有资源有使总利润最大？null 下面从另一个角度来讨论这个问题： 假定：该厂的决策者不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于接受外来加工任务，只收取加工费。试问该决策者应制定怎样的收费 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 （合理的）？null 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 问题： 1、每种资源收回的费用不能低于自己生产时的可获利润； 2、定价又不能太高，要使对方能够接受。null 一般而言，W 越大越好，但因需双方满意，故为最好。该问题的数学模型为：模型对比：模型对比：null 例二、合理配料问题，其数学模型为： 假设工厂想把这m 种营养成分分别制成一种营养丸销售，问如何定价（以保证总收入为最多）？nullnull例三、二、线性规划的对偶理论 （一）、对偶问题的形式 二、线性规划的对偶理论 （一）、对偶问题的形式 1、对称型对偶问题：已知 P，写出 D。null 例一、写出线性规划问题的对偶问题解：首先将原式变形nullnull2、非对称型对偶问题null例二、原问题null2、混合型对偶问题nullnullnull综上所述，其变换形式归纳如下：null例四、线性规划问题如下：null练习：练习：null（二）、对偶问题的性质 （二）、对偶问题的性质 min Z’= - CX s.t. - AX≤- b X ≥01、对称性定理：对偶问题的对偶是原问题。max W’ = -Yb s.t. YA≥ C Y ≤ 0nullnull 推论⑵.在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。null 推论⑶.在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行，（如D），则该可行的问题无界。例一、试估计它们目标函数的界，并验证弱对偶性原理。（P）null解：（D）null例二、已知试用对偶理论证明原问题无界。null例3、已知显然，这两个问题都无可行解。null 3、最优性判别定理： 若 X* 和 Y* 分别是 P 和 D 的可行解且 CX* = Y* b， 则X*. Y*分别是问题 P和D 的最优解。 例如，在例1中，可找到 X*=（0.0.4.4）， Y*=（1.2，0.2）,则Z=28，W=28.故X* .Y*分别是 P和D 的最优解。null 4、对偶定理（强对偶性）： 若一对对偶问题 P 和 D 都有可行解，则它们都有最优解，且目标函数的最优值必相等。 推论⑷.若 P 和 D 的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。 综上所述，一对对偶问题的关系，只能有下面三种情况之一出现： ①.都有最优解，分别设为X* 和 Y*，则必有CX* =Y*b； ②. 一个问题无界，则另一个问题无可行解； ③.两个都无可行解。null 5、互补松弛定理： 设X*和Y*分别是问题 P 和 D 的可行解，则它们分别是最优解的充要条件是同时成立 一般而言，我们把某一可行点（如X*和Y* ）处的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。所以有如下推论： 设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。null例4、已知试通过求对偶问题的最优解来求解原问题的最优解。解：对偶问题为null用图解法求出： Y*=（1 . 3）， W=11。 将y*1=1， y*2=3 代入对偶约束条件， （1）（2）（5）式为紧约束，（3）（4）为松约束。 令原问题的最优解为X* = （x1.x2.x3.x4.x5），则根据互补松弛条件，必有x3 = x4 =0(1 . 3)（1）（2）（3）（4）（5）null 又由于y*1＞0， y*2 ＞0，原问题的约束必为等式，即化简为此方程组为无穷多解 令x5 =0,得到x1=1，x2=2 即X*1 =（1.2.0.0.0）为原问题的 一个最优解，Z=11。 再令 x5 =2/3，得到x1=5/3，x2=0 即X*2 （5/3.0.0.0.2/3） 也是原问题的一个最优解，Z=11。null例5、已知原问题的最优解为X* =（0.0.4），Z=12 试求对偶问题的最优解。 解：（1）（2）（3）null将X* =（0 . 0 . 4）代入原问题中，有下式：所以，根据互补松弛条件，必有y*1= y*2=0，代入对偶问题 （3）式， y3 =3。因此，对偶问题的最优解为 Y*=（0 . 0 . 3），W=12。null6、对偶问题的解利用原问题的最优单纯形表和改进单纯形表求解对偶问题的最优解。⑴.设原问题为： maxZ=CX AX ≤ b X≥0 引入xs ，构建初始基变量，然后，用单纯形法求解。当检验数满足σj≤0 ，则求得最优解。此时， xs对应的σjs 为- Y* ，故求对偶Y* ，只要将最优单纯形表上xs 对应的检验数反号即可。null例一、null初 始 表最终表null 由上表可知： X*=（50/7 . 200/7），Z=4100/7 对偶问题的最优解： Y*=（0 . 32/7 . 6/7），W=4100/7 也就是外加工时的收费标准。⑵.设原问题： maxZ=CX AX=b X≥0 此时，矩阵A中没有现成的矩阵I，必须通过加入人工变量来凑一个单位矩阵，再用大M法或两阶段法求解。 如何求Y* ，经分析得出如下结论： σB =0 最优基变量检验数向量 σI =CI －CB B-1 初始基变量检验数向量 σD = CD －CB B-1D 非基变量检验数向量 所以， Y* = CI － σI null例二、nullnull 所以， X*=（4 . 1 . 9），Z = 2 ∴ y*1= (0－ σ4 )=1/3 y*2=(－M－ σ6 )= －M－(1/3－M)=－1/3 y*3 =(－M－ σ7 )= －M－(2/3－ M)=－2/3 Y*=（1/3 . －1/3 . －2/3） W = 2 初始基变量的检验数σ4 =－1/3，σ6 =1/3－M, σ7 =2/3－M三、对偶问题的经济解释——影子价格 三、对偶问题的经济解释——影子价格 定义：在一对 P 和 D 中，若 P 的某个约束条件的右端项常数bi 增加一个单位时，所引起的目标函数最优值Z* 的改变量y*i 称为第 i 个约束条件的影子价格，又称为边际价格。 null 设：B是问题 P的最优基，由前式可知， Z*=CB B-1b = Y*b =y*1b1+ y*2b2+…+y*Ibi+…+y*mbm 当bi 变为bi+1 时（其余右端项不变，也不影响B），null 目标函数最优值变为： Z′*= y*1b1+ y*2b2+…+y*I （ bi+1 ）+…+y*mbm ∴ △Z*= Z′*－ Z* = y*i 也可以写成： 即y*i 表示Z*对 bi的变化率。 其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量yi 就是第 i 个约束条件的影子价格。 也可以理解为目标函数最优值对资源的一阶偏导数（但问题中所有其它数据都保持不变）。null 若第i 种资源的单位市场价格为mi ，当yi > mi 时，企业愿意购进这种资源，单位纯利为yi－mi ，则有利可图；如果yi < mi ，则企业有偿转让这种资源，，可获单位纯利mi－yi ，否则，企业无利可图，甚至亏损。nullnull多了 32/7nullnull多了 6/7null01 2 3 4 5 6 7 8 1 2 3 4 5 6 ⑴⑵⑶⑷x2 x1(4 2)⑴′ X*=（4 . 2 . 0 . 0. 0 . 4）Y*=（0 . 3/2 . 1/8 . 0）null01 2 3 4 5 6 7 8 1 2 3 4 5 6 ⑴⑵⑶⑷x2 x1(3 3)⑵′少了0.5null01 2 3 4 5 6 7 8 1 2 3 4 5 6 ⑴⑵⑶⑷x2 x1(4.25 1.75)⑶′少了0.25null01 2 3 4 5 6 7 8 1 2 3 4 5 6 ⑴⑵⑶⑷x2 x1(4 2)⑷′四、对 偶 单 纯 形 法四、对 偶 单 纯 形 法 对偶单纯形法是求解线性规划的另一的基本方法。它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。 由对偶理论可以知道，对于一个线性规划问题，我们能够通过求解它的对偶问题来找到它的最优解。null 也就是说，求解原问题（P）时，可以从（P）的一个基本解（非基可行解）开始，逐步迭代，使目标函数值（Z=Y b= CB B-1b =CX）减少，当迭代到 XB=B-1b≥0时，即找到了（P）的最优解，这就是对偶单纯形法。 同原始单纯形求法一样，求解对偶问题（D），也可以从（D）的一个基本可行解开始，从一个基本可行解（迭代）到另一个基本可行解，使目标函数值减少。null例一、用对偶单纯形法求解：解：将模型转化为nullnullnull 所以， X*=（2 . 2 . 2 . 0 . 0 . 0）， Z′* =－72， 原问题 Z* =72 其对偶问题的最优解为： Y*= (1/3 . 3 . 7/3)，W*= 72nullnullnull 五、 灵敏度分析 五、 灵敏度分析null求下列LP问题 nullnullnull 求下列LP问题的最优解 nullnull一、 价值系数cj的变化分析一、 价值系数cj的变化分析例：某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划已知最优表如下。 （1）确定x2的系数c2的变化范围，使原最优解保持最优； （2）若c2=6，求新的最优计划。 nullnullσ4 = c2－5 ≤ 0 σ5 = 5－2c2 ≤ 0 5/2 ≤ c2 ≤ 5最优解X*=（35，10，25，0，0）保持不变。（1）nullx1*=45/2，x2*=45/2，x4*=25/2，x3*= x5*=0，z*=495/2（2）二、右端常数bi的变化分析二、右端常数bi的变化分析XB= B－1b例：对于上例中的线性规划作下列分析： （1）b3在什么范围内变化，原最优基不变？ （2）若b3=55，求出新的最优解。 nullnull解得40≤b3≤50，即当b3∈[40，50] 时，最优基B 不变null（2）当 b3= 55 时 =nullnullnullnull四、 增加新的约束条件的分析 例2.11 假设在例2.8中，还要考虑一个新的资源约束：4x1+2x2≤1504x1+2x2+x6=150X*=（35，10，25，0，0）Tnull4x1+2x2+x6=150nullnull五、 其它变化情况的分析 1. cj和bi同时变化的情况例2.12 在例2.8中，假定c2由4上升为6，b3增加到55，试问最优解将会发生什么变化？代替最优表的b列，并把c2改为6null原问题与对偶问题均非可行解，表中第一方程是 x3+2x4－5x5=－25， 两边乘以（-1），得： －x3－2x4+5x5=25， 再引入人工变量x6： －x3－2x4+5x5+x6=25 以x6为基变量，增添第6列，应用大M法继续求解。null新的最优计划产量为x1*=30，x2*=20，z*=270。 －x3－2x4+5x5+x6=25null2. 技术系数aij的变化 例2.13 在例2.8中，第一种产品的消耗系数改变为 ，价值系数不变，求新的最优解。 nullnull