LINGO软件在数学建模中的典型应用举例

产业聚焦　软件阔Ｉｎｄｕｓｔｒｙ　ｆｏｃｕｓ　ＬＩＮＧＯ软件在数学建模中的典型应用举例　瞿勇，袁昊劫，黄登斌／海军工程大学理学院　摘要：本文给出了几个在数学建模中ＬＩＮＧＯ软件的典型应用实例，运用在数学软件课程教学中会使学生更容易理解和　掌握ＬＩＮＧＯ软件的编程语言与技巧。　关键词：ＬＩＮＧＯ软件；数学建模；数学软件；线性规划；非线性规划　全　—上—　ＬＩＮＧ０软件［１－２１可用来解决整数规划等优化问　算　广到大规模情形。　例２：　（汽车厂生产计划）　汽车厂生产３种类型汽　题，在求解规划问题时具有易于输入、修改、求解和程序　执行速度快的特点，为求解规划问题带来了极大的方便。　因此，数学软件课程教学需要介绍ＬＩＮＧＯ软件的编程语言　及其在数学建模中的应片ｊ。　１　ＬＩＮＧＯ软件的典型应用实例　例１：　（钢管下料问题）”。　某钢管零售商从钢管厂　进货，将钢管按照顾客的要求切割后售出，原料钢管为　１９ｍ。　车，已知各类型每辆车对钢材、劳动时间的需求，利润及　工厂钢材与劳动时间每月的现有量。　（１）制订月生产计划，使工厂的利润最大。　（２）如果生产某一类型汽车，则至少生产８０辆，那　么最优生产计划如何改变？　设每月生产３科ｔ类型汽车的数量为ｘ．，３种类型每辆　车对钢材的需求为ａ；，对劳动时间的需求为ｔ．，利润为ｒ，　（ｉ＝ｌ，２，３）。　对于第（１）问建立如下线性规划模型　＾　，　：：－，・Ｙ　（１）现有客户需要５０根４ｍ，２０根６ｍ和１５根８ｍ的钢　管，问如何下料最节省？　（２）此外该客户除需要（１）中钢管外，还需要ｌ０根　一　５ｍ的钢管。该零售商规定采用的不同切割模式不能超过３　种，问如何下料最节省？　此问题是一个经典问题，第１问由于合理切割模式共　有７种，设第ｉ种模式切割的原料钢管数为Ｘ．（ｉ－１，２，…，　７），建立如下线性规划模型：　ｘｉ＝０或ｘｉ＝＞８０　｝∑“　＿　６００　：Ｊ　１　Ｉ　３　：∑ｆ，一　６０００　ｌ，一１　Ｉ　，≥０，ｉ＝１，２，３　对于第（２）问，第３个约束条件改为：　ｆ４　ｌ十３　！＋２ｘ；＋＿＋　５　５０　・，・Ｘ．＋２Ｘ４＋ｘ５＋３Ｘｈ≥２。　而此约束条件是非线性的，若将其分解为８个线性　子模型，则此思路不能推广到大规模，故引入０—１变量Ｙ；　（ｉ＝ｌ，２，３），将其化为线性规划，即将第３个约束条件　第２问合理切割模式比较多，要用约束条件界定合理　切割模式。由于不同切割模式不能超过３种，设按第ｉ种模　式切割的原料钢管数为ｘ．（ｉ－１，２，３），第ｉ种切割模式下　每根原料钢管切成４ｍ，５ｍ，６ｍ和８ｍ的钢管数分别为ｒＩ１，　ｒＩ２，ｒ　ｒ　（ｉ＝ｌ，２，３）。建立如下非线性规划模型：　｛　以如下方式线性化：　Ｘｉ≤Ｍｙｉ，ｘｉ＝＞８０ｙ。，Ｙｉ∈｛０，１｝，ｉ＝ｌ，２，３　其中Ｍ为较大的数（取Ｍ＝５００￣可）。　此例的典型意义就在于引入０一ｌ变量后，将非线性　规划转化为线性规划，而且用Ｌｉｎｇｏ集合语言编程方便可　行，容易推广。　例３：ＤＶＤ租赁（ＣＵＭＣＭ２００５Ｂ问题２）［４１　考虑如下在线ＤＶＤ租赁问题。顾客缴纳月费成为会　Ｍｉｎ：＝∑　３　∑　≥，）　，＝Ｉ，２，３．４：　４　￡一　，ｊ＜　，，名≤￡　员，订购ＤＶＤ租赁服务。会员对哪些ＤＶＤ有兴趣，只要在　线提交订单，会员提交的订单包括多张ＤＶＤ，这些ＤＶＤ是　基于其偏爱程度排序的。附表列出了网站１００￣ＤＶＤ的现　有张数和当前要处理的１０００位会员的在线订单，如何对这　些ＤＶＤ进行分配，才能使会员获得最大的满意度？　、厂Ｌ　其中ｂ　１，（’－１，２，３，４）分别表示４；￣００钢管的需求　量、长度，Ｌ为原料钢管的长度。　此例的典型意义在于由线性规划到非线性规划，由简　单到复杂，非线性规划模型用Ｌｉｎｇｏ集合语言编程容易推　ｆ１．　ｉ个会　分刮厂　，种１）ｖＤ　一１０，　小　个　牝分刘　，ｆＩｌＩ）ＶＤ’　●卜＿——————————一　中图分类号：０１４１．４－２　６３　Ｉ　ＣＤ　Ｓｏｆｔｗａｒｅ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ　ｎｄｕｓｔｒｙ　ｆｏｃｕｓ软件园　建立如下０一ｌ规划模型：　产业聚焦　其中Ｓ为起始站，ｅ为终点站，ｔｉ，表示从第ｉ站到第ｊ站的　㈨　＿　＾∑ＪＩＯ００∑ｔＯＯ　ｌ　ｌ×ｌ㈣Ｏ　‘　最短时间。　此例的典型意义在于第２个约束，它不仅很好地解决　∑　．，　ｌ，２，－－，，１００　了回路问题，而且化成线性规划。当然由ｙ－ｎ＝１９５７，规模　很大，在求解上述线性规划模型时，采用传统求解方法时　不可行，但用Ｌｉｎｇｏ软件可通过稀疏矩阵来实现。　例５：交巡警服务平台的设置与调度（ＣＵＭＣＭ　２０１１Ｂ）［６－７］　某市中心城区Ａ的交通网络和现有的２０个交巡警服务　平台的设置情况相关的数据信息见附件。请为各交巡警服　务平台分配管辖范围，使其管辖范围出现突发事件时，尽　量能在３分钟内有交巡警到达事发地。　∑　≤３，ｉ＝１．２，－－－，１０００　Ｘ　＝Ｏ或１，　＝１，２　…．１０００，－，＝１，２，－一．１００　其中ｃ．为第ｊ种ＤＶＤ的现有量，巩ｊ，ｂ　分别表示第ｉ个会　员对第ｉ种ＤＶＤ的偏爱度、满意度，定义为：　．　１ｄ１．　　（）　ｌ０，“．　０　引入０—１变量：　一ｊ１，　：　潞Ｉｌｌ｝１勒、　僻鞭，　‘｛０，　！　它．　设第ｉ路口的发案量为Ｗｊ则第ｉ平台的总工作　为：　此例的典型意义在于对于大规模问题，Ｍａｔｌａｂ软件不　能处理，因为这涉及一个１０００００×ｌＯ００的矩阵（超出了　ＭａｔｌａｂＨ　‘ｅ处理的范围），而用Ｌｉｎｇｏ软件编程不仅可以解决　大规模问题，而且程序易于输入、修改，求解程序执行速　度快，容易推广。　例４：乘公交看奥运（ＣＵＭＣＭ２００７Ｂ）　某公司准备研发一个解决公交线路选择问题的自主查　询计算机系统，该系统的核心是线路选择的模型与算法，　要求满足查询者的不同需求。解决如下问题：仅考虑公汽　线路，给出任意两公汽站点之间线路选择问题的一般数学　Ｇ，：∑　’　（　：ｌ　２，…　，７）　Ｉ　：　第ｉ路１３到第ｉ平台的最短距离记为ｄ，ｉ则第ｊ平台到第ｉ路　口的的出警时问可表示为Ｔｌ　＝ｄ　ｘ　由于有６个路口到任意　平台的时问都超过３分钟，所以将它们分配给距离最近的　平台管辖，建立如下０—１规划模型：　ｍｉｎ　Ｄ（Ｇ）　∑　＝１（　Ｊ　ｌ　．…，　）　ｔ　ｔ／＝ｔ，２　…，　）　模型与算法，并根据附录数据，利用此模型与算法，求出　所给６对起始站一终点站之问的最佳路线。　引入０一ｌ变量ｘ　即设　ｆ　１．　Ａ＂ｎ一　≤３　（　，：１，２，　一，／／，ｉ≠２８，２９，３８，３９．６１．９２）　≤３ｍ　（　）（，　１，２，…，　，ｉ＝２８ｔ２９，３８，３９　６ｔ，９２）　＝Ｏ或１　（　ｌ　２一，　，：１，２，…，　）　．弧“．　｝　起，　划终点的鼢｝　，　其中，）（（　｝＝　∑（（　一　）　为样本方差，　，ｆ　。　万一１÷ｒ　一其中ｉ，ｉ分别表示两站点，而弧（ｉ，Ｊ）表示从第ｉ站　”台”　为平均工作量。　到第ｉ站的路线。　建　行程总时间为目标的最短路模型如下：　此例的典型意义在于分配模型足非线性规划，而且使　Ｄ（Ｇ）最小体现了工作量的均衡性。用Ｌｉｎｇｏ集合语言编　程，编写程序非常方便，而且结果可直接输出到ＥｘｃＥＬ表　ｍｉｎ∑，　Ｖ，　｛５（∑．　—１）　３　∑Ｘｉ　－Ｉ≤　格，执行速度也非常快。　２结束语　介绍了几个在数学建模中线性规划与非线性规划的　典型实例（例３，例４，例５均为历年数学建模赛题），应　用ＬＩＮＧＯ软件求解，非常典型，运用在数学软件课程教　∑　一∑　ｒ　ｌ　学中，会使学生更好地掌握建模思想，并且更容易掌握　ＬＩＮＧＯ软件的编程语言及技巧。　参考文献：　［１】谢金星，薛毅．优化建模与ＬＩＮＤＯ／ＬＩＮＧＯ软件【Ｍ］．北京：清华大学出版社，２００５．　［２】袁新生，邵大宏，郁时炼．ＬＩＮＧＯ和Ｅｘｃｅｌ在数学建模中的应用［Ｍ］．北京：科学出版社，２００７．　［３】姜启源，谢金星，叶俊．数学模型（第三版）【Ｍ］．北京：高等教育出版社，２００７．　［４］王颖，高德宏，施恒．ＤＶＤ租赁优化方案［Ｊ］．工程数学学报，２００５（０７）：７６—８４．　【５】汤志高，王继利，曹莹瑛．公共交通系统最佳路径模型与算法［Ｊ】．工程数学学报（增刊二），２　００７（２４）：８　３—９４　【６］叶云佳，刘剑，王禹．交巡警服务平台的设置与调度方案研究【Ｊ］．工程数学学报（增刊一），２０１１（２８）：９８－１　０４　［７】但琦，韩中庚，杨廷鸿．交巡警服务平台的设置与调度模型［Ｊ】．工程数学学报（增刊一），２０１１（２８）：１　０５—１１　５．　作者简介：瞿勇，男，副教授，主要研究方向：对策理论、系统优化与决策及算法编程与实现。　作者单位：海军工程大学理学院，武汉４３００３３　ＣＤ　Ｓｏｆｔｗａｒｅ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ　Ｉ　６４