第10讲 线性规划(new).ppt

1、数学建模方法及其应用,韩中庚 编著,数 学 建 模 教 学 片,第十章 线性规划方法,设计制作：,主要内容,第十章 线性规划方法,3,2020年8月5日,线性规划的一般模型；,线性规划解的概念与理论；,线性规划的求解方法；,线性规划的软件求解方法；,线性规划的应用案例分析。,一、线性规划的一般模型,4,2020年8月5日,每种资源的拥有量和每种产品所消耗的资源量，以及单位产品的利润如下表，试问如何安排生产计划使得该企业获利最大?,1. 问题的提出,5,2020年8月5日,一、线性规划的一般模型,1. 问题的提出,6,2020年8月5日,2 .线性规划模型的一般形式,一、线性规划的一般模型,7,

2、2020年8月5日,3 .线性规划模型的标准型,一、线性规划的一般模型,标准化方法：,8,2020年8月5日,二、线性规划解的概念与理论,（1）解：,1 .线性规划解的概念,9,2020年8月5日,1. 线性规划解的概念,（2）基,10,2020年8月5日,1. 线性规划解的概念,（4）基可行解：满足非负约束条件的基解称为基可行解。,（5）可行基：对应于基可行解的基称为可行基。,11,2020年8月5日,2 、线性规划解的基本理论,定理3 （1）如果线性规划问题的可行域有界，则问题的最优解一定在可行域的顶点上达到。 （2）如果线性规划问题的可行域有无界，则问题可能无最优解；若有最优解也一定在可

3、行域的某个顶点上达到。,二、线性规划解的概念与理论,12,2020年8月5日,1、单纯形法的基本思想,三、线性规划的求解方法,寻求问题的一个基可行解(即可行域的顶点)；检查该基可行解是否为最优解；如果不是，则设法再求另一个没有检查过的基可行解,如此进行下去,直到得到某一个基可行解为最优解为止。 现在要解决的问题： （1)如何求出第一个基可行解？ （2)如何判断基可行解是否为最优解？ （3)如何由一个基可行解过渡到另一个基可行解？,2、线性规划的MATLAB求解,三、线性规划的求解方法,用MATLAB求解线性规划模型,13,2020年8月5日,MATLAB(Matrix Laboratory)的

4、基本含义是矩阵实验室； 它是由美国MathWorks公司研制开发的一套高性能的基数值计算、信息处理、图形显示等于一体的可视化数学工具软件。,用MATLAB求解线性规划模型,14,2020年8月5日,MATLAB的优化工具箱(Optimization toolbox)，它的基本功能： (1) 求解线性规划和二次规划问题； (2) 求解无约束条件非线性规划的极小值问题； (3) 求解带约束条件非线性规划极小值问题； (4) 求解非线性方程组； (5) 求解带约束约束的线性最小二乘问题； (6) 求解非线性最小二乘逼近和曲线拟合问题.,用MATLAB求解线性规划模型,15,2020年8月5日,应用M

5、ATLAB优化工具箱中的函数linprog来求解线性规划问题，要求线性规划模型化为统一的基本模型：,用MATLAB求解线性规划模型,16,2020年8月5日,x=linprog(C,A1,b1,A2,b2)； 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.,用MATLAB求解线性规划模型,17,2020年8月5日,x,fv=linprog()； 要求返回目标函数

6、值 x,fv,ef=linprog()；要求返回程序结束标志 x,fv,ef,out=linprog()； 要求返回程序的优化信息 x,fv,ef,out,lambda=linprog()； 要求返回在程序停止时的拉格朗日乘子,用MATLAB求解线性规划模型,18,2020年8月5日,LINGO(Linear Interactive and General Optimizer )的基本含义是交互式的线性和通用优化求解器 它是美国芝加哥大学的 Linus Schrage 教授于1980年开发了一套用于求解最优化问题的工具包，后来经过完善成何扩充，并成立了LINGO SYSTEM INC,3、线性

