第一章线性规划与单纯形法

1、1第一章第一章线性规划与单纯形法线性规划与单纯形法2第一节第一节 线性规划问题及其数学模型线性规划问题及其数学模型1.1 问题的提出问题的提出例例1 某工厂在计划期内要安排某工厂在计划期内要安排、两种产品的生产，两种产品的生产，已知生产单位产品所需的设备台时及已知生产单位产品所需的设备台时及A、B两种原材料两种原材料的消耗以及资源的限制，如下表：的消耗以及资源的限制，如下表：问题：如何安排生产才能使工厂获利最多？问题：如何安排生产才能使工厂获利最多？ 资资源源限限制制 设设 备备 1 2 8 台台时时 原原料料 A 4 0 16 千千克克 原原料料 B 0 4 12 千千克克 单单位位产产品品

2、获获利利 2 元元 3 元元 3线性规划模型三个要素决策变量决策变量 目标函数目标函数约束条件约束条件4例例2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天天500万立方米，在两个工厂之间有一条流量为每天万立方米，在两个工厂之间有一条流量为每天200万立方米万立方米的支流。第一化工厂每天排放含有某种有害物质的工业污水的支流。第一化工厂每天排放含有某种有害物质的工业污水2万万立方米，第二化工厂每天排放这种工业污水立方米，第二化工厂每天排放这种工业污水1.4万立方米。从第一万立方米。从第一化工厂排出的工业污水流到第二化工厂以前，有化工厂

3、排出的工业污水流到第二化工厂以前，有20可自然净化。可自然净化。根据环保要求，河流中工业污水的含量应不大于根据环保要求，河流中工业污水的含量应不大于0.2。这两个工。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是本是1000元元/万立方米，第二化工厂处理工业污水的成本是万立方米，第二化工厂处理工业污水的成本是800元元/万立方米。现在要问在满足环保要求的条件下，每厂各应处理多万立方米。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。少工业污水，使这两个工厂总的处理工业污

4、水费用最小。工厂1工厂2500万立方米200万立方米5例3： 下料问题 某工厂要做某工厂要做100套钢架，每套有长套钢架，每套有长2.9米、米、2.1米和米和1.5米的圆钢组成，已知原料长米的圆钢组成，已知原料长7.4米，米，问应如何下料使需用的原材料最省。问应如何下料使需用的原材料最省。方案方案1 1方案方案2 2方案方案3 3方案方案4 4方案方案5 5方案方案6 6方案方案7 7方案方案8 82.92.9m m1 12 20 01 10 01 10 00 02.12.1m m0 00 02 22 21 11 13 30 01.51.5m m3 31 12 20 03 31 10 04 4

