第1、2章线性规划详解.ppt

本章内容 线性规划问题的数学建模 图解法 单纯形法原理 单纯形法的计算步骤 Lingo软件求解 教学说明 教学目标：掌握LP的建模方法，熟练地使用单纯形法求解模型，借助Lingo软件求解问题 重点与难点：重点是LP的建模与解法；难点是单纯形法的原理 教学方法：配合课件和Lingo软件，课堂讲授为主，案例研讨为辅 思考题、讨论题、作业：教材第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万元。问如何安排投资，使第三年年底本利和的金额最大？ 思考题1：配料问题 某化工厂要用三种原料混合配置三种不同规格的产品，各产品的规格、单价见下表： 问如何安排生产使得生产利润最大？ 思考题2：人力资源分配问题 某个中型百货商场对售货人员（周工资400元）的需求经统计如下表 为了保证销售人员充分休息，销售人员每周连续工作5天，休息2天。问应如何安排销售人员的工作时间，使得人力总成本最小？ 思考题3：合理下料问题 要制作100套钢筋架子，每套有长2.9m、2.1m和1.5m的钢筋各一根。已知原材料长7.4m，应如何切割，使用原材料最节省，试建立线性规划模型并求解。 课堂练习： 三种产品要分别经过A,B两道工序。 产品Ⅰ可在A,B的任何设备上加工；产品Ⅱ可在A的任何设备上加工后，只能在B1设备上加工；产品Ⅲ只能在A2和B2设备上加工。 试安排最优生产计划，使该厂获利最大。 1-2.Lingo软件介绍 小结：LP图解法有如下四种情况 有唯一最优解，这个最优解一定在可行解集合的某一顶点上达到 有无穷多最优解，最优解充满一个线段，可以用它的两个端点作为代表 有可行解，但无最优解（无界解） 无可行解 线性规划问题解的关系 规定: 将下列线性规划模型化为标准形 单纯形法的计算步骤 单纯形法的思路 单纯形法的计算步骤 例1 用单纯形法求下列线性规划的最优解 单纯形法的计算步骤 2）求出线性规划的初始基可行解，列出初始单纯形表。 单纯形法的计算步骤 3）进行最优性检验 单纯形法的计算步骤 用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。 单纯形法的计算步骤 单纯形法的计算步骤 第2章 线性规划的对偶理论 对偶问题的提出 原问题与对偶问题 对偶问题的基本性质 影子价格 对偶单纯形法 灵敏度分析 线性规划的对偶理论 教学目的与要求：了解对偶问题产生的经济背景，熟练掌握对偶单纯形法和影子价格概念，熟练掌握灵敏度分析方法。 重点与难点：重点同上，难点是对偶理论。 教学方法：课堂讲授为主并配合课件和Lingo软件。 思考题、讨论题、作业：教材第二章习题 参考资料：见绪论 学时分配：8学时　　 对偶线性规划的特点： 一个规划中的每一个约束，对应对偶规划中的一个决策变量； 一个规划中目标函数系数恰为对偶规划约束条件右端常数项； 一个规划求最小化，而对偶规划求最大化； 目标函数求最小化搭配 约束；目标函数求最大化搭配 约束； 两个规划都有非负限制。 定理1 如果线性规划中第k个约束条件是等式，则它的对偶规划中的第k个变量无非负限制，反之亦然。