运筹学全册配套完整课件2

1、本章知识结构本章知识结构第第 2 章章 线性规划线性规划本章教学目标与要求本章教学目标与要求 n n掌握线性规划模型基本概念，熟悉线性规划的标准型掌握线性规划模型基本概念，熟悉线性规划的标准型并能将一般线性规划问题转化为标准型；并能将一般线性规划问题转化为标准型； n n理解单纯形法的基本原理，掌握应用单纯形表求解线性理解单纯形法的基本原理，掌握应用单纯形表求解线性规划的方法；规划的方法； n n对给定的线性规划问题，能熟练写出其对偶问题，掌握对给定的线性规划问题，能熟练写出其对偶问题，掌握对偶单纯形算法，能对线性规划的解进行灵敏度分析；对偶单纯形算法，能对线性规划的解进行灵敏度分析； n n

2、能熟练地建立实际问题的线性规划模型。能熟练地建立实际问题的线性规划模型。2.1线性规划模型与图解法线性规划模型与图解法2.1线性规划问题及其数学模型线性规划问题及其数学模型【例例2.1】（生产计划问题）某企业生产（生产计划问题）某企业生产I、II和和III三种产品三种产品，每种产品需经过三道工序，每种产品需经过三道工序A、B、C，每件产品在每道工序中，每件产品在每道工序中的工时定额、每道工序在每周可利用的有效工时和每件产品的的工时定额、每道工序在每周可利用的有效工时和每件产品的利润见下表。问每种产品各生产多少利润见下表。问每种产品各生产多少,可使这一周内生产的产品可使这一周内生产的产品所获利润

3、最大？所获利润最大？定额定额( (工时工时/ /件件) )产品型号产品型号每周可利用每周可利用的有效工时的有效工时IIIIII工序工序A1.21.01.15400B0.70.90.62800C0.90.81.03600利润（元利润（元/ /件）件）1015122.1.1问题的引入问题的引入2.1线性规划模型与图解法线性规划模型与图解法设一周内企业各产品的生产件数为设一周内企业各产品的生产件数为xj( ( j=1,2,3) ) 生产计划问题的生产计划问题的数学模型数学模型： 其中其中s.t.是英文是英文“subjectto”（受约束于）的缩写。（受约束于）的缩写。定额定额( (工时工时/ /件件

4、) )产品型号产品型号每周可利用每周可利用的有效工时的有效工时IIIIII工序工序A1.21.01.15400B0.70.90.62800C0.90.81.03600利润（元利润（元/ /件）件）101512123123123123max1015121.11.01.154000.70.90.62800. .0.90.81.0360001, 2, 3jzxxxxxxxxxs txxxxj2.1线性规划模型与图解法线性规划模型与图解法 【例例2.22.2】 （营养配餐问题）假定一个成年人每天需要从（营养配餐问题）假定一个成年人每天需要从食物中获取食物中获取30003000卡路里热量，卡路里热量，5

5、555克蛋白质和克蛋白质和800800毫克钙。如果毫克钙。如果市场上只有四种食品可选，它们每千克所含热量和营养成份以市场上只有四种食品可选，它们每千克所含热量和营养成份以及市场价格如下表所示。问如何选择才能满足营养的前提下使及市场价格如下表所示。问如何选择才能满足营养的前提下使购买食品的费用最小？购买食品的费用最小？ 食品的营养构成表食品的营养构成表序号序号 食品名称食品名称 热量热量(卡路里卡路里)蛋白质蛋白质(g)钙钙(mg)价格价格(元元)1猪肉猪肉100050400102鸡蛋鸡蛋8006020063大米大米9002030034白菜白菜200105002则该问题的数学模型为：则该问题的数

6、学模型为：2.1线性规划模型与图解法线性规划模型与图解法设设xj( ( j=1,2,3,4) )为第为第 j 种食品每天的购买量，种食品每天的购买量，1234123412341234min10632100080090020030005060201055.4002003005008000,(1,2,3,4)jzxxxxxxxxxxxxstxxxxxj2.1.2线性规划问题及其模型线性规划问题及其模型上面所建立的数学模型中有三个要素：上面所建立的数学模型中有三个要素：l）决策变量决策变量 这些决策变量的一组定值代表所给问题的一个这些决策变量的一组定值代表所给问题的一个具体解决方案、措施等。具体解决

7、方案、措施等。2.1线性规划模型与图解法线性规划模型与图解法2）目标函数目标函数一个决策问题总有一个试图达到的目标，数学上一个决策问题总有一个试图达到的目标，数学上表示为决策变量的函数，称为目标函数。表示为决策变量的函数，称为目标函数。3）约束条件约束条件决策变量取值时受到的各种资源限制，通常表决策变量取值时受到的各种资源限制，通常表示成决策变量的等式或不等式。示成决策变量的等式或不等式。由这三个要素组成的问题，在数学上叫作规划问题，一般称由这三个要素组成的问题，在数学上叫作规划问题，一般称为为数学规划数学规划。如果目标函数及约束条件均为决策变量的如果目标函数及约束条件均为决策变量的线性函线性

