数学实验课件线性和非线性规划

数学实验课件线性和非线性规划第一页，共六十页，编辑于2023年，星期三实验目的

1)了解最优化问题的基本结构和基本建模方法;2)线性规划的求解方法;3）非线性规划的求解方法.第二页，共六十页，编辑于2023年，星期三一,优化问题的普遍性以及引例1，无处不在的优化每一个人，高致总统首相，总裁经理，平民百姓，无不在做决策：该做什么，该怎么做，才能有最好的效果?甚至自然中的动植物，也时刻面临这样的问题.类似的问题，还广泛的存在于无机世界中.第三页，共六十页，编辑于2023年，星期三一,优化问题的普遍性以及引例看看下面的例子分别属于哪一类？a)证券的投资组合；b)国家经济发展战略；c)产品规格、性能设计；d)球形的水滴；e)狼群的集体捕食；f)好的购物方案；g)物质分子结构；

h)生物的身体构造；i)乘务组排班表;j)光传播路径:直线,反射,折射课堂作业：和你的同桌讨论还有什么方面需要优化的。第四页，共六十页，编辑于2023年，星期三一,优化问题的普遍性以及引例2,一些成功的优化例子：“最优人员安排”为美国航空每年节约两千万美元.

“改进的出货流程”每年为YellowFreight公司节约一千七百多万美元.“改进的卡车分派”为

Reynolds公司每年节约七百万美元.最优全局供应链为数字设备行业节约超过三亿美元.重建的

NorthAmericaOperations,ProctorandGamble减少20%的工厂,每年节约两亿美元.大阪的Hanshin高速的最优安排每年节约一千七百万人小时.第五页，共六十页，编辑于2023年，星期三

为说明最优化的价值,建立了专门的网站,列举了哪些公司的什么问题,运用最优化方法节约和增加了多少金额.

有可选的行业,考察的方面,受益的方式,希望同学们各选择其中的一个,提一份报告,以说明最优化的价值.第六页，共六十页，编辑于2023年，星期三一,优化问题的普遍性以及引例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同学们有没有发现,英文和中文短语间有很大的不同,原因可能是什么?第七页，共六十页，编辑于2023年，星期三一,优化问题的普遍性以及引例3,相关的几句格言：Wasteneithertimenormoney,butmakethebestuseofboth.--BenjaminFranklinObviously,thehighesttypeofefficiencyisthatwhichcanutilizeexistingmaterialtothebestadvantage.--JawaharlalNehruItismoreprobablethattheaveragemancould,withnoinjurytohishealth,increasehisefficiencyfiftypercent.--WalterScott请同学翻译上面的句子，你喜欢那一句？你有什么好的表述？第八页，共六十页，编辑于2023年，星期三引例1,动物饲料配置问题

美国一家公司以专门饲养并出售一种实验用的动物而闻名。这种动物的生长对饲料中的三种营养成分特别敏感，即蛋白质、矿物质和维生素。需要的营养量蛋白质：70克矿物质：3克维生素：9.1毫克

现有五种饲料，公司希望找出满足动物营养需要使成本达到最低的混合饲料配置。第九页，共六十页，编辑于2023年，星期三饲料蛋白质(克)矿物质(克)维生素(毫克)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第十页，共六十页，编辑于2023年，星期三引例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第十一页，共六十页，编辑于2023年，星期三二,优化问题建模的基本步骤介绍

在我们的生活中,始终有这样的问题:为了一定的目的做一些事情,我们可能要考虑有哪些重要的因素,这些因素和要完成的目标之间有什么样的关系.也就是说,我们在做一个决定时,会注意下面的三个要点:目的是什么?有哪些重要的因素?这些因素和你的目标之间有什么样的关系?第十二页，共六十页，编辑于2023年，星期三二，优化问题的表述目标函数对应决策者而言,对其有利的程度必须定量的测度,在商业应用中，有效性的测度经常是利润或者成本,但对于政府，更经常的使用投入产出率来测度.

表示有效性测度的经常称为目标函数.目标函数要表出测度的有效性,必须说明测度和导致测度改变的变量之间的关系.系统变量分为决策变量和参数.决策变量是指能由决策者直接控制的变量.而参数是指不能由决策者决定的量.实际上，数学模型很少有能表达变量和有效性测度之间的精确关系的.实际上，运筹学分析者的任务就是找出对测度有最重要影响的变量然后找出这些变量和测度之间的数学关系.这个数学关系也就是目标函数.第十三页，共六十页，编辑于2023年，星期三二，优化问题的表述决策变量和参数我们称对应决策者可控的量称为决策变量,决策变量的取值确定了系统的最终性能,也是决策者采用决策的依据.在系统中还有一些量,它不能由决策者所控制,而是由系统所处的环境所决定,我们称之为参数.第十四页，共六十页，编辑于2023年，星期三二，优化问题的表述约束条件

