数学建模启发式算法范文第1篇

关键词：运输模型；选址问题；整数规划；分支定界算法

中图分类号：TG659 文献标识码：A 文章编号：1009-2374（2013）10-0022-02

1 概述

RDC全称为Regional Distribution Center，即区域分发中心。RDC是现代企业物流运作的一种常见模式，是企业进行产品分发和配送的中心。本文研究的RDC配送模式如图1所示，产品生产完毕后由公司CDC先运往各个RDC进行暂存，然后再从各个RDC分发至各地的零售商。通过RDC网络的建立，可以提高对顾客需求的反应速度，加速产品的流通。

RDC的选址问题，是指在供应点（CDC）和若干需求点（零售店）的经济区域内，选择若干合适的地址建设RDC的规划问题。Aikens（1985）、Holmberg（1999）对选址问题的模型和算法进行了综述，由于主要考虑运费费用和建造费用，因此我们使用运输模型进行建模。运输模型是NP-hard问题，多数文献采用启发式或元启发式方法进行求解，如张培林和魏巧云（2003）使用启发式算法求解了物流配送中心选址问题；王恪铭等（2012）采用了元启发式算法中的遗传算法和禁忌算法，对灾后重建地区新增血站选址问题进行了研究；王竹芳等（2012）研究了救灾物资的运输问题，采用了启发式算法中的改进算法（变量闭回路法）。

本文使用精确求解的算法进行求解。实践表明在规模较大时，常规数学优化软件难以在有限时间内求解，故本文设计隐枚举方法对问题进行优化求解。隐枚举方法中的子问题是大大简化的线性规划问题，可以使用数学规划软件进行计算。

2 数学模型和算法

2.1 模型建立

2.2 求解算法

3 案例研究

公司在建RDC仓库时主要考虑的是地价、交通便利程度和优惠政策，在长时间的发展过程中建立了很多RDC，仓库维护费用很高，公司希望能够减少仓库降低运营成本。如何合理地布置仓库以及仓库的供应范围，可以使得公司在满足一定需求的基础上，使费用尽可能少，成为公司现在的一个突出问题。

公司计划采用的原方案是6个地址都建设RDC，通过模型计算可知方案的年运营费用为416.99万元，其中仓库维护费用为284.64万元，运输费用为132.35万元。通过使用模型进行优化计算后可知，最优方案的年运营费用为273.45万元，其中仓库维护费用为101.24万元，运输费用为172.21万元，RDC数目由6个减少为3个，减少费用：416.99-273.45=143.54万元。

4 结语

为了提高企业物流网络的运营效率，降低企业运输和仓储的总成本，本文建立了运输模型并设计隐枚举算法求解，来指导RDC的选址决策。计算结果表明，进行优化计算的方案能够大幅度降低企业物流网络的运营费用。本方法为企业进行物流网络规划提供了决策依据，对于企业进行生产型建设也具有参考价值。

参考文献

[1] 张培林，魏巧云.物流配送中心选址模型及其启发式算法[J].交通运输工程学报，2003，3（2）：65-68.

[2] 甘应爱，田丰，胡运权，等.运筹学（第三版）[M].北京：清华大学出版社，2005.

[3] 陆朝荣，李乐喜，黄永平.基于LINGO的物资运输最短时间计算[J].运筹与管理，2012，21（2）：89-91.

[4] 曹玉敏.基于0-1整数规划的选址决策[J].经营管理者，2011，11：252.

[5] 王恪铭，马祖军，郑斌.灾后重建地区新增血站的选址问题研究[J].运筹与管理，2012，21（1）：136-141.

[6] 王竹芳，缪文清.一种求解救灾物资运输问题的改进解法[J].运筹与管理，2012，21（1）：142-146.

[7] AikensC.H.Facilitylocationmodelsfordistribution planning[J].EuropeanJournalofOperationalResearch，

数学建模启发式算法范文第2篇

关键词：计算思维；教学模式；教学方法；思维能力；学习能力

中图分类号：G642 文献标识码：A 文章编号：1009-3044（2013）18-4276-03

美国心理学和教育学家Robert J.Sternberg指出：思维教学的核心理念是培养聪明的学习者，教员不仅要教会学员如何解决问题，也要教会他们发现值得解决的问题。教员要为学员提供足够的思维空间，设法激励和引导学员自主学习，发现问题所在继而解决问题[1]。思维教学要以所教授的学员为核心，以培养思维能力为目的，使学员既在思维活动中学习知识，也能够学习思维的方法，达到“鱼”“渔”同授的目的，培养学员良好的思维能力。

1 计算思维

计算思维最早是在2006年，由曾任美国卡内基·梅隆大学计算机科学系主任的周以真（Jeannette M.Wing）教授提出的，他指出：“计算思维代表着一种普遍的认识和一类普适的技能，每一个人，而不仅仅是计算机科学家，都应热心于它的学习和应用。计算思维是每个人的基本技能，不仅仅是计算机科学家。我们应当使每个孩子在培养解析能力时不仅掌握阅读、写作和算术，还要学会计算思维。[2]”

中国科学院计算所李国杰院士也指出：“计算思维是运用计算机科学的基础概念求解问题、设计系统和理解人类行为，它选择合适的方式陈述一个问题、对一个问题的相关方面建模，并用最有效的办法实现问题求解。[3]”

因此，对计算思维的认识我们可以这样来理解：计算思维是运用计算机科学的基础概念来进行问题的求解，它是一种本质的、所有人都必须具备的思维方式，就像读书、写字一样，成为人们基础的、不可缺少的思维方式。我们要准备会议，把开会所需的东西放进公文包，这就是“预置和缓存”；当你弄丢了自己的手机，沿着走过的路线去寻找，这就叫“回推”；在食堂排队去买饭时，站在哪一队更快呢？这就是“多服务器系统”的性能模型。这些都是计算思维在我们生活中的运用。学会计算思维，是在信息社会中创新的需要。要培养出创新型人才，教育在思想和方法上就必须摆脱传统教学的偏见，让学员运用高效的思维去思考。

