线性规划及其单纯形法精品文稿.ppt

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

1、线性规划及其单纯形法第1页，本讲稿共62页引引 言言线线性性规规划划是是运运筹筹学学的的重重要要分分支支，也也是是运运筹筹学学中中最最基基本本的的内内容容。早早在在19391939年年，前前苏苏联联著著名名数数学学家家康康特特洛洛维维奇奇研研究究了了运运输输和和下下料料等等问问题题，编编著著了了生生产产组组织织和和计计划划中中的的数数学学方方法法一一书书，为为线线性性规规划划的的研研究究奠奠定了基础。定了基础。19471947年年Dantgig提提出出了了一一般般线线性性规规划划的的算算法法单单纯纯形形法法。尔尔后后KuhnKuhn提出了线性规划的对偶理论，使线性规划的理论和方法日趋完善成熟。

2、提出了线性规划的对偶理论，使线性规划的理论和方法日趋完善成熟。随随着着电电子子计计算算机机的的产产生生与与发发展展，线线性性规规划划在在工工业业、农农业业、商商业业、交交通通运运输输业业、建建筑筑业业、军军事事等等行行业业的的计计划划和和管管理理及及决决策策分分析析中中得得到到了了广广泛泛与与深深入入的的应应用用，取取得得了了良良好好的的效效果果。目目前前，线线性性规规划划正正以以它它具具有有理理论论成成熟熟，计计算算简简单单精精确确，适适应应性性强强，应应用用面面广广的的特特点点引引起起了了工工程程技技术术人人员员、管管理理人人员员和和经经济济学学者者的的重重视视。它它已已成成为重要的优化技

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

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

5、及应用运筹学基础及应用第一章例第一章例第一章例第一章例2 2【例例2 2】某某企企业业计计划划生生产产I I、两两种种产产品品。这这两两种种产产品品都都要要分分别别在在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、161

6、6、1212小小时时，又又知知每每生生产产一一件件产产品品I I企企业业能能获获得得2 2元元利利润润、每每生生产产一一件件产产品品企企业业能能获获得得3 3元元利利润润，问问该该企企业业应应安安排排生生产两种产品各多少件，使总的利润收入为最大？产两种产品各多少件，使总的利润收入为最大？2023/2/65第5页，本讲稿共62页 产品产品资源资源产品产品产品产品生产能力生产能力（h）设备设备A（h）2212设备设备B（h）128设备设备B（h）4016设备设备B（h）0412利润（元利润（元/件）件）23假设：假设：计划期内生产计划期内生产 产品产品x1件，件，产品产品x2件。件。2023/2/

7、66第6页，本讲稿共62页例例2 2捷捷运运公公司司拟拟在在下下一一年年度度的的1 14 4月月份份的的4 4个个月月内内租租用用仓仓库库堆堆放放物物资资。已已知知各各月月份份所所需需仓仓库库面面积积数数。仓仓库库租租借借费费用用随随合合同同期期而而定定，期期限限越越长长，折折扣扣越越大大，具具体体数数字字如如表表1-21-2所所示示。租租借借仓仓库库的的合合同同每每月月初初都都可可办办理理，每每份份合合同同具具体体规规定定租租用用面面积积和和期期限限。因因此此，该该厂厂可可根根据据需需要要，在在任任何何一一个个月月初初办办理理租租借借合合同同。每每次次办办理理可可签签一一份份，也也可可签签若

8、若干干份份租租用用面面积积和和租租借借期期限限不不同同的的合合同同，试试确确定定该该公公司司签签定定租租借借合合同同的的最最优决策，目的是使所付租借费用最小。优决策，目的是使所付租借费用最小。2023/2/67第7页，本讲稿共62页假假设设用用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+