5、合计合计7.47.47.37.37.27.27.17.16.66.66.56.56.36.36.06.0剩余料头剩余料头0 00.10.10.20.20.30.30.80.80.90.91.11.11.41.46线性规划的一般模型线性规划的一般模型 0,),(),(),(. max(min)21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxat sxcxcxcz技术系数技术系数价值系价值系数数资源系数资源系数例例1 某工厂在计划期内要安排某工厂在计划期内要安排、两两种产品的生产，已知生产单位产品种产品的生产，已知生产单位

6、产品所需的设备台时及所需的设备台时及A、B两种原材料两种原材料的消耗以及资源的限制，如下表：的消耗以及资源的限制，如下表：问题：如何安排生产才能使工厂获问题：如何安排生产才能使工厂获利最多？利最多？7 资资源源限限制制 设设 备备 1 2 8 台台时时 原原料料 A 4 0 16 千千克克 原原料料 B 0 4 12 千千克克 单单位位产产品品获获利利 2 元元 3 元元 0,12416482.32max21212121xxxxxxtsxxz0,),(),(),(. max(min)21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxa

7、bxaxaxat sxcxcxcz价值系数技术系数资源系数34840 x2x1A1.2 线性规划的图解法0,12416482.32max21212121xxxxxxtsxxz1.画可行域2.画等值线3.找最优解步骤惟一最优解34840 x2x1AB0,12416482.42max21212121xxxxxxtsxxz无穷多最优解（多重最优解）34840 x2x1-2420,12416482.32max2121212121xxxxxxxxtsxxz无可行解x1x20240,242.max21212121xxxxxxtsxxz无界解无界解解的情况总结解的情况总结12有最优解有最优解无最优解无最优解

8、惟一最优解惟一最优解无穷多最优解无穷多最优解无可行解无可行解无界解无界解图解法的局限与启示图解法的局限与启示 局限局限：只能求解两个变量的线性规划问题只能求解两个变量的线性规划问题 启示启示: 通过图解法，能够直观的看到，如果线性规通过图解法，能够直观的看到，如果线性规划问题有最优解，一定能够在其顶点上达到最优。划问题有最优解，一定能够在其顶点上达到最优。131434840 x2x1A惟一最优解1534840 x2x1AB无穷多最优解（多重最优解）160,4150105.3max) 1 (212212121xxxxxxxtsxxz0,233.5 . 1min)2(21212121xxxxxxt

9、sxxz0,25 . 01.22max) 3(21212121xxxxxxtsxxz0,330.max)4(21212121xxxxxxtsxxz171.3 线性规划问题的标准形式我们规定的标准形式要求：我们规定的标准形式要求：w目标函数求极大值目标函数求极大值w所有约束为等式所有约束为等式w约束条件右端项都大于等于零约束条件右端项都大于等于零w所有变量都大于等于零所有变量都大于等于零 18练练 习习123123123123123min2372.325,0,zxxxxxxxxxstxxxx xx 无约束052222. .max121212121xxxxxxxtsxxz0,522327.332m

10、in765421542175421654215421xxxxxxxxxxxxxxxxxxxxtsxxxxz7 , 6 , 5 , 4 , 3 , 1; 0522222. .max743164315431431ixxxxxxxxxxxxxtsxxxzi191 12211 11221121 1222221 12212max.,0nnnnnnmmmnnmnzc xc xc xa xa xa xba xa xa xbsta xa xa xbx xx11jmax i=1,2,m.x0 j=1,2,nnjjjnijjijzc xa xbst1max.0 j=1,2,nnjjjjzCXP xstxbmax.

11、0zCXAXstXb一般形式简写形式向量形式矩阵形式201.4 线性规划问题解的概念可行解：满足所有约束条件的解，称为线性规划问题的可行：满足所有约束条件的解，称为线性规划问题的可行解。解。最优解：使目标函数值达到最优的可行解。：使目标函数值达到最优的可行解。基：设：设A是约束方程组的是约束方程组的mn维系数矩阵，其秩为维系数矩阵，其秩为m。B是矩是矩阵中阵中m阶非奇异子矩阵，则称阶非奇异子矩阵，则称B是线性规划问题的一个基。是线性规划问题的一个基。基变量：与基向量对应的变量。：与基向量对应的变量。非基变量：与非基向量对应的变量。：与非基向量对应的变量。基解：令非基变量为零，求解方程组：令非基

12、变量为零，求解方程组,得到一个基解。得到一个基解。基可行解：满足非负条件的基解。：满足非负条件的基解。可行基：对应于基可行解的基，为可行基。：对应于基可行解的基，为可行基。12341234282440(1,2,3,4)jxxxxxxxxxj21例题12341234282440(1,2,3,4)jxxxxxxxxxjTXB)0 , 0 , 2 , 6(,4211)1 (1TXB)0 ,12, 0 , 4(,1211)2(2TXB)512, 0 , 0 ,516(,1221)3(3TXB)0 ,536,54, 0(,1411)4(4TXB)736, 0 ,716, 0(,1421)5(5TXB)3

