《对偶线性规划》PPT课件.ppt

1,第二章线性规划的对偶理论及其应用,窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象,2,2.1 线性规划的对偶理论 2.1.1 线性规划原问题与对偶问题的表达形式,任何线性规划问题都有其对偶问题对偶问题有其明显的经济含义,假设有商人要向厂方购买资源A和B，问他们谈判原料价格的模型是怎样的？,3,例,设A、B资源的出售价格分别为 y1 和 y2显然商人希望总的收购价越小越好工厂希望出售资源后所得不应比生产产品所得少,目标函数 min g(y)=25y1+15y2,4,2.1.1 线性规划原问题与对偶问题的表达形式,5,2.1.1 线性规划原问题与对偶问题的表达形式,6,2.1.2(max,)标准型的对偶变换,目标函数由 max 型变为 min 型对应原问题每个约束行有一个对偶变量 yi，i=1,2,m对偶问题约束为 型，有 n 行原问题的价值系数 C 变换为对偶问题的右端项原问题的右端项 b 变换为对偶问题的价值系数原问题的技术系数矩阵 A 转置后成为对偶问题的技术系数矩阵矩阵原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义,7,2.1.3 非标准型的对偶变换,8,表2.1.1 对偶变换的规则,约束条件的类型与非负条件对偶非标准的约束条件类型对应非正常的非负条件对偶变换是一一对应的,9,弱对偶定理推论,max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限；min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限如果原max(min)问题为无界解，则其对偶min(max)问题无可行解如果原max(min)问题有可行解，其对偶min(max)问题无可行解，则原问题为无界解,10,2.2.2 最优解判别定理,定理 若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0,Y0分别是相应问题的最优解证：由弱对偶定理推论1，结论是显然的。即CX0=Y0b CX,Y0b=CX0 Yb。证毕。,2.2.3 主对偶定理定理 如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。证：由弱对偶定理推论1可知，原问题和对偶问题的目标函数有界，故一定存在最优解。现证明定理的后一句话。,11,主对偶定理的证明,证：现证明定理的后一句话。设 X0 为原问题的最优解，它所对应的基矩阵是 B，X0=B1 b，则其检验数满足 C CBB1A 0 令 Y0=CBB1，则有 Y0 A C。显然Y0为对偶问题的可行解。因此有对偶问题目标函数值，g(Y0)=Y0b=CBB1 b 而原问题最优解的目标函数值为 f(X0)=CX0=CBB1 b故由最优解判别定理可知Y0 为对偶问题的最优解。证毕。该定理的证明告诉我们一个非常重要的概念：对偶变量的最优解等于原问题松弛变量的机会成本。即对偶变量的最优解是原问题资源的影子价格,12,2.2.4 互补松弛定理,定理 设X0,Y0分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、V0为对偶问题剩余变量的值。X0,Y0分别是原问题和对偶问题最优解的充分必要条件是 Y0 U0+V0 X0=0证：由定理所设，可知有 A X0+U0=b X0,U0 0(1)Y0 A V0=C Y0,V0 0(2)分别以Y0左乘(1)式，以X0右乘(2)式后，两式相减，得 Y0 U0+V0 X0=Y0 b C X0若 Y0 U0+V0 X0=0，根据最优解判别定理，X0,Y0分别是原问题和对偶问题最优解。反之亦然。证毕。,13,2.2.5 原问题检验数与对偶问题的解,在主对偶定理的证明中我们有：对偶(min型)变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛或剩余)的检验数对应其对偶问题实变量(对偶变量)的最优解，原问题实变量(决策变量)的检验数对应其对偶问题虚变量(松弛或剩余变量)的最优解。因此，原问题或对偶问题只需要求解其中之一就可以了。,14,例2.2.3 原问题检验数与对偶问题的解,15,16,17,2.3 对偶单纯型算法,2.3.1 基本思路原单纯型迭代要求每步都是基础可行解达到最优解时，检验数 cjzj 0(max)或 cjzj 0(min)但对于(min,)型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决大M法和二阶段法较繁能否从剩余变量构成的初始基础非可行解出发迭代，但保证检验数满足最优条件，cjzj 0(max)或 cjzj 0(min)每步迭代保持检验数满足最优条件，但减少非可行度如何判断达到最优解如何保证初始基础解满足最优条件为什么叫对偶单纯型法,18,2.3.2 迭代步骤,确定出变量找非可行解中最小者，即 min bi|bi0，设第 i*行的最负，则i*行称为主行，该行对应的基变量为出变量，xi*确定入变量最大比例原则,设 j*列满足(2.3.1)式，j*列称为主列，xj*为出变量 以主元 ai*j*为中心迭代 检查当前基础解是否为可行解 若是，则当前解即为最优解 否则，返回步骤 1,19,例2.3.1 对偶单纯型解法,解：化原问题为适合对偶解法的标准型,20,表2.3.1 对偶单纯型法的单纯型表(min),答：最优解为x1=14,x3=8,x2=x4=0,OBJ=14,21,2.4 灵敏度分析,灵敏度分析又称为后优化分析,22,2.4 线性规划的灵敏度分析,线性规划是静态模型参数发生变化，原问题的最优解还是不是最优哪些参数容易发生变化C,b,A每个参数发生多大的变化不会破坏最优解灵敏度越小，解的稳定性越好,23,2.4.1 边际值(影子价)qi,以(max,)为例边际值(影子价)qi 是指在最优解的基础上，当第 i 个约束行的右端项 bi 减少一个单位时，目标函数的变化量,24,例,25,关于影子价的一些说明,影子价是资源最优配置下资源的理想价格，资源的影子价与资源的紧缺度有关松弛变量增加一个单位等于资源减少一个单位剩余变量增加一个单位等于资源增加一个单位资源有剩余，在最优解中就有对应松弛变量存在，且其影子价为 0影子价为 0，资源并不一定有剩余应用，邮电产品的影子价格,26,2.4.2 价值系数 cj 的灵敏度分析,cj 变动可能由于市场价格的波动，或生产成本的变动cj 的灵敏度分析是在保证最优解的基变量不变的情况下，分析cj 允许的变动范围cj cj 的变化会引起检验数的变化，有两种情况非基变量对应的价值系数变化，不影响其它检验数基变量对应的价值系数变化，影响所有非基变量检验数1、非基变量对应的价值系数的灵敏度分析,27,例,28,2、基变量对应的价值系数的灵敏度分析,由于基变量对应的价值系数在CB中出现，因此它会影响所有非基变量的检验数只有一个基变量的 cj 发生变化，变化量为 cj 令 cj 在CB中的第k行，研究非基变量xj 机会成本的变化,29,设x4的价值系数增加c4，对应k=2，,有一边为空集如何处理,为什么akj=0不出现在任何一边的集合中,与对偶单纯型法找入变量的公式一样,30,2.4.3 右端项 bi 的灵敏度分析,设XB=B1b是最优解，则有XB=B1b0b的变化不会影响检验数b的变化量b可能导致原最优解变为非可行解,31,2.4.3 右端项 bi 的灵敏度分析,32,以b2为例,x6是对应的初始基变量，所以有,33,2.4.4 技术系数 aij 的灵敏度分析,技术系数aij变化的影响比较复杂对应基变量的 aij，且资源bi已全部用完对应基变量的 aij，但资源bi未用完 对应非基变量的 aij，且资源bi全用完或未用完1、对应基变量的 aij，且资源bi已全部用完 aij=02、对应基变量的 aij，但资源bi未用完 aijxn+i/xj上述两个公式不充分，为什么？B1发生变化，从而引起非基变量检验数 cj zj 的变化3、对应非基变量的 aij只影响对应非基变量xj的检验数 cj zj 若 aij 0，不会破坏最优解若 aij 0，必须保证 cj zj 0,34,35,x1,x3为非基变量，q1=0,q2=0.25,q3=1,故有,x2,x4为基变量，x5=100,b1有剩余，故有,36,2.4.5 新增决策变量的分析,例中，若新增产品 x8，问是否生产？已知 c8=9,a18=5,a28=4,a38=3计算 x8 的检验数可知生产是否有利,结论：生产x8有利。将B1P8加入最优单纯型表中，以x8为入变量进行迭代,37,2.4.6 新增约束条件的分析,1、将最优解代入新的约束条件，若满足，则最优解不变2、若不满足，则当前最优解要发生变化；将新增约束条件加入最优单纯型表，并变换为标准型3、利用对偶单纯型法继续迭代为什么可以利用对偶单纯型法,例2.4.2 第2步,38,39,注意：最优解的目标函数减少了25个单位,40,2.4.7 灵敏度分析举例,例 某工厂生产三种产品A,B,C，有五种生产组合方案。下两表给出有关数据。规定每天供应A产品至少110 个，求收益最大的生产方案。,41,例,解：设xj为已选定各种组合方案的组数(j=1,2,5)，x6为A产品的剩余变量，x7，x8分别为工人工时和机器工时的松弛变量。,42,例,最优解的B1是什么产品A的影子价为多少第II组方案的生产费用提高2元，是否要调整生产组别若工人加班费为1元/小时，是否要采取加班措施若通过租借机器增加工时，租费的上限应为多少A产品的订购合同是否有利若要选用第IV组方案，该组的生产费用应降低多少若工人加班费为0.3元/小时，最多允许加班时间多少若机器租费低于44元/小时，问租几部机器才合适(每天8小时计)若第III组方案使机器工时减少0.5小时，能否被选入,43,2.5 参数线性规划,2.4 节中 aij,bi,cj 只有一个发生变化，多个同时发生变化则很难解析但在一些特殊情况下，用参数表示变化量，也可以用来进行多个系数的灵敏度分析 2.5.1 参数cj的变化分析i 第i种资源的单位费用变化量，i 不限i i 变化对 cj 的影响率,44,例2.4.2 资源b1变化量1，j=a1j,45,例2.4.2 资源b1变化量1 与c5,46,参数 bi 的变化分析,例中，将b1,b2,b3理解为三个车间的周工时资源。假设从第1向2车间调动工人 个，每个工人的周工时为 40小时，问调动多少工人不会破坏最优产品组合,