运筹学线性规划与单纯形法ppt课件.pptx

《运筹学线性规划与单纯形法ppt课件.pptx》由会员分享，可在线阅读，更多相关《运筹学线性规划与单纯形法ppt课件.pptx（153页珍藏版）》请在三一办公上搜索。

1、1,运筹学,线性规划与单纯形法,感谢你的观看,2019年7月3,2,运 筹 学,教师：赵玮电话：,感谢你的观看,2019年7月3,3,引言,数学要求课程的地位与作用运筹学概要,感谢你的观看,2019年7月3,4,感谢你的观看,2019年7月3,5,线性规划(LP),问题与建模二维线性规划图解法计算机解法极小化下的求解与大M法灵敏度分析对偶规划LP求解步骤与OR软件包操建模与案例分析,感谢你的观看,2019年7月3,6,线性规划(LP),问题与建模二维线性规划图解法计算机解法极小化下的求解与大M法灵敏度分析对偶规划LP求解步骤与OR软件包操建模与案例分析,例1、例2，基本概念模型的基本化,感谢你

2、的观看,2019年7月3,7,线性规划(LP),问题与建模二维线性规划图解法计算机解法极小化下的求解与大M法灵敏度分析对偶规划LP求解步骤与OR软件包操建模与案例分析,基本原理图解法步骤最优解的几种类型,感谢你的观看,2019年7月3,8,线性规划(LP),问题与建模二维线性规划图解法计算机解法极小化下的求解与大M法灵敏度分析对偶规划LP求解步骤与OR软件包操建模与案例分析,图解法的启示与求解思路需待解决的理论问题基本概念与基本理论算法（单纯形法）与求解退化与循环,感谢你的观看,2019年7月3,9,线性规划(LP),问题与建模二维线性规划图解法计算机解法极小化下的求解与大M法灵敏度分析对偶规

3、划LP求解步骤与OR软件包操建模与案例分析,图解法的启示与求解思路需待解决的理论问题基本概念与基本理论算法（单纯形法）与求解退化与循环,三种元素算法的比较单纯形法求解思路最优解的搜索迭代过程与检验数迭代与基变换单纯形表计算单纯形表基变换的进一步认识,感谢你的观看,2019年7月3,10,线性规划(LP),问题与建模二维线性规划图解法计算机解法极小化下的求解与大M法灵敏度分析对偶规划LP求解步骤与OR软件包操建模与案例分析,图解法的灵敏度分析计算机解法的灵敏度分析,感谢你的观看,2019年7月3,11,线性规划(LP),问题与建模二维线性规划图解法计算机解法极小化下的求解与大M法灵敏度分析对偶规

4、划LP求解步骤与OR软件包操建模与案例分析,对偶规划及其经济含义对偶规划基本理论对偶单纯形法算法比较影子价格,感谢你的观看,2019年7月3,12,2.线性整数规划,基本概念 定义 研究概况分支定界法的理论与算法基本思想算法与判别准则,感谢你的观看,2019年7月3,13,线性规划,人力资源分配的问题例1.某昼夜服务的工交公交线路每天各时间段内所需司机和乘务人员数如下：,感谢你的观看,2019年7月3,14,xi：实际安排司乘人员数 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务员？解：设xi表示第i班次

5、时开始上班的司机和乘务人员数，这样可以知道在第i班工作的人数应包括第i-1班次时开始上班的人员数和第班次时开始上班的人员数，例如有x1+x270。又要求这六个班次时开始上班的所有人员最少，既要求x1+x2+x3+x4+x5+x6最小，这样建立如下的数学模型：,感谢你的观看,2019年7月3,15,目标函数：min z=(x1+x2+x3+x4+x5+x6)约束条件：,感谢你的观看,2019年7月3,16,生产计划决策,例2.某工厂在计划内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A,B两种原材料的消耗，以及资源的限制，如下表所示。,感谢你的观看,2019年7月3,17,可以用x1

6、和x2的线性函数形式来表示工厂所要求的最大利润的目标：max z=50 x1+100 x2其中max为最大化的符号（最小化符号为min)；50和100分别为单位产品、的利润。上式称为目标函数。同样也可以用x1和x2的线性不等式来表示问题的一些约束条件。对于台时数方面的限制可以表示为：x1+x2300.同样，原材料的限量可以表示为 2x1+2x2400 x2250,感谢你的观看,2019年7月3,18,暂不考虑市场需求。该工厂每生产一单位产品可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少个产品和产品才能使工厂获利最多？这个问题可以用以下的数学模型来加以描述。工厂目前要决策的问

