多目标规划MALAB年wgx

MATLAB求解多目标规划江西师范大学数信学院吴根秀一、0-1规划的MATLAB求解数学模型：MINf’xS.T.Ax<=bAeqx=beqx=0,1命令格式：x=bintprog(f)x=bintprog(f,A,b)x=bintprog(f,A,b,Aeq,beq)x=bintprog(f,A,b,Aeq,beq,x0)x=bintprog(f,A,b,Aeq,beq,x0,options)[x,fval]=bintprog(...)[x,fval,exitflag]=bintprog(...)[x,fval,exitflag,output]=bintprog(...)数学模型：MINlambdaS.T.F(x)-weight*lambda<=goal(达到目标）Ax<=b（线性不等式约束）Aeqx=beq（线性等式约束）C(x)<=0（非线性不等式约束）Ceq(x)=0（非线性等式约束）lb<=x<=ubF=[f1(x),f2(x),…]为多目标的目标函数；F与[C(x),Ceq(x)]都是通过function来定义；命令格式：x=fgoalattain(fun,x0,goal,weight)x=fgoalattain(fun,x0,goal,weight,A,b)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq)x=fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub)二、多目标规划的MATLAB求解命籍令似格沟式孤：x哭=衔f称g热o情a吨l朋a斥t量t坏a犁i版n鸣(各f骆u提n余,宅x编0肺,到g慨o辩a外l身,吨w兆e滋i赠g挤h禁t资)x拣=陈f翁g漂o馒a罚l已a占t苗t瓜a怀i稀n也(芦f脆u叔n礼,既x猛0锄,吹g追o增a垃l渠,寒w虎e均i学g陈h鲜t叮,裕A糠,证b父)x养=灵f方g敬o巨a猎l性a书t泪t暮a幻玉i旦n虾(勒f血u息n术,臣x则0太,肢g役o傅a船l水,股w滚e老i醋g成h梦t颗,些A欲,羡b川,当A驴e它q世,吹b熟e谋q良)x厘=盯f踏g勤o贴a厉l超a志t悬t见a绝i汗n绝(拢f爹u隆n汽,情x题0饶,悔g铲o储a催l储,故w碑e锻i截g猫h怀t脆,被A农,绞b窗,储A绘e支q药,月b楼e报q颠,富l宁b秀,长u样b心)x丸=务f厉g滑o圣a伶l捐a元t抱t渴a依i待n荡(糖f闲u跪n年,仗x漏0罗,字g纪o馆a帐l你,连w时e射i此g西h环t扁,恢A盖,缴b刮,藏A洪e爷q姨,登b象e如q优,暖l辆b宁,邻u嫩b比,春n喷o奋n政l僚c销o垂n傍)x碎=滤f储g摧o悉a读l颂a魂t称t称a士i漫n枝(番f清u辆n烧,慰x错0离,围g朵o奇a迫l技,船w漏e眉i看g拿h灭t胜,胸A怜,雷b适,茫A刑e怪q回,吹b讨e责q鼓,蛙.摄.尼.l驱b窃,安u步b淡,乐n乎o男n锯l蹄c吵o富n本,碰o妻p肥t镜i送o抛n戴s免)[师x术,支f荐v益a美l码]父=匙f修g识o柏a艰l摄a默t兰t热a谎i登n驴(痰.眠.浇.稿)[乡丰x慰,宫f恰v未a澡l算,易a肠t喊t议a粗i闯n小f赠a惊c魄t糖o第r并]默=扬f绸g贝o贡a粪l宗a奇t懂t邪a势i会n志(米.驼.咳.绘)[病x锣,乖f赛v养a在l所,故a零t克t津a状i忆n江f腔a纸c幻玉t厌o惠r塘,度e巴x蕉i昨t缝f私l根a王g愚]筒=顺f黄g期o膀a培l些a她t剖t想a士i犯n缸(烟.揭.见.扮)[致x长,字f符v己a鹿l徐,诞a心t劝t留a筐i比n名f惨a标c刺t刚o迅r挎,束e梨x耕i换t灵f帐l享a引g黑,智o剧u苗t五p吉u程t光]吼=镜f穴g笑o君a稳l弟a永t疲t鱼a寒i裹n袍(魂.肠.挖.皂)[夫x桑,狡f贤v罩a齐l家,眼a自t两t幻玉a临i细n谱f匪a销c眯t妙o性r翻,饰e痕x眠i纳t响f微l枝a努g衰,鲁o乳u埋t卡p虽u粉t镇,仓l赢a变m险b海d林a柔]汁=恨f砖g尖o发a号l包a梅t斧t清a的i予n沟(目.买.输.翼)二、多刚目测标撕规案划话的M周A侄T烫L遣A深B求掉解x盾=苦f虎g去o愚a扔l翠a絮t直t获a溜i送n与(搁@塔m损y攻f冤u扯n外,颜x爽0供,界g概o厦a京l题,电w陶e枣i穿g论h拘t愿,计A铅,朗b考,此A坛e贱q采,担b落e械q依,统.牢.渐.l聪b筑,羡u晨b镜,钟@慎m次y互c陵o遍n拉)w剩h偶e托r失e架m报y向c短o新n毁i脑s寻a贺M终A岩T徒L煎A判B步f策u盛n舰c盟t赠i箭o既n蒙s层u却c升h坏a腾sf泡u滥n宽c河t衡i笨o殖n椒[嫩c督,恨c鄙e巡寿q曲]助=肝m脖y恒c琴o其n中(永x耻)c羽=泉.招.衣.尾%垃c误o染m甲p响u牵t喝e著n剑o斧n缘瑞l婚i放n价e伤a烟r价i坦n穿e胶q远u附a炮l族i粒t蚀i糕e享s妖a行t涌x梯.c牙e瓣q染=幸.相.奔.农%晶c僻o上m场p昨u境t袋e昌n望o神n液l稻i嚼n滋e那a装r线e哗q机u塞a使l棋i焰t迅i充e粪s绝a疮t二、多掩目僚标径规隔划亡的M注A奸T震L腐A达B求衡解x思=挂f遣g漏o拿a壤l贺a持t崭t桥a蜂i垄n卖(翠@顾m违y钟f丽u振n吹,境x葬0箭,破g铃o项a笼l心,乞w活e寻i绘g类h睬t祸)w纯h顿e阴r秋e忧m租y钟f有u稠n曲i刷s康a制M类A认T亦L娇A候B喊f合u针n庄c上t侨i葡o信n忠s仍u燃c敢h摆a闻sf蕉u源n婶c热t壳i凭o锯n脏F慰=法m阵y乏f定u叠n折(撕x慢)F真=岸.侵.候.询%疮C清o惰m浓p腐u关t到e阔f灶u判n挽c珍t挥i继o拥n煌v支a读l走u花e枪s旁a初t踏x彩.有却关爷优宣化治参矛数锐设宗置址：o职p打t哭i才o聋n撒s涝=帐o先p吨t银i戒m亿s估e违t慕(态‘抹G纵r素a霜d信O息b铺j道’润,替‘任o虹n食’蓄)目退标善函厚数汉的匠梯衰度床方胁向尖参库数爪设挑置劝为‘阶o副n罢’时腔，墙用放下具列民函纷数捷定圈义腾：f击u槐n忽c训t券i啦o绑n谁[择F殿,宰G鲜]拨=创m醒y次f肌u途n卵(穿x押)F估=猪.腾.浊.坊%哑C境o爪m抗p写u霜t功e霜t鸭h甜e境f丝式u国n认c床t往i眉o共n能v零a相l姻u长e鲜s莫a胞t辨xi晓f勾n垮a扎r磁g津o眨u年t爸>伤1席%删T珍w员o柱o终u敌t造p蹲u带t虫a狮r料g女u捞m抓e楼n晴t婚sG医=烛.配.苗.功%巴G见r假a族d仿i益e爱n辱t泛s唇e燥v占a凑l否u尘a孩t价e对d塌a岁t绵xE廊n羊dT哈h姐e灵g米r娃a境d表i袖e阁n正t撇c罪o纲n懒s深i译s约t携s气o搜f旱t特h拘e截p睛a堂r辨t台i秘a晌l六d管e傅r都i掀v翅a盆t狸i遣v皆e涌d博F之/期d似x浮o妹f她e架a害c筑h莲F判a瓶t凑t睛h讨e肢p纹o缓i膏n妈t方x弊.二、多莲目洋标锹规贴划芦的M盒A妈T糠L消A娱B求辱解二、多怒目坟标伸规堪划节的M持A革T罚L厘A篮B求欢解有趁关身优匹化陡参追数美设闭置万：o诊p咱t茅i写o牢n篇s步=饮o爬p听t匙i协m皆s洗e鼓t爪(走‘心G予r煌a喉d桂C何o拼n昏s谨t宿r贺’兼,祥‘械o化n绿’）责约办束语条渴件灭的泉梯准度绘方柳向有参怒数您设岂置撞为‘陈o泄n嘱’时浮，箭用思下维列跪函棕数颜定砖义湿：f碎u英n序c杨t恋i蜡o固n酒[诞c舰,铁c论e玻q晓,冬G气C瓦,节G饭C怨e爸q旧]故=兄m叉y穗c秆o掩n薪(希x狼)c嫁=信.颜.咬.卵%点N去o刷n暑l仆i必n给e离a叨r归i戒n招e晃q搏u聪a醉l烟i纳t钉i咐e扁s题a酒t怪xc躲e休q宿=姓.启.仪.汽%聋N仰o违n语l淡i朵n匪e勇a咱r衔e额q夜u多a凳l眉i直t攻i械e龟s章a鸭t紫xi老f语n液a墨r府g佩o稿u砍t弯>职2蜻%糖N庄o固n蹈l倡c土o帜n分c德a绕l离l谨e球d祝w唯i鼓t揭h品4趴o伸u扛t胜p禁u平t蛙sG滑C贱=汪.舒.鄙.敲%绘G淋r监a剩d棕i将e原n伙t朝s者o装f喇t咳h棕e疏i效n鱼e厦q捡u梳a浙l屿i面t鹅i耽e细sG如C讽e膝q网=劫.岭.险.销%夜G兰r联a丈d拿i伍e奖n厦t粉s射o贺f惩t钳h钢e留e透q临u篮a么l已i公t续i英e窜sE蛋n猛d注吓意初：抵一祸般w野e包i枪g完h傅t脂=术a舱b浑s蠢(械g腥o山a含l偏)模栗型笼：x胡’溪=瞎(进A径+乔B跨K俭C唯)沸x营+洁B模u，猛设介计K满吉足剧目它标仰：Y煌=倾C奶x1）舞循锐环饮系必统垦的水特泄征抽值畏（邮由享命食令e惹i午g御(晓A抚+旬B省*任K渡*倡C榆)确庆定速）牺的顽目蹄标师为g绵o花a昏l咬=饱[乐-庙5后,瓣-淡3伯,骨-裂1凑]2）K中趁元砍素订均吐在[妈-泉4好,袖4烈]中;设仰特焦征很值荣的w耐e冤i衡g奏h楼t溜=责a浆b始s召(迅g僵o星a香l发)惧,定渔义统目即标参函阻数F如片下哗：f刑u刚n技c寸t巨i降o救n习F颂=耐e走i值g忧f怪u夹n宿(帆K锅,槽A蜻,艘B顾,返C疤)F租=步s养o辞r黄t佛(踢e谊i馅g姓(续A锄+过B姓*番K勤*绸C售)屋)弯;往%配E仁v闯a听l著u晶a上t候e松o克b赶j狼e饺c耻t芳i瓦v缸e厕s，奋由临小索到番大巩排拍列优巷化套程近序洗为茄：A识=赶[邪-承0手.妻5掌0俱0散;歼0龙-小2源1借0召;痰0照1垃-宋2雁]晓;哀B制=遣[乱1其0授;设-屿2弃2勒;仪0凝1紫]侍;C侮=秃[赛1师0宴0坝;幼0召0枪1杆]炒;夕K犁0冬=破[暖-为1露-疯1逆;腐-胳1绿-照1祸]盏;山%抵I乏n苏i奋t访i邀a门l阴i姜z身e寺c胖o段n扁t选r列o邻l吃l薄e纺r及m流a伤t洁r距i挨xg蹲o板a晕l惰=拒[臣-产5泡-呜3较-脑1川]捏;中%宗S戏e目t章g更o乡丰a轻l圣v赏a谢l料u签e目s画f宁o肃r幻玉t毯h惩e霉e片i蒸g页e逝n旧v倍a邮l俯u页e码sw惊e盐i泄g拢h妙t锐=钩a定b需s给(荷g其o桨a休l混)由%未S漠e仪t坑w吗e篮i首g衰h柴t说f怀o和r坊s捏a渴m求e萝p巩e缝r爪c秆e烂n桑t部a丹g胳el达b蠢=党-短4酸*巩o膊n帮e业s歼(冷s添i达z富e与(旬K荐0手)森)霞;敏%把S骂e颈t很l摊o拥w柏e墓r续b刚o奋u汉n拿d皮s匙o台n盒t阿h招e呈c央o畏n坡t猫r显o绿l咐l悄e似ru房诚b黑=骑4喝*染o血n图e锄s系(潜s溉i娱z蜂e萍(虾K剩0叨)文)炼;纠%董S忍e复t裹u磨p朴p逗e蔑r两b好o愤u林n赵d栗s弄o铺n罗t窑h嗽e升c奥o削n虫t角r据o乎l脆l战e颈ro仙p济t衬i业o秤n撕s开=撤o仗p格t竭i缝m枯s良e抱t徐(修'岛D内i切s京p亦l榴a闸y秩'尤,蝇'治i令t只e幻玉r匹'华)尖;甘%笨S水e绑t倡d告i旱s吃p泊l撑a壤y贿p亿a申r哲a挣m旅e碧t腊e劲r[栋K艳,齐f喜v远a盏l例,堂a解t隐t丙a狮i捏n裕f倾a陡c华t踢o和r祖]责=岂f坡g燥o督a紫l痒a廉t伙t枣a赤i之n带(炎@离(眨K忆)蓬e央i湿g为f朋u躺n瘦(椒K柏,汪A蒙,疼B香,果C乳)搁.汉.张.g稻o壳a督l顽,崭w傅e银i扒g零h誓t胳,事[麦]活,蔑[史]握,士[蚂]飞,饰[贡]绸,陪l膏b拦,士u庸b猜,抄[胀]筹,畏o骑p仇t国i蹄o谢n球s碧)二、举眼例-抄-页-有卵关傻循性环制控闻制歉系煤统硬优穗化岸问鹊题运雹行龙结嘴果舱如像下A贷c要t胞i昼v友e贞c买o仍n级s政t牙r羞a述i蹄n璃t繁s扬:12491申0K足=-姨4宿.仰0金0喜0执0座-寨0凝.东2径5镇6迎4-迫4漂.将0跨0家0倚0义-棕4首.穴0迈0斥0堂0f迹v转a畜l大=-象6垃.戒9答3言1浸3-酒4援.娃1享5倍8渐8-捷1筋.准4吩0生9典9a威t愚t高a汪i讯n耽f帆a浓c除t责o圣r馅=-番0据.心3始8挖6婚3二、举栏例-象-途-有隔关堆循萍环烈控瓦制侄系登统气优植化鹿问蛋题如面果此至暑少肺保暂证3猾8杂.虹6约3名%的秩目巨标搭精印确社匹锁配讯，厉设雄置‘裕G江o湾a叮l破s颗E背x疼a材c脊t在A匹c碰h效i欠e族v仅e做’参蛮数锐值制为3o脏p赠t治i政o咏n纯s射=备o屈p壮t旁i笛m此s这e表t欢(槽'岭G缠o拦a们l蔽s衣E木x光a漫c浅t桂A戴c骆h朝i伐e走v交e痛'惨,讨3跃)躺;[蜡K垂,丙f士v馋a浓l孕,瞒a敏t沸t客a值i吸n捞f千a忠c尤t老o去r阴]回=僵f樱g纽奉o趋a吩l首a课t佳t照a落i独n因(创.哪.便.@吉(相K壤)伸e辨i颂g张f变u贪n袜(根K某,差A田,素B针,鸟C宜)愈,云K恰0级,舒g忌o义a砍l炮,水w演e飘i纤g爽h问t迫,社[陆]辰,者[牙]集,弟[革]吵,乖[矮]洁,骆l细b临,牢u顷b芹,额[疮]乏,慕.饿.梢.足o度p包t坐i荣o组n砍s舅)A帖f依t长e邪r粪a键b侨o肃u怎t身s纽奉e煎v偶e押n那i警t诞e惰r宽a紧t否i特o践n概s熟,神a办s献o傍l颂u勤t冠i再o神n或i驾sK核=-便1库.戴5呈9抬5索4缘瑞1敌.齐2仅0新4膀0-闭0侦.创4孩2管0物1芝-棵2炼.屡9饲0境4监6f事v蓄a璃l躁=-切5声.刺0危0晓0捡0-榨3详.天0钥0为0为0-戏1哨.府0住0缺0裂0a替t详t悔a亚i雕n朵f涂a状c践t兵o朗r袭=1勾.洁0设8此5挤9其e套-垫2笨0表炸明点目含标相已殖完高全腾匹序配二、举展例-调-银-有蹄关荡循驳环洋控湾制怖系莲统影优械化撒问走题谢掠谢欧！初讨等躬模智型洁举泥例常阻见糕类胸型定案性渠模脱型经卫验论公雀式剂（雀拟淹合兄、笋插认值意）量绢纲垄分撕析比难例造模桨型§辆2礼.虾1崖转高读的哭估位算假旁如饱你要站曲在孤崖麦顶旁且愉身雅上摸带哥着泽一举只柜具美有打跑远表糟功能灵的怒计稍算子器缓，塌你晌也桐许颠会岩出级于蕉好弹奇汪心疾想暖用眯扔坦下一广块外石既头尘听防回齿声羊的悬方冰法扰来乞估猜计肉山晚崖首的弱高阿度挽，假弟定层你熔能暗准击确疼地哲测辞定惹时沫间向，细你拥又幸怎滚样卵来左推猫算山穗崖泼的琴高喂度碧呢反，注请夺你卷分皂析症一麦下叮这桂一搭问究题萍。我有一只具有跑表功能的计算器。方拘法凡一假定空气阻力不计，可以直接利用自由落体运动的公式来计算。例如，设t=4秒，g=9.81米/秒2，则可求得h≈78.5米。我烤学忌过籍微影积颠分识，薪我平可租以泥做得罗更各好雀，拦呵扬呵垮。除去地球吸引力外，对石块下落影响最大的当属空气阻力。根据流体力学知识，此时可设空气阻力正比于石块下落的速度，阻力系数K为常数，因而，由牛顿第二定律可得：

令k=K/m，解臣得代瞧入美初腔始买条遮件v(屠0否)洪=攀0，雅得c=－g悼/翻k，辨故贵有再义积京分菜一妄次哪，龟得症：若唯设k=持0胖.蝇0择5并烧仍坏设t=燃4秒亿，雷则锈可纱求蒸得h≈7挤3习.速6米雅。听义到菜回寨声环再托按素跑杯表阁，慌计厕算廉得握到衬的休时现间惑中反包保含则了反魔应粮时挺间进具一姜步曲深辞入拍考务虑不删妨袄设平昆均距反湖应番时诞间为0各.猴1秒滑，忠假记如厚仍脑设t=既4秒画，惰扣杯除偶反抗应鸣时炒间初后势应箩为3辛.碌9秒箩，孟代肝入愈式①，尝求精得h≈6溪9阔.挂9米棕。①多海测宜几逗次冲，骄取肺平泊均似值再觉一硬步堡深铲入讯考票虑代入初始条件h(0)=0，得到计算山崖高度的公式：

将e-kt用泰勒公式展开并令k→0+

，即可得出前面不考虑空气阻力时的结果。还应考虑回声传回来所需要的时间。为此，令石块下落的真正时间为t1，声音传回来的时间记为t2，还得解一个方程组：这一方程组是非线性的，求解不太容易，为了估算崖高竟要去解一个非线性主程组似乎不合情理

相对于石块速度，声音速度要快得多，我们可用方法二先求一次

h，令t2=h/340，校正t，求石块下落时间t1≈t-t2将t1代入式①再算一次，得出崖高的近似值。例如，若h=69.9米，则t2≈0.21秒，故t1≈3.69秒，求得h≈62.3米。§缝2谁.梁2录朴像陆带发还爱能博录厘多荡长培时稼间录况像届机膊上泡有柔一坡个改四察位某计别数费器慈，胞一未盘1昂8渡0分历钟的假录伤像渔带旧在栏开梦始拜计群数显时王为0芒0晓0绩0，汽到椒结承束容时软计数寸为1枯8林4匆9，情实腐际谨走烈时缸为1胁8刮5分2肺0秒沙。泥我台们戒从0胜0间8蛙4观伯察恶到0代1头4踪蝶7共贴用旁时肆间3分2渠1秒比。依若挺录默像机洁目增前张的映计店数文为1络4董2辽8，茄问杏是器否摸还告能筋录的下最一灯个6腊0分温钟喊的体节碍目边？rθRl由得到又因和得

积盆分惨得香到即从号而蓝有我们希望建立一个录像带已录像时间t与计数器计数n之间的函数关系。为建立一个正确的模型，首先必须搞清哪些量是常量，哪些量是变量。首先，录像带的厚度W是常量，它被绕在一个半径为r的园盘上，见图。磁带转动中线速度v显然也是常数，否则图象声音必然会失真。此外，计数器的读数n与转过的圈数有关，从而与转过的角度θ成正比。rθRl此式中的三个参数W、v和r均不易精确测得，虽然我们可以从上式解出t与n的函数关系，但效果不佳，故令则可将上式简化为：故令上式又可化简记成t=an2+bn

t迎=绸a仗n2+抽b尤nrθRl上蜜式羞以a、b为邪参执数辣显卵然痛是皂一焦个践十茎分扬明热智某的重做裤法友，费它临为窄公拖式枯的薪最杏终燥确阅立捞即捉参祖数霉求协解脏提树供蜡了朱方拳便兵。坝将赛已说知顺条盗件窑代规入葱，诞得动方胃程尽组丸：从轰后承两触式悔中合消记去t1，艳解程得a昆=0廉.叛0筹0克0帖0湾2删9慌1,b石=0澡.厕0形4石6骗4泰6,故t绿=0临.裕0瞎0胳0励0倒2腔9藏1n2+恳0妙.拘0对4只6医4睬6n，凭令n枯=1打4滑2严8，核得晶到t粗=1鹅2召5腿.巧6巩9（器分雀）非由披于援一哀盒禁录动像晃带坊实区际获可泡录词像灰时甩间纲为1具8播5蹲.证3裙3分呼，炮故腐尚申可尸录甲像盒时侦间报为5蜻9壮.倡6籍4分击，悬已跌不摆能脂再换录插下进一辉个6夜0分嘉钟侄的谨节旱目龙了啊。在解决实际问题时，注意观察和善于想象是十分重要的，观察与想象不仅能发现问题隐含的某些属性，有时还能顺理成章地找到解决实际问题的钥匙。本节的几个例子说明，猜测也是一种想象力。没有合理而又大胆的猜测，很难做出具有创新性的结果。开普勒的三大定律（尤其是后两条）并非一眼就能看出的，它们隐含在行星运动的轨迹之中，隐含在第谷记录下来的一大堆数据之中。历史上这样的例子实在太多了。在获得了一定数量的资料数据后，人们常常会先去猜测某些结果，然后试图去证明它。猜测一经证明就成了定理，而定理一旦插上想象的翅膀，又常常会被推广出许多更为广泛的结果。即使猜测被证明是错误的，结果也决不是一无所获的失败而常常是对问题的更为深入的了解。§2.3最短路径与最速方案问题例5（翁最婚短即路辱径目问等题将）设治有华一盏个池半稼径伞为r的膀圆娱形耽湖围，繁圆惨心故为O。A、B位顺于秩湖顺的宰两魂侧傻，A分B连盯线年过O，闷见挥图仓。现盘拟税从A点崭步群行埋到B点片，酬在黑不罢得爷进方入攻湖蹲中甚的情限制岂下路，陈问优怎川样疾的星路兰径示最念近温。ABOr将湖想象成凸出地面的木桩，在AB间拉一根软线，当线被拉紧时将得到最短路径。根据这样的想象，猜测可以如下得到最短路径：过A作圆的切线切圆于E，过B作圆的切线切圆于F。最短路径为由线段AE、弧EF和线段FB连接而成的连续曲线（根据对称性，AE′，弧E′F′，F′B连接而成的连续曲线也是）。EFE′F′以戚上挖只逆是乡丰一色种嘉猜游测政，奶现岩在嗓来乘证理明深这示一籍猜贿测凳是释正浴确彻的喇。耕为残此吹，口先圾介抽绍庙一号下芹凸丙集蚁与肆凸成集裤的梢性边质骨。定义2.1（凸集）称集合R为凸集，若x1、x2∈R及λ∈[0，1]，总有λx1+（1+λ）x2∈R。即若x1、x2∈R，则x1、x2的连线必整个地落在R中。定理2.2（分离定理）对平面中的凸集R与R外的一点K，存在直线l,l

分离R与K，即R与K分别位于l的两侧（注：对一般的凸集R与R外的一点K，则存在超平面分离R与K），见图。klR下朝面协证需明献猜说想猜尿测嗽证伍明知如番下垒：（方法一）显然，由AE、EF、FB及AE′，E′F′，F′B围成的区域R是一凸集。利用分离定理易证最短径不可能经过R外的点，若不然，设Γ为最短路径，Γ过R外的一点M，则必存在直线l分离M与R，由于路径Γ是连续曲线，由A沿Γ到M，必交l于M1，由M沿Γ到B又必交l于M2。这样，直线段M1M2的长度必小于路径M1MM2的长度，与Γ是A到B的最短路径矛盾，至此，我们已证明最短路径必在凸集R内。不妨设路径经湖的上方到达B点，则弧EF必在路径F上，又直线段AE是由A至E的最短路径，直线FB是由F到B的最短路径，猜测得证。ABOrEFE′F′M1M2MΓl还半可篮用微伸积谊分方锐法喘求挪弧赖长缴，省根剥据归计副算洪证葛明督满进足阻限洞止黎条鼠件呀的复其其他叨连默续捎曲耳线按必迟具凉有纲更雀大出的幸长让度订；蝇此音外个，缝本励猜翻测暑也杜可邪用平控面联几根何知职识堤加株以甩证西明饼等阳。根据猜测不难看出，例5中的条件可以大大放松，可以不必设AB过圆心，甚至可不必设湖是圆形的。例如对下图，我们可断定由A至B的最短路径必为l1与l2之一，其证明也不难类似给出。ABl1l2D到取此搂为渠止汉，犯我淡们殃的温研蜜讨减还杆只污局巧限袖于输平钉面蚂之萝中监，备其细实掩上狗述字猜爸测莫可双十蜘分或自睛然怕地防推叠广马到帝一女般翠空袖间钩中转去朗。1挖9铺7暖3年栋，J同.害W舒.鹿C厘r投a趋g元g醋s证唇明唉了栽以吨上伤结嘉果驻：若可行区域的边界是光滑曲面。则最短路径必由下列弧组成，它们或者是空间中的自然最短曲线，或者是可行区域的边界弧。而且，组成最短路径的各段弧在连接点处必定相切。例6一姓辆杨汽存车酱停餐于A处跪并吴垂罢直鼠于A种B方兵向省，陡此汽王车鸣可挡转闸的汤最翁小呀圆亚半敢径达为R，谁求他不宣倒愿车荣而扩由A到B的潜最羊短背路惩径认。解（情况1）若|AB|>2R，最短路径由弧AC与切线BC组成（见图①

）。（情况2）若|AB|<2R，则最短路径必居于图②（a）、（b）两曲线之中。可以证明，（b）中的曲线ABC更短。AR2RBRC①②ABoC（a）CABo1o2（b）例7驾笑驶兰一葵辆露停省于A处弃与A明B成θ1角切度凤的去汽车磁到B处微去前，傅已题知B处心要岛求剧的洞停属车照方勤向驰必利须与A赞B成θ2角圣，若试逆找测出差最乒短连路爱径迁（抖除颜可退转的诱最萄小予圆词半法径尺为R外份，怪不拜受桌其识他抵限工止寸）怕。解根据Craggs定理并稍加分析可知，最短路径应在l1与l2中，见图，比较l1与l2的长度，即可得到最短路径。Al1l2Bθ2θ1最屿速滤方笔案说问险题例8将狂一捧辆矛急南待子修卖理梳的捧汽握车荐由夫静胶止章开枪始墙沿后一直叶线狸方皆向加推田至骂相限隔S米戚的窄修任车僵处松，旺设训阻泽力直不计理，球推焰车确人姿能唐使宪车耐得验到偷的姑推怕力f满品足:-堪B汗≤密f传≤岩A,f偿>0为抱推甩力件，f集<0为屈拉奔力恐。况问私怎李样推张车仗可倾使供车伸最扎快底停杯于混修睛车该处跌。

设该车的运动速度为υ=υ(t)，根据题意，υ(0)=υ(T)=0，其中T为推车所花的全部时间。由于-B≤f≤A，且f=mυ′，可知-b≤υ′≤a（其中m为汽车质量，a=A/m,b=B/m）。据此不难将本例归纳为如下的数学模型：

minT

υ(0)=υ(T)=0此吧问架题旁为详一岛泛胸函轻极敢值单问后题者，闭求谱解独十呢分谱困通难棍，止为闻得控出确一盛个已最价速古方诵案火。居我修们蜜作失如嫂下降猜俩测拣：猜测最速方案为以最大推力将车推到某处，然后以最大拉力拉之，使之恰好停于修车处，其中转换点应计算求出证明设υ=υ(t)为在最速推车方案下汽车的速度，则有。设此方案不同于我们的猜测。现从O点出发，作射线y=at；从（t,0）出发，作直线y=-b(t-T)交y=at于A，由于，曲线υ=υ(t)必位于三角形区域DAT的内部，从而有ΔOAT的面积大于S。在O到T之间任取一点T′

，过T′作AT的平行线交OA于A′

。显然ΔOA′T′的面积S（T′）是T′的连续函数，当T′=0时S（0）=0，当T′=T时，S（T）>S，故由连续函数的性质存在某T′<T，S（T′）=S但这一结果与υ=υ(t)是最优方案下的车速的假设矛盾，因为用我们猜测的推车方法推车，只需T′时间即可将车推到修车处，而T′<T。oυtAT′TA′Sy=aty=-b(t-T)逻臣辑叼模嫂型例1

拟将一批尺寸为1×2×4的的商品装入尺寸为6×6×6的正方体包装箱中，问是否存在一种装法，使装入的该商品正好充满包装箱。解将子正些方副体凝剖帮分克成2白7个2冰×捞2陶×政2的剂小霉正们方东体界，括并按考下吩图匀所去示脚黑微白详相纸间丘地旋染撞色伤。再蕉将挣每来一2谈×绿2兔×匙2的推小片正闲方崖体纤剖烟分低成1宪×雄1启×冤1的邮小娃正心方忠体应。易云见木，2供7个2钓×棚2捎×祸2的横正系方赢体幕中坑，傲有1绘4个冈是稀黑腊的叛，1晒3个芒是奖白惊的习（培或1泊3黑1很4白威）疯，书故销经慌两爽次巨剖椒分滚，忽共句计驶有1呆1价2个1废×册1洽×尼1的雄黑皇色宿小摧正主方滩体子和1欢0注4个1跑×迹1属×绍1的桑白邻色裁小敏正枪方泥体昼。虽厅然穷包柄装趣箱符的岩体塘积纸恰站好鹅是仰商行品傍体电积绳的2绵7倍嫁，街但换容社易扮看乔到茅，赵不肺论裳将境商作品雹放叙置伤在饱何傻处群，自它效都玩将且占寸据4个集黑麻色偷和4个玩白吉色窑的1演×版1胡×耐1小签正晓方栽体刚的墙位旗置女，谎故锹商鸡品愤不北可叹能止充敲满堂包君装胃箱董。德兆国絮著殖名柳的匪艺脸术馋家A急l锯b向r桨e传c丸h早t油D穗ü词r符e早r吧(炉1须4亮7皂1蚕-萄1奖5旦2康1索)于1译5草1领4年被曾首铸哑造饶了欠一膀枚邮名他为敢“M廊e姨l卸e幸n钓c扩o内t掘i近a稻I趣”的溜铜踏币粉。抱令伞人仁奇始怪旋的墨是绘在贼这罩枚遵铜假币违的万画规面圈上贼充垦满丧了伙数鸭学食符拣号将、细数抛字野及径几肃何油图作形陶。而这猫里倾，症我葬们深仅露研联究佛铜冈币译右踏上烛角胃的陶数木字墓问畅题

例2.Dürer魔方（或幻方）问题所费谓窜的雅魔膀方益是厦指海由1悠~随n2这n2个职正瓜整象数列按乘一鹿定针规麻则途排吉列储成息的况一桃个n行n列锅的仪正煌方肺形总。n称纪为双此繁魔帝方卷的绝阶敞。D始ü繁r画e掘r魔软方：4阶辨，枕每赏一出行样之刻和赖为3恋4，炼每王一闭列抛之逮和庆为3鞠4，场对马角默线恼（笛或情反天对纱角贱线诵）输之属和访是3宫4，纯每连个派小外方终块坝中炎的霞数羊字县之肯和网是3浸4，粒四帜个佣角往上世的筒数闻字舞加激起搬来樱也伪是3荒4什么是Dürer魔方多负么丹奇持妙弊的牲魔浮方啄！铜煎币蚕铸适造丘时攀间同：1但5屯1赌4年构园造亦魔秤方肤是衬一皇个价古葡老热的招数色学身游神戏哥，绩起攻初贯它柔还抚和虹神期灵稼联被系助在攀一跨起亚，余带肚有锋深迟厚策的我迷纵信婚色靠彩盖。陶传发说沙三脉千赵二鄙百恼多衫年丙前裳（占公筒元反前2钩2稻0纷0年垫）灿，进因厌治敬水认出羞名肯皇些帝写大贵禹输就弓构味造浅了激三笔阶趋魔想方岔（喉被毒人悄们灭称腐“免洛臭书运”沙）术，脾至堡今穗还根有朵人兼把满它贪当床作口符仍咒煤用朗于砍某广些白迷诊信邀活磨动拒，搭大散约哭在坦十施五个世般纪匠时阳，狮魔贯方挂传巧到忘了弃西悄方锦，驾著州名敢的央科极尼选利蒜厄芳斯·阿矩格耕里柿帕临（1坏4盼8劈燕6饿-聚1处5吐3臭5）冷先如后尸构奶造滤出旦了3唇~陷9阶楚的明魔班方平。如何构造魔方奇乡丰数潮（宏不白妨n油=壮5）堡阶塔的月情镜况Step1:在第一行中间写1Step2:每次向右上方移一格依次填按由小到大排列的下一个数，向上移出界时填下一列最后一行的小方格；向右移出界时填第一列上一行的小方格。若下面想填的格已填过数或已达到魔方的右上角时，改填刚才填的格子正下方的小方格，继续Step2直到填完1234567891任01污11爹21受31魔41而51补61稻71慌81狗92州02遇12陕22走32崭42莫5偶数阶的情况

偶数阶的魔方可以利用奇数阶魔方拼接而成，拉尔夫·斯特雷奇给出了一种拼接的方法，这里不作详细介绍五阶没人知道有多少个！！！三阶1个反射和中心旋转生成8个四阶880个反射和中心旋转生成7040个魔杀方谎数惭量改随趟阶岁数n增秋长竹的怕速呢度住实谣在税是舅太欠惊旧人叨了告！同阶魔方的个数允繁许森构很成霉魔种方伴的柴数鼠取哥任舅意执实责数允酿许栋取沾实弊数n阶错魔网方A、B，骄任颤意左实驼数α、βα苦A脏+谢β狠B是n阶喉魔贯方具零有电指骄定键性框质未的喘魔勤方从全掀体上构俊成般一爷个搏线懒性路空闸间问题已发生了实质性变化注乳：郊刻独画钥一蒜个齐线返性它空朴间伯只瞒需盒指菊出符它范的变维衔数称并宣求藏出纲此娘线俯性软空楼间么的蛋一免组氏基伍底松驰问题的讨论1在名第酷一倘行栋中摩共巷有4种茅取禾法巩，杀为唐保丘持据上彼述如性猪质谣的拾成席立组，仙第者二阵行多中恋的1还柿有乏两储种姨取膀法桨。送当静第危二员行捐的1也西取路定柏后散，金第乎三距行桌与羡第桑四岩行失的1就跨完厌全抹定董位倒了翼，俗故笑一草共会可收作漠出8个舞不螺同曾的糟最傍简呜方倒阵虎，握称寻之睁为价基每本爹魔少方土并昂记侨之克为Q1，…，Q8仍稿以4阶漏方泥阵狡为洞例神。令R为淡行姓和你，C为建列首和或，D为湖对迅角践线达和烤，S为它小前方缎块带和定占义0眉-方坡：R禁=驱C奇=叔D吊=汉S域=束0定棉义1膨-方踏：R膝=偿C捧=悟D盈=测S腐=占4R迎=防C蜡=舅D筋=卖S奏=暮1的溜方响阵尊构踪蝶成苦的死线测性桶空双间唯具好有凤什幻玉么萄样施的谜性喜质粘？类坟似谜于粪构惰造n维棉欧蛾氏免空扰间掘的唇标品准案基略，拆利铸用0和1我州们锁来湾构伞造说一吴些R睁=篇C复=题D饥=怎S酬=补1的型最胀简辰单颂的锄方意阵牛。显冰然味，D梅ü吃r饼e熄r空辅间钻（蒸简敞称D空匀间威）董中锡任召何等一味个印元正素上都哑可只以馒用Q1，Q2，…，Q8来巩线位性邪表桂示等，腊但榨它逗们萍能哲否容构锻成D空纯间穿的继一高组拔基表呢既？容易看出：Q1，…，Q8这8个基本方是线性相关的，即至少存在一个Qj，可以通过其它7个基本方的线性组合得到。这8个基本方的地位是等同的，故可不妨设j=8。下面验证Q1，Q2，…，Q7是否线性相关。

令：，即=等号两边对应元素相比较，得r1=r2=…=r7=0，所以是线性无关是D空间的最小生成集。

令D

即解方程组：

=

解得

D=研纪究A染l佳b市r摘e絮c县h庙t特D驴ü令r达e声r铸消造鱼的榜铜贴币2快0肃0晨4年航浙耀江属大析学荒数盟学乳建阻模世竞鼠赛（B题般）腐通谢讯扑卫规星佩上怠的挤开蜻关脏设笛置地衔面样上陪存搞在例着n个奖接拜收场站结与n个洗发赤送乏站吃，通而循在勿通钻讯袜卫源星塔上独则予设存置姐了狼若灶干束种厘开矛关触模朴式蛇。柱开光关城模屿式敢可裤用映矩谢阵P=录(p羡i爷j)来耻表脆示坑，殊若肥卫寻星素可龄接忙收惑发翼送滋站i发遍射浇的肢信谱息仰并肝将既信嘱息澡传兽送适回商地嘴面泪的蔽接楚收揪站j时坦，茶矩荒阵豆中赢的截元啄素p饭i触j=卧1，震否狡则p鼠i渣j=稍0。鸦通馋讯骆卫还星点上金的嫌接熟收锡发桥送著任刻务赤也捧可迎以凳用摄一念个窜矩沾阵T=（t谎i初j）主来垒表晶示将，杯其咽元副素t植i私j为眠需注经辟通样讯葱卫略星垮传乞递阁的港由i发漂点恶发隔送理到j接林收燃点忙的脊信横息性量脑的坚传颗送摘时足间亲长工度抄。幼由局于痰技艘术你上门的旬原讽因绒，嗓当知发柔送桂站i在灶发剃送虎给测接拥收违站j信虏息他时单，悼它钞不猜能屯同辰时圆发铸送烛给撤别膜的毫接雀收崖站汇信通息将；架同刊样恨，台当俊接爬收旦站j在乓接遮收功发阵送款站i的肯信虾息透时璃，残也括不跪能物同弟时极接妇收责其竿他秒发谱送泛站乎发您送丹的洋信苹息兆。专你送的歇任亿务婆是技：设兔计栽一低组揭开役关摩模精式糠，k诉=俱1隆,举…把,杠r（谋注扔：r应学当奶尽映可印能撤小追）村，仍使章得傅对第任外意阳给阔定矛的足任呜务似矩词阵T，队卫洲星烤开席关疼设馒置仅均开能稠完慎成根要蜘求业的概发晓接沫收保任所务聚。设勾计身一如个烘算衰法圣，锹在称发葱接联收幻玉任捐务T给盯出邪后窗，蜘可斧根铁据毕你鬼设脏计片的耗开些关框模宴式持（k出=惯1劣,洋…圈,傲r）支求权出纯各堆开拳关嫩的练使阻用兴时馒间λk，店使避得拘在牵完锐成圈预李定类传稠送捕任枝务幅的铲前蹄提掀下迫使震用周各勇开洗关呈模无式巷的糠总辞时葱间竟最羽短喊。同跟样谱由携于流技进术觉上质的斤原他因蓄，葛开熟关激模遗式任的胶总算数r有敏一弃个评上捆限依。辅当浩需爽要影传呜送蜜的遍任小务睬数窑数镜量蚁较唤大仇时锈，岭仍赠无织法荒分查派税任朴务舰。失请寒你盖想策一伟些加办返法倍来歉解看决放这改一胳困跌难强，沃（逗当泉然矿，脑这既时含你盛可城能膜要布作耐出剪一嫂些窗牺母牲绞，逝即车传积送纠时狮间臣可掘能触会铃增匠加仁一辫些巡寿）盖。问匪题抓及远模纤型问杯题挽的飞标本准贿形启式级为误：当在屋地房诚面俭上庄存补在就着n个论收技站陕与n个周发田战吩，厉而接在塑通抄讯慢卫互星窃上况则咳设骄置忧了戒若聪干坡种热开辈关驻模往式帝。同开母关裁模粥式嫂可疲用箱矩唱阵P=阁(pi丢j)来呀表届示剑，现若导卫善星蔽可窗接切收店发塔射权站i发利射弓的昏信捎息雀并蓝将莲信赔息递传隆送谨回包地葛面绣的狂接确收陆站j时卷，爆矩柴阵糠元母素pi应j=遥1，喊否却则pi劝j=贝0。颠通奶讯合卫阴星孝的桑接饱发朴任害务送也疼可秃用裤一损矩麦阵T=（ti舰j）足来北表窄示琴，慨其照元割素ti歼j为主需况经宴通职讯偷卫盛星喜传艺递前的劈燕由i发馆点湾发落送穷到j接泉受狼点弄的长信峰息尸量纲的纱传菠送糊时工间各长浴度旷。杨问确题坚要溉求燥求r并凡设收计膀一承组喷开独关嚷模肥式Pk，k=疲1害,文…腾,r及捐模西式Pk的浩使档用路时吊间λk，顿使毛得勤在缘瑞完私成尼预就定学传朽送闻任痕务凑的束前梅提戴下寻各谅开涂关除模程式斑使棚用桐的志总辅时析间轻最迟短程，当即赴要丝式求霜求切解闷下永面伞的排问欺题陆：例1

设

这托是获一压个呀有3个色发校送葱站拴与3个债接踩收漫站壳的适实标例无，ti萝j在吵矩凤阵忘中才已喊给炭出醋，甩例坡如居由梅发柱站1传谢送参到接收符站1的割通逝讯狡量束为3单梳位彼时闪间田等号。分抵析容着易捧看袄出絮，磨三转个誓发刚站头需呀传沉送隐的复时针间适分着别饲为6、5、5；梢而呈三串个边收痒站驾需体接册收鸽的粥时仔间锻分概别缺为6、3、7。直为掩完栽成膜全大部垂传渡送皮任胆务广，毒通耕讯她卫唯星贤总叙传锈送西时吹间巴至喇少讯应荒为7单材位阿时单间筝，堡即隐的洋下佳界蜻为7。由浪于叮技惩术林上富的宁原胃因后，遇当袖发章站i在乱发寺送壮给稼收绘站j信美息底时跳，侄它崭不途能劫同剑时麻发扯送纵给斥别阶的录收闪站嫂信册息耽；瞒同宽样浊，固当愁收鹅站j在杏接恢收喘发忆站i的碑信惕息兴时们，色也睬不枝能任同奶时膀接品收愧其该他拿发软站冰发捎送铜的百信厚息垫。鞋这杜一与要炉求糖说势明顿，引