理学建模线性规划.pptx

《理学建模线性规划.pptx》由会员分享，可在线阅读，更多相关《理学建模线性规划.pptx（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性规划方法线性规划方法线性规划方法线性规划方法1线性规划的一般模型；线性规划解的概念与理论；线性规划的求解方法；线性规划的软件求解方法；线性规划的应用案例分析。第1页/共44页2 线性规划研究的是线性目标函数在线性约束条件下的最值问题，在管理科学中有着广泛的应用。第十章第十章 线性规划方法线性规划方法 线性规划的两类重要的实际问题：（1）给定一定数量的人力、物力资源，问怎样安排运用这些资源，能使完成的任务量最大，或收到的效益最大；（2）给定一项任务，问怎样统筹安排，能使完成这项任务所耗费的人力、物力资源最少。第2页/共44页 一、线性规划的一般模型3每种资源的拥有量和每种产品所消耗的资源量，

2、以及单位产品的利润如下表，试问如何安排生产计划使得该企业获利最大?1.问题的提出第3页/共44页4 一、线性规划的一般模型 1.问题的提出第4页/共44页5 一、线性规划的一般模型 1.问题的提出该模型的特点：（1）用一组决策变量表示某一方案，这组决策变量的值就代表一个具体方案，一般这些变量取值是非负的；（2）存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示；（3）有一个要求达到的目标，它可用决策变量的线性函数（即目标函数）来表示，按问题的不同，要求目标函数实现最大化或最小化。第5页/共44页6 2.线性规划模型的一般形式 一、线性规划的一般模型第6页/共44页7 3.线性

3、规划模型的标准型 一、线性规划的一般模型标准化方法：第7页/共44页8二、线性规划解的概念与理论（1）解：1.线性规划解的概念第8页/共44页9 1.线性规划解的概念（2）基第9页/共44页10 1.线性规划解的概念（4）基可行解：满足非负约束条件的基解称为基可行解。（5）可行基：对应于基可行解的基称为可行基。基解和基可行解实例第10页/共44页11 1.线性规划解的概念几种解的关系：可行解基可行解基解第11页/共44页12 2、线性规划解的基本理论 定理3 （1）如果线性规划问题的可行域有界，则问题的最优解一定在可行域的顶点上达到。（2）如果线性规划问题的可行域有无界，则问题可能无最优解；若

