运筹学 02 线性规划.ppt

《运筹学 02 线性规划.ppt》由会员分享，可在线阅读，更多相关《运筹学 02 线性规划.ppt（85页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性规划Linear Programming1.线性规划及其数学模型LP and Its Mathematical Model 2.线性规划的图解法Graphic Method of LP3.线性规划解的概念与性质Concepts and Properties of LP Solution 4.线性规划的单纯形法Simplex Method of LP5.线性规划的软件包解法Package Method of LP6.线性规划的应用举例Applications of LP1 线性规划及其数学模型v线性规划问题的提出v线性规划的基本概念v线性规划的数学模型v线性规划模型的共同特征v线性规划模型的

2、一般形式v线性规划模型的标准形式问题的提出v例1：生产计划问题。工厂要安排生产两种产品：产品和产品，各需要设备、原材料A和原材料B，有关数据见表。问：如何安排生产使利润最大？产品产品资源限量设备128台时原材料A4016kg原材料B0412kg单台产品利润23产品I产品如何安排生产使利润最大?基本概念v决策变量(Decision variables)v目标函数(Objective function)v约束条件(Constraint conditions)v可行域(Feasible region)v最优解(Optimal solution)问题要确定的未知量，表明规划中用数量表示的方案、措施，可

3、由决策者决定和控制。是决策变量的函数。决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。满足约束条件的决策变量的取值范围。可行域中使目标函数达到最优(最大或者最小)的决策变量的值。数学模型v第1步-确定决策变量v第2步-定义目标函数v第3步-表示约束条件v第4步-形成数学模型第1步-确定决策变量设 x1产品的产量x2产品的产量第2步-定义目标函数 Max z=2 x1+3 x2决策变量决策变量目标函数最大化第3步-表示约束条件 x1+2 x2 84 x1 16 4 x2 12 x1,x2 0对我们有何限制?资源约束非负约束第4步-形成数学模型目标函数 Max Z=2

4、x1+3 x2约束条件 x1+2 x2 8 4 x1 16 4 x2 12 x1,x2 0 x1 x2线性规划模型的共同特征v一组决策变量X表示一个方案，一般X大于等于零。v约束条件是关于X的线性等式或不等式。v目标函数是线性的，求目标函数最大化或最小化线性规划模型的一般形式 线性规划模型的标准形式目标函数最大右边常数非负约束条件等式决策变量非负简写用向量表示用矩阵表示C价值向量b资源向量A约束条件系数矩阵X决策变量向量0零向量线性规划问题的标准化v目标函数求最大值min Z=CX 等价于 max Z=-CXv约束条件右边常量为非负负数常量两边乘以-1，如x1-5等价于-x15v约束条件为等式

5、“”约束：加上非负松驰变量“”约束：减去非负松弛变量v决策变量为非负x0：令x=-x，则x0 x变量为无符号要求：令x-x=x，其中x,x0线性规划问题的标准化-例1+x3=+x4=+x5=vmax z=2x1+3x2x1+2x284x1 16 4x212 x1,x20vmax z=2x1+3x2+0 x3+0 x4+0 x5 x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12x1,x2,x3,x4,x50结果线性规划问题的标准化-例2vmin z=-x1+2x2-3x3x1+x2+x37x1-x2+x32-3x1+x2+2x3=7x1,x20,x3无约束令x3=x4-x5

6、，其中x4,x50。加上x6,x7，非负约束条件为：x1,x2,x4,x5,x6,x70max z=x1-2x2+3(x4-x5)+0 x6+0 x7x1+x2+(x4-x5)+x6=7x1-x2+(x4-x5)-x7=23x1+x2+2(x4-x5)=7vmax f=-z=x1-2x2+3(x4-x5)+0 x6+0 x7x1+x2+(x4-x5)+x6=7x1-x2+(x4-x5)-x7=2-3x1+x2+2(x4-x5)=7x1,x2,x4,x5,x6,x70结果课堂练习：建立LP数学模型v例2：有两个煤厂A、B，每月产量分别为60吨、100吨；三个居民区X、Y、Z从这些煤厂获得一定量煤