7、题是生产多少个产品和产品，把这个要决策的问题用变量x1、x2来表示，则称x1和x2为决策变量，即决策变量x1=生产产品的数量，决策变量x2=生产产品的数量。,感谢你的观看,2019年7月3,19,除了上述约束外，显然还应该有x10，x20，因为产品、产品的产量是不能取负值的。综上所述，就得到了例1的数学模型如下：目标函数：max z=50 x1+100 x2 满足约束条件：,感谢你的观看,2019年7月3,20,问题与建模,模型：对真实系统的结构与行为用图、解析式或方程来描述的合称为模型。预测模型 评价模型 优化模型 仿真模型,感谢你的观看,2019年7月3,21,例1.生产计划决策,max

8、z=50 x1+100 x2 xj生产产品j的数量,感谢你的观看,2019年7月3,22,例2.人力资源分配问题决策,min z=(x1+x2+x3+x4+x5+x6)xj：第j个班次司乘人员数,感谢你的观看,2019年7月3,23,LP四要素s.t：subject约束条件z称为目标函数xj称为决策变量max或min成为优化准则LP def1：若目标函数z为决策变量xj的线性函数，约束条件亦为决策变量xj的线性不等式（或等式），则该数学表达式（模型）称为线性规划。若目标与约束中至少有一为非线性时，则该模型称为非线性模型（NLP）。,感谢你的观看,2019年7月3,24,模型的标准化,标准化LP

9、模型的特点目标函数仅限与极大化（或极小化）所有约束条件均由等式表示所有决策变量限于取非负值每一约束不等式（或等式）之右端均为非负值,感谢你的观看,2019年7月3,25,n：决策变量个数m：约束方程个数,感谢你的观看,2019年7月3,26,模型的标准化,约束方程的标准化（增加变量个数换取求解难度）,感谢你的观看,2019年7月3,27,感谢你的观看,2019年7月3,28,模型的标准化,def2：满足所有约束条件的解x称为LP的可行解，使目标函数z取得最大（小）的可行解x*称为LP的最优解，此时对应的目标函数值z(x*)称为LP的最优值。例1的解,感谢你的观看,2019年7月3,29,例1（

10、标准化模型）,模型的标准化,感谢你的观看,2019年7月3,30,模型的标准化,例2（标准化模型）,感谢你的观看,2019年7月3,31,二维LP图解法,(利用解析式与平面区域对应关系求解)基本原理图解法步骤最优解的几种类型,感谢你的观看,2019年7月3,32,基本原理,感谢你的观看,2019年7月3,33,def3：满足LP中所有约束条件（不等式或等式约束）的点必在这些约束条件所对应区域所围成的公共区域D内，则称此公共区域D为LP的可行域。例1,感谢你的观看,2019年7月3,34,当目标函数z取z1，z2，z3时，直线 有相同的斜率和不同的截距，这一族平行直线称为等值线族；目标函数按优化

11、准则递增（或递减）的方向称为等值线族的法线方向。z=x1+x2=300称为等值线，因直线上的点（0，300），（300，0），（150，150），（100，200）等均具有相等的目标函数值300。,感谢你的观看,2019年7月3,35,图解法步骤,在平面x1ox2上求出LP的可行域利用目标函数作等值线族求出等值线的法线方向等值线沿法线方向（max准则递增方向，min准则递减方向）移动，并使目标函数z到（max,min)时，其与可行域D相交之点即为最优解,感谢你的观看,2019年7月3,36,最优解的几种类型,唯一解无穷多解无界解无最优解,感谢你的观看,2019年7月3,37,例1.唯一解,ma

12、x z=50 x1+100 x2,感谢你的观看,2019年7月3,38,例2.无穷多解,max z=50 x1+50 x2,感谢你的观看,2019年7月3,39,例3.无界解,max z=x1+x2,感谢你的观看,2019年7月3,40,例4.无最优解,max z=50 x1+50 x2,350,感谢你的观看,2019年7月3,41,计算机算法(图解法只对n3有效),图解法的启示与计算机求解思路需待解决的理论问题基本概念与理论算法与求解退化与循环,感谢你的观看,2019年7月3,42,图解法的启示与计算机求解思路,最优解 在可行域D内（或边界）最优解 在D的顶点或边界达到求解思路设想：首先搜索

