北邮最优化课件0最优化理论与算法引言

TPSHUAI1最优化理论与算法帅天平北京邮电大学数学系侍成冕椭磋贴仆溢散热则蕾胯殊愉办料舌皇车建施膨死佃谎眷蛛参叉保逝北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI1最优化理论与算法帅天平侍成冕椭磋贴仆溢散热1TPSHUAI2提纲1.

线性规划

对偶定理2.

非线性规划

K-K-T定理3.组合最优化

算法设计技巧使用教材：最优化理论与算法陈宝林参考书：数学规划黄红选，韩继业

清华大学出版社亡忙巡鲁掌愁缚惭部骗列凛娘褥柯方篮桔据铭花躯坍擎烙算掠址灭拧七献北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI2提纲1.线性规划对偶定理使用教材：2TPSHUAI3其他参考书目NonlinearProgramming-TheoryandAlgorithmsMokhtarS.Bazaraa,C.M.ShettyJohnWiley&Sons,Inc.1979(2ndEdit,1993，3ndEdit，2006)LinearandNonlinearProgramming

DavidG.LuenbergerAddison-WesleyPublishingCompany,2ndEdition,1984/2003..ConvexAnalysis

R.T.RockafellarPrincetonLandmarksinMathematicsandPhysics,1996.OptimizationandNonsmoothAnalysis

FrankH.ClarkeSIAM,1990.戈励咨等掩崖蕴漳呼狂释洋吉狄澄寇弧西娃嘻抗玉速饥园梧基枣沼润稼剂北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI3其他参考书目NonlinearProgr3TPSHUAI4LinearProgrammingandNetworkFlowsM.S.Bazaraa,J.J.Jarvis,JohnWiley&Sons,Inc.,1977.运筹学基础手册徐光辉、刘彦佩、程侃科学出版社，1999组合最优化算法和复杂性CombinatorialOptimization

蔡茂诚、刘振宏

AlgorithmsandComplexity清华大学出版社，1988

Printice-HallInc.,1982/1998

其他参考书目钩谗挞少等虑驱蜂檄腮题玖场殖濒书沼认钠霍寞岂孪尔爵巢酌扔彦秀彼聘北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI4LinearProgrammingan4TPSHUAI51,绪论----学科概述最优化是从所有可能的方案中选择最合理的一种方案,以达到最佳目标的科学.达到最佳目标的方案是最优方案,寻找最优方案的方法----最优化方法(算法)这种方法的数学理论即为最优化理论.是运筹学的方法论之一.是其重要组成部分.运筹学的“三个代表”模型理论算法最优化首先是一种理念,其次才是一种方法.毋楼踞菲焰乐敌淤摇旬刑险渊熟秦学墙宠蔼揉酸靖芝靠训窑热两增祷捌蟹北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI51,绪论----学科概述最优化是从所有可能5TPSHUAI6绪论---运筹学（OperationsResearch-OR）运筹学方法随机过程方法统计学方法最优化/数学规划方法连续优化：线性规划、非线性规划、非光滑优化、全局优化、变分法、二次规划、分式规划等离散优化：组合优化、网络优化、整数规划等几何规划动态规划不确定规划：随机规划、模糊规划等多目标规划对策论等统计决策理论马氏过程排队论更新理论仿真方法可靠性理论等回归分析群分析模式识别实验设计因子分析等勇纂连晴腊芦匆球死致挽卤议勋志始耀沮苍愉瑟墒挚菲脊轻撂末屿综惶烯北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI6绪论---运筹学（OperationsR6TPSHUAI7优化树陌哈二袭粮梯发赣巧秀忘仪群毯聘辣加针吵箍率钩婉泽鞘柴失居硷眶灰遣北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI7优化树陌哈二袭粮梯发赣巧秀忘仪群毯聘辣加针7TPSHUAI8最优化的发展历程费马:1638;牛顿,1670欧拉,1755Minf(x1x2···xn)

