线性规划(new)课件

主要内容线性规划方法1线性规划的一般模型；线性规划解的概念与理论；线性规划的求解方法；线性规划的软件求解方法；线性规划的应用案例分析。

线性规划研究的是线性目标函数在线性约束条件下的最值问题，在管理科学中有着广泛的应用。线性规划方法

线性规划的两类重要的实际问题：（1）给定一定数量的人力、物力资源，问怎样安排运用这些资源，能使完成的任务量最大，或收到的效益最大；（2）给定一项任务，问怎样统筹安排，能使完成这项任务所耗费的人力、物力资源最少。2

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

一、线性规划的一般模型1.问题的提出

一、线性规划的一般模型1.问题的提出

该模型的特点：（1）用一组决策变量表示某一方案，这组决策变量的值就代表一个具体方案，一般这些变量取值是非负的；（2）存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示；（3）有一个要求达到的目标，它可用决策变量的线性函数（即目标函数）来表示，按问题的不同，要求目标函数实现最大化或最小化。562.线性规划模型的一般形式

一、线性规划的一般模型73.线性规划模型的标准型

一、线性规划的一般模型标准化方法：8二、线性规划解的概念与理论（1）解：1.线性规划解的概念9

1.线性规划解的概念（2）基10

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

1.线性规划解的概念几种解的关系：可行解基可行解基解1112

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

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

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

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

2、线性规划的MATLAB求解三、线性规划的求解方法用MATLAB求解线性规划模型14

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

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

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

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

(6)求解非线性最小二乘逼近和曲线拟合问题.用MATLAB求解线性规划模型16

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

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

SYSTEMINC．

3、线性规划的LINGO解法三、线性规划的求解方法17

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

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

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

LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，用LINGO求解线性规划模型19用LINGO求解线性规划模型20数据段集合段目标约束用LINGO求解线性规划模型21四、线性规划的应用案例分析

一般讲，一个应用问题凡满足一下条件时，才能建立线性规划模型（1）要求解问题的目标函数能用数值指标来反映且为线性函数；（2）存在多种方案；（3）要求达到的目标是在一定约束条件下实现的，这些约束条件可以用线性等式或不等式来描述。2223

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

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

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

7.4m2.9m2.1m1.5m0.9m案例1:合理下料问题25案例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

x2x3x4x5x6

决策变量：——按第i种模式切割的原料钢管根数（i=1,2,…,6）模式2.9米根数2.1米根数1.5米根数余料11030（米）22010.1（米）30220.2（米）41200.3（米）50130.8（米）61110.9（米）需求10010010026

决策目标：所用的原材料最省，而最省可以有两种标准，一是切割后总余料量最小，二是切割原材料的总根数最少，按照这两种标准建立数学模型如下：案例1:合理下料问题2728案例1:合理下料问题29案例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)30案例1:合理下料问题

用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;ENDDATA[OBJ]MIN=@SUM(ARRANGE(J):C(J)*X(J););@FOR(ROW(I):@SUM(ARRANGE(J):A(I,J)*X(J))=B(I););@FOR(ARRANGE(J):X(J)>=0;);END31案例1:合理下料问题

用LINGO求解模型

某投资公司拟制定今后五年的投资计划，初步考虑下面的四个投资项目：从第1年到第4年每年年初需要投资，并于次年年末收回成本，并可获利润15%；第3年年初需要投资，到第5年年末可以收回成本，并获得利润25%，但为了保证足够的资金流动，规定该项目的投资金额上限为不超过总金额的40%；AB

2、连续投资问题四、线性规划的应用案例分析32问题:

现有投资金额100万元，如何使得第五年年末能够获得最大的利润。第2年年初需要投资，到第5年年末可以收回成本，并获得利润40%，但公司规定该项目的最大投资金额不超过总金额的30%；五年内每年年初可以购买公债，于当年年末可以归还本金，并获利息6%。CD

2、连续投资问题四、线性规划的应用案例分析33年份项目12345Ax11x21x31x41Bx32Cx23Dx14x24x34x44x54案例2:连续投资问题34第1年：将100万元资金全部用于项目A和项目D的投资，即案例2:连续投资问题35案例2:连续投资问题36案例2:连续投资问题37案例2:连续投资问题连续投资问题的数学模型:38MODEL: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求解模型39问题的连续投资方案：第1年：项目A为716981.1元和项目D为283018.9元第2年：项目C的投资金额为300000元，第3年：项目B的投资为400000元和项目D为424528.3元，第4年：投资项目A的金额为450000元。第5年年末该公司拥有总资金为1437500元，即收益率为43.75%。案例2:连续投资问题4041

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