约束条件就是决策变量和参数之间的关系.约束集界定决策变量可以取某些值而不能取其他的值.比如对应生产问题,任何活动中,时间和物品不能为负数.当然,也有一些优化问题不带约束条件,我们称之为无约束优化问题.而在实际问题中,决策变量带有约束是普遍的.第十五页，共六十页，编辑于2023年，星期三三,优化问题的分类优化问题的分类可以从几个方面进行:1,从变量取值的连续和离散可以分成:连续优化,离散优化和混合优化2,从问题的线性非线性可以分为:线性规划和非线性规划3,从变量是确定性和随机性可以分为:随机规划和确定性问题.第十六页，共六十页，编辑于2023年，星期三JohnVonNeumann

约翰·冯·诺依曼(1903－1957),美藉匈牙利人.20世纪最杰出的数学家之一,被誉为”计算机之父”,”博弈论之父”.被认为是数学规划的三大创始人之一.以下的三个人物和线性规划的出现有重要的关系.第十七页，共六十页，编辑于2023年，星期三GeorgeB.Dantzig

GeorgeB.Dantzig(1914-2005),美国人,线性规划单纯形法的创始人,被誉为”线性规划之父”.美国科学院三院院士,美国军方数学顾问,教授.并以其名字设立Dantzig奖.数学规划的三大创始人之一.发现算法时非常年轻,以至到日本时,人们以为”线性规划之父”是个老人,而对他无人问津.第十八页，共六十页，编辑于2023年，星期三LeonidVitalyevichKantorovichKantorovich(1912-1986)苏联人,著名数学家和经济学家,教授,年仅18岁获博士学位.因在经济学上提出稀缺资源的最优配置获诺贝尔奖.线性规划对偶理论的提出者,数学规划的三大创始人之一.第十九页，共六十页，编辑于2023年，星期三非线性规划问题在实践中也是及其常见的.标志着这一学科的产生的奠基性工作由美国的数学家Tucker和Kuhn在1952年的一篇文章.该文章给出了非线性规划问题的必要条件和充分条件,后来成为Kuhn-Tucker条件.这为非线性规划问题的求解算法的提出提供了理论基础和算法的基本思路.相关的规划问题,比如多目标规划,决策论等等.第二十页，共六十页，编辑于2023年，星期三

美国一家公司以专门饲养并出售一种实验用的动物而闻名。这种动物的生长对饲料中的三种营养成分特别敏感，即蛋白质、矿物质和维生素。需要的营养量蛋白质：70克矿物质：3克维生素：9.1毫克

现有五种饲料，公司希望找出满足动物营养需要使成本达到最低的混合饲料配置。四,线形规划问题的解法及举例第二十一页，共六十页，编辑于2023年，星期三饲料蛋白质(克)矿物质(克)维生素(毫克)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第二十二页，共六十页，编辑于2023年，星期三建立数学模型决策变量：在混合饲料中，每天所需第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第二十三页，共六十页，编辑于2023年，星期三完整的线性规划模型：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≥10

xj≥0j=1,2,3,4,5;mincTxs.t.Ax≥b

x≥0归纳：返回第二十四页，共六十页，编辑于2023年，星期三linprogmincTxs.t.Ax≤bAeqx=beqlb≤x≤ubSolvealinearprogrammingproblemwherec,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(...)第二十五页，共六十页，编辑于2023年，星期三原油生产计划原油类别买入价(元/桶)买入量(桶/天)辛烷值(%)硫含量(%)A45≤5000120.5B35≤500062.0C25≤500083.0汽油类别卖出价(元/桶)需求量(桶/天)辛烷值(%)硫含量(%)甲703000≥10≤1.0乙602000≥8≤2.0丙501000≥6≤1.01:1加工费:4元/桶能力:<=14000桶/天I:安排生产计划，在满足需求的条件下使利润最大第二十六页，共六十页，编辑于2023年，星期三决策变量：目标：甲(3000)乙(2000)丙(1000)A/45X1X2X3B/35X4X5X6C/25X7X8X9约束：总利润最大

