几个“简单”的问题的数学模型.ppt

钞票问题 CashProblem 背包问题 Knapsackproblem 装箱问题 BinPacking 城市公交查询系统的数学模型电梯问题的数学模型流水线设计问题 几个 简单 的问题 背包问题 Knapsackproblem 一般情形 有一个容量为b的背包和数量足够多的价值和体积分别为c1 c2 cn和a1 a2 an的物品 问如何装这些物品使得价值最大 数学模型 由钞票问题想起的 现需要数量为C的钞票 钞票规格有1分 5分 1角 2角 5角 1元 5元 10元 50元和100元 问最少需要多少张这些规格的钞票能够支付数量为C的钞票 数学模型 装箱问题 BinPacking 有一批容量为1的箱子和体积分别为a1 a2 an的物品 问最少需要多少箱子能够装下这些物品 数学模型 0 1背包问题 Knapsackproblem 特殊情形 有一个容量为b的背包和n个价值和体积分别为c1 c2 cn和a1 a2 an的物品 问如何装这些物品使得价值最大 数学模型 GreedyAlgorithm 价值大的物品优先装 不妨假设 四 城市公交查询系统的数学模型 问题 第29届奥运会明年8月将在北京举行 北京的公交将面临更大的挑战 这些年来 公共交通工具 简称公交 包括公汽 地铁等 发展迅速 目前北京市的公交线路已达800条以上 使得公众的出行更加通畅 便利 但同时也面临多条线路的选择问题 针对市场需求 某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统 为了设计这样一个系统 其核心是线路选择的模型与算法 应该从实际情况出发考虑 满足查询者的各种不同需求 请你们解决如下问题 1 仅考虑公汽线路 给出任意两公汽站点之间线路选择问题的一般数学模型与算法 并根据附录数据 利用你们的模型与算法 求出以下6对起始站 终到站之间的最佳路线 要有清晰的评价说明 1 S3359 S1828 2 S1557 S0481 3 S0971 S0485 4 S0008 S0073 5 S0148 S0485 6 S0087 S36762 同时考虑公汽与地铁线路 解决以上问题 3 假设又知道所有站点之间的步行时间 请你给出任意两站点之间线路选择问题的数学模型 附录1 基本参数设定 相邻公汽站平均行驶时间 包括停站时间 3分钟相邻地铁站平均行驶时间 包括停站时间 2 5分钟公汽换乘公汽平均耗时 5分钟 其中步行时间2分钟 地铁换乘地铁平均耗时 4分钟 其中步行时间2分钟 地铁换乘公汽平均耗时 7分钟 其中步行时间4分钟 公汽换乘地铁平均耗时 6分钟 其中步行时间4分钟 公汽票价 分为单一票价与分段计价两种 标记于线路后 其中分段计价的票价为 0 20站 1元 21 40站 2元 40站以上 3元地铁票价 3元 无论地铁线路间是否换乘 注 以上参数均为简化问题而作的假设 未必与实际数据完全吻合 附录2 公交线路及相关信息 见数据文件B2007data rar 五 电梯问题的数学模型在日常生活中 我们大家经常要乘电梯 但是在当前电梯运行系统中 乘客是在线到达的 也就是事先不知道他们的有关信息 不知道有多少乘客要乘电梯 他们何时到达 在乘客到达并且未进入电梯前 也仅仅只知道他们所处的位置和要乘的方向 并不知道他们要到达什么地方 目前 电梯的主要按钮是在电梯内 乘客到达仅仅只告诉电梯要上或下 电梯并不知道更多的信息 请您分析这种信息不完全对电梯运行带来的损失 并据此提出电梯按钮设计的改进意见 分析改进效果 我们是否能够将按钮设计在电梯外 使得电梯的运行效率得到提高呢 在乘电梯时 由于乘客都是在线到达 我们是否能够基于这一特征来建立电梯在线运行的数学模型呢 在乘电梯时 等待常常是不可避免的 我们自然要问 通常情况下 我们需要等待多长时间才能到达目的地呢 有没有一种好的电梯运行方案使得乘客能够尽可能快到达呢 为此 我们需要建立电梯运行的数学模型 并回答如下问题 1 在当前电梯运行系统中 乘客是在线到达的 请分析乘客在线到达的特征 建立电梯在线运行的数学模型 研究电梯的最优运行方案 探讨乘客的满意情况 2 研究电梯的按钮设计 对电梯的按钮提出改进建议 并分析改进效果 3 在离线情形 所有信息已知的情形 下 建立电梯运行的数学模型 并比较离线和在线两种情形下电梯运行的优化方案和电梯的运行效率 4 由于电梯是一个系统 请先研究单台电梯的情形 再对多台电梯系统进行全面研究 分析 讨论 并请你采集电梯数据验证你的模型 六 流水线设计问题 某缝纫机厂要设计一条生产流水线 流水线有两条