i?1,2,?,k；??i?1，使X???iX(i)，则称X为X(1),X(2),?,X(k)的凸组合。
i?1i?1kk顶点：设K是凸集，X?K；若X不能用不同的两点X(1)?K和X(2)?K的线性组合表示为
X??X(1)?(1??)X(2)，（0???1）；则称X为K的一个顶点（或极点）。
2.2 基本定理
n定理1 若线性规划问题存在可行域，则其可行域D?{X|?Pxjj?1j?b,xj?0}是凸集。
T引理1 线性规划问题的可行解X?(x1,x2,?,xn)为基可行解的充要条件是X的正分量所对应的系数
列向量是线性独立（无关）的。
定理2 线性规划问题的基可行解对应于可行域D的顶点。
引理2 若K是有界凸集，则任何一点X?K可表示K的顶点的凸组合。
定理3 若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。有时目标函数可能在多个顶点处达到最大值，这时在这些顶点的凸组合上也达到最大值。若可行域为无界，则可能无最优解，也可能有最优解，若有也必定在某顶点上得到。
总结：线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应于可行域的一个顶点；若线性规划问题有最优解，必在某顶点上得到。
§3 单纯形法
基本思路：根据问题的标准型，从可行域中某个基可行解（顶点）开始，从一个基可行解（顶点）转换到另一个基可行解（顶点），使目标函数值不断增大，当目标函数值达到最大时就得到了最优解。 3.1 举例
maxz?2x1?3x2?0x3?0x4?0x5?x1?2x2?x3?8??4x?x4?16?1s.t.??4x2?x5?12???x1,x2,x3,x4,x5?03.2 初始基可行解的确定
9
为确定初始基可行解，先找出初始可行基，其方法如下： 1. 若线性规划问题
?n??Pjxj?b?j?1n?maxz??cjxj (1.20) s.t. ?xj?0j?1??规定b?0??(1.21)
j?1,2,?,n 从Pj（j?1,2,?,n）中
?10?0????01?0?,P,?,P)?直接观察到一个初始可行基B?(P12m??????。
???00?1???2. 对所有约束条件是“?”形式的不等式，可利用化标准型的方法，在每个约束条件的左端加上一个松
驰变量。经过整理，重新对xj及aij（i?1,2,?,m;j?1,2,?,n）进行编号，则可得下列方程组：
x1?10?0???x2?a2,m?1xm?1???a2nxn?b201?0??,P,?,P)? 得初始可行基B?(P12m??????
??????????????????00?1???xm?am,m?1xm?1???amnxn?bm?a1,m?1xm?1???a1nxn?b1T令非基变量XN?(xm?1,xm?2,?xn)?(0,0,?,0)，求得初始基可行解X?(b1,b2,?,bm,0,0,?0)。
3. 对所有约束条件是“?”形式的不等式及等式约束情况，若不存在单位矩阵时，就采用人造基方基。
即对于不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束再加上一个非负的人工变量，总能得到一个单位矩阵。（本章§5深入讨论） 小结：任一线性规划问题都可化为以下类型的线性规划问题来求解，我们称之为典则型线性规划问题：
?x1?a1,m?1xm?1???a1nxn?b1??x?a2,m?1xm?1???a2nxn?b22?maxz?c1x1?c2x2??cnxn s.t. ? （1.22）
??????????????????xm?am,m?1xm?1???amnxn?bm? 10
3.3 最优性检验与解的判别
nmnmxi?b?m'ij?m?1?axj (i?1,2,?,m) (1.24) ； z??cb?'ij'iii?1j?m?1?'(cj??ciaij)xj (1.25) ；令
i?1z0??cb , zj??cia , (j?m?1,?,n), 则 z?z0?'ii'iji?1i?1mj?m?1?(cnj?zj)xj (1.26)；再令
?j?cj?zj , (j?m?1,?,n) , 则z?z0?j?m?1??njxj （ 1.27）。
(0)''?(b1',b2,?,bm,0,?,0)T为对于基B的一个基可行解，且对于一切1. 最优解的判别定理：若Xj?m?1,?,n有?j?0，则X(0)为最优解。称?j为检验数。
2. 无穷多最优解判别定理：若X(0)''?(b1',b2,?,bm,0,?,0)T为一个基可行解，对于一切j?m?1,?,n有?j?0，又存在某个非基变量的检验数?m?k?0，则线性规划问题有无穷多最优解。
(0)''?(b1',b2,?,bm,0,?,0)T为一个基可行解，有一个?m?k?0，并且对 3. 无界解判别定理：若X。 i?1,2,?,m有ai,m?k?0，则线性规划问题有无界解（或称无最优解）
注：以上讨论都是针对标准型，即求目标函数极大化时的情况。当求目标函数极小化时，一般情况如前所述，将其化为标准型。如果不化为标准型，只需在上述1，2点中把?j?0改为?j?0，第3点中将?m?k?0改为?m?k?0即可。 3.4 基变换 若初始基可行解X(0)不是最优解及不能判别无界时，需要找一个新的基可行解。作法是从原可行基中换
一个列向量（保持线性无关），得到一个新可行基，这称之为基变换。为换基，先确定换入变量，再确定
换出变量，对换系数列向量，就得新基可行解。
1. 换入变量的确定 一般选max{?j?0}??k对应的xk为换入变量，也可任选或按最小足码选
j?j(?0)对应的xj为换入变量。
2. 换出变量的确定
11
(0)设P。将X(0)代入约束方程组（1.21）1,P2,?,Pm是一线性无关的向量组，它们对应的基可行解是Xm得：
?xi?1(0)iPi?b (1.28) ；Pm?1,Pm?2,?,Pm?t,?,Pn可用P1,P2,?,Pm线性表示，设Pm?t为换入变量，
m则Pm?t???i?1mi,m?tPi ，其中?i,m?t（i?1,2,?,m）不全为零；于是，Pm?t???i,m?tPi?0 （1.29），
i?1(0)i取??0，得
?xi?1mPi??(Pm?t???i,m?tPi)?b，即?(xi(0)???i,m?t)Pi??Pm?t?b （1.30）；只
i?1i?1mm(0)??xl(0)?xi??i,m?t?0??要按最小比值规则选取??min?，xl为换出变量，则得新基可行解：
i????l,m?t?i,m?t?X(1)?(0)xl(0)?xl(0)xl(0)(0)?(0)??x1??1,m?t,?,0,?,xm??m,m?t,0,?,0,,0,?,0?；由此得由X??l,m?t?l,m?t?l,m?t???(0)xl(0)?i,m?t?xi??l,m?t???(0)?xl??l,m?t?i?l
到X(1)的各分量的转换公式：xi(1)i?l用反证法可证X(1)的m非零分量对应的列向量Pj（j?1,2,?,m;j?l）、Pm?t是线性无关：反设Pj（j?1,2,?,m;j?l）、Pm?t线性相关，因为Pj（j?1,2,?,m;j?l）线性无关，所以Pm?t可由Pj（j?1,2,?,m;j?l）线性表示，即Pm?t?m??j?1j?lmjPj；又因Pm?t???i,m?tPi，所以
i?1m?(?j?1j?lj,m?t??j)Pj??l,m?tPl?0；根据?规则，?l,m?t?0，再由上式知P1,P2,?,Pm线性相关，这与
已知条件矛盾。 3.5 迭代（旋转运算）
12
