数学建模实用教程课件第4章-最优化模型-PPT课件

1、2022/7/20数学建模实用教程高教出版社12022/7/20数学建模实用教程高教出版社2第4章 最优化模型 二次规划模型； 整数规划模型； 综合案例分析。主要内容 非线性规划模型； 线性规划模型； 2022/7/20数学建模实用教程高教出版社3一、线性规划模型 1. 问题的提出2022/7/20数学建模实用教程高教出版社4一、线性规划模型 1. 问题的提出2022/7/20数学建模实用教程高教出版社5一、线性规划模型 2. 线性规划模型的一般形式2022/7/20数学建模实用教程高教出版社6一、线性规划模型 3. 线性规划解的概念（1）解：2022/7/20数学建模实用教程高教出版社7一、

2、线性规划模型 3. 线性规划解的概念（1）解的基本性质：2022/7/20数学建模实用教程高教出版社8一、线性规划模型 4. 线性规划的求解方法（1）用MATLAB软件求解MATLAB(Matrix Laboratory)的基本含义是矩阵实验室； 它是由美国MathWorks公司研制开发的一套高性能的基数值计算、信息处理、图形显示等于一体的可视化数学工具软件。2022/7/20数学建模实用教程高教出版社9一、线性规划模型 4. 线性规划的求解方法（1）用MATLAB软件求解 MATLAB的优化工具箱(Optimization toolbox)，它的基本功能： (1) 求解线性规划和二次规划问题

3、； (2) 求解无约束条件非线性规划的极小值问题； (3) 求解带约束条件非线性规划极小值问题； (4) 求解非线性方程组； (5) 求解带约束的线性最小二乘问题； (6) 求解非线性最小二乘逼近和曲线拟合问题.2022/7/20数学建模实用教程高教出版社10一、线性规划模型 4. 线性规划的求解方法（1）用MATLAB软件求解应用MATLAB优化工具箱中的函数linprog来求解线性规划问题，要求线性规划模型化为统一的基本模型：2022/7/20数学建模实用教程高教出版社11一、线性规划模型 4. 线性规划的求解方法（1）用MATLAB软件求解x=linprog(C,A1,b1,A2,b2)

4、；x=linprog(C,A1,b1,A2,b2,x1,x2)；x=linprog(C,A1,b1,A2,b2,x1,x2,opt)； % 设置可选参数值，而不是采用缺省值x=linprog(C,A1,b1,A2,b2,x1,x2,x0,opt)； % x0为初始解，缺省值为0.2022/7/20数学建模实用教程高教出版社12一、线性规划模型 4. 线性规划的求解方法（1）用MATLAB软件求解x,fv=linprog()； 要求返回目标函数值x,fv,ef=linprog()； 要求返回程序结束标志x,fv,ef,out=linprog()； 要求返回程序的优化信息x,fv,ef,out,l

5、ambda=linprog()； 要求返回在程序停止时的拉格朗日乘子2022/7/20数学建模实用教程高教出版社13一、线性规划模型 4. 线性规划的求解方法（2）用Lingo软件求解LINGO(Linear INteractive and General Optimizer )的基本含义是交互式的线性和通用优化求解器 LINDO(Linear, INteractive, and Discrete Optimizer)的基本含义是交互式的线性和混合优化求解器它是美国芝加哥大学的 Linus Schrage 教授于1980年开发了一套用于求解最优化问题的工具包，后来经过完善和扩充，并成立了LIN

6、DO SYSTEM INC2022/7/20数学建模实用教程高教出版社14一、线性规划模型 4. 线性规划的求解方法（2）用Lingo软件求解LINGO(Linear INteractive and General Optimizer )的基本含义是交互式的线性和通用优化求解器 LINDO(Linear, INteractive, and Discrete Optimizer)的基本含义是交互式的线性和混合优化求解器它是美国芝加哥大学的 Linus Schrage 教授于1980年开发了一套用于求解最优化问题的工具包，后来经过完善和扩充，并成立了LINDO SYSTEM INC2022/7/2