8、函数，数，则称这样的数学规划为则称这样的数学规划为线性规划线性规划，否则称为，否则称为非线性规划非线性规划。2.1线性规划模型与图解法线性规划模型与图解法线性规划的数学模型的一般形式为：线性规划的数学模型的一般形式为： 112211212211212222221222max()( ,)( ,). .( ,)0,1,2,.min nnnnnnmmmnnmjzc xc xc xa xa xaxbaxaxaxbs taxaxaxbxjn或 2.1线性规划模型与图解法线性规划模型与图解法 矩阵形式：矩阵形式： 0XbAX),(. .)max(mintsCXz或向量形式：向量形式： njxxtsCXzj

9、jnj, 2, 10),(. .min)max(1bPj或 其中：其中：C=(=(c1,c2,cn) )是是n 维行向量维行向量，称为价值系数向量，简称为价值系数向量，简称为称为价值向量价值向量；b=(=(b1,b2,bm) )T是是m 维列向量维列向量, ,称为称为资源向量资源向量；X=(=(x1,x2,xn) )T称为称为决策向量决策向量；A为技术系数矩阵（也称为消耗为技术系数矩阵（也称为消耗系数矩阵），简称为系数矩阵），简称为技术矩阵技术矩阵，)(212222111211n21PPPAmnmmnnaaaaaaaaamiiiaaa21iP2.1线性规划模型与图解法线性规划模型与图解法2.1

10、.3线性规划模型的标准型线性规划模型的标准型 为了求解方便，通常规定线性规划的某种形式为标准形。为了求解方便，通常规定线性规划的某种形式为标准形。0XbAXCXzmax 线性规划的线性规划的标准型的特点标准型的特点：目标函目标函数是最大化；数是最大化；b0；约束条件均由等式；约束条件均由等式组成；组成；决策变量均为非负。决策变量均为非负。 不满足上述不满足上述4 4个特点的个特点的LPLP问题，称为非标准形。对于非标准问题，称为非标准形。对于非标准形式的线性规划，都可以形式的线性规划，都可以通过适当的变换转化为等价的标准型问通过适当的变换转化为等价的标准型问题。题。njxbxaxaxabxax

11、axabxaxaxatsxcxcxczjmnmnmmnnnnnn,2,1,0.max2211222221211121211122112.1线性规划模型与图解法线性规划模型与图解法【例例2.3】将下列线性规划问题化成标准型将下列线性规划问题化成标准型无约束321321321321321,0,0632442392.32minxxxxxxxxxxxxtsxxxz 解解 1）引入变量）引入变量 33311331, 0,xxxxxxxx ，使0,0,0,063324422392.332min33213321332133213321xxxxxxxxxxxxxxxxtsxxxxz2.1线性规划模型与图解法线

12、性规划模型与图解法2）第一个约束引入松弛变量）第一个约束引入松弛变量x4,第二个约束引入剩余变量第二个约束引入剩余变量x5; ; 0, 0, 0, 0, 0, 063324422392. .00332min54332133215332143321543321xxxxxxxxxxxxxxxxxxxxtsxxxxxxz3）目标函数）目标函数min变为改变为变为改变为max0, 0, 0, 0, 0, 063324422392. .00332max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxtsxxxxxxz2.1线性规划模型与图解法线性规划模型与图解

13、法4）将第三个等式约束两边同乘以）将第三个等式约束两边同乘以1。最后得到该问题的标准形式为：最后得到该问题的标准形式为：0, 0, 0, 0, 0, 063324422392. .00332max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxtsxxxxxxz星期所需人数一300二300三350四400五480六600日5507654321minxxxxxxxz7.,2,1,0550600480350300300765436543254321763217652176541jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxj某产品由2件

14、甲零件和3件乙零件组成。2种零件均须在设备A、B上加工，每件甲零件在2种设备上的加工时间分别为5分钟和9分钟；每件乙零件在2种设备上加工时间分别为4分钟和10分钟。现有设备A 2台，设备B 3台，每台设备可供加工的时间为每天8小时。为了保持两种设备负荷均衡，要求一种设备的加工总时间不超过另一种的加工总时间1小时。问每天加工2种零件各多少，能使总产量最大？ 21,xx)31,21min(21xxy 设备加工时间的限制为 96028604521xx1440386010921xx60)109()45(2121xxxx设备负荷均衡约束：写成线性形式： 60)109()45(2121xxxx60)109