13、4,316, 0 , 0(,1121)6(6思考思考w非基变量取值是否为零？非基变量取值是否为零？w取值为零的变量是否一定为非基变量？取值为零的变量是否一定为非基变量？w大于零的变量是否是基变量？大于零的变量是否是基变量？w基变量的系数列向量是否一定线性无关？基变量的系数列向量是否一定线性无关？22解之间的关系解之间的关系23可行解基解非可行解基可行解例题例题249 , 2 , 1, 002226.9832763154321jxxxxxxxxxxxxxxtsjTTTXXX)0 , 0 , 0 , 0 , 0 , 0 ,27,47,43()0 , 0 , 0 , 0 , 3 , 0 , 2 ,

14、1 , 0()0 , 0 , 2 , 0 , 6 , 0 , 0 , 0 , 0()3()2()1(25第二节第二节 线性规划问题的几何意义线性规划问题的几何意义2.1 基本概念基本概念凸集凸集：设：设K是是n维欧式空间的一点集，若任意两维欧式空间的一点集，若任意两点的连线上的一切点都属于点的连线上的一切点都属于K；则称；则称K为凸集。为凸集。凸集凸集凸集凸集不是凸集不是凸集极点极点) 10()1 ()2()1(XXX26两点连线上的点的数学表示方法两点连线上的点的数学表示方法M1(x1)M(x)M2(x2)221xxxx121xxx01121MMMM(x,y)M2(x2,y2)M1(x1,y

15、1)yx0212:1MMM M222121,xxyyxxyy121211xxxyyy12121xxxyyy121MMM01212:1MMM M27282.2 几个定理几个定理例题例题299 , 2 , 1, 002226.9832763154321jxxxxxxxxxxxxxxtsjTTTXXX)0 , 0 , 0 , 0 , 0 , 0 ,27,47,43()0 , 0 , 0 , 0 , 3 , 0 , 2 , 1 , 0()0 , 0 , 2 , 0 , 6 , 0 , 0 , 0 , 0()3()2()1(30特殊情况特殊情况n有时目标函数可能在多个顶点处达到最大值有时目标函数可能在多

16、个顶点处达到最大值。这时在这些顶点的凸组合上也达到最大值。这时在这些顶点的凸组合上也达到最大值。称这种线性规划问题有无限多个（无穷多。称这种线性规划问题有无限多个（无穷多个）最优解。个）最优解。n若可行域无界，则可能无最优解，也可能有若可行域无界，则可能无最优解，也可能有最优解，若有也必定在某顶点上得到。最优解，若有也必定在某顶点上得到。31结论结论 线性规划问题的所有可行解构成的集合线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行点，线性规划问题的每个基可行解对应可行域的一个顶点；若线性规划问

17、题有最优解，域的一个顶点；若线性规划问题有最优解，必在某顶点上得到。必在某顶点上得到。33第三节第三节 单纯形法单纯形法 单纯形法的基本思路单纯形法的基本思路：根据问题的标准，从：根据问题的标准，从可行域中某个基可行解（一个顶点）开始，可行域中某个基可行解（一个顶点）开始，转换到另一个基可行解（顶点），并且使目转换到另一个基可行解（顶点），并且使目标函数值达到最优时，问题就得到了最优解。标函数值达到最优时，问题就得到了最优解。343.1 举例举例12121212max2328416.412,0zxxxxxstxx x12345123142512345max2300028416.412,0zxx

18、xxxxxxxxstxxx x x x x12,34512100,4001004001AP P P P P35312415282164124xxxxxxx12023zxx3154125122164134xxxxxxx153924zxx 10,3,2,16,0TX 0(0,0,8,16,12)TX52534531413248212)3(xxxxxxxxTX)0 , 8 , 0 , 3 , 2()2(5341213xxZ43243541812122124414)4(xxxxxxxx 34,2,0,0,4TX43812314xxZ(1)(2)36几何意义分析 12345678910123456x1+

19、2x2=84x2=124x1=16x2x1Q1Q2Q3Q437312415282164124xxxxxxx12023zxx 0(0,0,8,16,12)TX(1)25414234124144124)2(xxxxxxx422138)12, 0 , 4 , 0 , 4(xxZXT43541432212441481212)3(xxxxxxxx43812314)4 , 0 , 0 , 2 , 4(xxZXT38几何意义分析 12345678910123456x1+2x2=84x2=124x1=16x2x1Q1Q2Q3Q4无穷多最优解举例无穷多最优解举例3912123142512345max242841

20、6.412,0zxxxxxxxstxxx x x x x312415282(1)164124xxxxxxx12024zxx 0(0,0,8,16,12)TX324145214241(2)44124xxxxxxx(1)24(4,0,4,0,12)1842TXZxx43541432212441481212)3(xxxxxxxx(2)3(4,2,0,0,4)162TXZx251354351341(4)22842xxxxxxxx(3)3(2,3,0,8,0)162TXZx(2)(3)(1)0,1XXX无界解举例无界解举例40121231241234max24.2,0zxxxxxst xxxx x x

21、x3124124 2(1)2xxxxxx (0)12(0,0,4,2)TXZxx32412482(2)2xxxxxx (1)24(2,0,8,0)22TXZxx入基，由方程组可知， 可以无限增加，所以目标函数可以趋向于无穷大，此时为无界解。2x2x413.2 初始可行基的确定1.直接观察直接观察2.对所有约束条件是对所有约束条件是“”的不等式，可在每的不等式，可在每个不等式左端引入一个松弛变量，变成标准个不等式左端引入一个松弛变量，变成标准型，从而得到一个初始基可行解。型，从而得到一个初始基可行解。3.不存在单位阵时，采用人造基方法。不存在单位阵时，采用人造基方法。423.3 最优性检验与解的

22、判别（目标函数求极大）（目标函数求极大）w最优解判别定理：最优解判别定理： 若非基变量的系数（检验数）都小于等于零，则为若非基变量的系数（检验数）都小于等于零，则为最优解。最优解。w无穷多最优解判别准则：无穷多最优解判别准则： 若非基变量的检验数都小于等于零，且其中至少有若非基变量的检验数都小于等于零，且其中至少有一个为零，则线性规划问题有无穷多个最优解。一个为零，则线性规划问题有无穷多个最优解。w无界解（无最优解）判别定理：无界解（无最优解）判别定理： 对于一个基可行解，若有一个检验数大于零，且该对于一个基可行解，若有一个检验数大于零，且该检验数对应的所有系数都小于等于零，则该线性规检验数对

23、应的所有系数都小于等于零，则该线性规划问题具有无界解（无最优解）。划问题具有无界解（无最优解）。433.4 基变换（一个顶点变换到另一个顶点）w换入变量确定：一般选择绝对值最大的，但换入变量确定：一般选择绝对值最大的，但也可以任选或按最小号码选。也可以任选或按最小号码选。w换出变量确定：最小比值原则。其原理是保换出变量确定：最小比值原则。其原理是保证所有变量都为非负。证所有变量都为非负。443.5 迭代（旋转运算） 利用系数的增广矩阵进行初等变换来实现。利用系数的增广矩阵进行初等变换来实现。w将主元素变为将主元素变为1。w将入基变量所对应的列向量变为单位向量。将入基变量所对应的列向量变为单位向

24、量。1234512100 840010 1604001 12xxxxx b1234510101/2 2400101601001/4 3xxxxxb45第四节第四节 单纯形法的计算步骤单纯形法的计算步骤4.1 单纯形表若线性规划问题目标函数为：若线性规划问题目标函数为：约束条件为：约束条件为：1 122maxnnzc xc xc x11,111122,1122,110,1,2,mmnnmmnnmm mmmnnmjxaxa xbxaxa xbxaxa xbxjn增广矩阵为：mmnmmnmnmbbbaaaaaa212,22, 211, 110001000146根据增广矩阵设计计算表根据增广矩阵设计计

25、算表473.1 举例举例12121212max2328416.412,0zxxxxxstxx x12345123142512345max2300028416.412,0zxxxxxxxxxxstxxx x x x x12,34512100,4001004001AP P P P P484.2 计算步骤计算步骤49例题例题121211212min232.321,0zxxxxxstxxx x121231412512345zmax 232.321,0zzxxxxxxxstxxxx x x x x 令50单纯形法的求解步骤单纯形法的求解步骤w目标函数求极大目标函数求极大w初始可行基（单位阵）初始可行基（

26、单位阵）w解的判别解的判别w所有非基变量检验数都小于零小于零，得惟一最优解w所有非基变量检验数都小于等于零小于等于零，且至少有一个为零，得无穷多最优解。w如果有一个非基变量的检验数大于大于零，而其在方程组中的系数都小于等于零，为无界解。w迭代迭代w入基变量：检验数大于大于零w出基变量：最小比值原则方程组求解（矩阵初等行变换）方程组求解（矩阵初等行变换）w目标函数求极小目标函数求极小w初始可行基（单位阵）初始可行基（单位阵）w解的判别解的判别w所有非基变量检验数都大于零大于零，得惟一最优解w所有非基变量检验数都大于等于零大于等于零，且至少有一个为零，得无穷多最优解。w如果有一个非基变量的检验数小

27、于小于零，而其在方程组中的系数都小于等于零，为无界解。w迭代迭代w入基变量：检验数小于小于零w出基变量：最小比值原则方程组求解（矩阵初等行变换）方程组求解（矩阵初等行变换）5152例例812312312313123min3211423.21,0zxxxxxxxxxstxxx x x 123123412351312345min3211423.21,0zxxxxxxxxxxxstxxx x x x x 0,12324112.21321231153214321yyxxxyxxyxxxxxxxxts第五节第五节 单纯形法的进一步讨论单纯形法的进一步讨论531.大大M法法w在一个线性规划问题的约束条件中

28、加入人工在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数取值没有变量后，要求人工变量对目标函数取值没有影响，为此假定人工变量在目标函数中的系影响，为此假定人工变量在目标函数中的系数为（数为（-M）（）（M为任意大的数），为任意大的数），（若目标函数值为求最小值，则人工变量在目（若目标函数值为求最小值，则人工变量在目标函数中的系数为标函数中的系数为M）。）。w这样目标函数要实现最大化时，必须把人工这样目标函数要实现最大化时，必须把人工变量从基变量换出，否则目标函数不可能实变量从基变量换出，否则目标函数不可能实现最大化。现最大化。 54例例812312312313123min3

29、211423.21,0zxxxxxxxxxstxxx x x (4,1,9,0,0,0,0)2TXZ 123123412351312345min3211423.21,0zxxxxxxxxxxxstxxx x x x x 0,12324112.3min2132123115321432121321yyxxxyxxyxxxxxxxxtsMyMyxxxz原问题新问题552.两阶段法两阶段法w第一阶段：不考虑原问题是否存在基可行解，第一阶段：不考虑原问题是否存在基可行解，给原线性规划问题加入人工变量，并构造仅含给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数，要求其实现最小化。用人工变量的目标

30、函数，要求其实现最小化。用单纯形法求解此模型，若目标函数值等于零，单纯形法求解此模型，若目标函数值等于零，说明原问题有基可行解，可以进行第二阶段计说明原问题有基可行解，可以进行第二阶段计算，否则原问题无可行解，应停止计算。算，否则原问题无可行解，应停止计算。w第二阶段：将第一阶段得到的最终表，除去人工第二阶段：将第一阶段得到的最终表，除去人工变量，将目标函数行的系数，换原问题的目标函数变量，将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始表。系数，作为第二阶段计算的初始表。 实质是：第一阶段为原问题找出了一个基可行解。实质是：第一阶段为原问题找出了一个基可行解。56例例912312312313123min3211423.21,0zxxxxxxxxxs txxxxx 1231234123513123min3211423.21,0zxxxxxxxxxxxstxxx x x 0,12324112.min2132123115321432121yyxxxyxxyxxxxxxxxtsyyz第一阶段原问题1.6123123123123max2357.2510,0zxxxxxxstxxxx x x0,10527.532max43214321321321xxxxxxxxxxx