7、0数学建模实用教程高教出版社15一、线性规划模型 4. 线性规划的求解方法（2）用Lingo软件求解 LINGO功能：求解线性规划、二次规划、非线性规划、目标规划、图论与网络优化、整数规划的求解，以及一些线性和非线性方程(组)、最大最小和排队论中的最优化问题求解等 2022/7/20数学建模实用教程高教出版社16一、线性规划模型 4. 线性规划的求解方法（2）用Lingo软件求解 LINGO的特色：它允许优化模型中的决策变量为整数，即可以求解整数规划，而且执行速度快求解线性和非线性优化问题的简易工具LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题,利用LINGO高效的求解器可

8、快速求解并分析结果.2022/7/20数学建模实用教程高教出版社17一、线性规划模型 4. 线性规划的求解方法（2）用Lingo软件求解哇！Lingo软件是你正确的选择！2022/7/20数学建模实用教程高教出版社18一、线性规划模型 4. 线性规划的求解方法集合段数据段目标约束2022/7/20数学建模实用教程高教出版社19一、线性规划模型 5. 线性规划的应用举例（1）下料问题7.4m2.9m2.1m1.5m 问题的提出：某单位需要加工制作100套工架，每套工架需用长为2.9米，2.1米和1.5米的圆钢各一根。已知原材料长7.4米，现在的问题是如何下料使得所用的原材料最省？2022/7/2

9、0数学建模实用教程高教出版社20一、线性规划模型 （1）下料问题 模型分析:在每一根原材料上各一根截取2.9米，2.1米和1.5米的圆钢做成一套工架，每根原材料剩下料头0.9米，要完成100套工架，就需要用100根原材料，共剩余90米料头。 7.4m2.9m2.1m1.5m0.9m2022/7/20数学建模实用教程高教出版社21一、线性规划模型7.4m2.9m2.1m1.5m0.9m2.9m1.5m1.5m1.5m2.9m2.9m0.1m1.5m2.9m2.1m2.1m0.3m2.1m2.1m1.5m0.2m1.5m2.1m1.5m0.8m1.5m1.5mx1x2x3x4x5x6ABCDEF2

10、022/7/20数学建模实用教程高教出版社22一、线性规划模型 （1）下料问题哇！这样分析就好建立数学模型了！2022/7/20数学建模实用教程高教出版社23一、线性规划模型 （1）下料问题2022/7/20数学建模实用教程高教出版社24一、线性规划模型 （1）下料问题 用Lingo软件求解2022/7/20数学建模实用教程高教出版社25一、线性规划模型 （1）下料问题2022/7/20数学建模实用教程高教出版社26一、线性规划模型 （1）下料问题 用MATLAB软件求解问题的MATLAB程序:C=0, 0.1, 0.2, 0.3, 0.8,0.9; b1=0, 0, 0, 0, 0,0;b2

11、=100, 100, 100;A1=-1,0,0,0,0,0;0,-1,0,0,0,0;0,0,-1,0,0,0; 0,0,0,-1,0,0;0,0,0,0,-1,0;0,0,0,0,0,-1;A2=1,2,0,1,0,1;0,0,2,2,1,1;3,1,2,0,3,1; x, fv=linprog(C, A1, b1, A2, b2)2022/7/20数学建模实用教程高教出版社27一、线性规划模型 （2）连续投资问题某投资公司拟制定今后五年的投资计划，初步考虑下面的四个投资项目：AB2022/7/20数学建模实用教程高教出版社28一、线性规划模型 （2）连续投资问题CD问题: 现有投资金额1

12、00万元，如何使得第五年年末能够获得最大的利润。2022/7/20数学建模实用教程高教出版社29一、线性规划模型 （2）连续投资问题 年份项目12345Ax11x21x31x41Bx32Cx23Dx14x24x34x44x542022/7/20数学建模实用教程高教出版社30一、线性规划模型 （2）连续投资问题第1年：将100万元资金全部用于项目A和项目D的投资，即2022/7/20数学建模实用教程高教出版社31一、线性规划模型 （2）连续投资问题2022/7/20数学建模实用教程高教出版社32一、线性规划模型 （2）连续投资问题2022/7/20数学建模实用教程高教出版社33一、线性规划模型