2 基于计算思维的教学模式探索

计算思维是当前教育系统十分关注的一个问题，该文研究的基于计算思维的教学模式，就是综合利用计算思维的教学策略，构建以教员为主导，以学员为主体、以能力培养为目标的思维教学模式。通过任务引领和问题探究，让学员在不断的探索研究过程中启发思考、总结规律、掌握科学方法，培养学员的创新能力和科学精神，提高独立思考和解决问题的能力。

教员在教学过程中创设提出问题的实际情境，刺激学员发现问题，提出高质量的问题，然后不断引导和启发学员采用转化、约简、递归、仿真、启发式推理等方式进行问题的思考和研究解决的方法[4]。在此过程中，学员对所学知识进行重构，对新旧知识进行意义建构的过程就是计算思维能力培养的过程。通过这个过程，计算思维潜移默化地被植入学员脑内，学员的抽象思维及推理能力被有效地建立起来。当学员掌握这一思维方法以后，教员再启发学员运用所学方法解决其它方面的问题。其教学基本步骤为：一是设置启发性问题，调动学员的学习积极性，激发学习热情；二是用计算思维的方法提示学员，启发其进行独立的思考；三是将学习资源和学习方法通过网络或其它形式提供给学员，指导学员进行学习；四是指导小组讨论、交流，帮助学员对所学知识的内化和进行知识体系构建；五是对学员的学习情况进行总结讲评，提出拓展性问题，深化知识的理解。

学员在学习过程中要根据教员的教学进程，紧跟教学思路，完成各类教学活动。一是根据教员创设的情境，进入学习状态，形成学习心理；二是根据教员的启发进行思考，展开相应的学习动作；三是对学习资源进行加工整理和提练；四是进行小组协作、讨论交流、共享学习资源、内化知识形成体系；五是运用所学方法对知识进行迁移和拓展。

3 基于计算思维的教学案例应用

基于计算思维教学模式我们在不断探索过程中，在进行VB语言程序设计的教学中，我们运用了这种教学模式，起到了良好的效果。

3.1创新情景，激发学习兴趣

第一步，教员设置基于计算思维的启发性问题。

例如，在学习VB语言的“递归算法”时，我们先设置启发性的问题来吸引学员的注意力：

教员在纸上写一个词“坚持”，在上课之前事先告诉其中的一个学员，要求从第一排的第一个学员开始，每位学员只问他相邻的学员，每位学员最多只能被问一次，而且一个学员不能再问第二人，当任何一个学员知道了答案，要求立即告诉曾经问过他的那个学员，不能告诉其它人，然后知道内容的学员，继续向前告之，以此类推；一直到第一个学员结束。在这个过程中，第一个学员想知道结果，就必须第二个学员知道，第二个学员想知道结果，就必须第三个学员知道，同理，一直往后进行；当有一个学员知道结果后，就逐级向前告知，一直返回到第一个学员，任务结束。这个过程就是递归算法的思想的简单表述。

学员在学习过程中兴趣很高，与纯粹的数字问题相比，学习起来要快，更加容易走进递归的思维模式，为进一步学习递归算法埋下伏笔。

3.2 运用计算思维的方法，启发思考

第二步，教员将计算思维的方法融入教学的过程中，启发学员运用计算思维的方式进行思考。教学过程中，教员要掌握好教学进程，在恰当的时机和关键环节，提示学员用计算思维各种方法来思考问题，提供学习策略上的指导。

在前面引导学员运用递归思维的基础上提出“猴子吃桃问题”，（有一天小猴子摘若干个桃子，它吃了一半，觉得不够，又多吃了一个。第二天，又吃了一半，吃完觉得不过瘾，又多吃了一个，以后小猴子都是吃尚存桃子一半多一个。到第10天早上小猴子再去吃桃子的时候，看到只剩下一个桃子。问小猴子第一天共摘下了多少个桃子？）教员在提出问题后，启发学员是否可以用计算思维的递归方法解决。给出表格，引导学员运用计算思维的递归方法，逆向思维，从表格的后面往前填写。

通过填写表格，学员对递归算法中递归展开和回归有了直观的认识，递归展开过程是把问题的计算规模逐步变小的过程。如第n天的桃子数可以找出规律tao（n） =（tao（n+1）+1）*2。在回归过程中，由最简单的解，逐级返回。即第10天的桃子数为1个，第9天是（1+1）*2=4个，以此类推，前一天桃子数即是后一天的桃子数加上1后的2倍。

通过这种分析，教员引导学员以递归算法的逆向思维求解问题，在分析的过程中体会递归算法。学员通过运用计算思维的方法思考，逐步掌握递归算法，当遇到类似问题时就会能够使用计算思维的方法去解决问题。

3.3 提供资源、方法，培养自主学习

第三步，教员通过网络提供学习的资源，学习资源不局限于单个问题，是对相关问题的覆盖，以达到开拓学员视野丰富知识面的目的，同时启发学员运用计算思维的方法，对知识进行归纳和提炼。

教员通过教学网络提供递归算法学习的相关知识内容，使学员对递归算法有进一步的认识，同时提出递归的方法步骤，并指导学员建立数学模型：

假设第n，（n

tao（10）=1

tao（n）=（tao（n+1）+1）*2 n

学员依据数学模型，在VB编程环境中完成对该模型的程序设计。通过这种方式的思维训练，使学员在不断的思考过程中学习，在学习的过程中又不断运用新的方法破解难题，培养学员分析问题、解决问题的能力，在巩固知识的同时拓展技能和技巧。

3.4 讨论交流，进行知识构建

第四步，教员指导学员小组讨论、交流，通过让学员进行讨论交流、内化知识，建构自己的学习体系。

教员可再设置“古典兔子问题”：假定小兔子一个月就可以长成大兔子，而大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子，问到年底时将有多少对兔子？

