1/31/3000-4/32/31009x31-1001
01x21-2/31/30014x1-31000-1-0010-21x31-
-100101x214-2100312x40x5x4x3x2x1bXBCB0
011-3cj由于人工变量x6=x7=0,所以（0,1,1,12,0）T是该线性规划问题的基可行解。于是转入第二阶段
运算：此时达到该LP问题的最优解：X=(4,1,9,0,0)T;目标函数值Z=-2。三、单纯形法中存在的问题
1.存在两个以上的最大正检验数。选择任何变量（对应最大正检验数）作为换入变量。2.最小比值相同。LP问题出现退化现象，
即基变量取值为0000-61/2-203/4010001001x700103-
1/2-121/20x600019-1-81/40x50x7x6x5x4x3x2x1
bXBCB3/4-201/2-6000
cj00-3217/240010001001x70010-153/24
00x6000436-4-3210x13/4x7x6x5x4x3x2x1bXBCB
3/4-201/2-6000cj选取
x1为换入变量；按Bland算法，选取下标最小的x5为换出变量，得下表：此时换出变量为x1，换入变量为x4，迭代
后目标函数值不变，继而出现了循环现象，达不到最优解。解决退化的方法有：“摄动法”、“辞典序法”、Bland规则等197
4年Bland提出Bland算法规则：3.最小比值原则失效-30011-12cj-Zj101-34
x23110-26x30x4x3x2x1bXBCB0032cj经过一次迭代后可得右表
4.在最优表中出现某非基变量检验数为01/3-2/30014x13-10000-36
cj-Zj01/20106x24-1/32/31004x30x5x4x3x2x1b
XBCB-10000-36cj-Zj001018x131/40-3/4103x24
-1/213/2006x40000430cj-Zj结论：若线性规划问题存在某非基变量检验数为0
,而其对应列向量Pk≤0,仍可判断线性规划问题有无穷多最优解。式中的X是否能由单纯形法求得？为什么？
补充作业2-2单纯形法总结其它
情形以上讨论都是针对标准型的，即求目标函数极大化时的情况。当要求目标函数极小化时，一种情况是将其化为标准型。如果不化为标准型，
只需在上述1，2点中把σj≤0改为σj≥0，第3点中将σm+k＞0改写为σm+k＜0即可。五、基变换1.换入变量的
确定2.换出变量的确定则第l个约束方程对应的基变量xl为换出变量。六、迭代(旋转运算)上述讨论的基可行解的转换方法是用
向量方程描述的，在实际计算时不太方便，因此下面介绍系数矩阵法。考虑以下形式的约束方程组一般线性规划问题的约束方程组中加入松弛变
量或人工变量后，很容易得到上述形式设x1,x2,…,xm为基变量，对应的系数矩阵是m×m单位阵I，它是可行基。令非基变量xm
+1,xm+2,…,xn为零，即可得到一个基可行解。若它不是最优解，则要另找一个使目标函数值增大的基可行解。这时从非基变量中确定
xk为换入变量。显然这时θ为在迭代过程中θ可表示为其中是经过迭代后对应于的元素值。
六、迭代(旋转运算)按θ规则确定xl为换出变量，xk,xl的系数列向量分别为六、迭代(旋转运算)为了使xk与xl进
行对换，须把Pk变为单位向量，这可以通过(1-33)式系数矩阵的增广矩阵进行初等变换来实现。六、迭代(旋转运算)变换的步骤
是：(1)将增广矩阵(1-34)式中的第l行除以alk，得到(2)将(1-34)式中xk列的各元素，除alk变换为1以
外，其他都应变换为零。其他行的变换是将(1-35)式乘以aik(i≠l)后，从(1-34)式的第i行减去，得到新的第i行。由
此可得到变换后系数矩阵各元素的变换关系式是变换后的新元素。六、迭代(旋转运算)六、迭代运算例6
迭代运算示例3.1单纯型表3.2计算步骤第三节单纯形法的步骤3.1单纯型表为了便于理解计算关系
，现设计一种计算表，称为单纯形表，其功能与增广矩阵相似。将(1-22)式与目标函数组成n+1个变量，m+1个方程的方程组。
线性规划的方程组线性规划的方程组为了便于迭代运算，可将上述方程组写成增广矩阵形式清华大学出版社线性规划的方程组
若将z看作不参与基变换的基变量，它与x1,x2,…,xm的系数构成一个基，这时可采用行初等变换将c1,c2,…,cm变换为零，使其
对应的系数矩阵为单位矩阵。得到线性规划的方程组表2-2（P38）清华大学出版社线性规划的方程组表2-2的说明X
B列中填入基变量，这里是x1，x2,…，xm；CB列中填入基变量的价值系数，这里是c1,c2,…,cm；它们是与基变量相对应的；
b列中填入约束方程组右端的常数；cj行中填入基变量的价值系数c1,c2,…,cn；θi列的数字是在确定换入变量后，按θ规则计
算后填入；最后一行称为检验数行，对应各非基变量xj的检验数是3.2计算步骤表2-2称为初始单纯形表，每迭代一步构造一
个新单纯形表。计算步骤：(1)按数学模型确定初始可行基和初始基可行解，建立初始单纯形表。(2)计算各非基变量xj的检验数
，检查检验数，若所有检验数则已得到最优解，可
停止计算。否则转入下一步。4.2计算步骤(3)在σj＞0,j=m+1,…,n中，若有某个σk对应xk的系数列向量Pk≤
0，则此问题是无界，停止计算。否则，转入下一步。(4)根据max(σj＞0)=σk，确定xk为换入变量，按θ规则
计算清华大学出版社3.2计算步骤(5)以alk为主元素进行迭代(即用高斯消去法或称为旋转运算)，把xk所对应的列向
量将XB列中的xl换为xk，得到新的单纯形表。重复(2)～(5)，直到终止。3.2计算步骤现用例
1的标准型来说明上述计算步骤(1)取松弛变量x3,x4,x5为基变量，它对应的单位矩阵为基。这就得到初始基可行解X(
0)=(0,0,8,16,12)T将有关数字填入表中，得到初始单纯形表，表中左上角的cj是表示目标函数中各变量的价值系数。在CB
列填入初始基变量的价值系数，它们都为零。单纯形表算法
X(0)＝(0,0,8,16,12)TO点以[1]为主元素进行旋转运算，x1为换入变量，x3为换
出变量0qi300x5x2x3x40x4x3XBb
sj0x1CB2cjx1cjx2x3x4x51
4020410001000123000b816
12XBx3x4x5CB000以[4]为主元素进行旋转运算，x2为换入变量，x5为换出变量
sj23000qi8/2—12/4[4]x23主元列主元行000
1/43140101600110-1/22X(1)＝(0,3,2,16,0
)TQ4点200-3/4016/42/1—[1]此时达到最优解。X=(4,
2),maxZ=14。0qi300x5x2x3x40x4x23
XBbsjx1CB2cj0qi3
00x5x2x3x4x23x1XBbsj2
x1CB2cj0001/4310-201/40x120
110-1/22[2]0-412808/212—x500-21
/2140101/40401/2-1/800210-3/2-1/8
00X(3)＝(4,2,0,0,4)TQ2点X(2)＝(2,3,0,8,0)TQ3点
以[2]为主元素进行旋转运算，x5为换入变量，x4为换出变量一、最小化问题最优解判别第四节LP问题的进一步讨论
前面讨论的LP问题都是以最大化目标函数作为标准型的，但也有用最小化目标函数作为LP问题标准型的构成要素的情况。二者
的区别如下：按最小比值规则maxZ=CXAX=b，X30minZ=CXAX=b，X30
￡030min{sj|sj<0}max{sj|sj>0}换入变量xk换出变量xl最优解的sj标准型
比较条目二、人工变量法化为标准型化标准型时，若找不到单位矩阵，可人为添加非负变量（人工变量）凑
成单位矩阵。因人工变量是虚拟的变量，无任何物理意义，它们的取值最终必须为零，才能保证约束方程不发生变化。
为此，必须把人工变量从基变量中替换出去而变成非基变量，则LP问题有解；若最优解中含有人工变量，则LP问题无可行解。这是L
P问题无解的判别条件。加入松弛变量x4;剩余变量x5;人工变量x6,x7例7人工变量示例（1）基本思路（2
）目标函数的处理（3）计算1.大M法(M为任意大的正数)例8(P42,例8)3M-10M001-M
-1-100010-21x311-21-100101x6M--10010
-2310x4000M01-3M1-M-3+6M1100010-21x7M3/2
01-1021-43x6M1100011-2111x40x7x6x5x4x3x
2x1bXBCBMM0011-3cj结果得:X=(4,1,9,0,0)TZ=-2
M-2/3M-1/31/31/3000-7/34/3-4/32/31009x31-21-1
00101x21-5/32/3-2/31/30014x1-3M+1M-11000-1
-100010-21x31--21-100101x214-52-2100
312x40x7x6x5x4x3x2x1bXBCBMM0011-3cj（接上表）
将LP问题分成两个阶段来考虑第I阶段:不考虑原问题是否存在可行解，给原LP问题加入人工变量，并构造仅含人工变
量的目标函数和要求最小化；然后用单纯形法求解，若得W=0，则进行第二阶段计算，否则无可行解。第II阶段：将第一阶
段得到的最终表除去人工变量，将目标函数行的系数换为原问题的系数，作为第二阶段的初始表。2.两阶段法加入松弛变量x4;剩
余变量x5;人工变量x6,x7用单纯形法求解第一阶段的结果得：例9(P43,例9)两阶段法示例11000
00-000010-21x30--21-100101x204-52-21
00312x4030100-10-100010-21x301-21-10
0101x61--10010-2310x400010-3-1611000
10-21x713/201-1021-43x611100011-2111x4
0x7x6x5x4x3x2x1bXBCB1100000cj此时，达到第一阶段的最优解，W=
0第二节单纯形法SimplexMethod由线性代数知，对LP标准型问题，理论上可以求出
所有基解（枚举法），再通过观察找出其中基可行解，进而找出最优解。但如果变量和方程较多，比如m=50，n=100，所有基解有可能达1
029个，即使计算机每秒能求解1亿个这样的方程组，也需要30万亿年！因此，必须寻求有效的算法。为加快计算速度，算
法必须具有两个功能，一是每得到一个基可行解，就能检验是否已经最优，若是，停止。二是若不是最优，要保证下一步得到的基可行解不劣于当前
解。基于线性代数原理，并将上述功能贯穿于算法过程，这就是线性规划的单纯形法。一、基本思想化LP问题为标准型，确定一个初
始基可行解检验解的最优性结束Y旋转运算（枢轴运算）确定另一个基可行解N基本思路：化LP问题为标准型，从可行域的某个
基可行解（一个顶点）开始，转换到另一个基可行解（另一个顶点），并使目标函数值得到改善，如此反复，从而求得问题的最优解。其实质是逐
步迭代（逼近）法。二、基本原理举例1.初始基可行解的确定要得到一个初始基可行解，必须找到一个初始可行基。由于典型示例
标准化后，x3、x4、x5的系数列向量构成单位矩阵，该矩阵B0是一个基，并且是一个可行基（可以证明，标准化后的单位矩阵一定是可行基
）。例5(P28,例6)举例约束条件(1-12)式的系数矩阵为从(1-12)式可看到x3,x4,x5的系数构成的
列向量举例P3,P4,P5是线性独立的，这些向量构成一个基B。对应于B的变量x3,x4,x5为基变量.从(1-
12)式中可以得到（1-13）举例将(1-13)式代入目标函数(1-11)：得到当令非基变量x1=x2=0，便得
到z=0。这时得到一个基可行解X(0)X(0)=(0,0,
8,16,12)T本基可行解的经济含义是：工厂没有安排生产产品Ⅰ、Ⅱ，资源都没有被利用，所以工厂的利润为z=0。举例
从分析目标函数的表达式(1-14)可以看到：非基变量x1,x2(即没有安排生产产品Ⅰ，Ⅱ)的
系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品Ⅰ或Ⅱ，就可以使工厂的利润指标增加。
所以只要在目标函数(1-14)的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与基变量进行对换
。举例如何确定换入、换出变量一般选择正系数最大的那个非基变量x2为换入变量，将它换到基变量中，同时还要确定基变量中哪一
个换出来成为非基变量。可按以下方法来确定换出变量：分析(1-13)式，当将x2定为换入变量后，必须从x3,x4,x5中确定一个
换出变量，并保证其余的变量仍然非负，即x3,x4,x5≥0。举例如何确定换入、换出变量当x1=0时，由(1-13)式得
到举例如何确定换入、换出变量当x2取何值时，才能满足非负要求呢？从(1-15)式可看出，只有选择
x2=min(8/2,-,12/4)=3时，才能使(1-15)式成立。因当x2=3时，基变量x5=0，这就决定
用x2去替换x5。以上数学描述说明，每生产一件产品Ⅱ，需要用掉的各种资源数为(2，0，4)。由这些资源中的薄弱环节，就
确定了产品Ⅱ的产量。这里就是由原材料B的数量确定了产品Ⅱ的产量x2=12/4=3件。举例如何确定换入、换出变
量为了求得以x3,x4,x2为基变量的一个基可行解和进一步分析问题，需将(1-13)中x2的位置与x5的位置对换，得到举例
将(1-16)式中x2的系数列向量变换为单位列向量。其运算步骤是：③′=③/4；①′=①-2×③′;②′=②,并将结果仍按原
顺序排列有：高斯消去法举例再将(1-17)式代入目标函数(1-11)式得到举例从目标函数的表达式(
1-18)可看到，非基变量x1的系数是正的，说明目标函数值还可以增大，即X(1)还不是最优解。于是，再用上述方法确
定换入、换出变量，继续迭代，得到另一个基可行解X(2)X(2)=(2,3,0,8,0)T再经过一次迭代，又得到一
个基可行解X(3)X(3)=(4,2,0,0,4)T而这时得到目标函数的表达式是：
z=14?1.5x3?0.125x4(1-19)
再检查(1-19)式，可见所有非基变量x3,x4的系数都是负数，这说明若要用剩余资源x3,x4，就必须支付附加费用。
所以当x3=x4=0时，即不再利用这些资源时，目标函数达到最大值。所以X(3)是最优解。即当产品Ⅰ生产4件，产品Ⅱ生产2件
时，工厂可以得到最大利润。小结通过上例，可将每步迭代得到的结果与图解法做一对比。例1的线性规划问题是二维的，即有两个变量
x1,x2。当加入松弛变量x3,x4,x5后，变换为高维的。这时可以想象，满足所有约束条件的可行域是高维空间中的凸多面体(凸集)。
该凸多面体上的顶点，就是基可行解。初始基可行解为X(0)=(0,0,8,16,12)T，对应于图1-2中的原点(0，0)；X(1
)=(0,3,2,16,0)T对应于图中的Q4点(0，3)；X(2)=(2，3，0，8，0)T对应于Q3点(2，3)；最优解X(
3)=(4，2，0，0，4)T相当于图中的Q2点(4，2)。从初始基可行解X(0)开始迭代，依次得到X(1)，X(2)，X(3
)，相当于图中的目标函数平移时，从0点开始，首先碰到Q4，然后碰到Q3，最后达到Q2。结论：
（1）在标准化的LP问题的约束系数矩阵中，只要存在单位矩阵，就可求得初始基可行解；（2）基变量确定后，目标
函数和基变量均可表示成非基变量的代数和形式，从而便于求出基可行解及相应的目标函数值。（3）在非基变量的代数和形式
表示的目标函数中，若非基变量的系数（称为检验数）为正，则目标函数值还有增加的可能，表明当前的基可行解不是最优解。（4
）单纯形法在寻找新的可行基时，是以当前的可行基为基础的，即把当前的可行基中某一列用非基向量替换，从而形成新的可行基。总
结（5)确定换入变量：一般选择正系数最大的非基变量为换入变量。本例为非基变量x2。
（6)确定换出变量：其依据是（a）保证换出的变量取值为0，变成非基量；
（b）其它的变量取值为非负。三、初始基可行解的确定为了确定初始基可行解，要首先找出初始可行基，其方法如下。(1)直接
观察(2)加松弛变量(3)加非负的人工变量三、初始基可行解的确定从线性规划问题的系数构成的列向量Pj(
j=1,2,…,n)中，通过直接观察，找出一个初始可行基(1)直接观察对所有约束条件为“≤”形式的不等式，利
用化标准型的方法，在每个约束条件的左端加上一个松弛变量。经过整理，重新对xj及aij(i=1,2,…,m;j=1,2,…,n)
进行编号，则可得下列方程组（x1,x2,…,xm为松弛变量）：(2)加松弛变量三、初始基可行解的确定于是，(1-22)
中含有一个m×m阶单位矩阵，初始可行基B即可取该单位矩阵。将(1-22)式每个等式移项得三、初始基可行解的确定
令xm+1=xm+2=…=xn=0，由(1-23)式可得xi=bi(i=1,2,…,m)得到一个初始基可行解。又因bi
≥0(在1-3节中已做过规定)，所以得到一个初始基可行解X=(x1,x2,…,xm,0，…，
0)Tn?m个
=(b1,b2,…,bm,0，…，0)T
n?m个三、初始基可行解的确定对所有约束条件为“≥”形式的不等式及等式约束情况，若不存在单位矩阵时，可
采用人造基方法。即对不等式约束，减去一个非负的剩余变量，再加上一个非负的人工变量；对于等式约束，再加上一个非负的人工变量这样
，总能在新的约束条件系数构成的矩阵中得到一个单位矩阵。(3)加非负的人工变量三、初始基可行解的确定四、最优性检验及解
的判别1.检验数公式补充作业2-1：请给出公式（2）的推导过程。2.
最优性检验与解的判别设X(0)=(b￠1,b￠2,…,b￠m,0,…,0)T为对应于基B的一个基可行解
。对于最大化问题，最优性检验与解的判别如下：（1）唯一最优解对于一切j=m+1,…,n，有sj<
0，则X(0)为唯一最优解。（2）无穷多最优解对于一切j=m+1,…,n，有sj￡0，且至少有一个sm+k=0，则该LP问题有无穷多最优解，X(0)为其中之一。（3）无界解在j=m+1,…,n中，至少有一个sm+k>0，且对i=1,…,m，有a￠i,m+k￡0，则该LP问题具有无界解。若为一个基可行解，对于一切j=m+1，…,n，有σj≤0，又存在某个非基变量的检验数σm+k=0，则线性规划问题有无穷多最优解。证:只需将非基变量xm+k换入基变量中，找到一个新基可行解X(1)。因σm+k=0，由(4)式知z=z0，故X(1)也是最优解。由2.2节的定理3可知，X(0)和X(1)连线上所有点都是最优解。（2）无穷多最优解论证清华大学出版社若为一基可行解，有一个σm+k＞0，并且对i=1,2,…，m，有a‘i,m+k≤0，那么该线性规划问题具有无界解(或称无最优解)。证:构造一个新的解X(1)，它的分量为（3）无界解论证因，所以对任意的λ＞0都是可行解，把x(1)代入目标函数内，得到z=z0+λσm+k因σm+k＞0，故当λ→+∞，则z→+∞，故该问题目标函数无界。（3）无界解论证 |
|
