第10讲线性规划方法

数学建模方法及其应用韩中庚编著数学建模教学片第十章线性规划方法设计制作：主要内容

第十章线性规划方法32023年2月1日线性规划的一般模型；线性规划解的概念与理论；线性规划的求解方法；线性规划的软件求解方法；线性规划的应用案例分析。

一、线性规划的一般模型42023年2月1日每种资源的拥有量和每种产品所消耗的资源量，以及单位产品的利润如下表，试问如何安排生产计划使得该企业获利最大?1.问题的提出52023年2月1日

一、线性规划的一般模型1.问题的提出62023年2月1日2.线性规划模型的一般形式

一、线性规划的一般模型72023年2月1日3.线性规划模型的标准型

一、线性规划的一般模型标准化方法：82023年2月1日二、线性规划解的概念与理论（1）解：1.线性规划解的概念92023年2月1日

1.线性规划解的概念（2）基102023年2月1日

1.线性规划解的概念（4）基可行解：满足非负约束条件的基解称为基可行解。（5）可行基：对应于基可行解的基称为可行基。112023年2月1日

2、线性规划解的基本理论定理3

（1）如果线性规划问题的可行域有界，则问题的最优解一定在可行域的顶点上达到。（2）如果线性规划问题的可行域有无界，则问题可能无最优解；若有最优解也一定在可行域的某个顶点上达到。二、线性规划解的概念与理论122023年2月1日

1、单纯形法的基本思想三、线性规划的求解方法

寻求问题的一个基可行解(即可行域的顶点)；检查该基可行解是否为最优解；如果不是，则设法再求另一个没有检查过的基可行解,如此进行下去,直到得到某一个基可行解为最优解为止。现在要解决的问题：（1)如何求出第一个基可行解？（2)如何判断基可行解是否为最优解？（3)如何由一个基可行解过渡到另一个基可行解？

2、线性规划的MATLAB求解三、线性规划的求解方法用MATLAB求解线性规划模型132023年2月1日

MATLAB(MatrixLaboratory)的基本含义是矩阵实验室；它是由美国MathWorks公司研制开发的一套高性能的基数值计算、信息处理、图形显示等于一体的可视化数学工具软件。用MATLAB求解线性规划模型142023年2月1日MATLAB的优化工具箱(Optimizationtoolbox)，它的基本功能：(1)求解线性规划和二次规划问题；(2)求解无约束条件非线性规划的极小值问题；

(3)求解带约束条件非线性规划极小值问题；

(4)求解非线性方程组；

(5)求解带约束约束的线性最小二乘问题；

(6)求解非线性最小二乘逼近和曲线拟合问题.用MATLAB求解线性规划模型152023年2月1日应用MATLAB优化工具箱中的函数linprog来求解线性规划问题，要求线性规划模型化为统一的基本模型：用MATLAB求解线性规划模型162023年2月1日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求解线性规划模型172023年2月1日[x,fv]=linprog(……)；％要求返回目标函数值[x,fv,ef]=linprog(……)；％要求返回程序结束标志[x,fv,ef,out]=linprog(……)；％要求返回程序的优化信息．[x,fv,ef,out,lambda]=linprog(……)；％要求返回在程序停止时的拉格朗日乘子．用MATLAB求解线性规划模型182023年2月1日

LINGO(LinearInteractiveandGeneralOptimizer)的基本含义是交互式的线性和通用优化求解器．

它是美国芝加哥大学的LinusSchrage教授于1980年开发了一套用于求解最优化问题的工具包，后来经过完善成何扩充，并成立了LINGO

SYSTEMINC．

3、线性规划的LINGO解法三、线性规划的求解方法192023年2月1日

LINGO功能：求解线性规划、二次规划、非线性规划、目标规划、图论与网络优化、整数规划的求解，以及一些线性和非线性方程(组)、最大最小和排队论中的最优化问题求解等．用LINGO求解线性规划模型202023年2月1日

LINGO的特色：它允许优化模型中的决策变量为整数，即可以求解整数规划，而且执行速度快．

求解线性和非线性优化问题的简易工具．

LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，用LINGO求解线性规划模型212023年2月1日用LINGO求解线性规划模型222023年2月1日数据段集合段目标约束用LINGO求解线性规划模型232023年2月1日242023年2月1日

1、合理下料问题四、线性规划的应用案例分析

(1)问题的提出：某单位需要加工制作100套工架，每套工架需用长为2.9米，2.1米和1.5米的圆钢各一根。已知原材料长7.4米，现在的问题是如何下料使得所用的原材料最省？7.4m2.9m2.1m1.5m252023年2月1日

模型分析:在每一根原材料上各一根截取2.9米，2.1米和1.5米的圆钢做成一套工架，每根原材料剩下料头0.9米，要完成100套工架，就需要用100根原材料，共剩余90米料头。

7.4m2.9m2.1m1.5m0.9m案例1:合理下料问题262023年2月1日案例1:合理下料问题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.5mABCDEFx1

x2x3x4x5x6272023年2月1日案例1:合理下料问题282023年2月1日案例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)292023年2月1日案例1:合理下料问题

用LINGO求解模型302023年2月1日案例1:合理下料问题

用LINGO求解模型

某投资公司拟制定今后五年的投资计划，初步考虑下面的四个投资项目：AB

2、连续投资问题四、线性规划的应用案例分析312023年2月1日问题:

现有投资金额100万元，如何使得第五年年末能够获得最大的利润。CD

2、连续投资问题四、线性规划的应用案例分析322023年2月1日年份项目12345Ax11x21x31x41Bx32Cx23Dx14x24x34x44x54案例2:连续投资问题332023年2月1日第1年：将100万元资金全部用于项目A和项目D的投资，即案例2:连续投资问题342023年2月1日案例2:连续投资问题352023年2月1日案例2:连续投资问题362023年2月1日案例2:连续投资问题连续投资问题的数学模型:372023年2月1日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;enddata[OBJ]max=@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)+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)<=300000;@for(link(i,j):x(i,j)>=0;);END案例2:连续投资问题

用LINGO求解模型382023年2月1日问题的连续投资方案：第1年：项目A为716981.1元和项目D为283018.9元第2年：项目C的投资金额为300000元，第3年：项目A的投资为424528.3元和项目B为400000元，第5年：投资项目D的金额为488207.5。第5年年末该公司拥有总资金为1437500元，即收益率为43.75%。案例2:连续投资问题392023年2月1日402023年2月1日

3、南水北调水指标分配问题四、线性规划的应用案例分析南水北调中线工程建成后，预计2010年年调水量为110亿立方米，主要用来解决京、津、冀、豫四省（市）的沿线20个大中城市的生活用水、工业用水和综合服务业的用水，分配比例分别为40％、38％和22％．这样可以改善我国中部地区的生态环境和投资环境，推动经济发展．用水指标的分配总原则是：改善区域的缺水状况、提高城市的生活水平、促进经济发展、提高用水效益、改善城市环境．41