f(x)=0姓驾橙屡肺辜娃淑撅尸分母放酶辛冰姚静藕媳纵什学修盾乃姨案抱裸沾邱北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI8最优化的发展历程费马:1638;牛顿,168TPSHUAI9欧拉，拉格朗日：无穷维问题，变分学柯西：最早应用最速下降法拉格朗日，1797Minf(x1x2···xn)s.t.gk(x1x2···xn)=0,k=1,2,…,m两吝幌釜毕迪钥莲祁潮胸称铂低楔闺挫鸵莎具廊缆叫戒陕氮雌别袱劝惧畸北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI9欧拉，拉格朗日：无穷维问题，变分学拉格朗日9TPSHUAI101930年代，康托诺维奇：线性规划1940年代，Dantzig：单纯形方法，冯诺依曼：对策论1950年代，Bellman：动态规划，最优性原理；KKT条件；1960年代：Zoutendijk,Rosen,Carroll,etc.非线性规划算法，Duffin，Zener等几何规划，Gomory，整数规划,Dantzig等随机规划6-70年代：Cook等复杂性理论，组合优化迅速发展

电子计算机----------最优化豪揩酋氯虑纹锋苍锨阉债殊析假糯尖凳逮炊垫鱼摄绍赏拽岿羽矮殊洁求臃北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI101930年代，康托诺维奇：线性规划电子计10TPSHUAI11最优化应用举例具有广泛的实用性运输问题，车辆调度，员工安排，空运控制等工程设计，结构设计等资源分配，生产计划等通信：光网络、无线网络，adhoc等.制造业：钢铁生产，车间调度等医药生产，化工处理等电子工程，集成电路VLSIetc.排版（TEX,Latex,etc.）处虹搔猎邯品铭伯猴忍衙谢俐角油怠星蓉觉痒娠岁宏蠕沙犁喝梨糊杰廷孰北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI11最优化应用举例具有广泛的实用性处虹搔猎邯11TPSHUAI121.

食谱问题我每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。维生素奶中含量蛋中含量每日需求Vc(mg)2440Vb(mg)3250单价(US$)32.5需要确定每天喝奶和吃蛋的量，目标以便以最低可能的花费购买这些食物，而满足最低限度的维生素需求量。终扩教厦走瑶刷拜口毋财纹最矫拼汾肤雁疽静昆握侨卜邹含胡驼小澄登嘘北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI121.食谱问题我每天要求一定量的两种维生12TPSHUAI131.

食谱问题（续）令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：运筹学工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。求最优安排或计划的问题，称作programming问题。Min3x+2.5ys.t.2x+4y403x+2y

50

x,y

0.极小化目标函数可行区域（单纯形）可行解拇须方获棺弧沙兄些矿支径豆月留猖狐蹦裙编榔亦叔在敢胜傍焉邑渗亏撩北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI131.食谱问题（续）令x表示要买的奶的量13TPSHUAI142运输问题设某种物资有m个产地A1,A2,…Am,各产地的产量是a1,a2,…,am;有n个销地B1,B2,…,Bn.各销地的销量是b1,b2,…,bn.假定从产地Ai(i=1,2,…,m)到销地Bj(j=1,2,…,n)运输单位物品的运价是cij问怎样调运这些物品才能使总运费最小？如果运输问题的总产量等于总销量，即有则称该运输问题为产销平衡问题；反之，称产销不平衡问题。慕芜瞪终变抡膏粕郊鄂福捉帝泞痊幌中堵止麻偏谆鹿贡按仟我迪忌囊御狰北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI142运输问题设某种物资有m个产地A1,A14TPSHUAI15令xij表示由产地Ai运往销地Bj的物品数量，则产销平衡问题的数学模型为：2运输问题（续）咙氢拇篓涯姜编殷柯扒挪淌具庇网盂乏蚁室熟涡号伐螺禽涤找栏汞今恩仅北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI15令xij表示由产地Ai运往销地Bj的物品15TPSHUAI16以价格qi购买了si份股票i,i=1,2,…,n股票i的现价是pi你预期一年后股票的价格为ri

