运筹学Chapter线性规划及其单纯形法.pptx

《运筹学Chapter线性规划及其单纯形法.pptx》由会员分享，可在线阅读，更多相关《运筹学Chapter线性规划及其单纯形法.pptx（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/3/271一、线性规划问题的数学模型一、线性规划问题的数学模型在现有各项资源条件的限制下，如何确定方案，在现有各项资源条件的限制下，如何确定方案，使预期目标达到最优，这就是规划方法。使预期目标达到最优，这就是规划方法。例例1 1 美佳公司计划制造美佳公司计划制造、两种家电产品。已两种家电产品。已知各制造一件时分别占用的设备知各制造一件时分别占用的设备A A、B B的台时、调试时的台时、调试时间、调试工序每天可用于这两种家电的能力、各售出间、调试工序每天可用于这两种家电的能力、各售出一件时的获利情况，如表一件时的获利情况，如表1-11-1所示。问该公司应制造所示。问该公司应制造两种家电

2、产品各多少件，使获取的利润为最大？两种家电产品各多少件，使获取的利润为最大？1-1 1-1 线性规划问题及其数学模线性规划问题及其数学模型型返回第一章目录第1页/共61页2023/3/2721-1 线性规划问题及其数学模型用数学语言来描述这个问题。假设美佳公司每天制造、两种家电产品的数量分别是x1和x2件。max约束条件目标函数Z2x1x25x2156x12x224x1x25x1，x20这就是例1的数学模型第2页/共61页2023/3/273运筹学基础及应用运筹学基础及应用运筹学基础及应用运筹学基础及应用第一章例第一章例第一章例第一章例2 2【例例2 2】某企业计划生产某企业计划生产I I、两

3、种产品。这两种产品都要分别在两种产品。这两种产品都要分别在A A、B B、C C、D D四种不同设备上加工。按工艺资料规定，生产每件产品四种不同设备上加工。按工艺资料规定，生产每件产品I I需占用各设备分别为需占用各设备分别为2 2、1 1、4 4、0 0小时，生产每件产品小时，生产每件产品B B，需占用各设备分别为，需占用各设备分别为2 2、2 2、0 0、4 4小时。已知设备计划小时。已知设备计划期内用于生产这两种产品的能力分别为期内用于生产这两种产品的能力分别为1212、8 8、1616、1212小时，又知每生产一件产品小时，又知每生产一件产品I I企业能获得企业能获得2 2元利润、每生

4、产一件产品元利润、每生产一件产品企业能获得企业能获得3 3元利润，问该企业应安排生产元利润，问该企业应安排生产两种产品各多少件，使总的利润收入为最大？两种产品各多少件，使总的利润收入为最大？第3页/共61页2023/3/274 产品产品资源资源产品产品产品产品生产能力生产能力（h）设备设备A（h）2212设备设备B（h）128设备设备C（h）4016设备设备D（h）0412利润（元利润（元/件）件）23假设：假设：计划期内生产计划期内生产 产品产品x1件，件，产品产品x2件。件。第4页/共61页2023/3/275例例2 2捷运公司拟在下一年度的捷运公司拟在下一年度的1 14 4月份的月份的4

5、 4个月内租用仓库堆放物资。已知各月份个月内租用仓库堆放物资。已知各月份所需仓库面积数。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字如所需仓库面积数。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字如表表1-21-2所示。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。所示。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此，该厂可根据需要，在任何一个月初办理租借合同。每次办理可签一份，也可因此，该厂可根据需要，在任何一个月初办理租借合同。每次办理可签一份，也可签若干份租用面积和租借期限不同的合同，试确定该公司签定租借合同的最优决策，签若干份租用面

