例4．
maxz?x1?x2??x1?x2?1?x?x?1?12???x1?x2?1??x1,x2?0无可行解。?x1?x2?1在x1,x2?0时无解。
注：出现例3和例4说明线性规划的数学模型有错误，前者缺乏必要的约束条，后者有矛盾的约束条件。
§1.4 单纯形法
基本思路：根据线性规划的标准形，从线性规划的某个基可行解（或可行域
的某个顶点）开始，按照一定的规则，转换到线性规划的另一个基可行解（或可行域的另一个顶点），最终使目标函数达到最大值。 1． 初始基可行解（可行域顶点）的确定
maxz?cxAx?b
x?0若A中存在单位阵构成的基，不妨设A?(p1,...,pm,pm?1,...,pn)，而
(p1,...pm,?I)m，则Ax?b的解等价于
?x1 +a1 m+1xm+1?...?a1 nxn?b1? x +ax?...?ax?b?22 m+1m+12 nn2? ? ...?? xm +am m+1xm+1?...?am nxn?bm 于是存在基可行解x?(b1,...,bm,0,...,0)T。\\ 2． 单纯形表
9
将约束条件中基变量x1,...,xm用非基变量xm?1,...,xn表示，即有
xi?bi?代入目标函数，则有
j?m?1?ax , (i?1,...,m)
ijjnz??cxii?1mi?1mmi?i?m?1?nncixiaijxj)?n =?ci(bi?j?m?1m?j?m?1?ncjxjn =?cibi??i?1mi?1j?m?1?ciaijxj?mj?m?1?cjxj
=?cibi?i?1j?m?1?n(cj??ciaij)xji?1 =z0?mj?m?1m?i?1n?jxj这里z0??cibi,?j?cj??ciaij
i?1单纯形表 xB x1 x2 ? b x1 1 0 ? x2 0 1 ? ? ? ? xm 0 0 ? xm?1 ? ? ? xn a1n a2n ? b1 a1m?1 a2m?1 ? b2 ? ? ? ? ? xm bm ?z0 0 0 0 0 1 0 amm?1 amn ?m?1 ?n 这里xB是基变量，具体的每个分量写在第1列，b是基变量的值，具体的每个分量的值写在第2列。x1,…,xn下1面的行是约束条件的系数矩阵A的行。最后一行是检验数行，其中基变量x1,…,xm的检验数是0，非基变量的检验数是
?m?1,...,?n。
3．解的判别定理
10
定理1. 设x(0)?(b1,b2,...,bm,0,...,0)T是线性规划的基可行解，那么 （I）若?j?0(j?m?1,...,n)，则x(0)是线性规划的最优解； （II）若存在m?1?k?n，使?k?0，且P)k?(a1k,...,amk最优解；（有至少一个检验数大于零）
（III）若存在m?1?k?n，使?k?0，且存在1?i?m，使aik?0，则线性规划需进行迭代运算；
（IV）若?j?0(j?m?1,...,n)，且存在m?1?k?n，使?k?0，则线性规划有无穷多个最优解。 证明：（I）因为在此单纯形表中，目标函数： z?z0?T?0，则线性规划无
j?m?1??njxj
若?j?0，则由于xj?0，必有z?z0。x(0)?(b1,b2,...,bm,0,...,0)T时，
z?z0。故x(0)是最优解。
(II)令xk???0，xj?0，m?1?j?n，j?k,则xi?bi?aik??0,i?1,...,m。且 z?z0??k???? ,当????时，故该问题的目标函数无上界。
（IV）只需将非基变量xk换入到基变量中（其它基变量不变），找出一个新的基可行解x(1)，故目标函数中对应基可行解x(1)的目标函数的值仍为z0，故x(1)也是最优解。因此x(0)，x(1)连线上所有点都是最优解。 4．迭代规则
若初始基可行解x(0)不是最优解或不能判别其无解时，需要找一个新的基可行解。为此要确定换入变量，再确定换出变量，这样就得到一个新的基可行解。 一个非基变量换入成为基变量。一个基变量换出成为非基变量。
（I）换入变量的确定
若max(?j?0)??k，则非基变量xk成为基变量.
（II）换出变量的确定
??min?i?bi?b|aik?0??l ?aik?alk11
则基变量xl成为非基变量。 （III）迭代后的单纯形表
将单纯形表中第1列中的xl（换出变量）换成xk（换入变量），然后利用行初等变换将Pk中的第l个分量变成1，而其余的分量变为0。具体方法是：将单纯形表中的第l行除以alk，然后用?aik(aik?0)乘以第l行后+第i行，这样就可得到新的单纯形表。
（IV）迭代的合理性
已知p1,...,pm线性无关，下面要证明
p1,...,pl?1,pk,pl?1,...,pm线性无关，且x(1)?bi?blaik?0,i?1,...,m。 alk证明： 因为 故对??0，有
?pxjj?1mj?b,pk??pj?j，这里xj?bj,?j??jk。
j?1m?pxjj?1mj??(pk??pj?j)?b
j?1m 即 取
?(xj?1mj???j)pj??pk?b
???xj???min?|?j?0?j????j????bj??min?|ajk?0?j???ajk? bl?alk 故x(1)?bi?blaik?0.i?1,...,m alk 若p1,...,pl?1,pk,pl?1,...,pm线性相关，则 pk??p?
jjj?k 12
而 pk??pj?j
j?1m故
?p???p?jjjj?k?j1jjm?j0
即
?p(?j?l ??j)?p?l?l0而 ?l??lk?0，故有p1,...,pm线性相关，矛盾。 5．单纯形法
计算步骤
（I）建立初始单纯形表（假设A中存在单位阵）；
（II）若?j?0(j?m?1,...,n)，则已得到最优解，停止。否则转入下一步； （III）若在j?m?1,...,n中，存在?k?0，而Pk?0，则无最优解，停止。否
则转入下一步；
（IV）由max(?j?0)??k，确定xk为换入变量，按?规则
?bi?a|ik? ??miin?aik 可确定xl为换出变量； （V）以alk为主元进行迭代
?bl??0?alk
?0????a1k???????0?????? 即将Pk??alk? 迭代成?1??l行，
???0???????a?????mk??0??? 并将单纯形表xB列中的xl换成xk，得到新的单纯形表； 重复（ⅱ）~（ⅴ）。
例1． 应用单纯形法求解线性规划
13