在这里，教员引导学员进行讨论交流，让学员提出自己的见建，并相互之间进行评判，从而拓展学员的思路，巩固其知识体系。学员经过交流讨论后，对“古典兔子问题”基本形成解题思路，达到了知识迁移的目的。

通过填写表格，很容易列出一条递推式而得到解决。假设第N个月的兔子数目是F（N），则：

f（n）=1 当n=1或2时；

f（n）=f（n-1）+f（n-2） 当n>=3时 。

通过这种交流讨论，进一步培养学员分析问题、归纳、梳理知识的能力。

3.5 总结拓展

第五步，教员进行点评、总结，并对知识进行拓展。

教员运用计算思维的方法对课程内容进行高度概括、归纳、总结，从知识的体系结构、学习的方法步骤以及学员的协作交流和计算思维训练情况等方面对学员进行综合评估，并提供知识拓展的学习资源。

学员在教员的提示下对知识点进行归纳和总结，将新知识内化，同时通过对拓展知识的学习加深对知识点的理解。通过这样的教学，学员能够主动进行思考，加强了对知识的总结和梳理，达到了培养学员自学、知识迁移和自我建构知识体系的能力的目的。

思维学习的目的是为了创造，思维发展水平是学员成才的关键，思维方式对学员的成长具有非常重要的影响。教学实践表明，基于计算思维的教学模式充分发挥了学员的主观能动性，使他们积极参与教学过程，锻炼了计算思维和创新能力，并对学习过程有一个正确的方向把握，对提高教学质量有很大的帮助，为学员提供了受益终生的学习方法。

参考文献：

[1] 斯滕伯格.思维教学.培养聪明的学习者[M]. 北京：中国轻工业出版社，2001.

[2] 周以真.计算思维[J].北京：中国计算机学会通讯，2007.

数学建模启发式算法范文第3篇

关键词：农网网架结构优化

1农网高压配电网结构特点

相对于城区电网来说，农网的拓扑结构要简单、清晰，但由于负荷对电能可靠性要求等其他原因，一般都会有小型发电厂，且通常均为小容量机组，即系统除了通过若干220kV、110kV变电所接受区域大电网电力以外，往往包括多个110kV及以下并网发电的若干电源点，从而使得电网不是单纯的放射型单方向模型，需要通过建立数学模型来确立电源点的建设和系统接线方式。

2农网网架结构优化方法的选择

2.1网架结构优化的一般方法

负荷预测是电力系统规划工作的基础，在负荷预测的基础上一般应结合区域规划进行负荷分布分析，进而确定负荷平衡结果，即确定变电所的分布和容量规划，在负荷预测和变电所布点确定的基础上进行网络优化规划。一般来说，网络规划的目标是满足系统有功负荷的最优网架设计，有静态规划和动态规划之分。静态规划考虑的是针对某一负荷水平进行网架规划，一般从基准年开始按年度进行，需考虑现有的网架，同时后一年的网架结构规划需将前一年的网架设定为已有网架，因此，每规划目标年的网架规划既要瞻前也要顾后，做到从时间序列上的前后协调相互呼应，从而节约建设投资。但规划设计方案的评价指标一般考虑整个规划期的总的性能指标最优来评价方案，而且往往加入投资分析，甚至列入资金的时间价值，因而称为动态规划。网架规划优化方法常用的有两类，即启发式方法和数学优化方法。数学最优方法是通过将电网规划问题用数学化模型进行描述，然后采用一定的算法求解，从而获得满足系统要求的最优规划方案。该类方法从理论上将可以保障方案的最优性，但一般要求得最优解需要很大的计算量。启发式方法则是通过定义方案运行性能以及投资需求等综合指标，根据一定规则对线路进行逐步迭代选择直至得到满意的最优解。该类方法难以保证方法的最优性，但计算量较数学优化方法要小，计算较为方便且便于与规划设计人员的检验相结合，因而是一种更为经济而实用的方法。

2.1.1启发式网架优化方法

根据所确定的衡量安全性指标的不同，启发式方法分为基于支路性能的启发式方法和基于系统性能指标的启发式方法。基于支路性能指标的启发式分析方法中，线路的选择是根据系统运行时线路功率传输情况来实现的，常选用的有线路是否能满足负荷要求或者线路过负荷程度等指标；而基于系统性能指标的启发式方法中，线路的选择是根据线路对系统运行时整个系统的一个特定运行性能指标的影响程度来实现的，常选用的指标有系统缺负荷大小指标等对线路的逐步选择。

基于线路指标的启发式网架规划方法分为逐步倒退法和逐步扩展法两种。逐步倒退法是根据目标年数据构成一个虚拟网络，该网络除了已有线路以外，包括所有待选的线路，这样，构成的就是一个冗余度很高但不经济的网络，然后采用潮流模型对该网络进行分析，比较各待选线路在系统中的作用和有效性，逐步去掉有效性低的线路，直到网络没有冗余线路为止。而采用逐步扩展法是根据各待选线路对过负荷线路的过负荷量的消除的有效度，选择适当的线路到现状网络上，直至网络无过负荷为止。为计算各待选线路的有效度，需要进行变结构时的潮流计算。

基于支路性能指标的启发式方法有计算简单灵活等优点，但由于通常是独立地考虑各待选线路的作用，无法直接体现系统充裕的大小等性能指标，而基于系统性能指标的启发式方法则能体现系统性能指标，从而可以从整体上识别薄弱环节并充分考虑各待选线路对系统的整体影响来选择最佳扩建线路。

2.1.2网架结构的数学优化方法