需求限制；原料限制；含量限制；非负限制第二十七页，共六十页，编辑于2023年，星期三含量限制非负限制原料限制需求限制约束第二十八页，共六十页，编辑于2023年，星期三总盈利：126000元c=[45 45 45 35 35 35 25 25 25];a1=[1 0 0 1 0 0 1 0 0;0 1 0 0 1 0 0 1 0;0 0 1 0 0 1 0 0 1];a2=[1 1 1 0 0 0 0 0 0;0 0 0 1 1 1 0 0 0;0 0 0 0 0 0 1 1 1;-12 0 0 -6 0 0 -8 0 0;0 -12 0 0 -6 0 0 -8 0;0 0 -12 0 0 -6 0 0 -8;0.5 0 0 2 0 0 3 0 0;0 0.5 0 0 2 0 0 3 0;0 0 0.5 0 0 2 0 0 3];b1=[30002000 1000];b2=[50005000 5000 -30000 -16000 -6000 3000 4000 1000];v1=zeros(1,9);[xf]=linprog(c,a2,b2,a1,b1,v1)z=356000-f甲(3000)乙(2000)丙(1000)A/452400800800B/35000C/256001200200第二十九页，共六十页，编辑于2023年，星期三II:通过广告增加销售(1元广告费：增加10桶销售)决策变量：目标：甲(3000+)乙(2000+)丙(1000+)A/45X1X2X3B/35X4X5X6C/25广告销售X7X103000+10X10X8X112000+10X11X9X121000+10X12约束：总利润最大需求限制；原料限制；产量限制；含量限制；非负限制第三十页，共六十页，编辑于2023年，星期三含量限制非负限制产量限制原料限制需求限制约束第三十一页，共六十页，编辑于2023年，星期三总盈利：287750元c=[4949493939392929 29 -699 -599 -499];a1=[10 01 0 0 1 0 0-10 00;01 00 1 0 0 1 00-100;00 10 0 1 0 0 10 0-10];a2=[1 1 1 0 0 0 00000 0;0 0 0 1 1 1 00000 0;0 0 0 0 0 0 11100 0;-12 0 0 -6 0 0 -800100 00;0 -12 0 0 -6 0 0-80 0 800;0 0 -12 0 0 -6 00-8 0 060;0.5 0 0 2 0 0 300 -10 00;0 0.5 0 0 2 0 030 0 -200;0 0 0.5 0 0 2 003 0 0-100 0 0 0 0 000 0 111];b1=[3000 2000 1000];b2=[5000 5000 5000 -30000 -16000 -600030004000 1000 800];v1=zeros(1,12);[xf]=linprog(c,a2,b2,a1,b1,v1)z=380000-f甲(3000)乙(2000)丙(1000)A/452121.82185.3692.9B/35695.54036.8267.6C/25广告182.703277.975039.40第三十二页，共六十页，编辑于2023年，星期三某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di(单位：吨）假设：料场和工地之间有直线道路五,非线形规划问题的解法及举例第三十三页，共六十页，编辑于2023年，星期三用例中数据计算，最优解为总吨公里数为136.2线性规划模型决策变量：cij(料场j到工地i的运量）~12维Shili084lin.m第三十四页，共六十页，编辑于2023年，星期三选址问题：NLP2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij

，在其它条件不变下使总吨公里数最小。决策变量：cij，(xj,yj)~16维非线性规划模型结果：总吨公里数为85.3，但局部最优解问题严重Shili084.m:shili084fun.m第三十五页，共六十页，编辑于2023年，星期三决策变量：ci，(xj,yj)~10维计算方法的改善局部最优解问题有所改进第三十六页，共六十页，编辑于2023年，星期三+为工地,数字为用量;*为新料场,数字为供应量。第三十七页，共六十页，编辑于2023年，星期三约束非线性规划情形标准模型fmincon语句的具体用法[x,fval,exitflag,output]=fmincon(@fun,x0,A,b,Aeq,beq,lb,ub,@con)第三十八页，共六十页，编辑于2023年，星期三①建立m文件函数

function[f,G]=fun(x)f=f(x);G=[G1(x),G2(x)];②选项options

输出参数options(8)=目标函数最优值；输入参数options(13)=等式约束的个数(m)；③L，U是决策变量的下界和上界；2、fmincon语句的具体用法第三十九页，共六十页，编辑于2023年，星期三maxf(x)=x12+

x22-x1x2-2x1-5x2s.t.-(x1–1)2+x2≥02

x1-3x2+6≥0,x0=[0,1]例2fmincon语句的具体用法转化成标准形minf(x)=-x12-x22+x1x2+2x1+5x2s.t.(x1–1)2-x2≤0-2

x1+3x2–6≤0,x0=[0,1]第四十页，共六十页，编辑于2023年，星期三①functionf=fun22(x)f=-x(1)^2-x(2)^2+x(1)*x(2)+2*x(1)+5*x(2);②function[G,Geq]=cont2(x)G=(x(1)-1)^2-x(2);Geq=[];③x0=[01];A=[-2,3];b=6;Aeq=[];beq=[];lb=[];ub=[];fun22[x,fval]=fmincon(@fun22,x0,A,b,Aeq,beq,lb,ub,@cont2)④x=1.0e+008*[-0.0006-2.7649]fval=-7.6432e+016fun22=

’

-x(1)^2-x(2)^2+x(1)*x(2)+2*x(1)+5*x(2)’fmincon语句的具体用法第四十一页，共六十页，编辑于2023年，星期三例fmincon语句的具体用法第四十二页，共六十页，编辑于2023年，星期三functionfm=ex02(x)n=10;c=[-6.089,-17.164,-34.054,-5.914,-24.721,-14.986,-24.1,-10.708,-26.662,-22.179];sx=0;fori=1:nsx=sx+x(i);%endfm=0;fori=1:nfm=fm+x(i)*(c(i)+log(x(i)/sx));end1)

建立目标函数ex02.m第四十三页，共六十页，编辑于2023年，星期三供应与选址

某公司有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第四十四页，共六十页，编辑于2023年，星期三

（2）为进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量仍各为20吨，问应建在何处，节省的吨千米数有多大？供应与选址第四十五页，共六十页，编辑于2023年，星期三范例：供应与选址(a1,b1),d1=3(a2,b2),d2=5(a6,b6),d6=11A(x1,y1)e1=20B(x2,y2)e2=20x11x12x16……x21x26x22目标：使得吨公里min第四十六页，共六十页，编辑于2023年，星期三建立规划模型

记工地的位置为(ai,bi)，水泥日用量为di,i=1,…,6,料场位置为(xj,yj),日储量为ej,j=1,2；从料场j向工地运送量为xij（决策变量）。20吨第四十七页，共六十页，编辑于2023年，星期三①当料场位置为(xi,yi)为已知时,上述模型为线性规划模型。从料场i向工地运送量为xij（决策变量）。②当料场位置为(xi,yi)为未知时,上述模型为非线性规划模型。对决策变量(xi,yi)而言。如何求解？第四十八页，共六十页，编辑于2023年，星期三其中a，b，d，e

都是常数向量（数组）。①当料场位置为(xj,yj)为已知时,上述模型为线性规划模型。从料场j向工地运送量为xij（决策变量）。思考：矩阵形式第四十九页，共六十页，编辑于2023年，星期三②当料场位置为(xi,yi)为未知时,上述模型为非线性规划模型。对决策变量(xi,yi)而言。线性规划求解结果：最优目标值f=136.23（吨千米）j123456x1j(料场A)350701x2j(料场B)0040610程序liaocx.m第五十页，共六十页，编辑于2023年，星期三function[f,g]=liaoch(x)a=[1.258.750.55.7537.25];b=[1.250.754.7556.57.75];d=[3547611];e=[2020];f1=0;forj=1:6s(j)=sqrt((x(13)-a(j))^2+(x(14)-b(j))^2);f1=f1+s(j)*x(j);%A(x13,x14)到各工地的吨公里数endf2=0;第五十一页，共六十页，编辑于2023年，星期三fori=7:12s(i)=sqrt((x(15)-a(i-6))^2+(x(16)-b(i-6))^2);f2=f2+s(i)*x(i);%B(x15,x16)到各工地的吨公里数endf=f1+f2;%总的目标函数fori=1:6g(i)=x(i)+x(i+6)-d(i);%第一组约束条件endg(7)=sum(x(1:6))-e(1);g(8)=sum(x(7:12))-e(2);%第二组约束条件第五十二页，共六十页，编辑于2023年，星期三x0=[ones(1,12)];L=zeros(1,12);opt(13)=6;[x,opt]=constr('liaoch',x0,opt,L)f=opt(8),n=opt(10)MATLAB运行程序(liaochj.m)i123456ABCi1(料场A)0507085.906x3xCi2(料场B)3040635.073y6.5y计算结果：最优目标值f=93.14（吨千米）新料场位置的改变，