.30.第1章线性规划及单纯形法-4+++4s.t.2+-3-xs =13x2+13=9,≥0 (j=1,,5)写出其约束系数矩阵，见（1.29）P1P2P3P4Ps07111110-21-1(1.29)010031因式（1.29）中不存在单位矩阵，如果从中确定一个基，则需要通过求解联立方程组才能找出一个基解，还不一定是基可行解，此外，即使找出了基可行解，但由于基不是单位矩阵，使建立初始单纯形表仍会碰到困难为此在式（1.29）中人为地添加两列单位向量P6、P7，见式（1.30）.P,P2P3P4PsP6P70F111100-0(1.30)-21-10-11001-L0310线性规划（1.28）的约束条件可相应表为：=4X++2+t+a4=1-2+2--xs+16+=9322+r3≥0(j=1, , 7)因P6、P是人为添加的，其对应变量6、α被称为人工变量。约束条件中添加人工变量后，目标函数应如何处理？由于第三个约束条件3x2+±3=9在添加人工变量前已经是等式，第二个约束在减去剩余变量5后变为一21+r2x3-15=1，也是等式．对任何可行解，这些等式约束必须满足，因此在最优解中人工变量取值必须为零。为此，令日标函数中人工变量的系数为足够大的一个负值，用“一M”代表，只要当人工变量的取值不为零，目标函数就不可能极大化，对剩余变量，因实质上也是松弛变量，因此目标函数中的系数也为0.这样化为标准形式后例6的目标函数为max2=-3x1+x3+0z4+0xs-Mr6-Mr7从约束条件的系数矩阵中看到，P4、P6、P，都是单位向量，可以此作为基确定初始基可行解，在用单纯形法求解时，M可着作一个代数符号一起参加运算.用添加M来处理人.T变量的方法称为大M法：本例在添加符号M后
85单纯形法的进一步讨论31用单纯形法求解的过程见表1一7表1-730100-M-M5Ch基b13312224T516t7110041100140101-2[1]-1-1-M3609031001- M370010-M-2M-34Mc,-z,211030-103C400110-2-1-11x23104036[6]-M370004M+13M-4M6M-3c, - z,1-1/2000~1/21/200a4001/3011/3003x200-1/21/61[2/3]1n1-33100033-M-3/2-M + 1 /2c,-%0011n-120-120024001/41/41-1/405/2-12321/40103/43/43/213/2a30003/4-M+3/4-M-1/43/2c, - z,用大M法处理人工变量，用手工计算求解时不会碰到麻烦.但用电子计算机求解时，对M就只能在计算机内输人一个机器最大字长的数字，如果线性规划问题中的a、b,或c，等参数值与这个代表M的数相对比较接近，或远远小子这个数字，由子计算机计算时取值上的误差，有可能使计算结果发生错误，为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法，两阶段法5-2两阶段法的第一阶段是先求解一个目标函数中只包含人工变量的线性规划间题，即令目标函数中其他变量的系数取零，人工变量的系数取某个正的常数（一般取1），在保持原问题约束条件不变的情况下求这个目标函数极小化时的解，显然在第一阶段中，当人工变量取值为0时，目标函数值也为0.这时候
32第1章线性规划及单纯形法的最优解就是原线性规划问题的一个可行解，如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有人匕变量，表明原线性规划问题无可行解，当第一阶段求解结果表明问题有可行解时，第二阶段是从第-阶段的最终单纯形表出发，去掉人工变量，并按问题原来的目标函数，继续寻找问题的最优解.例6用两阶段法求解时，第一阶段的线性规划问题可与为：minw=6+x7=4ri+t2+x3+r4s.t.=1-2x1+2"x3-Ts+a63x2+3+r7=9(j=1,.，7)a,≥0用单纯形法求解的过程见表1-8.表1~800000-1c-+1Ca6基x1t2t3XA16x7as01111000414[1]0101-2-1-1-11690310001-121000-240-1c,~z,0302110143-110100-2-1-11x26[6]04031~3-137604030-4c, -.2,010000~1h1/2~1/2x403000011/31/33200112/3121/60at1/200000-1-1c,72,第二阶段是将表1-8中的人工变量6、7除去，目标函数改为：max2=-3x,+0r2+x3+0x4+0rs再从表1一8中的最后一个表出发，继续用单纯形法计算，求解过程见表1~9
85单纯形法的进一步讨论33表1-95--30100CB基b31x2T3T4.ts000001-1/22403011/30022-310[2/3]011/2Z100303/2C, -21000001- 1/2340005./21-1/2- 1/4201013/23/23/4x3000-3/2 3/4c,%关于解的刺别5-3本章第三节中关于最优性检验部分已讲了如何判别存在无穷多最优解和出现无界解的情况.本节中又讲了当线性规划问题中添加了人工变量，问题满足最优性条件时基变量仍含有人工变量，表明问题无可行解.下面对图解法中已求解过的几个例子，再用单纯形法计算，对比一下各种解在单纯形表中的出现形式，[例7]用单纯形法求解线性规划问题max=3r1+3x2[21+2x212s.t.八164315x2≤15x1,2=0【解】先将其化成标准形式maxz=3x1+312+0r3+0x4+0xs= 12[2x1 +2x2+t3s.t.= 164x1+14542+#5=15[x,≥0 (j=1, ,5)用单纯形法求解时得最终单纯形表见表1一10由于表中非基变量又5的检验数为0，若将其作为换人变量继续选代，得表1-11.从表1-10和表1-11中分别得到两个最优解：x=（3，3，0，4，0），X2=（4，2，0，0，5），其月标函数值相等均为*=18，这两个点连线上的
34第1章线性规划及单纯形法点目标函数值也相等，说明问题有无穷多最优解。但需要说明当所有c，，≤0，某一非基变量检验数,=0，存在无穷多最优解的条件是P列向量中至少存在一个元素a,>0，且能找出另一最优解，表1-10基bCar112T413as331001/ai 1/504001-24/5443301001/5t20000-3/2C, = 2,表1-11基bCxx3x4xs320034101/4105001-5/25/4ts201031/21/42000-3/20c,~z,[例8]用单纯形法求解线性规划间题max 2=2x1+3r2s.t. [4ri≤161,2≥0【解】图解法求解时已看到本例具有无界解，用单纯形法求解时，先将表 1 - 12其化为标准形式230max±=2xi+3x2+0r3c-基Cab[4x]+x3=16112T3s.t.00164113(,2,≥0302c, - z,用单纯形法计算过程见表1一12.表中2>0，但2列数字为0，即x2的取值可无限增大而不受限制、由此目标函数值也可无限增大，说明间题的解无界，[例9]用单纯形法求解线性规划问题maxz=2ai+3x2S.t.[21+2x2121+2x2=141x1,x20