13、D的顶点，然后通过顶点对应的目标值的比较来求解最优解,感谢你的观看,2019年7月3,43,计算机求解,寻找Ax=b,非基变量=0之解（基本解）,寻找max z=Cx，Ax=b，x0之解（最优解）,寻找Ax=b,非基变量=0，x0之解（基本可行解）,图解法（n3）,可行点（D内点）,顶点,目标函数值比较,？,感谢你的观看,2019年7月3,44,def4：在 之LP中，若rank(A)=mn，则A（或对A作初等行变换）中必有m个线性武官的列向量，他们够成满秩矩阵B(|B|0)，使有A=(B,N)（或(N,B)或其它），称B为A的一个基，此中N为A中除B外的子阵，相应的决策变量亦有x=(xB,x

14、N)T，此中称xB中各分量为基变量，xN中各分量为非基变量，B中各列称为基向量，N中各列称为非基向量。满足方程Ax=b，且取非基变量为0时的解称为LP基本解，满足非负条件（x 0）的基本解称为基本可行解，对应的基B称为可行基，满足 的解称为可行解。,感谢你的观看,2019年7月3,45,例1.,求A的基，基向量，非基向量，LP的基变量，非基变量，基本解，基本可行解，最优解，,感谢你的观看,2019年7月3,46,感谢你的观看,2019年7月3,47,四种解的相互关系,最优解,基本可行解,基本解,可行解,后述定理,def4,def4,为基本解，但非可行解（x 0）,为可行解，但非基本解xN=0,

15、?,?,感谢你的观看,2019年7月3,48,搜索算法思路,最优解,基本可行解,基本解（在计算机上易于求得）,满足x0,逐个比较目标函数值,感谢你的观看,2019年7月3,49,需待解决的理论问题,什么条件下LP的可行域非空？可行域D有何特性？（Th1)可行域D是否有顶点？顶点有多少个？顶点的数学含义？（Th2)是否一定能保证最优解在顶点（D内）上达到？（Th3)，顶点是什么概念？基本可行解是否存在？如何判断？（Th4)基本可行解是否唯一对应D的一个顶点？（Th5)如何求基本可行解？（Th6),感谢你的观看,2019年7月3,50,基本概念与理论,def5：设D为Rn中一点集，若对则称D为凸集

16、。几何意义：凸集D内的任两点联线上的点仍在D内（含边界）def6：设D为Rn中一点集，则称z为凸集D的顶点。几何意义：凸集D的任何顶点都不可能在D内任两点的联线上。,感谢你的观看,2019年7月3,51,感谢你的观看,2019年7月3,52,Th1：若rank(A)=mn，则LP的可行域 非空且为凸集,基本概念与理论,感谢你的观看,2019年7月3,53,Th2：在LP中，若可行域D为非空凸集时，则D中至少有一个顶点，且顶点个数为有限。Th3：在LP中，若可行域D为非空凸集且有界时，则LP最优解必在D的顶点上达到。Th4：在LP中，若有可行解（即D非空），则LP至少有一基本可行解。Th5：x是

17、LP的基本可行解 x是LP可行域D的顶点Th1Th5解决了上述问题（1）（5）,基本概念与理论,感谢你的观看,2019年7月3,54,需待解决的理论问题,什么条件下LP的可行域非空？可行域D有何特性？（Th1)可行域D是否有顶点？顶点有多少个？顶点的数学含义？（Th2)是否一定能保证最优解在顶点（D内）上达到？（Th3)，顶点是什么概念？基本可行解是否存在？如何判断？（Th4)基本可行解是否唯一对应D的一个顶点？（Th5)如何求基本可行解？（Th6),感谢你的观看,2019年7月3,55,基本概念与理论,Th6：见后（基本可行解是否为最优解的判别法则，及无最优解的判别）。Th7：求解过程中基本

