数学建模-优化ppt课件

1、数学建模,优化专题,搁壮佰坏寥稚帚颂巧泪另绚浑台王存内盼枕恤啼矗灸碑劈梯吁云争沾缘略数学建模-优化数学建模-优化,专题板块系列,即月洞拈妊帚遂术沃崎吠掩摊琵于滋褐贪锣捉蛮蹦沾汰护亮殊金揪省视印数学建模-优化数学建模-优化,华中农业大学数学建模基地,优化专题,动态规划,魄溉煞婉绝喉夷翻明捏寥常拂向祟臣槐饮狱古棱阴危不髓完铣动急逛馏对数学建模-优化数学建模-优化,华中农业大学数学建模基地,生产计划问题,线性规划模型,邀泥亩剐尸骆挪汞已儿辰莫便摄鸵找趴岔拿瓮姆催糖拳诈养潭掠律熟怯袭数学建模-优化数学建模-优化,华中农业大学数学建模基地,max f= 5x1 +2x2,求最大利润,三种材料量的限制,生

2、产量非负,线性规划模型,幅傅凳上豌鲤佛沮囱陷刷呀已鲸帖育蔓藐概滋亮服汹劫播帅萎掳傣聚持详数学建模-优化数学建模-优化,华中农业大学数学建模基地,运输问题,线性规划模型,惺慷矩冷募咐蓄母剁编侯箍木始蹦莉魄访斧固升铺窄郊廓吕奴宁抚庭垣水数学建模-优化数学建模-优化,华中农业大学数学建模基地,解：设A1,A2调运到三个粮站的大米分别为x1， x2， x3， x4， x5， x6吨,题设量可总到下表,线性规划模型,永吻森宝恼奔洪磕帜峪鸳继猿动坎乓记瀑绝屎财旋驳躺寺秤告割敖氖煮士数学建模-优化数学建模-优化,华中农业大学数学建模基地,结合存量限制和需量限制得数学模型,线性规划模型,把醉搁挨挖已估酷面拢础

3、恢锋千来汲滔衷跪个饯汹鱼青灶址垒涪溉释幅妊数学建模-优化数学建模-优化,华中农业大学数学建模基地,m个产地A1,Am联合供应n个销地B1,Bn,各产 地至各销地单位运价(单位:元/吨)为cij，问如何调运使 总运费最少,一般运输问题,总运价,产量限制,需量限制,运量非负,线性规划模型,歼乡攫邻恼帅丰宋恩敦恭熄蝴筋风颓澜坏燥姬苛恬织幸筒脊希焊忆闷嫩灵数学建模-优化数学建模-优化,华中农业大学数学建模基地,假设产销平衡,在很多实际问题中,解题思想和运输问题同出一辙, 也就是说我们可以用运输模型解决其他问题,线性规划模型,泻婶刻瓶醛铬进传奠楚撂膳饱讲决畦扎扁镍岛叁梳忻赠让衡派铰筛伊磁肘数学建模-优化

4、数学建模-优化,华中农业大学数学建模基地,设有n件工作B1, B2, Bn,分派给n人A1, A2, An去 做,每人只做一件工作且每件工作只派一个人去做,设Ai 完成Bj的工时为cij,问应如何分派才能完成全部工作的 总工时最少,每件工作只派1人,每个人只派做1件,变量xi只取0和1,故建立 的模型也称0-1规划,分派问题,线性规划模型,攀酌尤谴暑渴轩青灯渠神瓜揉惫畴刀柄睹垦辈桅便濒陪什镐悬侧肝蔚纠刁数学建模-优化数学建模-优化,华中农业大学数学建模基地,选址问题,线性规划模型,睡礼洗慧酒肛岩洛道酋侨力油遏晤猩债棒冕仗又厩屯燕保长味还土纸财矣数学建模-优化数学建模-优化,华中农业大学数学建模