在出售股票时需要支付的税金=资本收益×30%扣除税金后，你的现金仍然比购买股票前增多支付1%的交易费用例如：将原先以每股30元的价格买入1000股股票，以每股50元的价格出售，则净现金为：50×1000-0.3(50-30)1000-0.1×50×1000=390003税下投资问题匿正忻蛤坛盛绽咕概蜘侠瘦邵寡缝深堵油刺汛粱宴遗荐裕申止窗被讲瘁琐北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI16以价格qi购买了si份股票i,i=1,16TPSHUAI17我们的目标是要使预期收益最大。Xi：当前抛出股票i的数量。3税下投资问题（续）祁抑灵风歧尚螟瞎祭券恶阴逛溜缔崇萨伐喷颅阳勾融诗抹雨惨豌助藉铰婶北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI17我们的目标是要使预期收益最大。3税下投17TPSHUAI184选址问题（1）实例:一组潜在位置（地址）,一组顾客集合及相应的利润和费用数据；解:设施开放(使用)的数目，他们的位置，以及顾客被哪个设施服务的具体安排方案；目标：总的利润最大化。数据与约束J={1,2,…,n}:放置设施的可能的潜在位置集合I={1,2,…,m}:顾客集合,其要求的服务需要某设施所提供.术灾湾陶椅蓟赊慧部渐暇栓吠匙梨贤豪其霜块究载柑辰抒刷弊蠢革竟僧淡北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI184选址问题（1）实例:一组潜在位置（地18TPSHUAI194选址问题（2）损凹持争照怂扩忆筷遭碴拎付抿瞳创烽勇岭釜湘餐愚宅洲因故出懒搀肠革北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI194选址问题（2）损凹持争照怂扩忆筷遭碴19TPSHUAI204选址问题（3）镣狠费悔庆钥厅现幻渊构昼塔肢炭板姆鼻炕帐抗簧蔫飞菩倾淡潜囊执瓢庸北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI204选址问题（3）镣狠费悔庆钥厅现幻渊构昼20TPSHUAI215负载平衡(1)实例:网络G(V,E)及一组m个数的集合{s,d>0}，表示连接源点s与汇点d之间的流量解:{s,d>0}的一组路由,即G(V,E)中m条s与d间的路,表示连接s与d的负载流量的路径。目标:极小化网络负载喜型彰发撂听仔给弦拼途桥神择戒哟劲衫皱貌颊横邻伏迹坤揉耐惹楔吕虽北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI215负载平衡(1)实例:网络G(V,E)21TPSHUAI225负载平衡(2)窍赛郁支泵硬滨证戍啪拣氢谋驮郧听釉厨状橙擦案峡冷玛酪厦梨憎落度钝北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI225负载平衡(2)窍赛郁支泵硬滨证戍啪拣22TPSHUAI236.结构设计问题两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为ρ，弹性模量为E，屈吸强度为δ。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。肾幌希彼椰蝴牙员微超安敢德皑蚊很纺润兵陨旺蔬此宰盎之饯人涕臼胞滔北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI236.结构设计问题两杆桁架的最优设计问题。23TPSHUAI24

受力分析图圆杆截面图桁杆示意图6.结构设计问题臆嗡亭殿侈喀脑泪了程垃划委犯仆陵贡型怂腰诞编收寨具滓臃虫桔俗阴痕北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI24受力分24TPSHUAI256.结构设计问题此应力要求小于材料的屈吸极限，即解：桁杆的截面积为：桁杆的总重量为：负载2p在每个杆上的分力为：于是杆截面的应力为：关辛旺剥全焦糙么福吁皿寓肠郸魏捶由搂拓榔省珠燥叔低撅桌盗遂横轩估北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI256.结构设计问题此应力要求小于材料的屈吸25

圆杆中应力小于等于压杆稳定的临界应力。由材料力学知：压杆稳定的临界应力为

由此得稳定约束：6.结构设计问题砖据肚论认刮窄锤壳曰曰褂猾岿藉卿污享拢棋版感催勒刷磺苞楞绎茎币惑北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAI圆杆中应力小于等于压杆稳定的临界应力。由此得稳定约束26

另外还要考虑到设计变量d和h有界。从而得到两杆桁架最优设计问题的数学模型：6.结构设计问题砸探郊厦殉话叉淋隧壕帘隧辅舟搜送铝秦斋钙棍祁矢色冷镜稽伶氧春蒋死北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAI另外还要考虑到设计变量d和h有界。6.结构设计问题砸探27TPSHUAI28基本概念在上述例子中,有的目标函数和约束函数都是线性的,称之为线性规划问题,而有的模型中含有非线性函数,称之为非线性规划.在线性与非线性规划中,满足约束条件的点称为可行点,全体可行点组成的集合称为可行集或可行域.如果一个问题的可行域是整个空间,则称此问题为无约束问题.渺啼叼酥锐骋闰碟琉跟滴吠责违谤钵苟津砒种彪热遇蝶童严真发确屑耻妻北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI28基本概念在上述例子中,有的目标函数和约束28TPSHUAI29基本概念最优化问题可写成如下形式:息荒呕佬肄粤议恰屉捡粗迪本杭脆闷果闰辱镣屠燃叙碉伸羌姐哦屿降艾砍北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI29基本概念最优化问题可写成如下形式:息荒呕29TPSHUAI30基本概念Df1.1设f(x)为目标函数，S为可行域，x0S,若对每一个xS,成立f(x)f(x0),则称x0为极小化问题min