15、()45(2121xxxxyz max121xy 231xy ， 于是得到本问题的数学模型为： yz max0,606460641440109960453121.212121212121xxyxxxxxxxxxyxyts11221 121 22112 122 22221222m ax ()(,)(,). .(,)0,1, 2,.m in nnnnnnmmm nnmjzc xc xc xaxaxaxbaxaxaxbs taxaxaxbxjn 或0XbAX),(. .)max(mintsCXz或njxxtsCXzjjnj, 2, 10),(. .min)max(1bPj或0XbAXCXzmax 线

16、性规划的线性规划的标准型的特点标准型的特点：目标函目标函数是最大化；数是最大化；b0；约束条件均由等式约束条件均由等式组成；组成；决策变量均为非负。决策变量均为非负。 njxbxaxaxabxaxaxabxaxaxatsxcxcxczjmnmnmmnnnnnn,2, 1,0.max2211222221211121211122112.1线性规划模型与图解法线性规划模型与图解法2.1.4线性规划的图解法线性规划的图解法 对于只有两个变量的线性规划问题，可以直接使用图解法对于只有两个变量的线性规划问题，可以直接使用图解法求解。图解法简单直观，对一般线性规划问题的求解富有启发求解。图解法简单直观，对一

17、般线性规划问题的求解富有启发作用。作用。 图解法可分三步进行：图解法可分三步进行：1）在平面上建立直角坐标系；在平面上建立直角坐标系；2）根据约束条件画出相应的半平面，由这些半平面共同确根据约束条件画出相应的半平面，由这些半平面共同确定的区域即为定的区域即为可行域可行域；3）画出目标函数的等值线，然后沿目标函数要求的方向平画出目标函数的等值线，然后沿目标函数要求的方向平移至与可行域边界相切的点，该点就是最优解，相应的坐标即为移至与可行域边界相切的点，该点就是最优解，相应的坐标即为最优解。最优解。2.1线性规划模型与图解法线性规划模型与图解法 【例例2.42.4】 求解线性规划问题求解线性规划问

18、题 0, 02426023302. .5040max212212121xxxxxxxtsxxz解解应用图解法求解线性规划，应用图解法求解线性规划，分下面三步求解。分下面三步求解。1）建立直角坐标系）建立直角坐标系1x2xo2）确定可行域）确定可行域令令3个约束条件为等式，得到个约束条件为等式，得到3条直线，画条直线，画出第一象限的三个不等式区域，他们的交集出第一象限的三个不等式区域，他们的交集就是可行域，亦即区域就是可行域，亦即区域OABCD，其内部及，其内部及边界上的每一个点都是线性规划的解。边界上的每一个点都是线性规划的解。301530221 xx3020602321 xx122422xA

19、BCD3）确定最优解）确定最优解目标函数的等值线目标函数的等值线z=40 x1+50 x2( (z z取定某取定某一个常值一个常值) ) 。沿着函数的梯度方向移动，。沿着函数的梯度方向移动，函数值会增大，当移动到点顶点函数值会增大，当移动到点顶点( (15,15/2) ) ，再继续移动就离开区域了。于是点再继续移动就离开区域了。于是点C就就是最优解，最优值为是最优解，最优值为z=40z=4015+5015+5015/2=97515/2=975 2.1线性规划模型与图解法线性规划模型与图解法2.1线性规划模型与图解法线性规划模型与图解法 【例例2.52.5】 求解线性规划问题求解线性规划问题 0

20、, 02426023302. .8040max212212121xxxxxxxtsxxz解解该题将例该题将例2.4中的目标中的目标函数变为函数变为z=40 x1+80 x2,可行域不可行域不变。变。由于目标函数等直线由于目标函数等直线z=40 x1+80 x2与直线与直线x1+2x2=30平行，平行， 当目标函数的等值线与直线当目标函数的等值线与直线x1+2x2=30重合时，重合时，目标函数目标函数z=40 x1+80 x2z=40 x1+80 x2达到最大值达到最大值12001200。于是线段。于是线段BCBC上的每一个点均为上的每一个点均为该问题的最优解。该问题的最优解。 1x2xo301

21、530221 xx3020602321 xx2422xABCD2.1线性规划模型与图解法线性规划模型与图解法 【例例2.62.6】 求解线性规划问题求解线性规划问题 0,2282. .42max21212121xxxxxxtsxxz1x2xo88221 xx42221xx2解解 由于可行域无界由于可行域无界, , 目标函目标函数数z=2x1+4x2z=2x1+4x2沿着它的法线方沿着它的法线方向向(2,4)(2,4)移动，移动可以无限移动，移动可以无限制下去，而目标函数值一直制下去，而目标函数值一直增加。增加。 所以该线性规划问所以该线性规划问题无有限最优解，有题无有限最优解，有无界解无界解。

22、2.1线性规划模型与图解法线性规划模型与图解法 【例例2.72.7】 求解线性规划问题求解线性规划问题 0,22. .24max212121xxxxtsxxz 解解 约束条件互不相容，没有约束条件互不相容，没有公共交点，可行域是一个空集，不存在满足条件的公共交点，可行域是一个空集，不存在满足条件的解，说明线性规划问题无解，当然更没有最优解，如图所示。解，说明线性规划问题无解，当然更没有最优解，如图所示。 1x2xo12221xx22）有无穷多最优解3）有无界解4）无可行解几点启示：几点启示： 1）线性规划若存在可行解，则其的可行域是若干个半平面）线性规划若存在可行解，则其的可行域是若干个半平面

23、的相交形成的一个多面凸集（可能是空集的相交形成的一个多面凸集（可能是空集）。）。 2）线性规划问题若存在最优解，则其最优解（或最优解）线性规划问题若存在最优解，则其最优解（或最优解之一）总可以之一）总可以在可行域的某个顶点上达到在可行域的某个顶点上达到。2.2单纯形法单纯形法 单纯形法是解决线性规划问题的基本方法。单纯形法是解决线性规划问题的基本方法。2.2.1线性规划的解的基本概念线性规划的解的基本概念 设线性规划的标准型为设线性规划的标准型为 ）（2) 1 (max0XbAXCXz 其中其中A是是mn矩阵矩阵( (n m ，？，？),),设设A A的秩的秩r( (A)=)=m，亦即，亦即A

24、中至少有中至少有一个满秩一个满秩mm子矩阵。子矩阵。 解解 满足系统约束条件（满足系统约束条件（1 1）的决策向量）的决策向量X=(=(x1,x2,xn) )T称称为线性规划的解为线性规划的解。 可行解可行解 满足符号约束条件（满足符号约束条件（2 2）的解）的解X=(=(x1,x2,xn) )T称为称为线性规划的线性规划的可行解可行解。 2.2单纯形法单纯形法可行域可行域全体可行解的集合称为线性规划的全体可行解的集合称为线性规划的可行域可行域，一般，一般记作记作D=X|AX=b,X0。最优解最优解使目标函数达到最小值（或最大值）的可行解使目标函数达到最小值（或最大值）的可行解X*=(=(x1

25、*,x2*,xn*) )T称为线性规划的最优解。称为线性规划的最优解。 最优值最优值 最优解的目标函数值称为线性规划的最优值。最优解的目标函数值称为线性规划的最优值。 基基若若B为为A的满秩子方阵，即的满秩子方阵，即r(B)=m,则，称则，称B是线性规划是线性规划问题的一个基。也就是说，矩阵问题的一个基。也就是说，矩阵B是由是由A的的m个线性无关列向量个线性无关列向量所构成，不妨设为：所构成，不妨设为：mmmmmmmPPPaaaaaaaaaB21212222111211称称Pj( (j=1,2,m) )为为基向量基向量。 2.2单纯形法单纯形法 基变量、非基变量基变量、非基变量 与其基向量与其

26、基向量Pj( (j=1,2,m) )相对应的变相对应的变量量xj( (j=1,2,m) )为为基变量基变量，其他决策变量称为，其他决策变量称为非基变量非基变量。 基解基解 记基变量为记基变量为XB=(=(x1,x2,xn) )T ，非基变量为，非基变量为XN= =( (xm+1,xm+2,xn) )T ，称满足方程，称满足方程(1)(1)的解的解X（XB，XN）为）为LPLP的基解，其中的基解，其中XB=B-1-1b，XN= =0。 基可行解基可行解 若基解满足非负约若基解满足非负约束（束（2 2），即），即XB=B-1-1b0 ，则称该，则称该其解为基可行解。称相应的基其解为基可行解。称相应

27、的基B为为可行基可行基。 解基解可行解基可行解【例例2.8】求出下面线性规划的所有基解求出下面线性规划的所有基解,并指出那些是基可行解并指出那些是基可行解.2.2单纯形法单纯形法04102532max515242131321xxxxxxxxxxxz解解 其系数矩阵为：其系数矩阵为： 521,.,100100102100101PPPA易知，其易知，其3 3阶子方阵共有阶子方阵共有1010个。可以验证：其中有个。可以验证：其中有2 2个子方个子方阵为奇异的即：阵为奇异的即：0,00010101194319BPPPB0,1010120001054210BPPPB而另外的而另外的8 8个个3 3阶子方

28、阵均为非奇异的，即该阶子方阵均为非奇异的，即该LPLP问题共有问题共有8 8个个基。基。2.2单纯形法单纯形法分别将这分别将这8 8个基对应的基解求出，例如：个基对应的基解求出，例如： ,1000100015431PPPB则基变量为则基变量为x3,x4,x5，令非基变量，令非基变量x1=x2=0，代入原约束方程，代入原约束方程，x1x2x3x4x5是否基可行解005104是04520是50054是05501否100504否55/2003/2是54030否24300是04102532max515242131321xxxxxxxxxxxz立即可得基解立即可得基解 X1 1（0,0,5,10,4)T

