OR_04参数规划

1、运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏20131 -参数规划中山大学中山大学. .智能交通研究中心智能交通研究中心黄敏黄敏运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏20132对偶单纯形法对偶单纯形法 灵敏度分析灵敏度分析 参数规划参数规划内容提要运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013maxstTz c xAxbx01.1. 给定的基给定的基B，计算基解：计算基解：1(,)(,0)TBNxBxxb2.

2、2. 若下列条件满足：若下列条件满足：1100TTNBBB Nbcc3.3.则则x x为最优解，最优目标函数为：为最优解，最优目标函数为：1TBzBcb运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏20134对偶单纯形法正则解：正则解：检验数全部为非正的基解检验数全部为非正的基解正则解一般不可行，如果可行，则为最优解正则解一般不可行，如果可行，则为最优解10NBcc B N解的正则性：解的正则性：检验数为非正检验数为非正解的可行性：解的可行性：资源向量列非负资源向量列非负10NBcc B N10B b正则性与可行性正则性与可行性maxst

3、0zcxAxbx运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201312121321235454max23subject to28416412,0zxxxxxxx x x x xxxx回顾原型范例的求解过程回顾原型范例的求解过程运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏20136x1x2x3x4x5bx3121008x44001016x50400112230000 x1x2x3x4x5bx31010-1/22x44001016x201001/432000-3/4-9运筹学运筹学

4、.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013x1x2x3x4x5bx11010-1/22x400-4128x201001/4300-201/4-13x1x2x3x4x5bx11001/404x500-21/214x2011/2-1/80200-3/2-1/80-14运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏20138思路：思路：保持保持LP问题的解是正则解（或对偶问题的解是可行解），问题的解是正则解（或对偶问题的解是可行解），即检验数非正即检验数非正原问题在正则解的基础上，用单纯形

5、法逐步迭代，消除原问题在正则解的基础上，用单纯形法逐步迭代，消除解的不可行性，最终得到可行解，即为最优解解的不可行性，最终得到可行解，即为最优解优点：优点：原问题的初始解不一定是基可行解，可从非可行的正则原问题的初始解不一定是基可行解，可从非可行的正则解开始迭代解开始迭代对偶单纯形法运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏20139单纯形法与对偶单纯形法的比较单纯形法与对偶单纯形法的比较运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201310对偶单纯形法的主要计算步骤对偶单纯

6、形法的主要计算步骤确定换出变量确定换出变量确定换入变量确定换入变量111:()min () ()0lliiixB bB bB bmin0jkkljjlkljxaaa：（保持正则性）（保持正则性）运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201311用对偶单纯形法求解用对偶单纯形法求解LP问题问题123123123123min234subject to23324,0 xxxxxxxxxx x x12312341235max234subject to233240,1,2,5 jzxxxxxxxxxxxxj运筹学运筹学.线性规划线性规划中山

7、大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201312Cj-2-3-400CBXBbX1X2X3X4X50X4-3-1-2-1100X5-4-21-301Cj -Zj-2-3-400X5出基，出基， X1入基入基比值测试：比值测试：min(-2/-2, -4/-3)=1运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201313Cj-2-3-400CBXBbX1X2X3X4X50X4-10-5/21/21-1/2-2X121-1/23/20-1/2Cj -Zj0-4-10-1X4出基，出基， X2入基入基运筹学运筹

8、学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201314最优解：最优解：X=(11/5, 2/5, 0, 0, 0)TCj-2-3-400CBXBbX1X2X3X4X5-3X22/501-1/5-2/51/5-2X111/5107/5-1/5-2/5Cj -Zj00-3/5-8/5-1/5运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201315灵敏度分析概述灵敏度分析：灵敏度分析：LP的最优解与其参数的关系的分析的最优解与其参数的关系的分析参数：价值系数、技术系数、资源参数参数：价值系数、

9、技术系数、资源参数灵敏度分析研究的问题灵敏度分析研究的问题各系数在什么范围内变化，原问题各系数在什么范围内变化，原问题最优解最优解不变不变如果系数的变化超过了上述范围，如何采用简便的方法、如果系数的变化超过了上述范围，如何采用简便的方法、迅速找到最优解迅速找到最优解运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201316决策变量决策变量解 系数矩阵系数矩阵I0BxNxj1NBcc B N1Bc B b1B N1B b10NBcc B N10BxB b最终单纯形表中，有最终单纯形表中，有(对对Max问题问题) 当各系数发生变化时，检查上述

