运筹学与最优化方法第章.ppt

第 四 章 线 性 规 划 本章内容 线性规划问题及其数学模型 线性规划的图解法 线性规划解的基本性质 单纯形算法 初始基本可行解求法 对偶性及对偶单纯形方法 线性规划灵敏度分析 线性规划的建模实例 用数学软件求解线性规划模型介绍 一、线性规划问题的提出例4.1生产计划问题(资源分配问题):某工厂生产门窗两种产品，已知的条件如表所示，试制订总利润最大的生产计划。 问题 分析 模型 例4.2投资问题：某公司有100万元资金要投资（要求全部用完）。该公司有六个投资项目可选，已知的条件如表所示，该公司希望投资风险最小，每年红利至少为6.5万，最低平均增长率为12%，最低平均信用度为7。试解该问题。 问题 分析 例4.3运输问题： 问 题 分 析 模 型 一般形式 其中 规 范 形 式 解的概念 非标准形式标准化方法： 例4.6 基 本 假 设 凸 集 可行域的凸性 问 题 三、基本可行解与基本定理 基 本 定 理 §4.4 单纯形法一、单纯形方法的原理和步骤 §4.6 对偶性及对偶单纯形方法 对偶规划问题 对偶理论 对偶单纯形算法 一、规范形LP问题的对偶问题 例13 资源的合理利用问题（基P 73例1）某工厂用三种原料生产二种产品，已知的条件如下表所示，试制订总利润最大的生产计划。 三、对偶单纯形算法 在实际问题中，规划模型中的大多数数据是测量、统计、评估或决策而得出来的。因此有必要分析当这些数据发生波动时会对最优解和最优值产生什么影响。这就是灵敏度分析。 一、 资源分配问题 二、成本收益平衡问题 三、 网络配送问题（运输问题,分配问题） 四、混合问题（配料问题） 某公司用A、B、C三种原料生产三种不同规格的产品甲、乙、丙。相关数据见下表，问该公司应如何安排生产，才能使总利润最大？ 某产品由两个零件I和三个零件II组成，每个零件均可由三个车间各自生产，但各车间的生产效率和总工时限制各不相同，见下表，试确定各车间生产每种零件的工作时间，使生产产品的件数最多。 处理 设xij表示第i个车间生产第j个零件的时间 于是得到该问题的LP模型为： 运筹学 线性规划 运筹学 线性规划 运筹学 线性规划 运筹学 线性规划 运筹学 线性规划 在用规划求解时，我们选择敏感性报告并保存得敏感性报告表如下 价值系数cj的变化的灵敏度分析 右端常数bi的变化的灵敏度分析 注：这里是分别市场上二种得到的结论，若考虑产品价格同时变化，则要求为 即敏感性报告给出的是分别变化的灵敏度分析。 运用敏感性报告给出的产品价值同时变化的灵敏度分析 百分之百法则——若目标函数系数同时变动，则当它们增加（或减少）时相对其允许增量（或允许减量）的相对变化率之和不超过百分之百（100%）时，最优解不变，则当它们增加（或减少）相对其允许增量（或允许减量）的相对变化率之和超过百分之百（100%）时，不能确定最优解是否改变。 运用见P35 敏感性报告中给出的只是单个产品价值变化的灵敏度分析,对同时变化有如下一种间单的分析方法: 也可利用软件做交叉变化分析来取代. 运筹学 线性规划 运筹学 线性规划 运筹学 线性规划 运用敏感性报告给出的生产条件约束值同时变化的灵敏度分析 百分之百法则——若生产条件约束值同时变动，则当它们增加（或减少）相对其允许增量或允许减量的相对变化率之和不超过百分之百（100%）时，最优基不变，则当它们增加（或减少）相对其允许增量或允许减量的相对变化率之和超过百分之百（100%）时，不能确定最优基是否改变。 运用见P43 也可利用软件做交叉变化分析来取代. 三、技术系数矩阵A变化的灵敏度变化分析 若生产的工艺技术条件的变化，则系数aij就会随之变化，即系数矩阵A就会随之变化。我们也可分析A的变化对最优方案的影响。若增加一道生产工艺就要增加一个约束条件，新增一个决策变量即是把原来忽略的一个因素考虑进去（或者是增加新产品也相当于增加一个决策变量，系数矩阵也将增加一列），又会如何？……这些都是属于灵敏度分析的内容。 在目前计算机普及率很高的情况下，通常的方法是程序中修改A后重新计算成即可。 作业:P50—52,1,3,5 小结： 一般信息的变化： 价值向量—市场变化 右端向量—资源变化 系数矩阵—技术进步 C的变化只影响检验数（对偶问题的解），不影响原问题的基本解； b的变化只影响原问题的基本解，不影响检验数（对偶问题的解）； A中系数的变化可能既影响原问题的基本解，又影响对偶问题的解。 灵敏度分析时，要弄清楚：1）系数在什么范围内变化时，最优解（基）不变；2）若系