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

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

2、要研究门学科，主要研究经济活动与军事活动中能用数量经济活动与军事活动中能用数量来表达的有关运用、筹划与管理方面的问题来表达的有关运用、筹划与管理方面的问题，它根，它根据问题的要求，通过数学的分析与运算，做出综合据问题的要求，通过数学的分析与运算，做出综合性合理安排，以达到较经济有效地使用人力物力性合理安排，以达到较经济有效地使用人力物力. . 作为一门定量优化决策科学，起源于第二次世界作为一门定量优化决策科学，起源于第二次世界战战，英文原意英文原意OperationOperationResearchResearch；二、运筹学简史二、运筹学简史深水炸弹的释放问题防空系统的预警问题运筹学的一些分

3、支英美海空军作战参谋部组成了运筹学研究小组二战中二战后军事工、商业领域存储论、决策科学、预测科学等分支 20世纪世纪50年代中期钱学森和许国志教授引入年代中期钱学森和许国志教授引入 “运用学运用学” 1957年年 取取 “运筹运筹”二字，将二字，将OR正式命名为正式命名为“运运筹学筹学” 开始应用于建筑业和纺织业开始应用于建筑业和纺织业史记史记中中“夫运筹帷幄之中，决胜千里之外夫运筹帷幄之中，决胜千里之外”线性规划线性规划数数学学规规划划非线性规划非线性规划整数规划整数规划动态规划动态规划多目标规划多目标规划组组合合优优化化最优计数问题最优计数问题网络优化网络优化排序问题排序问题统筹图统筹图随

