（3）若存在取值无约束的变量x，则可令x=x-x，其中，x，x≥0。例：将如下问题转化为标准形式：min z = Xj + 2x22x, +3x, ≤6X +x, ≥4X - X2 =3x≥0,x,无约束解：首先，用x-x替换x2，其中，x,x≥0；其次，在第一个约束条件的左端加上非负的松弛变量xs；再次，在第二个约束条件的左端减去非负的剩余变量x6；最后，令z=-z，将求minz改为求maxz。由此，可得标准形如下：max z'= -x, -2x, +2x4 +0xs +0x62x, +3x,-3x +x,=6X +X-4-X=4X, -X, +x =3[X,,4,X5,X≥01.3线性规划问题的解首先，将线性问题的标准形式用矩阵和向量形式表示如下：max z = Cx[AX = B[X≥0其中,C=(cj.c2..c,); X=(X2...)",B=b,b..b.)"[auai2ana21a22a2nA=amnLamlam21、可行解和最优解满足约束条件的所有解X=（x,x2x,）成为线性规划问题的可行解，其中，使目标函数达到最大的可行解成为最优解
（3）若存在取值无约束的变量 k x ，则可令 ' " k k k x = x − x ，其中， , 0 ' " xk xk 。 例：将如下问题转化为标准形式： − = + + = + 2无约束 1 2 1 2 1 2 1 2 0, 3 4 2 3 6 min 2 x x x x x x x x z x x 解： 首先，用 3 4 x − x 替换 2 x ，其中， x3 , x4 0 ； 其次，在第一个约束条件的左端加上非负的松弛变量 5 x ； 再次，在第二个约束条件的左端减去非负的剩余变量 6 x ； 最后，令 z' = −z ，将求 min z 改为求 max z' 。由此，可得标准形如下： − + = + − − = + − + = = − − + + + , , , , 0 3 4 2 3 3 6 max ' 2 2 0 0 1 3 4 5 6 1 3 4 1 3 4 6 1 3 4 5 1 3 4 5 6 x x x x x x x x x x x x x x x x z x x x x x 1.3 线性规划问题的解 首先，将线性问题的标准形式用矩阵和向量形式表示如下： = = 0 max X AX B z CX 其中， ( , ,., ) 1 2 n C = c c c ； T n X (x , x ,., x ) = 1 2 ， T B b b bm , ,., ) = 1 2 = m m mn n n a a a a a a a a a A . . . . . . . 1 2 21 22 2 11 12 1 1、可行解和最优解 满足约束条件的所有解 T n X (x , x ,., x ) = 1 2 成为线性规划问题的可行解，其 中，使目标函数达到最大的可行解成为最优解
2、基和基解设A为约束方程组的mxn维矩阵，其秩为m。设B为矩阵A中的mxm阶非奇异子矩阵（B±0），则称B为线性规划的一个基。不妨设前m个变量的系数矩阵为线性规划的一个基，则X=(x,x2.x.）为对应于这个基的基变量。用高斯消去法可求得一个解X= (X,X.. ..,0)该解得非零分量的数目不大于方程个数m，称X为基解。3、基可行解若基解X满足非负约束，则称其为基可行解。4、可行基对应于基可行解的基，成为可行基。1.4单纯形法一、单纯形表考察一种最简单的形式：目标函数最大化、所有约束条件均为“<”。利用所有约束条件化为等号的方法，在每个约束条件的左端加一个松弛变量，并整理，重新对变量及系数矩阵进行编号，得X, +ai,m+IXmI +...+ai,x,=b,X2+a2,m1Xm+1+...+a2nxn=b,.....Xm+amm+Xm+1+...+ammx,=bmx, ≥0,j=1,...n将其与目标函数的变换形式-z+c,x,+C2×2+.,+Cmm+Cm1m+.,+C,x，=0组成n+1个变量、m+1个方程的方程组。若将=看成不参与基变换的基变量，它与x,x2…,x.的系数构成一个基，利用初等变换将ci,C2.C变为零，则可得
2、基和基解 设 A 为约束方程组的 mn 维矩阵，其秩为 m 。设 B 为矩阵 A 中的 mm 阶非 奇异子矩阵（ B 0 ），则称 B 为线性规划的一个基。 不妨设前 m 个变量的系数矩阵为线性规划的一个基，则 T B m X (x , x ,., x ) = 1 2 为对应于这个基的基变量。用高斯消去法可求得一个解 T n X (x , x ,., x ,0,.,0) = 1 2 该解得非零分量的数目不大于方程个数 m ，称 X 为基解。 3、基可行解 若基解 X 满足非负约束，则称其为基可行解。 4、可行基 对应于基可行解的基，成为可行基。 1.4 单纯形法 一、单纯形表 考察一种最简单的形式：目标函数最大化、所有约束条件均为“ ”。利用 所有约束条件化为等号的方法，在每个约束条件的左端加一个松弛变量，并整理， 重新对变量及系数矩阵进行编号，得 = + + + = + + + = + + + = + + + + + + x j n x a x a x b x a x a x b x a x a x b j m m m m mn n m m m n n m m n n 0, 1,2., . . . . , 1 1 2 2, 1 1 2 2 1 1, 1 1 1 1 将其与目标函数的变换形式 − z + c1 x1 + c2 x2 +.,+cm xm + cm+1 xm+1 +.,+cn xn = 0 组成 n +1 个变量、 m+1 个方程 的方程组。若将 z 看成不参与基变换的基变量，它与 m x , x ,., x 1 2 的系数构成一个 基，利用初等变换将 m c ,c ,.,c 1 2 变为零，则可得
bX-2xX2xmXm+l.01br00ain...ai,m+10010b2a2n"..a2,m+1.................bm0001amnamm+l...-Nc.aNca2eb1000..Cm+1Cali=1i=li=l据此，可设计如下的数表..-cjCmCm+lC.ci0,b.XBCBXiXmXm+1Xn10...b,a1,m+1ain0,cixi00....b202a2nC2a2,m+1X2..........01.bm0mCmXmα m,m+Iamn0...Cj-2jc,aic,ai.m+i=li=1X,列表示基变量，在这里为x,x2XmC.列为基变量x,x2x对应的价值系数；b列为约束方程的右端项；c,行为所有变量的价值系数；0,列的数字是在确定换入变量后，按θ规则计算后填入；最后一行为各变量的检验数，尤其要注意的是非基变量的检验数。例，求解max z=2xi+3x2[x +2x2 ≤84x,≤164x, ≤12X,x2 ≥0首先将其转换为标准形式
= = = + + + + + + − − − − m i i i m i n i i n m i m i i m m m m n m m n m n m m n c c a c c a c b a a b a a b a a b z x x x x x b 1 1 1 , 1 1 1 , 1 , 1 2, 1 2 2 1, 1 1 1 1 2 1 1 0 0 . 0 . 0 0 0 . 1 . . . . . . . . . . 0 0 1 . 0 . 0 1 0 . 0 . . . 据此，可设计如下的数表 j c 1 c . m c m+1 c . n c i CB XB b 1 x . m x m+1 x . n x 1 c 1 x 1 b 1 . 0 a1,m+1 . n a1 1 2 c 2 x 2 b 0 . 0 a2,m+1 . a2n 2 . . . . . . . . . . m c m x mb 0 . 1 am,m+1 . amn m j j c − z 0 . = + − + m i m iai m c c 1 1 , 1 . = − m i n iain c c 1 XB 列表示基变量，在这里为 m x , x ,., x 1 2 ； CB 列为基变量 m x , x ,., x 1 2 对应的价值系数； b 列为约束方程的右端项； j c 行为所有变量的价值系数； i 列的数字是在确定换入变量后，按 规则计算后填入； 最后一行为各变量的检验数，尤其要注意的是非基变量的检验数。 例，求解 + = + , 0 4 12 4 16 2 8 max 2 3 1 2 2 1 1 2 1 2 x x x x x x z x x 首先将其转换为标准形式
maxz=2x,+3x,+0x,+0x,+0xsX,+2x2+=84x, +x4 =164x2 +x, = 12,x2,x,x,x,≥0构造初始单纯形表如下：23000ceCBXBbX3xsXIX2X420811004X300164010X4一[4] 00012013Xs23000c,-2j由上表可得初始基可行解X(0) = (0,0,8,16,12)由于x和x,的检验数大于零，表明上述解不是最优解，由于x,的检验数更大，所以，先以x，为换入变量。根据θ规则，可确定x。为换出变量，计算得新表如下：23000c,0,bCBXBX3xsXiX4X202[1] 0102X3-1/2016400104X43301001/4X22000-3/4Cj-zj可得新解X()）=03,2,16,0)，目标函数取值z=9。x的检验数为2，换入。根据θ规则，可确定x为换出变量，计算得新表如
+ = + = + + = = + + + + , , , , 0 4 12 4 16 2 8 max 2 3 0 0 0 1 2 3 4 5 2 5 1 4 1 2 3 1 2 3 4 5 x x x x x x x x x x x x z x x x x x 构造初始单纯形表如下： j c 2 3 0 0 0 i CB XB b 1 x 2 x 3 x 4 x 5 x 0 3 x 8 1 2 1 0 0 4 0 4 x 16 4 0 0 1 0 - 0 5 x 12 0 [4] 0 0 1 3 j j c − z 2 3 0 0 0 由上表可得初始基可行解 T X (0,0,8,16,12) (0) = 由于 1 x 和 2 x 的检验数大于零，表明上述解不是最优解，由于 2 x 的检验数更 大，所以，先以 2 x 为换入变量。根据 规则，可确定 5 x 为换出变量，计算得新表 如下： j c 2 3 0 0 0 i CB XB b 1 x 2 x 3 x 4 x 5 x 0 3 x 2 [1] 0 1 0 -1/2 2 0 4 x 16 4 0 0 1 0 4 3 2 x 3 0 1 0 0 1/4 - j j c − z 2 0 0 0 -3/4 可得新解 T X (0,3,2,16,0) (1) = ，目标函数取值 z = 9。 1 x 的检验数为 2，换入。根据 规则，可确定 3 x 为换出变量，计算得新表如
下:23000c0,CBXBbX3XsXiX2X4221010-1/2XI0800-41[2] 4X43301001/412X200-201/4C,-2j得新解X(2)=(2,3,08,0)，目标函数取值z=13。x,的检验数为1/4，换入。根据0规则，可确定x，为换出变量，计算得：23000c0,CBXBbXiX2X3X4Xs2410001/4XI0400-211/2xs32011/20-1/8X2000-3/2-1/8cj-2j得解X(3)=(4,2.00,4)，目标函数取值==14。由于所有的检验都小于零达到最优。PS：如果目标函数是求最小化，则，检验数的最优准则为检验数大于零。1.5单纯形法的进一步讨论及小结一、人工变量法如果初始约束条件不全是小于等于号，则不能直接得到初始基（单位基）和初始基可行解，此时必须要构造人工变量。在迭代结束后，如果最后基变量中不再含有非零的人工变量，表示原问题有解；反之，则表示无可行解。例：
下： j c 2 3 0 0 0 i CB XB b 1 x 2 x 3 x 4 x 5 x 2 1 x 2 1 0 1 0 -1/2 - 0 4 x 8 0 0 -4 1 [2] 4 3 2 x 3 0 1 0 0 1/4 12 j j c − z 0 0 -2 0 1/4 得新解 T X (2,3,08,0) (2) = ，目标函数取值 z =13。 5 x 的检验数为 1/4，换入。根据 规则，可确定 3 x 为换出变量，计算得： j c 2 3 0 0 0 i CB XB b 1 x 2 x 3 x 4 x 5 x 2 1 x 4 1 0 0 1/4 0 0 5 x 4 0 0 -2 1/2 1 3 2 x 2 0 1 1/2 -1/8 0 j j c − z 0 0 -3/2 -1/8 0 得解 T X (4,2,00,4) (3) = ，目标函数取值 z = 14 。由于所有的检验都小于零， 达到最优。 PS：如果目标函数是求最小化，则，检验数的最优准则为检验数大于零。 1.5 单纯形法的进一步讨论及小结 一、人工变量法 如果初始约束条件不全是小于等于号，则不能直接得到初始基（单位基）和 初始基可行解，此时必须要构造人工变量。 在迭代结束后，如果最后基变量中不再含有非零的人工变量，表示原问题有 解；反之，则表示无可行解。 例：