DOC《运筹学》

第二步: 计算到的其它面的距离的最小值的一半 第三步: 构造与平行, 到的距离为的超平面 ;

第四步: 构造与关联的可能的棱的集合 即的个元素的组合的全体;

第五步: 计算顶点的集合, 置, 对每个, 计算交点, 检查如果所有满足, 则令其为并令. 第六步: 令邻域. 结束. 例如, 对于我们讨论的例子, 这个小多面锥是一个三角形, 锥的顶点是(4,2), 底面上的端点是(3,5/2), (4, 7/6). 为保证新的目标函数超平面与多面体在最优值点不横截相交, 把多面锥的底面上的顶点代入新的目标函数超平面, 其计算结果的符号, 跟代入扰动前的目标函数后的符号, 应该是一样的, 即 得到 跟把参数代入单纯形表计算得到的结果是一样的. 但是, 后面讲的这个方法, 适合于已经知道最优结果的情况, 从计算过程看, 它也比较容易写成程序. 前面讲的例子是目标函数的系数(价值系数)变化下的敏感性. 下面介绍线性规划关于约束条件常数项的变化的灵敏度分析方法. 问题可叙述为: 设目标函数是, 约束条件为以及假定已经用某程序得到这个问题的解答, 最优解为 问: 约束条件的常数项有变化量, 这个变化在多大的范围内最优解能保持不变. 我们知道, 如果不通过, 即时, 只要的变化量足够小, 最优解的位置不改变, 仍然成立. 所以, 一般讨论常数项之灵敏度问题的时候, 假设. 显然, 这个时候, 不论多小, 最优解的位置都会发生改变. 如下图所示. 所以, 这时, 最优解保持不变的意思, 指决定最优解的还是原来的那些约束条件(多面体的侧面). 我们指出下面的方法: 不妨设考虑的是的常数项的变化. 考虑一般的情况, 设原先的最优值恰好是个约束条件取得的, 即 则解新的联立方程组 它的解可以表示为 为保证这个解还是新的线性规划的最优解, 需要线段与所有平面无交点, 即下面的条件成立: 这些式子都是线性不等式, 变量是. 解之即得的许可变化范围. 线性规划的灵敏度分析还涉及约束条件中的系数变化和增加约束条件引起的变化等两个问题. 我们将这两个问题列为学生的课外自学研究问题.

第二节平衡的运输问题 运输问题是一种特殊的线性规划问题. 从m个发点A1,A2,…,Am向n个收点B1,B2,…,Bn发送某种货物. A_i发点的发货量为a_i, B_j收点的收货量为b_j, 由A_i运往B_j单位货物的运费为c_{i,j}. 由A_i运往B_j货物的运量为x_{i,j}. 问如何调配, 才能使得总运费最小? (这里在黑板上画一个示意图) 当发点的发货量总和, 与收点的收货量总和相等的时候, 称此运输问题为平衡运输问题. 否则称之为非平衡运输问题. 若没有特别说明, 运输问题均假定为平衡运输问题. 设表示发点往收点的运量. 则可列出运输问题的数学模型 其中 约束方程的个数是个. 但是因为 所以约束方程不是互相独立的, 实际上只有个是独立的. 由此见, 运输问题是特殊的线性规划问题, 可以用单纯形方法求解. 这类问题, 有一个特殊的解法, 称为 表上作业法 . 表上作业法先建立如下

图表 然后分以下两个大的步骤在表上操作得到运输问题的解. 第一步, 找一个初始可行解;

第二步, 求最优方案. 第二步又分为检查当前方案是否最优和改善当前方案两小步. 循环执行第二步. 以下用一个具体的例子解释如下. 假设初始表格如下 一般教材上这样表示, 把运费写在右上角的一个小方格里. 每个格子里空白的区域待后面的操作中填写. 第一步: 找一个初始可行方案. 有3个方法: 西北角法, 最小运费法, Vogel法(差值法). 先介绍西北角法. ①初始表格的西北角是, 把填写在这个各自里, 并且从里面各自减去这个数, 填写在的格子里面, 与原先的数字用斜线隔开, 如果新数字是0, 在该列或者该行的每一格填写一个记号, 标记这一列或者行完成: ②当前的表格里, 找出没有标记的小表, 对这个小表的西北角执行操作: 中填写, 在填写原来的数字减去的结果, 与原先的数字用斜线隔开, 如果得0, 相应的行用标记完成. 现在的这个例子的当前西北角是. 具体操作结果如下面的图. ③对新表格循环执行操作②, 直到所有的行和列标记完成的记号. ④整理表格. 把所有的标记和斜线后面的数字取掉. 得初始可行方案. 这个初始方案的意思是: A1的40吨, 运往B1点40吨;