第二章 单纯形法

11
z=840 - 40x3+15x5 x1=6 - x3 + x5 x4= 18+3x3 - 2x5 x2=12 - 1/2 x5
x2 x(2) B
(6,12) (0,12) A (15,7.5)
x(3) x(4) C
(0,0) 0
D
z=40x1+50x2
x1
x(1)
12
单纯形法小结： 单纯形法小结： 单纯形法是这样一种迭代算法——如下图 单纯形法是这样一种迭代算法 如下图… 如下图 非基变量的系数的系数全为负值时 的系数的系数全为负值时， 当z(k)中非基变量的系数的系数全为负值时，这时的基 本可行解x 即是线性规划问题的最优解，迭代结束。 本可行解 (k)即是线性规划问题的最优解，迭代结束。
证 ： 只只 只 非 基 变 量 新基可行解 X ，因 知 z = z0 , 故 X
(1) (1)
x m + k 换 入 基 变量 中 ， 找 到 个
σ m + k = 0,由 z = z0 +
X
(0)
j = m +1 (1)
∑σ
n
j
xj
也是 最 优 解 ， 故
, X 连连连所
19
有 有 都是 最 优 解。
= 36 – 3x1 x2 = 12
- 1/ 2 x 5
- 1/2 x5
(2)“ ∵ 15>0
不是最优解 ∴ x(3)不是最优解
(3)" 选x5从0↗， x3 =0 ↗ x1=6 + x5 ≥ 0
x4= 18 - 2x5 ≥0 x2=12- 1/2 x5 ≥0 x5=min( 18/2 , 12/1/2 ) =9 x5进基， x4出基。 进基， 出基。

s.t.
32x1x133x2x22xx33
100 120
x1, x2, x3 0
CB XB b 0 x4 100 0 x5 120
OBJ = 0 zj cj-zj
40 45 24 0 0
x1 x2 x3 x4 x5
23110 33201 00000 40 45 24 0 0
求解过程：
序
40 45 24 0 0
基本步骤：
始
确定初试基础可行解
检查是否为
是
最优解？
否 确定改善方向
求新的基础可行解
求最优解的目标函数值
1、初始基本可行解的确定
对目标函数为(MAX≤)形式的线性规划背景模型，通过标准化， 每一个约束方程引入一个松弛变量，松弛变量为基变量，其 他变量为非基变量，得到一个初始基本可行解。
n
max f (x) cj xj j 1
cB
p
' j
c ia
' ij
,
j
m
1,
n;
机会成本
i1
j c j z j, j m 1, n ;
检验数
线性规划问题的典式展开式：
max z cBB1b (cm1 cB pm' 1)xm1 (cj cB p'j )xj
(cn cB pn' )xn
x1 x2
a x ' 1,m1 m1
a1', j xj
a' 1,n
xn
b1'
a x ' 2,m1 m1a2' , xja' 2,n
xn
b2'
xm
a x ' m,m1 m1

最小比值规则
当确定进基变量后, 当确定进基变量后,以进基变量的系数列向量 中的正数为分母, 中的正数为分母,以相应的方程右端常数为分子求 最小比值,所得到的最小比值的分母就是主元 主元. 最小比值,所得到的最小比值的分母就是主元.主 元所在的方程中的基变量就是离基变量 离基变量. 元所在的方程中的基变量就是离基变量.即:
bi bl min α ik > 0 = a ik a lk
令新的非基变量 x3 = x 4 = 0 ,得到新的 基本可行解: 基本可行解: T 经济含义—— 经济含义—— 分别生产甲,乙产品20 20个 分别生产甲,乙产品20个,此时可获得 利润200百元. 200百元 利润200百元.
几个名词
进基, 进基,进基变量 离基, 离基,离基变量 最大检验数规则 最小比值规则 主元/ 主元/主方程 迭代(旋转运算) 迭代(旋转运算)
增加单位产品甲比乙对目标函数 的贡献值大(600>400),故先把非 的贡献值大(600>400),故先把非 ), 变成基变量, 基变量 x1 变成基变量,称为让 x1 进基, 进基变量. 进基,同时称 x1 为进基变量.
R( A) = R( A, b ) = 3 < 5
则该函数约束等式方程组有无穷多组解. 则该函数约束等式方程组有无穷多组解.
分析目标函数表达式
max z = 6 x1 + 4 x 2 + 0 x3 + 0 x 4
非基变量的系数都是正数,若将它们转换 非基变量的系数都是正数, 为基变量,目标函数值则就会可能增加. 为基变量,目标函数值则就会可能增加. 经济含义:每分别多生产一个单位产品甲, 经济含义:每分别多生产一个单位产品甲, 目标函数值分别增加6 乙,目标函数值分别增加6,4,即利润分 别增加600 600元 400元 别增加600元, 400元.

4x1 = 16
3 4x2 = 12
X（1）10 Q4 X（0） O
Q2
Q1
X（3）
x1+2x2 = 8
x1
13/53
杨晓艺 数学建模（公修）
§2.2 单纯形法的计算步骤
确定初始基础可行解 检查是否为 最优解？ 否 确定改善方向 求新的基础可行解 是
求Hale Waihona Puke 优解的目标函数值杨晓艺 数学建模（公修）
14/53
xl a1k alk 1 alk amk alk
xm 0
xm 1
' a1, m 1
xk 0
xn
' a1 n
b b1' bl' ' bm
0
al' ,m 1
1
' aln
1
' am , m 1
0
' amn
杨晓艺 数学建模（公修）
20/53
数学建模（公修）
第2章 单纯形法
1
主要内容
2.1 2.2
单纯形法的引入
单纯形法的计算步骤
2.3
单纯形法的进一步讨论
杨晓艺 数学建模（公修）
2/53
单纯形方法的基本思路
先找到一个基可行解（初始基可行解），检验其是否为 最优解，否则，再找到一个使目标函数所改进的基可行解， 再进行检验，反复迭代，直至找到最优解或判定问题无界。
杨晓艺 数学建模（公修） 10/53
确定了换入变量x2 ，换出变量x5 以后，得到新的消 去系统（用非基变量表示基变量）： x3+2 x2 = 8- x1 （1） x3 = 2- x1+（1/2） x5 x4 = 16-4x1 （2） (1)-(1/2)(3) x4 = 16-4 x1 4x2 = 12- x5 （ 3） x2 = 3 - （1/4）x5 z= 9＋2 x1 -（3/4）x5 令新的非基变量（ x1，x5 ）=（0，0）T,得到新的基 可行解： X(1)=(0,3,2, 16 , 0) T z1= 9 经济含义：生产乙产品3个，获得利润9元。