9、x13+x14+x21+x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12xij 0 (i1，2，4；j1，2，4）租借期为一个月的仓库面积租借期为一个月的仓库面积租借期为二个月的仓库面积租借期为二个月的仓库面积租借期为三个月的仓库面积租借期为三个月的仓库面积租借期为四个月的仓库面积租借期为四个月的仓库面积一月份拥有的租借面积一月份拥有的租借面积二月份拥有的租借面积二月份拥有的租借面积三月份拥有的租借面积三月份拥有的租借面积四月份拥有的租借面积四月份拥有的租借面积一月份仓库需求面积约束一月份仓库需求面积约束二月份仓库需求面积约束二月

10、份仓库需求面积约束三月份仓库需求面积约束三月份仓库需求面积约束四月份仓库需求面积约束四月份仓库需求面积约束非负约束非负约束2023/2/68第8页，本讲稿共62页组成线性规划模型的三个要素组成线性规划模型的三个要素组成线性规划模型的三个要素组成线性规划模型的三个要素max Z2x1x25x2156x12x224x1x25x1，x20目标函数：约束条件（1 1 1 1）变量（决策变量）变量（决策变量）变量（决策变量）变量（决策变量）:它它它它是是是是规规规规划划划划中中中中要要要要确确确确定定定定的的的的未未未未知知知知量量量量，是是是是用用用用数数数数量量量量方方方方式式式式来来来来表表表表示

11、示示示的的的的方方方方案案案案或或或或措施，可由决策者决定和控制。措施，可由决策者决定和控制。措施，可由决策者决定和控制。措施，可由决策者决定和控制。（2 2 2 2）目标函数：）目标函数：）目标函数：）目标函数：它它它它是是是是决决决决策策策策变变变变量量量量的的的的函函函函数数数数，是是是是决决决决策策策策者者者者在在在在一一一一定定定定的的的的限限限限制制制制条条条条件件件件下下下下希希希希望望望望得得得得到的结果。到的结果。到的结果。到的结果。（3 3 3 3）约束条件：）约束条件：）约束条件：）约束条件：指指指指决决决决策策策策变变变变量量量量取取取取值值值值时时时时受受受受到到到到

12、的的的的各各各各种种种种资资资资源源源源条条条条件件件件的的的的限限限限制制制制，通通通通常常常常用用用用等等等等式式式式或不等式来表达。或不等式来表达。或不等式来表达。或不等式来表达。其中，其中，其中，其中，x xij ij00叫做非负约束。叫做非负约束。叫做非负约束。叫做非负约束。由由由由于于于于目目目目标标标标函函函函数数数数是是是是决决决决策策策策变变变变量量量量的的的的线线线线性性性性函函函函数数数数，约约约约束束束束条条条条件件件件是是是是含含含含决决决决策策策策变变变变量量量量的的的的线线线线性性性性等等等等式式式式或或或或不不不不等等等等式式式式，所所所所以以以以此此此此类类类

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

14、生生生产产产产多多多多种种种种产产产产品品品品对对对对某某某某种种种种资资资资源源源源的的的的消消消消耗耗耗耗量量量量等等等等于于于于各各各各产产产产品品品品对对对对该该该该项项项项资资资资源源源源的的的的消耗量之和。消耗量之和。消耗量之和。消耗量之和。2023/2/69第9页，本讲稿共62页模型中，cj称为价值系数。bi是资源限制量。aij称为技术系数或工艺系数。二、线性规划模型的一般形式假假假假设设设设线线线线性性性性规规规规划划划划问问问问题题题题中中中中含含含含有有有有n n个个个个变变变变量量量量，mm个个个个约约约约束束束束方方方方程程程程。则则则则线线线线性性性性规规规规划划划划

15、模模模模型型型型的一般形式为：的一般形式为：的一般形式为：的一般形式为：max(或或min)zc1x1+c2x2+cnxna11x1+a12x2+a1nxn（或，（或，）b1a21x1+a22x2+a2nxn（或，（或，）b2am1x1+am2x2+amnxn（或，（或，）bmx1,x2,xn0简写为：简写为：向量形式：向量形式：矩阵形式：矩阵形式：2023/2/610第10页，本讲稿共62页三、线性规划问题的标准形式三、线性规划问题的标准形式若得出的线性规划模型不是标准形式，应通过下列方法将其化为标准形式：1.目标函数为求极小值的情况，即本教材规定，线性规划模型的标准形式为：本教材规定，线性

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

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

18、题的解的概念一、线性规划问题的解的概念基B中的每一个列向量Pj(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

19、 1,x,x2 2,，x xmm,0,0,0,0）T T。这就是线性规划问题的基解这就是线性规划问题的基解这就是线性规划问题的基解这就是线性规划问题的基解。2023/2/618第18页，本讲稿共62页基可行解基可行解：满足非负约束的解称为基可行解。：满足非负约束的解称为基可行解。可行基可行基：对应于基可行解的基称为可行基。：对应于基可行解的基称为可行基。例例：找找出出下下述述线线性性规规划划问问题题的的全全部部基基解解，指指出出其其中中的的基基可可行行解解，并并确定最优解确定最优解。max z2x1+3x2+x3x1+x35x1+2x2+x410 x2+x54x150一、线性规划问题的解的概念

20、一、线性规划问题的解的概念解解解解：用穷举法找出该线性规划问题的全部基解。打者为基可行解。最优解为：x12，x24，x33，x40，x50与最优解对应的目标函数值为z192023/2/619第19页，本讲稿共62页凸集凸集设设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。即即

21、：X XXX1 1+(1-)X+(1-)X2 2C (0C (01)1)称称C C为凸集为凸集。从直观上看，凸集没有凹入部分，其内部没有孔洞。从直观上看，凸集没有凹入部分，其内部没有孔洞。二、凸集和顶点凸集凸集凸集凸集凸集凸集2023/2/620第20页，本讲稿共62页不是凸集不是凸集不是凸集不是凸集二、凸集和顶点二、凸集和顶点顶点顶点顶点顶点设设设设C C C C为为为为凸凸凸凸集集集集，XCXCXCXC，若若若若X X X X不不不不能能能能用用用用C C C C中中中中不不不不同同同同的的的的两两两两点点点点X X X X1 1 1 1，X X X X2 2 2 2的线性组合表示为的线性

22、组合表示为的线性组合表示为的线性组合表示为X X X XXXXX1 1 1 1+(1-)X+(1-)X+(1-)X+(1-)X2 2 2 2 C (0 C (0 C (0 C (01)1)1)1)则则则则称称称称X X X X为为为为C C C C的的的的一一一一个个个个顶顶顶顶点点点点（或或或或极极极极点点点点）。即即即即X X X X不不不不能能能能成成成成为为为为C C C C中任何线段的内点。中任何线段的内点。中任何线段的内点。中任何线段的内点。2023/2/621第21页，本讲稿共62页三、三、三、三、线性规划的基本定理线性规划的基本定理定定定定理理理理1 1 1 1：若若若若线线线

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

24、规规规规划划划划的的的的基基基基本本本本可可可可行行行行解解解解对对对对应应应应于于于于其其其其可可可可行行行行域的顶点。域的顶点。域的顶点。域的顶点。定定定定理理理理 3 3 3 3 若若若若线线线线性性性性规规规规划划划划问问问问题题题题有有有有最最最最优优优优解解解解，一一一一定定定定存存存存在在在在一个基可行解是最优解。一个基可行解是最优解。一个基可行解是最优解。一个基可行解是最优解。单纯形法迭代原理2023/2/622第22页，本讲稿共62页定理定理定理定理1 1 1 1：若线性规划问题存在可行解，则问题的可行域是凸集。：若线性规划问题存在可行解，则问题的可行域是凸集。：若线性规划问

25、题存在可行解，则问题的可行域是凸集。：若线性规划问题存在可行解，则问题的可行域是凸集。证明证明证明证明 若满足线性规划约束条件若满足线性规划约束条件若满足线性规划约束条件若满足线性规划约束条件线性规划的基本定理的证明线性规划的基本定理的证明线性规划的基本定理的证明线性规划的基本定理的证明Pjxjbj=1n的所有点组成的的所有点组成的的所有点组成的的所有点组成的集合集合集合集合C C C C是凸集是凸集是凸集是凸集,则则则则C C C C内任意两点内任意两点内任意两点内任意两点X X X X1 1 1 1，X X X X2 2 2 2连线上的点也必然在连线上的点也必然在连线上的点也必然在连线上的

26、点也必然在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，将，将，将，将X X X X1 1 1 1 ，X X X X2 2 2 2代入约束条件，有代入约束条件

27、，有代入约束条件，有代入约束条件，有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为凸集。为凸集。2023/2/623第23页，本讲稿共62页引理引理引理引理 线性规划的可行解线性规划的可行解线性规划的可行解线性规划的可行解X X =(=(=(=

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

29、必必必必有有有有kmkm时时时时；当当当当k=k=mm时时时时，它它它它们们们们恰恰恰恰好好好好构构构构成成成成一一一一个个个个基基基基，从从从从而而而而X=(xX=(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构构构构成成成成一一一一个个个个基基基基，其其其其对对对对应应应应

30、的的的的解解解解恰恰恰恰为为为为X X，所以根据定义它是基可行解。所以根据定义它是基可行解。所以根据定义它是基可行解。所以根据定义它是基可行解。返回2023/2/624第24页，本讲稿共62页定定理理2 2：线线性性规规划划的的基基本本可可行行解解对对应应于于其其可可行行域域的的顶点。顶点。证证:本定理需要证明本定理需要证明:X:X是可行域顶点是可行域顶点X X是基可行解。是基可行解。用用反反证证法法证证明明：X X不不是是可可行行域域的的顶顶点点X X不不是是基基可可行解。行解。（1 1）X X不是基可行解不是基可行解X X不是可行域的顶点。不是可行域的顶点。假设假设X X的前的前m m个分

31、量为正，有个分量为正，有2023/2/625第25页，本讲稿共62页由由由由引引引引理理理理知知知知P P P P1 1 1 1,P,P,P,P2 2 2 2,P,P,P,Pm 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.12

32、1.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.13)+(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 1mdmd

33、mdmd1 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,(xmmmdmdmdmdmm),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可以这样来选择，使得对所有可以这样来选择，使得对所有可以

34、这样来选择，使得对所有可以这样来选择，使得对所有i=1,2,mi=1,2,m有有有有 x xi i mdmdmdmdi i00即即即即 X X不不不不 是是是是 可可可可 行行行行域的顶点。域的顶点。域的顶点。域的顶点。引理2023/2/626第26页，本讲稿共62页（2 2 2 2）X X不是可行域的顶点不是可行域的顶点不是可行域的顶点不是可行域的顶点X X不是基本可行解。不是基本可行解。不是基本可行解。不是基本可行解。设设设设X X X X(x(x1 1,x,x2 2,0,0,0),0)T T不不不不是是是是可可可可行行行行域域域域的的的的顶顶顶顶点点点点，因因因因而而而而可可可可以以以以

35、找找找找到到到到可可可可行行行行域域域域内内内内另另另另外外外外两两两两个个个个不不不不同同同同点点点点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.15)得：得：得

36、：得：因因因因(y(yj jz zj j)不不不不全全全全为为为为零零零零，故故故故P P1 1,P,P2 2,P,Pr r线线线线性性性性相相相相关关关关，即即即即X X不是基可行解。不是基可行解。不是基可行解。不是基可行解。2023/2/627第27页，本讲稿共62页定定定定理理理理 3 3 若若若若线线线线性性性性规规规规划划划划问问问问题题题题有有有有最最最最优优优优解解解解，一一一一定定定定存存存存在在在在一一一一个基可行解是最优解。个基可行解是最优解。个基可行解是最优解。个基可行解是最优解。证：设证：设证：设证：设X X(0)(0)=(x=(x1 10 0,x,x2 20 0,x,

37、xn n0 0)是线性规划的一个最优解，是线性规划的一个最优解，是线性规划的一个最优解，是线性规划的一个最优解，若若若若X X(0)(0)不不不不是是是是基基基基可可可可行行行行解解解解，由由由由定定定定理理理理2 2知知知知X X(0)(0)不不不不是是是是顶顶顶顶点点点点，一一一一定定定定能能能能在在在在可可可可行行行行域域域域内内内内找找找找到到到到通通通通过过过过X X(0)(0)的的的的直直直直线线线线上上上上的的的的另另另另外外外外两两两两个个个个点点点点（X X(0)(0)+mdmdmdmd)0)0和和和和（X X(0)(0)mdmdmdmd）0 0 0 0。将将将将这这这这两个

38、点代入目标函数有两个点代入目标函数有两个点代入目标函数有两个点代入目标函数有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)(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(

39、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)仍仍仍仍不不不不是是是是基基基基可可可可行行行行解解解解，按按按按上上上上面面面面的的的的方方方方法法法法继继继继续续续续做做做做下下下下去去去去，最最最最后后后后一定可以找到一个基可行解，使目标函数值等于一定可以找到一个基可行解，使目标函数值等于一定可以找到一个基可行解，使目标函数值等于一定可以找到一个基可行解，使目标函数值等于CXCX(0)(0)，问题得得证。，问题得得证。，问题

40、得得证。，问题得得证。2023/2/628第28页，本讲稿共62页四、单纯形法迭代原理四、单纯形法迭代原理基基基基本本本本思思思思路路路路：先找出一个基可行解，判断它是否为最优解，如为否，则转换到相邻的基可行解，并使目标函数值不断增大，一直到求得最优解或判断问题无解为止。在约束条件（1.16）的系数矩阵中，总可以找到一个单位矩阵：1.1.确定初始基可行解确定初始基可行解确定初始基可行解确定初始基可行解2023/2/629第29页，本讲稿共62页基阵P1,P2,Pm称为基基基基向向向向量量量量，与其对应的变量x1,x2,xm称为基变量基变量基变量基变量，模型中的其它变量称为非基变量非基变量非基变

41、量非基变量。在约束条件中令所有的非基变量等于零，即可得到一个解：X(x1,x2,xm,xm+1,xn)T（b1,b2,bm,0,0)T因b0，所以X满足非负约束，是一个基可行解。2.2.从一个基可行解转换为相邻的基可行解从一个基可行解转换为相邻的基可行解从一个基可行解转换为相邻的基可行解从一个基可行解转换为相邻的基可行解定定义义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。2023/2/630第30页，本讲稿共62页设初始基可行解中的前m个为基变量为：X(0)(x10,x20,xm0,0,，0)T将其代入约束条件（1.16）有系数矩阵的增广矩阵为：系数矩阵的增广矩阵为：系数矩阵

42、的增广矩阵为：系数矩阵的增广矩阵为：因因因因P P1 1,P,P2 2,P,Pmm是是是是一一一一个个个个基基基基，其其其其它它它它向向向向量量量量P Pj j可可可可用用用用这这这这个个个个基基基基的的的的线线线线性性性性组组组组合来表示：合来表示：合来表示：合来表示：2023/2/631第31页，本讲稿共62页或或或或将（将（将（将（1.201.20）式乘上一个正数）式乘上一个正数）式乘上一个正数）式乘上一个正数 0 0得得得得（1.191.19）+（1.211.21）并整理得：）并整理得：）并整理得：）并整理得：由由由由（1.221.22）式式式式找找找找到到到到满足约束方程组满足约束方

43、程组满足约束方程组满足约束方程组的另一个点的另一个点的另一个点的另一个点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是是是是X X(1)(1)的第的第的第的第j j个坐标的值。个坐标的值。个坐标的值。个坐标的值。要使要使要使要使X X(1)(1)是一个基本可行解，必须使是一个基本可行解，必须使是一个基本可行解，必须使是一个基本可行解，必须使 x xi i0 0q q q qa

44、 aij ij0 1.230 1.23）令这令这令这令这mm个不等式中至少有一个等号成立。故可令个不等式中至少有一个等号成立。故可令个不等式中至少有一个等号成立。故可令个不等式中至少有一个等号成立。故可令2023/2/632第32页，本讲稿共62页由式（1.24）知因alj0，故由矩阵元素组成的行列式不为零，P1,P2,Pl-1,Pl,Pl+1,Pm是一个基。在上述增广矩阵中作初等变换，将第l行乘上（1/alj),再分别乘以（-aij)(i=1,2,l-1,l+1,m)加到各行去，则增广矩阵左半部分变成单位矩阵。所以，X(1)是一个可行解。与变量xl1,x1l-1,x1l+1,xm,xj对应的

45、向量经重新排列后得又因又因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)相相邻邻的的基基可可行行解解，且且由由基基向向量量组组成成的的矩矩阵阵仍仍为为单单位矩阵位矩阵。2023/2/633第33页，本讲稿共62页3.3.最优性检验和解的判别最优性检验和解的判别最优性检验和解的判别最优性检验和解的判别将基本可行解X(0)和X(1)分别代入目标函数得式中，因为q0,所以只要就有z z(1)(1)z z(0)(0)。2023/2/634第34页，本讲稿共62页最优性检验和解的

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

47、zj00基基基基变变变变量量量量及及及及其其其其值值值值问问问问题题题题中中中中所所所所有变量有变量有变量有变量单单单单位位位位矩矩矩矩阵阵阵阵非非非非基基基基变变变变量量量量系系系系数数数数向向向向量量量量P Pj j表表表表示示示示为为为为基基基基向向向向量量量量线线线线性性性性组组组组合合合合时时时时的的的的系系系系数数数数，因因因因基基基基向向向向量量量量是是是是单位向量，故有单位向量，故有单位向量，故有单位向量，故有P Pj j=a=a1j1jP P1 1+a+a2j2jP P2 2+a+amjmj。各各各各变变变变量量量量在在在在目目目目标标标标函函函函数数数数中中中中的的的的系系

48、系系数数数数值值值值各各各各基基基基变变变变量量量量在在在在目目目目标标标标函函函函数数数数中中中中对对对对应应应应的的的的系系系系数数数数检验数检验数检验数检验数s s s sj j=c=cj j-z-zj j=c=cj j-(c-(c1 1a a1j1j+c+c2 2a a2j2j+c+cmma amjmj)返回第一章目录2023/2/636第36页，本讲稿共62页第二步：最优性检验第二步：最优性检验第二步：最优性检验第二步：最优性检验若单纯形表中所有检验数cjzj0，且基变量中不含有人工变量，则得到线性规划问题的最优解，计算结束；若存在cjzj0，而Pj0，则问题为无界解，计算结束；否则

49、转下一步。第第第第三三三三步步步步：从从从从一一一一个个个个基基基基可可可可行行行行解解解解转转转转换换换换到到到到相相相相邻邻邻邻的的的的目目目目标标标标函函函函数数数数值值值值更更更更大大大大的的的的基基基基可可可可行行行行解，列出新的单纯形表。解，列出新的单纯形表。解，列出新的单纯形表。解，列出新的单纯形表。1.确定换入基的变量。只要有检验数sj0，其对应的xj就可以作为换入基的变量，当有一个以上检验数大于零时，从中找出最大的一个sk，其对应的变量xk为换入基的变量（简称换入变量）。2.确定换出基的变量。用Pk列的系数分别去除常数项，找出最小比值确定xl为换出基的变量，元素alk 决定了

50、从一个基可行解到相邻基可行解的转移去向，所以，称alk为主元。2023/2/637第37页，本讲稿共62页3.用换入变量xk替换换出变量xl，作初等变换，得到一个新的单纯形表。初等变换的方法是：将主元化为将主元化为将主元化为将主元化为1 1 1 1，主元所在列的其它元素化为，主元所在列的其它元素化为，主元所在列的其它元素化为，主元所在列的其它元素化为0 0 0 0。第四步：重复第二、三两步，直到得出计算结果。第四步：重复第二、三两步，直到得出计算结果。第四步：重复第二、三两步，直到得出计算结果。第四步：重复第二、三两步，直到得出计算结果。例例例例5 5 5 5 用单纯形法求解线性规划问题解：在