10、条件是否仍满足当各系数发生变化时，检查上述条件是否仍满足如何寻找如何寻找 1B运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201317x1x2x3x4x5bx3121008x44001016x50400112230000 x1x2x3x4x5bx31010-1/22x44001016x201001/432000-3/4-9运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013x1x2x3x4x5bx11010-1/22x400-4128x201001/4300-201/4-13x1

11、x2x3x4x5bx11001/404x500-21/214x2011/2-1/80200-3/2-1/80-14运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013191. 资源中某系数资源中某系数b br r发生变化，即发生变化，即b br r=b=br r+b+br r，并，并假设规划问题的其他系数都不变。这样使最终表中假设规划问题的其他系数都不变。这样使最终表中原问题的解相应地变化为原问题的解相应地变化为X XB B=B=B-1-1(b+b)(b+b)b=(0,b=(0,，bbr r,0,0,，0)0)T T10NBcc B N

12、10BxB b运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201320012121212max23subject to28416412,0 xxxxxxxx x例例设备台时增加设备台时增加4运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201321x1x2x3x4x5bx11001/404x500-21/214x2011/2-1/80200-3/2-1/80-14-z最优单纯形表最优单纯形表运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中

13、心黄敏黄敏201322111401/4040421/210021/21/800404822bB bB 计算新的资源系数列计算新的资源系数列运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201323Cj23000CBXBbX1X2X3X4X52X14+01000.2500X54-800-20.513X22+2010.5-0.1250Cj -Zj00-1.5-0.1250b列有负数，用对偶单纯形法求解列有负数，用对偶单纯形法求解将新的资源系数列填入原最终单纯形表将新的资源系数列填入原最终单纯形表运筹学运筹学.线性规划线性规划中山大学中山大学.

14、工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201324Cj23000CBXBbX1X2X3X4X52X141000.2500X32001-0.25-0.53X2301000.25Cj -Zj000-0.5-0.75最优解最优解x=(4,3,2,0,0)，z=4*2+3*3=17运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201325为保持最优解不变，设备台时的允许变化范围为保持最优解不变，设备台时的允许变化范围11110004042021/2bB bBb 142b 运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院

15、.智能交通研究中心智能交通研究中心黄敏黄敏2013262. 情况情况1：非基变量的价值系数发生变化：非基变量的价值系数发生变化10jjjBjjjcccc B P对于目标函数极大化，若对于目标函数极大化，若则最优解不变，否则用单纯形法求解则最优解不变，否则用单纯形法求解 10NBcc B N10BxB b运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201327基z系数矩阵系数矩阵I0NxBxj1NBcc B N1Bc B b1B N1B b基z系数矩阵系数矩阵I0NxBxj1Bc B b1B N1B b1(,)kkn mc 原最终单纯形表

16、原最终单纯形表新的单纯形表新的单纯形表运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201328情况情况2：基变量的价值系数发生变化：基变量的价值系数发生变化12,Bkknc ccccc 10NBcc B N10BxB b检验系数为检验系数为11()=NBBBcNcN ccBB在最终单纯形表放入改变量，重新计算检验系数在最终单纯形表放入改变量，重新计算检验系数确定变化范围确定变化范围 (0,0)Bkcc运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201329*00000000NBj

17、iIBkIikkIBxxzzbbbaxcII1运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201330*0000010000NBjIBikkIIjkikBxxzIc abxabIbz新的单纯形表新的单纯形表运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013原型范例原型范例12123142512345max23subject to28416412,0zxxxxxxxxxx x x x xx2的系数的系数c2的变化范围？的变化范围？运筹学运筹学.线性规划线性规划中山大学中山大学.工

18、学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201332x1x2x3x4x5解x11001/404x500-21/214x2011/2-1/80200-3/2-1/80142cj最优单纯形表中加入价值系数的改变量运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201333基x1x2x3x4x5解x11001/404x500-21/214x2011/2-1/802z0002(3)/2c2(1)/8c2142 c222(3)/20(1)/8and031 ccc运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心