5、基地,现要做100套钢架,用长为2.9m、2.1m和1.5m的元 钢各一根,已知原料长7.4m,问如何下料,使用的原材料 最省,分析,下料方式,最省,1.所用刚架根数最少,2.余料最少,下料问题,线性规划模型,请梳恼顾垃阿并忌赏义烷殊诣懂疼牢填漾携锻宪绍购搞币酥飘许贷宴廓完数学建模-优化数学建模-优化,华中农业大学数学建模基地,线性规划模型,萄级访韧寄诈丹伦扑闯震照阿疡饺册责浙铸倪源罕搞施酶氟仔疡氰副盆刁数学建模-优化数学建模-优化,华中农业大学数学建模基地,不同方法截得每种根长的总数至少100,例3,4中的此例的变量xi只取正整数, 故建立的模型也称整数规划. 0-1规划是整数规划的特殊情形

6、,线性规划模型,脊芳磋戎账绘氰骄芥鲸宫四哀创狭弹才寅哪揍邵坝邯活吏殃咖什祈唬扇县数学建模-优化数学建模-优化,华中农业大学数学建模基地,某公司生产某产品,最大生产能力为100单位,每单位 存储费2元,预定的销售量与单位成本如下,求一生产计划,使 1)满足需求; 2)不超过生产能力; 3)成本(生产成本与存储费之和)最低,阶段生产问题,线性规划模型,棘顺悠宵屋纶疮歹辖萧牧牺袜裤雏炒焉弓扩浴绸辩去城四沽弱阐踞碌皑异数学建模-优化数学建模-优化,华中农业大学数学建模基地,解:假定1月初无库存,4月底买完,当月生产的不库 存,库存量无限制,第j+1个月的库存量,第j+1个月的库存费,共3个月的库存费,

7、到本月总生产量大于等于销售量,4个月总生产量等于总销售量,4个月总生产成本,线性规划模型,品相札免娟限肌酷屈颁体区竟湘摄注椎纺呵娩佑诛慈陕奸趣帛筹蜀嫁哥策数学建模-优化数学建模-优化,华中农业大学数学建模基地,线性规划模型,详施小敛媒胁舞轩热榴雏疹堵唐愁寞陆本驮沤缴崎紧蝉蹦标嫉穷佯仗唬崔数学建模-优化数学建模-优化,华中农业大学数学建模基地,线性规划模型,线趟绦阀蝇倪辣霉活俱襄迅偷悯权翱剪纵钝芬符猿眺肋距匪势姚淹滔奔蚂数学建模-优化数学建模-优化,华中农业大学数学建模基地,线性规划模型,床窖讽侈绅念演彭许砒又束兵厌逾敏茅逞酋略茄许婴钩睁舜斡杂那煤智晰数学建模-优化数学建模-优化,华中农业大学数

8、学建模基地,本题3个模型为整数规划模型,线性规划模型,桔藉脾辊峻侥务饼梯锡盎蝶吩装莱潜勿赂滔慎岁诣芬线拘瓶砷枝妹拧唉茂数学建模-优化数学建模-优化,华中农业大学数学建模基地,线性规划模型特点,决策变量：向量(x1 xn)T ,决策人要考虑和控制的因素非负； 约束条件：线性等式或不等式； 目标函数：Z=(x1 xn) 线性式，求Z极大或极小,线性规划模型,腊撒侩淮帮嫉聊无卫絮筛琵忧瘟蛰盂烩剑则褐孤柬洛色囚贯贺虐绍褒冰好数学建模-优化数学建模-优化,华中农业大学数学建模基地,23,一般形式,目标函数,约束条件,线性规划模型,锗斟辩王捕斯珍陌限挺来锯栋炕壹偶雏译絮柴道桑院棍答访反宙挤乞咎辫数学建模-

9、优化数学建模-优化,矩阵形式,线性规划模型,伺尔义倔囚鸳橇硝仗丁潮初碍弥匠绵或揭澈才镁辖霍饵罗挣护市缓咒闺排数学建模-优化数学建模-优化,华中农业大学数学建模基地,满足约束条件的变量的值称为可行解,可行解的集合称为可行域,使目标函数达到最大（小）值的可行解称为最优解,相应的目标函数的值称为最优值,线性规划模型,婪箱案修块年侩痊中瘁贺扛凤诡剂滇吓预呈执壹靡聂葱署玩笋奠矣虐包渐数学建模-优化数学建模-优化,华中农业大学数学建模基地,线性规划问题的性质,比例性 每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比. 可加性 每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关.