6、积和租借期限不同的合同，试确定该公司签定租借合同的最优决策，目的是使所付租借费用最小。目的是使所付租借费用最小。第5页/共61页2023/3/276假设用xij表示捷运公司第i（i1，2，4）个月月初签订租借期为j（j1，2，4）个月的仓库面积数(单位为100m2）。则min z2800(x11+x21+x31+x41)+4500(x12+x22+x32)+6000(x13+x23)+7300 x14x11+x12+x13+x1415x12+x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12xij 0 (i1

7、，2，4；j1，2，4）租借期为一个月的仓库面积租借期为二个月的仓库面积租借期为三个月的仓库面积租借期为四个月的仓库面积一月份拥有的租借面积二月份拥有的租借面积三月份拥有的租借面积四月份拥有的租借面积一月份仓库需求面积约束二月份仓库需求面积约束三月份仓库需求面积约束四月份仓库需求面积约束非负约束第6页/共61页2023/3/277组成线性规划模型的三个要素组成线性规划模型的三个要素max Z2x1x25x2156x12x224x1x25x1，x20目标函数：约束条件（1 1 1 1）变量（决策变量）变量（决策变量）变量（决策变量）变量（决策变量）:它是规划中要确定的未知量，是用数量方它是规划中

8、要确定的未知量，是用数量方它是规划中要确定的未知量，是用数量方它是规划中要确定的未知量，是用数量方式来表示的方案或措施，可由决策者决定式来表示的方案或措施，可由决策者决定式来表示的方案或措施，可由决策者决定式来表示的方案或措施，可由决策者决定和控制。和控制。和控制。和控制。（2 2 2 2）目标函数：）目标函数：）目标函数：）目标函数：它是决策变量的函数，是决策者在一定它是决策变量的函数，是决策者在一定它是决策变量的函数，是决策者在一定它是决策变量的函数，是决策者在一定的限制条件下希望得到的结果。的限制条件下希望得到的结果。的限制条件下希望得到的结果。的限制条件下希望得到的结果。（3 3 3

9、3）约束条件：）约束条件：）约束条件：）约束条件：指决策变量取值时受到的各种资源条件的指决策变量取值时受到的各种资源条件的指决策变量取值时受到的各种资源条件的指决策变量取值时受到的各种资源条件的限制，通常用等式或不等式来表达。限制，通常用等式或不等式来表达。限制，通常用等式或不等式来表达。限制，通常用等式或不等式来表达。其中，其中，x xij ij00叫做非负约束。叫做非负约束。由由由由于于于于目目目目标标标标函函函函数数数数是是是是决决决决策策策策变变变变量量量量的的的的线线线线性性性性函函函函数数数数，约约约约束束束束条条条条件件件件是是是是含含含含决决决决策策策策变变变变量量量量的的的的

10、线线线线性性性性等等等等式式式式或或或或不不不不等等等等式式式式，所所所所以以以以此此此此类类类类模模模模型型型型称称称称为为为为线线线线性性性性规规规规划划划划的的的的数学模型。数学模型。数学模型。数学模型。实际问题中，线性的含义有二：实际问题中，线性的含义有二：实际问题中，线性的含义有二：实际问题中，线性的含义有二：一一一一是是是是严严严严格格格格的的的的比比比比例例例例性性性性，即即即即某某某某种种种种产产产产品品品品对对对对资资资资源源源源的的的的消消消消耗耗耗耗量量量量和和和和可可可可获获获获得得得得的的的的利利利利润润润润与与与与其其其其生产数量严格成比例。生产数量严格成比例。生产

11、数量严格成比例。生产数量严格成比例。二二二二是是是是可可可可迭迭迭迭加加加加性性性性。即即即即生生生生产产产产多多多多种种种种产产产产品品品品对对对对某某某某种种种种资资资资源源源源的的的的消消消消耗耗耗耗量量量量等等等等于于于于各各各各产产产产品品品品对对对对该该该该项资源的消耗量之和。项资源的消耗量之和。项资源的消耗量之和。项资源的消耗量之和。第7页/共61页2023/3/278模型中，cj称为价值系数。bi是资源限制量。aij称为技术系数或工艺系数。二、线性规划模型的一般形式二、线性规划模型的一般形式假设线性规划问题中含有假设线性规划问题中含有假设线性规划问题中含有假设线性规划问题中含有

12、n n个变量，个变量，个变量，个变量，mm个约束方程。则个约束方程。则个约束方程。则个约束方程。则线性规划模型的一般形式为：线性规划模型的一般形式为：线性规划模型的一般形式为：线性规划模型的一般形式为：max(或min)zc1x1+c2x2+cnxna11x1+a12x2+a1nxn（或，）b1a21x1+a22x2+a2nxn（或，）b2am1x1+am2x2+amnxn（或，）bmx1,x2,xn0简写为：向量形式：矩阵形式：第8页/共61页2023/3/279三、线性规划问题的标准形式三、线性规划问题的标准形式若得出的线性规划模型不是标准形式，应通过下列方法将其化为标准形式：1.目标函数

13、为求极小值的情况，即本教材规定，线性规划模型的标准形式为：本教材规定，线性规划模型的标准形式为：其特点是：(1)目标函数求极大；(2)约束条件取等式；(3)变量非负；(4)约束条件右边常数为正值。化为标准形式的方法是，令zz，则第9页/共61页2023/3/2710三、线性规划问题的标准形式3.3.约束条件为不等式的情况约束条件为不等式的情况。当约束条件为“”时，在约束符号的左边加上一个松弛变量，将“”变为“”；如6x1+2x224,化为标准形式为6x1+2x2x324，x30。当约束条件为“”时，在约束符号的左边减去一个剩余变量，将“”变为“”；如10 x1+12x218,化为标准形式为10

14、 x1+12x2x318，x30。4.4.对变量无约束的情况对变量无约束的情况。如x在（，）之间变化，即x的取值可正可负时，令xxx代入线性规划模型即可，其中x0，x0。5.5.对于对于x 00的情况的情况，令xx，显然x0。2.2.若若约约束束条条件件右右边边常常数数项项bim），其秩为其秩为m，B是矩阵是矩阵A中的一个中的一个mm阶的满秩子矩阵，称阶的满秩子矩阵，称B是线性规划问题的一个基是线性规划问题的一个基。系数系数系数系数矩阵矩阵矩阵矩阵基基基基：图解法返回第一章目录第15页/共61页2023/3/2716一、线性规划问题的解的概念一、线性规划问题的解的概念基B中的每一个列向量Pj(

15、j=1，2，m）称为基向量基向量基向量基向量，与基向量Pj对应的变量xj称为基变量基变量基变量基变量；除基变量以外的变量称为非基变量非基变量非基变量非基变量。基解基解基解基解：在约束方程中，将非基变量移到等式右边：P1P2Pm令非基变量xm+1xm+2xn0，得可解得可解得可解得可解得mm个基变量的唯一解为个基变量的唯一解为个基变量的唯一解为个基变量的唯一解为：X XB B（x x1 1，x x2 2，x xmm）T T。加上非基变量取加上非基变量取加上非基变量取加上非基变量取0 0的值，得的值，得的值，得的值，得X X（x x1 1,x,x2 2,，x xmm,0,0,0,0）T T。这就是

16、线性规划问题的基解这就是线性规划问题的基解这就是线性规划问题的基解这就是线性规划问题的基解。第16页/共61页2023/3/2717基可行解基可行解：满足非负约束的解称为基可行解。可行基可行基：对应于基可行解的基称为可行基。例：找出下述线性规划问题的全部基解，指出其中的基找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解可行解，并确定最优解。max z2x1+3x2+x3x1+x35x1+2x2+x410 x2+x54x150一、线性规划问题的解的概念一、线性规划问题的解的概念解解解解：用穷举法找出该线性规划问题的全部基解。打者为基可行解。最优解为：x12，x24，x33，x40

17、，x50与最优解对应的目标函数值为z19第17页/共61页2023/3/2718凸集凸集设设C C为为n n维欧氏空间的一个点集。若对于维欧氏空间的一个点集。若对于C C中任意两点中任意两点X X1 1，X X2 2满足满足X X1 1+(1-)X+(1-)X2 2C (0C (01)1)则称则称C C为凸集为凸集。也就是说，如果也就是说，如果X X1 1CC，X X2 2CC，则线段则线段X X1 1X X2 2上的所有点上的所有点X X也属于也属于C C。即即：X XXX1 1+(1-)X+(1-)X2 2C (0C (01)1)称称C C为凸集为凸集。从直观上看，凸集没有凹入部分，其内部

18、没有孔洞。二、凸集和顶点二、凸集和顶点凸集凸集凸集凸集凸集凸集第18页/共61页2023/3/2719不是凸集不是凸集不是凸集不是凸集二、凸集和顶点二、凸集和顶点顶点顶点顶点顶点设设设设K K K K为凸集为凸集为凸集为凸集，XCXCXCXC，若若若若X X X X不能用不能用不能用不能用C C C C中不同的两点中不同的两点中不同的两点中不同的两点X X X X1 1 1 1，X X X X2 2 2 2的线性组合表示为的线性组合表示为的线性组合表示为的线性组合表示为X X X XXXXX1 1 1 1+(1-)X+(1-)X+(1-)X+(1-)X2 2 2 2 C (0 C (0 C (

19、0 C (01)1)1)1)则称则称则称则称X X X X为为为为C C C C的一个顶点（或极点）。即的一个顶点（或极点）。即的一个顶点（或极点）。即的一个顶点（或极点）。即X X X X不能成为不能成为不能成为不能成为C C C C中任何线段的内点。中任何线段的内点。中任何线段的内点。中任何线段的内点。第19页/共61页2023/3/2720三、三、线性规划的基本定理线性规划的基本定理定理定理定理定理1 1 1 1：若线性规划问题存在可行解，则问题的可行域是凸集。：若线性规划问题存在可行解，则问题的可行域是凸集。：若线性规划问题存在可行解，则问题的可行域是凸集。：若线性规划问题存在可行解，

20、则问题的可行域是凸集。引理引理引理引理 线性规划的可行解线性规划的可行解线性规划的可行解线性规划的可行解X=(=(=(=(x1 1 1 1,x2 2 2 2,xn)为基可行解的充要条件是为基可行解的充要条件是为基可行解的充要条件是为基可行解的充要条件是X 的正分量所对应的系数列向量线性独立。的正分量所对应的系数列向量线性独立。的正分量所对应的系数列向量线性独立。的正分量所对应的系数列向量线性独立。定理定理定理定理2 2 2 2：线性规划的基本可行解对应于其可行域的顶点。：线性规划的基本可行解对应于其可行域的顶点。：线性规划的基本可行解对应于其可行域的顶点。：线性规划的基本可行解对应于其可行域的

21、顶点。定理定理定理定理 3 3 3 3 若线性规划问题有最优解，一定存在一个基可行解是最优解。若线性规划问题有最优解，一定存在一个基可行解是最优解。若线性规划问题有最优解，一定存在一个基可行解是最优解。若线性规划问题有最优解，一定存在一个基可行解是最优解。单纯形法迭代原理第20页/共61页2023/3/2721定理定理1 1 1 1：若线性规划问题存在可行解，则问题的可行域是凸：若线性规划问题存在可行解，则问题的可行域是凸集。集。证明证明 若满足线性规划约束条件若满足线性规划约束条件线性规划的基本定理的证明线性规划的基本定理的证明Pjxjbj=1n的所有点组成的的所有点组成的集合集合C C C

22、 C是凸集是凸集,则则C C C C内任意两点内任意两点X X X X1 1 1 1，X X X X2 2 2 2连线上的点也必然在连线上的点也必然在C C C C内。内。设设X X X X1 1 1 1=(x=(x=(x=(x11111111,x,x,x,x12121212,，x x x x1n1n1n1n)T T T T,X,X,X,X2 2 2 2=(x=(x=(x=(x21212121,x,x,x,x22222222,，x x x x2n2n2n2n)T T T T为为C C C C内任意两点，即内任意两点，即X X X X1 1 1 1CCCC，X X X X2 2 2 2CCCC，

23、将将X X X X1 1 1 1 ，X X X X2 2 2 2代入约束条件，有代入约束条件，有Pjx1jbj=1nPjx2jbj=1n；（1-9）X X1 1，X X2 2连线上任意一点可表示为：连线上任意一点可表示为：Xa aX1（1a a）X2 （00a1a1)(1-10)(1-10)将（1-91-9）代入（1-101-10）得：所以 X X1 1CC，X X2 2CC。由于集合中任意两点连线上的点均在集合内，所以C C为凸集。第21页/共61页2023/3/2722引理引理引理引理 线性规划的可行解线性规划的可行解线性规划的可行解线性规划的可行解X X =(=(=(=(x x1 1,x

24、 x2 2,x xn n)为基可为基可为基可为基可行解的充要条件是行解的充要条件是行解的充要条件是行解的充要条件是X X 的正分量所对应的系数列向量的正分量所对应的系数列向量的正分量所对应的系数列向量的正分量所对应的系数列向量线性独立。线性独立。线性独立。线性独立。证：（证：（证：（证：（1 1 1 1）必要性。由基可行解的定义得证。）必要性。由基可行解的定义得证。）必要性。由基可行解的定义得证。）必要性。由基可行解的定义得证。（2 2 2 2）充充充充分分分分性性性性。若若若若向向向向量量量量P P1 1,P,P2 2,P,Pk k线线线线性性性性独独独独立立立立，则则则则必必必必有有有有k

25、mkm时时时时；当当当当k=k=mm时时时时，它它它它们们们们恰恰恰恰好好好好构构构构成成成成一一一一个个个个基基基基，从从从从而而而而X=X=(x(x1 1,x,x2 2,x xmm,0,0,0),0),0),0)T T T T为相应的基可行解。为相应的基可行解。为相应的基可行解。为相应的基可行解。当当当当k k mm时时时时，则则则则一一一一定定定定可可可可以以以以从从从从其其其其余余余余列列列列向向向向量量量量中中中中找找找找出出出出(mm-k k)个个个个与与与与P P1 1,P,P2 2,P,Pk k构构构构成成成成一一一一个个个个基基基基，其其其其对对对对应应应应的的的的解解解解恰

26、恰恰恰为为为为X X，所所所所以根据定义它是基可行解。以根据定义它是基可行解。以根据定义它是基可行解。以根据定义它是基可行解。返回第22页/共61页2023/3/2723定定理理2 2：线线性性规规划划的的基基本本可可行行解解对对应应于于其其可行域的顶点。可行域的顶点。证:本定理需要证明:X:X是可行域顶点X X是基可行解。用反证法证明：X X不是可行域的顶点X X不是基可行解。（1 1）X X不是基可行解X X不是可行域的顶点。假设X X的前m m个分量为正，有第23页/共61页2023/3/2724由由引引理理知知P P P P1 1 1 1,P,P,P,P2 2 2 2,P,P,P,Pm

27、 m m m线线性性相相关关，即即存存在在一一组组不全为零的数不全为零的数i i i i(i=1,2,(i=1,2,(i=1,2,(i=1,2,，m),m),m),m),使得使得d d d d1 1 1 1P P1 1+d d d d2 2 2 2P P2 2+d d d dm m m mP Pmm=0=0(1.12)(1.12)将（将（1.121.12）乘以一个不全为零的数）乘以一个不全为零的数 得得mdmdmdmd1 1 1 1P P1 1+mdmdmdmd2 2 2 2P P2 2+mdmdmdmdm m m mP Pmm=0=0(1.13)(1.13)(1.13)+(1.11)(1.1

28、3)+(1.11)得：得：(x(x1 1mdmdmdmd1 1 1 1)P)P1 1+(x+(x2 2mdmdmdmd2 2 2 2)P)P2 2+(x+(xmmmdmdmdmdmm)P)Pmm=b=b(1.11)-(1.13)(1.11)-(1.13)得：得：(x(x1 1mdmdmdmd1 1 1 1)P)P1 1+(x+(x2 2mdmdmdmd2 2 2 2)P)P2 2+(x+(xmmmdmdmdmdmm)P)Pmm=b=b令令X X(1)(1)=(x=(x1 1mdmdmdmd1 1),(x),(x2 2mdmdmdmd2 2 2 2),),),),(x,(xmmmdmdmdmdm

29、m),0,0),0,0X X(2)(2)=(x=(x1 1mdmdmdmd1 1),(x),(x2 2mdmdmdmd2 2 2 2),),),),(x,(xmmmdmdmdmdmm),0,0),0,0又又m m m m可以这样来选择，使得对所有可以这样来选择，使得对所有i=1,2,mi=1,2,m有有 x xi i mdmdmdmdi i00即即X X不是可行域的顶不是可行域的顶点。点。引理第24页/共61页2023/3/2725（2 2 2 2）X X不是可行域的顶点不是可行域的顶点不是可行域的顶点不是可行域的顶点X X不是基本可行不是基本可行不是基本可行不是基本可行解。解。解。解。设设X

30、 X X X(x(x1 1,x,x2 2,0,0),0,0)T T不是可行域的顶点，因而可以找到可行域内另外两个不不是可行域的顶点，因而可以找到可行域内另外两个不同点同点Y Y和和Z Z，有，有X=X=a a a aY+(1-Y+(1-a a a a)Z (0)Z (0a a a a1),1),或可写为：或可写为：x xj j=a a a ay+(1-y+(1-a a a a)z)zj j;(0;(0a a a a1;j=1,2,n)0,1-0,1-a a a a0,0,故当故当x xj j=0=0时，必有时，必有y yi i=z=zi i=0=0(1.14)-(1.15)(1.14)-(1.

31、15)得：得：因因(y(yj jz zj j)不全为零，故不全为零，故P P1 1,P,P2 2,P,Pr r线性相关，即线性相关，即X X不是基可不是基可行解。行解。第25页/共61页2023/3/2726定定理理 3 3 若若线线性性规规划划问问题题有有最最优优解解，一一定定存在一个基可行解是最优解。存在一个基可行解是最优解。证：设证：设X X(0)(0)=(x=(x1 10 0,x,x2 20 0,x,xn n0 0)是线性规划的一个最是线性规划的一个最优解，优解，若若若若X X(0)(0)不不不不是是是是基基基基可可可可行行行行解解解解，由由由由定定定定理理理理2 2知知知知X X(0

32、)(0)不不不不是是是是顶顶顶顶点点点点，一一一一定定定定能能能能在在在在可可可可行行行行域域域域内内内内找找找找到到到到通通通通过过过过X X(0)(0)的的的的直直直直线线线线上上上上的的的的另另另另外外外外两两两两个个个个点点点点（X X(0)(0)+mdmdmdmd)0)0和和和和（X X(0)(0)mdmdmdmd）0 0 0 0。将这两个点代入目标函数有。将这两个点代入目标函数有。将这两个点代入目标函数有。将这两个点代入目标函数有C(XC(X(0)(0)md)md)md)md)CXCX(0)(0)C Cmdmdmdmd;C(XC(X(0)(0)md)md)md)md)CXCX(0)

33、(0)C Cmdmdmdmd因因因因CXCX(0)(0)为目标函数的最大值，故有为目标函数的最大值，故有为目标函数的最大值，故有为目标函数的最大值，故有CXCX(0)(0)CX CX(0)(0)C Cmdmdmdmd；CXCX(0)(0)CX CX(0)(0)C Cmdmdmdmd由由由由此此此此知知知知C Cmdmdmdmd0 0 0 0，即即即即有有有有C(XC(X(0)(0)md)md)md)md)CXCX(0)(0)C(XC(X(0)(0)md)md)md)md)。如如如如果果果果（X X(0)(0)mdmdmdmd）或或或或(X(X(0)(0)md)md)md)md)仍仍仍仍不不不不

