运筹学单纯形法

加松弛变量Xs
AX+IXs=b
X≥0
X,Xs≥0
-x1+x2+4x3≤2 (引入松弛变量x4) -x1+x2+4x3+x4=2 松弛变量的意义：未被充分利用（剩余）的资源， 松弛变量的价格系数是0（c4=0）。
(3) -x1+x2+4x3≥2 (引入剩余变量x5) -x1+x2+4x3-x5=2 剩余变量的意义：超用的资源（c5=0）
运筹学
Operations Research
2.2 单纯形法
2.2.1 线性规划模型的标准形式
一、标准型要求：
（1）目标最大化（max） （2）约束是“=”约束 （3）右端项非负 （4）所有变量非负 标准型
二、非标准型化为标准型
(1) min CX
加负号
max(-CX)
min z=2x1+4x2 (令z’=-z) max z’=-2x1-4x2 (2) AX≤b
例2：将下面的线性规-x1，x3=x3’-x3”，增加松弛变量x4， 增加剩余变量x5。
(4) xj≤0
( 令 xj’= -xj )
x j ’≥ 0
(5) xj为自由变量
( 令xj=xj’-xj’’ )
xj’≥0, xj’’≥0
例1：在煤电油例中，其线性规划模型为： maxz = 7x1+12x2 9x1+ 4x2≤360 4x1+ 5x2≤200 s.t. 3x1+10x2≤300 x1,x2≥0 化标准型：增加松弛变量x3、x4、x5 maxz = 7x1+12x2+0x3+0x4+0x5 9x1+ 4x2 +x3 =360 +x4 =200 s.t. 4x1+ 5x2 3x1+10x2 +x5 =300 x1,…,x5≥0

0 0 1
在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的 各列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基 本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作 为初始可行基，我们将构造初始可行基，具体做法在以后详细讲述。
8Leabharlann §1 单纯形法的基本思路和原理
二、 最优性检验 所谓最优性检验就是判断已求得的基本可行解是否是最优解。
5
§1 单纯形法的基本思路和原理
线性规划解之间的关系：
1.可行解与最优解： 最优解一定是可行解，但可行解不一定是最优解。
2. 可行解与基本解： 基本解不一定是可行解，可行解也不一定是基本解。
3. 可行解与基本可行解： 基本可行解一定是可行解，但可行解不一定是基本可行解。
4. 基本解与基本可行解： 基本可行解一定是基本解， 但基本解不一定是基本可行解。
9
§1 单纯形法的基本思路和原理
2.最优解判别定理
对于求最大目标函数的问题中，对于某个基本可行解，如
果所有检验数 j≤0，则这个基本可行解是最优解。 下面我
们用通俗的说法来解释最优解判别定理。设用非基变量表示
的目标函数为: z z0 j xj jJ 由于所有的xj的取值范围为大于等于零，当所有的 j都小
由线性代数的知识知道，如果我们在约束方程组系数矩阵中找
到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就
可得到唯一的解了，这个解我们称之为线性规划的基本解。
在此例中我们不妨找到
1 1 0 B3 1 0 0
为A的一个基，令这个基的非
1 0 1
基变量x１，s2为零。这时约束方程就变为基变量的约束方程：
第五章 单 纯 形 法

单纯形表
max z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0
Cj CB XB b 0 0 Z X3 3 X4 1 0 1 2 0 0
标准化
max z=x1+2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40
X1 X2 X3 X4 1 0 1 1 1 2 1 0 0 0 1 0
Z=x1+2x2 x1+x2+ x3 =3 x2 +x4=1 单纯形表
Cj
1
2
0
0
单纯形法原理 单纯形表 CB XB b
z=x1+2x2 x3 =3-x1-x2 x4=1 -x2
x2进基，x4离基
X1 X2 X3 X4

3/1 11
0
1 0
1 1
1 1
2 2 0 1 0 2 0 1 0 0 1 0 -1 0
max z=x1+2x2 s.t. x1+x2+x3 =3 x2 +x4=1 x1, x2, x3, x40
x1=0
(x1,x2,x3,x4)= (0,1,2,0), z=2 C (x1,x2,x3,x4)= (2,1,0,0), z=4,最优解
B
x4=0 x3=0
(x1,x2,x3,x4)= (0,0,3,1), z=0
1 0
0 0
0 1
0
CB XB b 0 2 Z Cj CB XB b 1 2 Z X1 2 X2 1 4 X3 2 X2 1 2 1 1 0 0
X1 X2 X3 X4 1 0 1 1 0 0 0 -1 1 -1

