运筹学在数学建模中的应用

运筹学在数学建模中的应用一、运筹学概况二、线性规划三、整数规划与多目标规划四、图论与网络优化五、动态规划六、赛题选讲运筹学概况运筹学的定义运筹学简史运筹学的主要内容及应用重点运筹学应用步骤运筹学在数学建模竞赛中的地位运筹学是一种给出问题不坏的答案的艺术，否则的话问题的结果会更坏。一、运筹学的定义☆

运筹学(《辞海》)：20世纪40年代开始形成的一门学科，主要研究经济活动与军事活动中能用数量来表达的有关运用、筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，做出综合性合理安排，以达到较经济有效地使用人力物力.☆作为一门定量优化决策科学，起源于第二次世界战，英文原意OperationResearch；二、运筹学简史深水炸弹的释放问题防空系统的预警问题运筹学的一些分支英美海空军作战参谋部组成了运筹学研究小组二战中二战后军事工、商业领域存储论、决策科学、预测科学等分支☆

20世纪50年代中期钱学森和许国志教授引入“运用学”＊

1957年取“运筹”二字，将OR正式命名为“运筹学”开始应用于建筑业和纺织业《史记》中“夫运筹帷幄之中，决胜千里之外”线性规划数学规划非线性规划整数规划动态规划多目标规划组合优化最优计数问题网络优化排序问题统筹图随机优化对策论排队论库存论决策分析可靠性分析三、运筹学主要内容数学规划模型的数学描述下的最大值或最小值。将一个优化问题用数学式子来描述，即求函数在约束条件和数学规划问题的一般形式约束条件决策变量目标函数“受约束于”之意网络优化研究解决生产组织、计划管理中诸如最短路径问题、最小连接问题、最小费用流问题、最优分派问题及关键线路图等。特别在计划和安排大型复杂工程时，网络技术是重要的工具。排队论是20世纪初由丹麦数学家Erlang应用数学方法在研究电话话务理论过程中而发展起来的一门学科，排队论也称随机服务系统理论，排队论是定量的研究排队问题，寻找系统内在规律，寻找供求关系平衡的最优方案。如机器等待修理、船舶等待装卸、顾客等待服务等。对策论研究具有利害冲突的各方，如何制定对自己有利从而战胜对手的斗争策略田忌赛马运筹学的应用重点1.市场销售在广告预算和媒体的选择、竞争性定价、新产品开发、销售计划的制定等方面。如美国杜邦公司在五十年代起就非常重视将作业研究用于研究如合做好广告工作、产品定价和新产品的引入。2.生产计划在总体计划方面主要是从总体确定生产、储存和劳动力的配合等计划以适应变动的需求计划，主要用线性规划和仿真方法等。此外，还可用于生产作业计划、日程表的编排等。还有在合理下料、配料问题、物料管理等方面的应用。3.库存管理存货模型将库存理论与计算器的物料管理信息系统相结合，主要应用于多种物料库存量的管理，确定某些设备的能力或容量，如工厂的库存、停车厂的大小、新增发电设备容量大小、计算机的主存储器容量、合理的水库容量等。4.运输问题这里涉及空运、水运、公路运输、铁路运输、捷运、管道运输和厂内运输等。包括班次调度计划及人员服务时间安排等问题。5.财政和会计这里涉及预算、贷款、成本分析、定价、投资、证券管理、现金管理等。用得较多的方法是：统计分析、数学规划、决策分析。此外，还有盈亏点分析法、价值分析法等。6.人事管理这里涉及六方面。(1)人员的获得和需求估计；(2)人才的开发，即进行教育和训练；(3)人员的分配，主要是各种指派问题；(4)各类人员的合理利用问题；(5)人才的评价，其中有如何测定一个人对组织、社会的贡献；(6)薪资和津贴的确定等。7.设备维修、更新和可靠度、项目选择和评价如电力系统的可靠度分析、核能电厂的可靠度以及风险评估等。8.工程的最佳化设计在土木、建筑、水利、信息、电子、电机、光学、机械、环境和化工等领域皆有作业研究的应用。9.城市管理包括各种紧急服务救难系统的设计和运用。如消防队救火站、救护车、警车等分布点的设立。美国曾用等候理论方法来确定纽约市紧急电话站的值班人数。加拿大亦曾研究一城市警车的配置和负则范围，事故发生后警车应走的路线等。分析与表述问题建立模型

