《数学模型与数学实验1第一章线性规划讲述》由会员分享，可在线阅读，更多相关《数学模型与数学实验1第一章线性规划讲述（47页珍藏版）》请在金锄头文库上搜索。
1、第第1 1章章 线性规划线性规划 1.11.1线性规划问题线性规划问题 当今社会现状：经济快速发展，资源急 剧消耗，地球环境不堪重负 解决关键：如何利用现有资源安排生产 ，以取得最大经济效益-数学规划。 线性规划（Linear Programming, LP） 是其中的重要分支。 1947，G.B.Dantzig，单纯形法（ Simplex Method） 计算机快速求解 （1 1）实例）实例与与定义定义 例 1.1 某机床厂生产甲、乙两种机床， 每台销售后的利润分别为4000元与 3000 元。生产甲机床需用A、B机器加 工，加工时间分别为每台2小时和1小 时；生产乙机床需用A、B、C三种机
2、器 加工，加工时间为每台各一小时。若每 天可用于加工的机器时数分别为A机器 10小时、B机器8小时和C机器7小时， 问该厂应生产甲、乙机床各几台，才能 使总利润最大？ 产品甲产品乙机器资源（小时 ） 机器A2110 机器B118 机器C017 利润（元/件 ） 40003000 概括：在如下资源条件下，应生产甲、 乙机床各几台，才能使总利润最大？ 数学模型：设该厂生产x1台甲机床和x2 乙机床时总利润最大，则x1, x2应满足 （目标函数） max z = 4000 x1 + 3000 x2 (subject to) s.t. 2x1+x210 (约束条件)x1+x2 8 x2 7 x1,x2
3、0 其中x1, x2称为决策变量。 定义（线性规划问题）：在一组线性约 束条件下，求一线性目标函数的最大（ 或最小）。 单纯形法基本思想：线性规划问题的可 行域是n维向量空间Rn中的多面凸集， 其最优值如果存在必在该凸集的某顶点 处达到。据此可以完成计算求解。 （2 2）解的概念）解的概念 LP问题标准形式 可行解：满足约束条件的解 可行域：所有可行解构成的集合 最优解、较优解 （3 3）MatlabMatlab形式及软件求解形式及软件求解 LP问题的Matlab形式(向量形式) 求解命令格式 x,fval=linprog(f,A,b,Aeq,beq,lb,ub,x0) 注：更多内容可help
4、 linprog了解 例1.2 求解LP问题 解: 1)编写m文件ex1_2.m f=2;3;-5; A=-2,5,-1;1,3,1; b=-10;12; Aeq=1,1,1; beq=7; lb=zeros(3,1); x=linprog(-f,A,b,Aeq,beq,lb);z=f*x; 2)执行ex1_2.m 注意不同情形下的命令格式 x,z=linprog(f,A,b,lb,ub,x0) x,z=linprog(f,Aeq,beq,lb,ub,x0) x,z=linprog(f,A,b,Aeq,beq,ub) （4 4）可转化）可转化为为LPLP的形式的形式 例1.4 规划问题 例1.
5、5 求解数学规划问题 解：1)转化为Matlab标准形式 由 且 2)编写m文件ex1_5.m A=1,-1,-1,1;1,-1,1,-3;1,-1,-2,3; b=-2;-1;-0.5;c=1,2,3,4; f=c;c; Amat=A,-A; lb=zeros(8,1); y=linprog(f,Amat,b,lb);z=f*y; x=y(1:4)-y(5:8); 3)执行ex1_5.m 例1.6 某商品有m个产地、n个销地，各 产地的产量分别为a1,a2,am，各销地 的需求量分别为b1,b2,bn。若该商品 由i产地运到j销地的单位运价为cij，问 应该如何调运才能使总运费最省？ 改写为
6、Matlab形式，由 且 求解程序transport.m function x,z=transport(a,b,c) %a is m*1,b is 1*n, c is m*n m,n=size(c); Aeq1=;Aeq2=; for j=1:n Aeq1=Aeq1,eye(m); end for i=1:m tmat=zeros(n);tmat(i,:)=1;Aeq2=Aeq2,tmat; end Aeq=Aeq1;Aeq2; beq1=a;beq2=b;beq=beq1;beq2; x,z=linprog(c(:),Aeq,beq,zeros(m*n,1); ex1_6.m clear;c
7、lc; m=4;n=5; a=rand(m,1);b=rand(1,n);c=rand(m,n); x,z=transport(a,b,c); 例1.7 改写为Matlab形式，由 得 1.2 1.2 投资的收益与风险投资的收益与风险 社会经济快速发展，各种理财产品层出 不穷，投资行为变得越来越普及（财团 、公司、boss、大妈？）。如何在当 前复杂环境下对有限资本进行合理投资 ？ （1 1）问题提出）问题提出 可用投资总额为M； 市场上有n种资产si (i=1,2,n)可选， 投资si时，收益率qi，风险损失率ri，交 易费率为pi(购买额不超ui时按ui计算)； 总体风险可用投资资产中最大
8、的一个风 险来度量； 同期银行存款利率为q0(=5%)，无交易 费无风险； 给定n=4时数据，试设计投资方案使静 收益尽可能大，总体风险尽可能小。 n=4时数据 siqi(%)ri(%)pi(%) ui s1282.51103 s2211.52198 s3 235.54.5 52 s4252.66.5 40 （2 2）符号规定和基本假设）符号规定和基本假设 a)符号规定 si表示第i种投资项目,i=0,1,n, s0表示存 入银行; qi,pi,ri表示si的收益率,交易费率,风险损失 率,p0=r0=0; ui表示si的交易定额,u0=0; xi表示投资项目si的资金; R表示总体风险; Q
9、表示总体收益. b)基本假设 投资数额M相当大; 总体风险R用所投资项目si中的最大风险度 量; si之间相互独立; 在投资时期内,ri,pi,qi为定值,不受意外因素 影响; 收益Q和风险R不受其它因素干扰. （3 3）模型分析与建立）模型分析与建立 a)总体风险R用所投资项目si中的最大 风险度量，即 R=max rixi, i=0,1,n b)投资si的交易费为 pimaxxi,ui,i=0,1,2,n 故投资si的净收益为Qi=qixi-pimaxxi,ui c)要使净收益尽可能大，总体风险尽可 能小，即max iQi和min R需要同时进 行，此即多目标规划 适当条件(uiM)下可以
10、考虑近似模型 d)模型简化 多目标规划的求解较复杂，一般可转化 为单目标规划再进行求解。 约束风险，优化收益(模型ex1_8a)； 若投资者所能承受最高风险度为a，则 约束收益，优化风险(模型ex1_8b)； 若投资者要求的最低综合收益率为k，则 风险-收益平衡优化(模型ex1_8c)， 即对风险和收益分别赋以权重s和1-s； （4 4）模型求解）模型求解 a)模型可改写为Matlab形式 编写m文件ex1_8a.m clear;clc; M=1e5; r=0,2.5,1.5,5.5,2.6*1e-2;q=5,28,21,23,25*1e-2; p=0,1,2,4.5,6.5*1e-2;u=0
11、,103,198,52,40*1e-2; f=p-q; A=diag(r); Aeq=(1+p);beq=M; lb=zeros(5,1); aset=0:0.001:0.05;xset=;Qset=; for a=aset b=M*a; x,rQ=linprog(f,A,b,Aeq,beq,lb); xset=xset,x;Qset=Qset,rQ; end plot(aset,Qset,k*);xlabel(a);ylabel(Q); 执行ex1_8a.m，绘图结果如下 b)模型可改写为LP形式 进一步改写为Matlab形式 编写m文件ex1_8b.m clear;clc; M=1e5;
12、r=0,2.5,1.5,5.5,2.6*1e-2;q=5,28,21,23,25*1e-2; p=0,1,2,4.5,6.5*1e-2;u=0,103,198,52,40*1e-2; f=zeros(5,1);1; A=diag(r),-ones(5,1);p-q,0; Aeq=(1+p),0;beq=M; lb=zeros(5,1); kset=0.05:0.01:0.5;yset=;Rset=;rRset=; for k=kset b=zeros(5,1);-M*k; y,R=linprog(f,A,b,Aeq,beq,lb); yset=yset,y;Rset=Rset,R; rRset
13、=rRset,max(r.*y(1:5); end figure;hold on; plot(kset,Rset,k:);plot(kset,rRset,b.-); xlabel(k);ylabel(R);legend(ideal,real); 执行ex1_8b.m，绘图结果如下 c)模型三可改写为LP形式 进一步改写为Matlab形式 编写m文件ex1_8c.m clear;clc; M=1e5; r=0,2.5,1.5,5.5,2.6*1e-2;q=5,28,21,23,25*1e-2; p=0,1,2,4.5,6.5*1e-2;u=0,103,198,52,40*1e-2; A=diag
14、(r),-ones(5,1);b=zeros(5,1); Aeq=(1+p),0;beq=M; lb=zeros(5,1); sset=0:0.1:1; yset=;Zset=;rZset=;Qset=;Rset=; for s=sset f=(1-s)*(p-q);s; y,Z=linprog(f,A,b,Aeq,beq,lb); yset=yset,y;Zset=Zset,Z; Qset=Qset,-(p-q)*y(1:5); Rset=Rset,max(r.*y(1:5); rZset=rZset,s*max(r.*y(1:5)+(1-s)*(p- q)*y(1:5); end figure;hold on; plot(sset,Zset,k:);plot(sset,rZset,b.-); plot(sset,Rset,bv-);plot(sset,Qset,b-); xlabel(s);ylabel(Z);legend(ideal,real);box on; 执行ex1_8c.m，绘图结果如下 （5 5）结果分析）结果分析 略 作业作业 习题1，1.2，1.3
