6-线性规划ppt课件

1、1Mathematics Laboratory办公地址：理科楼办公地址：理科楼222Experiments in Mathematics数学实验数学实验2实验目的实验目的 本实验通过具体问题介绍线性规划的一些基本概念本实验通过具体问题介绍线性规划的一些基本概念和性质；掌握线性规划问题的图解法、软件解法以及和性质；掌握线性规划问题的图解法、软件解法以及当线性规划问题规模较小，并且存在最优解时的理论当线性规划问题规模较小，并且存在最优解时的理论解法。解法。实验内容实验内容 线性规划线性规划(Linear Programming)是运筹学的一个重要是运筹学的一个重要分支，在科学实践中有着广泛的应用，

2、不仅许多实际分支，在科学实践中有着广泛的应用，不仅许多实际课题属于线性规划问题，而且运筹学其它分支中的一课题属于线性规划问题，而且运筹学其它分支中的一些问题也可转化为线性规划问题来计算，因此，线性些问题也可转化为线性规划问题来计算，因此，线性规划在最优化学科中占有重要地位。本实验通过具体规划在最优化学科中占有重要地位。本实验通过具体问题介绍线性规划的一些基本概念和性质，给出求解问题介绍线性规划的一些基本概念和性质，给出求解线性规划问题的图解法和软件解法以及当线性规划问线性规划问题的图解法和软件解法以及当线性规划问题规模较小，并且存在最优解时的理论解法。题规模较小，并且存在最优解时的理论解法。3