4、随机机优优化化对策论对策论排队论排队论库存论库存论决策分析决策分析可靠性分析可靠性分析三、运三、运 筹筹 学学 主主 要要 内内 容容数学规划模型的数学描述数学规划模型的数学描述下的最大值或最小值。下的最大值或最小值。.,.,)(mihi210 x.,.,),)()(piggii2100 xx),.,(nxxxx321x将一个优化问题用数学式子来描述，即求函数将一个优化问题用数学式子来描述，即求函数)(xfu 在约束条件在约束条件和和数学规划问题的一般形式数学规划问题的一般形式约约束束条条件件决策变量决策变量njiDxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(min

5、njiDxljxgmixhtsxf,.,1, 0)(,.,1, 0)(. .)(min目标函数目标函数tosubjectts .“受约束于”之意网络优化网络优化研究解决生产组织、计划管理中诸如最短路径问研究解决生产组织、计划管理中诸如最短路径问题、最小连接问题、最小费用流问题、最优分派题、最小连接问题、最小费用流问题、最优分派问题及关键线路图等。特别在计划和安排大型复问题及关键线路图等。特别在计划和安排大型复杂工程时，网络技术是重要的工具。杂工程时，网络技术是重要的工具。排队论排队论是是20世纪初由丹麦数学家世纪初由丹麦数学家Erlang应用数学方法在研应用数学方法在研究电话话务理论过程中而发

6、展起来的一门学科，排究电话话务理论过程中而发展起来的一门学科，排队论也称随机服务系统理论，排队论是定量的研究队论也称随机服务系统理论，排队论是定量的研究排队问题，寻找系统内在规律，寻找供求关系平衡排队问题，寻找系统内在规律，寻找供求关系平衡的最优方案。的最优方案。如机器等待修理、船舶等待装卸、顾客等待服务等。如机器等待修理、船舶等待装卸、顾客等待服务等。对策论对策论研究具有利害冲突的各方，如何制定对自己有利研究具有利害冲突的各方，如何制定对自己有利从而战胜对手的斗争策略从而战胜对手的斗争策略田忌赛马田忌赛马运筹学的应用重点运筹学的应用重点1.市场销售市场销售在广告预算和媒体的选择、竞争性定价、

7、新产品开发、在广告预算和媒体的选择、竞争性定价、新产品开发、销售计划的制定等方面。如美国杜邦公司在五十年代起销售计划的制定等方面。如美国杜邦公司在五十年代起就非常重视将作业研究用于研究如合做好广告工作、产就非常重视将作业研究用于研究如合做好广告工作、产品定价和新产品的引入。品定价和新产品的引入。2. 生产计划生产计划在总体计划方面主要是从总体确定生产、储存和劳动力在总体计划方面主要是从总体确定生产、储存和劳动力的配合等计划以适应变动的需求计划，主要用线性规划的配合等计划以适应变动的需求计划，主要用线性规划和仿真方法等。此外，还可用于生产作业计划、日程表和仿真方法等。此外，还可用于生产作业计划、

8、日程表的编排等。还有在合理下料、配料问题、物料管理等方的编排等。还有在合理下料、配料问题、物料管理等方面的应用。面的应用。 3. 库存管理库存管理存货模型将库存理论与计算器的物料管理信息系统相结存货模型将库存理论与计算器的物料管理信息系统相结合，主要应用于多种物料库存量的管理，确定某些设备合，主要应用于多种物料库存量的管理，确定某些设备的能力或容量，如工厂的库存、停车厂的大小、新增发的能力或容量，如工厂的库存、停车厂的大小、新增发电设备容量大小、计算机的主存储器容量、合理的水库电设备容量大小、计算机的主存储器容量、合理的水库容量等。容量等。 4. 运输问题运输问题这里涉及空运、水运、公路运输、

9、铁路运输、捷运、管这里涉及空运、水运、公路运输、铁路运输、捷运、管道运输和厂内运输等。包括班次调度计划及人员服务时道运输和厂内运输等。包括班次调度计划及人员服务时间安排等问题。间安排等问题。 5.财政和会计财政和会计这里涉及预算、贷款、成本分析、定价、投资、证券管这里涉及预算、贷款、成本分析、定价、投资、证券管理、现金管理等。用得较多的方法是：统计分析、数学理、现金管理等。用得较多的方法是：统计分析、数学规划、决策分析。此外，还有盈亏点分析法、价值分析规划、决策分析。此外，还有盈亏点分析法、价值分析法等。法等。 6. 人事管理人事管理这里涉及六方面。这里涉及六方面。(1)人员的获得和需求估计；

10、人员的获得和需求估计；(2)人才人才的开发，即进行教育和训练；的开发，即进行教育和训练；(3)人员的分配，主要是人员的分配，主要是各种指派问题；各种指派问题；(4)各类人员的合理利用问题；各类人员的合理利用问题；(5)人才人才的评价，其中有如何测定一个人对组织、社会的贡献；的评价，其中有如何测定一个人对组织、社会的贡献；(6)薪资和津贴的确定等。薪资和津贴的确定等。 7.设备维修、更新和可靠度、项目选择和评价设备维修、更新和可靠度、项目选择和评价如电力系统的可靠度分析、核能电厂的可靠度以及风如电力系统的可靠度分析、核能电厂的可靠度以及风险评估等。险评估等。 8.工程的最佳化设计工程的最佳化设计

11、在土木、建筑、水利、信息、电子、电机、光学、机在土木、建筑、水利、信息、电子、电机、光学、机械、环境和化工等领域皆有作业研究的应用。械、环境和化工等领域皆有作业研究的应用。 9.城市管理城市管理包括各种紧急服务救难系统的设计和运用。如消防队救包括各种紧急服务救难系统的设计和运用。如消防队救火站、救护车、警车等分布点的设立。美国曾用等候理火站、救护车、警车等分布点的设立。美国曾用等候理论方法来确定纽约市紧急电话站的值班人数。加拿大亦论方法来确定纽约市紧急电话站的值班人数。加拿大亦曾研究一城市警车的配置和负则范围，事故发生后警车曾研究一城市警车的配置和负则范围，事故发生后警车应走的路线等。应走的路

12、线等。分析与表述问题分析与表述问题建立模型建立模型对模型和由模型导出的解进行检验对模型和由模型导出的解进行检验建立起对解的有效控制建立起对解的有效控制对问题求解对问题求解方案实施方案实施不满意不满意满意满意运筹学应用步骤运筹学应用步骤五、运筹学在数学建模竞赛中的地位五、运筹学在数学建模竞赛中的地位有人统计：有人统计：在全国大学生数学建模竞赛题中有在全国大学生数学建模竞赛题中有40%可以用运筹可以用运筹学中的优化方法解决学中的优化方法解决1. CUMCM-1995A: 一个飞行管理问题一个飞行管理问题 2. CUMCM-2000B: 钢管订购与运输钢管订购与运输3. CUMCM-2003B：露天

13、矿生产的车辆安排：露天矿生产的车辆安排4. CUMCM-2000D: 空洞探测空洞探测5. CUMCM-2006 B: 艾滋病疗法的评价及疗效的预测艾滋病疗法的评价及疗效的预测6. CUMCM-2006 C : 易拉罐形状和尺寸的最优设计易拉罐形状和尺寸的最优设计7. CUMCM-2009B：眼科病床的合理安排：眼科病床的合理安排线线 性性 规规 划划线性规划实例 在各类经济活动中，经常遇到这样的问题：在各类经济活动中，经常遇到这样的问题：在生产条件不变的情况下，如何通过统筹安排，在生产条件不变的情况下，如何通过统筹安排，改进生产组织或计划，合理安排人力、物力资源，改进生产组织或计划，合理安排

14、人力、物力资源，组织生产过程，使总的经济效益最好。组织生产过程，使总的经济效益最好。可以化成或近似地化成可以化成或近似地化成“线性规划线性规划”（Linear Linear ProgrammingProgramming，简记为，简记为LPLP）问题）问题1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资

15、最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到的获利增加到 30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？ 每天每天例例: 奶制品生产计划奶制品生产计划 1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1 x2桶牛奶生产桶牛奶生产A2 获利获利 243x1 获利获利 164 x2 原料供应原料供应 5021 xx劳动时间劳动时间 48081221 xx加工能力加工能力 10031x决策变量决策变量 目标函数目标函数 216472xxzMax每天获利每天获利约束条件约束条件非负约束非负

16、约束 0,21xx线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天1212121127264. .501284803100,0Max zxxstxxxxxx x一般形式一般形式 目标函数目标函数 价值向量价值向量 价值系数价值系数 决策变量决策变量Tnccc),(1 njcj, 2 , 1, njxj, 2 , 1, nqjxqjxmsibxaxaxaspibxaxaxapibxaxaxatsxcxczjjininiiininiiininiinn, 1, 0, 1, 0, 1, 1, 1,.min(max)221122112

17、21111右端向量右端向量 mbbb1系系数数矩矩阵阵 mnmmnnaaaaaaaaaA212222111211非负约束非负约束自由变量自由变量规范形式规范形式标准形式标准形式 0.minxbAxtsxcT 0.minxbAxtsxcT三种形式的三种形式的LP问题全都是等价的，即一种形式问题全都是等价的，即一种形式的的LP可以简单的变换为另一种形式的可以简单的变换为另一种形式的LP，且它，且它们有相同的解们有相同的解 . max fx)(min(xfAxbAxb1nx1nAxxb1nAxxb0b jxjxjx jjjxxx min. .0Tc xst Axbx三者皆满足的向量三者皆满足的向量x

18、是最优解是最优解最优值：最优解的目标函数值最优值：最优解的目标函数值 0, xbAxxD线性规划模型的解的几种情况线性规划模型的解的几种情况 线性规划问题线性规划问题有可行解有可行解(Feasible)无可行解无可行解（Infeasible）有最优解（有最优解（Optimal）无最优解无最优解(Unbounded)图解法图解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx约约束束条条件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMax目标目标函数函数 Z=0Z=2400Z

19、=3600c在在B(20,30)点得到最优解点得到最优解模型求解模型求解 软件实现软件实现 LINDO 6.1 max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.0000

20、00 0.000000 NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生产桶牛奶生产A1, 30桶生产桶生产A2，利润，利润3360元。元。 结果解释结果解释 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4

21、) 40.000000 0.000000 NO. ITERATIONS= 2原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三种种资资源源“资源资源” 剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束） 结果解释结果解释 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR

22、 SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增的增量量 原料增加原料增加1单位单位, 利润增长利润增长48 时间增加时间增加1单位单位, 利润增长利润增长2 加工能力增长不影响利润加工能力增长不影响利润影子价格影子价格 35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？35 48, 应该买！应该买！ 聘用临时工人付出的工资最多每小时几元？聘用临时工人付出的工资最多每小

23、时几元？ 2元！元！RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666

24、667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000最优解不变时目标函最优解不变时目标函数系数允许变化范围数系数允许变化范围 DO RANGE(SENSITIVITY) ANALYSIS? Yesx1系数范围系数范围(64,96) x2系数范围系数范围(48,72) A1获利增加到获利增加到 30元元/公斤，应否改变生产计划公斤，应否改变生产计划 x1系数由系数由24 3=72增加增加为为30 3=90，在在允许范围内允许范围内 不变！不变！(约束条件不变约束条件不变)结果解释结果解释 RANGES IN WH

25、ICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.33

26、3332 80.000000 4 100.000000 INFINITY 40.000000影子价格有意义时约束右端的允许变化范围影子价格有意义时约束右端的允许变化范围 原料最多增加原料最多增加10 时间最多增加时间最多增加53 35元可买到元可买到1桶牛奶，每天最多买多少？桶牛奶，每天最多买多少？最多买最多买10桶桶!(目标函数不变目标函数不变)运运 输输 问问 题题分分 析：析：v决策变量决策变量 设设 表示从仓库表示从仓库 运往零售点运往零售点 的物资数量的物资数量ijxiAjBv目标函数目标函数目标：运费最省目标：运费最省11 11121213 13141421212222232324

27、24zc xc xc xc xc xc xc xc xv约束条件约束条件从仓库运出总量不超过可用总量，运入零售从仓库运出总量不超过可用总量，运入零售点的数量不低于需求量。由于总供给量等于点的数量不低于需求量。由于总供给量等于总需求量，所以都是等号。即总需求量，所以都是等号。即2 , 1;4321 iaxxxxiiiii4 , 3 , 2 , 1;21 jbxxjjj蕴含约束蕴含约束：数量非负：数量非负4 , 3 , 2 , 1, 2 , 1; 0 jixij模模 型：型：收发平衡型的运输问题收发平衡型的运输问题1111min. .,1,2,1,2,0,1,2,1,2,mnijijijnijij

28、mijjiijzc xstxa imxbjnxim jn从从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个产

29、地和个产地和4个销地的运个销地的运输问题，其产量、销量及单位运费如表输问题，其产量、销量及单位运费如表7-1所示所示.试求总运费最少的运输方案，以及总运费试求总运费最少的运输方案，以及总运费.解：解：从前面的分析来看，运输问题属于线性规划问从前面的分析来看，运输问题属于线性规划问题，因此，不论是题，因此，不论是LINDO软件或软件或LINGO软件都可以对软件都可以对该问题求解该问题求解. 写出写出LINDO软件的模型（程序），程序名：软件的模型（程序），程序名：transportation.ltx ! 3 Warehouse, 4 Customer Transportation Problem

30、! The objectivemin 6x11 + 2x12 + 6x13 + 7x14 + 4x21 + 9x22 + 5x23 + 3x24 + 8x31 + 8x32 + x33 + 5x34subject to! The supply constraints2) x11 + x12 + x13 + x14 = 303) x21 + x22 + x23 + x24 = 254) x31 + x32 + x33 + x34 = 21! The demand constraints5) x11 + x21 + x31 = 156) x12 + x22 + x32 = 177) x13 + x