19、智能交通研究中心黄敏黄敏201312221/31/331 (3,5)1/52/5210 BcC B p计算新的检验数计算新的检验数故最优解不变故最优解不变*(3,0,5,0,0)Tx 运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏201335参数线性规划n在线性规划的实际应用中，由于某种原因，线性规划在线性规划的实际应用中，由于某种原因，线性规划问题的目标函数的价值系数问题的目标函数的价值系数C C和约束条件的右端常数和约束条件的右端常数b b会随着某个参数而连续变动。会随着某个参数而连续变动。n当当C C和和b b随着某个参数连续变化时

20、，目标函数随着某个参数连续变化时，目标函数z z将随着将随着C C或或b b的变动而呈线性变动。由于的变动而呈线性变动。由于z z是这个变动参数的线是这个变动参数的线性函数，因而称为参数线性规划。性函数，因而称为参数线性规划。v目标函数的价值系数含有参数的线性规划问题目标函数的价值系数含有参数的线性规划问题v右端常数含有参数的线性规划问题右端常数含有参数的线性规划问题运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013(1)(1)目标函数的价值系数含有参数的线性规划问题目标函数的价值系数含有参数的线性规划问题.0MaxZCCXAXbst

21、X ABCCABCCABCABCCCABCCCCBBBBBB11111 bBCbBCbBCCZBBBB111 为原为原LPLP的价值向量，的价值向量， 为变动向量，为变动向量， 为参数为参数CC运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013 求解步骤：求解步骤： 令令= 0= 0，求得最优解与最优基，求得最优解与最优基B B； 根据根据 求得求得的区间；的区间； 运用单纯形法求得其余区间的最优解。运用单纯形法求得其余区间的最优解。（检验数行全为非正值）（检验数行全为非正值） 0 运筹学运筹学.线性规划线性规划中山大学中山大学.工学

22、院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013例例042044602343022552633212131321321x,x,xxxxxxxxt . sxxxzMax 运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013解：解：1 1） 化为标准形；化为标准形；求求= 0 = 0 的最优解与最优基的最优解与最优基B B 621042044602343022552636215314321321,jxxxxxxxxxxxt . sxxxZMaxj 则则= 0 时最优解为时最优解为(0, 100, 230, 0, 0, 20)T C

23、 i325000B-1bCBXBx1x2x3x4x5x62x2 -1/4101/2-1/401005x33/20101/202300 x6 200-21120j-400-1-201350运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏20132 2）根据）根据 求得求得 1=BCC B A ()236， ，TBXxxx()145， ，TNXxxx()5， 2， 0TBC ()6， 0， 0TNC C i325000B-1bCBXBx1x2x3x4x5x62x2 -1/4101/2-1/401005x33/20101/202300 x6 20

24、0-21120j-400-1-201350123362 552MaxZxxx/1=-6-(-5,2,0)(-1/4,3/2,2)41 4T 运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏20132 2）根据）根据 求得求得 1=BCC B A 123362 552MaxZxxxC i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52 x2 -1/4101/2-1/4010025x33/20101/2023000 x6 200-21120j-400-1-201350j-41/4005/2-9/40-40运筹

25、学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏20133) 3) 根据根据 求得求得的区间的区间 0 049202510441454152411698524116 即当即当时最优解为时最优解为 40135020002301000ZXTC i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52 x2 -1/4101/2-1/4010025x33/20101/2023000 x6 200-21120j-400-1-201350j-41/4005/2-9/40-40运筹学运筹学.线性规划线性规划中山大学中山大学.工学

26、院工学院.智能交通研究中心智能交通研究中心黄敏黄敏20134 4） 运用单纯形法求得其余区间的最优解运用单纯形法求得其余区间的最优解当当52时时C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52x2 -1/4101/2-1/4010025x33/20101/2023000 x6 200-21120j-400-1-201350j-41/4005/2-9/40-4000 x4 -1/2201-1/2020025x33/20101/2023000 x6 140001420j-9/2200-5/201150j-9-500-10460最优解为最优解为 460115

27、0420020023000ZXT运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013当当时时4116 C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52x2 -1/4101/2-1/4010025x33/20101/2023000 x6 200-21120j-400-1-201350j-41/4005/2-9/40-40-52x2 0101/4-1/81/8205/225x30013/2-1/4-3/4215-63x1 100-11/21/210000-31/423/80