7、规划的LINGO解法,三、线性规划的求解方法,19,2020年8月5日,LINGO功能：求解线性规划、二次规划、非线性规划、目标规划、图论与网络优化、整数规划的求解，以及一些线性和非线性方程(组)、最大最小和排队论中的最优化问题求解等,用LINGO求解线性规划模型,20,2020年8月5日,LINGO的特色： 它允许优化模型中的决策变量为整数，即可以求解整数规划，而且执行速度快 求解线性和非线性优化问题的简易工具 LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，,用LINGO求解线性规划模型,21,2020年8月5日,用LINGO求解线性规划模型,22,2020年8月5日,

8、数 据 段,集 合 段,目标 约束,用LINGO求解线性规划模型,23,2020年8月5日,24,2020年8月5日,1、合理下料问题,四、线性规划的应用案例分析,(1)问题的提出：某单位需要加工制作100套工架，每套工架需用长为2.9米，2.1米和1.5米的圆钢各一根。已知原材料长7.4米，现在的问题是如何下料使得所用的原材料最省？,25,2020年8月5日,模型分析:在每一根原材料上各一根截取2.9米，2.1米和1.5米的圆钢做成一套工架，每根原材料剩下料头0.9米，要完成100套工架，就需要用100根原材料，共剩余90米料头。,案例1:合理下料问题,26,2020年8月5日,案例1:合理

9、下料问题,A B C D E F,x1 x2 x3 x4 x5 x6,27,2020年8月5日,案例1:合理下料问题,28,2020年8月5日,案例1:合理下料问题,用MATLAB求解模型,问题的MATLAB程序: C=0, 0.1, 0.2, 0.3, 0.8; b1=0, 0, 0, 0, 0; b2=100, 100, 100; A1=-1,0,0,0,0;0,-1,0,0,0;0,0,-1,0,0; 0,0,0,-1,0;0,0,0,0,-1; A2=1,2,0,1,0;0,0,2,2,1;3,1,2,0,3; x, fv=linprog(C, A1, b1, A2, b2),29,2

10、020年8月5日,案例1:合理下料问题,用LINGO求解模型,30,2020年8月5日,案例1:合理下料问题,用LINGO求解模型,某投资公司拟制定今后五年的投资计划，初步考虑下面的四个投资项目：,2、连续投资问题,四、线性规划的应用案例分析,31,2020年8月5日,问题: 现有投资金额100万元，如何使得第五年年末能够获得最大的利润。,2、连续投资问题,四、线性规划的应用案例分析,32,2020年8月5日,案例2:连续投资问题,33,2020年8月5日,第1年：将100万元资金全部用于项目A和项目D的投资，即,案例2:连续投资问题,34,2020年8月5日,案例2:连续投资问题,35,20

11、20年8月5日,案例2:连续投资问题,36,2020年8月5日,案例2:连续投资问题,连续投资问题的数学模型:,37,2020年8月5日,MODEL: sets: row/1.5/; arrange/1.4/; link(row,arrange):c,x; endsets data: 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; enddata OBJmax=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,

12、4)=0; -1.15*x(1,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)=0;); END,案例2:连续投资问题,用LINGO求解模型,38,2020年8月5日,问题的连续投资方案： 第1年：项目A为716981.1元和项目D为283018.9元 第2年：项目C的投资金额为300000元， 第3年：项目A的投资为424528.3元和项目B为400000元， 第5年：投资项目D的金额为48820

13、7.5。 第5年年末该公司拥有总资金为1437500元，即收益率为43.75%。,案例2:连续投资问题,39,2020年8月5日,40,2020年8月5日,3、南水北调水指标分配问题,四、线性规划的应用案例分析,南水北调中线工程建成后，预计2010年年调水量为110亿立方米，主要用来解决京、津、冀、豫四省（市）的沿线20个大中城市的生活用水、工业用水和综合服务业的用水，分配比例分别为40、38和22 这样可以改善我国中部地区的生态环境和投资环境，推动经济发展用水指标的分配总原则是：改善区域的缺水状况、提高城市的生活水平、促进经济发展、提高用水效益、改善城市环境,41,2020年8月5日,要研究的问题是： （1）请你综