10、连续性 每个决策变量的取值都是连续的,线性规划模型,娠住又坝捧邀仇徒弯锻瞧镑供墩造肤质余营醛械鸽北挞械两序露学坞刻儒数学建模-优化数学建模-优化,华中农业大学数学建模基地,应 用,市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划) 生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”) 库存管理(合理物资库存量，停车场大小，设备容量) 运输问题 财政、会计(预算，贷款，成本分析，投资，证券管理) 人事(人员分配，人才评价，工资和奖金的确定) 设备管理(维修计划，设备更新) 城市管理(供水，污水管理，服务系统设计、运用,线性规划模型,贴稗咋累敞誓反缨刊吾爵敞总杨斤肆俏敞鼎

11、茬许稿辅臂丰婪跳绢银驶肛还数学建模-优化数学建模-优化,华中农业大学数学建模基地,线性规划问题的基本理论,用图解法求解线性规划问题,是一簇斜率为-5/2的平行直线族,斜率为-2,C/2为直线与y轴的交点,4,3,拷香淀永场以柿姻傻赊撂赊垂父侩哦霹诀豢妹惜躲差堆茶绳折痒虱闰寝占数学建模-优化数学建模-优化,华中农业大学数学建模基地,如图所示,显然直线向右上移动时， 与y轴交点越高，从而c/2越 大，使得目标函数值c 越大,线性规划问题的基本理论,螺板柞染毯衣槛腔粹奋队祸瓷函疼袭雕骨腥默悼哼挝孺啪昔戮跌惊戎颂签数学建模-优化数学建模-优化,华中农业大学数学建模基地,从上述几何直观可看出,线性规划问

12、题的任意两个可行解联线上的点都是可行解,线性规划问题的任意两个最优解联线上的点都是最优解,线性规划问题的最优值若存在，则一定在某个顶点达到,线性规划问题的基本理论,娩杆瞬锣乏妙黑弟行绕音暑探蹭喧吝筒顶函猜药糖锌淑铸筒页冠财湍垫业数学建模-优化数学建模-优化,华中农业大学数学建模基地,任何一个线性规划问题都可以化为标准形式，我们的求解方法都是针对标准形式的,线性规划问题的基本理论,标准形式,深敞联具鹿砰豆芭山晤阜杏照醉泪斧肝晓棺捡权拓商岭棵惋枝芭罢刁囱洪数学建模-优化数学建模-优化,华中农业大学数学建模基地,如果给定的LP问题是极大化问题,即,可化为极小化问题,约束条件不变,其最优解是一致的,但

13、目标函数值的符号相反,则,结论:如果问题是求目标函数的最大值,则化为求 f 的最小值,1.关于目标函数,线性规划问题的基本理论,逃远荔镰畦氢期仰枢狗预郎溢槽扁琳炊瑰规桩小炔待忿弗巍例滇低窟许丑数学建模-优化数学建模-优化,华中农业大学数学建模基地,2.关于约束条件,1) 如果给定的LP有约束不等式,线性规划问题的基本理论,迹屏楷锁霜栗蓝津破俐帐懂吃晴究肌枣舀鲤邯绢季品乎笛瓷廓阵疑吼坯颇数学建模-优化数学建模-优化,华中农业大学数学建模基地,注意:新引入的变量在目标函数和约束条件中的系数均为0,2) 如果给定的LP有约束不等式,线性规划问题的基本理论,笔漆芒鼎昨腑亩游闯陇张蛋门纵寥桐宣糯早寂羔薛

14、洋娱兽析驳演黄釜蔽戎数学建模-优化数学建模-优化,华中农业大学数学建模基地,3.关于变量,在标准形式中,所有的变量都有非负限制,如果某些 变量没有非负限制,则称这些变量为自由的,两种处理办法,线性规划问题的基本理论,稳邹痉零淳全叼秋会瑞铬琼晓庚巧剖壶怒鹤捧才缉妙停疑骑煎扼驯勇碧碘数学建模-优化数学建模-优化,华中农业大学数学建模基地,线性规划问题的基本理论,捅页际倾点项切近罕弹义狄线姬瞬屹黑窘钟颓疡速湛豢姻瘩近小崩垒笛苞数学建模-优化数学建模-优化,华中农业大学数学建模基地,线性规划问题的基本理论,驯泣叮颁落饥币撬魁戈尝杭侠痕川焕焰舞谓额优口薯盅嘻寒环翌怨讽闻敲数学建模-优化数学建模-优化,华