18、可行解迭代准则Th8：最优解的线性组合Th9：无穷多组解的判断,感谢你的观看,2019年7月3,56,算法与求解,三种主流算法的比较单纯形法求解思路最优解的搜索思路迭代过程与检验数迭代与基变换单纯形表计算基变换的进一步认识,感谢你的观看,2019年7月3,57,三种主流算法的比较,？,感谢你的观看,2019年7月3,58,非主流算法：修正单纯形法，阶段法，M法，对偈单纯形法（均为单纯形发法变型），随机搜索法等。1算法复杂性定义：在输入规模均为L的所有可能问题中，在最坏的情况下，算法需要执行的基本运算总次数f(L)，称为该算法的计算时间复杂性，简称复杂性。,耗费时间多少,仅考虑算法执行的基本运算

19、次数（指+、大小比较、转移指令）,满足精度要求下,排除计算机性能因素,消除LP规模因素,评价算法好坏,感谢你的观看,2019年7月3,59,单纯形法求解思路,计算机求解思路,?,显然,Th1,Th4,Th6,Th5,Th2,感谢你的观看,2019年7月3,60,最优解的搜索思路,A,.,.,解的迭代,解的迭代,感谢你的观看,2019年7月3,61,最优解的搜索思路,枚举所有的顶点作比较是不可行的，因为若，则D可能有 个可能顶点（基本解）。m阶子阵,感谢你的观看,2019年7月3,62,为使计算机能自动变更顶点，注意到两个相邻顶点对应的可行基仅有一个列向量不同的特点（可以证明，高等几何），故在已

20、得到一个顶点（对应一个基本可行解或一个可行解）后，只需变更一个列向量，使其仍为一个基本可行解（顶点）即可。,最优解的搜索思路,感谢你的观看,2019年7月3,63,最优解的搜索思路,若，则一顶点的相邻顶点有n个，究竟哪一个相邻顶点作为迭代的首选？这种迭代过程（由一个顶点到另一个顶点）应保证有以下不等式才能是有效的算法：，故需研究判断 的算法。应寻找这种迭代的终止规则（称为最优性准则）。,感谢你的观看,2019年7月3,64,迭代过程与检验数,命题：若，任取A的m阶子阵，设 则目标函数 必可由非基变量 描述。,感谢你的观看,2019年7月3,65,证：rank(A)=mn，对应于基B，Ax=b总

21、可经过初等行变换，转换成下式：,感谢你的观看,2019年7月3,66,感谢你的观看,2019年7月3,67,感谢你的观看,2019年7月3,68,迭代过程与检验数,def7：若B为A的可行基，则LP的目标函数z(x)可用非基变量 来描述如（*）式，则称此中非基变量 前之系数 为检验数（）,感谢你的观看,2019年7月3,69,迭代过程与检验数,Th6：设有LP（1）若 为LP对应于可行基B的基本可行解，且对于，则 为LP的最优解，并有最优值。（2）若，使，且对应PK 0（即），则LP无最优解。,感谢你的观看,2019年7月3,70,证明：（1）（2）略,感谢你的观看,2019年7月3,71,迭

22、代与基变换,def 8：在LP求解过程中，由一个可行基 转换成另一个可行基(j=0,1,l-1)的过程称为基变换，为使每次作基变换时，对应的D中的一个顶点 转换成另一相邻顶点，这只需在可行基Bj中仅改变一个列向量(基向量)即可，则该改变的列向量基向量对应的基变量称为出基向量，与此同时，应将A中另一非基变量转为基变量，此非基变量称为入基变量，经如此变换后，则可由一个可行基 转变成一个新的可行基，一般入基向量应为主元为1的单位向量。以下定理保证经上述的基变换后，对应的新的基本可行解将不劣于原基本可行解，但如何使基变换（或迭代）的效率更高，至今仍未解决此问题。,感谢你的观看,2019年7月3,72,

23、感谢你的观看,2019年7月3,73,无最优解,有无穷多个最优解,定主列K，取为入基变量定主行，取为出基变量,END,Y,YTh6,N,Y Th9,Th7,感谢你的观看,2019年7月3,74,感谢你的观看,2019年7月3,75,Th7：满足上述条件的出入基准则所得的新基本可行解，必含有，此中 为未经迭代前的基本可行解。,感谢你的观看,2019年7月3,76,单纯形表计算,感谢你的观看,2019年7月3,77,单纯形表计算,例1.(唯一最优解),感谢你的观看,2019年7月3,78,感谢你的观看,2019年7月3,79,初始单纯形表见上表，需从A中选取初始基B0，一般取B0=I，若无，可经初

