第4讲线性规划(教育精品)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,线性规划,数学建模与数学实验,实验目的,实验内容,2.,掌握用数学软件包求解线性规划问题,.,1.,了解线性规划的基本内容,.,2.,用数学软件包,MATLAB,求解线性规划问题,.,5.,实验作业,.,3.,用数学软件包,LINDO,、,LINGO,求解线性规划问题,.,1.,两个引例,.,4.,建模案例：投资的收益与风险,.,问题一：,任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件,.,假定这两台车床的可用台时数分别为,800,和,900,，三种工件的数量分别为,400,、,600,和,500,，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表,.,问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,两个引例,解,设在甲车床上加工工件,1,、,2,、,3,的数量分别为,x,1,、,x,2,、,x,3,，在乙车床上加工工件,1,、,2,、,3,的数量分别为,x,4,、,x,5,、,x,6,可建立以下线性规划模型：,解答,问题二：,某厂每日,8,小时的产量不低于,1800,件,.,为了进行质量控制，计划聘请两种不同水平的检验员,.,一级检验员的标准为：速度,25,件,/,小时，正确率,98%,，计时工资,4,元,/,小时；二级检验员的标准为：速度,15,件,/,小时，正确率,95%,，计时工资,3,元,/,小时,.,检验员每错检一次，工厂要损失,2,元,.,为使总检验费用最省，该工厂应聘一级、二级检验员各几名？,解,设需要一级和二级检验员的人数分别为,x,1,、,x,2,人,则应付检验员的工资为：,因检验员错检而造成的损失为：,故目标函数为：,约束条件为：,线性规划模型：,解答,返 回,线性规划模型的一般形式,目标函数和所有的约束条件都是设计变量,的线性函数,.,实际问题中,的优化模型,x,是决策变量,f,(,x,),是目标函数,g,i,(,x,),0,是约束条件,数学规划,线性规划,(LP),二次规划,(QP),非线性规划,(NLP),纯整数规划,(PIP),混合整数规划,(MIP),整数规划,(IP),0-1,整数规划,一般整数规划,连续规划,优化模型的分类,用,MATLAB,优化工具箱解线性规划,min,z=cX,1.,模型：,命令：,x=linprog,（,c,A,b,）,2.,模型,：,min,z=cX,命令：,x=linprog,（,c,，,A,，,b,，,Aeq,beq,）,注意：若没有不等式：存在，则令,A=,，,b=.,3.,模型,：,min,z=cX,VLBXVUB,命令：,1,x=linprog,（,c,，,A,，,b,，,Aeq,beq,VLB,，,VUB,）,2,x=linprog,（,c,，,A,，,b,，,Aeq,beq,VLB,，,VUB,X0,）,注意：,1,若没有等式约束,:,则令,Aeq=,beq=.,2,其中,X,0,表示初始点,4.,命令：,x,fval=linprog(),返回最优解,及,处的目标函数值,fval,.,解 编写,M,文件,xxgh1.m,如下：,c=-0.4-0.28-0.32-0.72-0.64-0.6;,A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08;,b=850;700;100;900;,Aeq=;beq=;,vlb=0;0;0;0;0;0;vub=;,x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),To MATLAB(xxgh1,),c=-0.4-0.28-0.32-0.72-0.64-0.6;A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08;b=850;700;100;900;Aeq=;beq=;vlb=0;0;0;0;0;0;vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),解,:,编写,M,文件,xxgh2.m,如下：,c=6 3 4;,A=0 1 0;,b=50;,Aeq=1 1 1;,beq=120;,vlb=30,0,20;,vub=;,x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),To MATLAB(xxgh2),s.t.,改写为：,例,3,问题一的解答,问题,编写,M,文件,xxgh3.m,如下,:,f=13 9 10 11 12 8;,A=0.4 1.1 1 0 0 0,0 0 0 0.5 1.2 1.3;,b=800;900;,Aeq=1 0 0 1 0 0,0 1 0 0 1 0,0 0 1 0 0 1;,beq=400 600 500;,vlb=zeros(6,1);,vub=;,x,fval=linprog(f,A,b,Aeq,beq,vlb,vub),To MATLAB(xxgh3),结果,:,x=,0.0000,600.0000,0.0000,400.0000,0.0000,500.0000,fval=1.3800e+004,即在甲机床上加工,600,个工件,2,在乙机床上加工,400,个工件,1,、,500,个工件,3,，可在满足条件的情况下使总加工费最小为,13800.,例,2,问题二的解答,问题,改写为：,编写,M,文件,xxgh4.m,如下：,c=40;36;,A=-5-3;,b=-45;,Aeq=;,beq=;,vlb=zeros(2,1);,vub=9;15;,%,调用,linprog,函数：,x,fval=linprog(c,A,b,Aeq,beq,vlb,vub),To MATLAB(xxgh4),结果为：,x=,9.0000,0.0000,fval=360,即只需聘用,9,个一级检验员,.,注：,本问题应还有一个约束条件：,x,1,、,x,2,取整数,.,故它是一个,整数线性规划,问题,.,这里把它当成一个线性规划来解，求得其最优解刚好是整数：,x,1,=9,，,x,2,=0,，故它就是该整数规划的最优解,.,若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解,.,返 回,用,LINDO,、,LINGO,优化工具箱解线性规划,一、,LINDO,软件包,下面我们通过一个例题来说明,LINDO,软件包的使用方法,.,LINDO,和,LINGO,软件能求解的优化模型,LINGO,LINDO,优化模型,线性规划,(LP),非线性规划,(NLP),二次规划,(QP),连续优化,整数规划,(IP),1,桶牛奶,3,千克,A,1,12,小时,8,小时,4,千克,A,2,或,获利,24,元,/,千克,获利,16,元,/,千克,50,桶牛奶,时间,:480,小时,至多加工,100,千克,A,1,制订生产计划，使每天获利最大,35,元可买到,1,桶牛奶，买吗？若买，每天最多买多少,?,可聘用临时工人，付出的工资最多是每小时几元,?,A,1,的获利增加到,30,元,/,千克，是否应改变生产计划？,每天：,例,1,加工奶制品的生产计划,x,1,桶牛奶生产,A,1,x,2,桶牛奶生产,A,2,获利,243,x,1,获利,164,x,2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型,(LP),建立模型,max 72x1+64x2,st,2,）,x1+x250,3,）,12x1+8x2480,4,）,3x1100,end,OBJECTIVE FUNCTION VALUE,1)3360.000,VARIABLE VALUE,REDUCED COST,X1 20.000000,0.000000,X2 30.000000,0.000000,ROW SLACK OR SURPLUS DUAL PRICES,2)0.000000 48.000000,3)0.000000 2.000000,4)40.000000 0.000000,NO.ITERATIONS=2,DO RANGE(SENSITIVITY)ANALYSIS?,No,20,桶牛奶生产,A,1,30,桶生产,A,2,，利润,3360,元,.,模型求解,OBJECTIVE FUNCTION VALUE,1)3360.000,VARIABLE VALUE REDUCED COST,X1 20.000000 0.000000,X2 30.000000 0.000000,ROW,SLACK OR SURPLUS,DUAL PRICES,2)0.000000,48.000000,3)0.000000,2.000000,4)40.000000,0.000000,原料无剩余,时间无剩余,加工能力剩余,40,max 72x1+64x2,st,2,）,x1+x250,3,）,12x1+8x2480,4,）,3x1100,end,三种资源,“,资源”剩余为零的约束为紧约束（有效约束）,结果解释,模型求解,reduced cost,值表示当该,非基变量,增加一个单位时（其他非基变量保持不变）,目标函数减少的量,(,对,max,型问题,),.,OBJECTIVE FUNCTION VALUE,1)3360.000,VARIABLE VALUE,REDUCED COST,X1 20.000000,0.000000,X2 30.000000,0.000000,ROW SLACK OR SURPLUS DUAL PRICES,2)0.000000 48.000000,3)0.000000 2.000000,4)40.000000 0.000000,NO.ITERATIONS=2,也可理解为：,为了使该,非基变量变成基变量,，目标函数中对应系数应增加的量,OBJECTIVE FUNCTION VALUE,1)3360.000,VARIABLE VALUE REDUCED COST,X1 20.000000 0.000000,X2 30.000000 0.000000,ROW SLACK OR SURPLUS,DUAL PRICES,2),0.000000,48.000000,3),0.000000,2.000000,4),40.000000,0.000000,结果解释,最优解下“资源”增加,1,单位时“效益”的增量,原料增,1,单位,利润增,48,时间增,1,单位,利润增,2,能力增减不影响利润,影子价格,35,元可买到,1,桶牛奶，要买吗？,35”,（或“,=”,（或“,=”,）功能相同,变量与系数间可有空格,(,甚至回车,),但无运算符,变量名以字母开头，不能超过,8,个字符,变量名不区分大小写,（包括,LINDO,中的关键字）,目标函数所在行是第一行，第二行起为约束条件,行号,(,行名,),自动产生或人为定义,.,行名以“）”结束,行中注有“,!”,符号的后面部分为注释,.,如,:,!Its Comment.,在模型的任何地方都可以用“,TITLE”,对模型命名（最多,72,个字符），如：,TITLE This Model is only an Example,变量不能出现在一个约束条件的右端,表达式中不接受括号“,()”,和逗号“,”,等任何符号,例,:,400(X1+X2),需写为,400X1+400X2,表达式应化简，如,2X1+3X2-4X1,应写成,-2X1+3X2,缺省假定所有变量非负；可在模型的“,END”,语句后用“,FREE name,”,将变量,name,的非负假定取消,可在“,END”,后用“,SUB”,或“,SLB”,设定变量上下界,例如：“,sub x1 10,”,的作用等价于“,x1=345.5,;