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

《《对偶线性规划》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《对偶线性规划》PPT课件.ppt（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、22.1 线性规划的对偶理论线性规划的对偶理论 2.1.1 线性规划原问题与对偶问题的表达形式线性规划原问题与对偶问题的表达形式 任何线性规划问题都有其对偶问题 对偶问题有其明显的经济含义0, B15232A 25322. .432)(max 1 . 1 . 2 4321432143214321xxxxxxxxxxxxtsxxxxxf资源资源例 假设有商人要向厂方购买资源A和B，问他们谈判原料价格的模型是怎样的？3 例例2.1.1 设A、B资源的出售价格分别为 y1 和 y2 显然商人希望总的收购价越小越好 工厂希望出售资源后所得不应比生产产品所得少0, 4 423 3 332 2 22 1

2、12. .2121212121yyyyyyyyyyts的所得产品的所得产品的所得产品的所得产品目标函数 min g(y)=25y1+15y20, B15232A 25322. .432)(max4321432143214321xxxxxxxxxxxxtsxxxxxf资源资源4 2.1.1 线性规划原问题与对偶问题的表达形式线性规划原问题与对偶问题的表达形式0XbAXCX. .)(max :tsxf原问题0YCYAYb. .)(min :tsyg对偶问题TmnmTnbbbcccyyyxxx),(),(),(),(21212121bCYX上两式中mnmmnnaaaaaaaaaA2122221112

3、115 2.1.1 线性规划原问题与对偶问题的表达形式线性规划原问题与对偶问题的表达形式0,. .)(min21221122222112112211112211mnmmnnnmmmmmmyyycyayayacyayayacyayayatsybybybyg把对偶问题展开0YCYAYbYTTTTTtsg. .)(min :对偶问题习惯写为6 2.1.2 (max,(max, ) )标准型的对偶变换标准型的对偶变换 目标函数由 max 型变为 min 型 对应原问题每个约束行有一个对偶变量 yi，i=1,2,m 对偶问题约束为 型，有 n 行 原问题的价值系数 C 变换为对偶问题的右端项 原问题的右

4、端项 b 变换为对偶问题的价值系数 原问题的技术系数矩阵 A 转置后成为对偶问题的技术系数矩阵矩阵 原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义7 2.1.3 非标准型的对偶变换非标准型的对偶变换0,510342023. .54)(max 2 . 1 . 2 1221212121xxxxxxxxtsxxxf不限原线性规划问题例 0, 551033420223. .554)(max)(max, 221221221221221221xxxxxxxxxxxxxxxtsxxxxf型标准问题化为0,532532443. .551020)(min 4321432

5、1432143214321wwwwwwwwwwwwwwwwtswwwwwh则应用标准型对偶变换规不限经整理得令32143213213214332211, 0, 0532443. .51020)(min:, yyywyyyyyytsyyyygwwywywy8 表表2.1.1 对偶变换的规则对偶变换的规则 约束条件的类型与非负条件对偶 非标准的约束条件类型对应非正常的非负条件 对偶变换是一一对应的原问题(max,)对偶问题(min,)技术系数矩阵 A技术系数矩阵 AT价值系数 C右端项 b右端项 b价值系数 C第 i 行约束条件为 型对偶变量 yi 0第 i 行约束条件为 型对偶变量 yi 0第

6、i 行约束条件为 = 型对偶变量 yi 不限决策变量 xj 0第 j 行约束条件为 型决策变量 xj 0第 j 行约束条件为 型决策变量 xj 不限第 j 行约束条件为 = 型9 弱弱对偶定理推论对偶定理推论 max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限； min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限 如果原max(min)问题为无界解，则其对偶min (max)问题无可行解 如果原max(min)问题有可行解，其对偶min (max)问题无可行解，则原问题为无界解10 2.2.2 最优解判别最优解判别定理定理定理定理 若原问题的某个可行解X0的目标

7、函数值与对偶问题某个可行解Y0的目标函数值相等，则X0, Y0分别是相应问题的最优解证证：由弱对偶定理推论1，结论是显然的。 即CX0 = Y0b CX, Y0b = CX0 Yb 。 证毕证毕。 2.2.3 主对偶主对偶定理定理定理定理 如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。证证：由弱对偶定理推论1可知，原问题和对偶问题的目标函数有界，故一定存在最优解。 现证明定理的后一句话。 11 主对偶主对偶定理的证明定理的证明 证证：现证明定理的后一句话。 设 X0 为原问题的最优解，它所对应的基矩阵是 B， X0= B1 b，则其检验数满足 C CBB1A

8、 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

9、, 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分别是原问题和对偶问题最优解。反之亦然。 证毕证毕。miuynjxviijj, 2 , 10, 2 , 10000013 2.2.5 原问题检验数与对偶问题的解原问题检验数与对偶问题的解 在主对偶定理

10、的证明中我们有：对偶(min型)变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值 容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值 由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。 更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量虚变量(松弛或剩余) 的检验数对应其对偶问题实变量实变量 (对偶变量)的最优解，原问题实变量实变量(决策变量) 的检验数对应其对偶问题虚变量虚变量 (松弛或剩余变量)的最优解。因此，原问题或对偶问题只需要求解其中之一就可以了。14 例2.2.3 原问题检验数与

11、对偶问题的解不限原问题321321321321321, 0,101632182. .635)(max :xxxxxxxxxxxxtsxxxxf不限对偶问题321321321321321, 0,633252. .101618)(min :yyyyyyyyyyyytsyyyyg15Cj 536-600 MCBXBbx1x2x 3x 3x4x5x60 x41 8121 11000 x51 621(3 ) 3010 Mx61 0111 1001O B J= 1 0 M M M MM00 Mcj - zj5 + M3 + M6 + M-6 -M0000 x43 8 /31 /35 /3001 1 /30

12、6x 31 6 /32 /31 /31 101 /30 Mx61 4 /31 /3(2 /3 )000 1 /31O B J=3 2 -1 4 M /34 -M /32 -2 M /36 602 + M /3 Mcj - zj1 + M /31 + 2 M /3000-2 -M /300 x41 1 /200011 /2 5 /26x 33(1 /2 )01 101 /2 3 /23x271 /21000 1 /23 /2O B J=3 99 /236 603 /23 /2cj - zj1 /20000 3 /2-M -3 /20 x44001 111 35x16102 201 13x2401

13、 1(1 )0 12O B J=4 2537 702 1cj - zj00 110 2-M + 10 x48010010 15x11 412000 13 6x 3401 110 12O B J=4 6546 6013cj - zj0 1000 1-M 3对 偶 问 题 最 优 解 ：y4= 0y5= 1y6= 0y1= 0y2= 1y3= 3原 问 题 最 优 解 ： x1= 1 4 , x2= 0 , x3= -4 , x4= 8 , x5= 0 , x6= 0 , O B J = 4 616Cj 18161000MCBYBby1y2y3y4y5y60y4-5-1-2-11000y5-3-2

14、-1-1010My6613(1)001OBJ=6MM3MM00Mcj - zj18-M16-3M10-M0000y410(1)01010y53-12001110y36131001OBJ=601030100010cj - zj8-14000M-1016y210101010y51-300-21-110y33101-30-2OBJ=46101610-140-4cj - zj800140M4原问题最优解：x4=8x5=0 x6=0 x1=14x2=0 x3=4对偶问题最优解：y1=0, y2=1, y3=3, y4=0, y5=1, y6=0, OBJ=46172.3 对偶单纯型算法对偶单纯型算法 2

15、.3.1 基本思路基本思路原单纯型迭代要求每步都是基础可行解达到最优解时，检验数 cjzj 0 (max) 或 cjzj 0 (min)但对于(min, )型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决大M法和二阶段法较繁能否从剩余变量构成的初始基础非可行解出发迭代，但保证检验数满足最优条件， cjzj 0 (max) 或 cjzj 0 (min) 每步迭代保持检验数满足最优条件，但减少非可行度 如何判断达到最优解 如何保证初始基础解满足最优条件 为什么叫对偶单纯型法b=B1b018 2.3.2 迭代步骤迭代步骤1确定出变量确定出变量 找非可行解中最小者，即 min bi |

16、 bi 0，不会破坏最优解 若 aij 0，必须保证 cj zj 034ijijjijjiijiijjjNjjiijjNjijijmkkkjjjaqzcqizcqaqazczcqazzaaqazx 所以型行约束为对于第即则有变动设则有为非基变量设 , 0 , 0, , 0001035x1, x3为非基变量， q1= 0, q2= 0.25, q3= 1, 故有333123211311175.275.2125.325.325.075.21125.025.313 aaaaaa x2, x4为基变量，x5=100, b1有剩余， 故有5 . 020010011001001412aa 36 2.4.5

17、 新增决策变量的分析新增决策变量的分析 例2.4.2中，若新增产品 x8，问是否生产？ 已知 c8=9, a18=5, a28=4, a38=3 计算 x8 的检验数可知生产是否有利05) 1325. 0405(9318888iiiaqczc结论：生产x8有利。将B1P8加入最优单纯型表中，以x8为入变量进行迭代37 2.4.6 新增约束条件的分析新增约束条件的分析1、将最优解代入新的约束条件，若满足，则最优解不变2、若不满足，则当前最优解要发生变化；将新增约束条件加入最优单纯型表，并变换为标准型3、利用对偶单纯型法继续迭代 为什么可以利用对偶单纯型法x1x2x3x4x5x6x7x8CBXBb

18、153400000 x51001/40-13/4011/4-104x420020-2101-105x2100-3/4(1)11/400-3/4100 x865012330001例2.4.2 第2步3839注意：最优解的目标函数减少了25个单位40 2.4.7 灵敏度分析举例灵敏度分析举例产量 组别单位售价 品种I II III IV V(元)A 产品数量3244010B 产品数量612145C 产品数量265184耗费 组别 资源I II III IV V资源限制工人工时(小时)0461280小时/天机器工时(小时)1121150小时/天每组生产费用(元)481930407例例2.4.3 某工

19、厂生产三种产品A, B, C，有五种生产组合方案。下两表给出有关数据。规定每天供应A产品至少110 个，求收益最大的生产方案。41 例例2.4.3解解：设xj为已选定各种组合方案的组数(j=1,2,5)， x6为A产品的剩余变量， x7，x8分别为工人工时和机器工时的松弛变量。8 , 2 , 1, 0502802641104423.455403020)(max854321754326432154321jxxxxxxxxxxxxxxxxxtsxxxxxxfj42 例例2.4.3 最优解的B1是什么 产品A的影子价为多少 第II组方案的生产费用提高2元，是否要调整生产组别 若工人加班费为1元/小时

20、，是否要采取加班措施 若通过租借机器增加工时，租费的上限应为多少 A产品的订购合同是否有利 若要选用第IV组方案，该组的生产费用应降低多少 若工人加班费为0.3元/小时，最多允许加班时间多少 若机器租费低于44元/小时，问租几部机器才合适(每天8小时计) 若第III组方案使机器工时减少0.5小时，能否被选入432.5 参数线性规划参数线性规划 2.4 节中 aij, bi, cj 只有一个发生变化，多个同时发生变化则很难解析 但在一些特殊情况下，用参数表示变化量，也可以用来进行多个系数的灵敏度分析 2.5.1 参数参数cj的变化分析的变化分析i 第i种资源的单位费用变化量， i 不限i i 变

21、化对 cj 的影响率njxmibxatsxcxfjinjjijjnjijj, 2 , 10 , 2 , 1),(.)(max11 44 例例2.4.2 资源b1变化量1，j=a1jx1x2x3x4x5x6x7CBXBb1-215-313-14-210000 x51001/40-13/4011/4-14-21x420020-2101-15-31x2100-3/4111/400-3/411300 -70014.25-1.7515-315.75-4.2514-2100.25+0.2511-1cj-zj-3.25-0.2510-2.75+3.25100-0.25-0.251-1+10,10003543

22、12004345800232. .)24()3()35()21 ()(max432143214321432141312111xxxxxxxxxxxxxxxxtsxxxxxf45 例例2.4.2 资源b1变化量1 与c5出现多重解现象的检验数的检验数优解在此范围内不会影响最由上单纯型表有要求0 ,8462.00 , 17001300)(max)100,200,100(),(8462.011 011025.025.08462.0025.375.213025.025.3, 0)(316112451111111111xxxfxxxzcjj 的一致结果与的变化范围松弛变量价值系数研究15558462. 0111,25. 375. 2min25. 025. 0,25. 025. 3max ccx46 2.5.2 参数参数 bi 的变化分析的变化分析例2.4.2中，将b1,b2,b3理解为三个车间的周工时资源。假设从第1向2车间调动工人 个，每个工人的周工时为 40小时，问调动多少工人不会破坏最优产品组合03040301002001000 0)( 040400. .)(max245101 NNNBNBNBxxxBXXbBXtsxf即要保证XbAXCX从目标函数中看出什么解得 101300)(533. 333. 3030100504020033. 3030100:bBC1BOBJ