实验8 (线性函数极值求解).ppt

1、数学实验,实验8 线性函数极值求解,实验目的,1、学会根据实际问题建立线性规划模型，求解线性极值问题。 2、掌握用matlab软件求解线性规划和线性极值问题。,实验内容,1、用matlab软件求解线性函数极值；,2、几个具体线性规划模型的建立及求解。,一种特殊形式的数学规划模型，即目标函数和约束条件是待求变量的线性函数、线性等式或线性不等式的数学规划模型。它可用于解决各种领域内的极值问题。它所描述的典型问题是怎样以最优的方式在各项活动中间分配有限资源的问题。 用n维向量x=(x1,x2, ,xn)T表示未知变量，求目标函数f(x)在x允许的范围x内的极小值（极大值）问题可统一表述为如下模型：

2、模型1 min(max)f(x) （1） S.t.x （2） 称为可行域，常用一组关于x的不等式（或等式）确定，亦称为约束条件。称满足（2）的解为可行解，同时满足（1）的解x*称为最优解。,线性规划（线性极值）模型,模型2 min(max)f(x)=CTx，,线性规划（线性极值）模型,模型3 min(max)f(x)=CTx，,其中c=(c1,c2, ,cn)T，x=(x1,x2, ,xn)T,一般的模型可以通过引入松驰变量（增加变量）转化为标准形式，标准形式有如下特点： （1）所有约束条件是等式； （2）约束条件右端常数项为非负； （3）所有变量为非负。,1）作出可行域的图形； 2）作出目标

3、函数等值域； 3）将目标函数等值线自坐标原点开始向上（下）平移，与可行域的最后一个交点就是最优解； 4）求最优解坐标和最优值。,线性规划模型的解法图解法,设A是秩为m的mn阶矩阵，A的m个线性无关的列构成的子矩阵AB称为模型的一个基（基阵）， AB的列向量称为基列（基向量），相应于基列的变量称为基变量。自然地，其余的列称为非基向量，相应的变量称为非基变量。,线性规划模型的解法理论解法,其中AB为基阵，AN为非基阵， xB由基变量构成，xN由非基变量构成。,为Ax=b的一个解，若令xN=0，则称,为模型的一个基本解；若AB-10，则称x为模型的一个基本可行解，简称可行解，这时的基阵AB称为可行基

4、。,由,得,，那么,线性规划模型的解法理论解法,调用函数：linprog,用matlab软件求解线性规划,linprog(c,A,b) linprog(c,A,b,vlb,vub) linprog(c,A,b,aeq,beq,vlb,vub) x,fval=linprog()%fval是目标函数的最值。,数学模型,命令,用matlab软件求解线性规划问题：,示例1,问题可改写为,c=1;3; A=-1 -1;1 0;b=-20;12; vlb=6; 2;vub=; x,fval=linprog(c,A,b,vlb,vub),示例1程序一,程序运行结果为 x=12.0000 8.0000 fva

5、l=36.0000,c=1;3; A=-1 -1;b=-20; vlb=6; 2;vub=12; inf; x,fval=linprog(c,A,b,vlb,vub),示例1程序二,程序运行结果为 x=12.0000 8.0000 fval=36.0000,示例2,已知生产单位甲产品工厂可获利4万元，生产单位乙产品工厂可获利3万元，问该厂如何安排生产才能使每周获得的利润最大？,某工厂生产每件产品需经过A、B、C三个车间，每个车间所需的工时数如下表所示，,示例2：模型建立,这是一个有约束的优化问题，其模型包括决策变量：生产甲乙两种产品的产量x1,x2；目标函数；工厂的周利润z；约束条件：三个车间

6、可使用工时之和以及非负性约束，由此得如下模型：,示例2：模型求解（一）图解法,下图中顶点分别为O、A、B、C、D五点的凸五边形为可行域。,示例2：模型求解（二）理论解法,首先引入松弛变量，化成标准形式：,选取基矩阵B=(P1,P2,P3)，解得基本解x1=(1,7,1,0,0)T 选取基矩阵B=(P1,P2,P5)，解得基本解x2=(2,6,0,0,1)T 选取基矩阵B=(P2,P3,P4)，解得基本解x3=(0,7,3,1,0)T 选取基矩阵B=(P1,P4,P5)，解得基本解x4=(5,0,0,3,7)T 选取基矩阵B=(P3,P4,P5)，解得基本解x5=(0,0,10,8,7)T 选取

7、基矩阵B=(P1,P2,P4)，解得基本解x6=(1.5,7,0,-0.5,0)T 选取基矩阵B=(P1,P3,P5)，解得基本解x7=(8,0,-6,0,7)T 选取基矩阵B=(P2,P3,P5)，解得基本解x8=(0,8,2,0,-1)T 选取基矩阵B=(P2,P4,P5)，解得基本解x9=(0,10,0,-2,-3)T,示例2：模型求解（二）理论解法,c=-4,-3;A=2,1;1,1;0,1;b=10;8;7; aeq=;beq=; vlb=0;0;0;vub=; x,fval=linprog(c,A,b,aeq,beq,vlb,vub) maxz=-fval,示例2：模型求解（三）软

