四, 单纯形法的一般描述：
1,初始可行解的确定
(1)初始可行基的确定
?观察法 —— 观察系数矩阵中是否含有现
成的单位阵？
?LP限制条件中全部是, ≤” 类型的约束 —
— 将新增的松弛变量作为初始基变量,
对应的系数列向量构成单位阵；
先将 约束条件标准化,再 引入非负
的人工变量, 以人工变量作为初始基变
量,其对应的系数列向量构成单位阵，
称为,人造基” ；
然后用 大 M法 或 两阶段法 求解；
?线性规划限制条件都是,≥”或,=”
类型的约束 ——
等式约束左端引入人工变量的目的
使约束方程的系数矩阵中出现一个
单位阵, 用单位阵的每一个列向量对
应的决策变量作为, 基变量,,这样，
出现在单纯形表格中的 B(i)列（即约
束方程的右边常数）值正好就是基变
量的取值。
（ 注意,用非基变量表示基变量的表达式 ）
① 如果限制条件中既有,≤”类型的约束，
又有,≥”或,=”类型的约束，怎麽办？
构造“不完全的人造基”！
讨 论
② 为什麽初始可行基一定要选 单位阵？
b列正好就是基变量的取值,检验数行
和 b列交叉处元素也正好对应目标函数值,
因此称 b列为 解答列
（ 2） 写出初始基本可行解 ——
根据, 用非基变量表示基变量的表达式,,
非基变量取 0,算出基变量, 搭配在一起构成
初始基本可行解 。
2,建立判别准则：
（ 1） 两个基本表达式的一般形式
就 LP限制条件中全部是, ≤” 类型约束, 新
增的松弛变量作为初始基变量的情况来描述：
?
?
?
?
?
?
?
?
?
?
?????
?????
?????
??
?
?
?
?
?
???
??
0,,,
..
0
21
2211
222222121
111212111
11
mn
mmnnmnmm
nnn
nnn
mn
nj
j
n
j
jj
xxx
bxxaxaxa
bxxaxaxa
bxxaxaxa
ts
xxcM a x Z
?
?
???
?
?此时 LP的标准型为
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
???
100
010
001
),,,(
21
)0(
?
????
?
?
?
mnnn
PPPB
初始可行基,
初始基本可行解：
T
mbbbX ),,,,0,,0,0( 21
)0( ???
一般 （ 经过若干次迭代 ）, 对于基 B，
用非基变量表出基变量的表达式 为：
mixabx
n
j
jijiin,2,1,
1
'' ???? ?
?
?
用非基变量表示目标函数的表达式：
?
?
?????
? ???
? ?????
?
?
?
?
?
?
?
?
??
?
? ?
?
??
?
? ?
?
??
??
?
?
?
??
?????
?????
???
??????
n
j
jj
jjjjj
n
j
j
m
i
ijinj
m
i
iin
m
i
jijin
n
j
j
m
i
iin
m
i
n
j
jijin
n
j
jj
m
i
iin
m
i
n
j
jijiin
n
j
jj
m
i
inin
n
j
jj
mn
j
jj
xZ
zcxzcZ
aczbcZxaccbc
xacxcbc
xabcxcxcxcxcZ
1
0
1
0
1
'
1
'
1
0
'
11
'
1 1
'
11
'
1 1
''
1111
)(
,)(
)(
?
?令
令
若 是对应于基 B的基本可
行解, 是非基变量 的检验数, 若对于
一切非基变量的角指标 j,均有 ≤0,则 X(0)
为最优解 。
),,,,0,,0,0( ''2'1)0( mbbbX ???
j? )0(jx
j?
（ 2） 最优性判别定理
（ 3）无“有限最优解”的判别定理
若 为一基本可行解，有
一非基变量 xk,其检验数,而对于
i=1,2,…, m，均有,则该线性规划问题
没有“有限最优解” 。
),,,,0,,0,0( ''2'1)0( mbbbX ???
0?k?
0' ?ika
证明思路 —— 构造性证明,
依据 用非基变量表示基变量的表达式 构造一族
可行解, 其对应的目标函数值趋于无穷大 。
几何意义, 沿着无界边界前进的一族可行解
举例,用非基变量表示基变量的表达式
?
?
?
????
????
4325
4321
636
3
xxxx
xxxx
代表两个约束条件：
?
?
?
????
????
663
3
5432
4321
xxxx
xxxx
x2对应的系数列向量 P2=（ 1,3） T，
当前的换入变量是 X2，按最小比值原则
确定换出变量：
?
?
?
?????
?????
0636
03
4325
4321
xxxx
xxxx
? ? ????
?
?
?
?
?
2/6,1/3m in
3/6
1/3
2
2
2 x
x
x
要求：
于是：
如果 x2的系数列变成 P2’=（ -1,0） T,则用非
基变量表示基变量的表达式就变成；
?
?
?
?????
?????
0606
03
4325
4321
xxxx
xxxx
可行性自然满足,最小比值原则失效,意即 x2的值
可以任意增大 → 原线性规划无, 有限最优解, 。
3,进行基变换
（ 1） 选择进基变量 —— 原则,正检验数 （ 或
最大正检验数 ） 所对应的变量进基, 目的是
使目标函数得到改善 （ 较快增大 ） ；
进基变量对应的系数列称为 主元列 。
（ 2） 出基变量的确定 —— 按最小比值原则确
定出基变量, 为的是保持解的可行性 ；
出基变量所在的行称为 主元行 。
主元行和主元列的交叉元素 称为 主元素 。
思考题
这样进行基变换后得到的新解对应的系数
列向量是否线性独立？
4,主元变换 （ 旋转运算或枢运算 ）
按照主元素进行矩阵的初等行变换 —— 把主
元素变成 1,主元列的其他元素变成 0（ 即主
元列变为单位向量 ）
写出新的基本可行解, 返回最优性检验 。
单纯形法小结
求解思想－－
顶点的逐步转移,
条件是
使目标函数值不断得到改善 。
表格单纯形法求解步骤
第一步,将 LP化为标准型, 并加以整理。
引入适当的松驰变量、剩余变量和人工变量
，使约束条件化为等式,并且约束方程组的系数
阵中有一个单位阵。
（这一步计算机可自动完成）
确定初始可行基，写出初始基本可行解
第二步,最优性检验
计算检验数，检查：
?所有检验数是否 ≤ 0？
是 —— 结束，写出最优解和目标函数最优值；
?还有正检验数 —— 检查相应系数列 ≤ 0？
是 —— 结束，该 LP无“有限最优解”！
?不属于上述两种情况,转入下一步 — 基变换。
确定是停止迭代还是转入基变换？
选择（最大） 正检验数 对应的系数列
为 主元列,主元列对应的非基变量为 换
入变量；
最小比值对应的行为 主元行, 主元行
对应的基变量为 换出变量 。
第三步,基变换
确定进基变量和出基变量。
利用矩阵的 初等行变换 把 主元列变成单
位向量，主元素变为 1,进基变量对应的
检验数变成 0，从而得到一张新的单纯形
表，返回第二步。
第四步 换基迭代（旋转运算、枢运算 )
完成一次迭代，得到新的基本可行解和
相应的目标函数值
该迭代过程直至下列情况之一发生时停止
?检验数行全部变为非正值；
（ 得到最优解） 或
?主元列 ≤0 （最优解无界）
停止迭代的标志（停机准则）
依据：最优性检验的两个定理
最优性判别定理；无“有限最优解”判断定理
计算机求解时的注意点
1,输入数据中的分数, 需 先化为小数再执行输入过程 。
2,每一张迭代表格中由基变量列 （ Basic） 和 B(i)列
（ 解答列 ） 可以读出现行解及相应的目标函数值,
同时显示进基变量和出基变量, 从而很容易识别主
元列, 主元行和主元素 。
3,最终表显示最优解, 最优目标函数值及总的迭代次
数 。 如遇该线性规划无可行解或无, 有限最优解,,
则屏幕将显示有关信息：
NO feasible solution,
或 * * unboundedsolution !!!
五, 各种类型线性规划的处理
1,分类及处理原则：
（ 1） 类型一,目标要求是, Max”,约
束条件是, ≤” 类型 —— 左边加上非负松
弛变量变成等式约束 （ 约束条件标准
化 ）, 将引入的松弛变量作为初始基变
量, 则初始可行基是一个单位阵, 用 原
始单纯形法 求解 。
（ 2） 类型二,目标要求是, Max”,约
束条件是, =”类型 —— 左边引入非负的
人工变量, 并 将引入的人工变量 作为 初
始基变量, 则初始可行基是一个单位阵,
然后 用大 M法或两阶段法 求解 。
（ 3） 类型三,目标要求是, Max”,约
束条件是, ≥” 类型 —— 约束条件标准
化, 左边减去非负的剩余变量, 变成等
式约束, 化为类型二 。
（ 4） 类型四,目标要求是, Min”
① 方法 1—— 化为极大化问题
②方法 2—— 按照极小化问题直接在单
纯形表格上计算处理，但
相应的原则要作改动 。
2,处理人工变量的方法：
（ 1） 大 M法 —— 在约束条件中人为地加入非负
的人工变量, 以便使它们对应的系数列向量构
成单位阵 。
问题：加入的人工变量是否合理？ 如何处理？
在 目标函数中, 给人工变量前面添上一个绝对
值很大的负系数 -M（ M>>0）, 迭代过程中,
只要基变量中还存在人工变量, 目标函数就不
可能实现极大化 —— 惩罚 ！
① 最优表中, 基变量不包含人工变量, 则 最
优解就是原线性规划的最优解, 不影响目标
函数的取值；
② 最优表中, 基变量中仍含有人工变量, 表
明原线性规划的约束条件被破坏, 线性规划
没有可行解, 也就 没有最优解 ！
结 果
问题 结果 ② 中求得的最优解是哪个线性
规划的最优解？ 为什麽？
（ 2） 两阶段法
第一阶段, 建立辅助线性规划并求解,
以判断原线性规划是否存在基本可行解 。
辅助线性规划的结构,目标函数 W为所
有人工变量之和,目标要求是使 目标函
数极小化,约束条件与原线性规划相同。
求解结果
① W最优值 =0—— 即所有人工变量取值全为 0
（ 为什麽？ ）, 均为非基变量, 最优解是原线
性规划的一个基本可行解, 转入第二阶段；
② W最优值 =0—— 但人工变量中有等于 0的基
变量, 构成退化的基本可行解, 可以 转化为情
况 ① ； 如何转化？
选一个不是人工变量的非基变量进基,
把在基中的人工变量替换出来
③ W最优值 >0—— 至少有一个人工变量取值
>0,说明 基变量中至少有 1个人工变量,表明 原
问题没有可行解,讨论结束 。
问题讨论
① 教材 P49辅助线性规划的结构是,目标函
数 W为所有人工变量之和的相反数, 目标要
求是使目标函数极大化, 约束条件与原线性
规划相同 。 这与上述的讨论 是否矛盾？
试比较：
?
?
?
?
?
????
???
?
?
?
?
..
21
ts
xxxM i n Z
mnnn
?
?
?
?
?
?????
???
?
?
?
?
..
21
ts
xxxM a x Z
mnnn
（ 1）
（ 2）
② （ 1）式目标要求改为极大化（或（ 2）式
目标要求改为极小化）行不行？
第二阶段：
将第一阶段的最优解作为初始可行解, 目标
函数换成原问题的目标函数, 进行单纯形迭
代, 求出最优解 。
问题讨论,① 如何实 施？ 需要重新建立初始
单纯形表吗？
实施中，在第一阶段最优表格中 划去
人工变量列,将表头部分和 CB列的价
值系数 换成原问题的价值系数 (把目标
函数换成原线性规划的目标函数 )，继
续迭代，直至求出最优解。
② 在大 M法中，当人工变量出基后能
否 立即划去 该人工变量所在的系数列？
3,用表格单纯形法直接计算极小化线性规划
时要修改哪些原则？
（ 初始表？ 最优解判别？ 换入变量？ 换出变
量？ 旋转运算？ 引入人工变量？ ）
? 最优性判别,所有检验数非负
? 换入变量的选择原则,（ 最小 ） 负检验数
所对应的变量进基, 以保证目标函数值 （ 较
快 ） 减小；
? 用大 M法求解时, 在 目标函数中人工变量
的前面添上一个很大的正系数 M；
六, 迭代过程中可能出现的问题及处理方法
1,为确定出基变量要计算比值, 该 比值 =
解答列元素 /主元列元素 。 对于主元列的 0
元素或负元素是否也要计算比值？
（ 此时 解的可行性自然满足, 不必计算 ；
如果 主元列元素全部为 0元素或负元素,
则 最小比值失效, 线性规划 无, 有限最优
解, ）
2,现若干个相同的最小比值怎麽办？
（ 说明 出现了退化的基本可行解, 即非 0分量
的个数小于约束方程的个数 。 按照, 摄动原理,
所得的规则, 从相同比值对应的基变量中选下
标最大的基变量作为换出变量 可以避免出现
,死循环, 现象 ）
3,选择进基变量时, 同时有若干个正检验数,
怎麽选？
（ 最大正检验数或从左至右第 1个出现的正
检验数所对应的非基变量进基 ）
课堂练习,直接按极小化问题求解下面的 LP：
?
?
?
?
?
??
?
???
??
0,0
3
22
..
2
21
1
21
21
xx
x
xx
ts
xxM i n Z
CB XB
cj
xj
b
1 2 0 0 M
X1 X2 X3 X4 X5
M
0
X5
X4
2
3
-1 2 -1 0 1
1 0 0 1 0
2/2
_
-Z -2M 1+M M 0
2-2M 0
2
0
X2
X4
1
3
-1/2 1 -1/2 0 1/2
1 0 0 1 0
-Z -2 2 0 1 0 M-1
?j
第三次作业 P71 1-6 三个小题
9月 26日交
由最优表得：
最优解为 X*=（ 0,1,0,3,0） T,
相应的目标函数最优值为 Zmin=2
1,初始可行解的确定
(1)初始可行基的确定
?观察法 —— 观察系数矩阵中是否含有现
成的单位阵？
?LP限制条件中全部是, ≤” 类型的约束 —
— 将新增的松弛变量作为初始基变量,
对应的系数列向量构成单位阵；
先将 约束条件标准化,再 引入非负
的人工变量, 以人工变量作为初始基变
量,其对应的系数列向量构成单位阵，
称为,人造基” ；
然后用 大 M法 或 两阶段法 求解；
?线性规划限制条件都是,≥”或,=”
类型的约束 ——
等式约束左端引入人工变量的目的
使约束方程的系数矩阵中出现一个
单位阵, 用单位阵的每一个列向量对
应的决策变量作为, 基变量,,这样，
出现在单纯形表格中的 B(i)列（即约
束方程的右边常数）值正好就是基变
量的取值。
（ 注意,用非基变量表示基变量的表达式 ）
① 如果限制条件中既有,≤”类型的约束，
又有,≥”或,=”类型的约束，怎麽办？
构造“不完全的人造基”！
讨 论
② 为什麽初始可行基一定要选 单位阵？
b列正好就是基变量的取值,检验数行
和 b列交叉处元素也正好对应目标函数值,
因此称 b列为 解答列
（ 2） 写出初始基本可行解 ——
根据, 用非基变量表示基变量的表达式,,
非基变量取 0,算出基变量, 搭配在一起构成
初始基本可行解 。
2,建立判别准则：
（ 1） 两个基本表达式的一般形式
就 LP限制条件中全部是, ≤” 类型约束, 新
增的松弛变量作为初始基变量的情况来描述：
?
?
?
?
?
?
?
?
?
?
?????
?????
?????
??
?
?
?
?
?
???
??
0,,,
..
0
21
2211
222222121
111212111
11
mn
mmnnmnmm
nnn
nnn
mn
nj
j
n
j
jj
xxx
bxxaxaxa
bxxaxaxa
bxxaxaxa
ts
xxcM a x Z
?
?
???
?
?此时 LP的标准型为
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
???
100
010
001
),,,(
21
)0(
?
????
?
?
?
mnnn
PPPB
初始可行基,
初始基本可行解：
T
mbbbX ),,,,0,,0,0( 21
)0( ???
一般 （ 经过若干次迭代 ）, 对于基 B，
用非基变量表出基变量的表达式 为：
mixabx
n
j
jijiin,2,1,
1
'' ???? ?
?
?
用非基变量表示目标函数的表达式：
?
?
?????
? ???
? ?????
?
?
?
?
?
?
?
?
??
?
? ?
?
??
?
? ?
?
??
??
?
?
?
??
?????
?????
???
??????
n
j
jj
jjjjj
n
j
j
m
i
ijinj
m
i
iin
m
i
jijin
n
j
j
m
i
iin
m
i
n
j
jijin
n
j
jj
m
i
iin
m
i
n
j
jijiin
n
j
jj
m
i
inin
n
j
jj
mn
j
jj
xZ
zcxzcZ
aczbcZxaccbc
xacxcbc
xabcxcxcxcxcZ
1
0
1
0
1
'
1
'
1
0
'
11
'
1 1
'
11
'
1 1
''
1111
)(
,)(
)(
?
?令
令
若 是对应于基 B的基本可
行解, 是非基变量 的检验数, 若对于
一切非基变量的角指标 j,均有 ≤0,则 X(0)
为最优解 。
),,,,0,,0,0( ''2'1)0( mbbbX ???
j? )0(jx
j?
（ 2） 最优性判别定理
（ 3）无“有限最优解”的判别定理
若 为一基本可行解，有
一非基变量 xk,其检验数,而对于
i=1,2,…, m，均有,则该线性规划问题
没有“有限最优解” 。
),,,,0,,0,0( ''2'1)0( mbbbX ???
0?k?
0' ?ika
证明思路 —— 构造性证明,
依据 用非基变量表示基变量的表达式 构造一族
可行解, 其对应的目标函数值趋于无穷大 。
几何意义, 沿着无界边界前进的一族可行解
举例,用非基变量表示基变量的表达式
?
?
?
????
????
4325
4321
636
3
xxxx
xxxx
代表两个约束条件：
?
?
?
????
????
663
3
5432
4321
xxxx
xxxx
x2对应的系数列向量 P2=（ 1,3） T，
当前的换入变量是 X2，按最小比值原则
确定换出变量：
?
?
?
?????
?????
0636
03
4325
4321
xxxx
xxxx
? ? ????
?
?
?
?
?
2/6,1/3m in
3/6
1/3
2
2
2 x
x
x
要求：
于是：
如果 x2的系数列变成 P2’=（ -1,0） T,则用非
基变量表示基变量的表达式就变成；
?
?
?
?????
?????
0606
03
4325
4321
xxxx
xxxx
可行性自然满足,最小比值原则失效,意即 x2的值
可以任意增大 → 原线性规划无, 有限最优解, 。
3,进行基变换
（ 1） 选择进基变量 —— 原则,正检验数 （ 或
最大正检验数 ） 所对应的变量进基, 目的是
使目标函数得到改善 （ 较快增大 ） ；
进基变量对应的系数列称为 主元列 。
（ 2） 出基变量的确定 —— 按最小比值原则确
定出基变量, 为的是保持解的可行性 ；
出基变量所在的行称为 主元行 。
主元行和主元列的交叉元素 称为 主元素 。
思考题
这样进行基变换后得到的新解对应的系数
列向量是否线性独立？
4,主元变换 （ 旋转运算或枢运算 ）
按照主元素进行矩阵的初等行变换 —— 把主
元素变成 1,主元列的其他元素变成 0（ 即主
元列变为单位向量 ）
写出新的基本可行解, 返回最优性检验 。
单纯形法小结
求解思想－－
顶点的逐步转移,
条件是
使目标函数值不断得到改善 。
表格单纯形法求解步骤
第一步,将 LP化为标准型, 并加以整理。
引入适当的松驰变量、剩余变量和人工变量
，使约束条件化为等式,并且约束方程组的系数
阵中有一个单位阵。
（这一步计算机可自动完成）
确定初始可行基，写出初始基本可行解
第二步,最优性检验
计算检验数，检查：
?所有检验数是否 ≤ 0？
是 —— 结束，写出最优解和目标函数最优值；
?还有正检验数 —— 检查相应系数列 ≤ 0？
是 —— 结束，该 LP无“有限最优解”！
?不属于上述两种情况,转入下一步 — 基变换。
确定是停止迭代还是转入基变换？
选择（最大） 正检验数 对应的系数列
为 主元列,主元列对应的非基变量为 换
入变量；
最小比值对应的行为 主元行, 主元行
对应的基变量为 换出变量 。
第三步,基变换
确定进基变量和出基变量。
利用矩阵的 初等行变换 把 主元列变成单
位向量，主元素变为 1,进基变量对应的
检验数变成 0，从而得到一张新的单纯形
表，返回第二步。
第四步 换基迭代（旋转运算、枢运算 )
完成一次迭代，得到新的基本可行解和
相应的目标函数值
该迭代过程直至下列情况之一发生时停止
?检验数行全部变为非正值；
（ 得到最优解） 或
?主元列 ≤0 （最优解无界）
停止迭代的标志（停机准则）
依据：最优性检验的两个定理
最优性判别定理；无“有限最优解”判断定理
计算机求解时的注意点
1,输入数据中的分数, 需 先化为小数再执行输入过程 。
2,每一张迭代表格中由基变量列 （ Basic） 和 B(i)列
（ 解答列 ） 可以读出现行解及相应的目标函数值,
同时显示进基变量和出基变量, 从而很容易识别主
元列, 主元行和主元素 。
3,最终表显示最优解, 最优目标函数值及总的迭代次
数 。 如遇该线性规划无可行解或无, 有限最优解,,
则屏幕将显示有关信息：
NO feasible solution,
或 * * unboundedsolution !!!
五, 各种类型线性规划的处理
1,分类及处理原则：
（ 1） 类型一,目标要求是, Max”,约
束条件是, ≤” 类型 —— 左边加上非负松
弛变量变成等式约束 （ 约束条件标准
化 ）, 将引入的松弛变量作为初始基变
量, 则初始可行基是一个单位阵, 用 原
始单纯形法 求解 。
（ 2） 类型二,目标要求是, Max”,约
束条件是, =”类型 —— 左边引入非负的
人工变量, 并 将引入的人工变量 作为 初
始基变量, 则初始可行基是一个单位阵,
然后 用大 M法或两阶段法 求解 。
（ 3） 类型三,目标要求是, Max”,约
束条件是, ≥” 类型 —— 约束条件标准
化, 左边减去非负的剩余变量, 变成等
式约束, 化为类型二 。
（ 4） 类型四,目标要求是, Min”
① 方法 1—— 化为极大化问题
②方法 2—— 按照极小化问题直接在单
纯形表格上计算处理，但
相应的原则要作改动 。
2,处理人工变量的方法：
（ 1） 大 M法 —— 在约束条件中人为地加入非负
的人工变量, 以便使它们对应的系数列向量构
成单位阵 。
问题：加入的人工变量是否合理？ 如何处理？
在 目标函数中, 给人工变量前面添上一个绝对
值很大的负系数 -M（ M>>0）, 迭代过程中,
只要基变量中还存在人工变量, 目标函数就不
可能实现极大化 —— 惩罚 ！
① 最优表中, 基变量不包含人工变量, 则 最
优解就是原线性规划的最优解, 不影响目标
函数的取值；
② 最优表中, 基变量中仍含有人工变量, 表
明原线性规划的约束条件被破坏, 线性规划
没有可行解, 也就 没有最优解 ！
结 果
问题 结果 ② 中求得的最优解是哪个线性
规划的最优解？ 为什麽？
（ 2） 两阶段法
第一阶段, 建立辅助线性规划并求解,
以判断原线性规划是否存在基本可行解 。
辅助线性规划的结构,目标函数 W为所
有人工变量之和,目标要求是使 目标函
数极小化,约束条件与原线性规划相同。
求解结果
① W最优值 =0—— 即所有人工变量取值全为 0
（ 为什麽？ ）, 均为非基变量, 最优解是原线
性规划的一个基本可行解, 转入第二阶段；
② W最优值 =0—— 但人工变量中有等于 0的基
变量, 构成退化的基本可行解, 可以 转化为情
况 ① ； 如何转化？
选一个不是人工变量的非基变量进基,
把在基中的人工变量替换出来
③ W最优值 >0—— 至少有一个人工变量取值
>0,说明 基变量中至少有 1个人工变量,表明 原
问题没有可行解,讨论结束 。
问题讨论
① 教材 P49辅助线性规划的结构是,目标函
数 W为所有人工变量之和的相反数, 目标要
求是使目标函数极大化, 约束条件与原线性
规划相同 。 这与上述的讨论 是否矛盾？
试比较：
?
?
?
?
?
????
???
?
?
?
?
..
21
ts
xxxM i n Z
mnnn
?
?
?
?
?
?????
???
?
?
?
?
..
21
ts
xxxM a x Z
mnnn
（ 1）
（ 2）
② （ 1）式目标要求改为极大化（或（ 2）式
目标要求改为极小化）行不行？
第二阶段：
将第一阶段的最优解作为初始可行解, 目标
函数换成原问题的目标函数, 进行单纯形迭
代, 求出最优解 。
问题讨论,① 如何实 施？ 需要重新建立初始
单纯形表吗？
实施中，在第一阶段最优表格中 划去
人工变量列,将表头部分和 CB列的价
值系数 换成原问题的价值系数 (把目标
函数换成原线性规划的目标函数 )，继
续迭代，直至求出最优解。
② 在大 M法中，当人工变量出基后能
否 立即划去 该人工变量所在的系数列？
3,用表格单纯形法直接计算极小化线性规划
时要修改哪些原则？
（ 初始表？ 最优解判别？ 换入变量？ 换出变
量？ 旋转运算？ 引入人工变量？ ）
? 最优性判别,所有检验数非负
? 换入变量的选择原则,（ 最小 ） 负检验数
所对应的变量进基, 以保证目标函数值 （ 较
快 ） 减小；
? 用大 M法求解时, 在 目标函数中人工变量
的前面添上一个很大的正系数 M；
六, 迭代过程中可能出现的问题及处理方法
1,为确定出基变量要计算比值, 该 比值 =
解答列元素 /主元列元素 。 对于主元列的 0
元素或负元素是否也要计算比值？
（ 此时 解的可行性自然满足, 不必计算 ；
如果 主元列元素全部为 0元素或负元素,
则 最小比值失效, 线性规划 无, 有限最优
解, ）
2,现若干个相同的最小比值怎麽办？
（ 说明 出现了退化的基本可行解, 即非 0分量
的个数小于约束方程的个数 。 按照, 摄动原理,
所得的规则, 从相同比值对应的基变量中选下
标最大的基变量作为换出变量 可以避免出现
,死循环, 现象 ）
3,选择进基变量时, 同时有若干个正检验数,
怎麽选？
（ 最大正检验数或从左至右第 1个出现的正
检验数所对应的非基变量进基 ）
课堂练习,直接按极小化问题求解下面的 LP：
?
?
?
?
?
??
?
???
??
0,0
3
22
..
2
21
1
21
21
xx
x
xx
ts
xxM i n Z
CB XB
cj
xj
b
1 2 0 0 M
X1 X2 X3 X4 X5
M
0
X5
X4
2
3
-1 2 -1 0 1
1 0 0 1 0
2/2
_
-Z -2M 1+M M 0
2-2M 0
2
0
X2
X4
1
3
-1/2 1 -1/2 0 1/2
1 0 0 1 0
-Z -2 2 0 1 0 M-1
?j
第三次作业 P71 1-6 三个小题
9月 26日交
由最优表得：
最优解为 X*=（ 0,1,0,3,0） T,
相应的目标函数最优值为 Zmin=2