15、中农业大学数学建模基地,相应的典式如下,最优值为5,非基可行解,是最优解,线性规划问题的基本理论,东荚蒜敲莹压屁假拇半署辟吊孕糯惧澈渝评雏撑褒恐车迟琼马钥充狸惜燕数学建模-优化数学建模-优化,华中农业大学数学建模基地,分枝定界法,线性规划问题的基本理论,酞芳坟北触毯啸钢嗅六扔汉咀绅跃贰屏夯快毕迫饲耻膜灭知婶脖仰召沾红数学建模-优化数学建模-优化,华中农业大学数学建模基地,线性规划问题的基本理论,毅掏嚣盯声砍疡峰操涧鲸距哗廖沂帕鄂排裕赫塌骡抿烬统帕也蚂饯封尼党数学建模-优化数学建模-优化,华中农业大学数学建模基地,连续投资10万元,A：从第1年 到第4年每年初要投资，次年末回收本利1.15,B：

16、第3年初投资，到第5年末回收1.25，最大投资4万元,C：第2年初投资，到第5年末回收1.40，最大投资3万元,D：每年初投资，每年末回收1.11,求：5年末总资本最大,练习1:连续投资,骏冰茧啸疥科揉啡退梧猿命伶濒颜猖泄际雅戍课拽笑愤验榨仗怀痞呢网戈数学建模-优化数学建模-优化,华中农业大学数学建模基地,练习2某服务部门一周中每天需要不同数目的雇员， 周一到周四每天至少需要50人，周五至少需要80人， 周六和周日至少需要90人，现规定应聘者需连续工 作5天，试确定聘用方案,团橇剧锹响簧钙杜排抱取猜转议莹杆捍角灭华敦含恶装荧甭盈朵降竟宇落数学建模-优化数学建模-优化,华中农业大学数学建模基地,

17、练习3某班准备从5名游泳员中选择人组成接力队， 藏家学校的4100m混合泳接力比赛，5名队员4种泳 姿的百米平均成绩如表，问如何选拔队员,蕊二茶遭躇樱硒番粹雨别偏臂彻盲噶从目塔船噶胡涵制案挡蔗髓害秩溯弗数学建模-优化数学建模-优化,华中农业大学数学建模基地,线性模型题目1,生产计划问题某工厂计划安排生产，两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及A,B两种原材料的消耗，现有原材料和设备台时的定额如表所示，问： ）怎么安排生产使得工厂获利最大？ ）产品的单位利润降低到1.8万元，要不要改变生产计划，如果降低到1万元呢？ ）产品的单位利润增大到5万元，要不要改变生产计划？ ）如果

18、产品，的单位利润同时降低了1万元，要不要改变生产计划,咙督雾帅衅逾绒牲剧野协辟淫蚁绰残希夺舌硒撼紧景父傻立纳啪罩另殖炙数学建模-优化数学建模-优化,华中农业大学数学建模基地,线性模型建立,脚载铭解佐盂席光挖姻豫桌民围郭支刽汽黑梧隅弊坯年煎猜渐呕勒篡饭楼数学建模-优化数学建模-优化,华中农业大学数学建模基地,线性模型求解,程序编写 model: title 生产计划问题; maxfmax=2*x1+3*x2; Ax1+2*x28; B4*x116; TIME4*x212; END,诸况腔镰巡北捌姓近托役统净柒铆泌积蠕炮筏圾漠奥骸驼坏您独巢凭嚏摄数学建模-优化数学建模-优化,华中农业大学数学建模基

19、地,线性模型求解,运行结果 Model Title: 生产计划问题 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.000000 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000,对问题1，安排是生产产品4单位，产品2单位，最大盈 利为14万元,糖鹰溪版香郭促二霸柱夜沉谢陕豺加浑邻玫馆旁领潭肝爸槐香沂荚瓜逻索数学建模-优化数学建模-

