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

运筹学在数学建模中的应用•一、运筹学概况•二、线性规划•三、整数规划与多目标规划•四、图论与网络优化•五、动态规划•六、赛题选讲运筹学概况运筹学的定义运筹学简史运筹学的主要内容及应用重点运筹学应用步骤运筹学在数学建模竞赛中的地位运筹学是一种给出问题不坏的答案的艺术，否则的话问题的结果会更坏。一、运筹学的定义☆运筹学(《辞海》)：20世纪40年代开始形成的一门学科，主要研究经济活动与军事活动中能用数量来表达的有关运用、筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，做出综合性合理安排，以达到较经济有效地使用人力物力.☆作为一门定量优化决策科学，起源于第二次世界战，英文原意OperationResearch；二、运筹学简史深水炸弹的释放问题防空系统的预警问题运筹学的一些分支英美海空军作战参谋部组成了运筹学研究小组二战中二战后军事工、商业领域存储论、决策科学、预测科学等分支☆20世纪50年代中期钱学森和许国志教授引入“运用学”＊1957年取“运筹”二字，将OR正式命名为“运筹学”开始应用于建筑业和纺织业《史记》中“夫运筹帷幄之中，决胜千里之外”线性规划数学规划非线性规划整数规划动态规划多目标规划组合优化最优计数问题网络优化排序问题统筹图随机优化对策论排队论库存论决策分析可靠性分析三、运筹学主要内容数学规划模型的数学描述下的最大值或最小值。.,...,,,)(mihi210x.,...,,),)(()(piggii2100xx),...,,,(nxxxx321x将一个优化问题用数学式子来描述，即求函数)(xfu在约束条件和数学规划问题的一般形式约束条件决策变量njiDxljxgmixhtsxf,...,1,0)(,...,1,0)(..)(minnjiDxljxgmixhtsxf,...,1,0)(,...,1,0)(..)(min目标函数tosubjectts..“受约束于”之意分析与表述问题建立模型对模型和由模型导出的解进行检验建立起对解的有效控制对问题求解方案实施不满意满意运筹学应用步骤五、运筹学在数学建模竞赛中的地位有人统计：在全国大学生数学建模竞赛题中有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公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1制订生产计划，使每天获利最大•35元可买到1桶牛奶，买吗？若买，每天最多买多少?•可聘用临时工人，付出的工资最多是每小时几元?•A1的获利增加到30元/公斤，应否改变生产计划？每天例:奶制品生产计划1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤x1桶牛奶生产A1x2桶牛奶生产A2获利24×3x1获利16×4x2原料供应5021xx劳动时间48081221xx加工能力10031x决策变量目标函数216472xxzMax每天获利约束条件非负约束0,21xx线性规划模型(LP)时间480小时至多加工100公斤A150桶牛奶每天1212121127264..501284803100,0Maxzxxstxxxxxxx⑴．一般形式目标函数价值向量价值系数决策变量Tnccc),,(1njcj,,2,1,njxj,,2,1,nqjxqjxmsibxaxaxaspibxaxaxapibxaxaxatsxcxczjjininiiininiiininiinn,1,0,,1,0,,1,,,1,,,1,..min(max)22112211221111右端向量mbbb1系数矩阵mnmmnnaaaaaaaaaA212222111211非负约束自由变量⑵．规范形式⑶．标准形式0..minxbAxtsxcT0..minxbAxtsxcT三种形式的LP问题全都是等价的，即一种形式的LP可以简单的变换为另一种形式的LP，且它们有相同的解.对于非标准形式的线性规划，可通过下列办法化成标准形式①若求,可化为求maxfx))(min(xf②若约束条件中含有不等式或则可引进新变量（称为松弛变量），化为等式约束：或AxbAxb1nx1nAxxb1nAxxb③总假定，否则在等式两边乘以-1即可0b④若变量无非负限制，则引入两个非负变量与令，便可化为标准形式jxjxjxjjjxxxmin..0TcxstAxbx满足所有约束条件的向量x称为可行解或者可行点三者皆满足的向量x是最优解最优值：最优解的目标函数值可行区域：所有的可行点组成的集合称为(LP)问题的可行区域.记为D}0,{xbAxxD线性规划模型的解的几种情况线性规划问题有可行解(Feasible)无可行解（Infeasible）有最优解（Optimal）无最优解(Unbounded)图解法x1x20ABCDl1l2l3l4l55021xx48081221xx10031x0,21xx约束条件50:211xxl480812:212xxl1003:13xl0:,0:2514xlxl216472xxzMax目标函数Z=0Z=2400Z=3600c在B(20,30)点得到最优解模型求解软件实现LINDO6.1max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100endOBJECTIVEFUNCTIONVALUE1)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.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料无剩余时间无剩余加工能力剩余40max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三种资源“资源”剩余为零的约束为紧约束（有效约束）结果解释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桶牛奶，要买吗？3548,应该买！•聘用临时工人付出的工资最多每小时几元？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系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)结果解释RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加53•35元可买到1桶牛奶，每天最多买多少？最多买10桶!(目标函数不变)运输问题例一个制造厂要把若干单位的产品从两个仓库2,1;iAi发送到零售点4,3,2,1;jBj，仓库iA能供应的产品数量为2,1;iai，零售点jB所需的产品的数量为4,3,2,1;jbj。假设供给总量和需求总量相等，即2411ijijab，且已知从仓库iA运一个单位产品往jB的运价为ijc。问应如何组织运输才能使总运费最小？分析：决策变量设表示从仓库运往零售点的物资数量ijxiAjB目标函数目标：运费最省11111212131314142121222223232424zcxcxcxcxcxcxcxcx约束条件从仓库运出总量不超过可用总量，运入零售点的数量不低于需求量。由于总供给量等于总需求量，所以都是等号。即2,1;4321iaxxxxiiiii4,3,2,1;21jbxxjjj蕴含约束：数量非负4,3,2,1,2,1;0jixij模型：min2141ijijijxc2,1;4321iaxxxxiiiiis.t.4,3,2,1;21jbxxjjj4,3,2,1,2,1;0jixij收发平衡型的运输问题1111min..,1,2,,1,2,0,1,2,,1,2,mnijijijnijijmijjiijzcxstxaimxbjnximjn从m个发点A