31、23 + x33 = 228) x14 + x24 + x34 = 12endLINDO软件的计算结果如下：软件的计算结果如下：LP OPTIMUM FOUND AT STEP 6 OBJECTIVE FUNCTION VALUE 1) 161.0000 VARIABLE VALUE REDUCED COST X11 2.000000 0.000000 X12 17.000000 0.000000 X13 1.000000 0.000000 X14 0.000000 2.000000 X21 13.000000 0.000000 X22 0.000000 9.000000 X23 0.0000

32、00 1.000000X24 12.000000 0.000000 X31 0.000000 7.000000 X32 0.000000 11.000000 X33 21.000000 0.000000 X34 0.000000 5.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 10.000000 0.000000 3) 0.000000 2.000000 4) 0.000000 5.000000 5) 0.000000 -6.000000 6) 0.000000 -2.000000 7) 0.000000 -6.000000 8) 0.000000 -

33、5.000000 NO. ITERATIONS= 6事实上，我们关心更多的是那些非零变量，因此事实上，我们关心更多的是那些非零变量，因此,可选择可选择LINDO中的命令只列出非零变量中的命令只列出非零变量. OBJECTIVE FUNCTION VALUE 1) 161.0000 VARIABLE VALUE REDUCED COST X11 2.000000 0.000000 X12 17.000000 0.000000 X13 1.000000 0.000000 X21 13.000000 0.000000 X24 12.000000 0.000000 X33 21.000000 0.00