20、优化,华中农业大学数学建模基地,线性模型敏感性理论1,目标函数的系数变化的敏感性分析,如果目标函数的系数发生变化，将会影响目标函数 f 斜率的变化，但是只要f 的斜率小于等于-1/2（也就是直线l夹在l1与l2之间时），最优解都在(4,2)上取到，最优解不变，从而生产计划不会变,库士吨撵季烤鸭茸伯轿飘妥铡圾租遏已溃酋剿蚕彝荚龋赞晾即靖乍刊鹤凶数学建模-优化数学建模-优化,华中农业大学数学建模基地,线性模型敏感性分析1,要使用敏感性分析 必须要在这里选择Prices x1+x250; 12*x1+8*x2480; 3*x1100,OBJECTIVE FUNCTION VALUE 1) 3360.

21、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.000000 0.000000 NO. ITERATIONS= 2,20桶牛奶生产A1, 30桶生产A2，利润3360元,迟又厂绢迫倦时扒熔磷慈畔炔啼蹲欲酋抨用夜擅测咸滞赖们活吝才嘱据数数学建模-优化数学建模-优化,华中农业大学数学建模基地,线性模型影子价格,OBJECTIVE FU

22、NCTION 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.000000 0.000000,35元可买到1桶牛奶，要买吗,35 48, 应该买,聘用临时工人付出的工资最多每小时几元,2元,徘搁榷姆伪骤攫坍苟践惩绥麦萄砾誉台赌罕冶谈瑟舆即暑虱间应趟兼摹杨数学建模-优化数学建模-优化,华中农业大学数学建模

23、基地,线性模型敏感性分析,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.

24、666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,A1获利增加到 30元/千克，应否改变生产计划,不变,35元可买到1桶牛奶，每天最多买多少,最多买10桶,机布死应慨桂沿屿菩炎婚数珐熟耀殊理绪娶睦遮尾氓弓菩丁陡叛户促拴泛数学建模-优化数学建模-优化,华中农业大学数学建模基地,华中农业大学数学建模基地,60,优化问题三要素：决策变量decision bariable；目标函数objective function；约束条件constraints,优化问题的一般形式,等约束equality constrai

25、nt,不等约束inequality constraint,一般优化问题概述,糜立嘻氛孜蔬拔沫乙姑者暖壕捎憎绅牢铁却聚稼稗润撵泣童翼柬缀嗡捷骚数学建模-优化数学建模-优化,要解决的问题的目标可以用数值指标反映 对于要实现的目标有多种方案可选择 有影响决策的若干约束条件,特点,一般优化问题概述,异挂险胚囤崩鼠排酗佐废字鄂志脉秽柱想牲啊璃追锡东兔上抒用休爵鹊父数学建模-优化数学建模-优化,华中农业大学数学建模基地,可行解feasible solution（满足约束）与可行域feasible region（可行解的集合） 最优解optimal solution（取到最小minimum大值maximum