13、（2）连续投资问题连续投资问题的数学模型:2022/7/20数学建模实用教程高教出版社34一、线性规划模型 （2）连续投资问题MODEL:sets:row/1.5/; arrange/1.4/;link(row,arrange):c,x;endsetsdata: c=0,0,0,0, 0,0,1.40,0, 0,1.25,0,0, 1.15,0,0,0, 0,0,0,1.06; enddataOBJmax=sum(link(i,j):c(i,j)*x(i,j);x(1,1)+x(1,4)=1000000;-1.06*x(1,4)+x(2,1)+x(2,3)+x(2,4)=0;-1.15*x(1

14、,1)-1.06*x(2,4)+x(3,1)+x(3,2)+x(3,4)=0;-1.15*x(2,1)-1.06*x(3,4)+x(4,1)+x(4,4)=0;-1.15*x(3,1)-1.06*x(4,4)+x(5,4)=0;x(3,2)=400000;x(2,3)=0;);END 用LINGO求解模型2022/7/20数学建模实用教程高教出版社35一、线性规划模型 （2）连续投资问题问题的连续投资方案：第1年：项目A为716981.1元和项目D为283018.9元第2年：项目C的投资金额为300000元，第3年：项目B的投资为400000元和项目D的投资为424528.3元，第4年：投资项

15、目A的金额为450000元。第5年年末该公司拥有总资金为1437500元，即收益率为43.75%。 2022/7/20数学建模实用教程高教出版社36一、线性规划模型 （3）运输问题2022/7/20数学建模实用教程高教出版社37一、线性规划模型 （3）运输问题2022/7/20数学建模实用教程高教出版社38一、线性规划模型 （3）运输问题 用LINGO求解模型MODEL:sets:num_i/1.m/:a； num_j/1.n/:b； link(num_i,num_j):c,x；endsetsdata:a=a(1),a(2),a(m)； b=b(1),b(2),b(n)； c=c(1,1),c

