运筹学线性规划和单纯形法.ppt

运筹学运筹学 第一章第一章线性规划及单纯形法线性规划及单纯形法Linear Programming and Simplex Method1 本章内容提要w线性规划问题及其数学模型w线性规划解的概念w单纯形法原理及算法步骤w线性规划应用建模2如何合理地利用如何合理地利用有限的人、财、物有限的人、财、物等资源，得到最等资源，得到最好的经济效果好的经济效果?1.1 1.1 问题的提出问题的提出线性规划是以数学为工具，研究在一定的人、财、物等资源条件下，用最少的资源耗费，取得最大的经济效果。1.线性规划问题及数学模型线性规划问题及数学模型3 例1.1：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：问题：工厂应如何安排生产可获得最大的总利润？产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）15001500250025004 解：设变量xi为第i种（甲、乙）产品的生产件数（i1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3 x1+2x265；对设备B，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2x1+x240；5 对设备C，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x275；另外，产品数不可能为负，即 x1,x20。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500 x1+2500 x2。综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：6目标函数maxz=1500 x1+2500 x2约束条件s.t.3x1+2x2652x1+x2403x275x1,x2 0 这是一个典型的利润最大化的生产计划问 题。其 中，“max”是 英 文 单 词“maximize”的缩写，含义为“最大化”；“s.t.”是“subjectto”的缩写，表示“满足于”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1,x2的取值。7营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？8各种食物的营养成分表9解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：min S=14xmin S=14x1 1+6x+6x2 2+3x+3x3 3+2x+2x4 4 s.t.1000 xs.t.1000 x1 1+800 x+800 x2 2+900 x+900 x3 3+200 x+200 x4 4 3000 3000 50 x 50 x1 1+60 x+60 x2 2+20 x+20 x3 3+10 x+10 x4 4 55 55 400 x 400 x1 1+200 x+200 x2 2+300 x+300 x3 3+500 x+500 x4 4 800 800 x x1 1，x x2 2，x x3 3，x x4 4 0 010线性规划数学模型的构成三要素决策变量决策变量表示某种重要的可变因素，变量的一组数据代表一个解决的方案或措施，用x1,x2,xn表示目标函数目标函数决策变量的函数，目标可以是最大化或最小化约束条件约束条件对决策变量取值的限制条件，由决策变量x1,x2,xn的不等式组或方程组构成11一般形式 max(min)z=c1x1+c2x2+cnxn Subjectto a11 x1+a12 x2+a1n xn (=,)b1a21 x1+a22 x2+a2n xn (=,)b2.am1 x1+am2x2+amn xn(=,)bm x1,x2,xn01213标准形式maxz=c1x1+c2x2+cnxn Subjecttoa11x1+a12x2+a1n xn =b1a21x1+a22x2+a2n xn =b2am1x1+am2x2+amn xn=bm x1,x2,xn0其中bi0，i=1,2,m14标准形式 15标准形式：用向量和矩阵表述 16 可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式。171.极小化目标函数的问题：设目标函数为 minf=c1x1+c2x2+cnxn则可以令z-f，该极小化问题与下面的极大化问题有相同的最优解，即 maxz=-c1x1-c2x2-cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 minf-maxz182、约束条件不是等式的问题：设约束条件为 ai1 x1+ai2 x2+ain xnbi可以引进一个新的变量xn+1，使它等于约束右边与左边之差 xn+1=bi(ai1 x1+ai2x2+ain xn)显然，xn+1也具有非负约束(xn+10)，这时新的约束条件成为 ai1 x1+ai2x2+ain xn+xn+1=bi19当约束条件为 ai1 x1+ai2 x2+ain xnbi 时，类似地令 xn+1=(ai1 x1+ai2 x2+ain xn)-bi 显然有 xn+10，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn-xn+1=bi为了使约束由不等式成为等式而引进的变量xn+1称为“松弛变量”，后一种情况也称为“剩余变量”。203.变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj=xj-xj”其中 xj 0，xj”0即用两个非负变量之差来表示一个无符号限制的变量。当然xj的符号取决于xj和xj”的大小。214.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi m），秩为m。B=(P1,P2,Pm)是A中m阶非奇异子矩阵，则称B是线性规划问题的一个基矩阵基矩阵，简称基基。B中的列向量Pj 称为基向量基向量，与基向量Pj对应的变量xj称为基变量基变量，其它变量称为非基变量非基变量。令非基变量为0，则由Ax=b可求出一个解，这个解x称为基解基解。满足非负条件的基解称为基可行解基可行解。48maxz=1500 x1+2500 x2s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x50例1.7：把例1.1化为标准型：49 32100A=P1,P2,P3,P4,P5 =2101003001A矩阵包含以下10个33的子矩阵：B1=P1,P2,P3B2 =P1,P2,P4B3=P1,P2,P5B4 =P1,P3,P4B5=P1,P3,P5B6 =P1,P4,P5B7=P2,P3,P4B8 =P2,P3,P5B9=P2,P4,P5B10=P3,P4,P550 其中B4=0，因而B4不是该线性规划问题的基。其余均为非奇异方阵，因此该问题共有9个基。对于基B3=P1,P2,P5，在等式约束中令非基变量 x3=0,x4=0，解线性方程组：3x1+2x2+0 x5=652x1+x2+0 x5=400 x1+3x2+x5=75 得到x1=15,x2=10,x5=45，对应的基解为基可行解：x3=(x1,x2,x3,x4,x5)T=(15,10,0,0,45)T，对应的目标函数值z3=47500。故基B3是一个可行基。51 类似可得到 x2=(5,25,0,5,0)T （对应B2,z2=70000）x5=(20,0,5,0,75)T （对应B5,z5=30000）x7=(0,25,15,15,0)T（对应B7,z7=62500）x10=(0,0,65,40,75)T（对应B10,z10=0）是基可行解，x2是最优解；而 x1=(7.5,25,-7.5,0,0)T （对应B1）x6=(65/3,0,0,-10/3,75)T（对应B6）x8=(0,40,-15,0,-45)T （对应B8）x9=(0,32.5,0,7.5,-22.5)T（对应B9）是基解但不可行。52可行解基解基可行解可行解，基可行解，基解的关系533.2.3.2.凸集与顶点凸集与顶点凸集：如果在集合C中任意取两个点x1,x2，其连线上的所有点也都在集合C中，则称集合C为凸集。用数学解析式表达为：对n维欧式空间中的一个集合C,任意x1,x2C，和实数a，均有 ax1+(1-a)x2C (0a0，那么相应的非基变量xs，它的值从当前值0开始增加时，目标函数值随之增加。这个选定的非基变量xs称为进基变量，转（3）。如果任何一个非基变量的值增加都不能使目标函数值增加，即所有j非正，则当前的基本可行解就是最优解，计算结束；78（3）基可行解的转换在用非基变量表示的基变量的表达式（1-1）中，观察进基变量增加时各基变量变化情况，确定基变量的值在进基变量增加过程中首先减少到0的变量xr，满足，=min bi/ais ais 0=br/ars （1-2）这个基变量xr称为出基变量。当进基变量的值增加到 时，出基变量xr的值降为0时，可行解就移动到了相邻的基本可行解（顶点），转（4）。(1-2)即所谓的最小检验比规则。79如果进基变量的值增加时，所有基变量的值都不减少，即所有ais 非正，则表示可行域是无界的，且目标函数值随进基变量的增加可以无限增加，此时，不存在有限最优解，计算结束；（4）将进基变量作为新的基变量，出基变量作为新的非基变量，确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础上重复（2）。80表格单纯形法表格单纯形法 设定设定：bi 0 i=1,2,mmaxz=c1 x1+c2 x2+cn xns.t.a11 x1+a12 x2+a1n xn b1 a21 x1+a22 x2+a2n xn b2 am1 x1+am2 x2+amn xn bm x1,x2,xn 081加入松弛变量加入松弛变量：max z=c1 x1+c2 x2+cn xn s.t.a11 x1+a12 x2+a1n xn+xn+1=b1 a21 x1+a22 x2+a2n xn+xn+2=b2 am1 x1+am2 x2+amn xn+xn+m=bm x1,x2,xn,xn+1,xn+m 082显然，xj=0,j=1,n;xn+i=bi,i=1,m是基本可行解 对应的基是单位矩阵。以下是初始单纯形表：其中：z=i=1,m cn+i bi,j=cj-i=1,m cn+i aij为检验数，cn+i=0,an+i,i=1,an+i,j=0(ji),i,j=1,m83xB(1)=b1-(a1,N(1)xN(1)+a1,N(2)xN(2)+a1,N(n)xN(n)xB(2)=b2-(a2,N(1)xN(1)+a2,N(2)xN(2)+a2,N(n)xN(n)xB(m)=bm-(am,N(1)xN(1)+am,N(2)xN(2)+am,N(n)xN(n)z=z+N(1)xN(1)+N(2)xN(2)+N(n)xN(n)对任一可行基B=(PB(1),PB(2),PB(m)，则m个基变量为 xB(1),xB(2),xB(m)，n-m个非基变量为xN(1),xN(2),xN(n-m)。所有的基变量都用非基变量来表示：84对应的单纯形表：其中：aB(i),B(i)=1,aB(i),B(j)=0(ji),i,j=1,m85maxmin高斯迭代运算：86 例例1.9 化标准形式：化标准形式：max z=1500 x1+2500 x2 s.t.3 x1+2 x2+x3 =65 2 x1+x2+x4 =40 3 x2 +x5 =75 x1,x2,x3,x4,x5 087 例例1.9 化标准形式：化标准形式：max z=1500 x1+2500 x2 s.t.3 x1+2 x2+x3 =65 2 x1+x2+x4 =40 3 x2 +x5 =75 x1,x2,x3,x4,x5 0最优解最优解:x1*=5,x2*=25,x4*=5（松弛标量，表示松弛标量，表示B设备有设备有5个机时的剩余）个机时的剩余）最优值：最优值：z*=7000088 一般情况下初始基本可行解不明显。通常用以下两种方法求初始可行解:大M方法；两阶段法。初始可行解的获取初始可行解的获取89maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2 +a2nxn=b2.am1x1+am2x2+amnxn=bm x1,x2,xn0考虑标准问题：90大大M法：法：引入人工变量 xn+i0（i=1,m）及充分大正数M（也称惩罚因子）：maxz=c1x1+c2x2+cnxn-Mxn+1-Mxn+ms.t.a11 x1+a12 x2+a1n xn+xn+1=b1 a21 x1+a22 x2+a2n xn +xn+2 =b2.am1 x1+am2 x2+amn xn +xn+m=bmx1,x2,xn,xn+1,xn+m091显然,xj=0,j=1,n;xn+i=bi,i=1,m是基本可行解，对应的基是单位矩阵。结论：若得到的最优解(x1,xn,xn+1,xn+m)满足xn+i=0,i=1,m，则(x1,xn)是原问题的最优解；否则，原问题无可行解。92例1.10：（LP）maxz=5x1+2x2+3x3-x4s.t.x1+2x2+3x3=152x1+x2+5x3=20 x1+2x2+4x3+x4=26x1,x2,x3,x4093 maxz=5x1+2x2+3x3-x4-Mx5-Mx6s.t.x1+2x2+3x3 +x5=152x1+x2+5x3 +x6=20 x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x60大大M法：法：94 maxz=5x1+2x2+3x3-x4-Mx5-Mx6s.t.x1+2x2+3x3 +x5=152x1+x2+5x3 +x6=20 x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x60959697最优解：(25/3,10/3,0,11)T 最优目标值：112/398两阶段法：大M法不适合计算机求解，因此进一步产生两阶段法。第一阶段：引入人工变量 xn+i0，i=1,m 构造一个新的目标函数:maxz=-xn+1-xn+2-xn+ms.t.a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2 =b2.am1x1+am2x2+amnxn+xn+m=bm x1,x2.xn,xn+1,xn+m099 第一阶段求解上述问题，将人工变量从基变量中换出，以求出原问题的初始基本可行解结论：若得到的最优解满足 xn+i=0,i=1,m 则是原问题的基本可行解;否则，原问题无可行解。第二阶段以得到的初始基本可行解为基础对原目标函数求最优解。100 第一阶段问题 maxz=-x5-x6 s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20 x1+2x2+4x3+x4=26 x1,x2,x3,x4,x5,x60两阶段法：101第一阶段第一阶段原问题的基本可行解：(0,15/7,25/7,52/7)T 102第二阶段第二阶段:划去人工变量，划去人工变量，把基本可行解填入表中原问题的最优解：(25/3,10/3,0,11)T；最优目标值：112/3103单纯形法解的几种情况讨论（1）有唯一最优解（2）有无穷多最优解（最优解不唯一）（3）有无界解(有可行解但无最优解)（4）无可行解（无解）（5）退化104（1）唯一最优解 最优表中所有非基变量的检验数非零大于零,则线性规划具有唯一最优解（2）无穷多解 当最优单纯形表中存在非基变量对应的检验数为零时，存在无穷多解。105求解线性规划求解线性规划【解解】:化为标准型后用单纯形法计算如下表所示化为标准型后用单纯形法计算如下表所示无穷多解的例子106XBx1x2x3x4x5b(1)x3x4x5111221100010001410225j24000(2)x2x4x51/221/21001/211/201000126438j40200(3)x2x1x50101001/41/23/41/41/21/40017/235/21410/3j00020(4)x2x1x30101000011/31/31/31/32/34/38/314/310/3j00020107 表表(3)中中j全部非正全部非正,则最优解为则最优解为:表表(3)表表明明,非非基基变变量量x3的的检检验验数数3=0,x3若若增增加加,目目标标函函数数值值不不变变,即即当当x3进进基基时时Z仍仍 等等于于20。使使x3进进基基x5出出基基继继续续迭迭代代,得得到到表表(4)的另一的另一 基本最优解基本最优解 X(1),X(2)是线性规划的两个最优解，它的凸组合是线性规划的两个最优解，它的凸组合 仍是最优解，从而原线性规划仍是最优解，从而原线性规划有多重最优解。有多重最优解。108（3）有无界解某某 个个 检检 验验 数数 k0且且 对对 应应 的的 Pk（i=1，2,m）则线性规划具有无界解）则线性规划具有无界解109求解线性规划求解线性规划【解解】化为标准型化为标准型110初始单纯形表为初始单纯形表为XBx1x2x3x4bx3x4322110011411002=10,x2进进基基，而而a120，a220的非基变量中选取下标最小的进基；当有多个变量同时可作为出基变量时，选择下标最小的那个变量出基。119求解线性规划求解线性规划解解 用大用大M单纯形法，加入人工变量单纯形法，加入人工变量x4、x5，构造数学模型，构造数学模型退化的例子120Cj121MMbCBXBX1x2x3x4x5(1)MMx4x51429414100141618/7j15M2+11M118M00(2)1Mx3x51/41/21/22101/47/2011244j3/41/2M5/2+2M01/4+9/2M0(3)1Mx1x5102142140140j04+M3+2M1+5M0(4)12x1x2100182942140j0011M17M4(5)11x1x31041/2011221/240j015/20M17M3/2121一般线性规划化为标准型小结122续表123单纯形法计算步骤小结单纯形法计算步骤小结124练习：练习：125练习：练习：A=3,b=2,c=4,d=-2,e=2,f=3,g=1,h=0,i=5,j=5,k=-1.5,l=0126 线性规划可以应用在线性规划可以应用在管理、经济、金融、管理、经济、金融、战争、通讯、工程设计等战争、通讯、工程设计等各个领域。很多决各个领域。很多决策问题可以抽象为线性规划模型。线性规划策问题可以抽象为线性规划模型。线性规划方法的应用为社会带来了无法估量的巨大效方法的应用为社会带来了无法估量的巨大效益。益。合理利用线材问题合理利用线材问题混合配料问题混合配料问题产品计划问题产品计划问题连续投资连续投资人员安排问题人员安排问题5.5.线性规划应用选讲线性规划应用选讲127合理利用线材问题合理利用线材问题现要做100套钢架,每套用长为2.9m,2.Im和1.5m的元钢各一根制成.已知原料长7.4米，问应如何下料，使用的原材料最省？128129生产存储问题电扇厂每月最多可生产3000台电扇，每台成本100元。如果当月销售不了，那么每台每月要支付10元的存储费。设4、5、6月的销售量预计为1000台、2500台和4000台。已知4月初没留有存货，也不要求6月底留下存货。问如何安排4、5、6月的生产计划，可使得总的生产、存储费最低？130假设4、5、6月份分别生产x1、x2、x3台目标函数minz=100（x1+x2+x3)+10(x1-1000)+10(2500-x1-x2)约束条件s.t.x11000 x1-1000+x22500 x1+x2-1000-2500+x3=4000 x13000 x23000 x33000 x1,x2,x3 0131动态投资问题动态投资问题132动态投资问题动态投资问题 133某某商商场场决决定定：营营业业员员每每周周连连续续工工作作5天天后后连连续续休休息息2天天，轮轮流流休休息息。根据统计，商场每天需要的营业员如表根据统计，商场每天需要的营业员如表1.2所示。所示。表表1.2 营业员需要量统计表营业员需要量统计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。最少。星期星期需要人数需要人数星期星期需要人数需要人数一一300五五480二二300六六600三三350日日550四四400人力资源分配的问题人力资源分配的问题134【解解】设设xj(j=1，2，7)为休息为休息2天后星期一到星期日开始上天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为班的营业员，则这个问题的线性规划模型为 星星期期需要需要人数人数星星期期需要人需要人数数一一300五五480二二300六六600三三350日日550四四400135混合配料问题混合配料问题136混合配料问题混合配料问题137混合配料问题混合配料问题138TheEnd139选择题线性规划问题的标准型最本质的特点是A目标要求是极小化B变量可以取任意值C变量和右端常数要求非负 D约束条件一定是不等式形式线性规划可行域的顶点一定是可行解非基本解非可行最优解140X是线性规划的基本可行解，则有X中的基变量非负，非基变量为零X中的基变量非零，非基变量为零X不是基本解X不一定满足约束条件141判断题是一个线性规划数学模型142判断题可行解一定是基解基解可能是可行解线性规划的可行域无界则具有无界解可行解集有界非空时,则在顶点上至少有一点达到最优值可行解集不一定是凸集143