34、0000 ROW SLACK OR SURPLUS DUAL PRICES 3) 0.000000 2.000000 4) 0.000000 5.000000 5) 0.000000 -6.000000 6) 0.000000 -2.000000 7) 0.000000 -6.000000 8) 0.000000 -5.000000 NO. ITERATIONS= 6参考文献参考文献1 谢金星，薛毅谢金星，薛毅.优化建模与优化建模与LINDO/LINGO软件软件M.北京：北京： 清华大学出版社清华大学出版社.2005,7.2 姜启源，谢金星，叶俊姜启源，谢金星，叶俊.数学模型（第三版）数学模型

35、（第三版）M.北京：北京： 高等教育出版社高等教育出版社.2005,12.3 刁在筠，刘桂真等刁在筠，刘桂真等. 运筹学运筹学M.北京：高等教育出版北京：高等教育出版 社社.2009,12.4 牛映武，运筹学牛映武，运筹学M.西安：西安交通大学出版社西安：西安交通大学出版社. 2006.55 胡运权，运筹学教程胡运权，运筹学教程M. 北京：清华大学出版社北京：清华大学出版社. 2007.4整整 数数 规规 划划要求变量取整数值的线性规划问题称为要求变量取整数值的线性规划问题称为整数线性规划整数线性规划要求变量取要求变量取0 0或或1 1的线性规划问题称为的线性规划问题称为0-10-1规划规划只