24、等行变换获得，或引入人工变量（大M）。在迭代过程中，迭代前后的两个可行基有m-1个相同的列向量，只有一个列向量不同，这样的基称为相邻基，几何上可证明在非退化的情况下，代表可行域D上的两个相邻顶点。本例有,感谢你的观看,2019年7月3,80,。,感谢你的观看,2019年7月3,81,。各次迭代之入、出基变量与主元素,感谢你的观看,2019年7月3,82,例4.,单纯形表计算,无有界最优解,Y,N,感谢你的观看,2019年7月3,83,解：图解法已得，现用单纯形法求解。,基变量,感谢你的观看,2019年7月3,84,Th8：证：,感谢你的观看,2019年7月3,85,感谢你的观看,2019年7月

25、3,86,感谢你的观看,2019年7月3,87,i+1,迭代数,感谢你的观看,2019年7月3,88,感谢你的观看,2019年7月3,89,感谢你的观看,2019年7月3,90,基变换的进一步认识,A,B1,B2,B3,BL,B0,感谢你的观看,2019年7月3,91,基变换的进一步认识,。,感谢你的观看,2019年7月3,92,详见下例1之单纯形表，其中,感谢你的观看,2019年7月3,93,感谢你的观看,2019年7月3,94,。,感谢你的观看,2019年7月3,95,感谢你的观看,2019年7月3,96,综合作业,设计与开发一个LP软件包应解决哪些问题？对解决这些问题你有何设想,感谢你的

26、观看,2019年7月3,97,退化与循环,def9：设 为LP的基本可行解，若x B的所有基变量分量都取正值，即x B 0，则称 是非退化的，若 中有一个或多个基变量分量取0，则称 为退化的，若LP的每一个基本可行解都是非退化的，则称LP为非退化的。,感谢你的观看,2019年7月3,98,退化与循环,当采用单纯形法求解时，若在迭代过程中出现了退化的基本可行解，则继续迭代下去可能产生如下三种结果：退化是暂时的，最终得到非退化的最优解（如例5）。最后得到退化的最优解。产生循环（Cycling）,目标函数得不到改善，永远得不到最优解（如例6）。,感谢你的观看,2019年7月3,99,退化与循环,Th

27、10：若LP是非退化的，则经过有限步单纯形迭代后，或者能判定LP没有最优解，或者能够求得最优解。即使基本可行解是非退化的，但在确定出基变量时，若有两个（或两个以上）比值（对应不同行）相等时，当采用min准则选出基变量时，仍有可能使新的基本可行基成为退化解，如i=0时，xB0=(2,4,3)T为非退化解，出现min比值=min2/1,4/2,3/1=2/1或4/2，此时可选s1或s2 作出基变量。由上表当选s1为出基变量时，经基变换由i=1之表知有xB0=(2,0，1)T，显然此为退化解。,感谢你的观看,2019年7月3,100,退化与循环,。由上表知此时虽经多次迭代，但目标函数无改进，但由于未

