《数学实验7线性函数极值》由会员分享，可在线阅读，更多相关《数学实验7线性函数极值（56页珍藏版）》请在金锄头文库上搜索。
1、实验八 线性函数极值求解,西安交通大学数学与统计学院 赵小艳 办公地点：理科楼214 电子邮箱：,实验目的 本实验通过具体问题介绍线性规划的一些基本概念和性质；掌握线性规划问题的图解法、软件解法以及当线性规划问题规模较小，并且存在最优解时的理论解法。,实验内容 本实验主要介绍线性函数的极值求解方法，即线性规划问题。它是运筹学的一个重要分支，在科学实践中有着广泛的应用，不仅许多实际课题属于线性规划问题，而且运筹学其它分支中的一些问题也可转化为线性规划问题来计算，因此，线性规划在最优化学科中占有重要地位。本实验通过具体问题介绍线性规划的一些基本概念和性质，给出求解线性规划问题的图解法和软件解法以及
2、当线性规划问题规模较小，并且存在最优解时的理论解法。,美国空军为了保证士兵的营养，规定每餐的食品中，要保证一定的营养成份，例如蛋白质、脂肪、维生素等等，都有定量的规定。当然这些营养成份可以由各种不同的食物来提供，例如牛奶提供蛋白质和维生素，黄油提供蛋白质和脂肪，胡萝卜提供维生素，等等。由於战争条件的限制，食品种类有限，又要尽量降低成本，於是在一盒套餐中，如何决定各种食品的数量，使得既能满足营养成份的需要，又可以降低成本？ 现代管理问题虽然千变万化，但大致上总是要利用有限的资源，去追求最大的利润或最小的成本，如何解决这些问题？,解决问题的方法：线性规划,在波斯湾战争期间，美国军方利用线性规划，有
3、效地解决了部队给养和武器调运问题，对促进战争的胜利，起了关键的作用。甚至有这样的说法：因为使用炸药，第一次世界大战可说是化学的战争；因为使用原子弹，第二次世界大战可说是物理的战争；因为使用线性规划，波斯湾战争可称为数学的战争。 在历史上，没有哪种数学方法，可以像线性规划那样，直接为人类创造如此巨额的财富，并对历史的进程发生如此直接的影响。,例1、生产计划问题：,问：A, B各生产多少, 可获最大利润?,一、引例,某企业生产A，B两 种产品，成本和利润指标如下：,max Z= 40x1 +50x2,解:设产品A, B的产量分别为变量x1 ， x2，则：,s.t.,例2：(资源配置问题) 现有四种
4、原料，其单位成本和所含维生素A，B，C成分如下：,求：最低成本的原料混合方案。,A B 每单位成本 原料1 4 1 0 2 原料2 6 1 2 5 原料3 1 7 1 6 原料4 2 5 3 8 每单位添加剂中 维生素最低含量,12 14 8,解：,minZ= 2x1 + 5x2 +6x3+8x4,设每单位添加剂中原料i的用量为xi(i =1,2,3,4)，则：,s.t.,有一批长度为7.4m的钢筋若干根。现有5种下料方案，分别作成2.9m， 2.1m，1.5m的钢筋架子各100根。每种下料方案及剩余料头如下表所示：,例3、 (资源配置问题),问：如何下料使得剩余料头最少？,解：设按第i种方案
5、下料的原材料为xi根，则：,minZ= 0.1x2 + 0.2x3+0.3x4+0.8x5,s.t.,例4、(运输问题),某棉纺厂的原棉需从仓库运送到各车间。各车间原棉需求量，单位产品从各仓库运往各车间的运输费以及各仓库的库存容量如下表所列：,问：如何安排运输任务使得总运费最小？,设xij为i 仓库运到 j车间的原棉数量(i 1,2,3; j 1,2,3)。则,minZ= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33,解：,s.t.,例5、连续投资10万元于4个项目。各项目投资时间和本利情况如下：,项目A：从第1年 到第4年每年初要投资，
6、次年末 回收本利1.15倍。,项目B：第3年初投资，到第5年末回收本利1.25倍， 最大投资4万元。,项目C：第2年初投资，到第5年末回收本利1.40倍， 最大投资3万元。,项目D：每年初投资，每年末回收本利1.11倍。,求：如何分配投资资金使得5年末总资本最大？,以上问题的特点:,2.某项任务确定后，如何安排人力、财力、物力，使之最省.,1.在人力、财力、资源给定条件下，如何合理安排任务，使得效益最高.,即以上问题都是在一定条件下，求目标函数的最大值或最小值问题，而且目标函数和约束条件都是线性函数。这类问题称为线性规划LP (Linear Programming，LP) 问题。,二 线性规划
7、问题的一般形式,max(min)Z=c1x1+ c2x2+cnxn,s.t.,或,三、线性规划问题的求解方法,2 二元线性规划问题的图解法,3 线性规划问题的理论解法,1 线性规划问题的MATLAB软件解法,x=linprog(f, A, b): 求解 min z = fx, Ax b,1 求解线性规划的MATLAB命令,若没有不等式约束,可用 替代A和b, 若没有等式约束,可用 替代Aeq和beq,若某个xi下无界或上无界,可设定-inf或 inf； 用x, Fval代替上述命令行中的x，可得最优解处的函数值Fval。,x=linprog(f, A, b, Aeq, beq): 求解： mi
8、n z = fx, Ax b, Aeqx = beq；,x=linprog(f, A, b, Aeq, beq, lb, ub): 指定lb x ub;,x,fval,exitflag,output=linprog(f, A, b, Aeq, beq, lb, ub) X为最优解向量；fval为最优值；exitflag描述linprog的终止条件：若为正值，表示目标函数收敛于解x，若为负值，表示目标函数不收敛，若为零值，表示已经达到函数评价或迭代的最大次数。output为返回优化算法信息的一个数据结构：output.iteration表示迭代次数， output.algorithm表示所采用的
9、算法，output.funcCount表示函数评价次数。,min Z= -40x1 -50x2,s.t.,例1、,解：程序如下 -zhao81,c=-40,-50; a=1,2;3,2;0,2; b=30;60;24; x=linprog (c,a,b) z=c*x,例2:,min Z= 4x1 +3x2,s.t.,解：,% zhao82.m % c=4,3;a=1,1;b=5; vlb=-6;-1; %lower bound of vector x % vub=10;4; % upper bound of vector x % x=linprog(c,a,b,vlb,vub) z=c*x,例
10、3:,min Z = -x1+2x2 3x3,s.t.,解：,% zhao83.m % c=-1,2,-3;a=1,1,1;-1,1,-1; b=7;-2; vlb=0;0;0; % lower bound of vector x % vub=; % upper bound of vector x % x=linprog(c,a,b,vlb,vub) z=c*x,minZ= 2x1 + x2+3x3+2x4 +2x5 +4x6 +3x7 +4x8 +2x9,x1 +x4 +x7 = 40， x2 +x5 +x8 =15， x3 +x6 +x9 =35， x1 +x2+x3 50， x4+x5+
11、x6 30， x7+x8+x9 10， xi 0， i 1,2,9;,s.t.,例4:,% zhao84.m % c=2,1,3,2,2,4,3,4,2; beq=40;15;35; b=50;30;10; a=1,1,1,0,0,0,0,0,0; 0,0,0,1,1,1,0,0,0; 0,0,0,0,0,0,1,1,1; aeq=1,0,0,1,0,0,1,0,0; 0,1,0,0,1,0,0,1,0; 0,0,1,0,0,1,0,0,1; vlb=zeros(9,1); % lower bound of vector x % vub=; % upper bound of vector x
12、% x=linprog(c,a,b,aeq,beq,vlb,vub) z=c*x,解：,2 线性规划问题的图解法,定义1：满足约束(1)、(2)的x=(x1 , , xn)T称为LP问题的可行解，全部可行解的集合称为可行域。,定义2：满足(3)的可行解称为LP问题的最优解.,图解法步骤 （1）作出可行域的图形； （2）作出目标函数等值线； （3）将目标函数等值线自坐标原点开始向上（下）平移，与可行域的最后一个交点就是最优解； （4）求最优解坐标和最优值。,max Z= 40x1 +50x2,例1:,s.t.,二元线性规划问题的图解法,x2=0 (纵),(0,30), (20,0),2x2 =2
13、4,(1)、确定可行域,解：,x1 0;,x1 =0 (横),x2 0;,x1+2x2 30,x1+2x2 =30,3x1+2x2 =60,2x2 24,3x1+2x2 60,(2)、求最优解,x* = (15,7.5),Z=40x1+50x2,0=40x1+50x2,Z=975,Z=0,Zmax =975,(0 1),maxZ=40x1+ 80x2,例2: 求解,s.t.,最优解：BC线段,B点 : x(1)=(6,12),C点: x(2)=(15,7.5),BC线段:,maxZ=1200,Z=1200,Z=0,例、 max Z=3x1+2x2,即无可行解.,s.t.,可行域无解.,3 线性
14、规划问题的理论解法,（） 线性规划问题的标准形式,特点： （1）所有约束条件是等式； （2）约束条件右端常数项为非负； （3）所有变量是非负。,A称为约束矩阵.,（）化一般线性规划问题为标准形,约束条件的转换：,称为剩余变量或松弛变量,maxZ=40x1+ 50x2+0x3 +0x4+0x5,max Z= 40x1 +50x2,例1:,s.t.,其中x3 , x4, x5 为松弛变量 。,s.t.,minZ= 2x1 + 5x2 +6x3+8x4,例2：,minZ= 2x1 + 5x2 +6x3+8x4 +0x5 +0x6 +0x7,其中x5 , x6, x7 为剩余变量 。,s.t.,s.t
15、.,变量的转换,例3:,令: x1= x1- x1 “,(1),令: x1 = x1 +6, 则 0 x1 16,例4:,(3),目标函数的转换,令Z = -Z,将以下线性规划问题,化为标准型。,例5:,min Z = -x1+2x2 3x3,s.t., 令x3 =x4 - x5, 加松弛变量x6,加剩余变量x7, 令 Z= -Z,max Z= x1 2x2 +3x4 3x5,解,min Z = -x1+2x2 3x3,（）线性规划问题的理论解法:,凸集：,定义1：,设D是n维欧氏空间的一个集合。 任意点x(1), x(2)D,若任一满足 x= x(1)+(1-) x(2) (0 1) 的点xD。则D称为凸集。,设线性规划的标准型,B P1