网络优化的数学化方法可以分为确定性和不确定性两种优化方法。传统上采用的常常是确定的网络优化方法，即将规划问题表达成确定性的优化问题来进行求解。但随着规划的环境以及相关要求日益复杂，且负荷、设备费用、线路路径等因素均具有不确定性，这些不确定性对电网规划有较为显著的影响，因而在规划中考虑不确定性因素是必要的。按照考虑不确定性因素特征的不同，不确定网络优化有分为随机优化法和模糊优化法。随机优化法常常用于事件是否发生以及发生的时刻存在不确定性的情形，而模糊优化法则常常用来处理有关事情表达不清晰的这种不确定性的情况。在通常情况下，在满足对保障负荷电能供应的前提下，可能有多种架线方法和导线截面的选择，要对多个方案进行比较选择，则需要选择目标函数，在电网规划设计中常用到的目标函数有网架建设总投资、电能损失、维修运行费用为目标函数。由于电能的特殊性，需要考虑各种约束条件，如电压范围、线路的长期极限传输容量限制等。因此，网架优化过程实际上是目标函数与约束条件、状态参数之间的协调处理过程。

网络规划法是针对网络的拓扑特性所提出来的一种数学规划方法，也是在线形规划中专门处理网络问题的一种特殊算法。数学上把图看作节点和弧的集合，弧是连接在两个节点之间的有向线段。在电力系统中，节点就是接受电力或者发送功率的发电厂、变电所或者负荷点，弧就是线路。这种优化网架方法在电力系统网络优化中常用的数学模型有最少费用法、最短路径法、费用最小最大流法等方法。

2.2农网网架结构优化方法的选择

结合农网高压配电网结构特点，选用支路交换法来进行这种辐射式结构的高压配电网的优化计算较为适用。采用该方法是从一个既定的辐射式电网开始，增加一条闭合联络支路后使辐射型网络变成一个闭合回路，然后将某一条支路断开，恢复网络的辐射型结构，并按照给定的目标函数对新构成的辐射型网络进行计算。重复上述计算过程，直到目标函数值最好为止，对应的网络即为所选用网络接线。采用这种方法简单实用，但只能达到局部最优解，对于农网来说，一般规划年需要新建的高压（110kV及以上）线路是局部的，因而采用支路交换法可以满足其要求。一般地对于既定的系统接线，考虑到节约投资，其改建项目的实施相对于系统网损等指标来说往往是不经济的，且由于受电压、可靠性等电网分析计算的约束性条件的影响。在工程实际中，其高压配电网往往是通过对新增支路，以及由于负荷的增长需要改建的线路的多个建设方案的比较，来确定规划年内网络结构的优化方案。在分析中，我认为需引入动态经济比较的概念，而对于网络优化设计方案来说，结合个人设计方案比较的经验来看，最适用的经济方案比较以年费用比较法较为适合。

3计算框图设计

计算步骤一：目标函数的确定。

当新建或者改建线路对支路潮流仅是局部影响时，只需对所需考察的支路进行网损最小分析。采用最小网损作为目标函数，即函数为：

计算步骤二：先计算电网的潮流分布，再找出与本次计算相关的支路，即列出目标支路集合，交换支路前辐射型网络网损计算。

计算步骤三：第一次支路交换后，重新进行潮流计算后，在潮流计算结果的基础上进行支路交换后的辐射型网络网损计算。

重复以上支路交换计算，直至得出最优结论为止。

4经济比较方法引入网架结构优化

在电力系统规划设计的实际应用中，单纯采用以上支路交换法优化网络接线是不够的，应该结合经济比较，即在对方案进行投资分析计算的基础上进行比较，从而得出经济的方案。常用的方案比较方法有最小费用法、净现值法、内部收益率法、折返年限法，每种方法又可以演化成不同的表达式。最小费用法是电力系统规划中较为普遍的方法，适用于比较效益相同或者效益基本相同，但难以具体估算的方案。最小费用法通常有以下三种不同的方案：费用现值比较法、计算期不同的现值费用比较法和年费用比较法。费用现值比较法是将各个方案基本建设期和生产运行期的全部支出费用均折算到计算期的第一年，现值低的方案是可取方案。对于不同建设期的方案则一般按照方案中计算期最短的进行计算，及计算期不同的现值费用比较法。

年费用比较法是将参加比较的诸方案计算期的全部支出折算成年费用后进行比较，费用低的方案为经济上的优越方案。其表达式为：

在比较方案部分费用相同的情况下，可以采用只考虑有差别的费用的年费用比较法，即只考虑差别部分的费用的比较，这种方法将初始投资差额以及末期残值差额折合为年费用或者年值，再综合运行维护、改造等运行年需要投入的差别费用，比较即可以得出经济最优方案。对于农网电力建设项目，笔者推荐使用这种简化了的年费用比较法。

5总结

结合农网作为辐射型受端电网的特点，用支路交换法来进行这种辐射式结构的高压配电网的优化计算，虽只能达到局部最优解。对于农网来说，一般规划年需要新建的高压线路是局部的，因而采用支路交换法可以满足其要求。在工程实际中，其高压配电网往往是通过对新增支路，以及由于负荷的增长需要改建的线路的多个建设方案的比较，来确定规划年内网络结构的优化方案。在分析中，文中引入了动态经济比较，并提出对于农网采用有差别的年费用比较法最为适用。

参考文献：

[12]张焰.陈章潮.不确定性的电网规划研究.电网技术,1999.3.

[13]李林川.夏道止等.电力系统电压和网损优化计算.电力系统及其自动化,1995.7.

[5]中电联供电分会技术管理专委会.城市配电网优化的指导意见.2003年.

数学建模启发式算法范文第4篇

[关键词] 网络环境； 计算思维； PBL； WPBL

[中图分类号] G434 [文献标志码] A

[作者简介] 张蕾（1980—），女，甘肃武威人。讲师，主要从事计算机教学及计算机网络理论研究工作。E-mail：。

一、 引 言

2006年3月，美国卡内基·梅隆大学计算机科学系主任周以真教授在美国计算机权威期刊《Communications of the ACM》杂志上给出了计算思维（Computational Thinking）的定义[1]。随即，计算思维成为国内外教育界及相关领域学者广泛关注的概念，计算思维和理论思维、实验思维一起成为推动人类文明进步和科技发展的三大支柱[2]。

