第二章对偶问题与灵敏度分析 ppt
- 1. 11/25管理科学与工程学院第二章 对偶问题与灵敏度分析
- 2. 11/25管理科学与工程学院要求了解LP对偶问题的实际背景 了解对偶问题的建立规则与基本性质 掌握对偶最优解的计算及其经济解释 掌握LP的灵敏度分析
- 3. 11/25管理科学与工程学院一、 对偶问题的提出 第一节 线性规划的对偶问题 对偶性是线性规划问题的最重要的内容之一。每一个线性规划（ LP ）必然有与之相伴而生的另一个线性规划问题，即任何一个求 maxZ 的LP都有一个求 minZ 的LP。其中的一个问题叫“原问题”，记为“P”，另一个称为“对偶问题”，记为“D”。对偶现象先是物理学中提到的正负之分，这是丁兆中提出的。现实生活中，有线性规划，则有对偶规划。
- 4. 11/25管理科学与工程学院例一、资源的合理利用问题 已知资料如表所示，问应如何安排生产计划使得既能充分利用现有资源有使总利润最大？1810单件利润150（设备）51C100（煤炭）32B170（钢材）25A资源限制乙甲单件 产 消耗 品 资源
- 5. 11/25管理科学与工程学院 下面从另一个角度来讨论这个问题： 假定：该厂的决策者不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于接受外来加工任务，只收取加工费。试问该决策者应制定怎样的收费标准（合理的）？
- 6. 11/25管理科学与工程学院 分析问题： 1、每种资源收回的费用不能低于自己生产时的可获利润； 2、定价又不能太高，要使对方能够接受。
- 7. 11/25管理科学与工程学院 一般而言，W 越大越好，但因需双方满意，故为最好。该问题的数学模型为：
- 8. 11/25管理科学与工程学院模型对比：
- 9. 11/25管理科学与工程学院例题二：美佳公司制造Ⅰ 、 Ⅱ两种产品，其有关情况如下表：ⅠⅡ 每天可用能力设备A(h)0515设备B(h)6224调试工序(h)115利润(元)21问题的两个方面:生产、不生产而出让原材料与设备等。
- 10. 11/25管理科学与工程学院max Z=2X1+X2 5X2≤15 6X1+2X2 ≤24 X1+X2≤5 X1，X2≥0一方面生产：线性规划问题为求利润最大的生产计划问题，设生产Ⅰ 、 Ⅱ产品分别为数学模型为： X1，X2。
- 11. 11/25管理科学与工程学院另一方面不生产：因为激烈的市场竞争，产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是多少？单位时间的设备A，设备B，调试工序的出让价分别用y1y2y3代表。前提条件：出让价≥盈利价ⅠⅡ可用/天设备A(h)0515设备B(h)6224调试工序(h)115利润(元)216y2+y3 ≥2对产品Ⅰ而言为：对产品Ⅱ而言为：5y1+ 2y2+y3 ≥1价格底线为：Min Z=15y1+24y2+5y3 Yi ≥0（i=1，2，3）
- 12. 11/25管理科学与工程学院minZ=15y1+24y2+5y3 6y2+y3 ≥2 5y1+ 2y2+y3 ≥1 yi ≥0（i=1，2，3） 线性规划为：此为原线性规划问题的对偶问题
- 13. 11/25管理科学与工程学院二、对称形式下对偶问题的一般形式原问题 max Z=CX AX ≤b X ≥0对偶问题minω=Y′b A ′Y≥C ′ Y ≥0
- 14. 11/25管理科学与工程学院例题max Z=17x1+20x2+16x3 30x1+24x2+13x3 ≤3 15x1+17x2+19x3 ≤2 18x1+22x2+26x3≤4 x1,x2,x3≥ 0其对偶问题为：min w=3y1+2y2+4y3 30y1+15y2+18y3 ≥ 17 24y1+17y2+22y3 ≥ 20 13y1+19y2+26y3 ≥ 16 y1，y2，y3 ≥0
- 15. 11/25管理科学与工程学院原问题有m个约束条件，对偶问题有m个变量 原问题有n个变量，对偶问题有n个 约束条件 原问题的价值系数对应对偶问题的右端项 原问题的右端项对应对偶问题的价值系数 原问题的技术系数矩阵转置后为对偶问题系数矩阵 原问题与对偶问题优化方向相反对偶规则
- 16. 11/25管理科学与工程学院三、非对称形式的原-对偶问题关系LPDPmax Z=CX AX =b X ≥0min ω=Yb YA ≥C Y 为自由变量事实上，约束条件为等式的线性规划问题。如果约束条件为等式，则对偶问题对应的是自由变量。max Z=CX AX =b X ≥0第一步：先将等式约束条件分解为两个不等式约束条件。AX =bAX ≤ b AX ≥ b AX ≤ b -AX ≤- b①②设 y'是对应①式的对偶变量。y"是对应②式的对偶变量。
- 17. 11/25管理科学与工程学院第二步：按对称形式变换关系，可写出它的对偶问题。对称式min w=min w=（y′-y″）b（ y′-y″）A ≥c y′，y″ ≥0y =y′-y″min w=Yb YA ≥c Y为自由变量 注意：以后不强调等式右段项 b≥0，原因在对偶单纯型表中只保证 而不保证 ，故 b可以是负数。
- 18. 11/25管理科学与工程学院例题：max Z=x1+4x2+3x3 2x1+3x2-5x3 ≤2 ① 3x1-x2+6x3 ≥1 ② x1+x2+x3=4 ③ x1 ≥ 0,x2 ≤0x3无约束解法1：利用变量替换等，使之变成对称式。（1）令x2´=-x2 x2´ ≥ 0，x3=x3´-x3 " x3´，x3" ≥ 0（2） ②式为“≥”，两边乘“-1”，换为“≤”-3x1+x2 ´ -6 x3´+6x3 " ≤- 1（3） ③为“=”化为x1+x2+x3 ≥ 4 ，x1+x2+x3 ≤ 4 即为： -x1+x2 ´ - x3´+x3 " ≤ -4 x1-x2 ´ + x3´-x3 " ≤ 4
- 19. 11/25管理科学与工程学院对称形式为：max Z=x1-4x2 ´ +3 x3´-3x3 " 2x1 -3x2 ´- 5x3´+5x3 " ≤2 -3x1-x2 ´- 6x3´+6x3 " ≤-1 x1 -x2 ´ +x3´ -x3 " ≤4 -x1 +x2 ´ -x3´ +x3 " ≤-4 x1 ，x2 ´，x3´，x3 " ≥ 0对应的对偶变量为：y1，y2 ´，y3 ´，y3 "
- 20. 11/25管理科学与工程学院按对称的对偶问题得到：min w=2y1-y2 ´+4y3 ´-4y3 " 2y1-3y2 ´+y3 ´-y3 " ≥ 1 -3y1-y2 ´-y3 ´+y3 " ≥ -4 -5y1-6y2 ´+y3 ´-y3 " ≥ 3 5y1+6y2 ´-y3 ´+y3 " ≥ -3 y1，y2 ´，y3 ´，y3 " ≥ 0
- 21. 11/25管理科学与工程学院再令：y2=-y2´ y2 ≤ 0 y3= y3 ´-y3 “ y3为无约束min w=2y1+y2 +4y3 2y1+3y2 +y3 ≥ 1 -3y1+y2 -y3 ≥ -4 -5y1+6y2 +y3 = 3 y1 ≥ 0， y2 ≤0 ，y3 无约束3y1-y2 +y3 ≤ 4
- 22. 11/25管理科学与工程学院解法2：利用对应表。 LP（DP） DP（LP） max z A 右端项 价值系数min w A ' 价值系数 右端项 变量 n个 ≥0 ≤0 无约束n个 ≥ ≤ =约束条件约束条件 m个 ≤ ≥ =m个 ≥0 ≤0 无约束 变量max Z=x1+4x2+3x3 2x1+3x2-5x3 ≤2 ① 3x1-x2+6x3 ≥1 ② x1+x2+x3=4 ③ x1 ≥ 0,x2 ≤0x3无约束min w=2y1+y2 +4y32y1+3y2 +y3≥ 13y1 - y2 +y3≤ 4-5y1+6y2 +y3= 3y1 ≥ 0y2 ≤0y3 无约束
- 23. 11/25管理科学与工程学院min Z=2x1+3x2-5x3 +x4 x1+x2-3x3+x4 ≥ 5 ① 2x1 +2x3 -x4≤ 4 ② x2 + x3 +x4=6 ③ x1 ≤ 0,x2，x3 ≥ 0 x4无约束练习求其对偶问题Max w=5y1+4y2 +6y3y1+2y2 y1 +y3-3y1+2y2 +y3y1-y2 +y3≥ 2≤ 3≤ -5=1y1 ≥ 0y2 ≤0y3 无约束
- 24. 11/25管理科学与工程学院min Z=2x1+3x2-5x3+x4 -3x1+x2-2x3+x4=4 x1+2x2-x3+4x4≥6 x1+3x2-x3+4x4≤5 x1,x2≥0,x3≤0,x4无约束 max w = 4y1+6y2+5y3 -3y1+y2+y3 ≤2 y1+2y2+3y3 ≤3 -2y1-y2-y3 ≥-5 y1+4y2+4y3=1 y1自由变量,y2 ≥0,y3 ≤0
- 25. 11/25管理科学与工程学院一、单纯形法计算的矩阵描述第二节 对偶问题的基本性质max Z=CX AX ≤b X ≥0加松弛变量后得到max Z=CX+0 XSX 、 XS≥0
- 26. 11/25管理科学与工程学院 项 目 0 XS b非基变量基变量XB XN B NCB CNXSI0Cj-ZjCN-CBB-1N -CBB-1 项 目 0 XB B-1b非 基 变 量基变量XB B-1N B-1 XN XSI0Cj-Zj
- 27. 11/25管理科学与工程学院（1）≤0≤0（2）CN-CBB-1N ≤0 -CBB-1≤0 A ′Y≥C ′ Y ≥0minω=Y′b= -CBB-1b=Z
- 28. 11/25管理科学与工程学院min Z’= - CX s.t. - AX ≥-b X ≥01、对称性定理：对偶问题的对偶是原问题。 min W= Y´b s.t. A´Y ≥ C´ Y≥0max Z=CX s.t. AX ≤ b X ≥0对偶的定义对偶的定义max W’ = -Y´b s.t. -A´Y≤-C´ Y≥0二、对偶问题的性质
- 29. 11/25管理科学与工程学院2、弱对偶原理（弱对偶性）：设 和 分别是问题（P）和（D）的可行解，则必有推论1：原问题任一可行解的目标函数值是对偶问题函数值的下界；对偶问题的任一可行解的目标函数值是其原问题目标函数值的上界。
- 30. 11/25管理科学与工程学院 推论⑵.如原问题有可行解且目标函数值无界，则对偶问题无可行解；对偶问题有可行解且目标函数值无解，则原问题无可行解。关于无界性有如下结论：问题无界无可 行解无可 行解问题无界对偶问题原问题无界如：（原）无可 行解（对）
- 31. 11/25管理科学与工程学院 推论⑶.若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；对偶问题有可行解而其原问题无可行解，则对偶问题目标函数值无解。例一、试估计它们目标函数的界，并验证弱对偶性原理。（P）
- 32. 11/25管理科学与工程学院解：（D） 由观察可知： =（1.1.1.1）， =（1.1），分别是（P）和（D）的可行解。Z=10 ，W=40，故有 ，弱对偶定理成立。由推论⑴可知，W 的最小值不能小于10，Z 的最大值不能超过40。＜
- 33. 11/25管理科学与工程学院例二、已知试用对偶理论证明原问题无界。 解： =（0.0.0）是 P 的一个可行解，而 D 的第一个约束条件不能成立（因为y1 , y2 ≥0)。因此，对偶问题不可行，由推论⑶可知，原问题无界。
- 34. 11/25管理科学与工程学院例3、已知显然，这两个问题都无可行解。
- 35. 11/25管理科学与工程学院 3、最优性判别定理： 若 是原问题的可行解， 是 对偶问题的可行解，且有 ， 则 是原问题的最优解， 是对 偶问题的最优解。 例如，在例1中，可找到 X*=（0.0.4.4）， Y*=（1.2，0.2）,则Z=28，W=28.故X* .Y*分别是 P和D 的最优解。
- 36. 11/25管理科学与工程学院 4、对偶定理（强对偶性）： 若原问题与对偶问题都有可行解，则它们都有最优解，且它们最优解的目标函数值相等。 推论⑷.若 P 和 D 的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。 综上所述，一对对偶问题的关系，只能有下面三种情况之一出现： ①.都有最优解，分别设为X* 和 Y*，则必有CX* =Y*b； ②. 一个问题无界，则另一个问题无可行解； ③.两个都无可行解。
- 37. 11/25管理科学与工程学院 5、互补松弛定理： 设X*和Y*分别是问题 P 和 D 的可行解，则它们分别是最优解的充要条件是同时成立 一般而言，我们把某一可行点（如X*和Y* ）处的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。所以有如下推论： 设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。
- 38. 11/25管理科学与工程学院例4、已知试通过求对偶问题的最优解来求解原问题的最优解。解：对偶问题为
- 39. 11/25管理科学与工程学院用图解法求出： 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）
- 40. 11/25管理科学与工程学院 又由于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。
- 41. 11/25管理科学与工程学院例5、已知原问题的最优解为X* =（0.0.4），Z=12 试求对偶问题的最优解。 解：（1）（2）（3）
- 42. 11/25管理科学与工程学院将X* =（0 . 0 . 4）代入原问题中，有下式：所以，根据互补松弛条件，必有y*1= y*2=0，代入对偶问题 （3）式， y3 =3。因此，对偶问题的最优解为 Y*=（0 . 0 . 3），W=12。
- 43. 11/25管理科学与工程学院6、对偶问题的解利用原问题的最优单纯形表和改进单纯形表求解对偶问题的最优解。⑴.设原问题为： maxZ=CX AX ≤ b X≥0 引入xs ，构建初始基变量，然后，用单纯形法求解。当检验数满足σj≤0 ，则求得最优解。此时， xs对应的σjs 为- Y* ，故求对偶Y* ，只要将最优单纯形表上xs 对应的检验数反号即可。CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1Z－CB B-1b0CN－CB B-1N－CB B-1
- 44. 11/25管理科学与工程学院原问题的检验数行对应对偶问题的一个基本解。（LP检验数的相反数是DP的一个基解）例一：下图为一线性规划最终单纯形表， 课本表1—9 cj21000CBXBbX1X2X3X4X50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2σj000-1/4-1/2则对偶问题的基解为Y*=（0，1/4，1/2）
- 45. 11/25管理科学与工程学院例二、
- 46. 11/25管理科学与工程学院cj1018000cBxBbx1x2x3x4x50x317052100170/20x410023010100/30x515015001150/5-Z01018000cj1018000cBxBbx1x2x3x4x50x3540/7001-23/711/710x150/71005/7-3/718x2200/7010-1/72/7-Z-4100/7000-32/7-6/7初 始 表最终表
- 47. 11/25管理科学与工程学院 由上表可知： 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
- 48. 11/25管理科学与工程学院例三、
- 49. 11/25管理科学与工程学院cj3-1-100-M-McBxBbx1x2x3x4x5x6x73x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3-Z-2000-1/3-1/31/3-M2/3- Mcj3- 1- 100- M- McBxBbx1x2x3x4x5x6x70x4111-21100011- Mx63-4120-1103/2- Mx71-20100011-Z3-6M-1+M-1+3M0-M00
- 50. 11/25管理科学与工程学院 所以， 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
- 51. 11/25管理科学与工程学院 影子价格就是指基金管理人于每一计价日，采用市场利率和交易价格，对基金持有的计价对象进行重新评估。当基金资产净值与影子价格的偏离达到或超过基金资产净值的0.5%时，或基金管理人认为发生了其他的重大偏离时，基金管理人可以与基金托管人商定后进行调整，使基金资产净值更能公允地反映基金资产价值，确保以摊余成本法计算的基金资产净值不会对基金持有人造成实质性的损害。影子价格反映资源对目标函数的边际贡献。即资源转换成经济效益的效率。影子价格反映了资源的稀缺程度，反映了资源的边际使用价值。第三节 影子价格
- 52. 11/25管理科学与工程学院 定义：在一对 P 和 D 中，若 P 的某个约束条件的右端项常数bi 增加一个单位时，所引起的目标函数最优值Z* 的改变量y*i 称为第 i 个约束条件的影子价格，又称为边际价格。 用线性规则方法计算出来的反映资源最优使用效果的价格
- 53. 11/25管理科学与工程学院 设：B是问题 P的最优基，由前式可知， Z*=CB B-1b = Y*b =y*1b1+ y*2b2+…+y*ibi+…+y*mbm 当bi 变为bi+1 时（其余右端项不变，也不影响B），CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1Z－CB B-1b0CN－CB B-1N－CB B-1
- 54. 11/25管理科学与工程学院 目标函数最优值变为： Z′*= y*1b1+ y*2b2+…+y*i （ bi+1 ）+…+y*mbm ∴ △Z*= Z′*－ Z* = y*i 也可以写成： 即y*i 表示Z*对 bi的变化率。 其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量yi 就是第 i 个约束条件的影子价格。 也可以理解为目标函数最优值对资源的一阶偏导数（但问题中所有其它数据都保持不变）。
- 55. 11/25管理科学与工程学院 若第i 种资源的单位市场价格为mi ，当yi > mi 时，企业愿意购进这种资源，单位纯利为yi－mi ，则有利可图；如果yi < mi ，则企业有偿转让这种资源，，可获单位纯利mi－yi ，否则，企业无利可图，甚至亏损。
- 56. 11/25管理科学与工程学院 由于影子价格是指资源增加时对最优收益的贡献，所以，也称它为资源的机会成本或边际产出，它表示资源在最优产品组合时，具有的“潜在价值”或“贡献”。 资源的影子价格是与具体的企业及产品有关的，同一种资源，在不同企业，或生产不同产品时对应的影子价格并不相同。 从对偶问题引出的实例中，可以看出，影子价格也是企业出让资源的最低价格，企业按这种价格出让资源与用这种资源自己生产所获得的收益是相等的。
- 57. 11/25管理科学与工程学院 影子价格是经济学中的重要概念，将一个企业拥有的资源的影子价格与市场价格比较，可以决定是购入还是出让该种资源。当某资源的市场价格低于影子价格时，企业应该买进该资源用于扩大生产；而当市场价格高于影子价格时，则企业的决策者应该将已有资源买掉。这样获利会更多。在考虑一个地区或一个国家某种资源的进出口决策中，资源的影子价格是影响决策的一个重要因素。 利用单纯形表求解线性规划，在求得最优解的同时很容易得到问题的各种资源的影子价格。某资源的影子价格，就是该资源对应的约束条件所加松弛变量在最优表中的检验数的相反数。
- 58. 11/25管理科学与工程学院 一 对偶单纯形法的基本思想 对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。第四节 对偶单纯形法
- 59. 11/25管理科学与工程学院 如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。
- 60. 11/25管理科学与工程学院 对偶单纯形法在什么情况下使用 ： 应用前提：有一个基，其对应的基满足: ① 单纯形表的检验数行全部非正（对偶可行）； ② 变量取值可有负数（非可行解）。 注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。
- 61. 11/25管理科学与工程学院1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2； 2.若b’≥0,则得到最优解,停止;否则,若有bl<0则选l行的基变量为出基变量,转3 3.若所有alj’≥0( j = 1,2,…,n )，则原问题无可行解,停止;否则,若有alj<0 则选 =min{j / alj┃akj<0}=k/alk那么 xk为进基变量,转4； 4.以alk为主元素,作矩阵行变换使其变为1,该列其他元变为0,转2。二、对偶单纯形法的计算步骤
- 62. 11/25管理科学与工程学院例：求解线性规划问题： 规范化： Max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 ≥ 0Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 ≥ 3 2x1 - x2 + x3 ≥ 4 x1 , x2 , x3 ≥ 0
- 63. 11/25管理科学与工程学院表格对偶单纯形法
- 64. 对偶单纯形法的适用范围 适合于解如下形式的线性规划问题在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。
- 65. 11/25管理科学与工程学院 对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算。
- 66. 11/25管理科学与工程学院例一、用对偶单纯形法求解：解：将模型转化为
- 67. 11/25管理科学与工程学院cj-9-12-15000cBxBbx1x2x3x4x5x60x4-10-2-2-11000x5-12-2-3-10100x6-14-1-1-5001(-9/-1.-12/-1. -15/-5)-Z′ 0-9-12-15000cj-9-12-15000cBxBbx1x2x3x4x5x60x4-36/5-9/5-9/5010-1/50x5-46/5-9/5-14/5001-1/5-15x314/51/51/5100-1/5(-30/-9.-45/-14 .-15/-1)-Z′ 42-6-9000-3
- 68. 11/25管理科学与工程学院cj-9-12-15000cBxBbx1x2x3x4x5x60x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14 (-3/-9.-45/-9. -33/-1)-15x315/71/140101/14-3/14-Z′ 501/7-3/14000-45/14-33/14cj-9-12-15000cBxBbx1x2x3x4x5x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/9-Z′ 72000-1/3-3-7/3
- 69. 11/25管理科学与工程学院 所以， X*=（2 . 2 . 2 . 0 . 0 . 0）， Z′* =－72， 原问题 Z* =72 其对偶问题的最优解为： Y*= (1/3 . 3 . 7/3)，W*= 72
- 70. 11/25管理科学与工程学院练习：
- 71. 11/25管理科学与工程学院cj-2-3-400cBxBbx1x2x3x4x50x4-3-1-2-1100x5-4-21-301-Z -2-3-400cj-2-3-400cBxBbx1x2x3x4x50x4-10-5/21/21-1/2-2x121-1/23/20-1/2-Z 0-4-10-1
- 72. 11/25管理科学与工程学院cj-2-3-400cBxBbx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5-Z 28/500-3/5-8/5-1/5Y=（8/5 . 1/5） X=（2/5 . 11/5 . 0） Z =28/5
- 73. 11/25管理科学与工程学院单纯形表的理解（例题）上表中6个常数 a1 , a2 , a3 , b , 1 , 2 取值在什么范围可使 1、现可行解最优，且唯一？何时不唯一？ 2、现基本解不可行； 3、问题无可行解； 4、无有限最优解； 5、现基本解可行，由 x1 取代 x6 目标函数可改善。
- 74. 11/25管理科学与工程学院ci , bj ,aij发生变化—— 本段重点 对于表格单纯形法，通过计算得到最优单纯形表。 应能够找到最优基 B 的逆矩阵 B-1 ， B-1b 以及 B-1N，检验数 j 等。第五节.灵敏度分析
- 75. 11/25管理科学与工程学院LP规划的灵敏度分析所研究的内容:1.当A、b、C中某些元素发生变化时，原来的最优解有什么变化2.当A、b、C中元素在什么范围内变化时， 原来求得的最优解或最优基不变.3.当A、b、C的变化引起最优解变化时， 如何用最简单的方法求得最优解
- 76. 11/25管理科学与工程学院分析设最优基为B:1.最优基可行解为与C无关2.检验数向量（非基变量的检验数向量）与b无关，与A,C有关 CjCBCNbCBXBXBXN….…B-1BB-1NB-1b
- 77. 11/25管理科学与工程学院3. 最终表中的系数矩阵与C和b均无关，与A有关4.最优目标值与A,b,C均有关
- 78. 11/25管理科学与工程学院 CjCBCNbCBXBXBXN….…B-1BB-1NB-1b将引起检验数行的变化重新计算检验数行5-1价值系数c发生变化：
- 79. 11/25管理科学与工程学院1.当xk为非基变量（仅引起 的变化）
- 80. 11/25管理科学与工程学院例1 Max z = -2x1 - 3x2 - 4x3 S.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 ≥0
- 81. 11/25管理科学与工程学院最优单纯形表 从表中看到σ3= c3+Δc3-(c2×a13+c1×a23 ) 可得到Δc3 ≤ 9/5 时，原最优解不变。
- 82. 11/25管理科学与工程学院2. Xk为基变量基变量的目标函数系数发生变化，会引起整行检验数的变化
- 83. 11/25管理科学与工程学院例1： Cj23100bCBXBx1x2x3x4x5………………2x110-14-113x2012-11200-3-5-18其单纯形最终表如下当c1变为4时400-1-131104x11113033x5012-1120-1-3-120124
- 84. 11/25管理科学与工程学院例2: Max z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5 s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 ≥ 0
- 85. 11/25管理科学与工程学院下表为最优单纯形表,考虑基变量系数c2发生变化 从表中看到 σj=cj-(c1×a1j+c5 × a5j+(c2+Δc2) ×a2j)j=3,4 可得到 -3≤Δc2≤1时，原最优解不变。
- 86. 11/25管理科学与工程学院Max{j/asjasj>0}≤cs≤Min{j/asjasj<0}
- 87. 11/25管理科学与工程学院5-2、b变化可用对偶单纯形法继续求解
- 88. 11/25管理科学与工程学院例： Cj23100bCBXBx1x2x3x4x5………………2x110-14-113x2012-11200-3-5-18设 b列变为要保持最优基不变，则否则，最优基改变 这是用对偶单纯形法继续求解
- 89. 11/25管理科学与工程学院例： Cj23100bCBXBx1x2x3x4x5………………2x110-14-113x2012-11200-3-5-18若b1=1/25/2--3/1-1[ ]0x5-101-4113x2111303/2-10-2-90最优解：X*=(0,2/3,0,0,1)T-111/2
- 90. 11/25管理科学与工程学院最优单纯形表中含有 B-1=( aij ）i=1,…,m; j=n+1,…,n+m 那么 新的xi=(B-1b)i+brair i=1,…, m 。 由此可得，最优基不变的条件是 Max {-bi/airair>0}≤br≤Min{-bi/airair<0}
- 91. 11/25管理科学与工程学院5-3增加一个变量 增加变量 xn+1 则有相应的pn+1 ,cn+1 。 那么 计算出B-1pn+1 , n+1=cn+1-∑cri ari n+1 填入最优单纯形表, 若 n+1 ≤ 0 则 最优解不变； 否则，进一步用单纯形法求解。
- 92. 11/25管理科学与工程学院例： A B C 备用资源 甲 1 1 1 12 乙 1 2 2 20 利润 5 8 6 产品原料问：如何安排产品产量，可获最大利润？
- 93. 11/25管理科学与工程学院maxZ=5X1 +8X2 +6X3X1+ X2 + X3+X4 = 12 X1+2X2+2X3 +X5 =20 X1 … X5 0解
- 94. 11/25管理科学与工程学院 5 8 6 0 0 X1 X2 X3 X4 X5 CB XB 0 5 8 6 0 0 0 X4 12 1 1 1 1 0 0 X5 20 1 2 2 0 1 CB XB 84 0 0 -2 -2 -3 5 X1 4 1 0 0 2 -1 8 X2 8 0 1 1 -1 1…
- 95. 11/25管理科学与工程学院例 对于新产品D，已知1个单位D要消耗 甲：3 乙：2 可以得利润10问：投产产品D是否有利？ 6 = C6 - CBB-1 P6 = 10 - (5 8) 2 -1 3 -1 1 2 = 10 - 12 = -2 < 0 结论：无利
- 96. 11/25管理科学与工程学院（1）利润为多少时，投产产品D有利？ 6 = C6 - CBB-1 P6 = C6 - 12 >0 得 C6 >12（2） C6 =15 时 6 =3 P6 = B-1 P6 = 2 -1 3 = 4 -1 1 2 -1~
- 97. 11/25管理科学与工程学院 X1 X2 X3 X4 X5 X6 XB 84 0 0 -2 -2 -3 3 X1 4 1 0 0 2 -1 (4) X2 8 0 1 1 -1 1 -1 87 -3/4 0 -2 -7/2 -9/4 0 X6 1 1/4 0 0 -1/2 -1/4 1 X2 9 1/4 1 1 -1/2 3/4 0
- 98. 11/25管理科学与工程学院5-4增加一个约束 增加约束一个之后，应把最优解带 入新的约束，若满足则最优解不变，否则 填入最优单纯形表作为新的一行，引入一 个新的非负变量（原约束若是小于等于形 式可引入非负松弛变量，否则引入非负人 工变量），并通过矩阵行变换把对应基变 量的元素变为0，进一步用单纯形法或对 偶单纯形法求解。
- 99. 11/25管理科学与工程学院例 新增加电力约束：13 A、B、C每单位需电 2、1、3问：原方案是否改变？2X1 +X2 +3X3 13 原方案 A：4 B：8 C：0 16 >13 原方案要改变 2X1 +X2 +3X3 +X6 = 13 user:
- 100. 11/25管理科学与工程学院 XB 84 0 0 -2 -2 -3 0 X1 4 1 0 0 2 -1 0 X2 8 0 1 1 -1 1 0 X6 13 2 1 3 0 0 1 XB 84 0 0 -2 -2 -3 0 5 X1 4 1 0 0 2 -1 0 8 X2 8 0 1 1 -1 1 0 0 X6 -3 0 0 2 (-3) 1 1 82 0 0 -10/3 0 -11/3 -2/3 5 X1 2 1 0 4/3 0 -1/3 2/3 8 X2 9 0 1 1/3 0 2/3 -1/3 0 X4 1 0 0 -2/3 1 -1/3 -1/3 … … … …
- 101. 11/25管理科学与工程学院5-5aij改变(计划生产的产品工艺结构改变) (1)、非基变量Xj工艺改变 只影响单纯形表Pj 列， 关键看 j 0? 还是 j >0? . 用(5-3)类似方法解决。(2)、基变量Xj工艺改变，复杂
- 102. 11/25管理科学与工程学院例：产品A工艺改变，对甲、乙需求变为2，2。 利润为7，问最优方案如何？先计算 p1’= 2 -1 2 = 2 -1 1 2 0一 1’= -3 取代 p1 与 1 放入最优表一一一
- 103. 11/25管理科学与工程学院 X1 X1’ X2 X3 X4 X5 0 -3 0 -2 -2 -3 X1 4 1 2 0 0 2 -1 X2 8 0 0 1 1 -1 1 78 0 0 -2 1 -3/2 7 X1’ 2 1 0 0 1 -1/2 8 X2 8 0 1 1 -1 1 80 -1 0 -2 0 -1 0 X4 2 1 0 0 1 -1/2 8 X2 10 1 1 1 0 1/2
- 104. 11/25管理科学与工程学院也可能 B-1 b出现负数 检验数与基变量均不满足最优解要求
- 105. 11/25管理科学与工程学院例 p1’ = 1 C1’ = 7 3p1’ = B-1 p1’ = 2 -1 1 = -1 -1 1 3 2 1’= -4一一
- 106. 11/25管理科学与工程学院 -M X1’ X2 X3 X4 X5 X6 -4 0 -2 -2 -3 X1 4 -1 0 0 2 -1 X2 8 2 1 1 -1 1 0 0 -2 -10 1 X1’ -4 1 0 0 -2 1 X2 16 0 1 1 3 -1
- 107. 11/25管理科学与工程学院X1’ - 2X4 +X5 = -4 -X1’ +2X4 -X5 +X6 = 4 -M+7 0 -2 2M-24 -M+8 0 X6 4 -1 0 0 (2) -1 1 X2 16 0 1 1 3 -1 0 -5 0 -2 0 -4 -M+12 X4 2 -1/2 0 0 1 -1/2 1/2 X2 10 3/2 1 1 0 1/2 -3/2
该用户的其他文档
相关PPT