8、件解法,程序运行结果为 x=2.0000 6.0000 fval=-26.0000 maxz=26.0000,某单位一批资金用于4个工程项目的投资，用于各工程项目时所得到的净收益（投入资金的百分比）如下表：,由于某种原因，决定用于项目A的投资不大于其他各项投资之和；而用于项目B和C的投资要大于项目D的投资。试确定使该单位收益最大的投资分配方案。,示例3,解：用 分别表示用于投资A、B、C和D 的投资百分数。数学模型为,示例3：模型建立,c=-0.15,-0.1,-0.08,-0.12; A=1,-1,-1,-1;0,-1,-1,1;b=0;0; aeq=1,1,1,1;beq=1; vlb=0

9、,0,0,0,vub=; x,fval=linprog(c,A,b,aeq,beq,vlb,vub) maxw=-fval,示例3：模型求解,运行结果,x = 0.5000 0.2500 0.0000 0.2500 fval =-0.1300 maxw =0.1300,示例4: 用lingo软件求解,示例4,示例4,% lingo程序; model: max=x1+3*x2; x1+x2=20; x1=6; x1=2;,示例5:人员配置问题,某城市110巡警大队要求每天各个时间段都有一定的数量的警员值班，随时处理突发事件，每人连续工作6小时。下表是一天8班次所需值班警员的人数统计。在不考虑时间

10、段中间有警员上班和下班的情况下，该城市110巡警大队至少需要多少警员才能满足值班要求？,示例5：模型建立,示例5:模型求解（一） matlab程序,c=ones(1,8); a=-1*1,0,0,0,0,0,0,1;1,1,0,0,0,0,0,0; 0,1,1,0,0,0,0,0;0,0,1,1,0,0,0,0; 0,0,0,1,1,0,0,0;0,0,0,0,1,1,0,0; 0,0,0,0,0,1,1,0;0,0,0,0,0,0,1,1; b=-1*70 80 65 90 80 100 120 90; lx=zeros(1,8); ux=inf*ones(1,8); x=linprog(c

11、,a,b) minz=c*x,示例5:模型求解（一）matlab结果,x = 47.7615 32.2385 37.5392 52.4608 33.4924 66.5076 61.7673 28.2327 minz = 360.0000,示例5:模型求解（一）续,x1=round(x) minz1=c*x1,x1= 48 32 38 52 33 67 62 28,minz1 = 360,示例5:模型求解（二 ）lingo程序,model: min=x1+x2+x3+x4+x5+x6+x7+x8; x1+x8=70; x1+x2=80; x2+x3=65; x3+x4=90; x4+x5=80;

12、 x5+x6=100; x6+x7=120; x7+x8=90; gin(x1);gin(x2);gin(x3);gin(x4); gin(x5);gin(x6);gin(x7);gin(x8); end,示例5:模型求解（二）lingo 8结果,Global optimal solution found at iteration: 9 Objective value: 360.0000 Variable Value Reduced Cost X1 80.00000 1.000000 X2 0.000000 1.000000 X3 65.00000 1.000000 X4 25.00000 1

13、.000000 X5 55.00000 1.000000 X6 45.00000 1.000000 X7 90.00000 1.000000 X8 0.000000 1.000000,示例6：最佳投资组合,下表给出4只股票在同一时期内的平均收益率ri%，购买股票时交易率为pi%，风险损失率qi%，投资越分散，总的风险越小。假定总风险用投资中最大一种股票的风险来度量，且同期银行存款利率是r0=5%，既无交易费又无风险，由于投资者承受风险的程度不一样，若给定风险一个界限a，即最大风险不超过a的情况下，为投资者建议一种投资策略，使其尽可能获得最大收益。,假设投资四种股票的资金分别为X1，X2，X3，

14、X4，存银行X0； 总投资资金为M。 并设四种股票之间是相互独立的，且在投资的同一时期内ri、pi、qi、r0都为定值，不受意外因素影响。,示例6：条件假设,投资四种股票的风险度分别为qiXi/M，i=1,2,3,4；购买四种股票时所付交易费分别为piXi，则购买四种股票的收益分别为(ri-pi)Xi，i=1,2,3,4，为使投资者获得最大收益，在总风险不超过a的情况下，可建立如下模型：,示例6：建立模型,示例6:模型化简,其中xi=Xi /M，i=0,1,2,3,4,示例6:模型求解,如何给定风险度a没有一定的准则，不同的投资者承受风险度的能力不同。可以从a=0开始，以某个步长进行循环搜索，

15、本次实验步长a=0.001。,示例6:模型求解程序,clear;clc;clf; a=0; while(1.1-a)1; c=-1*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;,示例6:模型求解程序（续一）,lx=zeros(1,5);ux=; x,val=linprog(c,A,B,Aeq,Beq,lx,ux); %a; x=x; Q=-val; plot(a,Q,.) axis(0,0.1,0,0.5) hold on a=a+0.001; end xlabel(a),ylabel(Q),示例6:模型求解结果,示例6:模型求解结果解释,1）风险大，收益也大； 2）当投资越分散时，投资者承担的风险越小，这与题意一致，即冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资； 3）曲线上的点表示当风险水平给定时能获得的最大收益率；,示例6:模型求解结果解释,4）分别在a=0.006和a=0.025附近有两个转折