因此，在教学的同时注重计算思维的培养以及基于计算思维的各种教学模式的研究成为了计算机教育者关注的焦点。2008年，美国国家计算机科学技术教学者协会（CSTA）了得到美国微软公司支持的《计算思维：一个所有课堂问题解决的工具》（Computational Thinking： A Problem Solving Tool For Every Classroom）的报告[3]。在软件工程课程中引入计算思维的关注点分离方法，并指出：作为最重要的计算思维原则之一，关注点分离是计算科学和软件工程在长期实践中确立的一项方法论原则；[4]2009年，董荣胜在《计算思维与计算机导论》一文中探讨了计算机导论课程的改革目标是以计算思维能力培养为核心[5]；王挺等结合计算思维概念分析了计算思维在编译理论和技术发展中的作用，并结合编译课程教学中的知识点，探讨了教学中如何结合具体案例培养计算思维[6]。尽管如此，计算思维在具体课程教学过程中的培养仍处于摸索阶段，还没有一套完整科学的方法体系。

近年来，随着现代信息技术的迅猛发展，在教学领域中不断涌现出各种基于网络环境的新型教学模式。其中网络环境下的问题学习（Web Problem-Based Learning简称WPBL）教学模式，强调利用网络多媒体教室、校园网、互联网、教学平台、多媒体教学软件、网络课程等网络环境及资源将学习设置到复杂的、有意义的问题情境中，通过学习者合作解决真实性问题，来掌握隐含在问题中的科学知识，并形成解决问题的技能，最终完成知识构建[7]。当前，以问题为基础开展的学习和教学活动已经成为国外教学改革浪潮中的基本思路，并迅速拓展到教育、经济、管理、数学、建筑、法律及社会工作等专业领域[8]；在国内，医学教育中已经逐步采用这种教学模式，其他教育领域也正开展相关探索研究[9]。

传统的WPBL教学模式并没有关注于计算思维能力的培养，本文对传统的WPBL教学模式进行了改进，使其更有利于计算思维能力的培养。首先对计算思维的内涵进行了概述，然后提出了面向计算思维的WPBL教学模式，并结合具体案例剖析了该教学模式的具体过程。该模式不仅对WPBL教学模式进行了进一步的研究和扩展，而且还在问题学习的过程中培养了学生使用计算思维方法分析解决问题的能力，同时，更有利于现代教育技术工作者进一步开展基于网络环境的新型教学模式的探讨和研究。

二、面向计算思维的WPBL教学模式

（一）计算思维

目前国际上广泛认同的计算思维定义来自周以真教授。他认为，计算思维是运用计算机科学的基础概念进行问题求解、系统设计，以及人类行为理解的涵盖计算机科学之广度的一系列思维活动[10]。典型的计算思维包括一系列广泛的计算机科学的思维方法：递归、抽象和分解、保护、冗余、容错、纠错和恢复，利用启发式推理来寻求解答，在不确定情况下的规划、学习和调度等。表1中对计算思维的概念进行了详细的解释：

（二）现有WPBL教学模式及存在的问题

基于李克东教授对教学模式的定义与分析[12]，结合网络环境的特点，王超杰在《WPBL教学模式的构成要素分析》一文中将WPBL教学模式定义为：在现代教育思想、教学理论与学习理论的指导下，在网络化教学环境和教学资源的支持下，以问题为中心，教与学活动中各要素之间稳定的关系和活动进程结构形式。同时，提出WPBL教学模式的构成要素为问题情境、网络环境资源、现代教与学理论、教师及学生五部分[13]。因此，针对 WPBL教学模式可以建立如下数学模型：

式（1）中，W表示WPBL教学模式；F（ ）是一个过程函数；P表示问题情境，它是WPBL教学模式的起点及核心，教师创设问题情境，由问题引导整个学习的推进；E表示网络化环境资源，包含现代教学过程中以网络和计算机技术为支撑的信息化教学环境、教学系统和教学资源，如多媒体网站、教学管理平台、多媒体网络教室、多媒体教学软件、网络资源库等；T表示现代教与学理论，包括建构主义学习理论及发现学习理论；AT表示WPBL教学模式下教师的动作集；AS表示WPBL教学模式下学生的动作集。

在WPBL教学模式下，教师设置问题情境，并对教学过程进行整体的把握和指导。学生作为主体，开展一系列围绕问题情境的活动，从而完成整个课程教学过程。然而，随着教学改革的不断深入，传统WPBL教学模式没有考虑对学生计算思维能力的培养，只是通过对问题的分析解答完成教学目标的要求。因此，如何在网络环境下开展结合计算思维培养的问题学习是当前亟需解决的问题。

（三）面向计算思维的WPBL教学模式

1. 面向计算思维的WPBL教学模式理论基础

计算思维吸取了问题解决所采用的一般数学思维方法、系统设计与评估的一般工程思维方法以及复杂性、智能、心理、人类行为的理解等一般科学思维方法，它包括关注点分离（SoC）、利用启发式推理寻求解答、递归、抽象、自动化、仿真、嵌入、约简等方法[14]。本文提出的面向计算思维的WPBL教学模式是利用多媒体网站、网络教学平台、多媒体网络教室、多媒体教学软件等网络环境资源，结合计算思维能力培养，创设问题情境，通过问题学习过程使学生达到构建知识、发现规律，并使用计算思维解决问题的教学新模式。面向计算思维的WPBL教学模式可用如下数学模型表示：

2. 面向计算思维的WPBL教学模型

面向计算思维的WPBL教学模型如图1所示，在该模型中，教学活动是围绕问题情境展开的，教师利用网络教学平台控制课堂节奏，按照教学规律适当引导，根据问题情境层层推进，使学生通过对真实问题的分析与解答，不断学习新知识、积累新经验，并将计算思维逐步渗透到自身的知识体系。