28、-285/2 22851310000215220510ZX41163120T时，时，则当则当运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013当当时时1320 C i-6-52000B-1bC i325000CBCBXBx1x2x3x4x5x6-52x2 0101/4-1/81/8205/225x30013/2-1/4-3/4215-63x1 100-11/21/210j0005001310j000-31/423/80-285/2-52x2 01-1/60-1/121/4200/300 x4002/31-1/6-1/2430/3-63

29、x1 102/301/30460/3j0010/30-5/6-1/21780/3j0031/6019/125/4-3760/3 3376031780Z3430032003460X3120T，时，时，则当则当00运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013 460115023000524013502301000524116228513102152205104116312033760317800320034603120ZXZXZXZX参变量的取值范围与最优解为参变量的取值范围与最优解为运筹学运筹学.线性规划线性规划中山大学中山大学.

30、工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013012031 21641 3251780376033Z28513102Z135040Z1150460Z *Z最优解的目标函数值最优解的目标函数值 随参数随参数 的变化情况如下的变化情况如下 *Z621042044602343022552636215314321321,jxxxxxxxxxxxt . sxxxZMaxj 对于对于 参数的系统改变，参数的系统改变， 总是有这种总是有这种分段线性分段线性且是且是凸状凸状的形式。的形式。注：对应的最优解只在函数注：对应的最优解只在函数 斜率改变的斜率改变的 值处值处( (当当 在增加时）在增

31、加时）发生变化。发生变化。jC *Z *Z运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013（2 2）右端常数含有参数的线性规划问题）右端常数含有参数的线性规划问题0XbbAXt . sCXZMax XXbBbBbbBX 111 求解步骤：求解步骤： 令令= 0= 0，求得最优解与最优基，求得最优解与最优基B B； 根据根据 求得求得的区间；的区间； 运用对偶单纯形法求得其余区间的最优解运用对偶单纯形法求得其余区间的最优解。（。（b b列不能再出现负值）列不能再出现负值） 0XXXb为原为原LPLP的右端常数，的右端常数，为变动向量，

32、为变动向量，为参数为参数b运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013例例604420444602343025233212131321321x,x,xxxxxxxxt . sxxxZMax 解：解： 化为标准形；求化为标准形；求= 0 的最优解与最优基的最优解与最优基 B 62104420444602343025236215314321321,jxxxxxxxxxxxt . sxxxZMaxj 运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013则则= 0 时最优解为时最

33、优解为(0 100 230 0 0 20)T C i325000B-1bCBXBx1x2x3x4x5x62x2 -1/4101/2-1/401005x33/20101/202300 x6 200-21120j-400-1-20135062104420444602343025236215314321321,jxxxxxxxxxxxt . sxxxZMaxj 144b 运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013C i325000B-1bX*CBXBx1x2x3x4x5x62x2 -1/4101/2-1/401003/25x33/2

34、0101/20230-20 x6 200-21120-10j-400-1-201350-7 根据根据 求得求得的区间；的区间； 0XXX 11XB bB bXX144b 20102023200115022303200023100321bbb运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013 20102023200115022303200023100321bbb713501020002230231000TZX最优解为最优解为62104420444602343025236215314321321,jxxxxxxxxxxxt . sxxxZ

35、Maxj 运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013当当时最优单纯形表为时最优单纯形表为2 运用单纯形法求得其余区间的最优解。运用单纯形法求得其余区间的最优解。C i325000B-1bb*CBXBx1x2x3x4x5x62x2 -1/4101/2-1/401003/25x33/20101/20230-20 x6 200-21120-10j-400-1-201350-72x2 1/410001/4105-15x33/20101/20230-20 x4 -1001-1/21/2-105j-5000-5/2-1/21360-12时，最优解为时，最优解为1213600051022301050TZX2105当当运筹学运筹学.线性规划线性规划中山大学中山大学.工学院工学院.智能交通研究中心智能交通研究中心黄敏黄敏2013当当时最优单纯形表为时最优单纯形表为2004303C i325000B-1bb*CBXBx1x2x3x4x5x62x2 -1/4101/2-1/401003/25x33/20101/20230-20 x6 200-21120-10j-400-1-201350-70 x5 1-40-2