线形规划与单纯形法

线性规划及单纯形法,线性规划及单纯形法,线性规划问题及其数学模型图解法单纯形法原理数学试验,第一节线性规划问题及其数学模型,一、问题的提出,线性规划主要解决：如何利用现有的资源，使得预期目标达到最优。,例1美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润最大？,表1-1,解：设公司制造、两种家电分别为件。,问题：x1=?x2=?利润Z最大？,设备A工时限制：,设备B工时限制：,解：公司制造、两种家电分别为件。,调试工序时间限制：,利润：,即要求：,表1-1,其中,目标函数,约束条件,资源约束,非负约束,约束条件可记s.t(subjectto),意思为“以,为条件“、”假定“、”满足“之意。,例2：捷运公司在下一年度的14月份的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于下表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租用期限不同的合同。试确定该公司签订租借合同的最优决策，目的是使所租借费用最少。,表1-2,表1-3,单位：100m2,单位；元/100m2,解：设表示捷运公司在第i(i=1,2,3,4)月初签订的租期为j(j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。,表1-2,表1-3,单位：100m2,单位；元/100m2,15,10,20,12,经过上面的讨论，得到下面的LP模型：,目标函数,约束条件,每一个问题都有一组变量-称为决策变量，一般记为,下面从数学的角度来归纳上述两个例子的共同点。,每个问题中都有决策变量需满足的一组约束条件-线性的等式或不等式。,对决策变量每一组值：,代表了,一种决策方案。通常要求决策变量取值非负，即,二、线性规划问题的数学模型,都有一个关于决策变量的线性函数-称为目标函数。要求这个目标函数在满足约束条件下实现最大化或最小化。,将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划。有时也将线性规划问题简记为LP（linearprogramming)其数学模型为：,上述模型的简写形式为：,若令,线性规划问题可记为矩阵和向量的形式：,用向量表示时，上述模型可写为：,三、线性规划问题的标准形式：,LP问题的数学模型的标准形式为：,其中常数项,LP问题标准形式的特征是：,求目标函数的最大值；约束条件为变量满足线性方程组与非负性两部分；方程组中常数项皆非负。,下面分析如何将LP问题标准化：,若目标函数为,引进新的目标函数,则,的最小值即为,的最大值，即：,从而目标函数变换为：,例1将LP问题,化为标准形。,例1将LP问题,化为标准形。,解：引进新的目标函数,于是原LP问题化为标准形式：,1.3单纯形法原理,1、复习：非齐次线性方程组解,例：解非齐次线性方程组,增广矩阵,（1）,若线性方程组没有现成的基，可利用增广矩阵的行初等变换法找到一组基。,为基变量。,称,其变量个数=,此方程组的解为,其中,为任意实数。,为非基变量，或自由变量。,称,称非基变量,为0的解（15，24，5，0，0）叫基解。,若对（1）式中的变量再加上非负限制,其解为,由,的非负性知：,（2）,从而,解域为,注意：此时的,已经不是任意实数。,不是自由变量了。,而对于带有非负约束的方程组,解的每个分量都是非负数，就叫做可行解。,如果基解是可行的，就叫基可行解。,基可行解所对应的基称为可行基。,非基,可行最优基基,非可行基,四种形式的基之间的关系为：,基与解的对应关系：,非可行解,可行基本解可行解,基本解,解与解之间的关系为：,基解,基,可行基,基可行解,最优基,基最优解,所对应的解,例如,是可行解。,所对应的解,是基本解。,也是可行解，故而是基本可行解。,（1）式中为一组可行基。,但并不是所有基都有资格充当可行基。例如（1）中,（-6）,所对应的方程组为：,令非基变量,为0，得到基解：,非可行解。,即,非可行基。,基可行解很重要，可以证明以下定理：,定理1若线性规划问题存在最优解，则问题的可行域是凸集。,定理2线性规划问题的基可行解对应线性规划问题可行域（凸集）的顶点。,定理3若线性规划问题最优解存在，则最优解一定在可行域顶点处取得。,由此可看出，最优解要在基可行解（可行域顶点）中找。,通过以上分析，可得到以下几个结论：,（1）线性规划问题的可行域是一个凸集，可行域可能有界，也可能无界，但其顶点数是有限个。（？）,（2）线性规划问题每个基本可行解对应于可行域的一个顶点。,（3）若线性规划问题有最优解，则必可在其可行域的某个（或多个）顶点上达到最优值。,如何从一个可行基找另一个可行基？称基变换。,定义：两个基可行解称为相邻的，如果它们之间仅变换一个基变量。对应的基称为相邻可行基。,例LP问题,当前可行基所对应的基本可行解,相应地，将代入目标函数得,显然不是最优。,因为从经济意义上讲，,意味着该厂不安排生产，因此没有利润。,从数学角度看，若让非基变量取值从零增加，,(对应可行域的),相应的目标函数值Z也将随之增加。因此有可能找到一个,新的基本可行解，使其目标函数值有所改善。即进行基变,换，换一个与它相邻的基。再注意到前的系数5比,前的系数2大，即每增加一个单位对Z的贡献比大。,故应让从非基变量转为基变量，称为进基。又因为基,变量只能有三个，因此必须从原有的基变量,中选一个离开基转为非基变量，称为出基。谁出基？,又因为仍留作非基变量，故仍有,（2）式变为,再让从零增加，能取得的最大值为,此时，已经从24降到了0，达到了非基的取值，变成非基变量。从而得到新的可行基。,由此得到一个新的基本可行解：,目标函数值：,从目标函数值明显看出，比明显地得到了改善。,此基本可行解对应可行域的,将（2）式,（2）,可行基,留在左边，非基变量,移到右边,（3）,用代入法的：,（4）,用代入法的：,（4）,代入目标函数得：,这一过程用增广矩阵的行初等变换表示为：,1/6,（-1）,（-2）,按最小比值规则：,主元素,目标函数系数行,按最小比值规则：,3/2,（-5）,（-1/3）,（-1/3）,所对应的LP问题,可行基,令非基变量为0，得到最优解,最优值,总结：在迭代过程中要保持常数列向量非负，这能保证基可行解的非负性。最小比值能做到这一点。主元素不能为0。因为行的初等变换不能把0变成1。主元素不能为负数。因为用行的初等变换把负数变成1会把常数列中对应的常数变成负数。,此基本可行解对应可行域的,其结果与图解法一致。,表1-7P/29,表1-8P/30,表1-9P/30,例2解LP问题：,对单纯形矩阵作初等行变换，有：,按最小比值原则：,确定主元素。,（-1）,（-1）,3。无穷多个解情况：,至此，检验行已没有正数，当前解即为最优解。,此时对应的LP问题为：,0,此时对应的LP问题为：,0,此时对应的LP问题为：,0,1,当,时，不管取何值，均有目标函数,取得最大值1。此时约束方程为：,其中为基变量。,用非基变量表示出基变量：,其中，为自由变量。设为有:,其中c是满足非负性的任意常数。,再由,的非负性，知：,解出,（其中）,最优解为：,最优值为：,另解：,当前最优基变量对应最优解为：,再强行让检验数为0的进基，再找一个最优解：,确定主元素。,1/3,按最小比值原则：,2,以与的连线段：,即,为全部解的一般形式。,若令：,有,4。无最优解的两种情况：,无界解,例3解LP问题：,解：,对单纯形矩阵作初等行变换，有：,1/2,（-2）,注意到6所在的列无正元素，将基变量及目标函数用非基变量表示为,从目标函数看，若令非基变量,无限增大，S也无限,性，即该LP问题所追求的目标函数是无界的。既无最大值，于是该LP问题无最优解。,增大，且没有影响的非负,无解,例7/P34求解LP问题,解：可行域为空集，无可行解。,下面先把此LP问题化为标准型，然后用单纯形法求解。,对单纯形矩阵作初等行变换，有：,1/2,从最后一个矩阵可看出，此LP问题无可行基，当然就无可行解。,（-1）,（-1）,（-1）,LP当前解已是最优的四大特征：,存在一组(初始)可行基（其系数矩阵为单位阵）。,检验行的基变量系数=0。,检验行的非基变量系数0。,全部0唯一解。,存在=0无穷多个解。,常数列向量0。,下面的问题是：所给LP的标准型中约束矩阵中没有现成的可行基怎么办？,下面介绍求初始可行基的方法：,最小比值法,例6用单纯形法求解LP问题,解：先将其化为标准形式,对单纯形矩阵作初等行变换，有：,（-1）,（-3）,1/6,（-3）,2,3,3/2,（-3）,（-1/3）,至此，检验行已没有正数，当前解即为最优解。,最优值为：,人工变量法（也称大M法）,针对标准形约束条件的系数矩阵中不含单位矩阵的处理方法。,例6用单纯形法求解LP问题,第五节单纯形的进一步讨论,解：先将其化为标准形式,再强行加上人工变量，使其出现单位矩阵：,但这样处理后：不易接受。因为是强行引进，称为,人工变量。它们与不一样。称为松弛变量和剩,余变量，是为了将不等式改写为等式而引进的，而改写前后,两个约束是等价的。人工变量的引入一般来说是前后不等,价的。只有当最优解中，人工变量都取值零时（此时人工,变量实质上就不存在了）才可认为它们是等价的。,处理办法：把人工变量从基变量中赶出来使其变为非基变量。为此，发明者建议把目标函数作如下处理：,其中M为任意大的实数，“-M”称为“罚因子”。用意：只要人,工变量取值大于零，目标函数就不可能实现最优。,对此单纯形矩阵作初等行变换，有：,M,M,（-1）,（-3）,（-4M）,1/6,3/2,（-1/3）,（-3）,至此，检验行已没有正数，当前解即为最优解。,最优值为：,例7/P34求解LP问题,去掉人工变量，即得原LP问题的最优解：,解：从上面已看出，此LP问题无解。下面用大M法求解看一,下会出现什么情况。引进人工变量，上述问题化为：,对单纯形矩阵作初等行变换，有：,M,（-2）,（-2-2M）,至此，检验行已没有正数，当前解即为最优解。,但此时基变量为：,含非零的人工变量,矛盾。说明原问题无可行解。,使用大M法小结：,对LP问题,式中,则在每个约束方程左边加上一个人工变量,（1.1）,（1.2）,式（1.2）中含有一个m阶单位阵。以,为基变量。得到一个初始基本可行解：,我们可以从出发进行迭代。,（1.3),当以式（1.2）为约束的线性规划问题的最优解中，人工变量都处在非基变量位置（即取零值），则原问题有最优解，且将前者最优解中去掉人工变量部分即为后者最优解。,当（1.2）问题的最优解中包含非零的人工变量时，则,原问题无可行解。,当（1.2）问题最优解的基变量中包含人工变量，但该人,工变量取值为零，这时可将某个非基变量引入基变量中，,来替换该人工变量。从而得到原问题的最优解。,从式（1.3）的做初始基本可行基解进行迭代时，目标是尽快把人工变量从基变量中全部“赶”出去（如果能全部“赶”出去的话）。所用方法除了大M法外，还有下面的两阶段法。,3。两阶段法,用大M法处理人工变量时，若用计算机处理，必须对M给出一个较大的具体数据，并视具体情况对M值作适当的调整。,为了克服这一麻烦，下面的两阶段法将问题拆成两个LP问题分两个阶段来计算：,第一阶段求解第一个线性规划：,若求得的单纯形矩阵中，所有人工变量都处在非基变量的位置。即及。则从第1阶段去掉人工变量后，即为原问题的初始单纯形矩阵。,若第一阶段所求得的单纯形中仍含有（解）非零的人工变量，则说明原问题无可行解。不再进入第2阶段。,进入第2阶段。,因此两阶段法的第1阶段求解有两个目的：一为判断原问题,有无可行解。二，若有，则得原问题的一个初始可行基，再,对原问题进行第2阶段的计算。,下面对例6用两阶段法求解：,第1阶段的线性规划问题可写为：,先对目标函数标准化：令有,对单纯形矩阵作初等行变换，有：,（-3）,（-4）,1/6,（-1）,（-3）,（-6）,2,转入第2阶段：,3/2,（-1/3）,（-1）,数学试验,LINDO软件包,LINDO软件包介绍,初试LINDO用LINDO求解整数规划注意事项,LINDO是一种专门用于求解数学规划问题的优化计算软件包,版权现在由美国LINDO系统公司(LindoSystemInc.)所拥有.LINDO软件包的特点是程序执行速度很快,易于输入、修改、求解和分析一个数学规划(优化问题),因此LINDO在教育、科研和工业界得到广泛应用.有关该软件的发行版本、发行价格和其他最新信息都可以从LINDO系统公司的INTERNET网络站点获取,该站点还提供部分LINDO软件的演示版本或测试版本学生版和演示版与发行版的主要区别在于对优化问题的规模(变量和约束数)有不同的限制.,LINDO是LinearInteractiveandDiscreteOptimizer字首的缩写形式,可以用来求解线性规划(LP-LinearProgramming)、整数规划(IP-IntegerProgramming)和二次规划(QP-QuadraticProgramming)问题.LINDO学生版可求解多达200个变量和100个约束的规划问题.,初试LINDO,如解如下LP问题:,LINDO中己假设所有的变量都是非负的,所以非负约束条件不必再输入到计算机中;LINDO也不区分变量中的大小写字符(实际上任何小写字符都将被转换为大写字符);约束条件中的“=”可用“”代替.上述问题用键盘输入如下:,：MAX2X+3Y?ST,(说明:也可写成S.T.,SUCHTHAT或SUBJECTTO等）,?4X+3Y10?3X+5Y12?END：,注：目标函数为第1行,两个约束条件分别为第2,3行.,直接键入运行命令(GO)就可得到解答,屏幕显示如下:,:GOLPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1）7.4545450VARIABLEVALUEREDUCEDCOSTX1.272727.000000Y1.636364.000000ROWSLACKORSURPLUSDUALPRICES.000000.090909.000000.545455NO.ITERATIDNS=2DORANGE(SENSITIVITY)ANALYSIS?,单纯形法在2次迭代后得到最优解。,最优目标值,最优解：,:GOLPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1）7.4545450VARIABLEVALUEREDUCEDCOSTX1.272727.000000Y1.636364.000000ROWSLACKORSURPLUSDUALPRICES2）.000000.0909093）.000000.545455NO.ITERATIDNS=2DORANGE(SENSITIVITY)ANALYSIS?,单纯形进行了2次迭代,带有松弛变量和剩余变量的最优解：,检验数,减少的成本,对偶价格,一个问题解答之后,LINDO会询问是否需要作灵敏度分析(DORANGE(SENSITIVITY)ANALYSIS?).如果不需要,你应回答N(No),回到提示符:之下.,如果想重新看到刚才输入的模型,可键入LOOK命令,LINDO会询问具体的行号范围(也可直接将行号范围写在LOOK后).典型的行号范围可以是3,或1-2,或ALL,而结果相应地会显示出第3行、第1-2行,或问题的所有行.如:,:LOOKROW:,3(等价于直接命令“LOOK3”),3)3X+5Y=12:,如果想修改问题,可键入ALTER命令,LINDO会询问行号,变量名及新的系数,例如:若想将上述问题中约束条件4x+3y10,修改为6x+3y10,然后再全部看一下,并求解新问题,那么键入ALTER命令后相应要键入2,X,6然后再键入:“LOOKALL”.在相应位置再键入“GO”，就会给出解答.以下是屏幕上演示过程:,：ALTERROW：2VAR：XNEWCOEFFICIENT：6(等价于直接命令“ALTER2X6”）,:LOOKALLMAX2X+3YSUBJECTTO2)6X+3Y=103）3X+5Y=12,END:GOLPOPTIMUMFOUNDATSTEPOOBJECTIVEFUNCTIONVALUE1)7.333333VARIABLEVALUEREDUCEDCOSTX.666667.000000Y2.0000.000000ROWSLACKORSURPLUSDUALPRICES.000000.047619.000000.571429,NO.ITERATIONS=0DORANGE(SENSITIVITY)ANALYSIS?N:QUIT,改动约束条件的右端项,可以将RHS(即right-handside)作为变量名.改变约束条件中的不等号方向(如,可以将DIR作为变量名.修改问题还可用EXT命令(增加新的约行),DEL命令(去掉一行)和APPC命令(增加一个新的变量),也可用EDIT全屏幕编辑器.,灵敏度分析,下面用一个具体例子来说明LINDO软件求对偶变量及进行灵敏度分析.,例有一家具制造车间,制造书桌(DESK)、桌子(TABLE)、椅子(CHAIR),所用原料及木工、漆工的数据如表1所示.,表1,若要求桌子的生产量不超过5件,问如何安排三种产品的产量可使收入最大?,用分别表示书桌、桌子、椅子的生产量.建立LP模型:,将上述模型输入LINDO并求解:,：MAX6OX1+3OX2+2OX3?S.T?2)8X1+6X2+x348?3)4XI+2X2+1.5X320?4)2XI+1.5X2+0.5X38?5)X25?END:GO,LPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)280.00000VARIABLEVALUEREDUCEDCOSTXI2.000000.000000X2.0000005.000000X38.000000.000000ROWSLACKORSURPLUSDUALPRICES2)24.000000.0000003).00000010.0000004).00000010.0000005)5.000000.000000,LINDO在2次迭代后得到最优解。,最优目标值,最优解,带有松弛变量的最优解,检验数,NO.ITERATIONS=2DORANGE(SENSITIVITY)ANA