29、。类似地求出其它基解，见下表类似地求出其它基解，见下表2.2单纯形法单纯形法2.2.2单纯形法的基本原理单纯形法的基本原理 基本概念基本概念凸集凸集设设D是是n维空间的一个点集，若对任意两点维空间的一个点集，若对任意两点均有均有；则称；则称D为凸集。为凸集。 ,) 1 (DxDx)2( 1 , 0,)1 ()2() 1 (Dxx几何意义：几何意义：凸集凸集D中的任意两点间的连线仍然在中的任意两点间的连线仍然在D中。中。顶点顶点设设D是凸集，若是凸集，若且且x 不能用不能用D中不同的两点中不同的两点的凸组合表示为的凸组合表示为，则称，则称x为为D的的一个顶点（或极点）。一个顶点（或极点）。 Dx

30、)2()1(,xx) 10( ,)1 ()2() 1 (DxxxS1S2S32.2单纯形法单纯形法 基本定理基本定理定理定理2.1若线性规划问题存在可行域，则可行域是凸集。若线性规划问题存在可行域，则可行域是凸集。定理定理2.2线性规划可行域线性规划可行域D中的点中的点X是顶点的充要条件为是顶点的充要条件为X是基可行解。是基可行解。定理定理2.3若线性规划有最优解，则最优解一定可以在可行若线性规划有最优解，则最优解一定可以在可行域的顶点上得到。域的顶点上得到。 引理引理线性规划可行解线性规划可行解X（x1,x2, xn ）为基可行解的充分）为基可行解的充分必要条件为必要条件为X的正分量对应的系

31、数列向量线性无关。的正分量对应的系数列向量线性无关。 11221 121 22112 122 22221222m ax ()(,)(,). .(,)0,1, 2,.m in nnnnnnmmm nnmjzc xc xc xaxaxaxbaxaxaxbs taxaxaxbxjn 或0XbAX),(. .)max(mintsCXz或njxxtsCXzjjnj, 2, 10),(. .min)max(1bPj或0XbAXCXzmax 线性规划的线性规划的标准型的特点标准型的特点：目标函目标函数是最大化；数是最大化；b0；约束条件均由等式约束条件均由等式组成；组成；决策变量均为非负。决策变量均为非负。

32、 njxbxaxaxabxaxaxabxaxaxatsxcxcxczjmnmnmmnnnnnn,2, 1,0.max2211222221211121211122112.1线性规划模型与图解法线性规划模型与图解法2.1.4线性规划的图解法线性规划的图解法 对于只有两个变量的线性规划问题，可以直接使用图解法对于只有两个变量的线性规划问题，可以直接使用图解法求解。图解法简单直观，对一般线性规划问题的求解富有启发求解。图解法简单直观，对一般线性规划问题的求解富有启发作用。作用。 图解法可分三步进行：图解法可分三步进行：1）在平面上建立直角坐标系；在平面上建立直角坐标系；2）根据约束条件画出相应的半平面

33、，由这些半平面共同确根据约束条件画出相应的半平面，由这些半平面共同确定的区域即为定的区域即为可行域可行域；3）画出目标函数的等值线，然后沿目标函数要求的方向平画出目标函数的等值线，然后沿目标函数要求的方向平移至与可行域边界相切的点，该点就是最优解，相应的坐标即为移至与可行域边界相切的点，该点就是最优解，相应的坐标即为最优解。最优解。2.1线性规划模型与图解法线性规划模型与图解法 【例例2.42.4】 求解线性规划问题求解线性规划问题 0, 02426023302. .5040max212212121xxxxxxxtsxxz解解应用图解法求解线性规划，应用图解法求解线性规划，分下面三步求解。分下

34、面三步求解。1）建立直角坐标系）建立直角坐标系1x2xo2）确定可行域）确定可行域令令3个约束条件为等式，得到个约束条件为等式，得到3条直线，画条直线，画出第一象限的三个不等式区域，他们的交集出第一象限的三个不等式区域，他们的交集就是可行域，亦即区域就是可行域，亦即区域OABCD，其内部及，其内部及边界上的每一个点都是线性规划的解。边界上的每一个点都是线性规划的解。301530221 xx3020602321 xx122422xABCD3）确定最优解）确定最优解目标函数的等值线目标函数的等值线z=40 x1+50 x2( (z z取定某取定某一个常值一个常值) ) 。沿着函数的梯度方向移动，。

35、沿着函数的梯度方向移动，函数值会增大，当移动到点顶点函数值会增大，当移动到点顶点( (15,15/2) ) ，再继续移动就离开区域了。于是点再继续移动就离开区域了。于是点C就就是最优解，最优值为是最优解，最优值为z=40z=4015+5015+5015/2=97515/2=975 2.1线性规划模型与图解法线性规划模型与图解法2.1线性规划模型与图解法线性规划模型与图解法 【例例2.52.5】 求解线性规划问题求解线性规划问题 0, 02426023302. .8040max212212121xxxxxxxtsxxz解解该题将例该题将例2.4中的目标中的目标函数变为函数变为z=40 x1+80

36、 x2,可行域不可行域不变。变。由于目标函数等直线由于目标函数等直线z=40 x1+80 x2与直线与直线x1+2x2=30平行，平行， 当目标函数的等值线与直线当目标函数的等值线与直线x1+2x2=30重合时，重合时，目标函数目标函数z=40 x1+80 x2z=40 x1+80 x2达到最大值达到最大值12001200。于是线段。于是线段BCBC上的每一个点均为上的每一个点均为该问题的最优解。该问题的最优解。 1x2xo301530221 xx3020602321 xx2422xABCD2.1线性规划模型与图解法线性规划模型与图解法 【例例2.62.6】 求解线性规划问题求解线性规划问题

37、0,2282. .42max21212121xxxxxxtsxxz1x2xo88221 xx42221xx2解解 由于可行域无界由于可行域无界, , 目标函目标函数数z=2x1+4x2z=2x1+4x2沿着它的法线方沿着它的法线方向向(2,4)(2,4)移动，移动可以无限移动，移动可以无限制下去，而目标函数值一直制下去，而目标函数值一直增加。增加。 所以该线性规划问所以该线性规划问题无有限最优解，有题无有限最优解，有无界解无界解。2.1线性规划模型与图解法线性规划模型与图解法 【例例2.72.7】 求解线性规划问题求解线性规划问题 0,22. .24max212121xxxxtsxxz 解解

38、约束条件互不相容，没有约束条件互不相容，没有公共交点，可行域是一个空集，不存在满足条件的公共交点，可行域是一个空集，不存在满足条件的解，说明线性规划问题无解，当然更没有最优解，如图所示。解，说明线性规划问题无解，当然更没有最优解，如图所示。 1x2xo12221xx22）有无穷多最优解3）有无界解4）无可行解几点启示：几点启示： 1）线性规划若存在可行解，则其的可行域是若干个半平面）线性规划若存在可行解，则其的可行域是若干个半平面的相交形成的一个多面凸集（可能是空集的相交形成的一个多面凸集（可能是空集）。）。 2）线性规划问题若存在最优解，则其最优解（或最优解）线性规划问题若存在最优解，则其最

39、优解（或最优解之一）总可以之一）总可以在可行域的某个顶点上达到在可行域的某个顶点上达到。2.2单纯形法单纯形法 单纯形法是解决线性规划问题的基本方法。单纯形法是解决线性规划问题的基本方法。2.2.1线性规划的解的基本概念线性规划的解的基本概念 设线性规划的标准型为设线性规划的标准型为 ）（2) 1 (max0XbAXCXz 其中其中A是是mn矩阵矩阵( (n m ，？，？),),设设A A的秩的秩r( (A)=)=m，亦即，亦即A中至少有中至少有一个满秩一个满秩mm子矩阵。子矩阵。 解解 满足系统约束条件（满足系统约束条件（1 1）的决策向量）的决策向量X=(=(x1,x2,xn) )T称称为

40、线性规划的解为线性规划的解。 可行解可行解 满足符号约束条件（满足符号约束条件（2 2）的解）的解X=(=(x1,x2,xn) )T称为称为线性规划的线性规划的可行解可行解。 2.2单纯形法单纯形法可行域可行域全体可行解的集合称为线性规划的全体可行解的集合称为线性规划的可行域可行域，一般，一般记作记作D=X|AX=b,X0。最优解最优解使目标函数达到最小值（或最大值）的可行解使目标函数达到最小值（或最大值）的可行解X*=(=(x1*,x2*,xn*) )T称为线性规划的最优解。称为线性规划的最优解。 最优值最优值 最优解的目标函数值称为线性规划的最优值。最优解的目标函数值称为线性规划的最优值。

41、 基基若若B为为A的满秩子方阵，即的满秩子方阵，即r(B)=m,则，称则，称B是线性规划是线性规划问题的一个基。也就是说，矩阵问题的一个基。也就是说，矩阵B是由是由A的的m个线性无关列向量个线性无关列向量所构成，不妨设为：所构成，不妨设为：mmmmmmmPPPaaaaaaaaaB21212222111211称称Pj( (j=1,2,m) )为为基向量基向量。 2.2单纯形法单纯形法 基变量、非基变量基变量、非基变量 与其基向量与其基向量Pj( (j=1,2,m) )相对应的变相对应的变量量xj( (j=1,2,m) )为为基变量基变量，其他决策变量称为，其他决策变量称为非基变量非基变量。 基解

42、基解 记基变量为记基变量为XB=(=(x1,x2,xn) )T ，非基变量为，非基变量为XN= =( (xm+1,xm+2,xn) )T ，称满足方程，称满足方程(1)(1)的解的解X（XB，XN）为）为LPLP的基解，其中的基解，其中XB=B-1-1b，XN= =0。 基可行解基可行解 若基解满足非负约若基解满足非负约束（束（2 2），即），即XB=B-1-1b0 ，则称该，则称该其解为基可行解。称相应的基其解为基可行解。称相应的基B为为可行基可行基。 解基解可行解基可行解【例例2.8】求出下面线性规划的所有基解求出下面线性规划的所有基解,并指出那些是基可行解并指出那些是基可行解.2.2单纯

43、形法单纯形法04102532max515242131321xxxxxxxxxxxz解解 其系数矩阵为：其系数矩阵为： 521,.,100100102100101PPPA易知，其易知，其3 3阶子方阵共有阶子方阵共有1010个。可以验证：其中有个。可以验证：其中有2 2个子方个子方阵为奇异的即：阵为奇异的即：0,00010101194319BPPPB0,1010120001054210BPPPB而另外的而另外的8 8个个3 3阶子方阵均为非奇异的，即该阶子方阵均为非奇异的，即该LPLP问题共有问题共有8 8个个基。基。2.2单纯形法单纯形法分别将这分别将这8 8个基对应的基解求出，例如：个基对应

44、的基解求出，例如： ,1000100015431PPPB则基变量为则基变量为x3,x4,x5，令非基变量，令非基变量x1=x2=0，代入原约束方程，代入原约束方程，x1x2x3x4x5是否基可行解005104是04520是50054是05501否100504否55/2003/2是54030否24300是04102532max515242131321xxxxxxxxxxxz立即可得基解立即可得基解 X1 1（0,0,5,10,4)T。类似地求出其它基解，见下表类似地求出其它基解，见下表2.2单纯形法单纯形法2.2.2单纯形法的基本原理单纯形法的基本原理 基本概念基本概念凸集凸集设设D是是n维空间

