《运筹学》胡运权第4版第二章线性规划的对偶理论及灵敏度剖析.ppt

参数线性规划分析步骤 分析步骤： （1）令λ=0求解得最终单纯形表； （2）将λC*或λb*项反映到最终单纯形表中去； （3）随λ值的增大或减小，观察原问题或对偶问题，一是确定表中现有解（基）允许λ值得变动范围，而是当λ值的变动超出这个范围时，用单纯形法或对偶单纯形法求取新的解； （4）重复（3），一直到λ值继续增大或减小时，表中的解（基）不再出现变化时为止。 参数线性规划举例 例2-11 分析λ值变化时，下述参数线性规划问题最优解的变化。 （1）令λ=0求得最优解，并将λC*反映到最终单纯形表中，得下表。 cj→ 2+λ 1+2λ 0 0 0 CB 基 b x1 x2 x3 x4 x5 0 x3 15/2 0 0 1 5/4 -15/2 2+λ x1 7/2 1 0 0 1/4 -1/2 1+2λ x2 3/2 0 1 0 -1/4 3/2 cj-zj 0 0 0 -1/4+1/4λ -1/2-5/2λ 表中，当-1/5≤λ≤1时，表中解为最优，且z=17/2+13/2 λ。 参数线性规划举例 （2）当λ1时，x4的检验数0，用单纯形表继续迭代： cj→ 2+λ 1+2λ 0 0 0 CB 基 b x1 x2 x3 x4 x5 0 x3 6 0 0 4/5 1 -6 2+λ x1 2 1 0 -1/5 0 1 1+2λ x2 3 0 1 1/5 0 0 cj-zj 0 0 1/5-1/5λ 0 -2-λ 当λ≥1，表中解即为最优解。这时有z=7+8λ。 参数线性规划举例 （3）当λ≤-1/5时，变量x5的检验数0，用单纯形法迭代： 当-2≤λ≤-1/5时，z=8+4λ;当λ≤-2时，z=0。 参数线性规划举例 讨论题 1－7 在极大化问题的下列表中，六个常数?,?1,?2, ?3,?1, ?2,之值未知（假定无人工变量），分别写出对六个未知数的约束条件，使以下各小题关于该表的说法为真。 ① 现行解最优，但不唯一； ② 现行解不可行（指出哪个变量造成）； ③ 一个约束条件有矛盾； ④ 现行解是退化的基本可行解； ⑤ 现行解可行，但问题无有限最优解； ⑥ 现行解是唯一最优解； ⑦ 现行解可行，但将x1取代x6后，目标函数能改进。 讨论题 ① 现行解最优，但不唯一； ② 现行解不可行； ③ 一个约束条件有矛盾； ④ 现行解是退化的基本可行解； ⑤ 现行解可行，但问题无有限最优解； ⑥ 现行解是唯一最优解； ⑦ 现行解可行，但将x1取代x6后，目标函数能改进。 CB XB cj xj b x1 x2 x3 x4 x5 x6 x3 ? 4 ?1 1 0 ?2 0 x4 2 -1 -5 0 1 -1 0 x6 3 ?3 -3 0 0 -4 1 ?1 ?2 0 0 -3 0 ?=0; ?1=0, ?2=0,且至少一个为零 ?0 ?0; ?10或 ?20 ?=0 ?=0; ?20, ?1=0 ?=0; ?10, ? 20 ?=0; ?10, ? 30且3/ ? 3= ?/4 影子价格 资源的市场价格是其价值的客观体现，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。因企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。 影子价格是一种边际价格。 资源的影子价格实际上又是一种机会成本。随着资源的买进卖出，其影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。 影子价格 生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。 影子价格反映单纯形表中各个检验数的经济意义。 一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利用。 影子价格举例 A B C 拥有量 工 时 1 1 1 3 材 料 1 4 7 9 单件利润 2 3 3 y1=5/3, y2=1/3 即工时的影子价格为5/3，材料的影子价格为1/3。 如果目前市场上材料的价格低于1/3，则企业可以购进材料来扩大生产，反之可以卖掉部分材料。 如果有客户以高于5/3的价格购买工时，则可以出售一些工时，反之则反 线性规划的对偶问题与灵敏度分析 线性规划的对偶问题 对偶问题的基本性质 影子价格 对偶单纯形法 灵敏度分析 参数线性规划 对偶单纯形法 对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。 求解单纯形法的基本思路： 对原问题的一个基可行解，判别是否所有检验数cj-zj≤0(j=1,…,n)。若是，又基变量中无非零人工变量，即找到了问题最优解；若为否，