2为进基变量
?0?x3?8
? ?x4?12?2x2?0 ?x?36?4x?02?5
?1236?12?x2?min?,??
?24?2
2是主元，其所在方程为主方程，且 x x44 为离基变量。? 此时基变量为： x3,x2,x5
? 非基变量为：
14 TX?0,6,8,0,12 z1?30? 得到另一基本可行解为： 1迭代结果
z?3x1?5x2 ? x1 ?x3 ?812?x4 ??3x?5?11?2 x ?x ?6?24
2?5 ?30?3x?x413x1 ?2x4?x5?12??2
1
??4???0,?5??1?0 2T**此时得到的基本可行解也就是最优解。即： 几何意义
2.2 单纯形法的计算过程2.2.1 单纯形表
? 方程组形式的单纯形法求解LP问题使用起来很不方便，为便于单纯形法的计算、
判断和检验，人们设计了若干种形式不同的迭代表格，但其基本思想都是一致的。下面的一种表格就是为了用更简洁、紧凑的方式描述方程组形式单纯形法的计算步骤，兼有增广矩阵的简明性和便于检验的优点而专门设计的，使用较为广泛，一般称为单纯形表。
cjcm?1cnc1?cm?初始单纯形表的一般形式
?i?????????
xm?1xnCBXBbx1?xm?
c1x1b11?0a1,m?1?a1n?1
c2x2b20?0a2,m?1a2n?2
????????
am,m?1cmxmbm0amn?m1??
?3,5??5????max?x,x??X??4,6,4,0,0? z?42检验行0?0cm?1??ciai,m?1?cn??ciaini?1i?1mm? ? ? ? ? ? CB列中填入基变量的价值系数，这里是c1,c2,…,cm；它们是与基变量相对应的； b列中填入初始约束方程组右端的常数；
XB列中填入基变量，这里是x1，x2,…，xm； cj行中填入所有变量的价值系数c1,c2,…,cn；
θi列的数字在确定进基变量后，按θ规则计算后填入； 最后一行称为检验数行，对应所有变量xj的检验数是:
m
jiijjBj
i?1
2.2.2 单纯形法的计算步骤：1）把LP问题化为标准形式；
（2）在系数矩阵中找出或构造出一个m阶单位矩阵作为初始可行基，建立初始单纯形表； （3）计算各非基变量 的检验数，检查检验数，若所有检验数
j m则表示已得到最优解，可停止 计算。否则转入下一步。 (4) 在所有 j ? 0 中，只要有一个 ? r ? 0 所对应 jj?的系数列向量 ? r ? 0 ， i?1即一切 a ir ? 0 ?i ? 1 , 2 , ? ? ，则该LP问题无 ,m界解（即无最优解），停止计算。
jB否则，转入下一步。 (5) 根据最大检验数规则
jjk
c??ca?c?C?(j?1,2,?,n)??0,j?m?1,m?2,?n??c??ciaij ?c?C?jmax ???0 ? ???
确定 为进基变量，
k再按最小比值规则
il
ik
iklk
确定主元，同时也确定了主元所在行的基变量为离基变量。（6）以主元为轴心对当前表格进行换基运算，得到一个新的单纯形表，再返回第3步，继续进行迭代。 2.2.3 单纯形法计算之例 maxz?2x1?3x2?0x3?0x4?0x5
x1?2x2?x3?8
4x1??x4?16 4x2?x5?12
xj?0j?1,2,?,5
目标函数中各变量的价值系数
x?b?b??min??aa?0???a??
m
计算非基变量的检验数 jjiiji?1
jBj
? 各非基变量的检验数为
?1? ???1?c1?CB?1?2??0,0,0??4??2
?0? ?? ?2???
?2?c2?CB?2?3??0,0,0??0??3 ?4???
继续迭代得下表，可以看到所有检验数都已为非正，这表示目标函数值已不可能再增大，于是得到最优解。 cj→ 2 3 0 0 0
θ
CB XB b x1 x2 x3 X4 x5
2 x1 4 1 0 0 1/4 0
0 x5 4 0 0 -2 1/2 1
3 1 1/2 -1/8 0 x2 2 0 0 0 -3/2 -1/8 0
该LP问题的最优解为：
TX*?4,2,0,0,4
最优值为： *z?2*4?3*2?14
12单纯形法求解下列LP问题： 12
??c??ca ?c?C??? max z ?3x?2x??2x? x?2?s.t. ? x1?3x2?3?x,x?0?12用单纯形法求解下列LP问题： max z ?6x1?3x2?3x3
?3x1? x2? x3?60 ?2x?2x?4x?20?123 s.t. ? ?3x1? 3x2?3x3?60 ??x1,x2,x3?0
? 2.3 人工变量法：应用单纯形法求解LP问题时，首先将其化为标准形，
然后设法找出或构造出一单位阵作为初始可行基。当约束条件都是“≤”时，加入的松弛变量就可以做为初始可行基，这样我们就可以马上进入单纯形表的运算步骤。然而并非所有问题标准化之后我们都很容易得到一个明显的初始可行基，比如当约束条件有“≥”或“＝”型时，所加入的剩余变量就不能作为初始可行基中的基变量。为了满足单纯形法的条典要求，这时就需要我们去构造新的初始可行基。通常采用的是构造人造基的方法，即人工构造单位矩阵。这种方法称为人工变量法，所加入的变量对应称为人工变量。 人工变量法常用方法
max z ?2x1?x2?3x3? 大M法、两阶段法
设法找出或构造出下列LP问题的初始可行基
??x1?4x2?x3?5
? s.t. ?2x1?3x2?6 max z ?5x1?3x2?2x3?4x4?x,x,x?0?123
?5x1? x2? x3?8x4?10
?
s.t. ?2x1?4x2?3x3?2x4?10
?x,x,x,x?0 ?1234
min ?2x1?3x2?x3
x1?4x2?2x3?8?
? s.t. ?3x1?2x2 ?6 ?x,x,x?0?123
? 2.3.1 大M法：这种方法是在原LP问题的目标函数中添上全部 的人工变量，并令其系数为 ，而M是一个充 分大的正数，这样就将原问题转化为求解新构造 出的辅助问题：
max z ?c1x1?c2x2???cnxn ?Mxn?1?xn?2???xn?m
x n ? 2 , ?? 其中：x n ? 1 , , x n ? m 为人工变量。
大M法在求解LP问题时一般遇到的几种情况 ? 若用单纯形表求得新构造出的辅助问题有最优解，且最优解的基变量中不含有添入
的人工变量，则辅助问题的最优解去掉人工变量分量就构成了原LP问题的最优解；否则原LP问题无可行解。
???? 若辅助问题迭代最终结果为无最优解，如果此时对应的最终单纯形表基变量中无人
工变量，则原LP问题也为无最优解；否则为无可行解。
例：用大M法求解下列LP问题 123
123
123 123解：按大M法引入人工变量，构造新的辅助问题如下： max z ?3x1?x2?2x3?Mx4?Mx5
?6?3x1?2x2?3x3?x4
? s.t. ? x1?2x2? x3 ?x5?4 ?x,x,x,x,x?0?12345
此时可以看到迭代最终表中所有非基变量的检验数全为非正数，则辅助问题存在最优解为： T**
因为此时基变量中不含有人工变量，去掉人工变量，取辅助问题最优解的前3个分量，则
T得到原LP问题的最优解为：
X*?3,0,1 z*?7
练习：试用大M法求解下列线性规划问题 min ? ??3x1?x2?x3
? x1?2x2? x3?11
??4x? x?2x?3
?123 s.t. ? x3?1 ??2x1? ?x1,x2,x3?0? 解：先将原LP问题加入松弛变量x4，剩余变量x5化为标准形 ，然后加入人工变量x6,x7，得到辅助问题如下：
min z ??3x1?x2?x3?Mx6?Mx7
?11? x1?2x2? x3?x4
??4x? x?2x ?x5?x6 ?3?123s.t. ? x3 ?x7?1??2x1? ?x1,x2,x3,x4,x5,x6,x7?0?
因本例的目标函数是要求min，所以用所有非基变量的检验数≥0来判别目标函数是否实现了最小化，相应的应该是所有负检验数采用最小检验数规则选择进基变量，离基变量选择
max z ?3x?x?2x?3x?2x?3x?6?s.t. ? x?2x? x?4?x,x,x?0?X??3,0,1,0,0? z?7??