面向计算思维的WPBL教学模式下，教师不再仅仅局限于用文字来描述问题，可以使用图片、动画、视频、音频等多媒体元素设计图文并茂、贴近生活的问题情境，以激发学生的学习兴趣。因此，教学活动开始前，教师首先应在对教材、教法熟悉的基础上，利用网络环境资源，从其积累的大量教学素材中筛选、设计出既体现知识点及教学内容，又能够引起学生兴趣、利于培养计算思维的问题。其次，教师还需通过教学管理平台查询学生相关信息，对学生学习背景及个体特征进行分析，针对学生情况进行适当的异质分组，并通过网络教学平台向各个小组问题系列。

三、面向计算思维的WBPL

教学模式案例分析

“VB程序设计”课程的教学目标是培养学生程序设计能力和创新能力，其核心是针对问题找到相应的算法。在传统教学模式中，教师引导学生分析解题步骤、写出算法，并通过这一过程培养学生的编程能力。而面向计算思维的WPBL教学模式，使学生通过对结合计算思维方法设置的问题情境的求解过程，不但掌握解决实际问题的程序设计方法，同时还将计算思维相关方法内化为自身技能，从而帮助学生更好地展开学习。对此，笔者将本文提出的面向计算思维的WPBL教学模式应用到“VB程序设计”课程教学中，针对一类问题，将教学过程分解为结合计算思维创设递进式问题情境和以问题引导教学两大步骤。第一步设计了五个递进问题：提出引例、求解过程抽象、算法优化、上机并对比算法效率和巩固练习，如图2所示；第二步以每个问题引发具体的教学活动。

（一） 结合计算思维创设递进式问题情境

创设结合计算思维的问题情境是面向计算思维的WPBL教学模式的核心，本例中（如图2所示）P1’是百元买百笔问题，作为引例是整个教学过程的起点，教师通过对本问题的讲解引出具体的计算思维方法。P2’结合了构造性思维方法，使学生通过解答本题可对构造性思维有较深刻的认识。P3’是如何将前面的算法进行优化，该问题结合了启发式推理方法。P4’是对两个算法进行效率测试，通过本题学生可以深刻地认识到计算思维方法中整体与细节的重要关系。P5’是学徒问题，该问题设计的目的是利用以上学习的计算思维方法，进行本题的求解，通过巩固练习实现计算思维的内化，达到教学目标。

（二） 提出引例，教师引导学生完成解题过程

P1’（引例）：用百元买百笔。已知钢笔每支5元，圆珠笔每支3元，铅笔1元3支，用100元买100支笔，将所有可能的结果打印出来。

该过程教师起主导作用，教师动作集AT’包括：引导学生了解题目的来龙去脉，弄清哪些是已知量、需要求解什么内容，以及数据规模如何等；向学生讲授抽象、分解、模型及归化思想的定义及方法；利用网络教学平台跟踪学习者的学习活动；引导学生采用抽象和分解的方法将复杂问题简单化，要求学生利用良好的网络环境了解算法的表示方法，并通过小组协作用NS流程图表示本题的算法等。

学生动作集AS’包括：跟随教师的引导，对题目作深入细致的审题分析；多角度无遗漏地收集题目有效信息；根据教师讲授的抽象、分解、模型的定义及方法将问题进行分解简化，并抽象出已知信息和未知信息；在网络环境下查找相应的学习资料、利用BBS、Chat Room等网络交流平台开展系列讨论与交流等。

并依据问题模型M1，结合网络环境下查找的算法描述的具体方法，写出本题算法1——NS流程如图3所示。

（三） 学生抽象出程序设计求解一般过程

P2’：总结以上算法1设计过程，抽象出程序设计解决问题的一般步骤。

在解答本题的过程中，教师动作集AT’包括：引导学生了解构造性思维方法的概念及一般步骤，学生通过网络教学平台及网络资源库寻找更多构造性思维的实例以加深认识。

学生动作集AS’包括：通过网络教学平台回顾P1’解题过程；通过网络教学平台及网络资源库寻找构造性思维实例；在网络交流平台对构造性思维过程进行小组讨论，并强化模型M1的建立过程等。

通过回顾算法1的设计，学生已经对程序设计解决问题的一般步骤有了大体认识，只是没有构造性思维的概念，通过教师介绍和强化构造性思维的概念，以及在网络环境下查找相关信息及讨论交流过程，学生可确定构造性思维的四个步骤为：

1. 审题：了解题目的来龙去脉，确定输入、输出及数据规模等。

2. 建模：根据题目条件抽象出能够简洁地表达题目本质的数学模型。

3. 分析和解决模型：分析模型的正确性，如果模型正确，则设计算法解决模型。

4. 编程实现。

（四） 对算法1进行优化

P3’：算法能进一步优化吗？如果可以，如何改进算法？

在解决本问题的环节，教师动作集AT'包括：提示学生在网络环境下利用网络教学平台查询影响程序运行速度的因素；讲授计算思维中的启发式推理方法；学生通过网络教学平台查找启发式推理方法的相关内容，并提示学生利用启发式推理方法改进算法1。

学生动作集AS’包括：通过网络环境查找影响程序运行速度的相关资料；利用网络教学平台查找启发式推理的相关内容；小组成员通过BBS、Chat Room等网络交互平台进行小组系列讨论、利用启发式推理方法改进算法1等。

通过教师讲授及网络学习和讨论，学生发现利用启发式推理方法可以在搜索问题解时充分利用与问题域有关的启发式信息， 提高问题求解效率。因此，针对教师提出的问题P2’，协作小组在网络交流平台上展开讨论，使用启发式推理方法，缩小变量的取值范围。现实中要买到总共100支笔。

钢笔：1～19之间，不可能为20，否则就不能买圆珠笔和铅笔了；圆珠笔：1～32之间，不可能超过32，为32时已达到96元，还需要买钢笔和铅笔。

另外，根据在网络教学平台上查找到的影响程序运行速度的因素：循环嵌套重数、加减乘除次数、逻辑判断次数以及所选用的数据结构，考虑到算法1是三重循环，因此，可把该算法优化为一重循环，做数学上的进一步变换，基于数学模型M1的结构，修改变量的取值范围及循环条件，将公式（6）、（7）中的X看作常数，解方程组得到公式（8）、（9）如下：