36、要求部分变量取整数值的线性规划称为只要求部分变量取整数值的线性规划称为混合整数线混合整数线性规划性规划例例投资决策问题投资决策问题 某某部部门门在在今今后后五五年年中中可可用用于于投投资资的的资资金金总总额额为为B万万元元，有有)2( nn个个可可以以考考虑虑的的投投资资项项目目，假假定定每每个个项项目目最最多多投投资资一一次次， 第第), 1(njj 个个项项目目所所需需的的资资金金为为jb万万元元，将将会会获获得得的的利利润润为为jc万万元元.问问应应如如何何选选择择投投资资项项目目，才才能能使使获获得得的的总总利利润润最最大大. B解解21n1b2bnb1c2cnc个项目个项目决定投资第

37、决定投资第jjjbb1 jjcc1 个项目个项目决定不投资第决定不投资第jjb00 jc00 个个项项目目；，决决定定不不投投资资第第个个项项目目；，决决定定投投资资第第jjxj01投资决策变量投资决策变量 设获得的总利润为设获得的总利润为z，则上述问题的数学模型为，则上述问题的数学模型为 njxBxbtsxczjnjjjnjjj, 1100.max11，或或0)1( jjxx变量限制为整数本质上是一个非线性约束，它不可变量限制为整数本质上是一个非线性约束，它不可能用线性约束来代替它能用线性约束来代替它. 1954年年 G.G.Dantzig D.R.Fulkerson and S.M.Joh

38、nson研究研究推销商问题（货郎担问题）推销商问题（货郎担问题）,首先提出首先提出破子圈方法破子圈方法和将和将问题问题分解为几个子问题之和分解为几个子问题之和的思想，这是的思想，这是割平面方法割平面方法和和分分枝定界法枝定界法的萌芽的萌芽1958年年 R.E.Gomory 创立创立割平面算法割平面算法1960年年 A.H.Land and A.G.Doig 对推销商问题提出对推销商问题提出分解算分解算法法，紧接着，紧接着，E.Balas等人将其发展成一般的等人将其发展成一般的分枝定界法分枝定界法，从而形成独立的整数规划分支从而形成独立的整数规划分支1993年年 W.J.Cook 平行计算平行计

39、算研究研究10907064个城市的货郎担个城市的货郎担问题问题整数规划简史整数规划简史例例旅行售货员问题旅行售货员问题 （货郎担问题）（货郎担问题）(TSP问题）问题）解对每一对城市对每一对城市iv和和jv，我们指定一个变量，我们指定一个变量ijx，令，令 ，其它情况，其它情况；直接进入直接进入，如果推销员决定从，如果推销员决定从01jiijvvx首先，每个城市恰好进入一次，即首先，每个城市恰好进入一次，即njxniij, 0, 10 nixnjij, 0, 10 其次，每个城市恰好离开一次，即其次，每个城市恰好离开一次，即第三，不能第三，不能出现多于一个互不连通的旅行路线圈，出现多于一个互不

40、连通的旅行路线圈，且不排除任何可能的旅行路线且不排除任何可能的旅行路线 1 22 11 22 33 11 22 32-1-11122nnni ii ii ii ii ii ii iiiiixxxxxxxxxn常用算法：常用算法：割平面算法、分枝定界法、解割平面算法、分枝定界法、解0-10-1规划的隐枚规划的隐枚举法、分解算法、举法、分解算法、 群论方法、动态规划方法群论方法、动态规划方法一般只能用来解决中小型的一般只能用来解决中小型的ILPILP问题问题近似算法近似算法19931993年年7 7月月 W.J.Cook 并行计算并行计算 10907064个城市个城市货郎担问题货郎担问题计算机模拟

41、法计算机模拟法 如如Monte-Carlo方法方法丁的蛙泳成绩退步到丁的蛙泳成绩退步到115”2；戊的自由泳成绩进；戊的自由泳成绩进步到步到57”5, 组成接力队的方案是否应该调整组成接力队的方案是否应该调整？如何选拔队员组成如何选拔队员组成4 4 100100米混合泳接力队米混合泳接力队? ?例例 混合泳接力队的选拔混合泳接力队的选拔 甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”45名候选人的名候选人的百米

42、成绩百米成绩穷举法穷举法：组成接力队的方案共有组成接力队的方案共有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.44151jiijijxcZMin每种泳姿有且

43、只有每种泳姿有且只有1 1人人 5, 1, 141ixjij4, 1, 151jxiij模型求解模型求解 最优解：最优解：x14 = x21 = x32 = x43 = 1, 其它变量为其它变量为0;成绩为成绩为253.2( (秒秒) )=413”2 MIN 66.8x11+75.6x12+87x13+58.6x14 + +67.4x51+71x52+83.8x53+62.4x54SUBJECT TO x11+x12+x13+x14 =1 x51+x52+x53+x54 =1 x11+x21+x31+x41+x51 =1 x14+x24+x34+x44+x54 =1END 输入输入LINDO求

44、解求解 甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”4甲甲 自由泳、乙自由泳、乙 蝶泳、蝶泳、丙丙 仰泳、丁仰泳、丁 蛙泳蛙泳. .丁蛙泳丁蛙泳c43 = =69.675.2，戊自由泳，戊自由泳c54= =62.4 57.5, , 方案是否调整？方案是否调整？ 敏感性分析？敏感性分析？乙乙 蝶泳、丙蝶泳、丙 仰泳、仰泳、丁丁 蛙泳、戊蛙泳、戊 自由泳自由泳IP规划一般没有与规划一般没有与LP规划相类似的理论，

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

46、最少，应学习哪些课程为了选修课程门数最少，应学习哪些课程 ？ 例例 选课策略选课策略要求至少选两门数学课、三门运筹学课和两门计算机课要求至少选两门数学课、三门运筹学课和两门计算机课 课号课号课名课名学分学分所属类别所属类别先修课要求先修课要求1微积分微积分5数学数学 2线性代数线性代数4数学数学 3最优化方法最优化方法4数学；运筹学数学；运筹学微积分；线性代数微积分；线性代数4数据结构数据结构3数学；计算机数学；计算机计算机编程计算机编程5应用统计应用统计4数学；运筹学数学；运筹学微积分；线性代数微积分；线性代数6计算机模拟计算机模拟3计算机；运筹学计算机；运筹学计算机编程计算机编程7计算机编

47、程计算机编程2计算机计算机 8预测理论预测理论2运筹学运筹学应用统计应用统计9数学实验数学实验3运筹学；计算机运筹学；计算机微积分；线性代数微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程选修课程最少，且学分尽量多，应学习哪些课程 ？ 0-1规划模型规划模型 决策变量决策变量 目标函数目标函数 xi=1 选修课号选修课号i 的的课程（课程（xi=0 不选）不选） 91iixZMin选修课程总数最少选修课程总数最少 约束条件约束条件最少最少2门数学课，门数学课，3门运筹学课，门运筹学课，2门计算机课。门计算机课。 254321xxxxx398653xxxxx29764xxxx课号课号课

48、名课名所属类别所属类别1微积分微积分数学数学2线性代数线性代数数学数学3最优化方法最优化方法数学；运筹学数学；运筹学4数据结构数据结构数学；计算机数学；计算机5应用统计应用统计数学；运筹学数学；运筹学6计算机模拟计算机模拟计算机；运筹学计算机；运筹学7计算机编程计算机编程计算机计算机8预测理论预测理论运筹学运筹学9数学实验数学实验运筹学；计算机运筹学；计算机先修课程要求先修课程要求74xx 02215xxx076 xx058xx02219xxx最优解：最优解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它为其它为0；6门课程，总学分门课程，总学分21 02213xxx0

49、-1规划模型规划模型 约束条件约束条件x3=1必有必有x1 = x2 =12313,xxxx074 xx模型求解（模型求解（LINDO） 课号课号课名课名先修课要求先修课要求1微积分微积分 2线性代数线性代数 3最优化方法最优化方法微积分；线性代数微积分；线性代数4数据结构数据结构计算机编程计算机编程5应用统计应用统计微积分；线性代数微积分；线性代数6计算机模拟计算机模拟计算机编程计算机编程7计算机编程计算机编程 8预测理论预测理论应用统计应用统计9数学实验数学实验微积分；线性代数微积分；线性代数学分最多学分最多多目标优化的处理方法：化成单目标优化。多目标优化的处理方法：化成单目标优化。两目标

50、两目标( (多目标多目标) )规划规划 987654321322343445xxxxxxxxxWMax,WZMin讨论：选修课程最少，学分尽量多，应学习哪些课程？讨论：选修课程最少，学分尽量多，应学习哪些课程？ 91iixZMin课程最少课程最少 以以学分最多为目标，不学分最多为目标，不管课程多少。管课程多少。 以课程最少以课程最少为目标，不为目标，不管学分多少。管学分多少。最优解如上，最优解如上，6门课门课程，总学分程，总学分21 。最优解显然是选修所最优解显然是选修所有有9门课程门课程 。多目标规划多目标规划 在在课程最少的前提下课程最少的前提下以以学分最多为目标。学分最多为目标。最优解：

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

52、加权形成一个目标，如三七开。对学分数和课程数加权形成一个目标，如三七开。 987654321322343445xxxxxxxxxW91iixZWZWZYMin3 . 07 . 021WZWZYMin3 . 07 . 021=-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。课号课号课名课名学分学

53、分1微积分微积分52线性代数线性代数43最优化方法最优化方法44数据结构数据结构35应用统计应用统计46计算机模拟计算机模拟37计算机编程计算机编程28预测理论预测理论29数学实验数学实验3 多目标规划的求解方法多目标规划的求解方法1、化多为少的方法：把多目标规划问题归为单目标、化多为少的方法：把多目标规划问题归为单目标的数学规划的数学规划(线性规划或非线线性规划或非线 性规划性规划)问题进行求解问题进行求解 线性加权和法线性加权和法 理想点法理想点法 2、分层求解法、分层求解法 假若目标函数多目标规划假若目标函数多目标规划 的各个分目标可以按其的各个分目标可以按其在问题中的重要程度排出先后次

54、序，先对第一个在问题中的重要程度排出先后次序，先对第一个目标进行极小化，设得到的最优解目标进行极小化，设得到的最优解 x,然后按固定然后按固定格式依次分层对各目标进行极小化格式依次分层对各目标进行极小化 3、层次分析法、层次分析法 (Analytic Hierarchy Process, AHP)图图 论论 与与 网网 络络 优优 化化 图论的研究最早可追溯到著名的图论的研究最早可追溯到著名的七桥问题七桥问题. .1818世纪欧世纪欧洲的哥尼斯堡城中有一条河叫普雷格尔河，该河中有洲的哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有七座桥，如图所示两个岛，河上有七座桥，如图所示. .当时

55、那里的人们当时那里的人们就考虑：能否从就考虑：能否从A A、B B、C C、D D中任一地方出发，走每座中任一地方出发，走每座桥一次而且只走一次，最后刚好回到出发点桥一次而且只走一次，最后刚好回到出发点. .例例 公路连接问题公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，城市连接起来， 使得从其中任何一个城市都可以经高速公使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市路直接或间接到达另一个城市. 假定已经知道了任意两个城假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市市之间

56、修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？间修建高速公路，使得总成本最小？ 例例 最短路问题（最短路问题（SPP-Shortest Path Problem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地往乙地. 从甲地到乙地的公路网纵横交错，因此有多种行车从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地

57、的最短路乙地的最短路. 例例 运输问题运输问题(Transportation Problem)某种原材料有某种原材料有M个产地，现在需要将原材料从产地运往个产地，现在需要将原材料从产地运往N个个使用这些原材料的工厂使用这些原材料的工厂. 假定假定M个产地的产量和个产地的产量和N家工厂的家工厂的需要量已知，单位产品从任一产地到任一工厂的的运费已需要量已知，单位产品从任一产地到任一工厂的的运费已知，那么如何安排运输方案可以使总运输成本最低？知，那么如何安排运输方案可以使总运输成本最低？ 例例 指派问题指派问题(Assignment Problem)一家公司经理准备安排一家公司经理准备安排N名员工去

58、完成名员工去完成N项任务，每人一项项任务，每人一项. 由于各员工的特点不同，不同的员工去完成同一项任务时由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的所获得的回报是不同的. 如何分配工作方案可以使总回如何分配工作方案可以使总回 报最报最大？大？ 例例 中国邮递员问题中国邮递员问题(CPP-Chinese Postman Problem)一名邮递员负责投递某个街区的邮件一名邮递员负责投递某个街区的邮件. . 如何为他如何为他( (她她) )设计设计一条最短的投递路线一条最短的投递路线( (从邮局出发，经过投递区内每条街道从邮局出发，经过投递区内每条街道至少一次，最后返回邮

59、局至少一次，最后返回邮局) )？由于这一问题是我国？由于这一问题是我国管梅谷管梅谷教教授授19601960年首先提出的，所以国际上称之为中国邮递员问题年首先提出的，所以国际上称之为中国邮递员问题. . 例例 旅行商问题旅行商问题/货郎（担）问题货郎（担）问题(TSP-Traveling Salesman Problem)一名推销员准备前往若干城市推销产品一名推销员准备前往若干城市推销产品. . 如何为他如何为他( (她她) )设设计一条最短的旅行路线计一条最短的旅行路线( (从驻地出发，经过每个城市恰好一从驻地出发，经过每个城市恰好一次，最后返回驻地次，最后返回驻地) )？这一问题的研究历史十

60、分悠久，通常？这一问题的研究历史十分悠久，通常称之为旅行商问题称之为旅行商问题. . 动动 态态 规规 划划运筹学的一个分支，解决多阶段决策过程最优化运筹学的一个分支，解决多阶段决策过程最优化的一种数学方法的一种数学方法多阶段决策过程多阶段决策过程指一类活动过程，它可以分为指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决若干个相互联系的阶段，在每个阶段都需要作出决策策. 这个决策不仅决定这一阶段的效益，而且决定下这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态一阶段的初始状态. 每个阶段的决策确定以后，就得每个阶段的决策确定以后，就得到一个决策序列，称为到一个决