45、的一个点集，若对任意两点维空间的一个点集，若对任意两点均有均有；则称；则称D为凸集。为凸集。 ,) 1 (DxDx)2( 1 , 0,)1 ()2() 1 (Dxx几何意义：几何意义：凸集凸集D中的任意两点间的连线仍然在中的任意两点间的连线仍然在D中。中。顶点顶点设设D是凸集，若是凸集，若且且x 不能用不能用D中不同的两点中不同的两点的凸组合表示为的凸组合表示为，则称，则称x为为D的的一个顶点（或极点）。一个顶点（或极点）。 Dx)2()1(,xx) 10( ,)1 ()2() 1 (DxxxS1S2S32.2单纯形法单纯形法 基本定理基本定理定理定理2.1若线性规划问题存在可行域，则可行域是

46、凸集。若线性规划问题存在可行域，则可行域是凸集。定理定理2.2线性规划可行域线性规划可行域D中的点中的点X是顶点的充要条件为是顶点的充要条件为X是基可行解。是基可行解。定理定理2.3若线性规划有最优解，则最优解一定可以在可行若线性规划有最优解，则最优解一定可以在可行域的顶点上得到。域的顶点上得到。 引理引理线性规划可行解线性规划可行解X（x1,x2, xn ）为基可行解的充分）为基可行解的充分必要条件为必要条件为X的正分量对应的系数列向量线性无关。的正分量对应的系数列向量线性无关。 线性规划的线性规划的解的四种可能情况解的四种可能情况：有唯一最优解；有无穷多最优解；有唯一最优解；有无穷多最优解

47、；有无界解；无可行解有无界解；无可行解基：基：系数矩阵系数矩阵A A的的m m阶非奇异子方阵阶非奇异子方阵基解：基解：令非基变量为令非基变量为0 0，求解由基变量构成的线性方，求解由基变量构成的线性方程组所得的解，该解与非基变量一起构成的约束方程程组所得的解，该解与非基变量一起构成的约束方程组的解组的解基可行解：基可行解：可行的基解，满足变量非负约束的基解。可行的基解，满足变量非负约束的基解。几个几个基本定理基本定理定理定理2.1若线性规划问题存在可行域，则可行域是凸集。若线性规划问题存在可行域，则可行域是凸集。定理定理2.2线性规划可行域线性规划可行域D中顶点的对应于中顶点的对应于LP的基可

48、行解。的基可行解。定理定理2.3若线性规划有最优解，则最优解一定可以在可行若线性规划有最优解，则最优解一定可以在可行域的顶点上得到。域的顶点上得到。 引理引理线性规划可行解线性规划可行解X（x1,x2,xn）为基可行解的充分）为基可行解的充分必要条件为必要条件为X的的正分量正分量对应的系数列向量对应的系数列向量线性无关线性无关。TmxxxX)0.0,0,.,(002001只考察基可行解。对于某一个基可行解，只需考察与其相邻的基可行解， 看是否比它们均优。（图示说明）设有基可行解TllmxxxxxX)0,.,0 , 0 ,., 0,.,(1111112111则它们是相邻的。)2(,.2 , 1,

49、 0) 1 (max11njxxaxczjnjjijnjjjb2.2.4 2.2.4 单纯形法的迭代原理单纯形法的迭代原理单纯形法的基本思想：单纯形法的基本思想：考察考察LPLP的基可行解，判断其是否的基可行解，判断其是否为最优解，若不是，则转到与其相邻的可使目标函数增为最优解，若不是，则转到与其相邻的可使目标函数增大的基可行解，直到找到最优解。大的基可行解，直到找到最优解。1.1.初始基可行解的确定初始基可行解的确定考察标准形的考察标准形的LPLP问题：问题：通常在方程（通常在方程（1 1）的系数）的系数矩阵矩阵A A中，总存在中，总存在1 1个单位个单位矩阵，不妨设为：矩阵，不妨设为：10

50、0010001).,(21mPPPB则则x1 1, ,x2 2,xm m为基变量，而为基变量，而xm+1,xm+2,xn为非基变量，令为非基变量，令非基变量非基变量0 0，则很容易得到一个基可行解：（，则很容易得到一个基可行解：（？）TmTnbbbxxxX)0.0 , 0 ,.,(),.,(21212.2.从一个基可行解转到相邻的另一个基可行解从一个基可行解转到相邻的另一个基可行解 按单纯形法的思想，找到一个基可行解后，进行检验，看按单纯形法的思想，找到一个基可行解后，进行检验，看它是否为最优解，用什么办法呢？就是将它和与其相邻的基可它是否为最优解，用什么办法呢？就是将它和与其相邻的基可行解比

51、较，为此须找到与它相邻的基可行解。行解比较，为此须找到与它相邻的基可行解。定义：定义：如果两个基可行解只有一个基变量不相同，则称这两个基如果两个基可行解只有一个基变量不相同，则称这两个基可行解相邻可行解相邻设已得到一个基可行解为设已得到一个基可行解为将其代入约束方程（将其代入约束方程（1），则得到：），则得到：TmxxxX)0.0 , 0 ,.,(002010) 3(10miiixPb因为因为P1,P2,Pm线性无关（？），则其它系数列向量线性无关（？），则其它系数列向量Pj可由它可由它们线性表示为们线性表示为:miiijjPaP1或写成：或写成：)4(01miiijjPaP将（将（4）两端同

52、时乘以）两端同时乘以0，则得到：，则得到：)5(0)(1miiijjPaP（3 3）+ +（5 5）整理后得到：）整理后得到：则得到了约束方程（则得到了约束方程（1）的另一个解。）的另一个解。取取则则X1的所有分量均的所有分量均0 0！这样！这样X1就是就是LPLP的一个的一个可行解可行解。j jTmjmjjaxaxaxX)0,.0 , 0.0 , 0 ,.,(02021011（6）系数矩阵为：）系数矩阵为：)6()(10bjmiiijiPPax)7(0|min00ljlijijiaxaax10000010100001000001, 1, 121mjjlljjljjaaaaaa容易看出，它是非

53、奇异的，所容易看出，它是非奇异的，所以以X1为基可行解。为基可行解。注意到注意到X0与与X1只有一个分量只有一个分量不同，则它们是不同，则它们是相邻相邻的基可的基可行解。行解。3.3.最优性检验和解的叛别最优性检验和解的叛别当当称为称为xj的检验数。的检验数。miiixcz100)8()()()(10110101miijijmimiijijiijmiijiiacczaccxccaxcz0)(1miijijacc时，就有时，就有01zz jjmiijijjzcacc1记记解的判别解的判别（1）若所有）若所有，则表明，则表明z0比各相邻的基可行解均优，则比各相邻的基可行解均优，则z0即为即为LP的

54、最优值，的最优值，X0即为即为LP的最优解。的最优解。0j（2）若所有）若所有，且有某个，且有某个j,同时可按同时可按规则找到规则找到00，则存在，则存在X1 1，也为最优解，且，也为最优解，且 而对于而对于X0 0和和X1的凸的凸组合组合X，有，有0j0j01zz 00010)1 ()1 (zzzXXCCXz即即X亦为亦为LP的最优解，此时的最优解，此时LP有有无穷多无穷多最优解最优解（3）若有）若有且且，则由，则由知，对任意的知，对任意的0，均有均有 , ,即即X1 1为可行解，而为可行解，而z1 1可以无限增大。可以无限增大。此此时，时，LP有有无界解无界解。0j0jPijiiaxx01

55、001ijiiaxx2 2）容易看出其一个基为：）容易看出其一个基为： 0,24261553. .002max43214213214321xxxxxxxxxxtsxxxxz4.单纯形法求解LP问题的步骤例2.10 求解LP问题0,24261553.2max21212121xxxxxxtsxxzStep1 确定初始基可行解，列初始单纯形表10260153A1001B则得到初始基可行解：则得到初始基可行解： 1）标准化TX)24,15, 0, 0(03 3）列初始单纯形表）列初始单纯形表 cj x1 x2 x3 x4 3 5 1 0 2 1 0 0 C B X B B-1b 0 x3 15 0 x

56、4 24 6 2 0 1 Step2检验检验 cj x1 x2 x3 x4 3 5 1 0 2 1 0 0 C B X B B-1b 0 x3 15 0 x4 24 6 2 0 1 j 2 1 0 0 1)计算计算检验数检验数jjmiijijjzcacc12)解的判别解的判别Step3基可行解的转换基可行解的转换1）入基变量的确定）入基变量的确定 2）出基变量的确定）出基变量的确定 5 4 6 ljlijijiaxaax000|min3）列新单纯形表）列新单纯形表 0 x3 2 x1 j 4 1 1/3 0 1/6 0 1 1/4 -1/8 1 x2 3/4 2 x1 15/4 1 0 -1/

