第三章
3.1单纯形法
单纯形法求解线性规划的思路：一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或者最小值为止。这样问题就得到了最优解。【2】 单纯形法的计算步骤如下：
第一步：对线性规划数学模型进行标准化，构造一个初始基可行解； 第二步：判断当前基本可行解是否是最优解；
第三步：若当前解不是最优解，则进行基变换迭代到下一个基本可行解。 例：
目标函数
2132m ax x x z += (3-1)
满足约束条件 ???????≥≤≤≤+0
,124164822121
21x x x x x x (3-2)【3】
在上述问题约束条件中加入松弛变量3x ，4x ，5x ，使不等式变成等式。这时得到标准型：
5432100032m ax x x x x x z ++++= (3-3)
??????
?≥=+=+=++0
,,,,1241648
254321524
1321x x x x x x x x x x x x (3-4) 约束方程(3-4)的系数矩阵
()????
?
??==100400100400121,,,,5
4321P P P P P A
从（3-4）式可以看到543,,x x x 的系数列向量
????? ??=0013p ，????? ??=0104p ，????
? ??=1005p
是线性独立的，这些向量构成一个基
()????
?
??==10001000154
3
P P P B
对应B 的变量543,,x x x 为基变量，从（3-4）式中可以得到
???
??-=-=--=25
242
1341241628x
x x x x x x （3-5） 将(3-5)式代入目标函数（3-1）式得到
21320x x z ++=
当令非基变量021==x x 便得到z=0。这时得到一个基可行解()0X
()()T
X 12,16,8,0,00=
将有关数字输入表中，得到初始单纯形表，见表 3-6
表3-6中左上角的j c 是表示目标函数中各变量的价值系数。在B c 列填入初始基变量的价值系数，它们都为零，各非基变量的检验数为
2)004010(2111=?+?+?-=-=z c σ
3)400020(3222=?+?+?-=-=z c σ
（1）因检验数都大于零，且21,p p 有正分量存在，转入下一步；
（2）332m ax m ax 21==），（），（σσ，对应的变量2x 为换入变量，计算θ
3)4/12,,2/8min(0min 22t
=-=???
?
??>=i i i a a b θ
它所在行对应的5x 为换出变量。2x 所在列和5x 所在行的交叉处[4]称为主元素或轴元素。
（3）以[4]为主元素进行旋转运算，即初等行变换，使2p 变为T
），，（100，在B X 列
中将2x 替换5x ，于是得到新表3-7
b 列的数字是3x =2，4x =16，2x =3。于是得到新的基可行解()T
X ），，，，（0162301=，
目标函数的取值z=9
（4）检查表3-7的所有j j z c -，这时211=-z c ；说明1x 应为换入变量。重复（1）~（4）的计算步骤，得表3-8
。
大，于是得到最优解
()T
），，，，（40024x x 3*==