由于学生已有算法1的经验，结合问题模型M2，学生可以快速地写出相对应的算法，算法2——NS流程，如图4所示。

（五）上机实验，对比算法效率

P4’：上机实验，对比两种算法的效率。

该问题仍然是围绕计算思维设计的，目的是使学生了解程序设计中常用的计算思维方法，正确认识和处理整体与细节的关系。

教师动作集AT’包括：学生小组成员互相协作，利用多媒体机房设备测试算法1及算法2的效率、督促、检查实验进度，为存在问题的学生提供帮助和指导；教师启发学生思考两个算法的区别等。

学生动作集AS’包括：小组讨论、任务划分、利用多媒体机房设备测试程序执行情况；使用网络资源库查找相关资料、分析运行结果；通过网络交互平台对实验数据展开讨论等。

经过实验，两个程序内循环执行次数及其他运算次数如表1所示。

对于同样复杂的问题，算法不同则程序运行的效率相差甚远。学生通过实验发现算法1内层循环体执行了19456次，其他运算次数均达到万次，而算法2的内循环体仅执行了4次，其他运算次数也远远少于算法1，两个算法的运行时间竟相差5000倍。因此，学生认识到，在程序设计过程中，注意变量取值范围、循环重数等细节问题，可以对程序起到“牵一发而动全身”的作用，虽然细节相对隐蔽，但如果处理不好常常会使程序运行效率有质的区别。

（六）重新提出问题，结合已掌握的计算思维方法解题

P5’：有一位学徒工资是三位数ABC元，小组内另外五位工人的工资恰好也是三位数（均高于学徒工资），分别为：ACB、BAC、BCA、CAB、CBA元，且这五位工人的工资之和等于3194元。请问该学徒工资是多少元？

面向计算思维的WPBL教学模式强调围绕问题情境完成知识的建构。通过以上问题的解决，学生已经对抽象、分解、构造性思维等程序设计过程中常用的计算思维方法有了深刻的认识。因此，要求学生使用以上计算思维方法分析、求解问题P5’，不但可以整理学生的思路，而且还可以起到巩固知识、总结反思、将计算思维内化为自身能力的作用。

通过问题P5’的练习，学生不但在网络环境下可自主运用问题情境中结合的计算思维方法解决相应的问题，同时还提高了利用网络检索、搜集、分析信息的能力，在潜移默化中实现了计算思维能力的培养。

四、教学效果分析

为了验证本文提出的基于计算思维的WPBL教学模式，特设计了如下教学实验：对一个教学班的学生随机分组为A组和B组。A组学生采用传统WPBL教学模式进行教学，B组学生采用基于计算思维的WPBL教学模式开展教学，之后采用一组相同题目对两个小组进行测试以评估其运用计算思维的解题能力， 测试结果见表2。

测试结果表明，采用面向计算思维的WPBL教学模式的分组在各个计算思维能力得分上均高于对照组。

五、总 结

本文基于现代教育技术理论与技术成果，结合“VB程序设计”案例对面向计算思维的WPBL教学模式进行了分析研究，该模式结合计算思维具体方法进行问题情境的设置，同时，围绕问题情境的一组问题展开学习过程，并在解决问题的过程中渗透计算思维的各种方法培养，最后通过教学实验，验证了该模式良好的教学效果。下一步，可以将该模式应用到更多课程的教学中，从而更好地将计算思维的培养作为学生素质教育的必要组成部分。

[参考文献]

[1] [14] putational Thinking[J].Communication of the ACM，2006，49（3）：33～35.

[2] 周以真.计算思维[J].中国计算机学会通讯，2007，（11）：26～28.

[3] putational Thinking：Aproblem-Solving Tool for Every Classroom[EB/OL]. [2013-4-6].http：///Resources/sub/Resource Files/ComputationalThinking.pdf.

[4] 何明昕.关注点分离在计算思维和软件工程中的方法论意义[J].计算机科学，2009，36（4）：60～63.

[5] 董荣胜.计算思维与计算机导论[J].计算机科学，2009，（4）：50～54.

[6] 王挺，李梦君，周会平.对编译原理课程教学中计算思维培养的探讨[J]. 计算机教育，2009，（11）：11～14.

[7] Savery，J.R. & Duffy，T. M. Problem-Based Learning：An Instructional Model and Its Constructivist Framework[J].Educational Technology，1995，（9～10）：31～38.

[8] 张建伟.基于问题式学习[J].教育研究与实验，2000，（3）：55～60.

[9] 马红亮，杨冬.网络环境下PBL的模式研究[J].现代教育技术，2002，（3）：17～21.

[10] Wing J M. Computational Thinking[J]. Communications of the ACM，2006，49（3）：22～24.

[11] Wing J M. Computational Thinking and Thinking about Computing[EB/OL].[2013-3-29].2008.http：//cs. cmu.edu/～wing/publi2 cations/Wing08a.pdf.

数学建模启发式算法范文第5篇

集装箱堆场C-M模型优化算法倒箱

1 C-M模型简介

Moshe Sniedovich和Stefan Vo？提出了一种新的用于求解动态规划的启发式算法C-M（corridor method）模型：设问题：P（X）：z*=optx∈Xf（X）

C-M框架：假设：问题P（X），方法M。条件：NM（基于M的邻域函数）、基于M的终止条件、ΠM（ΠM是X到本身的一个映射，x′=ΠM（x）是x的扰动）。开始：令j=1、选择x（1）∈X。迭代：重复以下过程直到满足基于M的终止条件。

x*=argoptMy∈N（x（j））f（y）

如果f（x*）=f（x（j）），令x（j+1）=ΠM（x（j））

否则，令x（j+1）=x*.

令j=j+1.