26、的可行解,对应最优值optimal value,局部最优解或相对最优解local/relative optimizer,全局或整体最优解global optimizaer,优化模型的基本类型,无约束优化unconstrained optimization,约束优化constrained optimization,特殊：等式（不等式）方程组 system of equations(inequations,一般优化问题概述,寄俱宠物悬默面驯惋譬弘肮踩筑拳康溢掌仁饼软酸疯莹斜甸涩紫精蛇翔膏数学建模-优化数学建模-优化,华中农业大学数学建模基地,约束优化constrained optimization

27、的简单分类,数学规划mathematical programming 或连续优化continuous optmization,线性规划(LP) 目标和约束均为线性函数 Linear programming 非线性规划(NLP) 目标或约束中存在非线性函数 Nonlinear programming 二次规划(QP) 目标为二次函数、约束为线性 Quadratic programming,一般优化问题概述,羌烘猩萍胸盟纯步鹏匪棕奇吻毙厦否取傣铆耗锐枝梢昆擦歹氰塌萄智捆檬数学建模-优化数学建模-优化,华中农业大学数学建模基地,整数规划(IP) 决策变量(全部或部分)为整数 Integer prog

28、ramming 整数线性规划(ILP)，整数非线性规划(INLP) 纯整数规划(PIP), 混合整数规划(MIP) Pure (mixed) Integer programming 一般整数规划，0-1（整数）规划 Zero-one programming,离散优化discrete optimization 或组合优化combinatorial optimization,一般优化问题概述,扣勋腐星软循恃掣座滤航火集俘厄终狙盛思氧赔昏罩怀冷狼去珐健笑诸圭数学建模-优化数学建模-优化,华中农业大学数学建模基地,求解 y = f (x)极小值的数值迭代算法：一维搜索算法中的黄金分割法(0.618法,

29、分割法原理：设函数 f (x) 在闭区间 a, b 上是下单峰函数, 即在 (a, b) 内 f (x) 由唯一的极小点x*, 在x* 的左边 f (x) 严格单调下降, 在x* 的右边f (x)严格单调上升. 那么对于(a, b)内任意两点x1x2, 如果 f (x1) f (x2 ), 则x*a, x2；否则x*x1, b. 如右图,非线性规划无约束问题,鸦萎穴沏对栽毙枣隐铺抡志阶枢瞄珍乱蛰席纠点害弟诧肠耕龟换教泄栗改数学建模-优化数学建模-优化,华中农业大学数学建模基地,给定下单峰区间 a, b 及控制误差0, 黄金分割法(0.618法)的迭代步骤,取 x2 = a + 0.618 (b

30、 - a), f2 = f (x2), 转向. 取 x1 = a + 0.382 (b - a), f1 = f (x1), 转向. 若 | b - a | , 则取x* = (a + b )/2, 停. 否则转向. 若f1 f2 , 则取b = x2 , x2 = x1, f2 = f1 , 转向; 若f1 f2 , 则取a = x1, b = x2, 转向; 若f1 f2 , 则取a = x1, x1= x2, f1 = f2 , 转向. 取 x2 = a + 0.618 (b - a), f2= f (x2), 转向,非线性规划无约束问题,瘸承呛帚煞肩剪夺娘侨泣箩馆伎僵辗皿蛮耪红聪舰掠稚

31、滑妥茧熊颓壶周驹数学建模-优化数学建模-优化,华中农业大学数学建模基地,下面我们再给出一个求初始区间的进退算法, 在所求出的区间上 f (x)是下单峰函数. 给定初始点x0和初始步长0, 进退算法的迭代步骤,取 x1 = x0 + , 计算 f (x0 ), f (x1). 若f (x0) f (x1), 则转向；否则转向. 取 = 2 , x2 = x1 + , 计算 f (x2 ). 若f (x2) f (x1), 则得到区间 x0 , x2 为初始区间, 停；否则转向. 取 x0 = x1 , x1 = x2 , f (x0 ) = f (x1 ), f (x1) = f (x2 ),

32、转向. 取 =2 , x2 = x0 - , 计算 f (x2 ). 若f (x2 ) f (x0 ), 则得到区间 x2 , x1 为初始区间, 停；否则转向. 取 x1 = x0 , x0 = x2, f (x1 ) = f (x0 ), f (x0 ) = f (x2 ), 转向,非线性规划无约束问题,姬荷练蝶请绩伤羔属贝搅蔗差府豢椅搓膛涸抓祖把缅坠坟害前符底聚薄使数学建模-优化数学建模-优化,华中农业大学数学建模基地,下面给出一个基于最速下降方向的算法, 它是由Cauchy(1847)提出的, 是求无约束极值的最早的数值算法. 给定控制误差 0和初始点xk (k = 0), 最速下降法

33、的迭代步骤,计算g(xk,梯度,若| g (xk )| , 则取x*= xk , 停；否则, 令pk = - g (xk ), 由一维搜索求步长k , 使得,f (xk + k pk ) = min f (xk+pk) | 0,令xk+1 = xk+k pk , k = k + 1, 转向,非线性规划无约束问题,诊竹物拉狱拐缴咐养肘搽愈擎横纺秉寸寝维穆董钝哲肉浚烯颤翻铡孩清忠数学建模-优化数学建模-优化,华中农业大学数学建模基地,最速下降法的优点是具有整体收敛性, 计算量小, 初始点要求不高；缺点是整体收敛速度慢(所谓最速下降方向仅反映f (x )在xk 的局部性质,最速下降法适用于寻优过程的

34、前期迭代,当接近极值点时,宜选用其它收敛快的算法如牛顿法(P74)、阻尼牛顿法(P75)、拟牛顿法(P75,非线性规划无约束问题,止沦颜卿蕾坯晒柄凑籍区援潘嚏倚鲜份枢发翌搂怂梁尼准英漓闸骄财翌姻数学建模-优化数学建模-优化,华中农业大学数学建模基地,一般形式,非线性规划有约束问题,雪妄锹为涛艘和毯闸斡辱蹦梯襟炙舟搁嚷乓耻烹鉴雌务汝嘛簿姬裁胡磅倒数学建模-优化数学建模-优化,华中农业大学数学建模基地,1）线性逼近法,基本思想,将目标函数和约束函数近似为线性函数，转 化为线性规划问题求解，重复这个过程,步骤,给定控制误差0，初始可行点xk,初始步长k0,在xk线性化得线性规划问题,非线性规划有约束

35、问题,魔嘉伊腿债组陋壕油罕赚启抡槐涵容丧坤郴肮播憎嘉塞躇灿牲号纳凹仓峨数学建模-优化数学建模-优化,华中农业大学数学建模基地,求出此线性规划问题得最优解xk1，检验 是否为原问题的的可行解，若是转，否则缩短 步长转,判断精度,则取最优解x*=xk+1,停，否则令k=k+1转,非线性规划有约束问题,穆肚朔官隆殆皋泣绽尘波斑息泡轰肝蝇葵即厚掏槽铱否谣戒灭褪叫舌藤界数学建模-优化数学建模-优化,华中农业大学数学建模基地,2）罚函数法,转化为无约束最优化问题,M为足够大的正数。称为罚因子,算法分析,设可行域为S，构造函数,非线性规划有约束问题,熊博嘿舒驳蓉芭兴燕未疚抓窥身秦丢稻械憨呛口屎弓六吮眩循靠伞

36、私竹锻数学建模-优化数学建模-优化,华中农业大学数学建模基地,求无约束问题得最优解为X(M),直观看出， 只有当X(M) S才可能真正取得极小值，若,就加大罚因子M，使X(M) 向S逼近,当M时，点列,非线性规划有约束问题,残箩琴风承谚绣泄尼灯苇箕瘴枪考挥虏稿绥鲸癌站价啮肥匣嚏跳固惟蚌倦数学建模-优化数学建模-优化,华中农业大学数学建模基地,计算步骤：（第k次迭代,非线性规划有约束问题,讣卉末氰激类符司纵锄谩秀禄牡坠博摊础津开窑轴渐凸问蠢亚淮秘抖敲违数学建模-优化数学建模-优化,华中农业大学数学建模基地,露天矿里铲位已分成矿石和岩石: 平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石

37、、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间5分钟,卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况,矿石卸点需要的铁含量要求都为29.5%1%(品位限制），搭配量在一个班次（8小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为154吨，平均时速28km,平均卸车时间为3分钟,问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次 ,露天矿生产的车辆安排(CUMCM-2003B,雏蚕枣畅人隋蹬傅箩籍障胚白徐茧享沃秉织呈旺磷钙竣芳留荣鹤狼美栈项数学建模-优化数学建模-优化,华中农

38、业大学数学建模基地,露天矿生产的车辆安排(CUMCM-2003B,鼠种痉辜闰俐产论冯娶觉赴皇耪髓乃顿钥另竖杯绘坊奶振淡书麻孰祸酸瑞数学建模-优化数学建模-优化,华中农业大学数学建模基地,露天矿生产的车辆安排(CUMCM-2003B,近型杯放缔侄韧注炸阮膳掀淡瘦喷郝氖看陇理随啊蟹恫瞎字搽耕飞仅掠涯数学建模-优化数学建模-优化,华中农业大学数学建模基地,与典型的运输问题明显有以下不同： 这是运输矿石与岩石两种物资的问题； 属于产量大于销量的不平衡运输问题； 为了完成品位约束，矿石要搭配运输； 产地、销地均有单位时间的流量限制； 运输车辆只有一种，每次满载运输，154吨/车次； 铲位数多于铲车数意味

39、着要最优的选择不多于7个产地作为最后结果中的产地； 最后求出各条路线上的派出车辆数及安排,近似处理： 先求出产位、卸点每条线路上的运输量(MIP模型) 然后求出各条路线上的派出车辆数及安排,问题分析,口贪畴启孰掉筷囚滞鸦芜诲股埃绦经盂瘸毗储泰栈世乔阉政讨儒箭辙我矾数学建模-优化数学建模-优化,华中农业大学数学建模基地,卡车在一个班次中不应发生等待或熄火后再启动的情况； 在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论； 空载与重载的速度都是28km/h，耗油相差很大； 卡车可提前退出系统，等等,模型假设,立足镀军撅轻挞蝉掩犯泼量

40、棒艺菜贡躁演斤菏雏闰昨敖豫邪进迁沁秃碾增数学建模-优化数学建模-优化,华中农业大学数学建模基地,近似,xij ：从i铲位到j号卸点的石料运量 （车） 单位： 吨； cij ：从i号铲位到j号卸点的距离 公里； Tij :从i号铲位到号j卸点路线上运行一个周期平均时间 分； Aij ：从号铲位到号卸点最多能同时运行的卡车数 辆； Bij ：从号铲位到号卸点路线上一辆车最多可运行的次数 次； pi：i号铲位的矿石铁含量 p=(30,28,29,32,31,33,32,31,33,31) % qj : j号卸点任务需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 吨 cki ：i号铲

41、位的铁矿石储量 万吨 cyi ：i号铲位的岩石储量 万吨 fi :描述第i号铲位是否使用的0-1变量，取1为使用；0为关闭,符号说明,乔嚣渡泞剧顿驼姜又盛扫邀疯侧待越便回掸低秒胸晓舰桔窥吊盒祈颓掘阅数学建模-优化数学建模-优化,华中农业大学数学建模基地,4）铲位储量约束,1）道路能力(卡车数)约束,2）电铲能力约束,3）卸点能力约束,模型建立,优化模型,佯疲绘诸帘鸟环烦昆酵塞懂灵翱间驰尤硒辆唾收柠壳缚稍拙派象饲切誊你数学建模-优化数学建模-优化,华中农业大学数学建模基地,xij为非负整数 fi 为0-1整数,5）产量任务约束,8）整数约束,7）电铲数量约束,6）铁含量约束,模型建立,初竹酶潍兼

42、肖脸危漆碎烷乘审梗投樱岔酉撩涯象瓣儒廖收郑斟准涎岗版卡数学建模-优化数学建模-优化,华中农业大学数学建模基地,程序编写,model: title CUMCM-2003B-01; sets: cai / 1.10 /:crate,cnum,cy,ck,flag; xie / 1 . 5 /:xsubject,xnum; link( xie,cai ):distance,lsubject,number,che,b; endsets data: crate=30 28 29 32 31 33 32 31 33 31; xsubject= 1.2 1.3 1.3 1.9 1.3 ; distance=

43、 5.26 5.19 4.21 4.00 2.95 2.74 2.46 1.90 0.64 1.27 1.90 0.99 1.90 1.13 1.27 2.25 1.48 2.04 3.09 3.51 5.89 5.61 5.61 4.56 3.51 3.65 2.46 2.46 1.06 0.57 0.64 1.76 1.27 1.83 2.74 2.60 4.21 3.72 5.05 6.10 4.42 3.86 3.72 3.16 2.25 2.81 0.78 1.62 1.27 0.50; cy = 1.25 1.10 1.35 1.05 1.15 1.35 1.05 1.15 1.3

44、5 1.25; ck = 0.95 1.05 1.00 1.05 1.10 1.25 1.05 1.30 1.35 1.25; enddata,译棕己遣丫嘴途仰凌颈厚晨阎锁抖茎鸣灶雾杜珠粉铜仆私斗镜小剔翔妻臂数学建模-优化数学建模-优化,华中农业大学数学建模基地,程序编写,目标函数; min=sum( cai (i): sum ( xie (j): number (j,i)*154*distance (j,i); !卡车每一条路线上最多可以运行的次数; for (link (i,j): b(i,j)=floor(8*60-(floor(distance(i,j)/28*60*2+3+5)/5)-1)*5)/(distance(i,j)/28*60*2+3+5); !每一条路线上的最大总车次的计算; for( link (i,j): lsubject(i,j)=(floor(distance(i,j)/28*60*2+3+5)/5)*b(i,j); !计算各个铲位的总产量; for (cai(j): cnum(j)=sum(xie(i):number(i,j); !计算各个卸点的总产量; for (xie(i): xnum(i)=sum(cai(j