《运筹学第8讲：对偶单纯形法及灵敏度分析简介课件》由会员分享，可在线阅读，更多相关《运筹学第8讲：对偶单纯形法及灵敏度分析简介课件（16页珍藏版）》请在金锄头文库上搜索。
1、第8讲：对偶单纯形法及灵敏度分析简介,浙江工业大学经贸管理学院 曹柬,X=2, 3, 0, 6, 0T, Y=1/10, 0, 3/2, 0, 0 原问题检验数的负值为对偶问题的解，原问题解的负值为对偶问题的检验数。,从(P)的一个基解出发，转换到另一基解，同时检验(D)的解的可行性（相当于检验(P)的j 0），逐步消除该基解的不可行性，直至基解变为可行解，就获得最优解，这就是对偶单纯形法的基本思想。,运筹学 第8讲：对偶单纯形法及灵敏度分析简介,一、对偶单纯形法,例2：采用对偶单纯形法求解LP问题,运筹学 第8讲：对偶单纯形法及灵敏度分析简介,例3：求解如下LP问题,运筹学 第8讲：对偶单纯
2、形法及灵敏度分析简介,对偶单纯形法一般应用于求解min型的对称型LP问题 对偶单纯形法主要应用于灵敏度分析及整数规划问题 若无解，则模型无可行解 若存在非基变量的j = 0，模型可能有多重最优解,作业：3.6,运筹学 第8讲：对偶单纯形法及灵敏度分析简介,P38：例3.6,某公司生产甲、乙、丙、丁四种产品，已知制造单件产品时分别占用的设备A、B的台时，设备A、B每天可用于生产的能力以及单件产品的收益情况如下表所示。问该公司应该如何制定最优生产计划？,一、灵敏度分析基本原理描述,运筹学 第8讲：对偶单纯形法及灵敏度分析简介,对应最后一张单纯形表 基变矢XB x1, x2T 4, 4T 非基变矢X
3、N x3, x4, x5, x6T 0, 0, 0, 0T 与XB对应的未转换前的基为最优基，用B表示 与XN对应的未转换前的列向量组合采用N表示,例如：,于是：,即,由于B是满秩的，即B可逆， 上式两边左乘B-1，得到,如果问题的参数发生变化，而新问题的最优基B不变，我们可以直接求出新问题的最优解,，,，,设 Pj 为初始单纯形表中的第j 列列向量， 设 Pj为最终单纯形表中的第j 列列向量,例如：,我们不难得到：,即B-1为最终单纯形表中的最右边的一个方阵,运筹学 第8讲：对偶单纯形法及灵敏度分析简介,同时，,例如：,运筹学 第8讲：对偶单纯形法及灵敏度分析简介,令C(CB, CN)，将式
4、(1)代入Z CX 中，得到,显然，Z*CBB-1b,运筹学 第8讲：对偶单纯形法及灵敏度分析简介,综合上述5个式子，灵敏度分析的步骤可归纳如下：,1、将参数的变化反映到最终单纯形表上来：,2、检查变化后的原问题及对偶问题是否仍为可行解, 原问题有可行解（b0）, 对偶问题有可行解（0），最优基不变 原问题有可行解（b0）, 对偶问题无可行解（存在j0），采用单纯形法继续求解 原问题无可行解（存在bi0），设法使bi0，并引入人工变量，采用大M 法继续求解,运筹学 第8讲：对偶单纯形法及灵敏度分析简介,cj 的变化仅仅影响到检验数j cj zj 的变化，所以只需将cj的变化反映到最终单纯形表中
5、，其结果是出现、两种情况,3.5.1 利益系数cj 变化的灵敏度分析,P44：例3.11 (1) 若家电甲、乙的收益分别改为3和5元/件，最优生产计划有何变化；(2) 乙的收益c2在什么范围内变化时，原先的最优生产计划不变。,运筹学 第8讲：对偶单纯形法及灵敏度分析简介,解：将c1、c2的收益变化情况直接反映到原问题的最终单纯形表上，得到,若0，说明最优生产计划不变，但总利润可能发生变化 两种资源的影子价格也发生变化，y1*=1/4，y2*=3/2,(2) 解：设乙的收益c2直接反映到原问题的最终单纯形表中，得到,为使最优生产计划不变，则3, 4 ,5, 6 0，得到,乙的收益c2变化范围应满足：,b 的变化将引起 b的变化，最终出现、两种情况,3.5.2 资源约束系数 bi 变化的灵敏度分析,P45:例3.12 若设备B每天可用能力不变，设备A每天可用能力增加到25小时，最优解如何变化？ 若设备A每天可用能力不变，设备B每天可用能力增加到40小时，最优解如何变化？ 若设备A每天可用能力不变，设备B每天可用能力在什么范围内变化时，最优基保持不变？,运筹学 第8讲：对偶单纯形法及灵敏度分析简介,作业：3.7(1,3), 3.8(1,2),
