《数学建模--线性规划》由会员分享，可在线阅读，更多相关《数学建模--线性规划（32页珍藏版）》请在金锄头文库上搜索。
1、 线性规划数学建模与数学实验后勤工程学院数学教研室Date数学建模实验目的实验内容2、掌握用数学软件包求解线性规划问题。1、了解线性规划的基本内容。*2、线性规划的基本算法 。5、实验作业。3、用数学软件包求解线性规划问题。1、两个引例。4、建模案例：投资的收益与风险Date数学建模问题一 ： 任务分配问题：某车间有甲、乙两台机床，可用 于加工三种工件。假定这两台车床的可用台时数分别为800和 900，三种工件的数量分别为400、600和500，且已知用三种 不同车床加工单位数量不同工件所需的台时数和加工费用如 下表。问怎样分配车床的加工任务，才能既满足加工工件的 要求，又使加工费用最低？两个
2、引例Date数学建模解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3， 在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立 以下线性规划模型：解答Date数学建模问题二： 某厂每日8小时的产量不低于1800件。为了进行质 量控制，计划聘请两种不同水平的检验员。一级检验员的标准 为：速度25件/小时，正确率98%，计时工资4元/小时；二级检 验员的标准为：速度15小时/件，正确率95%，计时工资3元/小 时。检验员每错检一次，工厂要损失2元。为使总检验费用最 省，该工厂应聘一级、二级检验员各几名？解 设需要一级和二级检验员的人数分别为x1、x2人, 则应付检验员的工资
3、为：因检验员错检而造成的损失为：Date数学建模故目标函数为：约束条件为：Date数学建模线性规划模型：解答返 回Date数学建模1.线性规划的标准形式：用单纯法求解时，常将标准形式化为 ：2. 线性规划的基本算法单纯形法线性规划的基本算法单纯形法Date数学建模引入松弛变量x3, x4, x5, 将不等式化为等式, 即单纯形标准形:显然A的秩ran(A)=3, 任取3个线性无关的列向量,如P3 P4 P5称为 一组基, 记为B. 其余列向量称为非基, 记为N .Date数学建模于是 f = cBxB + cNxN , Ax = BxB + NxN = b,则 xB = B-1b-B-1NxN
4、 , f = cBB-1b + (cN cBB-1N)xN 若可行基进一步满足: cN cBB-1N0, 即: cBB-1N - cN0 则对一切可行解x, 必有f(x) cBB-1b, 此时称基可行解x = (B-1b, 0) T 为最优解.3. 最优解的存在性定理将A的列向量重排次序成A = (B, N), 相应x = (xB, xN) T, c = (cB, cN) 基对应的变量xB称为基变量, 非基对应的变量xN称为非基变量.定理1 如果线性规划(1)有可行解，那么一定有基可行解.定理2 如果线性规划(1)有最优解，那么一定存在一个基可行解是最优解.Date数学建模4. 基可行解是最优
5、解的判定准则因为 f = cBB-1b + (cN cBB-1N)xN， 即 f - 0xB + (cBB-1N- cN )xN = cBB-1bDate数学建模5.基可行解的改进Date数学建模改进方法：返 回Date数学建模用MATLAB优化工具箱解线性规划min z=cX 1、模型：命令：x=linprog（c，A，b ） 2、模型：min z=cX 命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式： 存在，则令A= ，b= .Date数学建模3、模型：min z=cX VLBXVUB 命令：1 x=linprog（c，A，b，Aeq,beq, VLB，VUB）2
6、 x=linprog（c，A，b，Aeq,beq, VLB，VUB, X0） 注意：1 若没有等式约束: , 则令Aeq= , beq= .2其中X0表示初始点 4、命令：x,fval=linprog()返回最优解及处的目标函数值fval.Date数学建模解 编写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=
7、0;0;0;0;0;0; vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)To Matlab (xxgh1)Date数学建模解: 编写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)Date数学建模S.t.改写为：例3 问题一的解答问题Date数学建模编写M文件xxgh3.m如下:f = 13 9 10 11 12 8; A = 0.4 1.1 1 0 0 00
8、 0 0 0.5 1.2 1.3; b = 800; 900; Aeq=1 0 0 1 0 00 1 0 0 1 00 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)Date数学建模结果: x =0.0000600.00000.0000400.00000.0000500.0000 fval =1.3800e+004即在甲机床上加工600个工件2,在乙机床上加工400个工件1、 500个工件3，可在满足条件的情况下使总加工费最小
9、为13800。Date数学建模例2 问题二的解答问题改写为：Date数学建模编写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)Date数学建模结果为： x =9.00000.0000 fval =360即只需聘用9个一级检验员 。注：本问题应还有一个约束条件：x1、x2取整数。故它 是一个整数线性规划问题。这里把它当成一个线性规划来 解，求得其
10、最优解刚好是整数：x1=9，x2=0，故它就是该 整数规划的最优解。若用线性规划解法求得的最优解不是 整数，将其取整后不一定是相应整数规划的最优解，这样 的整数规划应用专门的方法求解。返 回Date数学建模投资的收益和风险Date数学建模二、基本假设和符号规定Date数学建模三、模型的建立与分析 1.总体风险用所投资的Si中最大的一个风险来衡量,即max qixi|i=1，2,n4. 模型简化：Date数学建模Date数学建模四、模型1的求解 由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资 者有不同的风险度。我们从a=0开始，以步长a=0.001进行循环搜索，编 制程序如下：D
11、ate数学建模a=0; while(1.1-a)1c=-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.055 0;0 0 0 0 0.026;b=a;a;a;a;vlb=0,0,0,0,0;vub=;x,val=linprog(c,A,b,Aeq,beq,vlb,vub);ax=xQ=-valplot(a,Q,.)，axis(0 0.1 0 0.5)，hold ona=a+0.001; end xlabel(a),ylabel(Q)T
12、o Matlab（xxgh5）Date数学建模计算结果：Date数学建模五、 结果分析返 回4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%，Q*=20% ，所对应投资方案为:风险度 收益 x0 x1 x2 x3 x40.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212 3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最 小风险。对于不同风险的承受能力，选择该风险水平下
13、的最优投资组合 。2.当投资越分散时，投资者承担的风险越小，这与题意一致。即:冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资 。1.风险大，收益也大。Date数学建模实验作业某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6千克, 工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20 名,可获利9万元.今工厂共有原料60千克,工人150名,又由于其 他条件所限甲饮料产量不超过8百箱.问如何安排生产计划,即 两种饮料各生产多少使获利最大.进一步讨论:1)若投资0.8万元可增加原料1千克,问应否作这项投资.2)若每百箱甲饮料获利可增加1万元,问应否改变生产计划.返 回Date数学建模