7、，每月需要量分别为45吨、75吨、40吨；单位运价见表。求运费最少的运输方案。居民区AB需求量X10445Y5875Z61540供应量601002 线性规划的图解法v图解法v图解法求解步骤v线性规划问题求解的几种可能结果v由图解法得到的启示图解法9 8 7 6 5 4 3 2 1 0|123456789x1x2x1+2x2=8目标函数 Max Z=2x1+3x2 约束条件 x1+2x2 8 4x1 16 4x2 12 x1,x204x1=164x2=122x1+3x2=6最优解(4,2)；最大值14图解法求解步骤v由全部约束条件作图求出可行域；v作目标函数等值线，确定使目标函数最优的移动方向；

8、v平移目标函数的等值线，找出最优点，算出最优值。线性规划问题求解的几种可能结果(a)唯一最优解 6 5 4 3 2 1 0|123456789x2x1(b)无穷多最优解6 5 4 3 2 1 0 x2|123456789x1(c)无界解 Max z=x1+x2 -2x1+x2 4 x1-x2 2 x1,x2 0 x2x1(d)无可行解 max z=2x1+3x2 x1+2x28 4x1 16 4x2 12 -2x1+x24 x1,x20可行域为空集图解法的几点结论(由图解法得到的启示)v在二维空间中图解法只能解决两个变量的线性规划问题v可行域是有界或无界的凸多边形v若线性规划问题存在最优解，它

9、一定可以在可行域的顶点得到v若两个顶点同时为最优解，则其连线上的所有点都是最优解v解题思路：找出凸集的顶点，计算其目标函数值，比较即得课堂练习：用图解法求解LP问题v Max z=34 x1+40 x24 x1+6 x248 2 x1+2 x2182 x1+x216x1,x203 线性规划解的性质v线性规划解的概念v线性规划解的关系图v线性规划问题的几何意义v基本定理v几点结论v求解LP的基本思路线性规划问题解的概念v标准型：max Z=CX,AX=b,X0v可行解：满足约束条件AX=b,X0的解X称为线性规划问题的可行解；全部可行解的集合称为可行域v最优解：使Z=CX达到最大值的可行解称为最

10、优解；对应的目标函数值称为最优值v基、基向量、基变量、非基变量：若B是系数矩阵A中mm阶非奇异子矩阵(B0)，则B是线性规划问题的一个基。不妨设B=(P1 P2 Pm)，则Pj为基向量；Xj(j=1,2,m)为基变量；Xj(j=m+1,m+2,n)为非基变量v基解：令非基变量为0，解出AX=b的X为基解v基可行解：非负的基解X称为基可行解v可行基：对应于基可行解的基称为可行基线性规划解的关系图 非可行解非可行解可行解可行解 基可行解基可行解 基解基解 最优解？最优解？例3：求基解、基可行解、最优解max z=2 x1+3 x2+1 x3+0 x4+0 x5x1+x3=5x1+2 x2+x4=1

11、0 x2+x5=4x1,x2,x3,x4,x50分析：设x4,x5为已知数，x1,x2,x3为未知数，得x2=4-x5x1=10-x4-2x2=10-x4-8+2x5=2-x4+2x5x3=5-x1=3+x4-2x5则z=2(2-x4+2x5)+3(4-x5)+(3+x4-2x5)=19-x4-x5序号x1x2x3x4x5z基可行解10051045是20452017是35005410是40550-120否5100-50415否652.5001.517.5是7540-3022否82430019是最优解最优解x1=2-x4+2x5x2=4-x5x3=3+x4-2x5z=19-x4-x5线性规划问题

12、的几何意义v凸集：设K是n维欧氏空间的一点集，对任意属于K中的两点X(1)和X(2)，若其连线上的任意点X()=X(1)+(1-)X(2)也属于K，其中01，则称K为凸集。v顶点：若K是凸集，对于属于K的任意一点X都不能用属于K的任意不同两点X(1)和X(2)线性表示，则称X为K的一个顶点(或极点)。v凸组合：设X(1),X(2),X(k)是n维欧氏空间中的k个点，若存在k个实数1,2,k，满足0i1(i=1,2,k)，且1+2+k=1，则称X=1X(1)+2X(2)+kX(k)为X(1),X(2),X(k)的凸组合。X n=2，k=3基本定理定理1 若线性规划问题存在可行域，则此可行域是凸集

13、。证明：设线性规划可行域是D=X|AX=b,X0。在D中任取不同的二点X(1)和X(2)，即X(1)X(2)，则必有AX(1)=b,X(1)0;AX(2)=b,X(2)0。令X是X(1)和X(2)连线上的任意点，即存在01，使得 X=X(1)+(1-)X(2)。则AX=AX(1)+(1-)X(2)=AX(1)+(1-)AX(2)=b+(1-)b=b且易知X0，即X属于D。根据定义，D为凸集。定理2 线性规划问题的可行解为基可行解的充要条件是该可行解的正分量所对应的系数列向量是线性独立的。证明：(1)必要性。由基可行解的定义可知。(2)充分性。若P1,P2,Pk线性独立，则必有km；当k=m时，

