DOC《运筹学》

2 线性规划问题灵敏度分析的几何意义 上面我们看到, 分析一个系统对于参数的敏感度有重要的实际意义. 线性规划问题亦如此. 下面我们先从几何上直观地了解一下线性规划中灵敏度和稳固的意义. 我们已经知道, 一个线性规划问题的最优解, 决定于问题的约束条件和目标函数. 约束条件形成一个多面体, 目标函数是一个超平面, 从(正/负)无穷远处沿着法线方向, 向多面体平行移动, 最优解是目标函数超平面平行移动与多面体的第一次接触. 看下面的示意图. 这里, 一个超平面的法线, 就是与它垂直的一个有向直线. 线性规划的参数的几何意义分别是: (1) 表示目标函数超平面的法向量的方向. 其中发生改变, 超平面在轴方向上的倾斜程度发生变化. (2) 表示第个约束条件对应的超平面的法向量的方向. 其中发生改变, 这个超平面在轴方向上的倾斜程度发生变化. (3) 表示第个约束条件对应的超平面在每个坐标轴上的截距. 变化为, 则对应的超平面发生平移, 超平面的法方向不变. 下面的图画的是一个2维的情况, 也就是有2个决策变量的问题. 这个例子中有5个约束条件. 约束条件围城一个凸5边形. 我们从这个图中观察, 几何对象(超平面, 多面体)的位移(旋转和平移)对于最优解有什么影响. 我们可以看出下面的信息. 约束条件的超平面, 如果不通过最优解, 则它的系数和常数项发生小的改变的时候, 不会影响最优解的位置. 例如上面图形中的f2, f3和f5. 约束条件的超平面, 如果通过最优解, 则它的系数可以在某一个范围变化, 而不致影响解的位置, 但是它的常数项的任何小的改变, 将影响解的位置. 例如上面图形中的f1, f4, 如果它们围绕最优解旋转, 在一定的范围内, 不使最优解的位置改变. 目标函数超平面, 能改变的是其中的系数, 也就是超平面的法方向. 这个超平面的法方向的改变, 也可能改变最优顶点的位置, 也可能不改变最优界顶点. 如下图. 目标函数只在一个顶点上取得最优值, 这时, 目标函数平面围绕这个顶点变动法方向(也就是价值系数), 只要不与多面体横截, 最优解的位置将保持不变. 如果在取得最优解的位置, 目标函数平面落在多面体的一个表面, 则目标函数的任意改变都导致最优解位置变化. 3如何计算参数的变化范围 下面介绍, 如何计算参数的许可变化范围. 一般教材介绍灵敏度分析的时候, 在待分析的系数上加一个增量符号, 如等, 放在单纯形表格中参与计算, 分析这些增量是否会改变计算过程中基础变元的选择. 但理解了灵敏度的几何意义, 可以先不增加变化量, 解得(用软件)最优解以后, 通过分析方程式和不等式, 了解增量在什么范围内变化的时候, 不影响解的位置. 以下是例子. 设考虑的线性规划问题是 这个例子的单纯形表是下面的四张 最优解是 现在假定的价值系数起了变化, 即, 则在最终单纯形表中, 把改成, 重新计算, 得 为保证解的不变, 需要 解得, . 所以, 基础变量在目标函数的系数当前值的许可变化范围是到2. 的取值范围是 , 在此范围内变化, 不影响当前最优值. 下面介绍如何直接用代数计算的方法, 得出的许可变化范围. 设价值系数, 目标函数 仍然通过点, 我们要确定的范围, 使得平面 在处与约束条件多面体不横截相交. 我们解释后面这句话的意思以及判定的方法. 什么叫做一个平面与一个多面体在一点附近是横截相交的? 在前面的问题中, 原目标函数是约束条件多面体在(4,2)处的支撑线(高维空间为支撑平面), 要确定的范围, 使得新的目标函数也是约束条件多面体在(4,2)处的支撑线. 于是, 我们得描述, 约束条件多面体在(4,2)处的局部形状. 一般, 一个多面体在它的一个顶点的局部是一个小的多面锥, 这个小多面锥可以这样计算. 输入: 一个多面体, 顶点, 超平面. 输出: 点集, 邻域满足 . 第一步: 构造与关联的面的集合;