16、(1,2),c(1,n)， c(2,1),c(2,2),c(2,n)， c(m,1),c(m,2),c(m,n)； enddataOBJmin =sum(link(i,j):c(i,j)*x(i,j)；for(num_i(i):sum(num_j(j):x(i,j)=a(i)；)；for(num_j(j):sum(num_i(i):x(i,j)=b(j)；)；for(link(i,j):x(i,j)=0；)；END2022/7/2039二、整数规划模型 1. 人员时间安排问题 某公司的营业时间是上午8点到22点，以2小时为一时段，各时段内所需的服务人员数如表。每个服务人员可在任一时段开始时上班

17、，但要连续工作8小时，而工资都相同。问应如何安排服务人员使公司所付工资总数最少。 序号时间区间需求人数18:0010:0020210:0012:0025312:0014:0010414:0016:0030516:0018:0020618:0020:0010720:0022:0052022/7/2040二、整数规划模型 1. 人员时间安排问题数学建模实用教程高教出版社2022/7/2041二、整数规划模型 2. 整数规划模型的一般形式数学建模实用教程高教出版社2022/7/2042二、整数规划模型 3. 整数规划模型的Lingo解法数据段集合段目标约束2022/7/2043二、整数规划模型 3.

18、 整数规划模型的Lingo解法MODEL:sets:num/1.4/:x；endsetsOBJmin=sum(num(i):x(i)；x(1)=20；x(1)+x(2)=25；x(1)+x(2)+x(3)=10；x(1)+x(2)+x(3)+x(4)=30；x(2)+x(3)+x(4)=20；x(3)+x(4)=10；x(4)=5；for(num(i):GIN(x(i)；x(i)=0；)；END数学建模实用教程高教出版社2022/7/2044二、整数规划模型 3. 整数规划模型的Lingo解法数学建模实用教程高教出版社第一时段开始工作人数为20人；第二时段开始工作人数为5人；第三时段开始工作人

19、数为10人；第四时段开始工作人数为5人；第五时段开始无需安排新的人员即该公司共需要40人2022/7/2045二、整数规划模型 4. 0-1整数规划模型数学建模实用教程高教出版社2022/7/2046二、整数规划模型 4. 0-1整数规划模型数学建模实用教程高教出版社2022/7/2047二、整数规划模型 4. 0-1整数规划模型数学建模实用教程高教出版社2022/7/2048二、整数规划模型 4. 0-1整数规划模型数学建模实用教程高教出版社 设2022/7/2049二、整数规划模型 4. 0-1整数规划模型数学建模实用教程高教出版社文体部 宣传部劳动部学习部甲6231乙7432丙81075

20、丁7854 试综合考虑四名候选人的情况，确定四个部长的最优选择方案 指派问题：某学校学生会准备在学生中选拔文体部、宣传部、劳动部、学习部四个部门的部长，经过层层筛选，最后剩下甲、乙、丙、丁四名候选人，根据各项考核与民主测评，四人主持各部的工作能力(量化为分值) 如表所示.2022/7/2050二、整数规划模型 4. 0-1整数规划模型数学建模实用教程高教出版社2022/7/2051二、整数规划模型 4. 0-1整数规划模型数学建模实用教程高教出版社2022/7/2052二、整数规划模型 4. 0-1整数规划模型数学建模实用教程高教出版社2022/7/2053二、整数规划模型 4. 0-1整数规

21、划模型数学建模实用教程高教出版社MODEL:sets:num_i/1.4/；num_j/1.4/；link(num_i,num_j):a,x；endsetsdata:a=6,2,3,1,7,4,3,2,8,10,7,5,7,8,5,4；enddataOBJ max =sum(link(i,j):a(i,j)*x(i,j)；for(num_i(i):sum(num_j(j): x(i,j)=1；)；for(num_j(j):sum(num_i(i): x(i,j)=1；)；for(link(i,j):BIN(x(i,j)；)；END 用LINGO求解模型2022/7/2054二、整数规划模型 4

22、. 0-1整数规划模型数学建模实用教程高教出版社最优分配方案是:甲去劳动部当部长，乙去文体部当部长，丙去宣传部当部长，丁去学习部当部长2022/7/2055三、二次规划模型 1. 二次规划模型的一般形式数学建模实用教程高教出版社2022/7/2056三、二次规划模型 2. 二次规划模型的Lingo解法数学建模实用教程高教出版社MODEL:sets:num_i/1.m/:b； !m 表示数组的维数，是具体的正整数；num_j/1.n/:x,c； !n 表示数组的维数，是具体的正整数；num_k/1.n/；link_ij(num_i,num_j)/:a；link_jk(num_j,num_k)/:

23、C；Endsetsdata: b=b(1),b(2),b(m)； !约束条件右端项的实际数值； c=c(1),c(2),c(n)； !目标函数的系数的实际数值； a=a(1,1),a(1,2),a(1,n), a(2,1),a(2,2),a(2,n), . . . . a(m,1),a(m,2),a(m,n)； !约束条件系数矩阵的实际数值； C=C(1,1),C(1,2),C(1,n), C(2,1),C(2,2),C(2,n), . . . . C(n,1),C(n,2),C(n,n)； !目标函数的系数的实际数值； enddatainit: x0=x0(1),x0(2),x0(n)； !

24、赋初始值； endinitOBJmax=sum(num_j(j):c(j)*x(j)+sum(link_jk(j,k):C(j,k)*x(j)*x(k)； for(num_i(i):sum(num_j(j):a(i,j)*x(j)=0；)； ENDMODEL:sets:num_i/1.m/:b； !m 表示数组的维数，是具体的正整数；num_j/1.n/:x,c； !n 表示数组的维数，是具体的正整数；num_k/1.n/；link_ij(num_i,num_j)/:a；link_jk(num_j,num_k)/:C；endsetsdata: b=b(1),b(2),b(m)； !约束条件右端

25、项的实际数值； c=c(1),c(2),c(n)； !目标函数的系数的实际数值； a=a(1,1),a(1,2),a(1,n), a(2,1),a(2,2),a(2,n), . . . . a(m,1),a(m,2),a(m,n)； !约束条件系数矩阵的实际数值； C=C(1,1),C(1,2),C(1,n), C(2,1),C(2,2),C(2,n), . . . . C(n,1),C(n,2),C(n,n)； !目标函数的系数的实际数值； enddata init: x0=x0(1),x0(2),x0(n)； !赋初始值； endinit OBJmax=sum(num_j(j):c(j)*

26、x(j)+sum(link_jk(j,k):C(j,k)*x(j)*x(k)； for(num_i(i):sum(num_j(j):a(i,j)*x(j)=0；)； END2022/7/2057三、二次规划模型 3. 产品生产销售计划问题数学建模实用教程高教出版社 某工厂生产的一种产品有甲、乙两种型号，厂长希望根据市场的需求，生产计划要保证产销平衡，争取获得更多的利润为此，请建模分析，该厂应该如何确定产品的生产计划（两种型号的产品各生产多少），使总的利润最大？2022/7/2058三、二次规划模型 3. 产品生产销售计划问题数学建模实用教程高教出版社2022/7/2059三、二次规划模型 3.

27、 产品生产销售计划问题数学建模实用教程高教出版社2022/7/2060三、二次规划模型 3. 产品生产销售计划问题数学建模实用教程高教出版社2022/7/2061三、二次规划模型 3. 产品生产销售计划问题数学建模实用教程高教出版社MODEL:sets:num_i/1,2/:x；endsetsOBJ max =98*x(1)+277*x(2)-x(1)2-0.3*x(1)*x(2)-2* x(2)2；x(1)+x(2)=100；x(1)=0；)；END 用LINGO求解模型2022/7/2062四、非线性规划模型 1. 非线性规划模型的一般形式数学建模实用教程高教出版社2022/7/2063四

28、、非线性规划模型 2. 非线性规划模型的Lingo解法数学建模实用教程高教出版社MODEL:sets:num_i/1.m/； !m 表示数组的维数，是具体的正整数；num_j/1.l/； !l 表示数组的维数，是具体的正整数；num_k/1.n/:x0,x； !n 表示数组的维数,是具体的正整数；endsetsinit:x0=x0(1),x0(2),x0(n)； !赋初始值；endinitOBJmin=f(x)； !目标函数的表达式；for(num_i(i):hi(x)=0；)； !等式约束条件；for(num_j(j):gj(x)=0；)； !不等式约束条件；for(num_k(k):x(k

29、)=0；)；END2022/7/2064四、非线性规划模型 3. 围墙圈地问题数学建模实用教程高教出版社 在长江沿岸有一个风景秀丽的小岛屿，某开发商承包下该小岛的开发权后，拟在该岛上建造一个度假村 在开发的过程中，按照惯例，要先用砖砌一个矩形围墙，以便存放建筑材料 在对岛上的旧建筑拆迁时，恰好留下了一批旧砖，可以利用这批旧砖来建造围墙，每块旧砖的长度是0.2m，厚度是0.05m，砖的总数量是24000块 在建造围墙时，要求围墙的高度不能低于2m， 围墙所圈地的面积越大越好 试问该如何来建造这个围墙？2022/7/2065四、非线性规划模型 3. 围墙圈地问题数学建模实用教程高教出版社2022/7/2066四、非线性规划模型 3. 围墙圈地问题数学建模实用教程高教出版社MODEL:OBJ max =x*y；2*(x+y)*z0；y0；z0；z=2；ENDSo easy！2022/7/2067五、综合案例分析 抢渡长江问题数学建模实用教程高教出版社 “渡江”是武汉城市的一张名片1934年9月9日，武汉警备旅官兵与体育界人士联手，在武汉第一次举办横渡长江游泳竞赛活动，起点为武昌汉阳门码头，终点设在汉口三北码头，全程约5000m有44人参加横渡，40人达到终点，张学良将军特意向冠军获得者赠送了一块银盾，上书“力挽狂澜” 2019年，“武汉抢渡长江挑战赛