1、二线性规划与目标规划二线性规划与目标规划第一章第一章 线性规划与单纯形法线性规划与单纯形法线性规划问题及其数学模型线性规划问题及其数学模型线性规划问题的几何意义线性规划问题的几何意义单纯形法及计算步骤单纯形法及计算步骤单纯形法的进一步讨论单纯形法的进一步讨论一、问题的提出一、问题的提出在生产和经营等管理工作中，需要经在生产和经营等管理工作中，需要经常进行计划或规划。常进行计划或规划。问题归结为：问题归结为：在现有各项资源条件下，如何确定方在现有各项资源条件下，如何确定方案，使预期目标达到最优。案，使预期目标达到最优。1 线性规划问题及其数学模型线性规划问题及其数学模型例例 某公司计划制造一型，
2、二型两种家用某公司计划制造一型，二型两种家用电器。已知各制造一件时分别占用的设电器。已知各制造一件时分别占用的设备备A,B的台时、调试时间、调试工序及每的台时、调试时间、调试工序及每天可用于这两种家电的能力、各售出一天可用于这两种家电的能力、各售出一件时的获利情况，如表件时的获利情况，如表1-1所示。问该公所示。问该公司每天应制造两种家电各多少件，使获司每天应制造两种家电各多少件，使获取的利润最大。取的利润最大。表表1-1项目项目一型一型二型二型每天可用能力每天可用能力设备设备A(h)0515设备设备B(h)6224调试工序调试工序(h)115利润利润(元元)21例例2捷运公司在下一年度的月的
3、个月捷运公司在下一年度的月的个月内拟租用仓库堆放物资。已知各月份所需仓库内拟租用仓库堆放物资。已知各月份所需仓库面积列于下表面积列于下表1-2。仓库租借费用随合同期而。仓库租借费用随合同期而定，期限越长，折扣越大，具体数据见表定，期限越长，折扣越大，具体数据见表1-3。租借仓库的合同每月初都可办理，每份合同具租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该公司可根据需体规定租用面积和期限。因此该公司可根据需要，在任何一个月初办理租借合同。每次办理要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租时可签一份合同，也可签若干份租用面积和租借期限不同
4、的合同，试确定该公司签订租借合借期限不同的合同，试确定该公司签订租借合同的最优策略，目的使所付租借费用最小。同的最优策略，目的使所付租借费用最小。12201015所需仓库面积所需仓库面积4321月份月份表表1-2 单位：单位：100m27300600045002800合同期内的租费合同期内的租费4个月个月3个月个月2个月个月1个月个月合同租借期限合同租借期限表表1-3 单位：元单位：元/100m2例例3 3某工厂拥有某工厂拥有A A、B B、C C三种类型的设备，生产甲、三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，
5、每件产品可以获得的利润以及用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：三种设备可利用的时数如下表所示：用线性规划制订使总利润最大的生产计划。用线性规划制订使总利润最大的生产计划。例例1变量选取：变量选取：二、线性规划问题的数学模型二、线性规划问题的数学模型21,xx表示每天制造一型，二型家电的数量表示每天制造一型，二型家电的数量获取利润：获取利润：212xxz 数学模型：数学模型：目标函数目标函数约束条件约束条件212xxzmax 0,052426155.2121212xxxxxxxst变量选取变量选取ijx：目标函数目标函数约束条件约束条件 012201015.
6、4132231432312322141323222114131214131211ijxxxxxxxxxxxxxxxxxxxxxst5,0 jixij如果(单位为单位为100m2)表示在第表示在第i(i=1,2,3,4)个月初签订的租期个月初签订的租期为为j(j=1,2,3,4)个月的仓库的面积的合同个月的仓库的面积的合同)(4500322212xxx )(60002313xx 147300 x)(280041312111xxxx zmin变量，或决策变量变量，或决策变量用以表明规划中的用数量表示的方案、措施，可由用以表明规划中的用数量表示的方案、措施，可由决策者决定和控制决策者决定和控制目标函
7、数目标函数决策变量的函数，按优化目标分别在该函数前加上决策变量的函数，按优化目标分别在该函数前加上max或或min约束条件约束条件决策变量取值时受到的各种资源条件的限制，通常决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式表达为含决策变量的等式或不等式规划问题数学模型三要素规划问题数学模型三要素决策变量的取值是连续的决策变量的取值是连续的目标函数是决策变量的线性函数目标函数是决策变量的线性函数约束条件是决策变量的线性等式或不等约束条件是决策变量的线性等式或不等式式实际问题中的线性含义实际问题中的线性含义严格的比率性严格的比率性可叠加性可叠加性线性规划的数学模型线性规划
8、的数学模型线性规划数学模型的一般形式线性规划数学模型的一般形式目标函数目标函数约束条件约束条件)1.1(.min)max(2211nnxcxcxcz 或)2.1(,.,2,1,0),(.),(.),(.22112222212111212111 nixbxaxaxabxaxaxabxaxaxastimnmnmmnnnn线性规划模型一般形式的和式表示线性规划模型一般形式的和式表示目标函数目标函数 njjjxcz1min)max(或约束条件约束条件)4.1(,.,2,1,0),.,2,1(),(.1 nixmibxastinjijij线性规划模型一般形式的向量表示线性规划模型一般形式的向量表示目标函
9、数目标函数CXz min)max(或约束条件约束条件)5.1(0),(.1 XbxPstnjjj mmjjjjnnbbbbaaaPxxxXcccC21212121;,.,线性规划模型一般形式的矩阵表示线性规划模型一般形式的矩阵表示目标函数目标函数CXz min)max(或约束条件约束条件)6.1(0),(.XbAXst mnmmnnaaaaaaaaaA212222111211线性规划问题的标准型式线性规划问题的标准型式目标函数目标函数约束条件约束条件nnxcxcxcz .max2211 nixbxaxaxabxaxaxabxaxaxastMimnmnmmnnnn,.,2,1,0.)(22112
10、222212111212111标准型式的其他表示标准型式的其他表示和式表示和式表示向量表示向量表示 njxmibxastMxczjinjjijnjjj,.,2,1,0),.,2,1(.)(max111 0.)(max11XbxPstMCXznjjj标准型式的矩阵表示标准型式的矩阵表示矩阵表示矩阵表示)7.1(0.max XbAXstCXzb为资源向量为资源向量C为价值向量为价值向量X为决策向量为决策向量A为参数矩阵为参数矩阵线性规划问题的向量说明线性规划问题的向量说明目标函数最小化转换成最大化目标函数最小化转换成最大化线性规划问题的标准化过程线性规划问题的标准化过程CXzzzCXz max,m
11、in即得令左端加入非负松弛变量 左端减去非负剩余变量 0,0,jjjjjjxxxxxx令无约束jjjxxx ,0 令约束方程为不等式转化为等式约束方程为不等式转化为等式决策变量非负性转化决策变量非负性转化线性规划的图解线性规划的图解max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20可行域可行域目标函数等值线目标函数等值线最优解最优解64-860 x1x2唯一解唯一解无穷多解无穷多解无界解无界解无可行解无可行解线性规划问题解的讨论线性规划问题解的讨论最优解最优解使目标函数达到最优的可行解。使目标函数达到最优的可行解。基基设设A是约束方程组的是约束方程组的mxn维系数矩阵
12、，维系数矩阵，其秩为其秩为m。B是是A的的mxm阶非奇异矩阵，则称阶非奇异矩阵，则称B是线性规划问题的一个基。是线性规划问题的一个基。线性规划问题解的概念线性规划问题解的概念)7.1(0.max XbAXstCXz标准型线性规划标准型线性规划可行解可行解满足约束条件满足约束条件(1.7)的解的解 ，称为该线，称为该线性规划的可行解。性规划的可行解。Tnxxxx),.,(21 mmmmmmmPPPaaaaaaaaaB,.,21212222111211 基向量基向量基变量基变量与基向量与基向量 相应的变量相应的变量 。非基变量非基变量基变量之外的变量。基变量之外的变量。对应于基对应于基B的基变量的
13、基变量记记 对应于基对应于基B的非基变量的非基变量 1P),.,2,1(mjPj jPjx),.,2,1(mj TmBxxxX,.,21 TnmNxxX,.,1 nmPPN,.,1 nE基可行解基可行解满足约束条件满足约束条件(1.7)的基解的基解。可行解可行解基解基解bXXNBNB ),(bAX 将将改写为改写为 001bBXXBNBNXbBX 从而从而0 NX令令可得唯一解可得唯一解可行基可行基对应于基对应于基可行解的基。可行解的基。基解基解对应于基对应于基B的方程的方程 的解的解bAX 0BXX基可行解基可行解2 线性规划问题的几何意义线性规划问题的几何意义2.1 2.1 基本概念基本概
14、念凸集凸集设设K是是n维欧氏空间的一个点集，维欧氏空间的一个点集，若任意两点若任意两点 的连线上的的连线上的一切点一切点则则称称K为凸集。为凸集。KXKX )2()1(,);10(,)1()2()1(KXX凸集凸集不是凸集不是凸集凸集凸集顶点顶点设设K是凸集，；若是凸集，；若X不能不能用不同的两点的线性用不同的两点的线性组合表示为组合表示为则称则称X为为K的一个顶点的一个顶点(或极点或极点)KX KXKX )2()1(,)10()1()2()1(XXX凸组合凸组合设设 是是n维欧氏维欧氏空间的空间的k个点。若存在个点。若存在 则称则称 的凸组合。的凸组合。),.,2,1()(kiXi nE k
15、iiikiiiiXXki1)(1,1);,.,2,1(10,使使),.,2,1()(kiXXi 为为凸组合集凸组合集设设),.,2,1()(kiXi 是是n维欧维欧 1),.,2,1(10,|11)(kiiikiiikiXXXD nE氏空间氏空间的的k个点。个点。),.,2,1()(kiXi 生成的凸组合集生成的凸组合集则称则称 D是由是由思考题思考题：2121|KxKxxKK 且 2121|KxKxxKK 或 2121|KxKxxKK 但 22112121,|KxKxxxxKK 22112121,|KxKxxxxKK 是否为凸集？是否为凸集？设设21,KK是是n维欧氏空间的两个凸集，问维欧氏
16、空间的两个凸集，问思考题思考题：凸组合集一定是凸集？凸组合集一定是凸集？凸集也一定是凸组合集？凸集也一定是凸组合集？凸组合集的顶点个数一定是有限的？凸组合集的顶点个数一定是有限的？凸集的顶点个数也一定是有限的？凸集的顶点个数也一定是有限的？凸集所包含的点的个数可否有限？凸集所包含的点的个数可否有限？2.2 2.2 基本定理基本定理定理定理1 1 若线性规划问题存在可行域，则其可若线性规划问题存在可行域，则其可bAXbandAXXXhaveWeDXDXD )2()1()2()1()2()1(,0,0,分析：分析：0,XbAXXD行域行域是凸集。是凸集。DXXHencebbbAXAXXXAXX )
17、2()1()2()1()2()1()2()1()1()1()1()1(0)1(,1,0 引理引理1 1 TnxxxX,.,21 由基解的定义，知由基解的定义，知X的非零分量所对应的系数的非零分量所对应的系数为基可行解的充分必要条件是为基可行解的充分必要条件是X X的正分量的正分量线性规划问题的可行解线性规划问题的可行解所对应的系数列向量是线性独立的所对应的系数列向量是线性独立的 。kxxx,.,21反之，若反之，若X的正分量的正分量所对应的向量所对应的向量kPPP,.,21线性独立，线性独立，;mk 则则,mk 若若mPPP,.,21则则线性规划问题的一个基；线性规划问题的一个基；,mk 若若
18、nkkPPP,.,21 则可从则可从中选取中选取m-k个向量，个向量，kPPP,.,21与与构成极大线性无关组。构成极大线性无关组。分析分析列向量是线性独立的；列向量是线性独立的；定理定理2 2 线性规划问题的基可行解线性规划问题的基可行解X X对应于可对应于可行域的顶点。行域的顶点。分析：分析：不妨可设可行解不妨可设可行解X的前的前k(k0，使得，使得0 iix DxxxXkk )0,.,0,.,(2211)1(DxxxXkk )0,.,0,.,(2211)2()2()1(2121XXX 若若X不是不是D的顶点，则它不是基可行解。的顶点，则它不是基可行解。设设X的前的前k个分量为正，故有个分
19、量为正，故有的相应分量也为零，因而有的相应分量也为零，因而有bPxbPxkiiikiii 1)2(1)1(及)1,0(,)2()1()2()1(XXDXDX使得使得)2()1()1(XXX 从而当从而当0 ix时，对应的时，对应的)2()1(,XX 01)2()1(kiiiiPxx引理引理2 2 若若K K是有界凸集，则是有界凸集，则K K上的任何一点上的任何一点 可表示为可表示为K K的顶点的凸组合。的顶点的凸组合。思考：思考：正正n边形区域是一凸集，且其上边形区域是一凸集，且其上的任意一点可表为的任意一点可表为K的至多三个顶点的至多三个顶点的凸组合。的凸组合。定理定理3 3 若可行域有界，
20、线性规划问题的目若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达标函数一定可以在其可行域的顶点上达到最优。到最优。分析：有界可行域，具有有限个顶点分析：有界可行域，具有有限个顶点),.,2,1()(kiXi 记记)(1)()(maxikimmCXCXX 则则CXCXDXDX max00若若事实上事实上 kiiikiiiXX11)(01,10,)(1)(1)(1)(0maxmkimikiiikiiiDXCXCXCXXCCXCX 几点说明：单点集是否为凸集？无界区域可否为凸集？单点集是否为凸集？无界区域可否为凸集？非空可行域是凸集；非空可行域是凸集；基可行解基可行解X X有界可行域
21、，目标函数的最优值可在该可行域有界可行域，目标函数的最优值可在该可行域的某一顶点达到，从而有某一基可行解的某一顶点达到，从而有某一基可行解X X使目使目标函数达到最优；标函数达到最优；可行域可行域D D的顶点；的顶点；nmA 基可行解，首先是基解，对于基可行解，首先是基解，对于所有可能的所有可能的mnCmnC 基的个数不超过基的个数不超过，所以基解的个数，所以基解的个数，mnC 更有基可行解的个数更有基可行解的个数。目标函数可在多个顶点处达到最优，则目标函数可在多个顶点处达到最优，则在这些顶点的凸组合上也达到最优，此在这些顶点的凸组合上也达到最优，此时该线性规划问题有无穷多个最优解；时该线性规
22、划问题有无穷多个最优解；若可行域无界若可行域无界可能无最优解可能无最优解可能有最优解，若有必定在某个顶点达到。可能有最优解，若有必定在某个顶点达到。线性规划可行域和最优解的几种情况线性规划可行域和最优解的几种情况1、可行域封闭、可行域封闭 唯一最优解唯一最优解2、可行域封闭、可行域封闭 多个最优解多个最优解3、可行域开放、可行域开放 唯一最优解唯一最优解4、可行域开放、可行域开放 多个最优解多个最优解5、可行域开放、可行域开放 目标函数无界目标函数无界6、无可行解、无可行解线性规划问题的直观求解线性规划问题的直观求解(枚举法枚举法)求矩阵求矩阵。，EndsiIfStepGoiiXXCXCXIf
23、StepGoiiCXCXIfCXandCXnComparisioStepiXXLetStepiiii,;,;,:maxmaxmaxmaxmax 21212010nmA),.,2,1(rkBk 的所有可能的基的所有可能的基kB 01bBXkBk对于每一基对于每一基，求解对应的基解，求解对应的基解),.,2,1(rkXkB 从基解从基解筛选出基可行解筛选出基可行解),.,2,1(0skXkB ),.,1,0(0skXk 或或由基可由基可 行解，行解，求解最求解最 优解。优解。3 3 单纯形法单纯形法单纯形法的基本思想单纯形法的基本思想1)1)线性规划问题标准化线性规划问题标准化2)2)从可行域中，
24、求解某一基可行解从可行域中，求解某一基可行解(一个顶点一个顶点)3)3)检验该基可行解是否达到最优，若达到最检验该基可行解是否达到最优，若达到最优，求解结束，否则，进入下一步优，求解结束，否则，进入下一步4)4)转换到另一个基可行解，并实施转换到另一个基可行解，并实施3)3)3.1 3.1 举例举例 2,1,012416482.32max212121jxxxxxtsxxzj标准化标准化)12.1(5,.,2,1,012416482.32max524132121 jxxxxxxxxtsxxzj 100400100400121,54321PPPPPA约束方程的系数矩阵约束方程的系数矩阵 10001
25、0001,543PPPB基基基变量基变量543,xxx)13.1(412416282514213 xxxxxxx TX12,16,8,0,0)0(基可行解基可行解0 z目标函数值目标函数值目标函数目标函数2132xxz 分析：目标函数表达式中存在正系数的非基变量，分析：目标函数表达式中存在正系数的非基变量，该目标函数值就有增加的可能该目标函数值就有增加的可能策略：将目标函数中正系数的非基变量，转变为策略：将目标函数中正系数的非基变量，转变为基变量；基变量；实施：选择正系数最大的非基变量，为新的基变实施：选择正系数最大的非基变量，为新的基变量，称为换入变量或进基变量；同时，将有一个量，称为换入变
26、量或进基变量；同时，将有一个基变量转换为非基变量，称为换出变量或出基变基变量转换为非基变量，称为换出变量或出基变量。量。具体地，选择具体地，选择2x为进基变量为进基变量)15.1(041201602825423 xxxxx1x仍为非基变量，仍为非基变量，3)4/12,2/8min(2 x选取选取原基变量原基变量05 x此时为出基变量，即非基变量。此时为出基变量，即非基变量。)16.1(4134162125214513 xxxxxxx(1.13)(1.13)变为变为此时此时 17.1432951xxz TX0,16,2,3,0)1(及另一基可行解及另一基可行解01 x此时此时取取)13.1(41
27、2416282514213 xxxxxxx有有目标函数表达式中存在正系数的非基变量目标函数表达式中存在正系数的非基变量1x2),4/16,2min(1 x选取选取原基变量原基变量03 x此时为出基变量，即非基变量。此时为出基变量，即非基变量。)18.1(41324821252534531 xxxxxxxx(1.16)(1.16)变为变为此时此时 19.14121353xxz TX0,8,0,3,2)2(及另一基可行解及另一基可行解选择选择1x为进基变量为进基变量)16.1(4134162125214513 xxxxxxx选择选择 为进基变量为进基变量5x目标函数表达式中存在正系数的非基变量目标
28、函数表达式中存在正系数的非基变量5x4)41/3,2/8,min(5 x选取选取原基变量原基变量04 x此时为出基变量，即非基变量。此时为出基变量，即非基变量。)20.1(81212212441443243541 xxxxxxxx(1.18)(1.18)变为变为此时此时 21.1125.05.11443xxz TX4,0,0,2,4)3(及另一新的基可行解及另一新的基可行解)18.1(41324821252534531 xxxxxxxx3.2 3.2 初始基可行解的确定初始基可行解的确定1.若线性规划问题若线性规划问题 0.maxXbAXstCXz从从A中可观察到中可观察到 mmEPPPB ,
29、.,21则取则取B为初始可行基，从而可得初始基可行解。为初始可行基，从而可得初始基可行解。00bX2.对于线性规划问题对于线性规划问题 0.maxXbAXstCXz经标准型化，在每个约束条件的的右端加上一个松弛变量经标准型化，在每个约束条件的的右端加上一个松弛变量 NEXXX约束方程约束方程其中其中 0XbXNEmnmm从而可得初始基可行解从而可得初始基可行解0 NX TmExxxX,.,21 TnmNxxX,.,1 23.1NENXbX 得得取取 00bXjjPx,重新编号，可得重新编号，可得经整理，对经整理，对3.对于线性规划问题对于线性规划问题 0),(.maxXbAXstCXz经标准型
30、化，若不存在单位矩阵，则采用经标准型化，若不存在单位矩阵，则采用人造基方法。即对不等式约束条件减去一人造基方法。即对不等式约束条件减去一个非负的剩余变量后，再加上一个非负的个非负的剩余变量后，再加上一个非负的人工变量，此时，总能得到一个单位矩阵。人工变量，此时，总能得到一个单位矩阵。3.3 3.3 最优性检验与解的判别最优性检验与解的判别线性规划问题的求解结果可能出现线性规划问题的求解结果可能出现唯一最优解；唯一最优解；无穷多个最优解；无穷多个最优解；无界解；无界解；无可行解。无可行解。TmExxxX,.,21 TnmNxxX,.,1 经过迭代经过迭代(1.23)其中其中 Tmbbbb21,.
31、,1,11,1nmmmnmaaaaN将将(1.24)代入目标函数代入目标函数 ,NENENNEENENEXNCCbCXCXCXXCCCXz mEcccC,.,21 nmNccC,.,1 其中其中解的判别准则的建立解的判别准则的建立 23.1NENXbX 24.1NEXNbX 将变成将变成 miiiEbcbCz10 nmjPCaczzzzNCzjEmiijijnmmEN,.,.,1121 记记 nnmmNNnmNzczczC ,.,.,111 于是于是)27.1(100 nmjjjNNxzXzz 称称),.,1(nmjj 为检验数。为检验数。miijijjacc1 线性规划问题的解的判别准则线性
32、规划问题的解的判别准则最优解的判别定理最优解的判别定理：若：若 TmbbbbX0,.,0,.,0210 为对应于基为对应于基B的一个基可行解，有的一个基可行解，有,0,.,1,0 jNnmj 都有即对于一切则则 0X为最优解。为最优解。无穷多最优解的判别定理无穷多最优解的判别定理：若：若 TmbbbbX0,.,0,.,0210 为对应于基为对应于基B的一个基可行解，有的一个基可行解，有njmnmjjjN 01,0,0,.,1,00 又有某都有即对于一切则该线性规划问题有无穷多最优解。则该线性规划问题有无穷多最优解。分析：分析：选择选择0jx为进基变量，可得一新的为进基变量，可得一新的基可行解基
33、可行解 1X此时此时),1(0jjnjmxj 仍为仍为非基变量，非基变量，而而00 j 故对应于故对应于 1X的目标的目标函数值函数值0zz )27.1(100 nmjjjNNxzXzz 构造构造 1X miabxijii,.,2,1,0001 011;,.,10,0jjnmjxxjj TmbbbbX0,.,0,.,0210 都有都有njmj 01,00 则该线性规划问题具有无界解则该线性规划问题具有无界解(或无最优解或无最优解)。且对于且对于mi,.,2,1 为一基可行解，有某一为一基可行解，有某一,00,jia无界解的判别定理无界解的判别定理：若：若 个分量第010100000,.,0,1
34、,0,.,0,.,jeAaaXXXXmjjTmjj 01000000,bAAbeNAEbeANEbXAXAXAjjmjjmmjjm 由此，知由此，知 1X为可行为可行解解代入目标函数代入目标函数 01CXCXCXz 个列向量的第表示单位矩阵kEemnk 个列向量的第表示矩阵00jAAj miijijjacc1000 00jz 3.4 3.4 基变换基变换为了换基，应先确定进基变量，再确定为了换基，应先确定进基变量，再确定出基变量。出基变量。0X判别无界时，需找一个新的基可行解；判别无界时，需找一个新的基可行解；即从原可行基中换出一个列向量，得到即从原可行基中换出一个列向量，得到一个新的基可行基
35、，称为基变换。一个新的基可行基，称为基变换。不是最优解且不能不是最优解且不能若初始基可行解若初始基可行解进基变量确定进基变量确定考察考察)27.1(10 nmjjjxzz 选取选取 kjnjm 0max1对应的对应的kx为进基变量为进基变量出基变量确定出基变量确定记记 mPPPB,.,21 是一个基是一个基 TmxxxX0,.,0,.,002010 其对应的基可行解为其对应的基可行解为其它向量其它向量nmmPPP,.,21 可由可由线性表示线性表示mPPP,.,21而而为进基变量为进基变量)1(nkmxk 且且 bPxmiii 10(1.28)则有不全为的数则有不全为的数使得使得 miki,.
36、,2,1,miikikPP1,(1.29)由由(1.28)和和(1.29)0 为确保为确保 mixkii,.,2,10,0 取取 kllkikiimixx,0,010min 这时这时为出基变量，为出基变量，lx 0,.,.,0,.,0,.,0,00,1,0011kllkmkllmkkllxxxxxX 有有 bPPxkmiikii 1,0(1.30)又使某一又使某一 mixkii 0,01000 第第l个分量个分量第第k个分量个分量并得到新的基可行解并得到新的基可行解 kiandnimorlikixlimixxxkllkikllii1,0,1,0,001 ljmjPj ;,.,2,1kP和和这这
37、m个向量是线性独立的个向量是线性独立的.limiiikPP1(1.31)又因又因 miikikPP1,(1.32)0,1,lkllimiiikiPP (1.32)(1.31)否则否则3.5 3.5 迭代迭代考虑基考虑基 mmEPPPB ,.,21 TmbbbX0,.,0,.,210 其对应的基可行解为其对应的基可行解为取相应的取相应的lklikikimiabaab 0min1 为出基变量为出基变量)1(mlxl 为进基变量为进基变量)1(nkmxk 如如 )(,1)(1|,|,|,|bNEbNEbNEbAirowlrowalimilrowaiklk 新基新基 mmlklEPPPPPB ,.,.
38、1111基变量为基变量为mlklxxxxx,.,.111 基可行解为基可行解为 0,.,0,.,0,.1111kmllbbbbbX )()(liablibaabblklllkikii )()(liaaliaaaaalkljiklkljijij4 4 单纯型法的计算步骤单纯型法的计算步骤对于线性规划问题对于线性规划问题 0.maxXbAXstCXz4.1 单纯型表单纯型表 011221111,2211,221111,11nnmmmmmnmnmmmmnnmmnnmmxcxcxcxcxczbxaxaxbxaxaxbxaxax约束方程与目标函数构成约束方程与目标函数构成m+1个方程的方程组个方程的方程
39、组 01100001000010211211,21,211,1121mnmmmnmmnmnmnmmbbbcccccaaaaaabxxxxxz miiimminiinmimiimmnmmnmnmnmmbcbbbaccaccaaaaaabxxxxxz1211,11,11,21,211,11210001100001000010mccc21mxxx21mbbb210011001,1,21,1 mmmmaaamnnnaaa21m 21z miiibc100 mimiimacc11,1 miininacc1BXBCb1xmx1 mxnx1cmc1 mcncjci 单纯型表单纯型表4.2 4.2 单纯形法的
40、计算步骤单纯形法的计算步骤Step 0 Step 0 找出初始可行基，确定初始基可行解，找出初始可行基，确定初始基可行解，建立初始的单纯形表；建立初始的单纯形表；,1 miijijjacc Step 1 Step 1 计算各非基变量计算各非基变量jx的检验数的检验数若若;,1,0nmjj 则已得到最优解，停止计算。否则转则已得到最优解，停止计算。否则转入入Step 2 Step 2。Step 2 Step 2 在在nmjj,1,0 k 中，若有某中，若有某个个,0 kP对应的对应的的系数列向量的系数列向量kx则此问题的解无界，停止计算。否则，转则此问题的解无界，停止计算。否则，转入入Step
41、3 Step 3。Step 3 Step 3 根据根据 ,0max1kjnjm ,kx确定进基变量确定进基变量按按 规则计算规则计算lklikikimiabaab 0min1 确定出基变量确定出基变量,lx转入转入Step 4 Step 4。Step 4 Step 4 以以lkakx为主元素进行迭代，把为主元素进行迭代，把对应的列向量对应的列向量 mklkkkaaaP1BX将将列中的列中的lxkx换为换为得到新的单纯型表，重复得到新的单纯型表，重复Step1-4Step1-4，直，直至终止。至终止。010第第行行l用单纯形法求解线用单纯形法求解线性规划问题（性规划问题（1）0,52426155
42、.2max212121221xxxxxxxstxxz单纯形法求解举例单纯形法求解举例标准化标准化 0,52426155.2max543215214213221xxxxxxxxxxxxxstxxz000543xxx5241516012501000110054 z 02 1000BXBCb1x2x3x5x4x21 000jci 单纯型表（单纯型表（1-11-1）初等行变换初等行变换020513xxx14150106462561610 00110023123z 8 031031 0BXBCb1x2x3x5x4x21 000jci 单纯型表（单纯型表（1-21-2）初等行变换初等行变换单纯型表（单纯型
43、表（1-31-3）120213xxx2327215010100414145 0012321215 z 217 0 0041 21 BXBCb1x2x3x5x4x21 000jc 217*2152327*,00 zXT 0,22426155.2max212121221xxxxxxxstxxz标准化（简化）标准化（简化）0,21233.2max543215214213221xxxxxxxxxxxxxstxxz线性规划问题（线性规划问题（2）添加添加人工人工变量变量 0,21233.2max65432165214213221xxxxxxxxxxxxxxxstxxz000643xxx212313011
44、1010001100 24 z 02 1000BXBCb1x2x3x5x4x21000jci 06x1000单纯型表（单纯型表（2-12-1）初等行变换初等行变换200143xxx263100121 010001130 2z 4 01 002BXBCb1x2x3x5x4x21000jci 06x130 2 单纯型表（单纯型表（2-22-2）初等行变换初等行变换200153xxx42310031321 31310001010123 z 8 031032 0BXBCb1x2x3x5x4x21000jci 06x010 0单纯型表（单纯型表（2-32-3）初等行变换初等行变换单纯型表（单纯型表（2-
45、42-4）201152xxx3431000013131031321 010z 9 0031 32 0BXBCb1x2x3x5x4x21000jc06x010 0 9,0,5,0,0,3,3*zXT 0,12324112.3min32131321321321xxxxxxxxxxxstxxxz标准化标准化 0,12324112.3max543213153214321321xxxxxxxxxxxxxxxstxxxz线性规划问题（线性规划问题（3）0,12324112.3max7654321731653214321321xxxxxxxxxxxxxxxxxxxstxxxz添加添加人工人工变量变量添加人工
46、变量添加人工变量000764xxx1311241 012 001121010 11z 031 1 00BXBCb1x2x3x5x4x31 1 00jci 06x010007x1000单纯型表（单纯型表（3-13-1）003761xxx234711001472 241361010 z 00 53 3 0BXBCb1x2x3x5x4x31 1 00jc06x010007x1000单纯型表（单纯型表（3-23-2）052 02 P人工变人工变量量无界？无界？0,12324112.3min32131321321321xxxxxxxxxxxstxxxz1321xx 0,11023.1min2122121
47、xxxxxstxxz 9103102322121 xxxxx321 xx2min2 z分析分析 0,12324112.3max7654321731653214321321xxxxxxxxxxxxxxxxxxxstxxxz添加添加人工人工变量变量添加人工变量添加人工变量26Mx 7Mx 在线性规划在线性规划 问题的约束条件中加入人工变量后问题的约束条件中加入人工变量后,要求人工变量对目标函数取值不受影响，要求人工变量对目标函数取值不受影响，为此假为此假定人工变量在目标函数中的系数为定人工变量在目标函数中的系数为-M(M-M(M为任意为任意大的正数大的正数)，这样目标函数要实现最大化时，必这样目标
48、函数要实现最大化时，必需把人工变量从基变量换出。否则目标函数不可需把人工变量从基变量换出。否则目标函数不可能实现最大化。能实现最大化。大大MM法法MM 0764xxx1311241 012 001121010 12311z 0M63 M 1M31 0M BXBCb1x2x3x5x4x31 1 00jci M 6x0100M 7x1000单纯型表（单纯型表（3 3-1-1）初等行变换初等行变换10 M364xxx1110203 012 001100010 1z 01M 100M BXBCb1x2x3x5x4x31 1 00jci M 6x0100M 7x100M31 单纯型表（单纯型表（3 3-
49、2-2）初等行变换初等行变换110 324xxx1112203 010001100010 4z 010001 BXBCb1x2x3x5x4x31 1 00jci M 6x010M 1M 7x100M 1单纯型表（单纯型表（3 3-3-3）初等行变换初等行变换113 321xxx9140010103203110034132 z 2 00031 31 BXBCb1x2x3x5x4x31 1 00jcM 6x34132M 31M 7x37235 M 32单纯型表（单纯型表（3 3-4-4）2,0,0,0,0,9,1,4*zXT第一阶段：不考虑原问题是否存在基可行解；第一阶段：不考虑原问题是否存在基可
50、行解；给原线性规划问题加入人工变量，并构造仅含给原线性规划问题加入人工变量，并构造仅含人工变量和的目标函数并要求实现最小化。人工变量和的目标函数并要求实现最小化。两阶段法两阶段法1mnnnxxx .min21 mnixbxxaxabxxaxabxxaxastimmnnmnmnnnnnn,.,2,1,0.11222121111111否则原问题无可行解，停止计算。否则原问题无可行解，停止计算。0 若若原问题存在基可行解，进入第二阶段；原问题存在基可行解，进入第二阶段；第二阶段：将第一阶段计算得到的最终表，除第二阶段：将第一阶段计算得到的最终表，除去人工变量。将目标函数行的系数，换成原问去人工变量。