对模型和由模型导出的解进行检验建立起对解的有效控制对问题求解

方案实施不满意满意运筹学应用步骤五、运筹学在数学建模竞赛中的地位有人统计：在全国大学生数学建模竞赛题中有40%可以用运筹学中的优化方法解决1.CUMCM-1995A:一个飞行管理问题2.CUMCM-2000B:钢管订购与运输3.CUMCM-2003B：露天矿生产的车辆安排4.CUMCM-2000D:空洞探测5.CUMCM-2006B:艾滋病疗法的评价及疗效的预测6.CUMCM-2006C:易拉罐形状和尺寸的最优设计7.CUMCM-2009B：眼科病床的合理安排线性规划线性规划实例★在各类经济活动中，经常遇到这样的问题：在生产条件不变的情况下，如何通过统筹安排，改进生产组织或计划，合理安排人力、物力资源，组织生产过程，使总的经济效益最好。可以化成或近似地化成“线性规划”（LinearProgramming，简记为LP）问题线性规划研究的实际问题：生产计划问题、物资运输问题、合理下料问题、库存问题、劳动力问题、最优设计问题等1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1

制订生产计划，使每天获利最大

35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?

A1的获利增加到30元/公斤，应否改变生产计划？每天例:奶制品生产计划

1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

每天获利约束条件非负约束

线性规划模型(LP)时间480小时至多加工100公斤A1

50桶牛奶每天⑴．一般形式目标函数价值向量价值系数决策变量右端向量系数矩阵非负约束自由变量⑵．规范形式⑶．标准形式三种形式的LP问题全都是等价的，即一种形式的LP可以简单的变换为另一种形式的LP，且它们有相同的解.对于非标准形式的线性规划，可通过下列办法化成标准形式①若求,可化为求②若约束条件中含有不等式或则可引进新变量（称为松弛变量），化为等式约束：或③总假定，否则在等式两边乘以-1即可④若变量无非负限制，则引入两个非负变量与令，便可化为标准形式满足所有约束条件的向量x称为可行解或者可行点三者皆满足的向量x是最优解最优值：最优解的目标函数值可行区域：所有的可行点组成的集合称为(LP)问题的可行区域.记为D线性规划模型的解的几种情况线性规划问题有可行解(Feasible)无可行解（Infeasible）有最优解（Optimal）无最优解(Unbounded)图解法

x1x20ABCDl1l2l3l4l5约束条件目标函数

Z=0Z=2400Z=3600c在B(20,30)点得到最优解模型求解

软件实现

LINDO6.1max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100endOBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产A1,30桶生产A2，利润3360元。结果解释

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料无剩余时间无剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三种资源“资源”剩余为零的约束为紧约束（有效约束）结果解释

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2最优解下“资源”增加1单位时“效益”的增量原料增加1单位,利润增长48时间增加1单位,利润增长2加工能力增长不影响利润影子价格

35元可买到1桶牛奶，要买吗？35<48,应该买！聘用临时工人付出的工资最多每小时几元？2元！RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标函数系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?

Yesx1系数范围(64,96)

x2系数范围(48,72)

A1获利增加到30元/公斤，应否改变生产计划x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)结果解释

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加53

35元可买到1桶牛奶，每天最多买多少？最多买10桶!(目标函数不变)运输问题分析：决策变量