集装箱翻倒箱操作本质上是动态规划问题，对于这类问题可以应用现已存在的传统的启发式算法，但是由于随着问题规模的增大，利用这些方法求解该问题的计算时间以及内存占用空间都会成指数形式增加，不利于问题求解的实时要求。针对集装箱翻倒箱问题Marco Caserta， Stefan Vo？，Moshe Sniedovich通过建立翻倒集装箱的数学模型：f（s）=minx∈D（s）{1+f（T（s，x））}，k=n-1，…，1。

其中：f（n，i，Φ，C）=1，s=（k，i，t，C）：状态变量，这里为k∈{1，…，n}需要提走的集装箱，i∈{1，…，m}为当前目标箱所在的栈，t为k的上面所有集装箱的集合，即当前需要翻倒的集装箱的集合，C为栈i以外的栈的布局；D（s）：当前需翻倒的集装箱的候选栈组成的集合；s′=（k′，i′，t′，C′）：利用决策x∈D（s）所得到的新的状态变量，表示为s′=T（s，x）。

以图1为例说明上述符号：假设需提走所有的集装箱，则n=9，当前需提走的集装箱为箱1，即k=1这时i=2，t={5，4}，C={{9，8}，{3，2}{7，6}}，D（s）={1，3，4}。如果把集装箱5倒到栈1，则x=1，s′=T（s，x），s′=（1，2，{4}，{{5，9，8}，{3，2}，{76}}）。在文中，作者利用上述递归公式对翻倒箱问题进行求解，然而由于随着贝位规模的增大，计算时间不能控制在一个可接受的范围内。作者进一步利用C-M的思想，通过对当前目标箱构造 “2维”通道（two-dimensional corridor）约束：D（s，δ，λ）={x∈{1，…，m}i}|i-δ≤x≤i+δ，cx

δ为对栈个数的约束；λ为对栈层数的约束。这样从s可以产生的领域为： N（s）={s′|s′=T（s，x），x∈D（s，δ，λ）} 。

如图2，k=1， i=3，t={5，4}，C={{11，9，8}，{3，2}{7，6}{10}}，若取δ=1 λ=3则D（s，δ，λ）={2，4}。这样通过约束领域的大小。减少了算法的计算时间，实验表明该方法对翻倒箱的数量控制达到了较好的结果。

2 针对出口箱取箱操作的C-M改进模型

在参考文献中作者在利用C-M解决倒箱问题时并没有考虑堆场对出口集装箱装船时的时间波动性的特殊要求，没有考虑单次装船的时间约束。在这里基于最大程度的降低翻倒箱数，以及减小出口箱取箱时的时间波动性两方面的考虑，把上述递归模型作以下改动，

设集装箱k被取走时为提取箱k+1所必须翻倒的集装箱个数为tk+1，记T=（t1，…tn），D（T）表示对T求方差，c为一个正数。f（s）=minx∈D（s）{1+f（T（s，x））}，k=n-1，…，1 并且：D（T）≤c.

通过添加约束式D（T）≤c使得每次提箱的翻倒箱数在一定程度上趋于平均值。这样对于出口箱的提箱过程既保证了总的作业量控制在较少的水平，又控制了作业流程的顺畅性。

由于文中并没有考虑作业流程顺畅性这一条件，故利用其所给出的C-M启发式求解方法并不能较好求解上述模型。现改进C-M启发式求解方法，这里把“‘2维’通道”（“two-dimensional”corridor）约束作改动：定义J={j|j∈{1，…，m}i}，即除了当前目标箱所在栈之外的栈的集合，aj（s）表示当前状态下栈j中优先级最高的集装箱的优先级，b（aj）表示aj（s）上面集装箱的数目，B（s，g）={j∈J|（b（aj）τ）} ，g为一个正整数，τ为当前需翻倒的集装箱。

D′（s，g，λ）={x∈J|x∈B（s）∧cj

这样有：N（s）={s′：s′=T（s，x），x∈D′（s，g，λ）}。

3 实验分析

在本实验中对堆放中经常出现的4×6，4×7，5×6，5×7，6×6，6×7规模贝位分别随机产生40个例子进行实验。为了说明本文算法的优越性，把g的初值g0分别取初始值1和2，并和文献[3]中的算法优化效果上作比较，结果如表1所示。从表中可以看出对于这几种规模的贝位，本文所提出的算法对于贝位平均翻箱数的平均求解效果均优于文献中的算法C-M，并且m=1时本文算法的优化效果最好。

通过比较可知本文所提的基于改进的C-M模型的算法在平均倒箱数上较之前所提算法有较好的优化结果，在倒箱均衡性方面效果差别不大。在运算时间上看，由于本文算法利用的基本框架是搜索方法，故运算效率不及之前所提的基于启发式的算法。在表2中给出了算法当L=2时和本章所提算法g0=2时的常见贝位状态的40个实例的平均计算时间比较数据。

为了进一步分析算法在对单次提箱耗时波动性控制方面的优越性，在表3、表4中分别对4×6、5×6的50个实验作统计分析，列出了对于不同取箱代价的集装箱的百分比，并列出了不同算法的不同取箱代价的集装箱百分比的样本方差D（Y），用来度量单次提箱耗时波动性。从表中可以看出在各种规模的实验本文算法得到的效果在控制波动性方面均有一定的提高。

4 结语

本文对贝内的倒箱问题进行了进一步的研究，设计了优化搜索算法可以保证在较短的时间内得到问题的较优解。通过建立改进的C-M模型以及C-M启发式优化算法合理选取候选栈既保证了单次提箱的流畅性又较好的限制了贝位提箱总倒箱率，通过实验验证了本章所提算法的优越性，进一步为码头集装箱的智能化管理提供了坚实的理论基础。

参考文献：

[1]袁福昌.集装箱装卸搬运机械[M].武汉：港口装卸杂志社，1988.

[2]白治江，王晓峰.集装箱翻箱优化方案设计[J].水运工程，2008，（4）：57-61.

[3] XU Ya，陈秋双，LONG Lei，杨立志，LIU Li-yun.集装箱倒箱问题的启发式算法研究[J].系统仿真学报，2008， 20（14）： 3666-3674.