《《线性规划新》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《线性规划新》PPT课件.ppt（41页珍藏版）》请在三一办公上搜索。
1、线性规划,线性规划简介,线性规划问题最早是前苏联学者康德洛维奇（L.V.Kantorovich）于1939年提出的，但他的工作当时并未广为人知。第二次世界大战中，美国空军的一个研究小组SCOOP（Scientific Computation of Optimum Programs）在研究战时稀缺资源的最优化分配这一问题时，提出了线性规划问题。并且由丹泽（）于1947年提出了求解线性规划问题的单纯形法。50年代初，电子计算机研制成功，较大规模的线性规划问题的计算已经成为可能。因此，线性规划和单纯形法受到数学家、经济学家和计算机工作者的重视，得到迅速发展，很快发展成一门完整的学科并得到广泛的应用。
2、1952年，美国国家标准局（NBS）在当时的SEAC电子计算机上首次实现单纯形算法。1976年IBM研制成功功能十分强大、计算效率极高的线性规划软件MPS，后来又发展成为更为完善的MPSX。这些软件的研制成功，为线性规划的实际应用提供了强有力的工具。,随着计算机硬件和软件技术的发展，目前用微型计算机就可以求解变量个数达106，约束个数达104的巨大规模的问题，并且计算时间也不太长。,线性规划问题,根据实际问题的要求，可以建立线性规划问题数学模型。线性规划问题由目标函数、约束条件以及变量的非负约束三部分组成。下面列举3种最常见的线性规划问题的类型。,生产计划问题,例1.1 某工厂拥有A、B、C三
3、种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,设变量xi为第i种产品的生产件数（i1，2，3，4），目标函数z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下，可以建立如下的线性规划模型：,这是一个典型的利润最大化的生产计划问题。其中max表示极大化（maximize），s.t.是subject to的缩写。求解这个线性规划，可以得到最优解为：x1=294.12x2=1500 x3=0 x4=58.82（件）最大利润为z=12737.06（元）,背包问题,例1.2 一只
4、背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价值如下表所示：,要在背包中装入这三种物品各多少件，使背包中的物品价值最高。,设装入物品1，物品2和物品3各为x1，x2，x3件，由于物品的件数必须是整数，因此背包问题的线性规划模型是一个整数规划问题：,指派问题,例1.3 有n项任务由n个人去完成，每项任务交给一个人，每个人都有一项任务。由第i个人去做第j项任务的成本（或效益）为cij。求使总成本最小（或效益最大）的分配方案。,例如，有张、王、李、赵4位教师被分配教语文、数学、物理、化学4门课程，每位教师教一门课程，每门课程由一位老师教。根据这四位教师以往教课的情
5、况，他们分别教这四门课程的平均成绩如下表：,四位教师每人只能教一门课，每一门课只能由一个教师来教。要确定哪一位教师上哪一门课，使四门课的平均成绩之和为最高。,设xij（i=1,2,3,4；j=1,2,3,4）为第i个教师是否教第j门课，xij只能取值0或1，其意义如下：,变量xij与教师 i 以及课程 j 的关系如下：,max z=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90 x32+74x33+65x34+93x41+61x42+83x43+75x44s.t.x11+x12+x13+x14=1（1）x21+x22+x23+x
6、24=1（2）x31+x32+x33+x34=1（3）x41+x42+x43+x44=1（4）x11+x21+x31+x41=1（5）x12+x22+x32+x42=1（6）x13+x23+x33+x43=1（7）x14+x24+x34+x44=1（8）xij=0,1,这个问题的变量只能取值0或1，这样的线性规划问题成为01规划。,一般的指派问题线性规划模型如下：设：,得到以下的线性规划模型：,由以上3个例子，我们可以归纳出线性规划问题的一般形式：,非线性规划简介,规划问题：在约束条件下求目标函数的最优值点。规划问题包含3个组成要素:决策变量(decision variable)目标函数(ob
7、jective function)约束条件(constraint)当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题,否则称为非线性规划问题。,3、用MATLAB软件求解线性规划问题,线性规划问题的求解方法包括图解法、单纯形法、矩阵法等.,但在决策变量个数较多，求解过程都比较复杂时，用MATLAB软件求解线性规划问题则比较简单.,MATLAB求解线性规划问题的命令,X=linprog(f,A,b),求解LP问题,命令格式,命令函数 linprog(),X,fval=linprog(f,A,b,Aeq,Beq,LB,UB),求解LP问题,X,fval,exitflag,output,
8、lambda=linprog(f,A,b,Aeq,Beq,LB,UB,X0,options).,其功能是求解有初始值X0和用options指定优化参数进行优化的LP问题.,函数说明(1),f,A,X,b,线性规划的不等式约束条件,Aeq,Beq,线性规划的等式约束条件,目标函数取得极值的决策变量组成的列向量,矩阵,向量,矩阵,向量,目标函数的系数组成的向量,LB,X0,Options,fval,UB,变量的上界约束,变量的初始值,变量的下界约束,控制规划过程的参数系列,优化结束后得到的目标函数值,X,fval,exitflag,output,lambda,=linprog(f,A,b,Aeq,
9、Beq,LB,UB,X0,options),目标函数取得极值的决策变量组成的列向量,优化结束后得到的目标函数值,目标函数的系数组成的向量,线性规划的不等式约束条件,矩阵,向量,控制规划过程的参数系列,变量的初始值,变量的下界约束,变量的上界约束,线性规划的等式约束条件,矩阵,向量,(2)运用linprog()命令时，系统默认为它的各种linprog(f,A,b,Aeq,Beq,LB,UB,X0,options)都存在，且按固定顺序排列。本例中，在存在约束LB的情况下，它后面的参数没给出，可以不声明，但是LB前面的参数即使没给出（例如等式约束条件）也要用空矩阵“”的方式给出声明，不能省略。,函数
10、说明,(3)返回值exitflag有3种情况：,exitflag=1 表示优化结果不收敛。,exitflag=1 表示优化过程中变量收敛于解X。,exitflag=0 表示优化结果已经超过函数的估计值 或者已声明的最大叠代次数；,(4)返回值output有3个分量，iterations表示优化过程的叠代次数，cgiterations表示PCG叠代次数，algorithm表示优化采用的运算规则。,函数说明,(5)返回值lambda有4个分量，ineqlin是线性不等式约束条件，eqlin是线性等式约束条件，upper是变量的上界约束条件，lower是变量的下界约会条件。它们的返回值分别表示相应的
11、约束条件在优化过程中是否有效，本例中可以看到，三个不等式约束中的后两个是有效的。,(6)线性规划问题没有可行解时,系统提示,Warning:The constraints are overly stringent;there is no feasible solution.,如果优化成功,系统将会提示:,Optimization terminated successfully,函数说明,案例二（生产计划的问题）某工厂在计划期内要安排生产、的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗以及每件产品可获的利润如下表所示。问应如何安排计划使该工厂获利最多？,返回,用MATLAB
12、求解案例二中关于生产计划的LP问题,解 原LP问题为,MATLAB命令的标准形是求目标函数的最小值,通常将maxf通常转变为min-f来编程求解。原问题转化为,在MATLAB中输入,clear,f=-2,3;,A=1,2;4,0;0,4;,B=8,16,12;,lb=0,0;,X,fval=linprog(f,A,B,lb),击回车键，显示最优解及目标函数最优值,Optimization terminated successfully.,X=,4.0000,2.0000,fval=,-14.0000,所以，工厂应选择生产第、产品的产量分别为4件和2件，工厂最多可获利14万元。,案例三(营养配餐
13、问题)假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场价格如下表所示。试建立满足营养的前提下使购买食品费用最小的数学模型。,返回,用MATLAB求解案例三中的线性规划问题。,解 原LP模型为,在MATLAB中输入,clear,f=10,6,3,2;,A=-10,-8,-9,-2;-5,-6,-2,-1;-4,-2,-3,-5;b=-30,-5.5,-8;,lb=0,0,0,0;,X,fval=linprog(f,A,b,lb),显示最优解及目标函数最优值,Optimization termin
14、ated successfully.,X=,0.0000,0.0000,3.3333,0.0000,所以应购买3.3333千克大米才能既满足营养需求，又能使购买食品的费用最小。,案例四(投资问题)某公司有一批资金用于4个工程项目的投资，其投资各项目时所得的净收益如下表：,由于某种原因，决定用于项目A的投资不大于其他各项投资之和而用于项目B和C的投资要大于项目D的投资。试建立该公司收益最大的投资分配方案的数学模型。,返回,用MATLAB求解案例四中的投资问题。,解 设x1、x2、x3、x4分别代表用于项目A、B、C、D的投资百分数，则投资问题的数学模型为,MATLAB中输入,clear,f=-0
15、.15;-0.1;-0.08;-0.12;,Optimization terminated successfully.,x=0.5000 0.2500 0.0000 0.2500,A=1-1-1-1,0-1-1 1;,b=0 0;,Aeq=1 1 1 1;,beq=1;,lb=zeros(4,1);,x,fval,exitflag=linprog(f,A,b,Aeq,beq,lb),回车后结果显示：,fval=-0.1300,exitflag=1,即4个项目的投资百分数分别为50%，25%，0,25%时可使该公司获得最大的收益，其最大收益可到达13%。过程正常收敛。,思考题,1、某厂生产甲乙两
16、种口味的饮料,每百箱甲饮料需用原料6千克,工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20名,可获利9万元.今工厂共有原料60千克,工人150名,又由于其他条件所限甲饮料产量不超过8百箱.问如何安排生产计划,即两种饮料各生产多少使获利最大.进一步讨论:1)若投资0.8万元可增加原料1千克,问应否作这项投资.2)若每百箱甲饮料获利可增加1万元,问应否改变生产计划.,2、某家具厂生产两种柜子，产一台A柜、B柜的时间分别为60小时和50小时；分别占用10、20立方米的仓库空间；家具厂每周有6000小时的上产时间，仓库空间有1500立方米。此外，A的销售量每周不超过80台。A的售价150元，成本90元；B的售价100元，成本65元。如果每周要使两种柜子的的总收入不低于6000元。问如何安排生产计划最有利？（求解最优解）,3、某工厂计划安排生产A 和B两种产品，已知生产单位产品所需的设备和原材料如下表所示。该工厂每生产一件A产品，可获利2元，每生产一件B产品可获利3元，问应该如何安排生产，可使工厂的获利最多？,