保持可行性 保持可行性 保持可行性
保持可行性
X1
X2
X3
...
Xk
保持单调增 保持单调增 保持单调增
Z1
Z2
Z3
...
保持单调增
Zk
当Zk 中非基变量的系数的系数全为负值时，这时的基 本可行解Xk 即是线性规划问题的最优解，迭代结束。
(2) 线性规划的典则形式
标准型
Max Z CX AX b
s.t X 0
j 1
j 1
j 1
j 1
与X 0 相比，X 1 的非零分量减少1个，若对应的k-1个 列向量线性无关，则即为基可行解；否则继续上述步
骤，直至剩下的非零变量对应的列向量线性无关。
几点结论
❖ 若线性规划问题有可行解,则可行域是一个凸多边形或 凸多面体(凸集),且仅有有限个顶点(极点);
❖ 线性规划问题的每一个基可行解都对应于可行域上的 一个顶点(极点);
10
令 x1 0 x2 0
则 x3 15
X 0 0 15 24T
x4 24
为基本可行解，B34为可行基
B
0
X 24
3
108
A
0
X 34
0
15 24
0
0
X 23
12
45 0
1 基本解为边界约束方程的交点； 2 基对应于可行解可行域极点； 3 相邻基本解的脚标有一个相同。
1 0
1 0
B23 1 0 B24 1 1 B34 0 1
C42
2!
4! 4
2
!
43 21 21 21
6
由于所有|B|≠ 0， 所以有6个基阵和 6个基本解。

总结：①在迭代过程中要保持常数列向量非负，这能确保基 可行解旳非负性。最小比值能做到这一点。 ②主元素不能为0。因为行旳初等变换不能把0变成1。 ③主元素不能为负数。因为用行旳初等变换把负数变成1会 把常数列中相应旳常数变成负数。
16
三、其他解旳情况 1、无穷多种解 例2 解LP问题：
min Z x1 2 x2 x3 0 x4 0 x5
xx51
1 2c 5 3c
其中c是满足非负性旳任意常数。
21
再由
x1,
x5
旳非负性，知：
x1 x2
1 2c c
0 0
x5 5 3c 0
解出 0 c 5 3
最优解为：
(2c 1, c,0,0,5 3c)T （其中0 c 5 ）
3
最优值为：max S 1.
22
2、无最优解旳两种情况：
相应地，将 X 0代入目的函数得 Z ( X 0 ) 0
从数学角度看，若让非基变量 x1, x2 取值从零增长，
6
min Z 2x1 x2 0x3 0x4 0x5
相应旳目旳函数值Z也将随之降低。所以有可能找到一种 新旳基本可行解，使其目旳函数值有所改善。即进行基变
换，换一种与它相邻旳基。再注意到 x1 前旳系数－2比 x2
x3
6 x1 x1
2x2 x2
x4 x5
xi 0
i 1,,5
15 24 5
目前可行基{ x3, x4 , x5 }所相应旳基本可行解
X 0 (0,0,15,24,5)T
(相应可行域旳 o(0,0) )
显然不是最优。 因为从经济意义上讲， x1 0, x2 0
意味着该厂不安排生产，所以没有利润。
2

所有检验数 j 0 ，则这个基本可行解是最优解。
n
z z0 j x j
j m 1
m
j ciaij c j =CTBa j c j
i 1
m
m
z0 c j x j = cibi =CBT b
j 1
i 1
✓对于求目标函数最小值的情况，只需 σj≤0
0
XB
b
x1
-1 x5 0
0
0 x4 3
1
-3 0
0
00
x2
x3
x4
0
-2 0
2
-2 1
0 10
-1 bi/aik
x5
1
0
0
29 2020/3/4
2、无界解
在求目标函数最大值的问题中，所谓无界解是指在约束条件 下目标函数值可以取任意的大。
•存在着一个小于零的检验数，并且该列的系数向量的每个元素 都小于或等于零，则此线性规划问题是无界的，一般地说此类
2x1 x2 x3 x5 2
s.t. x1 2x2
x4
3

x1,
x2 , x3, x4 , x5 0
✓添加人工变量x5来人为的创造一个单位矩阵作为基 ✓M叫做罚因子，任意大的数。 ✓人工变量只能取零值。必须把x5从基变量中换出去，否 则无解。
cj
3
2
00
CB XB
2020/3/4
14
(2)出基变量和主元的确定——最小比值规则
min

bi aik
aik

0


bl alk
确定出基变量的方法：把已确定的入基变量在各约束方程中的正的系数