34、是是是是基基基基可可可可行行行行解解解解，按按按按上上上上面面面面的的的的方方方方法法法法继继继继续续续续做做做做下下下下去去去去，最最最最后后后后一一一一定定定定可可可可以以以以找找找找到到到到一一一一个个个个基基基基可可可可行行行行解解解解，使使使使目目目目标标标标函函函函数数数数值值值值等等等等于于于于CXCX(0)(0)，问题得得证。，问题得得证。，问题得得证。，问题得得证。第26页/共61页2023/3/2727四、单纯形法迭代原理四、单纯形法迭代原理基本思路基本思路基本思路基本思路：先找出一个基可行解，判断它是否为最优解，如为否，则转换到相邻的基可行解，并使目标函数值不断增大，一直

35、到求得最优解或判断问题无解为止。在约束条件（1.16）的系数矩阵中，总可以找到一个单位矩阵：1.1.确定初始基可行解确定初始基可行解确定初始基可行解确定初始基可行解第27页/共61页2023/3/2728基阵基阵P1,P2,Pm称为基向量基向量基向量基向量，与其对应的变量x1,x2,xm称为基变量基变量基变量基变量，模型中的其它变量称为非基变量非基变量非基变量非基变量。在约束条件中令所有的非基变量等于零，即可得到一个解：X(x1,x2,xm,xm+1,xn)T（b1,b2,bm,0,0)T因b0，所以X满足非负约束，是一个基可行解。2.2.2.2.从一个基可行解转换为相邻的基可行解从一个基可行