57、12 5/24 j 0 0 -1/12 -7/24 3 0 4 1 -1/2 Step4重复重复step2-step3 0 1/3 0 -1/3 3 / 4 12 4 jjmiijijjzcacc1（1）若所有）若所有，X0即为即为LP的最优解。的最优解。0j（2）若所有）若所有，且有某个，且有某个j,同时可按同时可按规则找到规则找到00，0j0j此时此时LP有有无穷多无穷多最优解最优解（3）若有）若有且且，则，则LP有有无界解无界解。0j0jPStep3基可行解的转换基可行解的转换1）入基变量的确定）入基变量的确定2）出基变量的确定）出基变量的确定ljlijijiaxaax000|min3）

58、列新单纯形表）列新单纯形表Step4重复重复step2-step32.2单纯形法单纯形法【例例2.13】用单纯形法求解线性规划用单纯形法求解线性规划0,21024242max2121212121xxxxxxxxxxz解解将线性规划标准化，得将线性规划标准化，得0,21024200042max5432152142132154321xxxxxxxxxxxxxxxxxxxz容易看出，其初始基可行容易看出，其初始基可行解为：解为：TX)2 ,10, 4 , 0 , 0(02.2单纯形法单纯形法初始基单纯形表为：初始基单纯形表为： 2 4 0 0 0 2 5 4 4 0 -2 0 0 4 3 8 0 0

59、 0 -2 0 至此，所有非基变量的检验数均至此，所有非基变量的检验数均不大于不大于0，于是得到最优解为：，于是得到最优解为：TX)2/5 , 0 , 0 , 2/7 , 3(*20*z注意：注意：在最终单纯形表中，在最终单纯形表中，非基变量非基变量x3的检验数的检验数0，而，而它的系数列向量中有它的系数列向量中有00的系的系数，因此，迭代仍可继续。数，因此，迭代仍可继续。 0 14 10/30/3 0 0 0 -2 0 得到另一最优解得到另一最优解TX) , 0 , 0 , 3/10, 3/8 , 3/14(*120*1z2.2.4单纯形法的进一步讨论（大单纯形法的进一步讨论（大M法）法）【

60、例例2.14】用单纯形法求解线性规划用单纯形法求解线性规划) 1 (0,2314242max21212121xxxxxxxxz解解将线性规划标准化，得将线性规划标准化，得与前两例不同，本例中不存在明显的与前两例不同，本例中不存在明显的2阶单位子方阵，则初始基可行解的阶单位子方阵，则初始基可行解的确定成问题了！确定成问题了！0,2314242max432142132121xxxxxxxxxxxxz引入引入人工变量人工变量x50,0,构造辅助构造辅助LPLP问题问题)2(0,2314242max43215421321521xxxxxxxxxxxMxxxz这样初始基可行解就很容易确定了。这样初始基可