【解】首先将数学模型化为标准形式
max Z 3 x1 2 x2 x3 4 x1 3 x2 x3 x4 4 x x 2 x x 10 1 2 3 5 2 x1 2 x2 x3 1 x j 0, j 1,2, ,5
最优解X＝(31/3，13，19/3，0，0)T；最优值Z＝152/3 注意： (1)M 是一个很大的抽象的数，不需要给出具体的数 值，可以理解为它能大于给定的任何一个确定数值； (2)人工变量是帮助我们寻求原问题的可行基，人工变
量从模型中推出后，说明原问题有可行解，但不能
肯定有最优解。
1.5 单纯形法 Simplex Method
1.6 线性规划的对偶模型 Dual model of LP
【例1】 某企业计划生产甲乙两种产品，生产单位产品所需设备
A、B、C台时及产品的单位利润如下表：
生产能力 工时/天
产品 车间（资源） A B C
利润（百元/件）
单耗（工时/件） 甲 乙 x1 x2 1 0 0 2 3 4 3 5
8 12 36
max Z C X A X b X 0
由于 X s 对应的系数矩阵为单位阵，故容易确定初始基变量为 X s ， 得到如下初始单纯形表: C X A -C 0 Xs E 0
CB Xs
b 0
而对于一般的基B为
1
B A ( B A B ),
A 的子矩阵，
1 1
1.5 单纯形法 Simplex Method
引入松弛变量
X s ( xn1 , xn 2 , , xn m )
max Z CX 0 X s AX EX s b X 0, X s 0
T
化为标准形如下：
1.5 单纯形法 Simplex Method
X 记 X , A A E , C C 0, 则上述标准形式为 X s
式中x4，x5为松弛变量，x5可作为 一个基变量，第一、三约束中分 别加入人工变量 x6 、 x7 ，目标函 数中加入―Mx6―Mx7一项，得到 人工变量单纯形法数学模型
4 x1 3 x2 x3 x4 x6 4 x x 2x x5 10 1 2 3 2 x 2 x x x 1 1 2 3 7 x j 0, j 1,2, ,7
1.5 单纯形法 Simplex Method
maxZ CX AX b s.t. X 0
maxZ CX AX b s.t. X 0
1.大M法 2.两阶段法
maxZ CX AX IX S b s.t. X , XS 0
maxZ CX AX IX S b s.t. X , XS 0
大值，因此原问题只要有可行解，新的线性规划问
题的最优解中人工变量的取值一定为0， 这种方
法称为大M单纯形法（简称大M法）。
1.5 单纯形法 Simplex Method
大M法中加入人工变量后新的线性规划问题为
max Z’=c1x1+c2x2+…+cnxn –Mxn+1 – … –Mxn+m
a11x1 a12 x2 a1n xn xn 1 b1 a x a x a x x b 21 1 22 2 2n n n2 2 a x a x a x x b m1 1 m2 2 mn n nm m x 0 , j 1 , 2 , , n , n 1 , , n m j
3
－6
5
0
－1
0 0 0 0
1 0 0
3/5
0
-1 σj 2
x5
x3 x2
Z 0x4 + 0x50 －Mx6 8 max－ 3x2 x3 +0 1 Mx 7 0 33 x1 2 x x 2 x x 10 1 6M-5 2 3 -5M 5 0 2 x1 2 x2 x3 x7 1 3/5 1 0 － 6/5 x j 0, j 1,2, ,7 31/5 3/5 0 0 3 x2 x32 x4 1 x6 4 0 1 4 x12 －
1.5 单纯形法 Simplex Method
1.5.2 大M和两阶段单纯形法 在实际问题中有些模型并不含有单位矩阵，为
了得到一组基向量和初始基可行解，在约束条件的
等式左端加一组虚拟变量，得到一组基变量。这种
人为加的变量称为人工变量，构成的可行基称为人
工基，用大M法或两阶段法求解，这种用人工变量 作桥梁的求解方法称为人工变量法。
max Z 3 x1 2 x2 x3
1.5 单纯形法 Simplex Method
4 x1 3 x2 x3 x4 4 x x 2 x x 10 1 2 3 5 2 x1 2 x2 x3 1 x j 0, j 1,2, ,5 max Z 3 x1 2 x2 x3 +0x4 +0x5－Mx6 Mx7
Simplex Method
因为r(B)=m(或|B|≠0)所以B -1存在，因此可有
BX B b NX N X B B (b NX N ) B 1b B 1 NX N 令非基变量XN=0，XB=B—1b，由B是可行基的假设，
则得到基本可行解 X=(B－1b，0)T 消去目标函数中的基变量，于是目标函数可写成
新的线性规划问题的最优解中人工变量取值必为0，否则原 问题无可行解，在得到新问题的最优解后，去掉人工变量便得到 原问题的最优解，相应的在新问题的最终单纯形表中去掉人工变 量那一块即为原问题的最优单纯形表。
注: (1) 迭代过程中人工变量一旦出基就不会再进基，所以当
某个人工变量出基后，其对应的列可不再计算，以减少计算量；
X B 则X可表示成 X , 同理将C 写成分块矩阵 X N CB=(C1,C2,…,Cm), CN=(Cm+1Cm+2，…，cn), C=(CB，CN)，
则 AX=b 可写成
X B ( B，N ) BX B NX N b X N
1.5 单纯形法
建立总收益最大的数学模型。
产品 【解】设x1，x2分别为产品 甲、 乙的产量，则线性规划数学模 车间 型为： （资源） max z 3 x1 5 x 2 minW 8 y 12 y 36 y 1 2 3 8 x1 y1 A y1 3 y3 3 x2 6 y2 B s .t . 3 x1 4 x 2 36 2 y2 4 y3 5 C y 3 x1 , x 2 0 利润（百
1.5 单纯形法 Simplex Method
一、 大M 单纯形法
对于线性规划问题的标准形式：
max Z=c1x1+c2x2+…+cnxn
a11 x1 a12 x2 a1n xn b1 1、思想： a x a x a x b 21 1 22 2 2 n n 2 a x a x a x b m1 1 m2 2 mn n m x 0 , j 1 , 2 , , n j
C CB B 1 A C 0 CB B 1 A E C CB B 1 A CB B 1
C X 0 Xs b
CB
XB
B-1A
CB B-1A-C
B-1
CB B-1
B-1b
CB B-1 b
σj
1.6 线性规划的对偶模型
Dual Model of LP
一、引例
1
X B Z (CB , C N ) CB X B C N X N X N CB ( B 1b B 1 NX N ) CN X N
CB B 1b (CN CB B 1 N ) X N
1.5 单纯形法
Simplex Method
CB XB B
1.5 单纯形法
Simplex Method
不妨假设A＝(P1, P2, … ,Pn)中前m个列向量构成一个可
行基，记为B=(P1, P2 ,… ,Pm)。矩阵A中后n－m列构成
的矩阵记为N＝(Pm+1, … ,Pn), 则A可以写成分块矩阵
A=(B，N)。对于基B，基变量为XB=(x1, x2 ,… , xm )T, 非基变量为XN=(xm+1, xm+2,…, xn)T。
(2)在加入人工变量时，实际上不一定每个约束都加入人工变量， 例如某约束是“≤”型，则在加入松弛变量后，该松弛变量可作 为基变量；
1.5 单纯形法
Simplex Method
解的判断 唯一最优解的判断：最优表中所有非基变量的检验 数非零,则线性规划具有唯一最优解。 多重最优解的判断: 最优表中存在非基变量的检验 数为零,则线性规划具有多重最优解。 无界解的判断 : 某个 σk>0 且 aik≤ ０ (i=1 ， 2,…,m) ，则 线性规划具有无界解。 无可行解的判断：当用大M单纯形法计算得到最优解 并且存在非零人工变量时，则表明原线性规划无可行 解。
1.5 单纯形法 Simplex Method
新约束要与原约束等价当且仅当所有的人工变
量取值为零，为确保引入人工变量后新的线性规划
问题与原线性规划问题求解一致，我们在新的线性 规划目标函数中设人工变量的系数为-M（M>0为一 充分大的数），其作用为罚因子，这样只要人工变 量是基变量且取值大于0,目标函数就不可能达到最
1.5 单纯形法 Simplex Method
由于系数矩阵A中不包含m×m 维单位子矩阵，我们 在每个约束中人为的加入一个变量，将约束化为