管理运筹学课件.pptVIP

运输问题的实例 ? (B 西安一家商场 (B 1 ), 青岛一家 (B 2 ), .B 3 ) 各一份订单 , 要求下 1 的需求量为 100 台 ,B 120 台 . 该公司在北京和武汉 2 的需求量为 台 , 而 B 3 要求供应 (A 1 ,A 2 ), 预计 A 1 ,A 2 下月的库存量 200 台和 150 台 . 已知每个仓库到每家商 1 台电机的费用如表所示 . 问该公司应如 , 才能既满足用户的需要又使总的 ? 东风电机公司接到上海一家商场 商场 月供应电机 80 设有两个仓库 分别为 场运送 何调运电机 运费最少 B 1 A 1 B 2 B 3 15 21 18 A 2 20 25 16 第五章 指派问题 ? ? 设有 n 个人 A 1 , A 2 , …A n , 要分派去做 n 件事 B 1 , B 2… B n , 要求每一件事都 必须有一个人去做 , 而 且不同的事由不同的人去做 . 已知每个人 A i 做 每件事 B j 的效率 ( 如劳动工时或成本 , 或创造的 价值等 ) 为 C ij , 问应如何进行指派 ( 哪个人做哪件 事 ), 才能使 工作效益最好 ( 如工时最少 , 或成本 最低 , 或创造的价值最大 )? 指派问题既可以说是运输问题的特殊情形 , 也 可以说是整数规划的特殊情形 . 指派问题的数学模型 ? ? Min z= ?? c ij x ij ? c ij ? 0 ? i ? 1 j ? 1 S.t. n n n x ? 1 ? ij j ? 1 n ? x i ? 1 ij ? 1 x ij ? 0 / 1 举例 ? 有 4 个工人 , 要指派他们分别完成 4 项工 作 , 每人做各项工作所消耗的时间如下表 : 问如何指派使总的消耗时间最小 ? 人 工作 甲 乙 丙 丁 A 15 19 26 19 B 18 23 17 21 C 21 22 16 23 D 24 18 19 17 第六章 目标规划 ? ? ? 多目标 的线性规划问题 ( 多目标 决策 ), 而非单 目标 . 其模型是在线性模型的基础上 , 利用正负偏差 + - 变量 (d ,d ) 、优先因子 (p k ,p k p k+1 ) 、权系数 , 对同等级或不同等级的目标进行设置 . 因其模型结构与线性规划的数学模型结构没有 本质的区别 , 所以可用单纯形法求解 . 举例 ? 某商店有五位工作人员 : 经理 1 人 , 主任 1 人 , 售货 员 3 人 . 有关情况见下表 . 设广告费对销售额的贡 献为其投入的 15 倍 , 各工作人员的收入相当于 其完成销售额的 5.5%. 问如何安排才能达到以 下的目标 :P 1 保证全体人员正常工作时间 ;P 2 至 少完成销售额 70000 元 ;P 3 主任的月收入不少于 1200 元 , 售货员 A 和 B 的月收入不少于 600 元和 400 元 ;P 4 全体人员加班时间不超过规定 ; P 5 广 告费不超过 3000 元 , 力争销售额增加 10000 元 , 前 者的重要性为后者的两倍 . 经理 主任 每小时对销售 额的贡献 ( 元 ) 144 96 每月总 工时 200 200 每月加班限 量 ( 工时 ) 24 24 售货员 A 售货员 B 54 30 172 160 52 32 售货员 C 9 100 32 第七章 整数规划 ? ? ? 最优解不是分数或小数 , 而是整数的情形 . 整数规划的一种特殊情形是 0-1 规划 , 如 指派问题 . 整数规划的解法有割平面法、分枝定界 法。 0-1 规划的解法有 0-1 隐枚举法 . 纯整数规划 整数规划 混合整数规划 运用 0-1 规划的实际问题 ? ? ? 关于固定费用的问题 相互排斥的约束条件 投资场所的选定 ------ 相互排斥的计划 ? 例 : 某公司拟在市东、西、南三区建立门市部 , 拟 议中有 7 个位置 A i （ i=1,2, …7 ）可供选择 , 规定 : 在 东区 , 由 A 1 ,A 2 ,A 3 三个点中至多选两个 ; 在西区 , 由 A 4 ,A 5 两个点中至少选一个 ; 在南区 , 由 A 6 ,A 7 两个点 中至少选一个 . 如选用 A i 点设备投资估计为 b i 元 , 每 年可获利润估计为 c i 元 , 但投资总额不能超过 B 元 , 问如何选择使年利润最大 ? 建模 解 : 先引入 0-1 变量 , 令 1, 当 A X i 点被选用 i = 0, 当 A i 点没被选用 于是 :max z= ? 7 c i x i 7 i ? 1 ? b i x i ? ? , i ? 1 x 1 ? x 2 ? x 3 ? 2 , ? x i ? 0 /