1、运筹学在军事上，史记：决胜千里之外,运筹帷幄之中.田忌赛马。运筹学：operational research在工程上，丁渭修皇宫。运筹学的主要内容线性规划线性规划数数学学规规划划非线性规划非线性规划整数规划整数规划动态规划动态规划学学科科内内容容多目标规划多目标规划双层规划双层规划组组合合优优化化最优计数问题最优计数问题网络优化网络优化排序问题排序问题统筹图统筹图随随机机优优化化对策论对策论排队论排队论库存论库存论决策分析决策分析可靠性分析可靠性分析线性规划及单纯形法n线性规划问题及其数学模型n图解法n单纯形法原理n数学试验第一节 线性规划问题及其数学模型一.问题的提出线性规划主要解决：如何利
2、用现有的资源，使得预期目标达到最优。例1 美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润最大？项目每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润（元）21表1-1解：设公司制造、两种家电分别为 件。,1x2x问题：可使得利润Z 最大？设备A的工时限制：1552x设备B的工时限制：242621 xx1?x 2?x 解：公司制造、两种家电分别为 件。,1x2x调试工序的时间限制：521 xx利润：212xxZ即要求：2
3、12maxxxZ项目每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润（元）21表1-1212maxxxZ目标函数objective function 约束条件资源约束非负约束其中,约束条件可记 s.t.(subject to),意思为“以为条件”“假定”、“满足”之意。0,524261552121212xxxxxxx212maxxxZ21212125156224.5,0 xxxstxxxx例2：捷运公司在下一年度的14月份的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于下表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合
4、同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租用期限不同的合同。试确定该公司签订租借合同的最优决策，目的是使所租借费用最少。月份 1 2 3 4所需仓库面积15 10 20 12表1-2表1-3合同租借期限 1个月 2个月 3个月 4个月合同期内的租费2800 4500 6000 7300单位：100m2单位；元/100m2解：设 表示捷运公司在第i(i=1,2,3,4)月初签订的租期为j (j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。ijx月份 1 2 3 4所需仓库面积15
5、 10 20 12表1-2表1-3合同租借期限 1个月 2个月 3个月 4个月合同期内的租费2800 4500 6000 7300单位：100m2单位；元/100m211x12x11x12x13x14x21x22x23x31x32x41x151020121514131211xxxx10232221141312xxxxxx1241322314xxxx20323123221413xxxxxx月份 1 2 3 4所需仓库面积15 10 20 1211x12x13x14x21x22x23x31x32x41x2800Z)(41312111xxxx4500)(322212xxx6000)(2313xx 7
6、300合同租借期限 1个月 2个月 3个月 4个月合同期内的租费2800 4500 6000 730014x经过上面的讨论，得到下面的LP模型：)4,1;4,1(012201015.4132231432312322141323222114131214131211jixxxxxxxxxxxxxxxxxxxxxstij)(4500)(2800min32221241312111xxxxxxxZ1423137300)(6000 xxx目标函数约束条件每一个问题都有一组变量称为决策变量，一般记为下面从数学的角度来归纳上述两个例子的共同点。每个问题中都有决策变量需满足的一组约束条件线性的等式或不等式。.,
7、21nxxx对决策变量每一组值：Tnxxx),()0()0(2)0(1代表了一种决策方案。通常要求决策变量取值非负，即).,2,1(,0nixi二.线性规划问题的数学模型 都有一个关于决策变量的线性函数称为目标函数。要求这个目标函数在满足约束条件下实现最大化或最小化。将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划。有时也将线性规划问题简记为LP（linear programming)其数学模型为：nnxcxcxcZ2211max(min)11 11221121 1222221 122(,)(,).(,)0,(1,2,)nnnnmmmnnmja xa xa xba xa xa
8、xbs taxaxaxbxjn 上述模型的简写形式为：njjjxcZ1max(min),2,1(0),2,1(),(.1njxmibxatsjnjijij若令);,(21ncccC;21nxxxX;21mbbbb),(21212222111211nmnmmnnPPPaaaaaaaaaACXZ max(min)0),(.1XbxPtsnjjj用向量表示时，上述模型可写为：若令);,(21ncccC;21nxxxX;21mbbbbnnxcxcxcZ2211max(min)11 11221121 1222221 122(,)(,).(,)0,(1,2,)nnnnmmmnnmja xa xa xba
9、xa xa xbs taxaxaxbxjn 11;jjjmjaaPa若令);,(21ncccC;21nxxxX;21mbbbbnnxcxcxcZ2211max(min)11 11221121 1222221 122(,)(,).(,)0,(1,2,)nnnnmmmnnmja xa xa xba xa xa xbs taxaxaxbxjn 111212122212nnmmmnaaaaaaAaaa线性规划问题的矩阵形式：CXZ max(min)0),(.XbAXts三.线性规划问题的标准形式：LP问题的数学模型的标准形式为：nnxcxcxcZ2211max11 11221121 1222221 1
10、22.0,(1,2,)nnnnmmmnnmja xa xa xba xa xa xbsta xaxaxbxjn其中常数项 ,0ib),2,1(miLP问题标准形式的特征是：求目标函数的最大值；约束条件为变量满足线性方程组与非负性两部分；方程组中常数项皆非负。下面分析如何将LP问题标准化：若目标函数为nnxcxcxcZ2211min引进新的目标函数,ZZ则Z的最小值即为Z的最大值ZZ maxmin从而目标函数变换为：nnxcxcxcZ2211max即：例1 将LP问题3212minxxxZ1231322.20(1,2,3)ixxxstxxxi化为标准形。解：引进新的目标函数,ZZ于是原LP问题化
11、为标准形式：1231322.20(1,2,3)ixxxstxxxi3212maxxxxZ 当约束条件中含有不等式时，如：例2 将LP问题12max33Zxx)2,1(0142102.2121ixxxxxtsi化为标准形。此时，对10221 xx引入变量,03x使得式变为：102321xxx同理对式14221 xx引入变量,04x使得式变为：142421xxx于是原LP问题化为标准形式：12max33Zxx)4,3,2,1(0142102.421321ixxxxxxxtsi引进变量x3,x4称为松弛变量。例3 将LP问题123max2Zxxx)3,2,1(062142.21321ixxxxxxt
12、si化为标准形。对 式引进变量同理对 式6221 xx引入变量,05x使得 式变为：62521xxx,04x使得 式变为：1424321xxxx引进变量x4,x5称为剩余变量。12345max200Zxxxxx 1234125214.260(1,2,5)ixxxxstxxxxi于是原LP问题化为标准形式：若约束条件中线性方程式的常数项为负数，则将该线性方程式两端乘以-1。如：例4 将LP问题1234max3Zxxxx)4,3,2,1(021.421321ixxxxxxxtsi化为标准形。例4 将LP问题1234max3Zxxxx)4,3,2,1(021.421321ixxxxxxxtsi化为标
13、准形。解：将式 两边乘以-1得此LP问题的标准形式：1234max3Zxxxx)4,3,2,1(021.421321ixxxxxxxtsi 若变量lx无约束，则引进两个非负变量,0lx0 lx将lx表示为：lllxxx 例5 将LP问题12max2Zxx)4,3,2(0622.421321ixxxxxxxtsi化为标准形。例5 将LP问题12max2Zxx)4,3,2(0622.421321ixxxxxxxtsi化为标准形。解：111xxx 将上式代入目标函数及约束条件中，得到其标准形式：112max22Zxxx )4,3,2(0,0,0622.1142113211ixxxxxxxxxxxts
14、i例6 将LP问题12max3Zxx)2,1(016.2121ixxxxxtsi化为标准形。解：由于（2）式常数项为负，不等式两边乘以-1得)2,1(016.2121ixxxxxtsi12max3Zxx)2,1(016.2121ixxxxxtsi12max3Zxx解：引进松弛变量：,03x04x此LP问题的标准形为：12max3Zxx)4,3,2,1(016.421321ixxxxxxxtsi第二节 图 解 法一.预备知识：1.平面上一条直线可把平面分成三部分：平面上的点，直线一侧的点，直线另一侧的点。yx055例：5:21 xxl用集合表示：,5|),(212121Rxxxxxxl521 x
15、x2.二元一次不等式的解集代表一个平面域。例：521 xx代表：121255xxxx3.梯度：定义：设二元函数 若在点 的偏导数存在，则称向量：),(21xxfz,)(10 xXf20)(xXf)(,)(2010 xXfxXf为),(21xxfz 在点 处的梯度。记),()0(2)0(10 xxX),()0(2)0(10 xxX)(,)()(20100 xXfxXfXf其几何意义是：二元函数),(21xxfz 在某点),()0(2)0(10 xxX 沿梯度正向为增加最快的方向。例：函数yxz32 在原点 处的梯度为,202xz330yz0 xy23)3,2(二.两个变量LP问题的图解法图解法步
16、骤：根据约束条件画出可行域。根据目标函数Z的表达式画出目标直线Z=0,并表明目标函数增加的方向。在可行域中，找符合要求的距离目标直线Z=0的最远或最近点，并求出该点坐标。(0,0)例1 解LP问题：12max3Zxx2,10682.121ixxxxtsi 画出可行域。8221 xx61x1x2x4860 令Z=0,有2130 xx 在原点的梯度：123Zxx13,xZ 21xZ 所以(3,1)Z)3,1(123xx)3,1(123xx画出直线解：例1 解LP问题：12max3Zxx2,10682.121ixxxxtsi在原点的梯度：123Zxx13,xZ 21xZ 所以(3,1)Z解：8221
17、 xx61x1x2x48603)3,1()3,1(1123xx31例1 解LP问题：12max3Zxx2,10682.121ixxxxtsi解：8221 xx61x1x2x486031)3,1()3,1(随着直线 1123xx123xx沿梯度方向去扫可行域，123Zxx目标函数中的Z在增加。如：经过点)1,1(时，4.Z 例1 解LP问题：12max3Zxx2,10682.121ixxxxtsi解：8221 xx61x1x2x486031)3,1()3,1(1123xx 随着直线 123xx沿梯度方向去扫可行域，123Zxx目标函数中的Z在增加。如：经过点)1,1(时，4.Z 例1 解LP问题
18、：12max3Zxx2,10682.121ixxxxtsi解：8221 xx61x1x486031)3,1()3,1(1)1,6(由此可见，当目标函数沿梯度的方向去扫可行域时，在顶点)1,6(处取得最大值。从而得最优解：1621xx目标函数的最优值为：max3 6 119.Z 例2 解LP问题：12minZxx121.0(1,2)ixxstxi解：画出可行域。令Z=0,有210 xx 画出直线12xx 在原点的梯度：12Zxx11,xZ 21xZ 所以(1,1)Z1x2x0121 xx112xx)1,1(1例2 解LP问题：12minZxx)2,1(01.21ixxxtsi解：1x2x0121
19、 xx1112xx)1,1(随着直线 12xx 沿梯度反方向去扫可行域，12Zxx目标函数中的Z在减小。且在点)1,0()1,0(处取得最小值。从而得最优解：1021xx目标函数的最优值为：max02 12.Z 例3 解LP问题：12maxZxx 1224.0(1,2)ixxstxi解：1x2x0 画出可行域。令Z=0,有210 xx 画出直线12xx 在原点的梯度：12Zxx 11,xZ 21xZ 所以(1,1)Z12xx 4221 xx)2,8(48)1,1(例3 解LP问题：12maxZxx)2,1(042.21ixxxtsi解：1x012xx 4221 xx)2,8(482x)1,1(
20、123xx沿梯度方向去扫可行域，123Zxx目标函数在点 先把目标直线Z=0平行地拉到可行域内，再让直线)0,4(处取得最大值。从而得最优解：0421xx目标函数的最优值为：max404.Z 例4 解LP问题：12min24Zxx 解：12120.201,2ixxs txxxi 画出可行域。令Z=0,有21420 xx 画出直线122xx 在原点的梯度：1224Zxx 12,xZ 24xZ 所以(2,4)Z1x2x012xx 221 xx22122xx)4,2(BA仅为AB线段。1x2x012xx 221 xx22122xx)4,2(BA例4 解LP问题：12min24Zxx 解：12120.
21、201,2ixxs txxxi 由于目标函数是减小，故应沿梯度反方向去扫可行域，先把目标直线拉到上面。例4 解LP问题：12min24Zxx 解：2,1020.2121ixxxxxtsi1x2x012xx 221 xx22122xx)4,2(BA 随着直线 122xx 1224Zxx 目标函数中的Z在减小。且在点处取得最小值。从而得最优解：1121xx沿梯度反方向去扫可行域，A目标函数的最优值为：min2 14 12.Z 例5 解LP问题：12max2Zxx解：)2,1(02462.2121ixxxxxtsi 画出可行域。令Z=0,有,2021xx 画出直线在原点的梯度：122Zxx11,xZ
22、 22.xZ 所以(1,2)Z1x2x06221 xx41x22x2120 xx 2120 xx)2,1(s1x2x06221 xx41x22x2120 xx)2,1(s例5 解LP问题：12max2Zxx解：)2,1(02462.2121ixxxxxtsi 随着直线 沿梯度方向去扫可行域，122Zxx目标函数中的Z在增加。直到与直线2120 xx 6221 xx重合。DC此时，线段CD上的所有点均是最优解。其中，点C的坐标为：),1,4(点D的坐标为：).2,2(例5 解LP问题：212maxxxs解：过)2,1(02462.2121ixxxxxtsi1x2x06221 xx41x22x21
23、20 xx)2,1(sDC)2,2(),1,4(DC的直线方程为：32112xx)42(1 x6221 xx例6 解LP问题：12maxZxx12236.0(1,2)ixxstxi解：画出可行域。1x2x063221 xx 令Z=0,有,021xx 画出直线12xx 在原点的梯度：12Zxx11,xZ 21.xZ 所以(1,1)Z)1,1(s 随着直线 沿梯度方向去扫可行域，12Zxx目标函数中的Z一直在增加。所以，此LP问题无最优解。12xx 12xx 为无界域。例7 解LP问题：12min3Zxx12121.101,2ixxs txxxi 01x2x121xx121 xx111解：画出可行
24、域。由于可行域为空集，所以此LP问题无可行解，当然无最优解。通过以上的讨论，LP问题的解有下面四种类型：有最优解且有唯一的最优解。有可行解且有无穷多最优解。有可行解但无最优解。(4)无可行解补充知识：凸集凸集：在点集中任取两点，则其连线仍在其中。即没有凹入的部分；没有空洞。在凸集中，点A，B，C，D称为极点（或顶点）。ABCD从图解法中我们了解到以下事实：若LP问题的可行域存在，则可行域一定是凸集。若LP问题的最优解存在，则最优解或最优解之一（如果有无穷多最优解的话）一定是可行域凸集的某个顶点。思路：最优解先在可行域中找。（可行域为空集，则无可行解，故无最优解。）最优解在可行域的顶点中找。顶点
25、是有限个，若两个顶点都是最优解，则两个顶点所连线段上的所有点均是最优解）定义：LP问题的可行域的顶点称为基本可行解。可行解可行域中的点基本可行解可行域中的顶点最优解1.3 单纯形法 原 理1.复习：非齐次线性方程组解例：解非齐次线性方程组5242615552142132xxxxxxxx增广矩阵（1）51001124010261500150A1x2x3x4x5xb为基变量。称,3x,4x5x基变量个数=3)()(ArAr51001124010261500150A1x2x3x4x5xb此方程组的解为2152142352624515xxxxxxxx51001124010261500150A1x2x3
26、x4x5xb其中,1x2x为任意实数。为非基变量，或自由变量。2x,1x称称非基变量,1x2x为0的解 叫基解。TX)5,24,15,0,0(0若对（1）式中的变量再加上非负限制2152142352624515xxxxxxxx(0,0,15,24,5)04531x2x3241251212155024620500,0 xxxxxxxxxx05152 x50521xx0262421xx从而,1x2x解域为注意：此时的,1x2x已经不是任意实数。不是自由变量了。而对于带有非负约束的方程组1Q2Q3Q4Q解的每个分量都是非负数，就叫做可行解。如果基解是可行的，就叫基可行解。基可行解所对应的基称为可行基
27、。2152142352624515xxxxxxxxTX)5,24,15,0,0(0基解：345,xxx是可行基。解的每个分量都是非负数，就叫做可行解。如果基解是可行的，就叫基可行解。基可行解所对应的基称为可行基。基可行 最优基基 非 可 行 基基可行基非可行基基与解的对应关系：非可行解可行 基本解 可行解 基本解解与解之间的关系为：基解基可行基基可行解最优基基最优解5,100502624051521521423ixxxxxxxxxi,11x22x所对应的解例如T)2,14,10,2,1(是可行解。,01x02x所对应的解T)5,24,15,0,0(是基解。也是可行解，故而是基本可行解。3241
28、25121552462501,5ixxxxxxxxxi14,x 21x 所对应的解例如(4,1,10,2,0)T是非可行解。2152142352624515xxxxxxxx345,xxx是可行基。但并不是所有基都有资格充当可行基。例如51001124010261500150A（-6）51001166104015001505100116610401500150524235216465155xxxxxxxx所对应的方程组为：令非基变量,2x5x为0，得到基解：T)0,6,15,0,5(非可行解。即,431xxx非可行基。基可行解很重要，可以证明以下定理：定理1 若线性规划问题存在最优解，则问题的可
29、行域是凸集。定理2 线性规划问题的基可行解对应线性规划问题可行域（凸集）的顶点。定理3 若线性规划问题最优解存在，则最优解一定在可行域顶点处取得。由此可看出，最优解要在基可行解（可行域顶点）中找。通过以上分析，可得到以下几个结论：（1）线性规划问题的可行域是一个凸集，可行域可能有界，也可能无界，但其顶点数是有限个。（？）（2）线性规划问题每个基本可行解对应于可行域的一个顶点。（3）若线性规划问题有最优解，则必可在其可行域的某个（或多个）顶点上达到最优值。如何从一个可行基找另一个可行基？称基变换。定义：两个基可行解称为相邻的，如果它们之间仅变换一个基变量。对应的基称为相邻可行基。例 LP问题5,
30、105242615552142132ixxxxxxxxxi543210002maxxxxxxZ当前可行基 所对应的基本可行解TX)5,24,15,0,0(0显然不是最优。因为从经济意义上讲，,01x02x意味着该厂不安排生产，因此没有利润。(对应可行域的 )0,0(o345,xxx相应地，将 代入目标函数得0)(0XZ0X若让非基变量 取值从零增加，12,x x04531x2x05152 x50521xx0262421xxo1Q2Q3Q4Q相应的目标函数值Z也将随之增加。因此有可能找到一个新的基本可行解，使其目标函数值有所改善。即进行基变换，换一个与它相邻的基。再注意到 前的系数5比 前的系数
31、2大，即 每增加一个单位对Z的贡献比 大。2x1x2x1x故应让 从非基变量转为基变量，称为进基。又因为基1x变量只能有三个，因此必须从原有的基变量,3x,4x5x中选一个离开基转为非基变量，称为出基。谁出基？123452000Zxxxxx又因为 仍留作非基变量，故仍有2x02x（2）式变为05062401515143xxxxx再让 从零增加，能取得的最大值为1x6241x51x.45,624min1x此时，已经从24降到了0，达到了非基的取值，变成非基变量。从而得到新的可行基 。4x,531xxx将（2）式5,105262451521521423ixxxxxxxxxi（2）可行基,531xx
32、x留在左边，非基变量,2x4x移到右边5,105224651525142123ixxxxxxxxxi（3）5,105224651525142123ixxxxxxxxxi（3）用代入法的：5,10613216131451542542123ixxxxxxxxxi用代入法的：由此得到一个新的基本可行解：TX)1,0,15,0,4(1TX)1,0,15,0,4(1目标函数值：.0)(842)(01XZXZ从目标函数值明显看出，比 明显地得到了改 善。0X1X)0,4(1Q此基本可行解对应可行域的04531x2x05152 x50521xx0262421xxo1Q2Q3Q4Q代入目标函数得：423131
33、8xxZ这一过程用增广矩阵的行初等变换表示为：00001251001124010261500150A2x4x3x5x1xb1/6000012510011406/103/111500150（-1）（-2）按最小比值规则：415,624,min543210002xxxxxZ主元素803/103/10116/103/20406/103/1115001502x4x3x5x1xb目标函数系数行4231318xxZ按最小比值规则：233/21,3/14,515min803/103/10116/103/20406/103/1115001502x4x3x5x1xb3/2803/103/102/32/34/10
34、10406/103/111500150（-5）（-1/3）（-1/3）2/172/14/10002/32/34/10102/72/14/10012/152/154/5100所对应的 LP问题5,1023234127214121521554542541543ixxxxxxxxxxi542141217maxxxZ5,1023234127214121521554542541543ixxxxxxxxxxi542141217maxxxZ可行基123,xxx令非基变量 为0，得到最优解27 3 15(,0,0)2 2 2TX,4x5x最优值217maxZ此基本可行解对应可行域的2(7/2,3/2)Q其结果
35、与图解法一致。04531x2x05152 x50521xx0262421xxo1Q2Q3Q4Q总结：在迭代过程中要保持常数列向量非负，这能保证基可行解的非负性。最小比值也是为了保证解的非负性。主元素不能为0。因为行的初等变换不能把0变成1。主元素不能为负数。因为用行的初等变换把负数变成1会把常数列中对应的常数变成负数。5,105262451521521423ixxxxxxxxxi练习：LP问题12121228416.4120,0 xxxstxxx12max23Zxx标准化最优解：*(4,2,0,0,4)TX 目标函数值：*14z 2 1 0 0 0 基0 150 240 5 0 5 1 0 0
36、 6 2 0 1 0 1 1 0 0 1 2 1 0 0 0表 1-7 P/29jcBCb1x2x3x4x5x3x4x5xjjzc 2 1 0 0 0 基0 152 40 1 0 5 1 0 0 1 2/6 0 1/6 0 0 4/6 0 -1/6 1 0 1/3 0 -1/3 0表 1-8 P/30jcBCb1x2x3x5x3x4x5xjjzc 1x 2 1 0 0 0 基0 15/22 7/21 3/2 0 0 1 5/4 -15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2 0 0 0 -1/3 -1/2表 1-9 P/30jcBCb1x2x3x2x3x4x5xjjzc
37、 1x54321002maxxxxxxZ12341235221.60(1,2,3,4,5)ixxxxstxxxxxi例2 解LP问题：对单纯形矩阵作初等行变换，有：000121610111101221T按最小比值原则：116,11min确定主元素。（-1）（-1）3.无穷多个解情况：101100511330101221至此，检验行已没有正数，当前解即为最优解。此时对应的LP问题为：12345max0001Zxxxxx123412345221.03350(1,2,3,4,5)ixxxxstxxxxxxi0101100511330101221此时对应的LP问题为：12345max0001Zxxxx
38、x123412345221.03350(1,2,3,4,5)ixxxxstxxxxxxi0TX)5,0,0,0,1(11Z 101100511330101221此时对应的LP问题为：12345max0001Zxxxxx123412345221.03350(1,2,3,4,5)ixxxxstxxxxxxi01TX)2,0,0,1,3(21Z 当0043xx时，不管 取何值，均有目标函数取得最大值1。此时约束方程为：53125221xxxx其中 为基变量。,1x5x2x123412345221.03350(1,2,3,4,5)ixxxxstxxxxxxi53125221xxxx其中 为基变量。,1
39、x5x25213521xxxx用非基变量表示出基变量：其中，为自由变量。设为 有:2x,2cx cxcx352151其中c是满足非负性的任意常数。再由,1x5x的非负性，知：0350021521cxcxcx解出350 c（其中 ）350 cTccc)35,0,0,12(最优解为：最优值为：.1maxZcxcx352151另解：101100511330101221A2x4x3x5x1xb当前最优基变量 对应最优解为：,1x5xTX)5,0,0,0,1(1再强行让检验数为0的 进基，再找一个最优解：2x 1011003/53/13/11101012211011003/53/13/11103/133
40、/23/1001101100511330101221A2x4x3x5x1xb3535,min确定主元素。1/3按最小比值原则：2TX)0,0,0,3/5,3/13(2以 与 的连线段：1X2X21)1(XX10即TX)55,0,0,35,3101(10为全部解的一般形式。TX)5,0,0,0,1(12X1011003/53/13/11103/133/23/1001TX)55,0,0,35,3101(10为全部解的一般形式。若令：c35有TcccX)35,0,0,12(350 c（其中 ）350 cTccc)35,0,0,12(LP当前解已是最优的四大特征：存在一组(初始)可行基（其系数矩阵为单
41、位阵）。检验行的基变量系数=0。检验行的非基变量系数0。全部 唯一解。存在 无穷多个解。常数列向量0。下面的问题是：所给LP的标准型中约束矩阵中没有现成的可行基怎么办？00 人工变量法（也称大M法）针对标准形约束条件的系数矩阵中不含单位矩阵的处理方法。例6 用单纯形法求解LP问题313maxxxZ0,9312432132321321xxxxxxxxxxx第五节 单纯形的进一步讨论313maxxxZ12312323123421.39,0 xxxxxxstxxxxx543210003maxxxxxxZ123412352315421.390 xxxxxxxxstxxx解：先将其化为标准形式54321
42、0003maxxxxxxZ093124513253214321xxxxxxxxxxx再强行加上人工变量，使其出现单位矩阵：12341235623715421390 xxxxxxxxxxxxx但这样处理后：不易接受。因为 是强行引进，称为 76,xx人工变量。它们与 不一样。称为松弛变量和剩54,xx54,xx余变量，是为了将不等式改写为等式而引进的，而改写前后两个约束是等价的。人工变量的引入一般来说是前后不等价的。只有当最优解中，人工变量都取值零时（此时人工变量实质上就不存在了）才可认为它们是等价的。处理办法：把人工变量从基变量中赶出来使其变为非基变量。为此，发明者建议把目标函数作如下处理：7
43、6543210003maxMxMxxxxxxZ12341235623715421390 xxxxxxxxxxxxx其中M为任意大的实数，“-M”称为“罚因子”。用意：只要人工变量取值大于零，目标函数就不可能实现最优。对此单纯形矩阵作初等行变换，有：76543210003maxMxMxxxxxxZ12341235623715421390 xxxxxxxxxxxxx000103910001301011011240001111MMTMM111100042110110103100019234100010MMMM（-1）（-3）（-4M）302111032110110160403316630410340
44、6MMMMM1/63021110321101101102/301/21/21/616304103406MMMMM（-6M-3）2（-3）34/32/32/3030016/12/12/103/20133/10003/11002/12/12/11000MM3/234/32/32/3030014/14/34/30102/333/10003/11002/12/12/11000MM（-1/3）（-3）2/34/14/34/30002/92/34/14/34/30102/32/54/14/14/10012/102/12/12/11000MM2/34/14/34/30002/92/34/14/34/3010
45、2/32/54/14/14/10012/102/12/12/11000MM至此，检验行已没有正数，当前解即为最优解。TX)0,0,23,25,0(0最优值为：.23maxZ去掉人工变量 ，即得原LP问题的最优解：76,xx例7/P34 求解LP问题212maxxxZ1212122.226,0 xxstxxx x解：从上面已看出，此LP问题无解。下面用大M法求解看一下会出现什么情况。引进人工变量，上述问题化为：例7/P34 求解LP问题212maxxxZ1212122.226,0 xxstxxx x54321002maxMxxxxxZ06222415421321xxxxxxxx54321002m
46、axMxxxxxZ06222415421321xxxxxxxx对单纯形矩阵作初等行变换，有：00012611022200111MTMMMMM6002122611022200111（-2）（-2-2M）MMM24022102112002001112x4x3x5x1x至此，检验行已没有正数，当前解即为最优解。但此时基变量为：2251xx含非零的人工变量52x 矛盾。说明原问题无可行解。使用大M法小结：对LP问题njjjxcZ1max),2,1(0.1njxbxPtsjnjjj式中.),(,021TmjjjjaaaPb则在每个约束方程左边加上一个人工变量).,2,1(mixin（1.1）0,0112
47、211222222121111212111mnmnmmnnmnmmnnnnnnxxxbxxaxaxabxxaxaxabxxaxaxa（1.2）式（1.2）中含有一个m阶单位阵。以mnnnxxx,21为基变量。得到一个初始基本可行解：TmbbX),0,0(10我们可以从 出发进行迭代。0X（1.3)当以式（1.2）为约束的线性规划问题的最优解中，人工变量都处在非基变量位置（即取零值），则原问题有最优解，且将最优解中去掉人工变量部分即为式(1.1)最优解。当（1.2）问题的最优解中包含非零的人工变量时，且人工变量的值不为零，则原问题无可行解。当（1.2）问题最优解的基变量中包含人工变量，但该人工变
48、量取值为零，这时可将某个非基变量引入基变量中，来替换该人工变量。从而得到原问题的最优解。从式（1.3）的 做初始基本可行基解进行迭代时，目标是尽快把人工变量从基变量中全部“赶”出去（如果能全部“赶”出去的话）。所用方法除了大M法外，还有下面的两阶段法。0X3.两阶段法用大M法处理人工变量时，若用计算机处理，必须对M给出一个较大的具体数据，并视具体情况对M值作适当的调整。为了克服这一麻烦，下面的两阶段法将问题拆成两个LP问题分两个阶段来计算：第一阶段求解第一个线性规划：miinx1min0,0112211222222121111212111mnmnmmnnmnmmnnnnnnxxxbxxaxax
49、abxxaxaxabxxaxaxa 若求得的单纯形矩阵中，所有人工变量都处在非基变量的位置。即 及 。则从第1阶段去掉人工变量后，即为原问题的初始单纯形矩阵。0(1,2,)n ixim0*若第1阶段所求得的单纯形中仍含有（解）非零的人工变量，则说明原问题无可行解。不再进入第2阶段。进入第2阶段。因此两阶段法的第1阶段求解有两个目的：一为判断原问题有无可行解。二，若有，则得原问题的一个初始可行基，再对原问题进行第2阶段的计算。下面对例6用两阶段法求解：第1阶段的线性规划问题可写为：09312451732653214321xxxxxxxxxxxxx76minxx 先对目标函数标准化：令 有 76m
50、axxx 对单纯形矩阵作初等行变换，有：09312451732653214321xxxxxxxxxxxxx76maxxx 01100000910001301011011240001111T110101129100013010110112400011111000100429100013010110112400011111x2x3x4x5x6x7x1x2x3x4x5x6x7x100100429100130101011240011111x2x3x4x5x7x6030406613040610101123011203（-3）（-4）6304066304061101123112031/6（-1）63040