3、什么是优化问题？建立优化问题的数学模型，首先要确定问题的变量，建立优化问题的数学模型，首先要确定问题的变量，,),(21nxxxxn维向量表示用),(xf然后构造目标函数称为可行域取值范围允许,xxmixgxfzix, 2 , 1, 0)( .s.t)( min优化方法的优劣？优化方法的优劣？1、收敛性？、收敛性？2，收敛速度？，收敛速度？3、占用内存？、占用内存？1、线性规划（、线性规划（LP）2、二次规划（、二次规划（SQP）3、非线性规划（、非线性规划（NLP）4线性函数极值求解线性函数极值求解3例例1、生产计划问题：、生产计划问题：问：问：A, B各生产多少各生产多少, 可获最大利润可

4、获最大利润? A B 备用资源备用资源 煤煤 1 2 30劳动日劳动日 3 2 60 仓库仓库 0 2 24 利润利润 40 50一、引例一、引例某企业生产某企业生产A，B两两 种产品，成本和利润指标如下：种产品，成本和利润指标如下：5 x1 + 2x2 30， 3x1 + 2x2 60， 2x2 24， x1，x2 0；max Z= 40 x1 +50 x2解解:设产品设产品A, B的产量分别为变量的产量分别为变量x1 ， x2，则：则：s.t. A B 备用资源备用资源 煤煤 1 2 30劳动日劳动日 3 2 60 仓库仓库 0 2 24 利润利润 40 50465例例2 2：( (资源配

5、置问题资源配置问题) ) 现有四种原料，其单位成本和所含维生素现有四种原料，其单位成本和所含维生素A A，B B，C 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 876解：解：minZ= 2x1 + 5x2 +6x3+8x44x1 + 6x2 + x3+2x4 12，x1 + x2 +7x3+5x4 14， 2x2 + x3+3x4 8， xi 0 (

6、i =1,4)；设每单位添加剂中原料设每单位添加剂中原料i的用量为的用量为xi(i =1,2,3,4)，则：则：s.t. A B 每单位成本每单位成本 原料原料1 4 1 0 2 原料原料2 6 1 2 5 原料原料3 1 7 1 6 原料原料4 2 5 3 8每单位添加剂中每单位添加剂中维生素最低含量维生素最低含量12 14 88 有一批长度为有一批长度为7.4m的钢筋若干根的钢筋若干根。现有现有5种下料方案，分别作成种下料方案，分别作成2.9m， 2.1m，1.5m的钢筋架子各的钢筋架子各100根。每种下料方案及剩余料头如下表所示：根。每种下料方案及剩余料头如下表所示：例例3、 (资源配置

7、问题资源配置问题)问：如何下料使得剩余料头最少？问：如何下料使得剩余料头最少？ 2.92.9m 1 2 0 1 0m 1 2 0 1 02.1m 0 0 2 2 12.1m 0 0 2 2 11.5m 3 1 2 0 31.5m 3 1 2 0 3合计合计 7.4 7.3 7.2 7.1 6.6 7.4 7.3 7.2 7.1 6.6料头料头 0 0.1 0.2 0.3 0.8 0 0.1 0.2 0.3 0.879解：设按第解：设按第i种方案下料的原材料为种方案下料的原材料为xi根，则：根，则：minZ= 0.1x2 + 0.2x3+0.3x4+0.8x5 x1 + 2x2 + x4 = =

8、100， 2x3 +2x4+ x5= =100，3x1+ x2+2x3 +3x5= =100， xi 0 (i =1,5)，且为整数；且为整数；s.t. 2.92.9m 1 2 0 1 0m 1 2 0 1 02.1m 0 0 2 2 12.1m 0 0 2 2 11.5m 3 1 2 0 31.5m 3 1 2 0 3合计合计 7.4 7.3 7.2 7.1 6.6 7.4 7.3 7.2 7.1 6.6料头料头 0 0.1 0.2 0.3 0.8 0 0.1 0.2 0.3 0.8810例例4 4、( (运输问题运输问题) ) 1 2 3 库存容量库存容量 1 2 1 3 50 2 2 2

9、 4 30 3 3 4 2 10 需求需求 40 15 35仓库仓库车间车间某棉纺厂的原棉需从仓库运送到各车间。各车间原棉需求量，单位产品从各仓某棉纺厂的原棉需从仓库运送到各车间。各车间原棉需求量，单位产品从各仓库运往各车间的运输费以及各仓库的库存容量如下表所列：库运往各车间的运输费以及各仓库的库存容量如下表所列：问：如何安排运输任务使得总运费最小？问：如何安排运输任务使得总运费最小？911设设xij为为i 仓库运到仓库运到 j车间的原棉数量车间的原棉数量(i 1,2,3; j 1,2,3)。则则minZ= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x3

10、2 +2x33解：解：x11 +x12+x13 50，x21+x22+x23 30，x31+x32+x33 10，x11 +x21+x31 = 40，x12 +x22+x32 =15，x13 +x23+x33 =35， xij 0， i 1,2,3; j 1,2,3;s.t. 1 2 3 库存容量库存容量 1 2 1 3 50 2 2 2 4 30 3 3 4 2 10需求需求 40 15 35仓库仓库车间车间1012例例5 5、连续投资、连续投资1010万元于万元于4 4个项目。各项目投资时间和本利情况如下：个项目。各项目投资时间和本利情况如下：项目项目A A：从第从第1 1年年 到第到第4

11、 4年每年初要投资，次年末年每年初要投资，次年末 回收本利回收本利1.151.15倍。倍。项目项目B B：第第3 3年初投资，到第年初投资，到第5 5年末回收年末回收本利本利1.251.25倍倍， 最大投资最大投资4 4万元。万元。项目项目C C：第第2 2年初投资，到第年初投资，到第5 5年末回收年末回收本利本利1.401.40倍倍， 最大投资最大投资3 3万元万元。项目项目D D：每年初投资，每年末回收每年初投资，每年末回收本利本利1.111.11倍倍。求：如何分配投资资金使得求：如何分配投资资金使得5 5年末总资本最大？年末总资本最大？1113解：解： 1 2 3 4 5A x1A x2

12、A x3A x4A B x3BC x2CD x1D x2D x3D x4D x5D 项目项目年份年份设设xik( i =1,2,3,4,5; k =A,B,C,D)表示第表示第i年初投资第年初投资第k项目的资金数。项目的资金数。1214xik( i =1,2,5; k =A,B,C,D)为第为第i年初投年初投k项目的项目的资金数资金数.则：则：maxZ= 1.15x4A +1.40 x2C+1.25x3B+1.11x5Dx1A+x1D=10 x2A+x2C+x2D= 1.11 x1Dx2C 3x3A +x3B+x3D =1.15 x1A+ 1.11 x2Dx3B 4x4A +x4D =1.15

13、 x2A+ 1.11 x3Dx5D =1.15 x3A+ 1.11 x4D xik 0, i =1,2,5; k =A,B,C,D;s.t.13151以上问题的特点以上问题的特点: :2.某项任务确定后，如何安排人力、财力、物力，使之最省某项任务确定后，如何安排人力、财力、物力，使之最省. .1.在人力、财力、资源给定条件下，如何合理安排任务，使得效益最高在人力、财力、资源给定条件下，如何合理安排任务，使得效益最高. .即以上问题都是在一定条件下，求线性函数的最大值或最小值问题。这类问题即以上问题都是在一定条件下，求线性函数的最大值或最小值问题。这类问题称为线性规划称为线性规划LP (Line

14、ar Programming) 问题。问题。161线性规划问题的一般形式线性规划问题的一般形式max(min)Z=c1x1+ c2x2+cnxna11x1+ a12x2+ a1nxn (=, (=, ) )b b1,1,a21x1+ a22x2+ a2nxn (=, (=, ) )b b2,2, am1x1+ am2x2+ amnxn (=, (=, ) )b bm m, ,xj j 0(0(j=1,n););s.t.Tizfxs tAxbxinmin(max) . .(,)0(1,2, ) 或或或或或或或或17三、线性规划问题的求解方法三、线性规划问题的求解方法二元线性规划问题的图解法二元线

15、性规划问题的图解法线性规划问题的理论解法线性规划问题的理论解法线性规划问题的线性规划问题的MATLAB软件解法软件解法18x=linprog(f, A, b): 求解求解 min z = f x,A x b求解线性规划的求解线性规划的MATLABMATLAB命令命令 若没有不等式约束若没有不等式约束,可用可用 替代替代A和和b, 若没有等式约束若没有等式约束,可用可用 替代替代Aeq和和beq, 若某个若某个xi下无界或上无界下无界或上无界,可设定可设定-inf或或 inf；用用x, Fval代替上述命令行中的代替上述命令行中的x，可得最优解处的函数值可得最优解处的函数值Fval。x=linp

16、rog(f, A, b, Aeq, beq): 求解：求解： min z = f x, A x b, Aeq x = beq；x=linprog(f, A, b, Aeq, beq, lb, ub): 指定指定lb x ub;719 x1 + 2x2 30， 3x1 + 2x2 60， 2x2 24，min Z= -40 x1 -50 x2s.t.例例1、解：程序如下解：程序如下c=-40,-50;c=-40,-50;a=1,2;3,2;0,2;a=1,2;3,2;0,2;b=30;60;24;b=30;60;24;x=x=linprog (c,a,b) (c,a,b) z=cz=c* *x

17、x1820 x1+x2 5,-6 x1 10, -1 x2 4;4;例例2:min Z= 4x1 +3x2s.t.解：解： % lp2.m % % lp2.m %c=4,3;a=1,1;b=5;c=4,3;a=1,1;b=5;vlb=-6;-1; %vlb=-6;-1; %lower bound of vector x % %vub=10;4; % vub=10;4; % upper bound of vector x % % x=linprog(c,a,b,vlb,vub)x=linprog(c,a,b,vlb,vub)z=cz=c* *x x1921x1+x2 +x3 7,-x1 +x2

18、-x3 -2,-2,x1 , x2 , ,x3 0 0;例例3:min Z = -x1+2x2 3x3s.t.20解：解：% lp3.m % lp3.m %c=-1,2,-3;a=1,1,1;-1,1,-1; b=7;-2;c=-1,2,-3;a=1,1,1;-1,1,-1; b=7;-2;vlb=0;0;0; % vlb=0;0;0; % lower bound of vector x % %vub=; % vub=; % upper bound of vector x % % x=linprg(c,a,b,vlb,vub)x=linprg(c,a,b,vlb,vub)z=cz=c* *x

19、x22minZ= 2x1 + x2+3x3+2x4 +2x5 +4x6 +3x7 +4x8 +2x9x1 +x4 +x7 = 40， x2 +x5 +x8 =15， x3 +x6 +x9 =35，x1 +x2+x3 50， x4+x5+x6 30， x7+x8+x9 10， xi 0， i 1,2,9;s.t.例例4:2123% % lp4.m %lp4.m %c=2,1,3,2,2,4,3,4,2;c=2,1,3,2,2,4,3,4,2;b=40;15;35;beq=50;30;10;b=40;15;35;beq=50;30;10;a(1,:)=1,0,0,1,0,0,1,0,0;a(1,:

20、)=1,0,0,1,0,0,1,0,0;a(2,:)=0,1,0,0,1,0,0,1,0;a(2,:)=0,1,0,0,1,0,0,1,0;a(3,:)=0,0,1,0,0,1,0,0,1;a(3,:)=0,0,1,0,0,1,0,0,1;aeq(1,:)=1,1,1,0,0,0,0,0,0;aeq(1,:)=1,1,1,0,0,0,0,0,0;aeq(2,:)=0,0,0,1,1,1,0,0,0;aeq(2,:)=0,0,0,1,1,1,0,0,0;aeq(3,:)=0,0,0,0,0,0,1,1,1;aeq(3,:)=0,0,0,0,0,0,1,1,1;vlb=zeros(9,1); %

21、vlb=zeros(9,1); % lower bound of vector x % %vub=; % vub=; % upper bound of vector x % % x=linprog(c,a,b,aeq,beq,vlb,vub)x=linprog(c,a,b,aeq,beq,vlb,vub)z=cz=c* *x x解：解：2224线性规划问题的图解法线性规划问题的图解法Ax=b (1)x 0 (2)maxZ=cx (3)定义定义1 1：满足约束：满足约束(1)、(2)的的x=(x1 , , xn)T称为称为LP问题的可行解，全部可行解的集问题的可行解，全部可行解的集合称为可行域。

22、合称为可行域。定义定义2 2：满足：满足(3)的可行解称为的可行解称为LP问题的最优解问题的最优解.231、两个概念、两个概念25 x1 + 2x2 30， 3x1 + 2x2 60， 2x2 24， x1，x2 0；max Z= 40 x1 +50 x2例例1:s.t.24、二元线性规划问题的图解法、二元线性规划问题的图解法26x2=0 (=0 (横横) ) (0,30), (20,0) 2x2 =24(1)、确定可行域、确定可行域解：解：x1 0;0;x1 =0 (=0 (纵纵) )x2 0;0;x1+2x2 30 x1+2x2 =30 (0,15) (30,0)与坐标轴交点与坐标轴交点:

23、3x1+2x2 =602x2 243x1+2x2 600 x2102030DABC3x1+2x2 = 60 x1+2x2 = 302x2 =243010 x12027(2)、求最优解、求最优解x* = (15,7.5)Z=40 x1+50 x20=40 x1+50 x2 x1+2x2 =30 3x1+2x2 =60C点点:0102030 x2DABC3x1+2x2 = 60 x1+2x2 = 302x2 = 24203010 x1Z=975Z=0Zmax =9753428(0 1)maxZ=40 x1+ 80 x2 x1+2x2 30,3x1+2x2 60, 2x2 24, x1 , x2 0

24、;0;例例2: 求解求解s.t.最优解：最优解：BC线段线段B点点 : x(1)=(6,12) C点点: x(2)=(15,7.5) BC线段线段: 21211xxxxx maxZ=1200 350102030 x2DABC3x1+2x2 = 60 x1+2x2 = 302x2 = 24203010 x1Z=1200Z=029例、例、 max Z=3x1+2x2 -x1 -x2 1,1,x1 , x2 0;0;即无可行解即无可行解.x2x1-1-1037s.t.可行域无解可行域无解.-x1 -x2 =1=130nnxcxcxcZ 2211max线性规划问题的理论解法线性规划问题的理论解法 ni

25、xbxaxaxabxaxaxatsimnmnmmnn, 2 , 1, 0.221111212111xCZTmax 0.xbAxtsA称为约束矩阵称为约束矩阵.或赋权向量。或赋权向量。称为价值向量称为价值向量TC21、 线性规划问题的标准形式线性规划问题的标准形式31化一般线性规划问题为标准形化一般线性规划问题为标准形)(1iijnjijbbxa （1）约束条件的转换：）约束条件的转换： 0)(11iniinjnjijiinjnjijxbxxabxxa或或inx 称为松弛变量或剩余变量称为松弛变量或剩余变量2232 x1 +2x2 +x3 =30， 3x1 +2x2 +x4 =60， 2x2 +

26、 +x5 =24， x1 , , x5 0 0 ； maxZ=40 x1+ 50 x2+0 x3 +0 x4+0 x5 x1 + 2x2 30， 3x1 + 2x2 60， 2x2 24， x1，x2 0；max Z= 40 x1 +50 x2例例1:s.t.其中其中x3 , x4, x5 为松弛变量为松弛变量 。s.t.2533minZ= 2x1 + 5x2 +6x3+8x44x1 + 6x2 + x3+2x4 12，x1 + x2 +7x3+5x4 14， 2x2 + x3+3x4 8， xi 0 (i =1,4)；例例2：minZ= 2x1 + 5x2 +6x3+8x4 +0 x5 +0

27、 x6 +0 x74x1 + 6x2 + x3+2x4 -x5 = =12，x1 + x2 +7x3+5x4 -x6 = =14， 2x2 + x3+3x4 x7= = 8， xi 0 (i =1,2,7)；其中其中x5 , x6, x7 为剩余变量为剩余变量 。s.t.s.t.2634(2)、变量、变量例例3:令令: : x1= x1- x1 3x1+2x2 8, x1 4x2 14,x2 0,0, x1 为自由变量为自由变量; ;(1)(1)3 x1 3 x1 +2x2 8, x1 x1 4x2 14,x1 , x1 , x2 0;0;(2)2735 0,jjjjjjxxxxxx则可令则可

28、令由变量），由变量），无非负限制，（称为自无非负限制，（称为自如果某个变量如果某个变量jjlx （2）变量转换：）变量转换：0 jjjlxyjjlx 0 jjjxly2336令令: : x1 = x1 +6, 则则 0 x1 16x1+x2 5,-6 x1 10,x2 0;0;(3)-6+6 x1+6 10+6易知易知:例例4:(3)x1 +x2 11,x1 16,x1 , x2 0;0;(4)2837(3)、目标函数的转换、目标函数的转换ZZ njjjxcZ1min njjjccZ1max令令Z = -ZxoZ2438将以下线性规划问题将以下线性规划问题x1+x2 +x3 7,x1 -x2

29、+x3 2,2,x1 , x2 0 0， x3为自由变量为自由变量;化为标准型。化为标准型。例例5:min Z = -x1+2x2 3x3s.t.2939 令令x3 =x4 - x5 加松弛变量加松弛变量x6加剩余变量加剩余变量x7 令令 Z= -Zmax Z= x1 2x2 +3x4 3x5 解：解：min Z = -x1+2x2 3x3x1+x2 +x3 7,x1 -x2 +x3 2,2,x1 , x2 0 0；s.t.x1 +x2 +x4 -x5 +x6 =7,x1 -x2 +x4 -x5 -x7 =2,x1 , x2 , x4 , x5 , x6 , x7 0;0;s.t.3040、线

30、性规划问题的理论解法、线性规划问题的理论解法:凸集凸集：定义定义1：Ax=b (1)x 0 (2)maxZ=cx (3)设设D是是n维欧氏空间的一个集合维欧氏空间的一个集合。任意点任意点x(1), x(2)DD, ,若任一满足若任一满足 x= x(1)+(1- ) x(2) (0 1)的点的点xDD。则则D称为凸集。称为凸集。38.x(2)x(1).x设线性规划的标准型设线性规划的标准型41B P1 PmN =Pm+1 Pna11 a1ma21 a2mam1 ammP1 Pma1m+1 a1na2m+1 a2namm+1 amnPm+1 PnA，定义定义2：基：基(基阵基阵) 若若A中一个子矩

31、阵方阵中一个子矩阵方阵B可逆，则矩阵可逆，则矩阵B称为称为LP问题的一个基问题的一个基(基阵基阵) 。基向量基向量:P1 Pm;非基向量非基向量:Pm+1 Pn;基变量基变量:x1 xmxB =;非基变量非基变量:xN =xm+1 xn;设设x=x1 xmxm+1 xn=xB xN，3942xB = B-1 b - B-1N xNA=BNx=xB xNAx=b记记:BxB +NxN=bBxB =b -NxN定义定义3：基本解：基本解称为称为Ax=b的一个基本解的一个基本解, 最多有最多有m m个非零分量。个非零分量。B-1 b 0 x=则称基则称基B B为为基本基本可行基。可行基。称为称为Ax

32、=b的一个基本的一个基本可行可行解。解。B-1 b 0 x=对应于基对应于基B，若若B-1 b 0 0，40 !mnnmcmn 最多最多43x1+2x2 +x3 =30,30,3x1+2x2 +x4 =60, 2x2 +x5=24,x1 x5 0;0;41例例1、b=306024取取B=P3 P4 P5=I 可逆可逆, 基阵基阵。1 2 1 0 03 2 0 1 00 2 0 0 1P1 P2 P3 P4 P5A=,N=P1 P2非基阵非基阵.非基向量非基向量xN=x1x2,xB=x3x4x5,基向量基向量x=xN xB解向量解向量4442xB = B-1 b - B-1N xNAx=b令令=

33、00 xN=x1x2则基本解则基本解 0 0306024x=xN xB=因为因为x 0 0，是是基本基本可行解。可行解。4543又又由由det(B1) =60, 知知B1可逆可逆,可以充当基矩阵可以充当基矩阵.1 2 13 2 0 0 2 0=若取若取B1 =(P1 P2 P3 )相应的非基阵相应的非基阵N1 =P4 P5xB1=x1x2x3,基变量基变量x4x5xN1=.非基变量非基变量得基本解得基本解令令1212-6 0 0 xB1 xN1x=(B1 ) -1 b 0=.x4x5xN1=00,非非基本基本可行解可行解46 -x3+x4 =0,0, x2 +x3 +x4 =3, -x1 +x

34、2 +x3+x4 =2,xj 0 0 ( j=1,2,3,4 );求出基变量是求出基变量是x1 , x3 , x4的基本解，是不是可行解？的基本解，是不是可行解？44例例2、给定约束条件给定约束条件解：解：0 -1 10 1 1-1 1 1B=(P1 P3 P4)= 0 1 -1 -1/2 1/2 0 1/2 1/2 0B-1= ,b=032 .4745 xB = x1 x3x4 = B-1 b 0 1 -1 -1/2 1/2 0 1/2 1/2 0=03213/23/2=是可行解是可行解.所以所以x =x1x2x3x4 1 03/23/2 =,48 设设x(1) , x (2) , , x(k) 是是n维欧氏空间中的维欧氏空间中的k个点