运筹学课件我的资源1-线性规划

2020/5/10,Copyright2013Czhang.Allrightsreserved.,张冲南京邮电大学经济管理学院Email：zcbling,线性规划与单纯形法,2020/5/10,Copyright2013Czhang.Allrightsreserved.,Chapter1线性规划(LinearProgramming),LP的数学模型图解法单纯形法单纯形法的进一步讨论人工变量法LP模型的应用,本章主要内容：,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,1.规划问题,生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。,线性规划通常解决下列两类问题：,（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标,（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.）,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,例1.1如图所示，如何截取x使铁皮所围成的容积最大？,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,例1.2生产计划问题胜利家具厂生产桌子和椅子两种家具。桌子售价50元，椅子售价30元，生产1个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120，油漆工工时为50。该厂如何生产才能使每月销售收入最大？,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,生产方案1：能生产25个桌子，木工剩余20小时，销售收入1250元生产方案2:生产20个桌子，10个椅子，木工仍剩余10小时，销售收入1300元；生产方案3：生产15个桌子，20个椅子，用完全部工时，销售收入1350元,2020/5/10,Copyright2013Czhang.Allrightsreserved.,资源使用利用表,线性规划问题的数学模型,2020/5/10,Copyright2013Czhang.Allrightsreserved.,目标函数Maxz=50 x1+30 x2约束条件4x1+3x21202x1+x250 x1,x20,线性规划问题的数学模型,2020/5/10,Copyright2013Czhang.Allrightsreserved.,例1.3:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,问题：工厂应如何安排生产可获得最大的总利润？,线性规划问题的数学模型,2020/5/10,Copyright2013Czhang.Allrightsreserved.,解：设变量xi为第i种（甲、乙）产品的生产件数（i1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3x1+2x265；对设备B，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2x1+x240；,线性规划问题的数学模型,2020/5/10,Copyright2013Czhang.Allrightsreserved.,对设备C，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x275；另外，产品数不可能为负，即x1,x20。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500 x1+2500 x2。综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：,线性规划问题的数学模型,2020/5/10,Copyright2013Czhang.Allrightsreserved.,目标函数Maxz=1500 x1+2500 x2约束条件3x1+2x2652x1+x2403x275x1,x20,线性规划问题的数学模型,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,练习某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,2.线性规划的数学模型由三个要素构成,决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints,其特征是：（1）问题都用一组决策变量表示某个方案（2）问题的约束条件是一组多个决策变量的线性不等式或等式。（3）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；,怎样辨别一个模型是线性规划模型？,2020/5/10,Copyright2013Czhang.Allrightsreserved.,合理利用线材问题：如何在保证生产的条件下，下料最少配料问题：在原料供应量的限制下如何获取最大利润投资问题：从投资项目中选取方案，使投资回报最大产品生产计划：合理利用人力、物力、财力等，使获利最大劳动力安排：用最少的劳动力来满足工作的需要运输问题：如何制定调运方案，使总运费最小,在管理中一些典型的线性规划应用,2020/5/10,Copyright2013Czhang.Allrightsreserved.,练习,1某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：,设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?,2020/5/10,Copyright2013Czhang.Allrightsreserved.,解：设xi表示第i班次时开始上班的司机和乘务人员数,这样建立如下的数学模型：目标函数：Minx1+x2+x3+x4+x5+x6约束条件：s.t.x1+x660 x1+x270 x2+x360 x3+x450 x4+x520 x5+x630 x1,x2,x3,x4,x5,x60,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,目标函数：,约束条件：,3.线性规划数学模型的一般形式,简写为：,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,向量形式：,其中：,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,矩阵形式：,其中：,2020/5/10,Copyright2013Czhang.Allrightsreserved.,图解法,线性规划问题的求解方法,一般有两种方法,图解法单纯形法,两个变量、直角坐标三个变量、立体坐标,适用于任意变量、但必需将一般形式变成标准形式,下面我们分析一下简单的情况只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。,2020/5/10,Copyright2013Czhang.Allrightsreserved.,1、在平面上建立直角坐标系2、图示约束条件，找出可行域3、图示目标函数和寻找最优解,图解法的步骤：,图解法,2020/5/10,Copyright2013Czhang.Allrightsreserved.,图解法,maxZ=2X1+X2X1+1.9X23.8X1-1.9X23.8s.t.X1+1.9X210.2X1-1.9X2-3.8X1，X20,例1.6用图解法求解线性规划问题,2020/5/10,Copyright2013Czhang.Allrightsreserved.,图解法,x1,x2,o,X1-1.9X2=3.8(),X1+1.9X2=3.8(),X1-1.9X2=-3.8(),X1+1.9X2=10.2(),4=2X1+X2,20=2X1+X2,17.2=2X1+X2,11=2X1+X2,Lo：0=2X1+X2,（7.6，2）,D,maxZ,minZ,此点是唯一最优解，且最优目标函数值maxZ=17.2,可行域,maxZ=2X1+X2,2020/5/10,Copyright2013Czhang.Allrightsreserved.,图解法,maxZ=3X1+5.7X2,x1,x2,o,X1-1.9X2=3.8(),X1+1.9X2=3.8(),X1-1.9X2=-3.8(),X1+1.9X2=10.2(),（7.6，2）,D,L0：0=3X1+5.7X2,maxZ,（3.8，4）,34.2=3X1+5.7X2,蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值maxZ=34.2是唯一的。,可行域,2020/5/10,Copyright2013Czhang.Allrightsreserved.,图解法,minZ=5X1+4X2,x1,x2,o,X1-1.9X2=3.8(),X1+1.9X2=3.8(),X1+1.9X2=10.2(),D,L0：0=5X1+4X2,maxZ,minZ,8=5X1+4X2,43=5X1+4X2,（0，2）,可行域,此点是唯一最优解,2020/5/10,Copyright2013Czhang.Allrightsreserved.,无界解无有限最优解,2020/5/10,Copyright2013Czhang.Allrightsreserved.,例1.8,无解无可行解,2020/5/10,Copyright2013Czhang.Allrightsreserved.,习题1：maxZ=40 x1+50 x2,2020/5/10,Copyright2013Czhang.Allrightsreserved.,(1)、建立坐标系,x1+2x230 x1+2x2=30(0,15)(30,0),3x1+2x2=60(0,30)(20,0),2x2=24,X1+2X2303X1+2X2602X224X1,X20,x10 x1=0(纵)x20 x2=0(横),(2)、确定可行域,解：,maxZ=40 x1+50 x2,2020/5/10,Copyright2013Czhang.Allrightsreserved.,(3)、求最优解,解：x1=15,x2=7.5,Z=40 x1+50 x2x2=-4/5x1+Z/50,maxZ=975,maxZ=40 x1+50 x2,2020/5/10,Copyright2013Czhang.Allrightsreserved.,最优解：BC线段B点x(1)=(6,12)C点x(2)=(15,7.5),求解,2020/5/10,Copyright2013Czhang.Allrightsreserved.,图解法,2,4,6,x1,x2,2,4,6,无界解(无最优解),maxZ=x1+2x2,习题3：,x1+x2=4(),x1+3x2=6(),3x1+x2=6(),maxZ,minZ,2020/5/10,Copyright2013Czhang.Allrightsreserved.,x1,x2,O,10,20,30,40,10,20,30,40,50,50,无可行解(即无最优解),maxZ=3x1+4x2,习题4：,2020/5/10,Copyright2013Czhang.Allrightsreserved.,习题:5,2020/5/10,Copyright2013Czhang.Allrightsreserved.,x1,x2,0,4,Q2(4,2),Q1,Q3,Q4,4x1=16,4x2=12,x1+2x2=8,3,Q2,4o.向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后交点，这种点就对应最优解。,2020/5/10,Copyright2013Czhang.Allrightsreserved.,maxz=x1+3x2s.t.x1+x26-x1+2x28x10,x20,可行域,目标函数等值线,最优解,6,4,-8,6,0,x1,x2,练习,习题6,2020/5/10,Copyright2013Czhang.Allrightsreserved.,当目标函数的直线族经过某一顶点时。,线性规划解的情况,2020/5/10,Copyright2013Czhang.Allrightsreserved.,当目标函数的直线族与某约束条件直线平行，且该问题有解时。,线性规划解的情况,2020/5/10,Copyright2013Czhang.Allrightsreserved.,有解但可行域可伸展到无穷时,线性规划解的情况,2020/5/10,Copyright2013Czhang.Allrightsreserved.,约束条件直线无公共区域。,线性规划解的情况,线性规划解的情况,2020/5/10,Copyright2013Czhang.Allrightsreserved.,图解法,学习要点：1.通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解）2.作图的关键有三点：(1)可行解区域要画正确(2)目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,4.线性规划问题的标准形式,2020/5/10,Copyright2013Czhang.Allrightsreserved.,对比,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,简记：,特点：(1)目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,5如何化标准形式,目标函数的转换,如果是求极小值即，则可将目标函数乘以(-1)，可化为求极大值问题。,也就是：令，可得到上式。,即,2020/5/10,Copyright2013Czhang.Allrightsreserved.,minZ=2x1+5x2+6x3+8x4,maxZ=-Z=-2x15x2-6x3-8x4,返回,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,变量的变换,若存在取值无约束的变量，可令其中：,变量的变换,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,令x1=x1-x1x10 x10,令x2=-x2x20,例,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,约束方程的转换：由不等式转换为等式。,称为松弛变量,称为剩余变量,2020/5/10,Copyright2013Czhang.Allrightsreserved.,约束条件,x3为松弛变量,x4为剩余变量,松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。,当约束条件为“”时，,当约束条件为“”时，,线性规划问题的数学模型,2020/5/10,Copyright2013Czhang.Allrightsreserved.,例,maxZ=2x1+x2,+0x3+0x4+0x5,5x2156x1+2x224x1+x25xi0(i=1,2),+x3=15,+x4=24,+x5=5,5）,线性规划问题的数学模型,2020/5/10,Copyright2013Czhang.Allrightsreserved.,例,minZ=2x1+5x2+6x3+8x4,4x1+6x2+x3+2x412x1+x2+7x3+5x4142x2+x3+3x48xi0(i=1,4),-x5=12,-x6=14,-x7=8,7）,+0 x5+0 x6+0 x7,线性规划问题的数学模型,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,变量的变换,可在等式两端乘以“-1”。当出现一个时，表示出现退化，这点将在以后讨论。,2020/5/10,Copyright2013Czhang.Allrightsreserved.,x1+x2+x3-9,-x1-x2-x39,线性规划问题的数学模型,例,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,例1.10将下列线性规划问题化为标准形式,用替换，且,解:（）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,(2)第一个约束条件是“”号，在“”左端加入松驰变量x4，x40,化为等式；(3)第二个约束条件是“”号，在“”左端减去剩余变量x5，x50；,(4)第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令z=-z,得到maxz=-z，即当z达到最小值时z达到最大值，反之亦然;,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,标准形式如下：,2020/5/10,Copyright2013Czhang.Allrightsreserved.,将minZ=-x1+2x23x3,化为标准型,例1.11：,线性规划问题的数学模型,2020/5/10,Copyright2013Czhang.Allrightsreserved.,解：令x3=x4-x5x40，x50,加松弛变量x6,减剩余变量x7,令Z=-Z,maxZ=x12x2-3x4+3x5+0 x6+0 x7,线性规划问题的数学模型,2020/5/10,Copyright2013Czhang.Allrightsreserved.,练习,习题：,解,2020/5/10,Copyright2013Czhang.Allrightsreserved.,练习,解,2020/5/10,Copyright2013Czhang.Allrightsreserved.,练习,习题3：将以下线性规划问题转化为标准形式minZ=-3x1+5x2+8x3-7x4s.t.2x1-3x2+5x3+6x4284x1+2x2+3x3-9x4396x2+2x3+3x4-58x1,x3,x40,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划的相关概念,k阶子式-在mn矩阵A中，任取k行与k列（km,kn），位于这些行列交叉处的k2个元素，不改变它们在A中所处的位置而得的k阶行列式，成为矩阵A的k阶子式。秩-设在矩阵A中有一个不等于0的r阶子式，且所有阶子式（如果存在的话）全等于，那么称为矩阵的最高阶非零子式，数称为矩阵的秩，记作（）。并规定零矩阵的秩等于。,线性规划问题的数学模型,2020/5/10,Copyright2013Czhang.Allrightsreserved.,矩阵的初等变换：（1）对调矩阵的两行或两列；（2）以非零数k乘矩阵的某一行（列）的所有元素；（3）以数k乘矩阵的某行（列）的所有元素加到另一行（列）的对应元素上去。,对方程组的系数矩阵A作初等行变换，得到新的方程组与原方程组同解。,线性规划的相关概念,线性规划问题的数学模型,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,6.线性规划问题的解,线性规划问题,求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,可行解：满足约束条件、的解为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最大值的可行解。,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划问题的数学模型,基：设A为约束条件的mn阶系数矩阵(m0,则判定原问题无可行解。,第2阶段：去除人工变量，求解原问题。第一阶段的最优解为原问题的初始基可行解。,2020/5/10,Copyright2013Czhang.Allrightsreserved.,maxZ=-x1+2x2,x1+x22-x1+x21x23x1x20,例：,x1+x2-x3=2-x1+x2-x4=1x2+x5=3x1x50,1.化标准型：,maxZ=-x1+2x2,+x6,+x7,2.增加人工变量，构造单位矩阵：,x6,x70,2020/5/10,Copyright2013Czhang.Allrightsreserved.,3.建立只包含人工变量的辅助问题。,minW=x6+x7,x1+x2-x3+x6=2-x1+x2-x4+x7=1x2+x5=3x1x70,2020/5/10,Copyright2013Czhang.Allrightsreserved.,0000011CBxBbx1x2x3x4x5x6x71x6211-100101x71-1(1)0-10010 x5301001000-211000,0 x11/210-1/21/201/2-1/20 x23/201-1/2-1/201/21/20 x53/200-1/21/21-1/2-1/20000011,1x6120-1101-10 x21-110-10010 x52100110-1-201-1002,解为：X=(1/2,3/2,0,0,3/2,0,0)。,目标函数值为:minW=x6+x7=0可转入第二阶段。去除人工变量，以第一阶段最优解为基可行解。,解为：X=(0,3,1,2,0)T。,目标函数值为:maxZ=-x1+2x2=6,4.去除人工变量，以第一阶段的最优解为基可行解,求解原问题。,0 x4120-1102x2211-1000 x51-10101-30200,0 x42100112x23010010 x31-10101-1000-2,2020/5/10,Copyright2013Czhang.Allrightsreserved.,单纯形法小结,单纯性法小结:,2020/5/10,Copyright2013Czhang.Allrightsreserved.,找出初始基可行解列出初始单纯形表,计算检验数i,所有i0,基变量中含人工变量,有非基变量检验数为零,唯一最优解,对某一i0有Pi0,无界解,无可行解,无穷多最优解,xk进基,迭代运算1.用xk替换xl2.列出新的单纯形表1）对主元素行（第l行）blbl/alk,alj/alk2)其他行（il）bibiaikbl/alk，aij=aij-aikalj/alk,是,是,是,是,否,否,否,否,单纯形法计算步骤框图,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划模型的应用,一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。,要求解问题的目标函数能用数值指标来反映，且为线性函数存在着多种方案要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划在管理中的应用,人力资源分配问题,例1.11某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：,设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少?,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划在管理中的应用,解：设xi表示第i班次时开始上班的司机和乘务人员人数。,此问题最优解：x150，x220，x350，x40，x520，x610，一共需要司机和乘务员150人。,2020/5/10,Copyright2013Czhang.Allrightsreserved.,线性规划在管理中的应用,2.生产计划问题,某厂生产、三种产品，都分别经A、B两道工序加工。