第三章对偶规划与灵敏度分析.ppt

对偶的定义 原始问题 max z=CX s.t. AX≤b X ≥0 （2）按照原始-对偶表直接写出 ； 原始-对偶表 下面讨论线性规划问题标准型的对偶问题 三 对偶线性规划的基本性质 考虑具有对称形式的线性规划问题 若B是系数矩阵(A,I)中的一个可行基，并假设(A,I)可表示为（B,N),则线性规划问题可改写为： 由此可以求得基本可行解 目标函数值 非基变量检验数 定理5，互补松弛定理 如果 和 分别是原问题和对偶问题的可行解，那么 和 是最优解的充要条件是 其中 为原问题的松弛变量， 为对偶问题的剩余变量。 即： 即： 如果 和 分别是原问题和对偶问题的最优解， 则由强对偶定理 和 具有相同的目标函数值， 则 定理6 原问题的检验数对应对偶问题的一个基本解。 例：某加工车间要把1单位劳动力和3单位原材料加工成A,B两种产品。生产1单位A需要1／3单位劳动力和1／3单位原材料，生产1单位B需要1／3单位劳动力和4／3单位原材料。售出1单位A可获利润2元，1单位B的利润是3元，问如何组织生产？ 实施图解法，以求出最优生产计划（最优解）。 沿着箭头的方向平移目标函数等值线，使其达到可行域中的最远点E, E点就是要求的最优点，它对应的相应坐标 x1=1,x2=2 就是最有利的产品组合，即生产A产品1吨，B产品2吨能使两种产品的总利润达到最大值 Zmax=2?1+3?2=8（千元），x1=1,x2=2就是线性规划模型的最优解，Zmax=8就是相应的目标函数最优值。 上例是寻求一个生产计划方案，使得在劳动力和原材料可能供应的范围内，产品的总利润最大，它的对偶问题就是一个价格系统，使在平衡了劳动力和原材料的直接成本后，所确定的价格系统最具有竞争力。 上例的对偶规划如下： 它的图解见右图。其中L1和L2分别为两个约束半平面的边界，虚线为目标函数等值线，可行域为图中阴影部分，沿着与箭头（目标函数值递增的方向）相反的方向平移目标函数等值线（注意：对偶规划中 要求对目标函数极小化） 得最优点为A, 其对应坐标为 y1=5,y2=1 两个特殊情况： 1如果b列全都大于0，则最优解已经得出。 2如果对应某个 小于0，而第r行的所有 都大于0，则说明无可行解。 例 目标函数系数cj的改变 例 max z= -2x1 -3x2 -4x3 ? ? ? ? ? -x1 -2x2 -x3 +x4 ? =-3 ? ? -2x1 +x2 -3x3 ? +x5 =-4 ? ? x1, x2, x3, x4, x5 ≥0 又因为 所以变换以后保证所有的检验数仍然小于零。 3.3灵敏度分析 一、灵敏度分析的含义和内容 1、什麽是灵敏度分析？ 研究线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程称为灵敏度分析或（优化后分析）。 2、灵敏度分析的内容： ? 目标函数的系数变化对最优解的影响； ?约束方程右端系数变化对最优解的影响； ? 约束方程组系数阵变化对最优解的影响 ； 回答两个问题： ①这些系数在什麽范围内发生变化时，最优基不变（即最优解或最优解结构不变）？ ②系数变化超出上述范围时，如何用最简便的方法求出新的最优解？ 二、? 进行灵敏度分析的基本原则 ? 1、在最优表格的基础上进行； 2、尽量减少附加计算工作量； 三、? 灵敏度分析举例： 研究下例 引入非负的松弛变量x4,x5, 将该LP化为 标准型： 用表格单纯形法求解如下： 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 1 2 X1 X2 2 3 1 9 3/4 0 -3/4 1 -1/4 1/4 1 7/4 0 1/4 3/4 9/4 X1 X5 0 3 5/4 0 -6/4 0 -3/4 0 0 -1 -5/3 -1/3 2 3 3 0 0 3/1 9/4 1 1 1 1