第1 2章 线性规划.pptVIP

本章内容 线性规划问题的数学建模 图解法 单纯形法原理 单纯形法的计算步骤 Lingo软件求解 教学说明 教学目标：掌握LP的建模方法，熟练地使用单纯形法和Lingo软件求解LP问题 重点与难点：重点是LP的建模与解法；难点是单纯形法的原理 教学方法：配合课件和WinQSB软件，课堂讲授为主，案例研讨为辅 思考题、讨论题、作业：教材第1章习题 学时分配：8学时　 线性规划的产生与发展 1939年苏联的经济学家康托洛维奇（Л.В.КОНТОРОВИЧ）在《生产组织与计划中的数学方法》一书中，首次用线性规划方法解决了生产组织与运输问题。 1947年美国数学家G.B.Dantzig提出了线性规划的数学模型，并给出了求解该模型的单纯形法（Simplex method)。这标志着线性规划这一运筹学的重要分支的诞生。 计算机的发展促进了LP计算理论的发展，使其应用更加广泛和深入。 线性规划的应用范围 生产中的组织与计划问题 运输问题 合理下料问题 配料问题 生产布局问题 特点：在现有条件下，统筹安排，使总的经济效益最好，或者是总成本最省。 例3：合理搭载问题 某货船的前舱、中舱、后舱的载重分别为2 000吨、3 000吨、1 000吨，容积分别为100 000立方米、135 000立方米、30 000立方米；顾客托运的货物A、B、C的重量、体积、运费等资料已知。为了保持货船的稳定，要求三个货舱载货率必须平衡。问如何装载，使收入最大？ 例4：连续投资问题 某地区今后三年内可以有A、B、C、D四个项目的投资选择，总资金量为3000万元。其中项目A在三年内每年年初投资，当年年底可回收本利和为120％；项目B第一年年初投资，第二年年底可回收本利和为150％，但投资额不超过2000万元；项目C第二年年初投资，第三年年底可回收本利和为160％，但投资额不超过1500万元；项目D第三年年初投资，当年年底可收回本利和为140％，投资额不超过1000万元。问如何安排投资，使第三年年底本利和的金额最大？ 小结：LP图解法有如下四种情况 有唯一最优解，这个最优解一定在可行解集合的某一顶点上达到； 有无穷多最优解，最优解充满一个线段，可以用它的两个端点作为代表； 有可行解，但无最优解； 无可行解。 线性规划问题解的关系 规定: 将下列线性规划模型化为标准形 单纯形法的计算步骤 单纯形法的思路 单纯形法的计算步骤 例1 用单纯形法求下列线性规划的最优解 单纯形法的计算步骤 2）求出线性规划的初始基可行解，列出初始单纯形表。 单纯形法的计算步骤 3）进行最优性检验 单纯形法的计算步骤 用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。 单纯形法的计算步骤 单纯形法的计算步骤 4.Lingo软件介绍 第2章 线性规划的对偶理论 对偶问题的提出 原问题与对偶问题 对偶问题的基本性质 影子价格 对偶单纯形法 灵敏度分析 线性规划的对偶理论 教学目的与要求：了解对偶问题产生的经济背景，熟练掌握对偶单纯形法和影子价格概念，熟练掌握灵敏度分析方法。 重点与难点：重点同上，难点是对偶理论。 教学方法：课堂讲授为主并配合课件和WinQSB软件。 思考题、讨论题、作业：教材第二章习题 参考资料：见绪论 学时分配：8学时　　 对偶线性规划的特点： 一个规划中的每一个约束，对应对偶规划中的一个决策变量； 一个规划中目标函数系数恰为对偶规划约束条件右端常数项； 一个规划求最小化，而对偶规划求最大化； 目标函数求最小化搭配 约束；目标函数求最大化搭配 约束； 两个规划都有非负限制。 定理1 如果线性规划中第k个约束条件是等式，则它的对偶规划中的第k个变量无非负限制，反之亦然。 原规划与对偶规划的对应关系 有关灵敏度分析的例题 综合例题：考虑下列线性规划 求出最优解后，分别对下列各种变化进行灵敏度分析，求出变化后的最优解。 有关灵敏度分析的例题 综合例题：考虑下列线性规划 求出最优解后，当右边常数项变化时，求出变化后的最优解。 从相反的角度提出问题：工厂决策者决定不生产甲、乙两种产品，而对设备的有效台时数进行出租，用收取加工费的方法获得最大利润。应如何考虑？ 决策者要考虑给每一种设备出租一个台时的定价。在何种价格下，决策者接受出租设备呢？ 建立LP数学模型 显然，当maxZ=minW时，对于决策者来说这两种方案都是最优的。 2.对偶线性规划的模型 例1：写出下面原规划的对偶规划 例2：写出下面原规划的对偶规划 例3：写出下面原规划的对偶规划 变量 约束条件 目标函数 LP原问题 LP对偶问题 约束条件 变量 目标函数 练习：写出