设表示从仓库运往零售点的物资数量目标函数目标：运费最省约束条件从仓库运出总量不超过可用总量，运入零售点的数量不低于需求量。由于总供给量等于总需求量，所以都是等号。即蕴含约束：数量非负模型：收发平衡型的运输问题从m个发点Ai,i=1,2,…,m,调运物资到n个收点Bj,j=1,2,…,n；发点Ai有物资ai，收点Bj的需求量是bj，从Ai运到Bj的运价为cij，且收发平衡，如何运输使总运费最省

运输问题的求解过程为了便于讨论，以一个运输问题实例的求解过程来介绍如何用LINDO或LINGO软件求解运输问题模型.

例设m=3,n=4即为有3个产地和4个销地的运输问题，其产量、销量及单位运费如表7-1所示.试求总运费最少的运输方案，以及总运费.

解：从前面的分析来看，运输问题属于线性规划问题，因此，不论是LINDO软件或LINGO软件都可以对该问题求解.写出LINDO软件的模型（程序），程序名：transportation.ltx

!3Warehouse,4CustomerTransportationProblem!Theobjectivemin6x11+2x12+6x13+7x14+4x21+9x22+5x23+3x24+8x31+8x32+x33+5x34subjectto!Thesupplyconstraints2)x11+x12+x13+x14<=303)x21+x22+x23+x24<=254)x31+x32+x33+x34<=21!Thedemandconstraints5)x11+x21+x31=156)x12+x22+x32=177)x13+x23+x33=228)x14+x24+x34=12endLINDO软件的计算结果如下：LPOPTIMUMFOUNDATSTEP6OBJECTIVEFUNCTIONVALUE1)161.0000VARIABLEVALUEREDUCEDCOSTX112.0000000.000000X1217.0000000.000000X131.0000000.000000X140.0000002.000000X2113.0000000.000000X220.0000009.000000X230.0000001.000000X2412.0000000.000000X310.0000007.000000X320.00000011.000000X3321.0000000.000000X340.0000005.000000ROWSLACKORSURPLUSDUALPRICES2)10.0000000.0000003)0.0000002.0000004)0.0000005.0000005)0.000000-6.0000006)0.000000-2.0000007)0.000000-6.0000008)0.000000-5.000000NO.ITERATIONS=6事实上，我们关心更多的是那些非零变量，因此,可选择LINDO中的命令只列出非零变量.

OBJECTIVEFUNCTIONVALUE1)161.0000VARIABLEVALUEREDUCEDCOSTX112.0000000.000000X1217.0000000.000000

X131.0000000.000000X2113.0000000.000000X2412.0000000.000000X3321.0000000.000000ROWSLACKORSURPLUSDUALPRICES3)0.0000002.0000004)0.0000005.0000005)0.000000-6.0000006)0.000000-2.0000007)0.000000-6.0000008)0.000000-5.000000NO.ITERATIONS=6参考文献[1]谢金星，薛毅.优化建模与LINDO/LINGO软件[M].北京：清华大学出版社.2005,7.[2]姜启源，谢金星，叶俊.数学模型（第三版）[M].北京：高等教育出版社.2005,12.[3]刁在筠，刘桂真等.运筹学[M].北京：高等教育出版社.2009,12.[4]牛映武，运筹学[M].西安：西安交通大学出版社.2006.5[5]胡运权，运筹学教程[M].北京：清华大学出版社.2007.4整数规划要求变量取整数值的线性规划问题称为整数线性规划要求变量取0或1的线性规划问题称为0-1规划只要求部分变量取整数值的线性规划称为混合整数线性规划例投资决策问题

解投资决策变量

设获得的总利润为z，则上述问题的数学模型为

