数学建模中问题的matlab求解

1、第二章 规划问题的MATLAB求解 2.1 线性规划2.2 非线性规划2.3 整数规划数学规划模型 序 规划问题是常见的数学建模问题，离散系统的优化问题一般都可以通过规划模型来求解。因此快速求解规划问题是数学建模的基本素质。利用MATLAB提供的规划模型求解命令，可以快速得到想要的结果。2.1 线性规划 1947年美国数学家G.B. Dantzig提出线性规划的一般数学模型和求解线性规划的通用方法单纯形法，为学科奠定基础。 1947年美国数学家J.von诺依曼提出对偶理论，开创了线性规划的许多新领域，扩大的应用范围和解题能力。 1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，并

2、与康拓罗维奇一起获得1975年诺贝尔经济学奖。2.1.1 线性规划的实例与定义 【例2-1】某电视台播放两套宣传片，宣传甲片播映时间为3.5min，广告时间为30s，观众60万；宣传乙片播映时间为1min，广告时间为1min，收视观众为20万。广告公司规定每周至少有3.5min广告，电视台智能为该栏目宣传不小于16min的节目。电视台每周至少要两套宣传片多少次，才能使人使收视观众最多？类别播甲片播放乙片节目要求片集时间（min）3.51=3.5收视观众/万60202.1.2线性规划的MATLAB标准形式2.1.3 求解线性规划的MATLAB解法x,fval=linprog(c,A,b,Aeq,

3、beq,LB,UB,X0,OPTIONS)其中的fval为返回目标函数的值；A，b对应不等式约束；Aeq，beq对应等式约束；LB，UB为变量x的下界和上界。X0为x的初始值；OPTIONS是控制参数。解:Matlab程序如下:c=2 3 1;a=1 4 2;3 2 0;b=8 6;x,y=linprog(c,-a,-b,zeros(3,1)解:Matlab程序如下:f=-5 -4 -6;A=1 -1 1;3 2 4;3 2 0;b=20 42 30;lb=zeros(3,1);x,fval,exitflag,output,lambda=linprog(f,A,b,lb)注:输出x为最优解，f

4、val为最优值，exitflag为程序停止的标志，output为个结构变量，包括程序运行的有关信息，lambda也是结构变量，对应于相应的约束的Lagrange乘子。解:Matlab程序如下:c=2;3;-5;a=-2,5,-1;b=-10;aeq=1,1,1;beq=7;x=linprog(-c,a,b,aeq,beq,zeros(3,1)%是求最大值而不是最小值value=c*xMatlab运行程序：f=-170.8582 17.7254 -41.2582 -2.2182 -131.8182 500000;A=1 -0.17037 -0.5324 0 1 0;0 0.17037 0.532

5、4 0 0 0;1 0.32 1 0 0 0;0 1 0 0 0 0;0 0 1 1 0 0;0 0 0 -1 -1 0;b=0;888115;166805;511265.625;683400;-660000;Aeq=0 0 0 0 0 1;beq=1;lb=0;0;0;0;0;0;x,fval,exitflag,output,lamda=linprog(f,A,b,Aeq,beq,lb,)练习:1、 2、1、Matlab程序：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

6、0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08;b=850;700;100;900;Aeq=;beq=;v1=0;0;0;0;0;0;v2=;x,fval=linprog(c,A,b,A1,b1,v1,v2)2、Matlab程序如下：c=6 3 4;A=0 1 0;b=50;A1=1 1 1;b1=120;v1=30,0,20;v2=; x,fval=linprog(c,A,b,A1,b1,v1,v2)练习:3、4、3、Matlab运行程序：c= 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 = 80

7、0; 900;A1=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1;b1=400 600 500;v1 = zeros(6,1);v2=;x,fval = linprog(c,A,b,A1,b1,v1,v2)4、Matlab运行程序：c =40;36;A=-5 -3;b=-45;A1=;b1=;v1 = zeros(2,1);v2=9;15;x,fval = linprog(c,A,b,A1,b1,v1,v2)2.2 非线性规划 如果规划问题中目标函数或约束条件中包含非线性函数，这种规划问题称为非线性规划问题。2.2.1 非线性规划 特点：非线性规划问题比线性规划问题的

8、求解要复杂得多，没有统一的解法。各种方法有自己特定的适用范围。2.2.2 非线性规划的Matlab求解MATLAB命令：x,y = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) （1）定义目标函数function f=fun1(x)f=x(1)2+x(2)2+8;（2）定义约束条件function g,h=fun2(x)g=-x(1)2+x(2);h=-x(1)-x(2)2+2;（3）编写主程序：options=optimset;x,y=fmincon(fun1,rand(2,1),zeros(2,1),. fun2,options)fun

9、ction f=fun44(x)f=-(sqrt(x(1)+sqrt(x(2)+sqrt(x(3)+sqrt(x(4);x0=1;1;1;1;lb=0 0 0 0;ub=;A=;b=;Aeq=;beq=;x,fval=fmincon(fun44,x0,A,b,Aeq,beq,lb,ub,mycon1)function g,ceq=mycon1(x)g(1)=x(1)-400;g(2)=1.1*x(1)+x(2)-440;g(3)=1.21*x(1)+1.1*x(2)+x(3)-484;g(4)=1.331*x(1)+1.21*x(2)+1.1*x(3)+x(4)-532.4;ceq=0;结果：

10、x = 86.2890 103.7586 127.1018 152.1895fval = -43.08582.2.3 二次规划 若非线性规划的目标函数为自变量x的二次函数，约束条件是线性的，则称这种规划为二次规划。求解命令一般格式x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options) h=4 -4; -4 8;f=-6,-3;a=1 1;4 1;b=3 9;x,value=quadprog(h,f,a,b,zeros(2,1)x = 1.9500 1.0500value = -11.0250罚函数法简介 罚函数法可将非线性规划问题转化为求解一序列无约束的极

11、值问题，因而也称这种方法为序列无约束最小化技术，简记为SUMT（sequential unconstrained minimization technique). 求解的基本思想是利用问题中的约束函数做出适当的罚函数，构造出带多参数的增广目标函数，把问题转化为无约束的线性规划问题求解。 一般分为外罚函数法和内罚函数法。 以下介绍外罚函数法，内罚函数法参考PPT“内罚函数法”。function g=test(x)M=50000;f=x(1)2+x(2)2+8;g=f-M*min(x(1),0)-M*min(x(2),0)-M*min(x(1)2-x(2),0). +M*abs(-x(1)-x(2

12、)2+2);命令窗输入x,y=fminunc(test,rand(2,1)2.3 整数规划 （线性）规划中的变量限制为整数时，称为整数（线性）规划。一般只能对整数线性规划进行求解，目前没有一种方法能有效地求解非线性整数规划问题。2.3.1 整数规划的定义 常见的整数规划问题的求解方法：（1）分枝定界法：可求纯或混合整数线性规划。（2）割平面法：可求纯或混合整数线性规划。（3）隐枚举法：用于求解0-1规划，有过滤隐枚举法和分枝隐枚举法。（4）匈牙利法：解决指派问题（0-1规划特殊情形）。（5）蒙特卡罗法：求解各种类型规划。2.3.2 0-1整数规划 三个变量共有8种组合，依次检验看是否是最优解。

13、 相应的目标值大于3，则进行步骤（3）（3）改进过滤条件。（4）对于每一个组合，首先计算目标值以验证过滤条件，因此优先计算目标值z，这样可以提前太高过滤门槛，以减少计算量。x目标值式子1式子2式子3式子4式子5条件(0,0,0)0(1,0,0)33(0,1,0)-2(0,0,1)53(1,1,0)1(1,0,1)83(0,1,1)3(1,1,1)6判断表及最优值 对于非线性整数规划，目前还没有有效通用的求解方法，一般采取枚举法。2.3.3 整数规划的定义定义目标函数f和约束函数gfunction f,g=mengte(x)f=x(1)2+x(2)2+3*x(3)2+4*x(4)2+2*x(5)

14、-8*x(1)-2*x(2)-3*x(3)-x(4)-2*x(5);g(1)=sum(x)-400;g(2)=x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800;g(3)=2*x(1)+x(2)+6*x(3)-200;g(4)=x(3)+x(4)+5*x(5)-200;求解程序：rand(state,sum(clock);p0=0;ticfor i=1:105 x=99*rand(5,1); x1=floor(x);x2=ceil(x); f,g=mengte(x1); if sum(g=0)=4 if p0=f x0=x1;p0=f; end endf,g=mengte(x

15、2); if sum(g=0)=4 if p0=f x0=x2;p0=f; end endendx0,p0toc 由于是随机取样，因此每一次运行结果是不一致的，误差不会太大。 一般情况，如果是整数规划问题，先考虑应用LINGO软件求解，其求解能力强。MATLAB是通用性较强。一、LINDO软件包 下面我们通过一个例题来说明LINDO软件包的使用方法.用LINDO、LINGO优化工具箱解线性规划LINDO和LINGO软件能求解的优化模型 LINGO LINDO优化模型线性规划(LP)非线性规划(NLP)二次规划(QP)连续优化整数规划(IP)1桶牛奶 3千克A1 12小时 8小时 4千克A2 或

16、获利24元/千克 获利16元/千克 50桶牛奶 时间: 480小时 至多加工100千克A1 制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到 30元/千克，是否应改变生产计划？ 每天：例1 加工奶制品的生产计划x1桶牛奶生产A1 x2桶牛奶生产A2 获利 243x1 获利 164 x2 原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利约束条件非负约束 线性规划模型(LP)建立模型:max=72*x1+64*x2st2）x1+x2=503）12*x1+8*x2=4804）3*x1=100en

17、d 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= 2DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生产A1, 30桶生产A2，利润3360元. 模型求解: OBJEC

18、TIVE 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原料无剩余时间无剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三种资源“资源” 剩余为零的约束为紧约束（有效约束） 结果解释 结

19、果解释 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也可理解为：为了使该非

20、基变量变成基变量，目标函数中对应系数应增加的量 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

21、元可买到1桶牛奶，要买吗？35 ”（或“=”（或“=”）功能相同变量与系数间可有空格(甚至回车), 但无运算符变量名以字母开头，不能超过8个字符变量名不区分大小写（包括LINDO中的关键字）目标函数所在行是第一行，第二行起为约束条件行号(行名)自动产生或人为定义.行名以“）”结束行中注有“!”符号的后面部分为注释.如: ! Its Comment.在模型的任何地方都可以用“TITLE” 对模型命名（最多72个字符），如： TITLE This Model is only an Example变量不能出现在一个约束条件的右端表达式中不接受括号“( )”和逗号“,”等任何符号, 例: 400(X1

22、+X2)需写为400X1+400X2表达式应化简，如2X1+3X2- 4X1应写成 -2X1+3X2缺省假定所有变量非负；可在模型的“END”语句后用“FREE name”将变量name的非负假定取消可在 “END”后用“SUB” 或“SLB” 设定变量上下界 例如： “sub x1 10”的作用等价于“x1=345.5; x1=98; 2*x1+x2=345.5 x1=98 2*x1+x21c=-0.05 -0.27 -0.19 -0.185 -0.185;Aeq=1 1.01 1.02 1.045 1.065;beq=1;A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.05