运筹学--对偶线性规划与灵敏分析.pptx

运筹学运筹学 第二章第二章 对偶偶线性性规划与灵敏度分析划与灵敏度分析本章重点本章重点n对偶问题的求解n对偶定理n对偶单纯形法 n灵敏度分析对偶线性规划问题的导出对偶线性规划问题的导出(1)n（前面（前面讲过的生的生产计划划问题）某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的日生产计划单位产品所需原料单位产品所需原料数量（公斤）数量（公斤）产品产品Q1产品产品Q2产品产品Q3原料可用量原料可用量（公斤（公斤/日）日）原料原料P12301500原料原料P2024800原料原料P33252000单位产品的利润单位产品的利润（千元）（千元）354对偶线性规划问题的导出对偶线性规划问题的导出(2)(2)n设每天生产三种产品的数量分别为x1、x2、x3现在三种产品销路不畅，可以将所有的原料外卖，现在要谈判，我们的价格底线是什么？对偶线性规划问题的导出对偶线性规划问题的导出(3)(3)n解决这一问题应考虑u外卖原料获利应不少于生产产品的获利，即出卖能够制造一件产品的原料的获利应该不少于生产一件该产品的获利u价格应该尽可能低，这样才有竞争力u价格应该是非负的n设出租或外卖三种原料的价格分别为y1、y2、y3对偶线性规划问题的导出对偶线性规划问题的导出(4)(4)n上述两个线性规划模型是在同一工厂的资源状况和生产状况条件下产生的，是同一问题从不同角度来观察所产生的，因此两者密切相关，我们称这两个线性规划问题互为对偶问题，其中一个问题是另一问题的对偶问题。对偶问题的定义对偶问题的定义(1)n对于线性规划问题（1）对偶问题的定义对偶问题的定义(2)和（2）对偶问题的定义对偶问题的定义(2)n称（1）是（2）的对偶问题；也称（2）是（1）的对偶问题n这种对偶关系称为对称形式的称形式的对偶偶，用矩阵表示为对偶问题的定义对偶问题的定义(3)n还有一种非非对称形式的称形式的对偶偶，用矩阵表示为求对偶问题求对偶问题原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数 MaxZ目标函数 MinW约束条件数：m个第i个约束条件类型为“”第i个约束条件类型为“”第i个约束条件类型为“=”变量数：m个第i个变量0第i个变量0第i个变量是自由变量 变量数：n个第j个变量0第j个变量0第j个变量是自由变量 约束条件数：n个第 j个 约 束 条 件 类 型 为“”第 j个 约 束 条 件 类 型 为“”第j个约束条件类型为“=”示例示例(2.1-1)n写出下面线性规划的对偶规划示例示例(2.1-2)n结果为作业作业(6)n书上99页的2-1对偶定理对偶定理(1)n对偶定理偶定理是揭示原始问题的解与对偶问题的解之间重要关系的一系列定理n定理1 对称性定理u对偶问题的对偶问题是原问题n定理2 弱对偶定理u极大化原问题的任一可行解的目标函数值，不大于其对偶问题的任一可行解的目标函数值对偶定理对偶定理(2)均有可行解，分别为均有可行解，分别为 和和 ，则，则证明：证明：由由(L)，左乘左乘 ，得，得 由由(D)，右乘右乘 ，得，得 设设（L）和和 （D）对偶定理对偶定理(3)n推论1u极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界n推论2u极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界n推论3u若原问题可行，则其目标函数无界的充要条件是对偶问题没有可行解对偶定理对偶定理(4)n推论4u若对偶问题可行，则其目标函数无界的充要条件是原问题没有可行解n定理3 最最优性准性准则定理定理u若 、分别为互为对偶问题的线性规划的可行解，且 ，则 和 分别是相应线性规划问题的最优解对偶定理对偶定理(5)CXbTYT弱对偶弱对偶定定 理理已已 知知结论结论最优解定义最优解定义X=Y=特别取特别取证证 明明CXCXC对偶定理对偶定理(6)n定理4 主主对偶定理偶定理u若原始问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数值相同n证明：u第一部分证明两者均有最优解由于原始问题和对偶问题均可行，根据弱对偶定理知两者均有界，于是均有最优解。u第二部分证明在达到最优时，两个问题的目标函数值相等利用单纯形法的特征，就非对称形式的对偶问题给出对偶定理对偶定理(7)第一步：给出原问题和对偶问题第一步：给出原问题和对偶问题(L)设原问题有对应于最优基B的最优基本可行解X=(XB,0)T,则有XB=B-1b(D)对偶定理对偶定理(8)第第二二步步：利利用用单单纯纯形形法法的的矩矩阵阵描描述述，由由单单纯纯形形法法最最优优性性判判别别定定理理得得出出重重要要结结论论 ,并并引出引出“单纯形乘子单纯形乘子”的定义的定义 ；定义 （最优单纯形乘子）令 A=（B,N），所以对应于最优基B的检验数满足 对偶定理对偶定理(9)第三步：证明最优单纯形乘子就是对偶问题的第三步：证明最优单纯形乘子就是对偶问题的可行解可行解所以，是对偶问题的可行解对偶定理对偶定理(10)第四步：进一步证明第四步：进一步证明 是对偶问题的最优解，是对偶问题的最优解，并验证两个问题的目标函数值相等。并验证两个问题的目标函数值相等。又又根根据据最最优优性性准准则则定定理理，这这时时的的 正正是是对对偶偶问问题题的最优解。的最优解。对偶最优解的经济含义对偶最优解的经济含义影子价格影子价格(1)n前面已经讲过，生产计划问题的对偶问题是资源定价问题。n该对偶问题的最优解代表的是工厂在当前的资源状况b，技术状况A和市场状况C已知的情况下，单位资源对企业的价值。n若X*=(x1*,x2*,xn*)T 和 Y*=(y1*,y2*,ym*)分别是生产计划问题和资源定价问题的最优解，根据主对偶定理，其最优值相等。即对偶最优解的经济含义对偶最优解的经济含义影子价格影子价格(2)n由此可知n若把Z*看作b1,b2,bm的函数，则由 可知，yi*是资源bi 价值的一种度量，称为bi 的影子价格影子价格，其含义是在其他条件不变的情况下，最优目标值随资源数量变化的变化率。对偶最优解的经济含义对偶最优解的经济含义影子价格影子价格(3)n影子价格所包含的信息u资源紧缺状况（越紧缺的资源价格越高）u确定资源转让基价u取得紧缺资源的代价由原问题最优单纯形表由原问题最优单纯形表求对偶问题最优解求对偶问题最优解n由检验数的计算方法可知n设B是原线性规划问题的最优基，则 是其对偶问题的最优解n若A中有单位子矩阵，该子矩阵对应的列为第i1,i2,im(i1i2 0 时，以xj为入基变量，用单纯形法继续迭代求出新的最优解B-1bIB-1N-CBB-1b0CN-CBB-1Nj=cj-CBB-1PjCB中的某个中的某个cj发生变化发生变化n从最优表中可以看出，CB中的某个cj发生变化时，影响最优值和所有的检验数N（N=CN-CBB-1N）u当N 0 时，最优基不变，最优解不变，最优值改变u若有某个j 0，以xj为入基变量，用单纯形法继续迭代求出新的最优解B-1bIB-1N-CBB-1b0CN-CBB-1NC中的某个中的某个cj发生变化发生变化ncj变化相当于生产问题中该产品的价格变动n当某个cj变化时，如能保持N 0，则当前解仍为最优解，否则可用单纯形法继续迭代求出新的最优解n将这个cj看作待定参数，令N=CN-CBB-1N0，解这n-m个不等式，可算出保持最优解不变时该cj的变化范围nC中多个 cj 发生变化时，其处理方法是u分别计算这几个 cj 变化对最优表的影响u根据计算结果决定是最优基不变或是继续迭代示例示例(2.4-1)n有如下的线性规划问题和其最优表，试求若c3由24变为26时，最优解和最优值是多少？若c1由40变为35时呢？2001-1/31-2/320101-11-170000-1-5-10示例示例(2.4-2)n当c3由24变为26时示例示例(2.4-3)n修改最优表为2001-1/31-2/320101-11-1700001-5-1080/31/3102/3-1/320101-11-1720-100-4-11示例示例(2.4-4)n得最优解为ux1=0，x2=80/3，x3=20umaxf(X)=1720示例示例(2.4-5)n当c1由40变为35时示例示例(2.4-6)n修改最优表为2001-1/31-2/320101-11-1600004-10-580/31/3102/3-1/320101-11-1680-400-6-9示例示例(2.4-7)n得最优解为ux1=0，x2=80/3，x3=20umaxf(X)=1680b中的某个中的某个bi发生变化发生变化(1)n从最优表中可以看出，bi 发生变化时，影响所有的解值和最优值u当解值 B-1b0 时，最优基不变，最优解改变，最优值改变u若有某个解值 xj0时，以xj为出基变量，用对偶单纯形法继续迭代求出新的最优解B-1bIB-1N-CBB-1b0CN-CBB-1Nb中的某个中的某个bi发生变化发生变化(2)nbi变化相当于生产问题中该资源的可用量发生变动n把这个 bi 看作待定参数，令B-1b0，解这m个不等式，可算出保持最优解不变时该bi的变化范围nb中多个 bi 发生变化，其处理方法和处理一个 bi 发生变化的方法相同示例示例(2.5-1)n有如下的线性规划问题和其最优表，试求若b1由100变为150时，最优解和最优值是多少？2001-1/31-2/320101-11-170000-1-5-10示例示例(2.5-2)n当b1由100变为150时示例示例(2.5-3)n修改最优表为7001-1/31-2/3-30101-11-195000-1-5-1040112/301/330-10-11-1-1800-50-60-15示例示例(2.5-4)n得最优解为ux1=0，x2=40，x3=0umaxf(X)=1800增加一个新的变量增加一个新的变量xn+1(1)n增加一个新的变量xn+1，需要增加cn+1、Pn+1，也就是说，将在最优表中增加一列，这样就增加了一个检验数n+1(n+1=cn+1-CBB-1Pn+1)u当n+10 时，最优基不变，最优解不变，最优值也不变u当n+1 0 时，以xn+1为入基变量，用单纯形法继续迭代求出新的最优解B-1bIB-1N-CBB-1b0CN-CBB-1N增加一个新的变量增加一个新的变量xn+1(2)n增加一个新的变量，相当于生产问题中有新的产品可以生产n若增加多个新变量，则相当于在最优表中增加多个列，这样就增加了多个检验数，根据检验数的值判定是否需要继续迭代示例示例(2.6-1)n有如下的线性规划问题和其最优表，试求若增加一个变量x4(c4=40,P4=(3,2)T)时，最优解和最优值是多少？2001-1/31-2/320101-11-170000-1-5-10示例示例(2.6-2)n当增加一个变量x4(c4=40,P4=(3,2)T)时示例示例(2.6-3)n修改最优表为2001-1/35/31-2/320101-1-11-170000-15-5-101203/5-1/513/5-2/53213/54/50-2/53/5-17600-300-8-8示例示例(2.6-4)n得最优解为ux1=32，x2=0，x3=0，x4=12umaxf(X)=1760增加一个约束增加一个约束(1)n增加一个约束，相当于生产问题中出现了新的生产限制n将原最优解代入新增的约束检查是否满足约束条件u满足，则说明新增约束不影响最优解u否则，把新的约束添加到最优表中新的一行，经过调整，会得到一个对偶单纯形表，用对偶单纯形法继续迭代求解增加一个约束增加一个约束(2)n若增加多个新约束u先判断最优解是否满足这些约束u将不满足的约束添加到最优表中新的若干行，经过调整，会得到一个对偶单纯形表，用对偶单纯形法继续迭代求解示例示例(2.7-1)n有如下的线性规划问题和其最优表，试求若增加一个约束x1+2x2+x350，最优解和最优值是多少？2001-1/31-2/320101-11-170000-1-5-10示例示例(2.7-2)n增加一个约束x1+2x2+x350，原最优解不满足这个约束n把新的约束添加到最优表中新的一行，得2001-1/31-2/3020101-11050121001-170000-1-5-1002001-1/31-2/3020101-110-10002/3-11/31-170000-1-5-100示例示例(2.7-3)n调整后为10011/30-1/3130101/302/3-11000-2/31-1/3-1-165000-13/30-35/3-5示例示例(2.7-4)n得最优解为ux1=30，x2=10，x3=0umaxf(X)=1650A中某个元素中某个元素aij发生变化发生变化(1)n分为两种情况讨论uaij 位于B中B中元素发生变化，最优表中各项元素都将发生变化，一般进行重新求解uaij 位于N中影响最优表第j列的所有元素值，相当于整个 Pj 发生变化要判断j（j=cj-CBB-1Pj）是否非正当j0 时，最优基不变，最优解不变，最优值也不变当j 0 时，以xj为入基变量，用单纯形法继续迭代求出新的最优解B-1bIB-1N-CBB-1b0CN-CBB-1NA中元素发生变化中元素发生变化(2)nA中某个元素aij发生变化，相当于生产问题中某个技术参数发生了变化n若A中多个元素发生变化u先判断发生变化的元素位于哪几列中若有元素位于最优基中，则重新求解若所有发生变化的元素都不在最优基中，则修改相应列的元素值，再根据修改后的表中检验数的值，决定是否使用单纯形法继续迭代求解示例示例(2.8-1)n有如下的线性规划问题和其最优表，试求若a23的值由2变为1，最优解和最优值是多少？2001-1/31-2/320101-11-170000-1-5-10示例示例(2.8-2)n当a23的值由2变为1时示例示例(2.8-3)n修改最优表为20011/31-2/320100-11-1700009-5-10600313-220100-11-22400-270-328示例示例(2.8-4)n得最优解为ux1=0，x2=0，x3=100umaxf(X)=24001002311020100-11-2400-8-270-240作业作业(8)n书上100页2-2的的最优表如下n若a21由0变为12，b2由 5变为10，最优解和最优值是多少？32/501-2/51/51-1/5101/5-3/527-7/500-13/5-1/5思考题思考题n对于极小化问题，能否不化为极大化问题，直接用单纯形法或对偶单纯形法求解？