线性规划在数学建模竞赛中的应用.pdf

第3 3 卷增刊 2 0 0 8 年6 月 广西大学学报 自然科学版 J c I u r n a o fG u a n g x iU n i v e r s i t y N a tS c iE d V 0 1 3 3 S u p J u n e 2 0 0 8 文章编号 1 0 0 1 7 4 4 5 2 0 0 8 增一0 2 2 6 0 4 线性规划在数学建模竞赛中的应用 朱光军 谭洁群 王 云 广西大学数学与信息科学学院 广西南宁5 3 0 0 0 4 摘要 通过介绍线性规划的基本知识 基本线性模型 使学生在短时间内了解在数学建模竞赛中怎样利用线性 规划的思想 方法建立数学模型作一个初步探讨 关键词 线性规划 数学模型 建模竞赛 中图分类号 G 6 4 0 文献标识码 A T h ea p p l i c a t i o no fl i n e a rp r o g r a m m i n gi n m a t h e m a t i c sm o d e l l i n gc o m p e t i t i o n Z H UG u a n g j u n T A NJ i e q u n W A N GY u n C o l l e g eo fM a t h e m a t i c sa n dI n f o r m a t i o nS c i e n c e G u a n g x iU n i v e r s i t y N a n n i n g5 3 0 0 0 4 C h i n a A b s t r a c t T h eb a s i ck n o w l e d g eo fl i n e a rp r o g r a m m i n g a n db a s i cl i n e a rm o d e la r ei n t r o d u c e d s ot h a tt h es t u d e n tu n d e r s t a n dh o wt om a k eu s eo f l i n e a rp r o g r a m m i n gi d e a s m e t h o d st o b u i l dam a t h e m a t i c a Jm o d e li nas h o r tt i m e K e yw o r d s l i n e a rp r o g r a m i n g m a t h e m a t i c a lm o d e l M o d e l i n gC o n t e s t 全国大学生数学建模竞赛 已经成为许多高 校学生课外科技活动的重要项目 每年参加数学 建模竞赛的学生中相当一部分是大学一 二年级 的同学 他们刚刚修完高等数学 线性代数和概率 论与数理统计等课程 对参加数学建模竞赛所需 具备的其它数学知识以及数学建模的方法没有更 多的了解 怎样使这部分学生能更好地参加数学 建模竞赛 成为许多指导教师经常讨论的问题 据 不完全统计 在以往的数学建模竞赛题中 大概有 7 0 的问题属于优化问题 而其中绝大部分又是 属于线性规划问题 因此尽快掌握线性规划的基 本知识 学会用线性规划的思想 方法建立数学模 型显得尤为迫切 下面通过介绍线性规划的基本 知识 基本线性模型 利用线性规划的思想 方法 建立数学模型 1基本知识 线性规划一般可写作 m i n m a x f c l z l c 2 2 2 c z S t a i l z l n 2 2 2 a i H z H 6 l i 1 2 m 7 0 歹 1 2 以 1 其中厂被称作目标函数 目标函数下的等式 或不等式被称作约束条件 z z z z T 被 称为决策变量 6 6 b b T 被称为决策向 量 f c f T 被称为价格系数 一组满足 1 式约束条件的变量z z 矗的值称为可行 解 可行解的集合称为可行解域 或可行解空间 线性规划问题也就是在可行解域上寻找使目标函 数取得极小 或极大 值的可行解 称之为最优解 一般线性规划问题可以采用单纯形法 对偶 单纯形法等常用的方法求解 在数学建模竞赛中 收稿日期 2 0 0 8 一0 1 2 1 修订日期 2 0 0 8 0 3 1 7 作者简介 朱光军 1 9 6 5 一 男 广西平南人 广西大学讲师 E m a i l z h u g i g x u e d u C Y I 增刊朱光军等 线性规划在数学建模竞赛中的应用 2 2 7 通常用相应的数学软件求解 如M a p l e L i n d o M a t l a b 等 因此 如何从实际问题中构造出模型 来是最关键的 在实际应用中 可以把基本线性规 划问题的模型所讨论的问题的共同点与实际问题 的具体特点相结合 构建实际问题的模型 下面介 绍几种常见的模型 2 基本线性规划模型 2 1 食谱问题 某公司饲养实验用动物以供出售 已知这些 动物的生长对饲料中三种营养成分 蛋白质 矿物 质 维生素特别敏感 每个动物每天至少需要蛋白 质7 0g 矿物质3g 维生素1 0m g 该公司能买到5 种不同的饲料 每种饲料1k g 所含营养成分如表 1 所示 每种饲料1k g 的成本如表2 所示 求能满 足动物生长需要 又使总成本最低的饲料配方 表15 种饲料单位重量 1k g 所含营养成分 T a b 1T h en u t r i e n tc o n t e n tt h a t1k gw e i g h tf e e dc o n t a i n s 表25 种饲料单位重量 1k g 成本 T a b 2T h ep r i c eo ff e e d 饲料 A 1A 2A 3A 4A 5 成本 元0 2 0 70 40 30 5 建立模型饲料配比问题是一个线性规划模 型 r a i n 0 2 x 1 0 7 x 2 0 4 x 3 o 3 z 0 5 x 5 s t0 3 0 x 1 2 0 0 x 1 0 0 x a 0 6 0 x 4 1 8 0 x s 7 0 0 1 0 x l 0 0 5 x 2 0 0 2 x 3 0 2 0 a 0 0 5 x 5 3 0 0 5 x l 0 1 0 x 2 0 0 2 x a 0 2 0 x O 0 8 x s 1 0 zJ 1 0 j 1 2 5 模型求解利用l i n d o 可得到问题的解为z t z 2 z 3 0 z 3 9 7 4 z 5 2 5 6 4 2 4 7 4 该公司可分别购买第四种饲料3 9 7 4 k g 和 第五种饲料2 5 6 4 k g 配成混合饲料 所耗成本 2 4 7 4 元 为满足营养条件下的最低成本 模型推广一般的食谱问题可叙述为 设有理种食物 每种食物中含有 n 种营养成 分 用口u 表示一个单位的第歹种食物中含有第i 种 营养的数量 b 用表示每人每天对第i 种营养的最 低需求量 c 表示第歹种食物的单价 毛表示所用 的第J 种食物的数量 求在满足m 种营养成分需 要的同时使食物的总成本最低 一般食物问题的线性规划模型为 m i n f c 一 J 罩1 s t a i j x J b i 芒i i 一1 2 m 而 0 歹 1 2 n 这类线性规划模型还可以描述很多诸如合理 下料 最小成本运输等问题 具有很强的代表性 2 2 生产计划安排问题 2 设某企业能够生产n 种产品 要求确定那些 品种的产品及其产量 使其总收入达到最大 一 般地 在安排生产计划时 要考虑以下两方面 1 某些产品的计划任务及用户的需求 这 里分别用z 表示第J 种产品的计划最低产量 乃 o 和受市场需求量控制的最大产量 J o 2 企业自身的生产条件 设该企业有m 种资 源 如原材料 辅助材料 动力 机器设备 劳动力 自然资源等 各种资源的信息如下 a 第歹种产 品对第i 种资源的单耗 觑 第i 种资源的拥有量 勺 第歹种产品每生产一个单位产品的收人 z 第 歹种产品的计划产量 则上述问题的数学模型为 m a x f 甲 J 1 1 s t 口 工 b i i 1 2 m 与 U 巧 0 歹 1 2 咒 2 3 分派问题L 2 有设n 项任务要分给n 个人去完成 每人完 成一项 由于每人的专长不同 完成不同任务所需 的成本也不同 若第i 个人完成第歹项任务的成本 为c 种问题是 如何分配这些工作任务 使总成本 为最小 f 1 指派第i 个人做第歹项工作 1 0 不指派第i 个人做第J 项工作 则问题的数学模型为 m i n 名一 q z u j lf 异l s t 一1 歹 1 2 挖 z 一1 i 1 2 咒 z D o l 1 这些基本模型的共同点是 1 有可以选择 2 2 8广西大学学报 自然科学版 第3 3 卷 的某一方案 它们可用一组变量五 i 1 2 m 表示 2 变量五 f 一1 2 m 满足一定的 约束条件 3 有一个决策目标 在数学建模比赛 中 假如遇到的问题是与上述特点相符合 可以利 用建立以上基本模型的思想 方法结合所面对的 问题的具体特点建立数学模型 下面考虑讨论建 立2 0 0 0 年网易杯全国大学生数学建模竞赛召题 问题 1 的模型 3钢管订购和运输问题 要铺设一条A 一A 一 一A s 的输送天然 气的主管道 如图1 所示 经筛选后可以生产这种 主管道钢管的钢厂有S S 5 图中粗线表示 铁路 单细线表示公路 双线表示要铺设的管道 假设沿管道或者原有公路 或者建有施工公路 圆圈 点 表示火车站 每段铁路 公路和管道旁 的阿拉伯数字表示里程 单位k m 为方便计 1 k m 主管道钢管称为1 单位钢管 一个钢厂如果承 担制造这种钢管 至少需要生产5 0 0 个单位 钢厂 毋在指定期限内能生产该钢管的最大数量为丑个 单位 钢管出厂销价1 单位钢管为只万元 如表 3 1 单位钢管的铁路运价如表4 10 0 0k m 以上每 增加1 至1 0 0k m 运价增加5 万元 图1铁路 公路网及天然气管道 F i g 1 T h er a i l w a y h i g h w a yn e t w o r ka n dg a sp i p e l i n e 表3单位钢管的出厂销售价 管 如果把管网分成每1k m 一段 设共有 段 编 T a b 3T h ep r i c eo fs t e e lt u b e 号为h 一1 则现在问题变为 如何从这7 个 i 1234 567 毛8 0 08 0 01 0 0 02 0 0 02 0 0 02 0 0 03 0 0 0 P i1 6 01 5 51 5 51 6 01 S 51 5 0 1 6 0 表4单位钢管的铁路运价 T a b 4T h er a i l w a y Xt r a n s p o r t a t i o np r i c e 里程 k m5 0 1 6 0 06 0 1 7 0 07 0 1 8 0 08 0 1 9 0 09 0 1 1 0 0 0 运价 万元3 74 45 0S 56 0 公路运输费用为1 单位钢管每公里0 1 万元 不足整公里部分按整公里计算 钢管可由铁路 公路运往铺设地点 不只是运到点A l A 而 是管道全线 请制定一个主管道钢管的订购和运输计划 使总费用最小 给出总费用 3 1模型1 模型分析制定订购和运输计划 意思是指 在钢厂 i 一1 7 处订购多少钢管以及确定 相应的运输路线 1k m 长的钢管为1 单位的钢 工厂订购总数为r 段 单位 钢管 使得费用最小 即 每一段 共r 段 应从哪个工厂订购以及怎样 组织运输路线才使总费用最小 可以看出这与分 派问题类似 总费用包括购买钢管的费用与运输费用 其 中购买钢管的费用与运输路线无关 运输费用包 括从钢厂经铁路 公路到管道结点 再沿管道旁的 公路到施工处的运输费用 因此可以把运输费用 分为从钢厂到管道结点的费用和沿管道旁的公路 到施工处的运输费用 注意 在 A A 川 之间的 一段上 钢管经A 或A 川运到施工处 模型假设 m 和挖分别表示钢厂数和管网中 的结点数 c j 表示一个单位钢管从钢厂只到管网 结点A 的最小运价 t 毋表示管网上相邻结点A 与A 之间的边长A A 里程数 e i f i 表示钢厂5 到 编号为h 这段的最低费用 包括订购和运输费 用 增刊 朱光军等 线性规划在数学建模竞赛中的应用2 2 9 f 0 第h 段钢管不在钢厂 出订购 钰一1 1 第h 段钢管在钢厂s 出订购 则在毛处订购钢管的数量为2 小 1 r 中1 的个数 下面以z 讯为决策变量建模 模型建立 1 求q 这个涉及求最短路径的问题 在复 杂的情形下 用D i j k s t r a 算法求解 2 求e 曲 编号为h 的一段可能是从矗运到 A 后沿A 方向运到施工处 或者是从凡运到A 后沿A J 方向运到施工处 设编号h 这一段在管网 的边A A 上从A 算起的第q 段 则已m m i n p r 幻 0 1 q A 0 1 一9 1 若管 网是直线 A A 可依次编号 正取 1 以2 认 i 一1 m h 1 作决策变量 建立模型 r a i n 孙 一 一 f l l 1 1 s t 彳请 l h 一1 r 百 o U 5 0 0 j 函 i 1 m 2 讯 0 1 这个模型的缺点是决策变量2 的个数较多 用相关的软件求解存在一定的困难 为此考虑下 面的模型 3 2 模型2 6 若以 记一个单位钢管从第i 个钢厂s i 运到 第歹个枢纽站点 的最小购运费用 为咒到 的运量 再把A 得到的钢管分解为向A A 一路段 铺设和向以 A 路段铺设的两部分 记两部分的 数量分别为孔和z A J A J l 路段的长度 e P 需铺设 的钢管数量 为乃 则从巩到A 的购运总费用为 7l S f 廿z u 而向两边铺设的费用为0 1 i 1j 1 堑垡 上旦 o 1 丝鱼 旦 问题的模型为 71 5 1 5 r a i n f 拍 譬 啄 J 1 Y J Y j 1 i lj I j 1 s t q o U 5 0 0 矗 i 1 州2 7 j l 三 z J z j y J Y j I z i 2 t l Z l f i20 Y z21 0 4 z I j 0 j 0 巧 0 f 1 2 7 1 2 1 5 1 5 模型的求解 由于约束条件 z o u 5 0 0 矗 i 一1 2 7 的存在 因此模型的求解 不能简单地调用二次规划的软件 一种合理的解 决办法是首先将该约束条件改为松弛条件 0 z 巧 跏i 1 2 7 J 1 1 于是模型便成为典型的二次规划 如果其最优解 符合原有的约束条件 则便是问题的最优解 如果 存在个别的i 使 巧 o 5 0 0 则可以针对这 J I 些作调整 在求解过程中关键是要求出 4 结束语 对于在数学建模竞赛中遇到的能用线性模型 描述的问题 一方面 要考虑利用现有基本线性模 型的思想 方法结合所讨论问题的具体特点建立数 学模型 在此基础上进一步要考虑建立符合具体问 题特性的具有创新特色的模型 另一方面 在模型 建立的同时要兼顾到模型的求解能否实现 因此 在竞赛前应加强对基本模型的理解 提高利用基本 模型的思想 方法对实际问题建立数学模型的能力 以及利用相关数学软件求解模型的能力 参考文献 1 谢云荪 张志让 数学实验 M 北京 科学出版社 1 9 9 9 2 谢金星 薛毅 优化建模与L I N D O L I N G O 软件 M 北京 清华大学出版社 2 0 0 5 3 3 温清芳 最优化方法在数学建模中的应用口 宁德 师专学报 2 0 0 7 5 4 姜启源 谢金星 叶俊 数学模型 第三版 M 北京 高等教育出版社 2 0 0 3 5 刘锋 数学建模 M 南京 南京大学出版社 2 0 0 5 6 朱道元 数学建模案例精选 M 北京 科学出版社 2 0 0 3 7 张干宗 线性规划E r a 武汉 武汉大学出版社 2 0 0 4 责任编辑刘海涛 线性规划在数学建模竞赛中的应用线性规划在数学建模竞赛中的应用 作者 朱光军 谭洁群 王云 ZHU Guang jun TAN Jie qun WANG Yun 作者单位 广西大学数学与信息科学学院 广西南宁 530004 刊名 广西大学学报 自然科学版 英文刊名 JOURNAL OF GUANGXI UNIVERSITY NATURAL SCIENCE EDITION 年 卷 期 2008 33 z1 被引用次数 0次 参考文献 7条 参考文献 7条 1 谢云荪 张志让 数学实验 1999 2 谢金星 薛毅 优化建模与LINDO LINGO软件 2005 3 温清芳 最优化方法在数学建模中的应用 期刊论文 宁德师专学报 2007 05 4 姜启源 谢金星 叶俊 数学模型 2003 5 刘锋 数学建模 2005 6 朱道元 数学建模案例精选 2003 7 张干宗 线性规划 2004 相似文献 10条 相似文献 10条 1 期刊论文 吴雪琴 线性规划在物流运输中数学模型的建立及应用 江西电力职业技术学院学报2007 20 1 介绍了建立物资调运 车辆调度的线性规划数学模型 以及建立线性规划的条件 从而用现代化工具计算出合理运输 实现运输费用最省 物流经济效 益最大化 2 学位论文 王少朋 随机线性规划在企业内部资源优化配置中的应用 1997 该文首先分析了中国卫星电视天线产业的发展情况 给出市场价格统计结果 并对天线生产过程中企业内部资源配置建立数学模型 然后介绍随机线性 规划 SLP 定义条件最优解 给出了目标参数为离散随机变量的随机线性规划 一类SLP的一种简单实用的算法 列出求解框图 并在计算机上实现 最后 分别应用线性规划 LP 和SLP模型 对两家天线生产企业内部资源配置进行研究验证 结果说明SLP模型的有效性 并对企业的内部资源配置提出优化建议 3 会议论文 胡俊辉 林俊 基于线性规划的高合金钢配料数学模型 2008 基于线性规划方法研究了高合金钢配料成本最小化问题 以返回料 合金 吨钢料耗 回收率等边界条件建立数学模型 利用在EXCEL中调用商业化软 件MATLAB中线性规划模块的算法 建立简单易用的计算软件 可实现对多元合金钢的最低成本配料 4 学位论文 张金旺 最优化方法在一类出版社资源优化配置中的应用 2007 本文针对一类出版社 带有出版分社 资源优化配置问题进行研究 以某教材类出版社为例 从利润 市场需求 资源 书号 各分社申请量 各分 社人员能力状况五个方面的因素运用优化方法建立数学模型 其优化目标是使出版社的年利润达到最大 即对该出版总社下一年效益值进行线性规划 运用运筹学思想与经济学理论对出版社书号资源进行优化配置 使其达到该出版社的利润最大 资源消耗最少 人员配置最优 给出一个明确的分配 方案 向该类出版社提供有益的建议 所建立的数学模型在此类出版行业的资源配置方面具有广泛的应用 本文给出了三个模型 模型一除考虑到出版社内部条件的约束情况和市场外部约束情况外 还考虑到了利润最大的市场原则 合理的构建了线性规 划数学模型 并根据01 05年度同一课程一个书号的平均利润 预测出2006年度单位书号的利润 从而运用所构建的数学模型对出版社的书号进行最优的 分配 根据近三年的单个书号的实际利润走势和每个出版分社5年来的计划准确度改进模型一的目标标函数及约束条件 建立线性规划模型二 利用灰色建 模预测2006年的各分社的单位书号的利润 用该值构建线性规划模型三 从而计算出2006年9各分社的书号 模型一至二中我们均运用Matlab数学软件 运行linprog命令 模型三 我们用Mathematica数学软件编制了 的运算程序 从而计算 出2006年各出版社的书号 通过问卷调查的统计 总结出商品市场占有率和满意率的走势 我们寻找出该出版社的各类图书的市场前景 并加以分析 从而约束书号的分配 以得到出版社书号的最优化的分配方案 使其出版社的利润最大化 在文章的最后 我们对模型一及模型三进行了简单评述 并指出了待改进的工作 对这三个模型的决策结果进行了分析 结果表明 第三个模型构 建的结果更为合理 使得出版社的利润达到了最大 5 期刊论文 李朝霞 线性规划的数学模型及实际应用 宿州教育学院学报2006 9 1 线性规划主要是研究在约束和目标都既定的前提下 如何优化整个系统 以最小输入得到最大输出 线性规划广泛应用于工农业 军事 交通运输 决 策管理与规划 科学实验等领域 所研究的课题也是多方面 本文通过介绍一些应用的实例 来提高数学建模技巧并为新的应用奠定基础 6 期刊论文 张奎俊 尚书河 时美荣 ZHANG Kui jun SHANG Shu he SHI Mei rong 网络计划费用优化中的线性规划 数学模型 山西建筑2008 34 18 介绍了线性规划数学模型建立的方法和步骤 运用Matlab优化工具箱进行分析计算 并通过具体实例对模型进行检验 将计算结果与纯压缩网络计划的 结果进行了对比分析 指出运用数学模型对网络计划优化配置更加简单 可靠 7 期刊论文 吕莹 毕璐璐 陆启彦 刘广臣 山东省高速公路路面的最优维护数学模型 科技风2010 5 本文通过对路面维护的各项指标分析并进行归一化处理 得到路面性能评价指标PQI 利用线性规划思想 建立以效果 费用比为目标函数的最优维护数 学模型 选择合适的养护策略 为高速公路路面的维护提供最优维护策略 8 期刊论文 郭连云 公保才让 张旭萍 丁生祥 金元锋 线性规划对以草定畜 季节性休牧育草的预测 青海省同 德县以草定畜 季节性休牧育草的优化