运筹学1绪论及线性规划详解.ppt

* * * * * * * * * * 如果集合 C 中任意两个点 ，其连线上的所有点也都是集合C 中的点。 * * 顶点：如果对于凸集 C 中的点 X ，不存在C 中的任意其它两个不同的点x1,x2 ，使得 X 在它们的连线上，这时称 X 为凸集的顶点。 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 运筹学在20世纪40年代以后得到迅速发展，其原因大致有以下几个方面： （1）大规模新兴工业的出现，同行业间的竞争加剧，迫切需要对大型工业的复杂的生产结构和管理关系进行研究，做出科学的分析和设计； （2）产品更新换代的加速使得生产者必须密切注意市场情况和消费者的心里分析； （3）高速计算机的出现，一些复杂的问题能得到及时解决而使运筹学具有现实意义。 * 丁谓的皇宫修复 * * * * * * * * * * * * * * * * * 线性规划是研究线性不等式组的理论，是线性代数的应用和发展。 * * * * * * * * * * * * 解： 设 分别是第一个月内电视台a， 电视台b,每日晨报,星期日报，广播电台进行广告宣传的次数，则其数学模型为： s.t. 例2 ：截料问题 某工程施工中需要制作10000套钢筋，每套钢筋有2.9米、 2.1米和1.5米三种不同长度但直径和材质相同的钢筋各一根组成。目前可采购到的同类钢筋的长度均为7.4米，问应购进多少根7.4米的钢筋才能满足工程的需要？ 解: 7.4米长的钢筋截成2.9米、2.1米和1.5米长的钢筋有下面几种截法 2.9米 2.1米 1.5米 余料 截料方案 1 2 0 1 0.1 2 1 2 0 0.3 3 1 1 1 0.9 4 1 0 3 0 5 0 3 0 1.1 6 0 2 2 0.2 7 0 1 3 0.8 8 0 0 4 1.4 设用第 j 种截法用去钢材 xj 根 s.t. 例3：人员安排问题 某昼夜服务公共交通系统每天各时间段（每4小时为一个时间段）所需的值班人员如下表所示。这些值班人员在某时段上班后要连续工作8个小时（包括轮流用膳时间在内）。问该公交系统至少需多少名工作人员才能满足值班的需要。 班次 时间段 所需人数 1 2 3 4 5 6 6:00 —— 10:00 10:00 —— 14:00 14:00 —— 18:00 18:00 —— 22:00 22:00 —— 2:00 2:00 —— 6:00 60 70 60 50 20 30 解：设在第 j 个时段开始上班的人数为 xj s.t. 例4： 混合配料问题 某糖果厂用原料A、B、C 加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C 含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表，问该厂每月生产这三种牌号糖果各多少千克，使该厂获利最大，试建立该问题的线性规划数学模型。 解：用 i = 1 , 2 , 3 分别代表原料A、B、C，用 j = 1, 2, 3 分别代表甲、乙、丙三种糖果。设 xij 为生产第 j 种糖果使用的第 i 种原料的质量，则问题的数学模型可归结为： 目标函数 约束条件为 例5： 投资项目的组合问题 兴安公司有一笔 30 万元的资金，考虑今后三年内用于下列项目的投资： 1. 三年内的每年年初均可投入，每年获利为投资额的 20%，其本利可一起用于下一年的投资； 2. 只允许第一年初投入，于第二年年末收回，本利合计为投资额的150%，但此类投资限额15万以内； 3. 允许于第二年初投入，于第三年末收回，本利合计为投资额的160%，但限额投资20万元以内； 4. 允许于第三年初投入，年末收回，可获利40%，但限额为10万元以内； 试为该公司确定一个使第三年末本利总和为最大的投资组合方案。 解：用 xij 表示第 i 年初投放到 j 项目的资金数，则可投资的变量表如下 由于第三年末收回的本利只包含第三年初项目一的投资、第二年初项目三的投资和第三年初项目四的投资，因此目标函数为： 第一年初投资总额为30万，因此有： 第二年初的投资额与第一年末收回的本利总额相同： 第三年初投资额与第二年末收回的本利总额相同： 再考虑各项目的投资限额，得到该问题的线性规划模型如下： 例6： 产品计划问题 某厂生