36、解转换为相邻的基可行解从一个基可行解转换为相邻的基可行解从一个基可行解转换为相邻的基可行解定义：定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。第28页/共61页2023/3/2729设初始基可行解中的前设初始基可行解中的前m个为基变量为：个为基变量为：X(0)(x10,x20,xm0,0,，0)T将其代入约束条件（1.16）有系数矩阵的增广矩阵为：系数矩阵的增广矩阵为：系数矩阵的增广矩阵为：系数矩阵的增广矩阵为：因因因因P P1 1,P,P2 2,P,Pmm是一个基，其它向量是一个基，其它向量是一个基，其它向量是一个基，其它向量P Pj j可用这个基的线可用这个基的线可用这

37、个基的线可用这个基的线性组合来表示：性组合来表示：性组合来表示：性组合来表示：第29页/共61页2023/3/2730或或将（将（1.201.20）式乘上一个正数）式乘上一个正数 0 0得得（1.191.19）+（1.211.21）并整理得：）并整理得：由（由（1.221.22）式找到满足）式找到满足约束方程组约束方程组的另一个点的另一个点X X(1)(1),有有X X(1)(1)(x(x1 10 0-q q q qa a1j1j,x,x2 20 0-q q q qa a2j2j,x,xmm0 0-q q q qa amjmj,0,0,q q q q,0),0)T T其中其中q q q q是是