4、有最优解也一定在可行域的某个顶点上达到。二、线性规划解的概念与理论图解法.ppt图解法第12页/共44页13 1、单纯形法的基本思想三、线性规划的求解方法 寻求问题的一个基可行解(即可行域的顶点)；检查该基可行解是否为最优解；如果不是，则设法再求另一个没有检查过的基可行解,如此进行下去,直到得到某一个基可行解为最优解为止。单纯形法实例现在要解决的问题：（1)如何求出第一个基可行解？（2)如何判断基可行解是否为最优解？（3)如何由一个基可行解过渡到另一个基可行解？第13页/共44页 2、线性规划的MATLAB求解三、线性规划的求解方法14第14页/共44页MATLAB(Matrix Labora

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

6、模型16第16页/共44页LINGO(Linear Interactive and General Optimizer)的基本含义是交互式的线性和通用优化求解器它是美国芝加哥大学的 Linus Schrage 教授于1980年开发了一套用于求解最优化问题的工具包，后来经过完善成何扩充，并成立了LINGO SYSTEM INC 3、线性规划的LINGO解法三、线性规划的求解方法17第17页/共44页 LINGO功能：求解线性规划、二次规划、非线性规划、目标规划、图论与网络优化、整数规划的求解，以及一些线性和非线性方程(组)、最大最小和排队论中的最优化问题求解等 用用LINGOLINGO求解线性规

7、划模型求解线性规划模型18第18页/共44页 LINGO的特色：它允许优化模型中的决策变量为整数，即可以求解整数规划，而且执行速度快求解线性和非线性优化问题的简易工具LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，用用LINGOLINGO求解线性规划模型求解线性规划模型19第19页/共44页用用LINGOLINGO求解线性规划模型求解线性规划模型20第20页/共44页数据段集合段目标约束用用LINGOLINGO求解线性规划模型求解线性规划模型21第21页/共44页22四、线性规划的应用案例分析四、线性规划的应用案例分析四、线性规划的应用案例分析四、线性规划的应用案例分析 一

8、般讲，一个应用问题凡满足一下条件时，才能建立线性规划模型（1）要求解问题的目标函数能用数值指标来反映且为线性函数；（2）存在多种方案；（3）要求达到的目标是在一定约束条件下实现的，这些约束条件可以用线性等式或不等式来描述。第22页/共44页23 1、合理下料问题四、线性规划的应用案例分析(1)问题的提出：某单位需要加工制作100套工架，每套工架需用长为2.9米，2.1米和1.5米的圆钢各一根。已知原材料长7.4米，现在的问题是如何下料使得所用的原材料最省？7.4m2.9m2.1m1.5m第23页/共44页24模型分析:在每一根原材料上各一根截取2.9米，2.1米和1.5米的圆钢做成一套工架，每

9、根原材料剩下料头0.9米，要完成100套工架，就需要用100根原材料，共剩余90米料头。7.4m2.9m2.1m1.5m0.9m第24页/共44页257.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.5mABCDEFx1x2x3x4x5x6第25页/共44页 决策变量：按第i i种模式切割的原料钢管根数（i=1,2,6i=1,2,6）模式模式2.9米根数米根数2.1米根数米根数1.5米根数米根数余料余料11030（米）（米）22010

10、.1（米）（米）30220.2（米）（米）41200.3（米）（米）50130.8（米）（米）61110.9（米）（米）需求需求100100100第26页/共44页27决策目标：所用的原材料最省，而最省可以有两种标准，一是切割后总余料量最小，二是切割原材料的总根数最少，按照这两种标准建立数学模型如下：第27页/共44页28第28页/共44页29 用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,

11、-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页/共44页30 用LINGO求解模型（以余料最小为目标）MODEL:SETS:ROW/1,2,3/:B;ARRANGE/1.5/:X,C;LINKS(ROW,ARRANGE):A;ENDSETSDATA:B=100,100,100;C=0,0.1,0.2,0.3,0.8;A=1,2,0,1,0,0,0,2,2,1,3,1,2,0,3;ENDDATAOBJMIN=SUM(ARRANGE(J):C(J)*X(J););FOR(ROW(I):SUM(ARRANGE(J

12、):A(I,J)*X(J)=B(I););FOR(ARRANGE(J):X(J)=0;);END第30页/共44页31 用LINGO求解模型第31页/共44页某投资公司拟制定今后五年的投资计划，初步考虑下面的四个投资项目：2、连续投资问题四、线性规划的应用案例分析32第32页/共44页问题:现有投资金额100万元，如何使得第五年年末能够获得最大的利润。2、连续投资问题四、线性规划的应用案例分析33第33页/共44页 年份年份项目目12345Ax11x21x31x41Bx32Cx23Dx14x24x34x44x5434第34页/共44页第1年：将100万元资金全部用于项目A和项目D的投资，即35

13、第35页/共44页36第36页/共44页37第37页/共44页连续投资问题的数学模型:38第38页/共44页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,1)-1.06*x(2,4)+

14、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求解模型39第39页/共44页问题的连续投资方案：第1年：项目A为716981.1元和项目D为283018.9元第2年：项目C的投资金额为300000元，第3年：项目B的投资为400000元和项目D为424528.3元，第4年：投资项目A的金额为450000元。第5年年末该公司拥有总资金为1437500元，即收益率为43.75%。4

15、0第40页/共44页41 3、南水北调水指标分配问题四、线性规划的应用案例分析 南水北调中线工程建成后，预计2010年年调水量为110亿立方米，主要用来解决京、津、冀、豫四省（市）的沿线20个大中城市的生活用水、工业用水和综合服务业的用水，分配比例分别为40、38和22 这样可以改善我国中部地区的生态环境和投资环境，推动经济发展用水指标的分配总原则是：改善区域的缺水状况、提高城市的生活水平、促进经济发展、提高用水效益、改善城市环境第41页/共44页42要研究的问题是：（1）请你综合考虑各种情况,给出2010年每个城市的调水分配指标,使得各城市的总用水情况尽量均衡（2）由于各城市的基本状况和自然条件不同，对相同的供水量所产生的经济效益不同，请从经济效益的角度，给出调水指标的分配方案但是，要注意到，每个城市的工业和综合服务业的发展受产业规模的限制，不可能在短时间内无限制的增长 3、南水北调水指标分配问题四、线性规划的应用案例分析(详细情况见教材!)第42页/共44页Thanks！Mathematical modeling cannot be learned by reading books or listening to lectures,but only by doing!-Practice!第十章第十章 线性规划方法线性规划方法第43页/共44页感谢您的观看！第44页/共44页