14、它们恰好构成一个基，从而X=(x1,x2,xm,0,0)T为相应的基可行解。当k2，对应变量x2每增加一个单位对利润的贡献是3个单位，比x1明显。故确定x2为换入变量v确定换出变量可以理解所有资源都用于增加x2的数量，最大能增加多少。资源1(对应x3)：82=4资源2(对应x4)：160=资源3(对应x5)：124=3min(4,3)=3，确定x5为换出变量转第3步v基变量x2,x3,x4，非基变量x1,x5。约束条件变为2x2+x3=8-x1x4=16-4x14x2=12-x5v解得x2=3-0.25x5x3=2-x1+0.5x5x4=16-4x1v代入目标函数中得到z=9+2x1-0.75

15、x5v令非基变量x1=x5=0，得到x=(0,3,2,16,0)Tv目标函数z=9转第4步，第5步v目标函数中20，没有达到最优，继续。v确定换入变量目标函数系数只有2为正数，确定对应的变量x1为换入变量v确定换出变量x2=3-0.25x5(对应x2)：30=x3=2-x1+0.5x5(对应x3)：21=2x4=16-4x1(对应x4)：164=4min(,2,4)=2，确定x3为换出变量转第3步v基变量x1,x2,x4，非基变量x3,x5。约束条件变为x2=3-0.25x5 x1+2x2=8-x3x1=2-x3+0.5x5 或者 4x1+x4=164x1+x4=16 4x2 =12-x5v解

16、得x1=2-x3+0.5x5x2=3-0.25x5x4=8+4x3-2x5v代入目标函数中得到z=2x1+3x2=13-2x3+0.25x5v令非基变量x3=x5=0，得到x=(2,3,0,8,0)Tv目标函数z=13转第4步，第5步v目标函数中0.250，没有达到最优，继续。v确定换入变量目标函数系数只有0.25为正数，确定对应的变量x5为换入变量v确定换出变量x1=2-x3+0.5x5(对应x1)：2(-0.5)=-4(无意义)x2=3-0.25x5(对应x2)：30.25=12x4=8+4x3-2x5(对应x4)：82=4min(-,12,4)=4，确定x4为换出变量转第3步v基变量x1

17、,x2,x5，非基变量x3,x4。约束条件变为x1-0.5x5=2-x3 x1+2x2=8-x3x2+0.25x5=3 或者 4x1=16-x42x5=8+4x3-x4 4x2+x5=12v解得x1=4-0.25x4x2=2-0.5x3+0.125x4x5=4+2x3-0.5x4v代入目标函数中得到z=2x1+3x2=14-1.5x3-0.125x4v令非基变量x3=x4=0，得到x=(4,2,0,0,4)Tv目标函数z=14转第4步v目标函数z=14-1.5x3-0.125x4中非基变量x3的系数、x4的系数分别为-1.5、-0.125，均小于0，线性规划已经达到最优，停止计算v结论：最优解

18、x=(4,2,0,0,4)T；最优目标值z=14单纯形法的表格计算步骤为书写规范和便于计算，对单纯形法的计算设计了单纯形表。每一次迭代对应一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表。本节介绍用单纯形表计算线性规划问题的步骤。初始单纯形表，第1次迭代BV-zx1x2x3x4x5b1230000 x31210084x44001016-x50400112312000-0.75-9x31010-0.522x440010164x201000.253-第1次迭代，第2次迭代BV-zx1x2x3x4x5b12000-0.75-9x31010-0.522x440

19、010164x201000.253-100-200.25-13x11010-0.52-x400-41284x201000.25312第2次迭代，第3次迭代BV-zx1x2x3x4x5b100-200.25-13x11010-0.52-x400-41284x201000.25312100-1.5-0.1250-14x11000.2504x500-20.514x2010.5-0.12502BV-zx1x2x3x4x5b1230000 x31210084x44001016-x50400112312000-0.75-9x31010-0.522x440010164x201000.253-100-200.