38、X X(1)(1)的第的第j j个坐标的值。个坐标的值。要使要使X X(1)(1)是一个基本可行解，必须使是一个基本可行解，必须使 x xi i0 0q q q qa aij ij0 1.230 1.23）令这令这mm个不等式中至少有一个等号成立。故可令个不等式中至少有一个等号成立。故可令第30页/共61页2023/3/2731由由 式式（1.24）知知因alj0，故由矩阵元素组成的行列式不为零，P1,P2,Pl-1,Pl,Pl+1,Pm是一个基。在上述增广矩阵中作初等变换，将第l行乘上（1/alj),再分别乘以（-aij)(i=1,2,l-1,l+1,m)加到各行去，则增广矩阵左半部分变成单

39、位矩阵。所以，X(1)是一个可行解。与变量xl1,x1l-1,x1l+1,xm,xj对应的向量经重新排列后得又因又因bl/aljq q，所以所以 b=(b1-q qa1j,bl-1-q qal-1,j,bl+1-q qal+1,j,bm-q qamj)T 由此由此X(1)是同是同X(0)相邻的基可行解，且由基向量组成的矩阵仍为单位矩阵相邻的基可行解，且由基向量组成的矩阵仍为单位矩阵。第31页/共61页2023/3/27323.3.最优性检验和解的判别最优性检验和解的判别将基本可行解X(0)和X(1)分别代入目标函数得式中，因为q0,所以只要就有z z(1)(1)z z(0)(0)。第32页/共

