线性规划和非线性规划

线性规划和非线性规划实验目的•1)了解最优化问题的基本结构和基本建模方法;•2)线性规划的求解方法;•3）非线性规划的求解方法.一,优化问题的普遍性以及引例1，无处不在的优化•每一个人，高致总统首相，总裁经理，平民百姓，无不在做决策：该做什么，该怎么做，才能有最好的效果?•甚至自然中的动植物，也时刻面临这样的问题.•类似的问题，还广泛的存在于无机世界中.一,优化问题的普遍性以及引例看看下面的例子分别属于哪一类？a)证券的投资组合；b)国家经济发展战略；c)产品规格、性能设计；d)球形的水滴；e)狼群的集体捕食；f)好的购物方案；g)物质分子结构；h)生物的身体构造；i)乘务组排班表;j)光传播路径:直线,反射,折射课堂作业：和你的同桌讨论还有什么方面需要优化的。一,优化问题的普遍性以及引例2,一些成功的优化例子：•“最优人员安排”为美国航空每年节约两千万美元.•“改进的出货流程”每年为YellowFreight公司节约一千七百多万美元.•“改进的卡车分派”为Reynolds公司每年节约七百万美元.•最优全局供应链为数字设备行业节约超过三亿美元.•重建的NorthAmericaOperations,ProctorandGamble减少20%的工厂,每年节约两亿美元.•大阪的Hanshin高速的最优安排每年节约一千七百万人小时.为说明最优化的价值,建立了专门的网站,列举了哪些公司的什么问题,运用最优化方法节约和增加了多少金额.有可选的行业,考察的方面,受益的方式,希望同学们各选择其中的一个,提一份报告,以说明最优化的价值.一,优化问题的普遍性以及引例Google上相关搜索的结果：Searchphrasenumberofhits（英文）短语点击数（中文）•“optimizethesupplychain”1,160,000优化供应链414,000•“optimize(the)return”2,490,000优化回报453,000•“optimalexperience”32,400,000最优经历•“optimalinvestment”8,320,000优化投资8,250,000•“optimalsystem”84,200,000优化系统13,800,000•“optimaldecision”28,800,000最优决策2,890,000•“optimizeyourPC”3,300,000优化你的PC•“optimalchoice”25,800,000最优选择10,900,000•“optimaldesign”77,300,000优化设计1,270,000•“optimalhealth”31,900,000优化健康还有如:优化产业结构2,830,000优化人员结构3,110,000同学们有没有发现,英文和中文短语间有很大的不同,原因可能是什么?一,优化问题的普遍性以及引例3,相关的几句格言：•Wasteneithertimenormoney,butmakethebestuseofboth.--BenjaminFranklin•Obviously,thehighesttypeofefficiencyisthatwhichcanutilizeexistingmaterialtothebestadvantage.--JawaharlalNehru•Itismoreprobablethattheaveragemancould,withnoinjurytohishealth,increasehisefficiencyfiftypercent.--WalterScott请同学翻译上面的句子，你喜欢那一句？你有什么好的表述？引例1,动物饲料配置问题美国一家公司以专门饲养并出售一种实验用的动物而闻名。这种动物的生长对饲料中的三种营养成分特别敏感，即蛋白质、矿物质和维生素。需要的营养量蛋白质：70克矿物质：3克维生素：9.1毫克现有五种饲料，公司希望找出满足动物营养需要使成本达到最低的混合饲料配置。饲料蛋白质(克)矿物质(克)维生素(毫克)1(x1)2(x2)3(x3)4(x4)5(x5)需要量0.302.001.000.601.80700.100.050.020.200.0530.050.100.020.200.089.1每一种饲料每磅所含的营养成分每种饲料每磅的成本饲料12345成本(美元)0.020.070.040.030.05引例2:供应与选址某公司有6个建筑工地要开工，每个工地的位置（用平面坐标a，b表示，距离单位：千米）及水泥日用量d吨由下表给出。目前有两个临时料场位于A(5,1),B(2,7)，日储量各有20吨。假设从料场到工地均有直线道路相连，（1）试制定每天的供应计划，即从A、B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611二,优化问题建模的基本步骤介绍在我们的生活中,始终有这样的问题:为了一定的目的做一些事情,我们可能要考虑有哪些重要的因素,这些因素和要完成的目标之间有什么样的关系.也就是说,我们在做一个决定时,会注意下面的三个要点:•目的是什么?•有哪些重要的因素?•这些因素和你的目标之间有什么样的关系?二，优化问题的表述•目标函数对应决策者而言,对其有利的程度必须定量的测度,在商业应用中，有效性的测度经常是利润或者成本,但对于政府，更经常的使用投入产出率来测度.表示有效性测度的经常称为目标函数.目标函数要表出测度的有效性,必须说明测度和导致测度改变的变量之间的关系.系统变量分为决策变量和参数.决策变量是指能由决策者直接控制的变量.而参数是指不能由决策者决定的量.实际上，数学模型很少有能表达变量和有效性测度之间的精确关系的.实际上，运筹学分析者的任务就是找出对测度有最重要影响的变量然后找出这些变量和测度之间的数学关系.这个数学关系也就是目标函数.二，优化问题的表述•决策变量和参数我们称对应决策者可控的量称为决策变量,决策变量的取值确定了系统的最终性能,也是决策者采用决策的依据.在系统中还有一些量,它不能由决策者所控制,而是由系统所处的环境所决定,我们称之为参数.二，优化问题的表述•约束条件约束条件就是决策变量和参数之间的关系.约束集界定决策变量可以取某些值而不能取其他的值.比如对应生产问题,任何活动中,时间和物品不能为负数.当然,也有一些优化问题不带约束条件,我们称之为无约束优化问题.而在实际问题中,决策变量带有约束是普遍的.三,优化问题的分类优化问题的分类可以从几个方面进行:1,从变量取值的连续和离散可以分成:连续优化,离散优化和混合优化2,从问题的线性非线性可以分为:线性规划和非线性规划3,从变量是确定性和随机性可以分为:随机规划和确定性问题.•JohnVonNeumann•约翰·冯·诺依曼(1903－1957),美藉匈牙利人.20世纪最杰出的数学家之一,被誉为”计算机之父”,”博弈论之父”.被认为是数学规划的三大创始人之一.以下的三个人物和线性规划的出现有重要的关系.GeorgeB.Dantzig•GeorgeB.Dantzig(1914-2005),美国人,线性规划单纯形法的创始人,被誉为”线性规划之父”.美国科学院三院院士,美国军方数学顾问,教授.并以其名字设立Dantzig奖.数学规划的三大创始人之一.•发现算法时非常年轻,以至到日本时,人们以为”线性规划之父”是个老人,而对他无人问津.LeonidVitalyevichKantorovich•Kantorovich(1912-1986)苏联人,著名数学家和经济学家,教授,年仅18岁获博士学位.因在经济学上提出稀缺资源的最优配置获诺贝尔奖.线性规划对偶理论的提出者,数学规划的三大创始人之一.•非线性规划问题在实践中也是及其常见的.标志着这一学科的产生的奠基性工作由美国的数学家Tucker和Kuhn在1952年的一篇文章.该文章给出了非线性规划问题的必要条件和充分条件,后来成为Kuhn-Tucker条件.这为非线性规划问题的求解算法的提出提供了理论基础和算法的基本思路.•相关的规划问题,比如多目标规划,决策论等等.美国一家公司以专门饲养并出售一种实验用的动物而闻名。这种动物的生长对饲料中的三种营养成分特别敏感，即蛋白质、矿物质和维生素。需要的营养量蛋白质：70克矿物质：3克维生素：9.1毫克现有五种饲料，公司希望找出满足动物营养需要使成本达到最低的混合饲料配置。四,线形规划问题的解法及举例饲料蛋白质(克)矿物质(克)维生素(毫克)1(x1)2(x2)3(x3)4(x4)5(x5)需要量0.302.001.000.601.80700.100.050.020.200.0530.050.100.020.200.089.1每一种饲料每磅所含的营养成分每种饲料每磅的成本饲料12345成本(美元)0.020.070.040.030.05建立数学模型①决策变量：在混合饲料中，每天所需第j种饲料的磅数xj，j=1，2，3，4，5；②约束条件：蛋白质：0.30x1+2x2+x3+0.6x4+1.8x5≥70矿物质：0.10x1+0.05x2+0.02x3+0.2x4+0.05x5≥3维生素：0.05x1+0.1x2+0.02x3+0.2x4+0.08x5≥10自然约束条件：xi≥0③确定目标：混合饲料的成本最低0.02x1+0.07x2+0.04x3+0.03x4+0.05x5→min完整的线性规划模型：min0.02x1+0.07x2+0.04x3+0.03x4+0.05x5s.t.0.30x1+2x2+x3+0.6x4+1.8x5≥700.10x1+0.05x2+0.02x3+0.2x4+0.05x5≥30.05x1+0.1x2+0.02x3+0.2x4+0.08x5≥10xj≥0j=1,2,3,4,5;mincTxs.t.Ax≥bx≥010370,08.02.002.01.005.005.02.002.005.01.08.16.0123.0]05.0,03.0,04.0,07.0,02.0[bAcT归纳：返回•linprog•mincTx•s.t.Ax≤b•Aeqx≤beq•lb≤x≤ub•Solvealinearprogrammingproblem•wherec,x,b,beq,lb,andubarevectorsandAandAeqarematrices.•调用格式:x=linprog(f,A,b,Aeq,beq)•x=linprog(f,A,b,Aeq,beq,lb,ub)•x=linprog(f,A,b,Aeq,beq,lb,ub,x0)•x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)•[x,fval]=linprog(...)•[x,fval,exitflag]=linprog(...)•[x,fval,exitflag,output]=linprog(...)•[x,fval,exitflag,output,lambda]=linprog(...)原油生产计划原油类别买入价(元/桶)买入量(桶/天)辛烷值(%)硫含量(%)A45≤5000120.5B35≤500062.0C25≤500083.0汽油类别卖出价(元/桶)需求量(桶/天)辛烷值(%)硫含量(%)甲703000≥10≤1.0乙602000≥8≤2.0丙501000≥6≤1.01:1加工费:4元/桶能力:=14000桶/天I:安排生产计划，在满足需求的条件下使利润最大决策变量：目标：甲(3000)乙(2000)丙(1000)A/45X1X2X3B/35X4X5X6C/25X7X8X9fxxxxxxxxxzmin35600025354560004100050200060300070max987654321约束：987654321253545minxx