20、25-13x11010-0.52-x400-41284x201000.25312100-1.5-0.1250-14x11000.2504x500-20.514x2010.5-0.12502单纯形法理论基础Cc1c2cnCBXBB-1bx1x2xnB-1Az=CBB-1bC-CBB-1A标准型线性规划中设A=(B,N)，X=(XB,XN)T，C=(CB,CN)(1)求基可行解求基可行解。根据AX=b，得(B,N)(XB,XN)T=b，即 BXB+NXN=b，XB=B-1b-B-1NXN=B-1b(令XN=0)(2)求目标函数值求目标函数值。z=CX=(CB,CN)(XB,XN)T=CBXB+CN

21、XN=CBB-1b+(CN-CBB-1N)XN=CBB-1b(令XN=0)(3)检验数检验数。C-CBB-1A=(CB,CN)-CBB-1(B,N)=(0,CN-CBB-1N)(4)解XB=B-1b是最优解的充要条件是C-CBB-1A0C23000CBXBB-1bx1x2x3x4x50 x381210040 x41640010-0 x512040013z=0230000 x321010-0.520 x4164001043x2301000.25-z=92000-0.752x121010-0.5-0 x4800-41243x2301000.2512z=1300-200.252x141000.250

22、0 x5400-20.513x22010.5-0.1250z=1400-1.5-0.1250单纯形法的进一步讨论人工变量法v一、大M法v二、两阶段法人工变量!?人工变量v问题的提出前述线性规划针对“型”约束条件进行单纯形法求解，只要各加上一个松弛变量就可以自然得到一个初始可行基(单位矩阵)，方便迭代假如线性规划问题化为标准形时，约束条件有“型”或者“=型”，则不容易得到初始可行基(单位矩阵)，迭代不方便若标准线性规划系数矩阵中不存在单位矩阵，如何构造初始可行基？大 M 法v人工变量与约束条件人工变量x是人为加入约束条件中的变量，其真实取值为0，但为了构造单位矩阵，设置该变量人工变量只加入等式约

23、束条件左边v人工变量与目标函数由于人工变量x只是形式上的变量，其实质是x=0，为了便于计算，目标函数中人工变量系数为-M或者M(用M表示很大正数)，只要人工变量大于0，则目标函数永远无法获得最优值对max型线性规划，人工变量系数为-M对min型线性规划，人工变量系数为Mv例5：用大M法求解下列线性规划问题vmax z=3x1-x2-x3x1-2x2+x311-4x1+x2+2x33-2x1+x3=1x1,x2,x30+x4-x5+x6+x7-Mx6-Mx7v引入松弛变量x4、剩余变量x5、人工变量x6和x7，将原线性规划标准化，得到下列线性规划问题vmax z=3x1-x2-x3+0 x4+0

24、 x5-Mx6-Mx7x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1x1,x2,x3,x4,x5,x6,x70BV-zx1x2x3x4x5x6x7b13-1-100-M-M0 x41-21100011x6-4120-1103x7-2010001113-6M-1+M-1+3M0-M004Mx41-21100011x6-4120-1103x7-20100011BV-zx1x2x3x4x5x6x7b13-6M-1+M-1+3M0-M004Mx41-2110001111x6-4120-11031.5x7-20100011111-1+M00-M01-3M1+

25、Mx43-20100-110 x60100-11-21x3-20100011BV-zx1x2x3x4x5x6x7b11-1+M00-M01-3M1+Mx43-20100-110-x60100-11-211x3-20100011-11000-11-M-1-M2x43001-22-512x20100-11-21x3-20100011BV-z x1x2x3x4x5x6x7b11000-11-M-1-M2x43001-22-5124x20100-11-21-x3-20100011-1000-1/3-1/31/3-M2/3-M-2x11001/3-2/32/3-5/34x20100-11-21x3001

26、2/3-4/34/3-7/39两阶段法v在用大M法计算时，可以设定M=10000或者更大，计算机也能处理v但M在计算机上处理不容易判断，分阶段处理先求初始基再求解v两阶段步骤第一阶段：构造人工变量之和为目标函数的线性规划问题，要求最小化，并求解；若有解且为0，则进一步进行第二阶段计算；否则无解第二阶段：去掉人工变量，还原目标函数系数，做出初始单纯形表，用单纯形法求解即可单纯形法计算中的几个问题v目标函数极小化时解的最优性判断只需用检验数j0作为最优性的标志v无可行解的判断当求解结果出现所有j0 时，如基变量仍含有非零的人工变量(两阶段法求解时第一阶段目标函数值不等于0)，则问题无可行解。v退化