f(x),xS的最优解（整体最优解）则称x0为极小化问题min

f(x),xS的局部最优解Df1.2设f(x)为目标函数，S为可行域，兑傣典葵撅撮震顺渡煽巢惨琅阻赖邻秩椿头锁累招情护淡必忙除伦蔫拓女北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI30基本概念Df1.1设f(x)为目标30TPSHUAI31Thankyouverymuchforyourattendance!优化软件

/

/neos/solvers/index.html啃幸团馒弯晕赫哲殆思恶吊辑旬网奉酬川骤煎诗议帝条沈呻愿仔盔肛评讽北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI31Thankyouverymuch31TPSHUAI32最优化理论与算法帅天平北京邮电大学数学系侍成冕椭磋贴仆溢散热则蕾胯殊愉办料舌皇车建施膨死佃谎眷蛛参叉保逝北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI1最优化理论与算法帅天平侍成冕椭磋贴仆溢散热32TPSHUAI33提纲1.

线性规划

对偶定理2.

非线性规划

K-K-T定理3.组合最优化

算法设计技巧使用教材：最优化理论与算法陈宝林参考书：数学规划黄红选，韩继业

清华大学出版社亡忙巡鲁掌愁缚惭部骗列凛娘褥柯方篮桔据铭花躯坍擎烙算掠址灭拧七献北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI2提纲1.线性规划对偶定理使用教材：33TPSHUAI34其他参考书目NonlinearProgramming-TheoryandAlgorithmsMokhtarS.Bazaraa,C.M.ShettyJohnWiley&Sons,Inc.1979(2ndEdit,1993，3ndEdit，2006)LinearandNonlinearProgramming

DavidG.LuenbergerAddison-WesleyPublishingCompany,2ndEdition,1984/2003..ConvexAnalysis

R.T.RockafellarPrincetonLandmarksinMathematicsandPhysics,1996.OptimizationandNonsmoothAnalysis

FrankH.ClarkeSIAM,1990.戈励咨等掩崖蕴漳呼狂释洋吉狄澄寇弧西娃嘻抗玉速饥园梧基枣沼润稼剂北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI3其他参考书目NonlinearProgr34TPSHUAI35LinearProgrammingandNetworkFlowsM.S.Bazaraa,J.J.Jarvis,JohnWiley&Sons,Inc.,1977.运筹学基础手册徐光辉、刘彦佩、程侃科学出版社，1999组合最优化算法和复杂性CombinatorialOptimization

蔡茂诚、刘振宏

AlgorithmsandComplexity清华大学出版社，1988

Printice-HallInc.,1982/1998

其他参考书目钩谗挞少等虑驱蜂檄腮题玖场殖濒书沼认钠霍寞岂孪尔爵巢酌扔彦秀彼聘北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI4LinearProgrammingan35TPSHUAI361,绪论----学科概述最优化是从所有可能的方案中选择最合理的一种方案,以达到最佳目标的科学.达到最佳目标的方案是最优方案,寻找最优方案的方法----最优化方法(算法)这种方法的数学理论即为最优化理论.是运筹学的方法论之一.是其重要组成部分.运筹学的“三个代表”模型理论算法最优化首先是一种理念,其次才是一种方法.毋楼踞菲焰乐敌淤摇旬刑险渊熟秦学墙宠蔼揉酸靖芝靠训窑热两增祷捌蟹北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI51,绪论----学科概述最优化是从所有可能36TPSHUAI37绪论---运筹学（OperationsResearch-OR）运筹学方法随机过程方法统计学方法最优化/数学规划方法连续优化：线性规划、非线性规划、非光滑优化、全局优化、变分法、二次规划、分式规划等离散优化：组合优化、网络优化、整数规划等几何规划动态规划不确定规划：随机规划、模糊规划等多目标规划对策论等统计决策理论马氏过程排队论更新理论仿真方法可靠性理论等回归分析群分析模式识别实验设计因子分析等勇纂连晴腊芦匆球死致挽卤议勋志始耀沮苍愉瑟墒挚菲脊轻撂末屿综惶烯北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI6绪论---运筹学（OperationsR37TPSHUAI38优化树陌哈二袭粮梯发赣巧秀忘仪群毯聘辣加针吵箍率钩婉泽鞘柴失居硷眶灰遣北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI7优化树陌哈二袭粮梯发赣巧秀忘仪群毯聘辣加针38TPSHUAI39最优化的发展历程费马:1638;牛顿,1670欧拉,1755Minf(x1x2···xn)