28、产生循环现象，经4次迭代后得最优解：,感谢你的观看,2019年7月3,101,退化与循环,例6 则由于退化基本可行解而出现了循环现象，可证明例6之LP有最优解，但经过6次迭代有 目标函数未得到改进而未能求得最优解。,感谢你的观看,2019年7月3,102,退化与循环,例5,感谢你的观看,2019年7月3,103,无改进,感谢你的观看,2019年7月3,104,例6.(P97，E.beale给出的循环例）本例与教材（P97）变量对应表,感谢你的观看,2019年7月3,105,循环,感谢你的观看,2019年7月3,106,B1,B2,B3,B4,B5,B6,B0,B0=,A(6)=A(0)，b(6

29、)=b(0),感谢你的观看,2019年7月3,107,退化与循环,为避免循环可用摄动法（由A.Charnes于1952年提出）也可用布兰德（R.G.Bland）提出的反循环法（1976年）或Dantzig（1954年）提出的字典法来解决。,感谢你的观看,2019年7月3,108,Bland法则如下：当所有变量均按x1,x2,xn排序时，若有若干个检验数均为正时，可选其中下标最小的非基变量作为入基变量，即取k=min j|j 0为入基变量之下标，xK为入基变量。若有若干个比值同时达到极小时，可选其中下标最小的基变量为出基变量，即取 为出 基变量下标。,感谢你的观看,2019年7月3,109,极小

30、化准则与大M法,例7.(P85),感谢你的观看,2019年7月3,110,解1,感谢你的观看,2019年7月3,111,极小化准则与大M法,人工变量引入的准则：人工变量的引入应不影响约束条件，也不影响目标函数的求解为构成基B=I，A中缺K个单位向量就引入K个人工变量（上例缺2个）人工变量引入后，为不影响约束方程应使 的最优解中人工变量为非基变量（即取）由于人工变量的引入为构成基I=B，故第0次迭代时 已成为基变量，因此在 以后的迭代过程中应尽可能将 从基变量中替换出来而成为非基变量，从而保证基本可行解分量。,感谢你的观看,2019年7月3,112,极小化准则与大M法,将目标函数设计成下型：即能

31、满足上述要求。这是由于只要 迭代过程中，若基变量含有一个人工变量，则上述设计的目标函数z(x)就不可能达到极大化（max），因此只要不出现退化现象，在经有限次迭代后总可将引入的人工变量一个一个地替换出来，而成为非基变量。因而有 如此的，其最优解与LP最优解相同（）。,感谢你的观看,2019年7月3,113,极小化准则与大M法,M 1故不必考虑其具体数值。本方法称为大M法来源与此。若 在某一次迭代中，仍然为基变量，则目标函数（此时 为基本可行解之一分量应满足非负条件），从而使此基本可行解不可能是最优解。,感谢你的观看,2019年7月3,114,极小化准则与大M法,若采用大M法始终无法将人工变量从

32、基变量替换出来，此时有两种情形：所有检验数已有，此时应认为无解。上述最优性条件仍未具备，需始终迭代下去，或改用其它方法。,感谢你的观看,2019年7月3,115,例7.解2,感谢你的观看,2019年7月3,116,感谢你的观看,2019年7月3,117,感谢你的观看,2019年7月3,118,为使b0，同时又可形成基B0=I，可在原增广矩阵（A0：b0）基础上作初等行变换以形成人工基B0=I。,感谢你的观看,2019年7月3,119,此经一次迭代即可得最优解将约束方程变形成下述，虽然保证有一个B0=I，但约束方程右端的b(i)0非负条件被破坏，从而使用单纯形法时，获得的可行解虽然是基本解，但非

33、基本可行解。易知此非基本可行解，故采用单纯形法无效。,感谢你的观看,2019年7月3,120,例8.(P88，无最优解例）解：引入松弛变量s1，s2，剩余变量s3，人工变量a1，可得上述标准型。,感谢你的观看,2019年7月3,121,感谢你的观看,2019年7月3,122,当M0，经二次迭代后，已有，按照一般原理下有下述的x(2)=(30,6,0,0,4)T应为最优解，并迭代终止。.虽然有z(x0)z(x1)z(x2)目标值早增大，但根据大M法原理应将人工变量以基变量xB中替换出来，而i=2时，由上表知a1仍为基变量，故此时应认为无最优解,感谢你的观看,2019年7月3,123,事实上由图解

34、法知该问题无可行解。或将,感谢你的观看,2019年7月3,124,灵敏度分析,图解法下的灵敏度分析定义：研究LP问题中目标函数系数C与约束条件中系数矩阵A与常数向量b的变化（局部或全部变动）对LP的最优解 与最优值 的影响程度分析的问题称为LP的灵敏度分析。由于C，b，A通常表述产品需求，原材料价格，未来的商品售价及企业的加工能力、资源消耗，故在数学建模时的估计有可能出现误差，且未来的环境亦是不确定的，有可能出现变化，因此有必要对应用问题的解作灵敏度分析。,感谢你的观看,2019年7月3,125,图解法下的灵敏度分析灵敏度分析通常讨论如下内容：C，b，A变动（局部或全部）后LP最优解是否仍存在

35、？若存在的话，最优解有多大程度的变化？C，b，A在什么范围内变动时能保证LP的原最优解不变？若C，b，A的变动超出上述范围后，如何利用LP的原最优解 来求解变动后的 最优解。这些C，b，A的变动，在出现情况下对决策者有利？在什么情况下对决策者不利？此称为对偶价格研究对象（C的变动对目标最优解的影响）。,感谢你的观看,2019年7月3,126,各种问题求解问题建模求解算法（理论、算法步骤、计算复杂性）解的存在性、唯一性、可靠性（误差分析、灵敏度分析）,感谢你的观看,2019年7月3,127,估计有误差未来环境变动,数值解,精确解,灵敏度分析,误差分析,数值解,估计正确,感谢你的观看,2019年7

36、月3,128,LPa（LP原规划）,max z=50 x1+100 x2,感谢你的观看,2019年7月3,129,LPb（C的变动对LP最优解的影响）,max z=60 x1+50 x2,感谢你的观看,2019年7月3,130,LPc（b1的变动对LP最优解的影响）,max z=50 x1+100 x2,感谢你的观看,2019年7月3,131,LPd（b2的变动对LP最优解的影响）,max z=50 x1+100 x2,感谢你的观看,2019年7月3,132,命题：在例1的优化模型中，A，b不变，讨论C变动的如下问题：欲使LP的最优解不变，仍为，C1与C2应满足什么条件？当C2=100 不变，

37、欲使LP 的最优解不变，仍为，C1应满足什么条件？当C1=50 不变，欲使LP 的最优解仍为,C2应满足什么条件？当C1，C2均变动，例如C1=60，C2=50时，最优解是否变动？欲使最优解变动为，求C1，C2应满足的条件？,感谢你的观看,2019年7月3,133,解：由图(a)，原最优解 对应B点，设LE，LF，LG直线之斜率分别为kE，kF，kG，则由对应直线方程可得kE=-1，kF=0，kG=-2，kz=-G1/G2，此中kz为等值线z=50 x1+100 x2之斜率。由图(a)中知，欲使最优点仍为B，则应有当C2=100时，由*式知，需要 方使最优点不变。当C1=50时，由*式知，需要

38、 方使最优点不变。,感谢你的观看,2019年7月3,134,解：当C1=60，C2=50时，由图(b)知最优点为C(100，200）,故最优解 且由*式知：此时显然不满足条件 欲使最优解变动为 即最优点为C时，由图(b)知应有 此时有最优值 z(100,200)=100C1+200C2。,感谢你的观看,2019年7月3,135,感谢你的观看,2019年7月3,136,问题：在例1的优化模型中，C不变，讨论b与A分别变动时的如下问题：b1=300310，b2，b3，A不变时，求设备(台时）的对偶价格Pb1。b2=400410，b1，b3，A不变时，求原料(克）的对偶价格Pb2。,感谢你的观看,2

39、019年7月3,137,解：。,感谢你的观看,2019年7月3,138,计算机解法下的灵敏度分析(P102P112),感谢你的观看,2019年7月3,139,LP：,LP,感谢你的观看,2019年7月3,140,（见上表）LP,感谢你的观看,2019年7月3,141,感谢你的观看,2019年7月3,142,注1,感谢你的观看,2019年7月3,143,注2,LP最终单纯形表,感谢你的观看,2019年7月3,144,注3,设G为R3中的凸集，它有8个顶点,每一个顶点对应一个基本可行解，当采用单纯形表迭代时，其基本原则是以一个初始顶点开始，然后沿相邻顶点行进(迭代)，直到终点(最优解)为止。注意到

40、在R3中的凸集D的每一个顶点的相邻顶点有三个（也可有五个如（b)等）凸集D中，每一顶点或基本可行解对应一个基矩阵，则相邻顶点对应的基矩阵只有一列不同），因此从一个起点B0(对应一个初始基本可行解或初始基)开始，沿相邻顶点行进（迭代），直到终点（对应最优解）B2的迭代或运行路径可以有多条，如B0B1B2，B0B5B4B3B2等，这多条路径尽管有相同的起点（初始可行解），相同的终点（最优解），但迭代步数可以不等。,感谢你的观看,2019年7月3,145,(a),(b),感谢你的观看,2019年7月3,146,感谢你的观看,2019年7月3,147,LP：L次迭代,LP r次迭代,感谢你的观看,2019年7月3,148,感谢你的观看,2019年7月3,149,感谢你的观看,2019年7月3,150,例9,对上述LP的C1(又称价值系数)作灵敏度分析,感谢你的观看,2019年7月3,151,解1,感谢你的观看,2019年7月3,152,解2,感谢你的观看,2019年7月3,153,感谢你的观看,2019年7月3,