DOC《运筹学》

运筹学 第五讲: 线性规划

(四) (2008年10月14日) 内容提要 (1) 线性规划的灵敏度分析45min, (2)平衡的运输问题45min (3)非平衡调运及其他问题 15min (4)转运问题15min (5)运输问题的悖论15min

第一节线性规划灵敏度分析 1什么是灵敏度分析, 灵敏度的意义何在? 回顾线性规划模型, 我们把一个具体的优化问题转化为下面形状的数学问题: 其中的字母是决策变量, 目标函数中的系数和约束条件中的系数和右端常数项是所研究的实际问题中决定的数.

问题的最优解决定于这些常数的具体的值. 线性规划的灵敏度指的是, 当这些常数的一个或者一些(作为参数)发生变化时, 最优解(最优方案)可能发生的变化. 理论上会发生下面的三种情况之一:

1 某一个或一些参数发生任何一个微小变化, 都会导致最优方案的改变;

2 有一个有限范围, 某一个或者一些参数在这个范围内改变的时候, 最优方案保持不变, 但变化超出了这个范围, 最优方案将发生改变;

3 某一个或者一些参数, 在任何范围内改变时, 最优方案保持不变. 一般人们不大相信现实世界中存在第三种这样的 放之四海而皆准 或者 以不变应万变 的最优方案. 但人们显然希望找到比较稳固的最优方案, 也就是, 参数在一个较大范围里发生变化的时候, 方案能够保持不变, 同时, 也需要知道, 目前这种约束条件下对应的最优解, 能够在参数的多大变化范围内保持不变. 这种范围越大, 就可以说方案甚至模型越稳固(robust). 下面的实际问题, 就需要分析灵敏度有关的问题, 以决定什么情况下调整生产方案. 例1: 设某工厂用甲, 乙两种原料生产A, B, C, D四种产品, 每种产品的利润, 需要消耗的原材料, 以及现有的原材料总数如下表. 原料(吨)/产品(万件) A B C D 原材料总量(吨) 甲3210

4 18 乙0021/2

3 利润(万元)

9 8

50 19 问题 怎样组织生产, 才能使得总利润最大? 若A, C产品的利润波动, 波动范围对于最优方案影响如何? 若想增加原料甲, 增加的量对于最优方案影响如何? 若考虑生产产品E, 且知其消耗甲原料3, 乙原料1. 问, 其利润多少时有利于投产? 灵敏度分析的另外一个必要性是, 实际的线性规划问题中的系数, 有可能是按照经验估计的近似数值, 如果最优解敏感依赖于某些参数, 那么, 我们就要特别注意这些参数的准确度. 下面介绍两个解事例,说明 敏感地依赖于参数 是什么意思. 这两个例子都不是线性规划的问题, 但是在计算数学中非常有名. 例2: 考虑下面的21次方程的实根 根据代数学基本定理, 我们知道, 一个n次方程有n个根. 这个21次方程的根, 很显然, 是0,-1,-2,-3,…,-20. 即, 它有21个实根. 这个方程展开后是下面的形式: (后面的低次项系数较大, 未打印). 现在, 我们把它的的第二个系数, 就是x的20次方的系数210, 减小, 再计算新方程的实根, 这个时候我们发现, 实根只有9个了! >

fsolve(f0-x^20/1000000);

这说明方程的根在一定情况下, 敏感地依赖于其系数. 第二个事例是非常有名的 蝴蝶效应 . 动力系统(Dynamics Systems, 动态系统)研究函数迭代作用下系统状态(点的轨道)的行为变化规律: 初始状态: 时刻状态: 其中为状态之间的函数. 很多系统状态随时间变化的实际问题, 都可以归结为动态系统. 例如天气预报. 动力系统中一个常见现象是初始状态(点)可能很接近, 但经过长期变化(多次函数迭代)后, 其走向可能出现天壤差别. 也就是说, 虽然知道其变化规律, 但很难预测它的未来状态(吸引子). 下图形象地表示一些起初比较接近的点走向不同的 吸引子 . 下面的图显示一个比较简单的函数, , 其迭代作用的动力系统的吸引子的形状可能非常复杂. 这个函数叫Henon映射, 图形是a=1.4, b=0.3时的吸引子. 这种吸引子很复杂的系统叫 混沌(chaotic) 系统. 大约上世纪60年代中期, 美国MIT气象学家Lorenz为了预报天气, 用计算机求解仿真地球大气的13个方程式. 为了更细致地考察结果, 他把一个中间解取出, 提高精度再送回. 而当他喝了一杯咖啡以后回来再看结果时, 大惊, 曰: 差之毫厘, 失之千里! 这种 对初始值的极端不稳定性 , 又称 蝴蝶效应(Butterfly effect) , 因为人们设想, 按照Lorenz的发现, 可能导致这样的情形: 墨西哥湾上空一只蝴蝶的翅膀轻轻扇动一下, 将引起几个月后加利福尼亚的一场大风暴.