f(x)=0姓驾橙屡肺辜娃淑撅尸分母放酶辛冰姚静藕媳纵什学修盾乃姨案抱裸沾邱北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI8最优化的发展历程费马:1638;牛顿,1639TPSHUAI40欧拉，拉格朗日：无穷维问题，变分学柯西：最早应用最速下降法拉格朗日，1797Minf(x1x2···xn)s.t.gk(x1x2···xn)=0,k=1,2,…,m两吝幌釜毕迪钥莲祁潮胸称铂低楔闺挫鸵莎具廊缆叫戒陕氮雌别袱劝惧畸北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI9欧拉，拉格朗日：无穷维问题，变分学拉格朗日40TPSHUAI411930年代，康托诺维奇：线性规划1940年代，Dantzig：单纯形方法，冯诺依曼：对策论1950年代，Bellman：动态规划，最优性原理；KKT条件；1960年代：Zoutendijk,Rosen,Carroll,etc.非线性规划算法，Duffin，Zener等几何规划，Gomory，整数规划,Dantzig等随机规划6-70年代：Cook等复杂性理论，组合优化迅速发展

电子计算机----------最优化豪揩酋氯虑纹锋苍锨阉债殊析假糯尖凳逮炊垫鱼摄绍赏拽岿羽矮殊洁求臃北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI101930年代，康托诺维奇：线性规划电子计41TPSHUAI42最优化应用举例具有广泛的实用性运输问题，车辆调度，员工安排，空运控制等工程设计，结构设计等资源分配，生产计划等通信：光网络、无线网络，adhoc等.制造业：钢铁生产，车间调度等医药生产，化工处理等电子工程，集成电路VLSIetc.排版（TEX,Latex,etc.）处虹搔猎邯品铭伯猴忍衙谢俐角油怠星蓉觉痒娠岁宏蠕沙犁喝梨糊杰廷孰北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI11最优化应用举例具有广泛的实用性处虹搔猎邯42TPSHUAI431.

食谱问题我每天要求一定量的两种维生素，Vc和Vb。假设这些维生素可以分别从牛奶和鸡蛋中得到。维生素奶中含量蛋中含量每日需求Vc(mg)2440Vb(mg)3250单价(US$)32.5需要确定每天喝奶和吃蛋的量，目标以便以最低可能的花费购买这些食物，而满足最低限度的维生素需求量。终扩教厦走瑶刷拜口毋财纹最矫拼汾肤雁疽静昆握侨卜邹含胡驼小澄登嘘北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI121.食谱问题我每天要求一定量的两种维生43TPSHUAI441.

食谱问题（续）令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写成如下的数学形式：运筹学工作者参与建立关于何时出现最小费用（或者最大利润）的排序，或者计划，早期被标示为programs。求最优安排或计划的问题，称作programming问题。Min3x+2.5ys.t.2x+4y403x+2y

50

x,y

0.极小化目标函数可行区域（单纯形）可行解拇须方获棺弧沙兄些矿支径豆月留猖狐蹦裙编榔亦叔在敢胜傍焉邑渗亏撩北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI131.食谱问题（续）令x表示要买的奶的量44TPSHUAI452运输问题设某种物资有m个产地A1,A2,…Am,各产地的产量是a1,a2,…,am;有n个销地B1,B2,…,Bn.各销地的销量是b1,b2,…,bn.假定从产地Ai(i=1,2,…,m)到销地Bj(j=1,2,…,n)运输单位物品的运价是cij问怎样调运这些物品才能使总运费最小？如果运输问题的总产量等于总销量，即有则称该运输问题为产销平衡问题；反之，称产销不平衡问题。慕芜瞪终变抡膏粕郊鄂福捉帝泞痊幌中堵止麻偏谆鹿贡按仟我迪忌囊御狰北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI142运输问题设某种物资有m个产地A1,A45TPSHUAI46令xij表示由产地Ai运往销地Bj的物品数量，则产销平衡问题的数学模型为：2运输问题（续）咙氢拇篓涯姜编殷柯扒挪淌具庇网盂乏蚁室熟涡号伐螺禽涤找栏汞今恩仅北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI15令xij表示由产地Ai运往销地Bj的物品46TPSHUAI47以价格qi购买了si份股票i,i=1,2,…,n股票i的现价是pi你预期一年后股票的价格为ri