变量限制为整数本质上是一个非线性约束，它不可能用线性约束来代替它.☆1954年G.G.DantzigD.R.FulkersonandS.M.Johnson研究推销商问题（货郎担问题）,首先提出破子圈方法和将问题分解为几个子问题之和的思想，这是割平面方法和分枝定界法的萌芽☆1958年R.E.Gomory创立割平面算法☆1960年A.H.LandandA.G.Doig对推销商问题提出分解算法，紧接着，E.Balas等人将其发展成一般的分枝定界法，从而形成独立的整数规划分支☆1993年W.J.Cook平行计算研究10907064个城市的货郎担问题整数规划简史例旅行售货员问题（货郎担问题）(TSP问题）解首先，每个城市恰好进入一次，即其次，每个城市恰好离开一次，即第三，不能出现多于一个互不连通的旅行路线圈，且不排除任何可能的旅行路线

常用算法：割平面算法、分枝定界法、解0-1规划的隐枚举法、分解算法、群论方法、动态规划方法一般只能用来解决中小型的ILP问题近似算法1993年7月W.J.Cook并行计算10907064个城市货郎担问题计算机模拟法如Monte-Carlo方法丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?例混合泳接力队的选拔

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”45名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种。目标函数若选择队员i参加泳姿j的比赛，记xij=1,否则记xij=0

0-1规划模型

cij(秒)~队员i第j种泳姿的百米成绩约束条件每人最多入选泳姿之一

ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每种泳姿有且只有1人模型求解

最优解：x14=x21=x32=x43=1,其它变量为0;成绩为253.2(秒)=4’13”2MIN66.8x11+75.6x12+87x13+58.6x14+……+67.4x51+71x52+83.8x53+62.4x54SUBJECTTOx11+x12+x13+x14<=1

……x51+x52+x53+x54<=1x11+x21+x31+x41+x51=1

……x14+x24+x34+x44+x54=1END输入LINDO求解

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”4甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.丁蛙泳c43

=69.675.2，戊自由泳c54=62.4

57.5,方案是否调整？敏感性分析？乙~蝶泳、丙~仰泳、丁~蛙泳、戊~自由泳IP规划一般没有与LP规划相类似的理论，LINDO输出的敏感性分析结果通常是没有意义的。最优解：x21=x32=x43=x51=1,成绩为4’17”7c43,c54的新数据重新输入模型，用LINDO求解指派(Assignment)问题：每项任务有且只有一人承担，每人只能承担一项，效益不同，怎样分派使总效益最大.讨论甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.原方案为了选修课程门数最少，应学习哪些课程？

例选课策略要求至少选两门数学课、三门运筹学课和两门计算机课课号课名学分所属类别先修课要求1微积分5数学

2线性代数4数学

3最优化方法4数学；运筹学微积分；线性代数4数据结构3数学；计算机计算机编程5应用统计4数学；运筹学微积分；线性代数6计算机模拟3计算机；运筹学计算机编程7计算机编程2计算机

8预测理论2运筹学应用统计9数学实验3运筹学；计算机微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程？

0-1规划模型

决策变量

目标函数

xi=1~选修课号i的课程（xi=0~不选）

选修课程总数最少约束条件最少2门数学课，3门运筹学课，2门计算机课。

课号课名所属类别1微积分数学2线性代数数学3最优化方法数学；运筹学4数据结构数学；计算机5应用统计数学；运筹学6计算机模拟计算机；运筹学7计算机编程计算机8预测理论运筹学9数学实验运筹学；计算机先修课程要求最优解：

x1=x2=x3=x6=x7=x9=1,其它为0；6门课程，总学分210-1规划模型

约束条件x3=1必有x1=x2=1模型求解（LINDO）课号课名先修课要求1微积分

2线性代数

3最优化方法微积分；线性代数4数据结构计算机编程5应用统计微积分；线性代数6计算机模拟计算机编程7计算机编程

8预测理论应用统计9数学实验微积分；线性代数学分最多多目标优化的处理方法：化成单目标优化。两目标(多目标)规划

讨论：选修课程最少，学分尽量多，应学习哪些课程？课程最少以学分最多为目标，不管课程多少。以课程最少为目标，不管学分多少。最优解如上，6门课程，总学分21。最优解显然是选修所有9门课程。多目标规划

在课程最少的前提下以学分最多为目标。最优解：

x1=x2=x3=x5=x7=x9=1,其它为0；总学分由21增至22。注意：最优解不唯一！课号课名学分1微积分52线性代数43最优化方法44数据结构35应用统计46计算机模拟37计算机编程28预测理论29数学实验3LINDO无法告诉优化问题的解是否唯一。可将x9=1易为x6=1增加约束，以学分最多为目标求解。多目标规划

对学分数和课程数加权形成一个目标，如三七开。=-0.8x1-0.5x2-0.5x3-0.2x4-0.5x5-0.2x6+0.1x7+0.1x8-0.2x9多目标规划

对学分数和课程数加权形成一个目标，如三七开。最优解：

x1=x2=x3=x4=x5=x6=x7=x9=1，其它为0；总学分28。课号课名学分1微积分52线性代数43最优化方法44数据结构35应用统计46计算机模拟37计算机编程28预测理论29数学实验3多目标规划的求解方法1、化多为少的方法：把多目标规划问题归为单目标的数学规划(线性规划或非线性规划)问题进行求解①线性加权和法②理想点法2、分层求解法假若目标函数多目标规划的各个分目标可以按其在问题中的重要程度排出先后次序，先对第一个目标进行极小化，设得到的最优解x,然后按固定格式依次分层对各目标进行极小化3、层次分析法(AnalyticHierarchyProcess,AHP)图论与网络优化图论的研究最早可追溯到著名的七桥问题.18世纪欧洲的哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有七座桥，如图所示.当时那里的人们就考虑：能否从A、B、C、D中任一地方出发，走每座桥一次而且只走一次，最后刚好回到出发点.例公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市.假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？

例最短路问题（SPP-ShortestPathProblem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地.从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路.例

运输问题(TransportationProblem)某种原材料有M个产地，现在需要将原材料从产地运往N个使用这些原材料的工厂.假定M个产地的产量和N家工厂的需要量已知，单位产品从任一产地到任一工厂的的运费已知，那么如何安排运输方案可以使总运输成本最低？

例

指派问题(AssignmentProblem)一家公司经理准备安排N名员工去完成N项任务，每人一项.由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的.如何分配工作方案可以使总回

报最大？

例中国邮递员问题(CPP-ChinesePostmanProblem)一名邮递员负责投递某个街区的邮件.如何为他(她)设计一条最短的投递路线(从邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题.例旅行商问题/货郎（担）问题(TSP-TravelingSalesmanProblem)一名推销员准备前往若干城市推销产品.如何为他(她)设计一条最短的旅行路线(从驻地出发，经过每个城市恰好一次，最后返回驻地)？这一问题的研究历史十分悠久，通常称之为旅行商问题.动态规划运筹学的一个分支，解决多阶段决策过程最优化的一种数学方法★多阶段决策过程—指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策.这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态.每个阶段的决策确定以后，就得到一个决策序列，称为策略.求解目的就是求一个策略，使各阶段的效益的总和达到最优，这种把一个问题可看作是一个前后关联具有链状结构的多阶段过程称为多阶段决策过程，这种问题称为多阶段决策问题12n状态决策状态决策状态状态决策例最短路线问题如图所示,设某厂A要把一批货物运到E城出售,中间可经过1~8城市,各城市间的交通线及距离如图所示,问应选择什么路线,可使总距离最短?AE873165428956458767893562343为了求出最短路线，一种简单的方法，可以求出所有从A至E的路长并加以比较.从A至E共有18条不同路径，要求出最短路线只需分别求出这18条路径的长度，再进行比较即可，这种方法称穷举法.可以看出，当问题的段数很多、各段的状态也很多时,穷举法的计算量会大大增加,甚至使得求优成为不可能下面介绍动态规划方法注意本方法是从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点E的最短路线，最后求得A点到E点的最短路线.★最短路的重要性质：A到C的最短路B到C的最短路ACBIIIII’I’反证：如果II不是从B到C的最优路线，II’是比II好的从B到C的路线，那么I-II’就是比I-II更好的从A到C的路线，与I-II是最优路线矛盾用d(sk,xk)表示由状态sk点出发，采用决策xk到达下一阶段sk+1点时的两点距离.第一步：从k=4开始，状态变量s4可取两种状态⑦,⑧，它们到E点的路长分别为4,3,即f4(7)=4，f4(8)=3第二步：k＝3，状态变量s3可取三个值④,⑤,⑥，这是经过一个中途点到达终点的两级决策问题，从④到E有两条路线，需加以比较、取其中最短的，即：=min=7这说明由④到终点的最短距离为7，其路径为④→⑦→E.相应决策为.⑤到终点的最短距离为5，其路径为⑤→⑧→E.相应决策为.=min=5=min=5⑥到终点的最短距离为5，其路径为⑥→⑦→E.相应决策为.第三步：k＝2，状态变量s2可取三个值①,②,③，这是经过两个中途点到达终点的三级决策问题.因为第三段各点④,⑤,⑥到E的最短距离f3(4),f3(5),f3(6)已知,所以若求①到E的最短距离，只需以它们为基础，分别加上①与④,⑤,⑥的一段距离，取其中最短者即可=min=9①到终点的最短距离为9，其路径为①→⑤→⑧→E。相应决策为。=min=11=min=13同理有：第四步：k＝1，只有一个状态点A，=min=17即从A到E的最短距离为17，第一阶段决策为再按计算顺序反推可得最优决策序列{xk}，即有最优路线为：A→①→⑤→⑧→E从上述计算过程可看出，在求解的各阶段，都利用了第k段和第k十1段的如下关系：这种递推关系称为动态规划的基本方程，f5(s5)=0称为边界条件退出前一页后一页[4][3][7][5][5][9][11][13][17]上述最短路线的计算过程也可用图直观表示出来，每个结点上方的括号内的数，表示该点到终点E的最短距离.连结各点到E点的粗线表示最短路径.这种在图上直接计算的方法叫标号法.逆序法顺序法2003B露天矿生产的车辆安排钢铁工业是国家工业的基础之一，铁矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务。

露天矿里有若干个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说，平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间5分钟。卸货地点（以下简称卸点）有卸矿石的矿石漏、2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场等，每个卸点都有各自的产量要求。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为29.5%1%,称为品位限制)搭配起来送到卸点，搭配的量在一个班次（8小时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为3分钟。所用卡车载重量为154吨，平均时速28。卡车的耗油量很大，每个班次每台车消耗近1吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运输。每个铲位到每个卸点的道路都是专用的宽60的双向车道，不会出现堵车现象，每段道路的里程都是已知的。一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次（因为随机因素影响，装卸时间与运输时间都不精确，所以排时计划无效，只求出各条路线上的卡车数及安排即可）。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考虑下面两条原则之一：1.总运量（吨公里）最小，同时出动最少的卡车，从而运输成本最小；2.利用现有车辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。请你就两条原则分别建立数学模型，并给出一个班次生产计划的快速算法。针对下面的实例，给出具体的生产计划、相应的总运量及岩石和矿石产量。某露天矿有铲位10个，卸点5个，现有铲车7台，卡车20辆。各卸点一个班次的产量要求：矿石漏1.2万吨、倒装场Ⅰ1.3万吨、倒装场Ⅱ1.3万吨、岩石漏1.9万吨、岩场1.3万吨。平面示意图各铲位和各卸点之间的距离（公里）距离铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏5.265.194.214.002.952.742.461.900.641.27倒装Ⅰ1.900.991.901.131.272.251.482.043.093.51岩场5.895.615.614.563.513.652.462.461.060.57岩石漏0.641.761.271.832.742.604.213.725.056.10倒装Ⅱ4.423.863.723.162.252.810.781.621.270.50铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石量0．951．051．001．051．101．251．051．301．351．25岩石量1．251．101．351．051．151．351．051．151．351．25铁含量30%28%29%32%31%33%32%31%33%31%各铲位矿石、岩石数量（万吨）和矿石平均含铁量一问题剖析露天矿生产主要是运石料，这是一个运输问题,与典型的运输问题比较有以下特点：这是运输矿石与岩石两种物资的问题；属于产量大于销量的不平衡运输问题；为了完成品位约束，矿石要搭配运输；变量设计解决约束条件设计解决约束条件设计解决产地、销地均有单位时间的流量限制；约束条件设计解决运输车辆只有一种，每次满载运输，154吨/车次；铲位数多于铲车数意味着要最优的选择不多于7个产地作为最后结果中的产地；整数要求→整数规划从C107=120个整数规划中取最优的即得到最佳物流最后求出各条路线上的派出车辆数及安排。由最佳物流算出各条路线上的最少派出车辆数再给出具体安排即完成全部计算目的：求出各条路线上的卡车数及安排两个阶段的规划问题第一个阶段：确定各条路线上运输石料的数量(车次)，可以用整数规划建模第二阶段：规划各条线路上的派车方案，是一个组合优化问题二模型假设卡车在一个班次中不应发生等待或熄火后再启动的情况；在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；空载与重载的速度都是28km/h，耗油相差很大；卡车可提前退出系统；卡车加油、司机吃饭与上厕所等休息时间忽略不计；对所有卡车来说，一个班次的8小时是同一时刻开始的原则之一总运量(吨公里)最小，同时出动最少的卡车，从而运输成本最小；三模型建立多目标决策问题（一）分阶段考虑，先考虑总运量最小目标：总运量(吨公里)最小xij：从i铲位到j号卸点的石料运量车●次；cij：从i号铲位到j号卸点的距离公里；目标函数：xij为整数约束(1)道路能力约束：一个电铲(卸点)不能同时为两辆卡车服务，所以一条路线上最多能同时运行的卡车数是有限制的在i号铲位到j号卸点路线上运行一个周期平均所需时间从i号铲位到j号卸点最多能同时运行的卡车数(辆)每辆卡车一个班次中在这条路线上最多可以运行的次数(Aij-1)×5是开始装车至最后一辆车的延时时间则一个班次中这条固定路线上最多可能运行的总车·次大约为：Lij=Aij×Bij；总吨数大约为154×Lij(2)电铲能力约束：还是因为1台电铲不能同时为两辆卡车服务，所以一台电铲在一个班次中的最大可能产量为：8×60／5=96(车·次)。fi:描述第i号铲位是否使用的0-1变量，取1为使用；0为关闭。(3)卸点能力约束：卸点的最大吞吐量为每小时60／3=20(车·次)，于是一个卸点在一个班次中的最大可能产量为：8×20=160(车·次)。(4)铲位储量约束：各铲位的矿石和岩石产量都不能超过相应的储藏量cki：i号铲位的铁矿石储量万吨cyi：i号铲位的岩石储量万吨(5)产量任务约束：各卸点的产量大于等于该卸点的任务要求qj:j号卸点任务需求，q=(1.2,1.3,1.3,1.9,1.3)*10000吨(6)铁含量约束：各矿石卸点的平均品位要求都在指定的范围内pi：i号铲位的矿石铁含量百分比p=(30,28,29,32,31,33,32,31,33,31)(7)车辆数量约束为各路线上运输量所需的实数卡车数学模型为计算结果（LINGO软件）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿漏135411倒Ⅰ4243岩场7015岩漏8143倒Ⅱ13270（二）对最佳物流进行派车——第二阶段规划这是一个组合优化中的一维装箱模型装箱问题

装箱问题（BinPacking）是一个经典的组合优化问题，有着广泛的应用，在日常生活中也屡见不鲜.装箱问题的描述

设有许多具有同样结构和负荷的箱子B1，B2，…其数量足够供所达到目的之用.每个箱子的负荷（可为长度、重量etc.）为

C,今有

n

个负荷为wj(0<wj<C,j=1，2，…，n)的物品

J1，J2，…，Jn

需要装入箱内.装箱问题：是指寻找一种方法，使得能以最小数量的箱子数将J1，J2，…，Jn全部装入箱内.

由于wj<C，所以BP的最优解的箱子数不超过n.设箱子Bi被使用否则物品Jj放入箱子Bi

中否则则装箱问题的整数线性规划模型为：约束条件（1）表示：一旦箱子Bi被使用，放入Bi的物品总负荷不超过C；约束条件（2）表示：每个物品恰好放入一个箱子中.上述装箱问题是这类问题最早被研究的，也是提法上最简单的问题，称为一维装箱问题.但装箱问题的其他一些提法：1、在装箱时，不仅考虑长度，同时考虑重量或面积、体积

etc.即二维、三维、…装箱问题；2、对每个箱子的负荷限制不是常数C;而是最优目标可如何提？3、物品J1，J2，…，Jn的负荷事先并不知道，来货是随到随装；即在线（On-Line）装箱问题；4、由于场地的限制，在同一时间只能允许一定数量的箱子停留现场可供使用,etc.

BP

的应用举例：1、下料问题轧钢厂生产的线材一般为同一长度,而用户所需的线材则可能具有各种不同的尺寸,如何根据用户提出的要求，用最少的线材截出所需的定货；2、二维BP

玻璃厂生产出长宽一定的大的平板玻璃,但用户所需玻璃的长宽可能有许多差异，如何根据用户提出的要求，用最少的平板玻璃截出所需的定货;3、计算机的存贮问题如要把大小不同的共10MB的文件拷贝到磁盘中去，而每张磁盘的容量为1.44MB,已知每个文件的字节数不超过1.44MB,而且一个文件不能分成几部分存贮，如何用最少的磁盘张数完成.装箱问题的近似算法一、NF(NextFit)算法设物品J1，J2,…，Jn的长度分别为w1，w2,…，wn箱子B1，B2，…的长均为C，按物品给定的顺序装箱.先将J1放入B1,如果则将J2放入B1…如果而则B1已放入J1，J2,…，Jj，将其关闭，将Jj+1放入B2.同法进行，直到所有物品装完为止.特点：1、按物品给定的顺序装箱；2、关闭原则.对当前要装的物品Ji

只关心具有最大下标的已使用过的箱子Bj

能否装得下？能.则Ji

放入Bj

；否.关闭Bj，Ji

放入新箱子Bj+1.计算复杂性为

O(n).Example1物品J1J2J3J4J5J6wj674283I:C=10J1J5J6J4J3J2B1B2B3B4B5J1J2J3J4J5J6Solution:首先，将J1放入B1;由于J2在B1中放不下,所以关闭B1,将J2放入B2,J3在B2中放不下(不考虑B1是否能装),所以关闭B2将J3放入B3，…解为:其余为零二、FF(FirstFit)算法设物品J1，J2,…，Jn的长度分别为w1，w2,…，wn箱子B1，B2，…的长均为C，按物品给定的顺序装箱.物品J1J2J3J4J5J6wj674283I:C=10用NF算法装箱,当放入J3时,仅看B2是否能放入，因B1已关闭,参见EX.1但事实上，B1此时是能放得下J3的.如何修正NF算法先将J1放入B1，若,

则J2放入B1,否则，J2放入B2;若J2已放入B2，对于J3则依次检查

B1、B2,若B1能放得下,则J3放入B1,否则查看B2,若B2能放得下，则J3放入B2,否则启用B3,J3放入B3.一般地，J1,…，Jj已放入B1,…，Bi