第一章 线性规划模型
③ z0??cb,?iii?1mj?zj?cj??ciaij?cj(j?m?1,...,n)
i?1m（2）判别最优解
① 在T(B)中，若所有的检验数?j?0 (j?1,2,则B为最优基，相应的基可行解为最优解，停止计算。
② 在T(B)中，若有?k?0(1?k?n)，且xk的系数列向量Pk?0，则该问题无界，停止计算。否则转入（3）。
（3）换基迭代（基变换）
① 先确定进基变量xk，根据max{?j?j?0}??k来确定k或k?min{j?j?0}，即选择最小检验数或行从左至右选择第一个负检验数所对应的变量进基。
,n)
?bL?bi|aik?0??② 按最小比值原则确定出基变量xL：??min?。 aaLk?ik?③ 以aLK为主元，进行初等行变换（又称旋转变换），即将列向量PK变换为单位列向量： 返回（2）。
换基迭代的关键在于将换入变量对应的列向量PK用初等行变换方法变换成单位列向量。
其中主元aLK?a1k??0??a??0??2k????:??:?变成1。即Pk???????第L个分量。
?aLk??1??:??:??????amk???0??如果在最终表中有非基变量的检验数为0，则该问题有多重最优解。
例2 求解下列线性规划问题
maxz?4x1?3x2?2x1?3x2?24 ?s..t?3x1?2x2?26?x,x?0?12解：引进松驰变量x3,x4，化为标准形得：
maxz?4x1?3x2?0x3?0x4?2x1?3x2?x3?24?s..t?3x1?2x2?x4?26?x,x,x,x?0?1234
11
第一章 线性规划模型
从标准形中可看出存在可行基，B?(P3,P4)?I，基变量为x3,x4；非基变量为x1,x2。建立初始单纯形表得： cj CB 0 4 3 0 0 XB b 24 x1 x2 x3 x4 2 3 1 0 3 2 0 1 x3 x4 0 26 0 z
?4 ?3 0 0 由于x1,x2的检验数均为负，且x1的检验数绝对值最大，选取x1为进基变量；再按最小比值??min(242,263)?263，因此选取x4为出基变量，进行换基迭代。
cj CB 0 4 3 0 0 XB b x1 x2 x3 x4 0 53 1 ?23 1 23 0 13 x3 x1 203 263 4 z
1043 0 ?13 0 43 cj CB 3 4 3 0 0 XB b 4 x1 x2 x3 x4 0 1 35 ?25 1 0 ?25 35 x2 x1 4 6 36 z 0 0 15 65 表中最后一行的所有检验数均为非负数，表明目标函数已达到最大值，上述表为最终表。从表中可得到最优解为X?(x1,x2,x3,x4)?(6,4,0,0)，最优值为z?36。
12
第一章 线性规划模型
三、单纯形法的进一步讨论──用人工变量法求初始基可行解
1、人工变量法
若对LP模型标准化后，不具有B?I时，如何办？此时可采用人工变量法得到初始基可行解。
所谓人工变量法是在原问题不含有初始可行基B?I的情况下，人为的对约束条件增加虚拟的非负变量（即人工变量），构造出含有B?I的另一个LP问题后求解。当增加的人工变量全部取值为0时，才与原问题等价。
这样，新问题将有一个初始基可行解（以人工变量为基变量），可用单纯形法进行迭代。经迭代后，若人工变量全部被换成非基变量，即人工变量全部出基，则得到原问题的一个基可行解。
在最终表中若人工变量不能全部被换出，则说明原问题无可行解。 因此，该法的关键在于将人工变量全部换出。 2、大M法（通过下例简略介绍其方法与步骤）
在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影响，为此当目标函数要实现最大时，假定人工变量的系数为(?M)，当目标函数要实现最小时，假定人工变量的系数为M（其中M为任意大的正数）。
例3 用大M法求解
minz?x1?1.5x2
?x1?3x2?3??x1?x2?2 ?x,x?0?12解：
minz?x1?1.5x2?0x3?0x4?Mx5?Mx6
?3?x1?3x2?x3?x5??x4?x6?2 ?x1?x2?x,x?0,x,x?0,x,x?03456?12其中x3,x4为剩余变量，x5,x6为人工变量，M为任意大的正数。 注意到：①分别在约束条件中增加人工变量x5,x6是为了构成“人工基”
②对于Min的目标函数采用(?M)，而对于Max的目标函数则采用(?M)作为人工变量的系数,是强加于人工变量的一种惩罚,其目的是为了强制人工变量由基变量转为非基变量，使
之恢复原问题，或与原问题等价。
③对于minz判别最优性准则应是cj?zj?0。
④大M法适合于计算机计算，不适用于手工求解。 所以本题求解过程略。
3、两阶段法
第一阶段：不考虑原问题是否存在基可行解；给原LP问题的约束条件加入人工变量，构
13
第一章 线性规划模型
造仅含人工变量的目标函数并要求实现最小化（即使原LP问题目标函数是求最大化）的辅助问题：
minw?xn?1?xn?2??xn?m
?a11x1?????a1nxn?xn?1?b1?ax?????ax?x?b2112nnn?22????????s.t.?
?ax?????ax?x?bmnnn?mm?m11x1,x2,???,xn?m?0??然后用单纯形法求解上述模型。若w?0，则原问题无可行解，停止计算。若w?0，且
所有的人工变量均为非基变量，则去掉人工变量后可得到原问题的基可行解；如果人工变量中含有为0的基变量时（即退化解），则可再进行初等行变换将其换出，从而获得原问题的基可行解。
第二阶段：在第一阶段所得的基可行解的基础上，将最终表中的人工变量列删去，同时将人工目标函数行换为原问题的目标函数作为第二阶段计算的初始表。
例4 将上例用两阶段法求解。
minz?x1?1.5x2?0x3?0x4解：原问题：?minw?x5?x6 辅助问题：??x1?3x2?x3?3?x4?2?x1?x2?x,x?0,x,x?034?12?x1?3x2?x3?x5?3
?x4?x6?2?x1?x2?x,x?0,x,x?0,x,x?03456?12用单纯形法求解的迭代表如下： cj CB 1 0 0 0 0 1 1 b XB x1 x2 x3 x4 x5 x6 1 3 ?1 0 1 0 x5 x6 3 1 2 1 1 0 ?1 0 1 w
5 2 4 ?1 ?1 0 0 cj CB 0 1 0 0 0 0 1 1 b 1 1 1 XB x1 x2 x3 x4 x5 x6 1/3 1 -1/3 0 1/3 0 2/3 0 1/3 -1 -1/3 1 2/3 0 1/3 -1 -4/3 0 x2 x6 w
14
第一章 线性规划模型
cj CB 0 0 0 0 0 1 1 b 1/2 3/2 0 XB x1 x2 x3 x4 x5 x6 0 1 -1/2 1/2 1/2 -1/2 1 0 1/2 -3/2 -1/2 3/2 0 0 0 0 -1 -1 x2 x1 0 w 上述表中目标函数值w?0，且人工变量已全部出基，得到原问题的一个可行基B?(P2,P1)和一个基可行解X?(x2,x1)T?(12,32)T。去掉人工变量列，并将目标函数行换为原目标函数行得：
cj CB 1.5 1 12 0 0 XB b x1 x2 x3 x4 0 1 ?12 12 1 0 12 ?32 x2 12 1 x1 32 z 94 0 0 ?14 ?34 上表中最后一行所有检验数均非正（因为是求极小化问题），所以上述表已是原问题的最优表。从表中可知原问题的最优解为x1?32，x2?12，最优目标函数值为z?94。
注意：第二阶段在填单纯形表时，检验数行的值是将原目标函数中的基变量用非基变量表示（x1?32?12x3?32x4，x2?12?12x3?12x4）后所得结果填入，或直接通过表中数字关系计算而得。
例5 分别用单纯形法中的大M法和两阶段法求解下述线性规划问题。
maxz?2x1?3x2?5x3?x1?x2?x3?7??2x1?5x2?x3?10?x,x,x?0?123解：（1）大M法
加入人工变量，原问题可化为
maxz?2x1?3x2?5x3?Mx4?0?x5?Mx6?7?x1?x2?x3?x4??x5?x6?10?2x1?5x2?x3?x,x,x,x,x,x?0?123456
15