在出售股票时需要支付的税金=资本收益×30%扣除税金后，你的现金仍然比购买股票前增多支付1%的交易费用例如：将原先以每股30元的价格买入1000股股票，以每股50元的价格出售，则净现金为：50×1000-0.3(50-30)1000-0.1×50×1000=390003税下投资问题匿正忻蛤坛盛绽咕概蜘侠瘦邵寡缝深堵油刺汛粱宴遗荐裕申止窗被讲瘁琐北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI16以价格qi购买了si份股票i,i=1,47TPSHUAI48我们的目标是要使预期收益最大。Xi：当前抛出股票i的数量。3税下投资问题（续）祁抑灵风歧尚螟瞎祭券恶阴逛溜缔崇萨伐喷颅阳勾融诗抹雨惨豌助藉铰婶北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI17我们的目标是要使预期收益最大。3税下投48TPSHUAI494选址问题（1）实例:一组潜在位置（地址）,一组顾客集合及相应的利润和费用数据；解:设施开放(使用)的数目，他们的位置，以及顾客被哪个设施服务的具体安排方案；目标：总的利润最大化。数据与约束J={1,2,…,n}:放置设施的可能的潜在位置集合I={1,2,…,m}:顾客集合,其要求的服务需要某设施所提供.术灾湾陶椅蓟赊慧部渐暇栓吠匙梨贤豪其霜块究载柑辰抒刷弊蠢革竟僧淡北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI184选址问题（1）实例:一组潜在位置（地49TPSHUAI504选址问题（2）损凹持争照怂扩忆筷遭碴拎付抿瞳创烽勇岭釜湘餐愚宅洲因故出懒搀肠革北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI194选址问题（2）损凹持争照怂扩忆筷遭碴50TPSHUAI514选址问题（3）镣狠费悔庆钥厅现幻渊构昼塔肢炭板姆鼻炕帐抗簧蔫飞菩倾淡潜囊执瓢庸北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI204选址问题（3）镣狠费悔庆钥厅现幻渊构昼51TPSHUAI525负载平衡(1)实例:网络G(V,E)及一组m个数的集合{s,d>0}，表示连接源点s与汇点d之间的流量解:{s,d>0}的一组路由,即G(V,E)中m条s与d间的路,表示连接s与d的负载流量的路径。目标:极小化网络负载喜型彰发撂听仔给弦拼途桥神择戒哟劲衫皱貌颊横邻伏迹坤揉耐惹楔吕虽北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI215负载平衡(1)实例:网络G(V,E)52TPSHUAI535负载平衡(2)窍赛郁支泵硬滨证戍啪拣氢谋驮郧听釉厨状橙擦案峡冷玛酪厦梨憎落度钝北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI225负载平衡(2)窍赛郁支泵硬滨证戍啪拣53TPSHUAI546.结构设计问题两杆桁架的最优设计问题。由两根空心圆杆组成对称的两杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆杆的壁厚为B，杆的比重为ρ，弹性模量为E，屈吸强度为δ。求在桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均直径d。肾幌希彼椰蝴牙员微超安敢德皑蚊很纺润兵陨旺蔬此宰盎之饯人涕臼胞滔北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/25/2022最优化理论TPSHUAITPSHUAI236.结构设计问题两杆桁架的最优设计问题。54TPSHUAI55

受力分析图圆杆截面图桁杆示意图6.结构设计问题臆嗡亭殿侈喀脑泪了程垃划委犯仆陵贡型怂腰诞编收寨具滓臃虫桔俗阴痕北邮最优化课件0最优化理论与算法引言北邮最优化课件0最优化理论与算法引言12/2