40、61页2023/3/2733最优性检验和解的判别准则最优性检验和解的判别准则（1）当所有sj0时，当前基可行解是线性规划问题的最优解；（2）当所有sj0，若对某个非基变量xj有cjzj0,则该线性规划问题有无穷多个最优解；若对所有非基变量有sj0，线性规划问题有唯一最优解。（3）若存在sj0，又Pj0，则表明线性规划问题有无界解。第33页/共61页2023/3/27341-4 1-4 单纯形法计算步骤单纯形法计算步骤第一步：求初始基可行解，列出初始单纯形表。第一步：求初始基可行解，列出初始单纯形表。cjc1 cmcjcnCB基bx1 xmxjxnc1x1b110a1ja1nc2x2b200a2

41、ja2ncmxmbm01amjamncjzj00基基变变量量及及其其值值问题中所有问题中所有变量变量单单位位矩矩阵阵非基变量系数向量非基变量系数向量P Pj j表示为基向量线性组合时的系数，表示为基向量线性组合时的系数，因基向量是单位向量，故有因基向量是单位向量，故有P Pj j=a=a1j1jP P1 1+a+a2j2jP P2 2+a+amjmj。各各变变量量在在目目标标函函数数中中的的系系数数值值各各基基变变量量在在目目标标函函数数中中对对应应的的系系数数检验数检验数s s s sj j=c=cj j-z-zj j=c=cj j-(c-(c1 1a a1j1j+c+c2 2a a2j2j

42、+c+cmma amjmj)返回第一章目录第34页/共61页2023/3/2735第二步：最优性检验第二步：最优性检验第二步：最优性检验第二步：最优性检验若单纯形表中所有检验数cjzj0，且基变量中不含有人工变量，则得到线性规划问题的最优解，计算结束；若存在cjzj0，而Pj0，则问题为无界解，计算结束；否则转下一步。第三步：从一个基可行解转换到相邻的目标函数值更大第三步：从一个基可行解转换到相邻的目标函数值更大第三步：从一个基可行解转换到相邻的目标函数值更大第三步：从一个基可行解转换到相邻的目标函数值更大的基可行解，列出新的单纯形表。的基可行解，列出新的单纯形表。的基可行解，列出新的单纯形表

43、。的基可行解，列出新的单纯形表。1.确定换入基的变量。只要有检验数sj0，其对应的xj就可以作为换入基的变量，当有一个以上检验数大于零时，从中找出最大的一个sk，其对应的变量xk为换入基的变量（简称换入变量）。2.确定换出基的变量。用Pk列的系数分别去除常数项，找出最小比值确定xl为换出基的变量，元素alk 决定了从一个基可行解到相邻基可行解的转移去向，所以，称alk为主元。第35页/共61页2023/3/27363.用用换换入入变变量量xk替替换换换换出出变变量量xl，作作初初等等变变换换，得到一个新的单纯形表。得到一个新的单纯形表。初等变换的方法是：将主元化为将主元化为将主元化为将主元化为

44、1 1 1 1，主元所在列的其它，主元所在列的其它，主元所在列的其它，主元所在列的其它元素化为元素化为元素化为元素化为0 0 0 0。第四步：重复第二、三两步，直到得出计算结果。第四步：重复第二、三两步，直到得出计算结果。第四步：重复第二、三两步，直到得出计算结果。第四步：重复第二、三两步，直到得出计算结果。例例例例5 5 5 5 用单纯形法求解线性规划问题解：在约束方程中加松弛变量，将该线性规划问题化为标准形式其约束条件系数矩阵的增广矩阵为：P1P2P3P4bP5基变量为x3、x4、x5；非基变量为x1、x2。单位矩阵构成一个基第36页/共61页2023/3/2737令令非非基基变变量量x1

45、、x2等等于于零零，的的初初始始基基本本可可行行解解为为：X(0)(0,0,15,24,5)T初始单纯形表cj 21000CB基bx1x2x3x4x50 x315051000 x424620100 x5511001cjzj21000因为存在s120，s210。所以初始基可行解不是最优解。选择最大检验数对应的非基变量作为换入变量。求最小比值，确定换入变量。主元列主元行将主元化为将主元化为将主元化为将主元化为1 1 1 1，主元所在列的其它，主元所在列的其它，主元所在列的其它，主元所在列的其它元素化为元素化为元素化为元素化为0 0 0 0。第37页/共61页2023/3/2738迭代运算初始单纯形

46、表初始单纯形表初始单纯形表初始单纯形表c cj j 2 21 10 00 00 0C CB B基基基基b bx x1 1x x2 2x x3 3x x4 4x x5 50 0 x x3 315150 05 51 10 00 00 0 x x4 42424 6 6 2 20 01 10 00 0 x x5 55 51 11 10 00 01 1c cj jz zj j2 21 10 00 00 0第一次迭代的单纯形表第一次迭代的单纯形表第一次迭代的单纯形表第一次迭代的单纯形表c cj j 2 21 10 00 00 0C CB B基基基基b bx x1 1x x2 2x x3 3x x4 4x

47、x5 5c cj jz zj jx3x1x5020141/301/600155100012/30-1/6101/30-1/30第38页/共61页2023/3/2739迭代运算第一次迭代的单纯形表第一次迭代的单纯形表第一次迭代的单纯形表第一次迭代的单纯形表c cj j 2 21 10 00 00 0C CB B基基基基b bx x1 1x x2 2x x3 3x x4 4x x5 50 0 x x3 315150 05 51 10 00 02 2x x1 14 41 11/31/30 01/61/60 00 0 x x5 51 10 0 2/32/3 0 0-1/6-1/61 1c cj jz

48、zj j0 01/31/30 0-1/3-1/30 0第二次迭代的单纯形表cj 21000CB基bx1x2x3x4x5cjzjx3x1x2021103/20-1/43/2017/201/4-1/20015/215/4-15/2000-1/4-1/2第39页/共61页2023/3/2740迭代运算结迭代运算结果果最终单纯性表最终单纯性表最终单纯性表最终单纯性表（第二次的结果）（第二次的结果）（第二次的结果）（第二次的结果）c cj j 2 21 10 00 00 0C CB B基基基基b bx x1 1x x2 2x x3 3x x4 4x x5 50 0 x x3 315/215/20 00

49、01 15/45/4-15/2-15/22 2x x1 17/27/21 10 00 01/41/4-1/2-1/21 1x x2 23/23/20 01 10 0-1/4-1/43/23/2c cj jz zj j0 00 00 0-1/4-1/4-1/2-1/2因为所有检验数sj0，且基变量中不含人工变量，所以得到线性规划问题的最优解为：代入目标函数得：第40页/共61页2023/3/27411-5 单纯形法的进一步讨论一、人工变量法一、人工变量法一、人工变量法一、人工变量法线性规划模型化为标准形式后，若其约束条件的系数矩阵中不含有单位矩阵，需加人工变量，以便求解。例例例例6 6 6 6

50、用单纯形法求解线性规划问题P4P6P7罚因子，任意大罚因子，任意大负值负值人工变量返回第一章目录第41页/共61页2023/3/2742单纯形法求解过程c cj j-3-30 01 10 00 0-M-M-M-MC CB B基基基基b bx x1 1x x2 2x x3 3x x4 4x x5 5x x6 6x x7 70 0 x x4 44 41 11 11 11 10 00 00 0-M-Mx x6 61 1-2-21 1-1-10 0-1-11 10 0-M-Mx x7 79 90 03 31 10 00 00 01 1c cj jz zj j-2M-3-2M-34M4M1 10 0-M