反之，若经过迭代，不能把人工变量都变
为非基变量，则表明原LP问题无可行解。
19
第2章
单纯形法
2.3 人工变量法
2.3.1 大M法
在原问题的目标函数中添上全部人工变量，并令其系数 都为-M，
而M是一个充分大的正数。即
max z = c1x1 + c2x2 + c3x3 + … + cnxn – M( xn+1 + xn+2 +…+ xn+m )
思路：由一个基本可行解转化为另一个基本可行解。 等价改写为 目标方程 max z max z = 3x1+5x2 z -3x1 -5x2 = 0 z -3x1 -5x2 x1 +x3 x1 +x3 = 8 2x2 +x4 2x2 +x4 = 12 s.t. s.t. 3x1+4x2 +x5 3x1 + 4x2 +x5 = 36 x1 ， x2 ，x3，x4，x5 x1 ， x2 ，x3，x4，x5 ≥ 0
以主列中正值元素为分母，同行右端常数为分子，求比值；
6
第2章
单纯形法
2.1 单纯形法的基本思想
(Ⅰ)
用换基运算 将X0 转化为 另一个基本 可行解 X1。
z- 3x1 -5x2 = 0 0 换基运算—— x1 +x3 = 8 ① 方程组的初等变换 目的是把主列变为 22x2 +x4 = 12 ② 单位向量：主元变 3x1 + 4x2 +x5 = 36 ③ 为1，其余变为0。 X0 = ( 0, 0, 8, 12, 36 )T z0 = 0
⑴ 当前基：m阶排列阵

解就是原问题的最优解
若变化后的问题中含有非零的人工变量则元问题无可行
解
7
2.最优性检验和解的判别
x i bi a im 1 x m 1 , ,a in x n i 1, , m代入目标函数 Z
c1 x1 c2 x 2 c n x n c1 (b1 a1m 1 x m 1 a1n x n ) c2 (b2 a 2 m 1 x m 1 a 2 n x n ) cm (bm a mm 1 x m 1 a mn x n ) c m 1 x m 1 c n x n ci bi
（1）因为所有 Xj ≥0，当所有σ j<0 时，则 Z≤Z0,则该基可行解 对应最优解； （2）因为所有 Xj ≥ 0 ，当 σ j≤ 0 且存在 σ j ＝0 （ j=m+1,„,n) 时，则该线性规划问题有无穷多最优解； （ 3 ）对基可行解 X0, 若存在某个 σ k>0, 且所有 aik≤0(Pj≤0), i=1,2,„,m，则该问题无界（无界解）； （4）因为所有Xj≥0，当存在σ j>0时，则该基可行解不是最优 解，需要寻找另一个基可行解；
9
3.基变换
• 变换目的：使目标函数Z值得到改善，接近最优解，一次基变换， 是从该顶点到相邻顶点，即一次基变换仅变换一个基变量。 换入变量的确定（入基变量）
σk>0,aik 至少一个大于0，若σk=Max{σj| σj>0},则xk为换入变量。
换出变量的确定（出基变量）
bi bl bi , i 1,, m, min | aik 0 aik aik alk
13
一.求初始基可行解
1.当约束条件为“≤”时，直接在约束不等式左边加上非负的松弛 变量，使约束方程的系数矩阵很容易找到一个单位矩阵，求出一 个初始基可行解。

第二步：寻求初始可行基，确定基变量
1 2 1 0 0
1 0 0
A


4 0
0 4
0 0
1 0
10
B P3,
P4 ,
P5



0
0
1 0
0 1
对应的基变量是 x3，x4，x5； 第三步：写出初始基本可行解和相应的
目标函数值
两个关键的基本表达式：
写出用非基变量表示基变量的表达式：
由 x4 3 x1 x2 x3 → x1 3 x2 x3 x4
x5 9 x1 4x2 7x3

x5

6

3x2

6x3

x4
得新的基本可行解 X(1)=(3，0，0，0，6)T
⑤ 写出用非基变量表示目标函数的表达式:
Z 2x1 3x2 3x3 2(3 x2 x3 x4 ) 3x2 3x3 6 x2 x3 x4
可得相应的目标函数值为Z(1)=6
检验数仍有正的, 返回①进行讨论。
三、单纯形法的一般描述：
1、初始可行解的确定
(1)初始可行基的确定 观察法——观察系数矩阵中是否含有现成 的单位阵？
于是，若LP只有唯一最优解，这个最 优解所对应的点一定是可行域的一个顶点； 若LP有多个最优解，那么肯定在可行域的 顶点中可以找到至少一个最优解。
转移条件？
转移结果？
使目标函数值得到改善
得到LP最优解，目标函数达到最优值
2．需要解决的问题：
(1)为了使目标函数逐步变优，怎么转移？ (2)目标函数何时达到最优——
要求：