27、 基可行解中存在基变量=0的解退化解v换入变量和换出变量的Bland规则选择j中下标最小的非基变量xk为换入变量,这里：k=min(j|j0)5 线性规划的软件包解法v管理运筹学运算软件2.5版(参见教学光盘)vLindovLingovMatlabvExcelLindoLindo可以用来求解线性规划问题。Lindo软件的数据输入要求变量的线性组合形式全在不等式左边，而常数在右边，每一行只能输入一种命令或一个函数说明。Title Production mixed problemmax 3x1+5x2stx142x2123x1+2x218endLingoLingo可以用来求解线性规划问题、非线性规

28、划问题、排队论、库存论等很多问题。Lingo软件的数据输入与Lindo软件的数据输入类似，但也存在差异。MODEL:max=3*x1+5*x2;x1=4;2*x2=12;3*x1+2*x2=18;endMatlabMatlab软件可以解大量的优化问题，包括线性的、非线性的、无约束的和有约束的等等function x,fval=prodmix(c,A,b,Aeq,beq);c=-5,4,2;A=6,-1,1;1,2,4;b=8,10;vlb=-1,0,0;vub=3,2;Aeq=;beq=;x,fval=linproc(c,A,b,Aeq,vlb,vub)title(Product Mix Pr

29、oblem);Excel6 线性规划的应用举例v线性规划模型条件(1)要求解问题的目标函数能用数值指标来反映，且为线性函数；(2)存在着多种方案；(3)要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式来描述。v线性规划的应用举例(一)运输问题(二)布局问题(三)分派问题(一)运输问题v设某种物资有m个产地，A1，A2，A m；联合供应n个销地：B1，B2，Bn。各产地产量(单位：吨)，各销地销量(单位：吨)，各产地至各销地单位运价(单位：元/吨)如下表所示。产地B1B2Bn产量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnam销量b1b2bn

30、如何调运，才使总运费最少？(1)产销平衡的运输问题满足a1+am=b1+bn的运输问题为产销平衡的运输问题。设xij表示由产地Ai运往销地Bj的物资数量(i=1,2,m;j=1,2,n)。那么，上述运输问题的数学模型为：求一组变量xij(i=1,2,m;j=1,2,n)的值,使总运费最低。min z=c11x11+c12x12+c1nx1n+cmnxmnxi1+xi2+xin=ai (i=1,2,m)x1j+x2j+xmj=bj (j=1,2,n)xij0 (i=1,2,m;j=1,2,n)(2)产大于销的运输问题满足a1+amb1+bn的运输问题为产大于销的运输问题。设xij表示由产地Ai运

31、往销地Bj的物资数量(i=1,2,m;j=1,2,n)。那么，上述运输问题的数学模型为：求一组变量xij(i=1,2,m;j=1,2,n)的值,使总运费最低。min z=c11x11+c12x12+c1nx1n+cmnxmnxi1+xi2+xinai (i=1,2,m)x1j+x2j+xmj=bj (j=1,2,n)xij0 (i=1,2,m;j=1,2,n)(3)产小于销的运输问题满足a1+amb1+bn的运输问题为产小于销的运输问题。设xij表示由产地Ai运往销地Bj的物资数量(i=1,2,m;j=1,2,n)。那么，上述运输问题的数学模型为：求一组变量xij(i=1,2,m;j=1,2,

32、n)的值,使总运费最低。min z=c11x11+c12x12+c1nx1n+cmnxmnxi1+xi2+xin=ai (i=1,2,m)x1j+x2j+xmjbj (j=1,2,n)xij0 (i=1,2,m;j=1,2,n)(二)布局问题v作物布局。在n块地上种植m种作物，已知各块土地 亩数、各种作物计划播种面积及各种作 物在各块的单产(每亩的产量)如表(与运输问题相似)。问：如何合理安排种植计划，才使总产量最多。v表格与运输问题类似；模型求最大化(略)(三)分派问题v设有n件工作B1,B2,Bn分派给n个人A1,A2,An去做，每人只做一件工作且每件工作只分派一人去做。设Ai完成Bj的工时为cij(i,j=1,2,n)。问：应如何分派才使完成全部工作的总工时最少。B1B2BnA1c11c12c1nA2c21c22c2nAncn1cn2cnnv设工作Bj分派给工人Ai去做的情况为xij(1表示做，0表示不做)。B1B2 Bn工人A1x11x12 x1n1A2x21x22 x2n1 1Anxn1xn2 xnn1工作1111