Ling Xueling
L.P,问题中变量个数多于 2 时,图解法 失 效即使是计算机求解,首先也要有 有效算法,然后才可能利用程序去实现它单形法,是 L.P,问题算法之基础 。 本质上,它是 代数方法,可以用线性代数的理论证明方法的合法性,清楚地说明算法背后的,为什么,
。 由于 课时限制我们不准备这么做,将把有限的精力和时间浅尝辄止：了解算法本身的使用
,并 不证明,为什么,。
第五章 L.P,单纯形法凌晨,凌晨,
Ling Xueling
一,例子假设 HT 公司正在计划下周两种计算机产品的生产台式机 /台：利润,50 装配工时,3 占地,8
便携机台 /：利润,40 装配工时,5 占地,5
资源限制：
下周最大可用工时,150
便携式显示器目前只有,20 pcs
仓储可用面积,300 平方英尺若以最大化利润为目标,如何安排生产？
第一节 单形法的代数说明凌晨,凌晨,
Ling Xueling
二,模型及其标准形设,x1 －计划的台式机数量 x2 － 计划的便携机数量
max 50x1 + 40x2
s.t.
3x1 + 5x2? 150 工时约束
x2? 20 便携机显示器约束
8x1 + 5x2? 300 仓储面积约束
x1,x2? 0 非负约束为了获得 标准形,分别为约束式引入 松弛 变量,s i。
第一节 单形法的代数说明凌晨,凌晨,
Ling Xueling
二,模型及其标准形
max 50x1 + 40x2 + 0s1 + 0s2 + 0s3 (5.1)
s.t.
3x1 + 5x2 + s1 = 150 (5.2)
x2 + s2 = 20 (5.3)
8x1 + 5x2 + s3 = 300 (5.4)
x1,x2,s1,s2,s3? 0
即为模型之 标准形 。 除非负约束之外,(5.2) － (5.4) 刚好构成一个 5个 变量,3 个方程的 线性方程组 。
第一节 单形法的代数说明凌晨,凌晨,
Ling Xueling
三,从代数观点思考标准形－－解题思路
1,将 (5.2) － (5.4) 线性方程组表示为增广阵,( A B ),则其一般解法是通过 初等变换 （ 保证既化简又同解 ）,
其 中 B’ 含自由变量可能有无穷多个解
2,因为不满足非负要求的线性方程组的解是 非可行 解,即使得到也要去除并重新求解 （ 换基 ）
3,从满足非负约束的线性方程组的解中找出 （ 迭代方法 ）
使得目标函数取值最好的解,即为最优解 。
第一节 单形法的代数说明凌晨,凌晨,
'
1
....
1
1
)( BAB
Ling Xueling
四,基解 （ basic solution）
1,定义：在 m 个方程,n 个变量之线性方程组中若令 n－ m 个变量为 0,然后求出的线性方程组解称为 基解,其中被令成 0 的变量称为 非基变量,没有被令成 0 的变量称为 基变量
2,上例中,m = 3,n = 5,令 （ 实际上可以任选 2
个 ）,x2 = 0,s1 = 0,代入方程组易得：
x1 = 50,x2 = 0,s1 = 0,s2 = 20,s3 = － 100
即为 L.P,问题一个基解,不过,非 可行解 ！
第一节 单形法的代数说明凌晨,凌晨,
Ling Xueling
五,基可行解
1,定义：满足非负要求的基解称为 基可行解很明显,我们要的是基可行解,是最优的基可行解
2,上例中,若令 x1 = 0,x2 = 0,则可得基解：
x1 = 0,x2 = 0,s1 = 150,s2 = 20,s3 = 300
正是一个基可行解 ！ 称之为初始基可行解
3,基可行解的几何解释作出本 L.P,问题的可行区域,可见,x1 = 0,x2 = 0 正是可行域的端点 （ 1） ！ 这不是偶然的,我们有一般的结论 。
第一节 单形法的代数说明凌晨,凌晨,
Ling Xueling
五,基可行解
4,可行域及其初始基可行解 的图形表示：
端点 （ 1） 即为初始基可行解 。
第二节 单形法用于最简单例子凌晨,凌晨,
(1) (2)
(3)
(4)
(5)
Ling Xueling
五,基可行解
5,定理一
L.P,问题中,约束线性方程组的 基可行解 就是其可行域的端点,反之亦然
6,定理二
L.P,问题最优解必是基可行解中的一个
7,单形法的迭代从任意一个初始 基可行解 出发 （ 只要令 n-m 个变量为零即可 ）,在不断改善目标函数前提下,设法将其变化 （ 迭代
） 成另一个基可行解,直至求出最优的 。
第一节 单形法的代数说明凌晨,凌晨,
Ling Xueling
一,L.P,的表格形式
1,表格形式的意义将 L.P,模型化成表格形式,可为单形法迅速提供一个 初始 基可行解 ！ 然后才开始迭代过程
2,例子
max 50x1 + 40x2 + 0s1 + 0s2 + 0s3 (5.1)
s.t.
3x1 + 5x2 + s1 = 150 (5.2)
x2 + s2 = 20 (5.3)
8x1 + 5x2 + s3 = 300 (5.4)
x1,x2,s1,s2,s3? 0
注意上例中,基变量 si 的系数阵是一个 单位阵 。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
一,L.P,的表格形式
3,表格形式定义
L.P,约束式化成线性方程组后若满足
1） 每一个方程中,某个基变量系数是 1,其余基变量系数是 0
2） 所有方程中,系数为 1 的基变量只能在一个方程中出现
3） 所有方程中,右手边值皆非负则称 L.P,问题已经表格化了,是表格形式说明：上述 1） 和 2） －－保证 基变量系数阵是单位阵
－－保证基解容易获得
L.P,中若所有约束式都是,?,且右手边值皆非负,则其标准形与表格形式一致 。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
二,建立初始单形表
1,定义将 L.P,表格形式中的系数所构成的如下形式之表格
C 行
A 矩阵 b 列称为 初始单形表例如,前述例子的初始单形表是
x1 x2 s1 s2 s3
50 40 0 0 0
3 5 1 0 0 150
0 1 0 1 0 20
8 5 0 0 1 300
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
二,建立初始单形表
2,求一个初始基可行解对表格形式来说,因为 基 变量下的系数刚好构成一个单位阵,所以 基变量的取值也就由 b 列数值所给出,
可见：在所谓表格形式中的确很容易求出基可行解单形法求解的思路：
不断 （ 令非基变量为 0） 求出新的基可行解以使 o.f.
的 值更加理想,具体来说,就是不断,换基,,选择一个当前的非基变量 入基 的同时,选择一个当前的基变量出基,逐步改善 o.f,值 。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
二,建立初始单形表
3,单形表的完善增加,1） 基的表达 ＋ 2） 设立检验行 ＋ 3） 反映出 o.f.
当前基 x1 x2 s1 s2 s3 C 行
Basic CB 50 40 0 0 0 b
s1 0 3 5 1 0 0 150
s2 0 0 1 0 1 0 20
s3 0 8 5 0 0 1 300
Zj 0 0 0 0 0 0
Cj － Zj 50 40 0 0 0
o.f.
检验行第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
二,建立初始单形表
4,完善的单形表的说明
1） Zj 行的计算
CB 列中的元素与其在 A 阵中第 j 列元素两两对应相乘后再全部相加
2） Cj － Zj 行的意义对应 A 的第 j 列变量在解中每增加一个单位时,o.f,的 净变化 －－检验行
3） o,f,的计算
CB （ 当前基之系数 ） 与 b 列系数两两相乘后相加所得 。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
三,迭代 （ iteration）
1,概念迭代－－ 换基,选入基变量,同时选出基变量是否迭代的依据：观察 Cj － Zj 值,正值,说明 xi 入基可以使得 o.f,增加,所以应当选为入基变量 。 得如下的：
2,选 入 基变量由 Cj － Zj 之意义,可知 变量是否 入基的标准是：
Cj － Zj > 0 且使 max {Cj － Zj } 对应之 j
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
三,迭代 （ iteration）
3,选 出 基变量
1） 原则要使入基变量尽可能大 ！ 以使对 o.f,的贡献尽量大
2） 求法
（ 1） 设 入 基变量在第 j 列,则对 A 之第 j 列 a i j,
对 a i j > 0（ 否则不予理会 ）,求 b i / a i j （ i = 1,2,......)
（ 2） 在诸 b i / a i j 中求出 最小的 一个,其所在的第 i 行对应的变量即为 出 基变量具体例子参见下页 。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
三,迭代 （ iteration）
x1 x2 s1 s2 s3
Basic CB 50 40 0 0 0 b bi / ai1
s1 0 3 5 1 0 0 150 150/3
s2 0 0 1 0 1 0 20 －
s3 0 8 5 0 0 1 300 300/8
Zj 0 0 0 0 0 0
Cj － Zj 50 40 0 0 0
说明：对应 入 基变量的列－－枢列；
对应 出 基变量的行－－枢行；
枢行与枢列交叉处的元素称为枢元 （ pivot） ( = 8)
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
三,迭代 （ iteration）
4,改善初始可行解的想法已得：让 s3 出基,x1 入基,可使 o.f,改善 300/8 = 37.5个单位即：当前初始可行解 x1 = 0,x2 = 0,s1 = 150,s2 = 20,s3 =
300 若 通过换基,可以使得 o.f,得到改善问题：新的基可行解是什么呢？ x1 =?
答：当基变量所对应的系数列是单位向量时,才能使在初始单形表中容易地求出 基 可行解,所以,为了方便地求出新的基 可行解,需要对 (AB) 通过初等变换使得 x1 所在 之 列 系数变成原基变量 s3 原先所在列的系数 ( 0 0 1)T 。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
三,迭代 （ iteration）
5,初等变换 改善初始可行解
1） 目标使得新的基变量对应于原来的基变量所对应的单位向量
2） 要求不管怎么变换,都要使新的表格是原约束线性方程组的等价系统
3） 初等行变换非零常数乘以任意一行,某行的倍数加至另一行注意：施用初等变换时,右手边数值 b i 也要跟着变 ！
变换从枢行除以枢元开始,如下图所示 。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
三,迭代 （ iteration）
5,初等变换 改善初始可行解 （ 续 ）
x1 x2 s1 s2 s3
Basic CB 50 40 0 0 0 b
s1 0 0 25/8 1 0 -3/8 75/2
s2 0 0 1 0 1 0 20
x1 50 1 5/8 0 0 1/8 75/2
Zj 1875
Cj － Zj
o.f.
新的基可行解,x1 = 75/2,x2 = 0,s1 = 75/2,s2 = 20,s3 = 0
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
三,迭代 （ iteration）
5,初等变换 改善初始可行解－－几何说明
（ 5） （ 4）
（ 3）
（ 1）
（ 2）
可见：初始可行解 （ 1） o.f,= 0
新的基可行解 （ 2） o.f,= 1875
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
四,向更好的解努力
1,求出新的检验行－－了解是否还能改善 o.f,？
x1 x2 s1 s2 s3
Basic CB 50 40 0 0 0 b
s1 0 0 25/8 1 0 -3/8 75/2
s2 0 0 1 0 1 0 20
x1 50 1 5/8 0 0 1/8 75/2
Zj 50 250/8 0 0 50/8 1875
Cj － Zj 0 70/8 0 0 -50/8
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
四,向更好的解努力
2,定入,出基变量因为 x2 所对应的检验值 ＝ 70/8,说明入基后可使 o.f,改善
70/8,所以 x2 应该入基出基变量：对应 x2 所在的系数列 a i2：若 a i2 > 0,求出 b i/ a i2
x1 x2 s1 s2 s3
Basic CB 50 40 0 0 0 b b i / a i2
s1 0 0 25/8 1 0 -3/8 75/2 12(小 ）
s2 0 0 1 0 1 0 20 20
x1 50 1 5/8 0 0 1/8 75/2 60
易见,25/8 是枢元,故,x2 应该入基,s1 应该出基 。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
3,初等行变换求新表格从枢行均除以枢元开始,将新入基变量 x2 的系数用初等变换改变为新出基变量 s1 的原系数列,( 1 0 0 )T
x1 x2 s1 s2 s3
Basic CB 50 40 0 0 0 b
x2 40 0 1 8/25 0 -3/25 12
s2 0 0 0 -8/25 1 3/25 8
x1 50 1 0 -5/25 0 5/25 30
Zj 50 40 14/5 0 26/5 1980
Cj － Zj 0 0 -14/5 0 -26/5
新的基可行解给出 o.f,= 1980。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
四,向更好的解努力
4,迭代停止准则对 Max 问题,Cj － Zj 对所有变量皆? 0 时,当前的基可行解即是最优解对 Min 问题,Cj － Zj 对所有变量皆? 0 时,当前的基可行解即是最优解
5,从几何上看最新的结果新的基可行解 x1 = 30,x2 = 12,s1 = 0,s2 = 8,s3 = 0
正对应着可行域的点 （ 3）,s2 = 8 表示：便携式显示器有闲置量 8。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
五,课堂练习
1,模型
Max 4x1 + 6x2 + 3x3 + x4
s.t.
3/2 x1 + 2x2 + 4x3 + 3x4? 550
4 x1 + x2 + 2x3 + x4? 700
2 x1 + 3x2 + x3 + 2x4? 200
x1,x2,x3,x4? 0
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
五,课堂练习
2,加入松弛变量变成标准形
3,将问题以表格形式给出因为,所有约束式皆,?,且 右手边值皆,?,
所以,标准形与表格形式一致
4,求检验行,定枢元
5,迭代
6,再迭代
7,停止迭代－－已经得到最优解：
x1 = 0,x2 = 25,x3 = 125,x4 = 0,s1 = 0,s2 = 425,s3 = 0
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
五,课堂练习 （ 求检验行,定枢元 ）
x1 x2 x3 x4 s1 s2 s3
B CB 4 6 3 1 0 0 0
s1 0 3/2 2 4 3 1 0 0 550
s2 0 4 1 2 1 0 1 0 700
s3 0 2 3 1 2 0 0 1 200
Zj 0 0 0 0 0 0 0
Cj － Zj 4 6 3 1 0 0 0 0
b i / a i2,550/2 = 275,700/1=700,200/3 = 66 (2/3)。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
五,课堂练习 （ 第一次迭代结果 ）
x1 x2 x3 x4 s1 s2 s3
B CB 4 6 3 1 0 0 0
s1 0 1/6 0 10/3 5/3 1 0 -2/3 416.6
s2 0 10/3 0 5/3 1/3 0 1 -1/3 633.3
x2 6 2/3 1 1/3 2/3 0 0 1/3 66.6
Zj 4 6 2 4 0 0 2
Cj － Zj 0 0 1 -3 0 0 -2 400
b i / a i3,125,380,200。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
五,课堂练习 （ 第二次迭代结果 ）
x1 x2 x3 x4 s1 s2 s3
B CB 4 6 3 1 0 0 0 b i
x3 3 1/20 0 1 1/2 3/10 0 -1/5 125
s2 0 195/60 0 0 -1/2 -1/2 1 0 425
x2 6 39/60 1 0 1/2 -1/10 0 2/5 25
Zj 81/20 6 3 9/2 3/10 0 54/30
Cj － Zj -1/20 0 0 -7/2 -3/10 0 -54/30 525
因为所有 Cj － Zj? 0,最优解是 x1 = 0,x2 = 25,x3 = 125,x4 = 0
,s1 = 0,s2 = 425,s3 = 0,o.f,= 525。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
前面讨论了用单形法求解 特殊 的 L.P,模型：
（ 只含,?,约束且目标函数为 Max L.P.问题 ）
max c1x1 + c2x2 + ………,,+ cnxn
s.t.
a11x1 + a12x2 + ………… + a1nxn? b1
a21x1 + a22x2 + …………,+ a2nxn? b2
……………………………,
am1x1 + am2x2 + ………,,+ amnxn? bm
x1,…,.,x n? 0
本节讨论一般情形下的 L.P,模型求解 。
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,含,?,约束的 L.P.问题
1,模型
max 50x1 + 40x2
s.t.
3x1 + 5x2? 150 工时约束
x2? 20 便携机显示器约束
8x1 + 5x2? 300 仓储面积约束
x1 + x2? 25 最小产量要求 (新增要求 )
x1,x2? 0 非负约束第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,含,?,约束的 L.P.问题
2,表格形式的困难
max 50x1 + 40x2 + 0s1 + 0s2 + 0s3 + 0s4
s.t.
3x1 + 5x2 + s1 = 150
x2 + s2 = 20
8x1 + 5x2 + s3 = 300
x1 + x2 － s4 = 25
x1,x2,si? 0
若同以前那样令 x1 = x2 = 0,则基解不可行 ！！ 表格形式在单形法中的便利是否无法继续了？
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,含,?,约束的 L.P.问题
3,引进人工变量 （ artificial variable） a4 的表格形式
max 50x1 + 40x2 + 0s1 + 0s2 + 0s3 + 0s4 － Ma4
s.t.
3x1 + 5x2 + s1 = 150
x2 + s2 = 20
8x1 + 5x2 + s3 = 300
x1 + x2 － s4 + a4 = 25
x1,x2,si? 0
人工变量－－本身没有实际意义,(M>0)仅仅是为了使我们能够继续享受表格形式带来的好处,方便地求出基可行解 。
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,含,?,约束的 L.P.问题
3,引进人工变量后的,基可行解,
x1 = 0,x2 = 0,s1 = 150,s2 = 20,s3 = 300,s4 = 0,a4 = 25
问题：引入人工变量以后,初始,基可行解,并不是现实世界的可行解 ！
但人工变量的确可以帮助我们方便地求出基可行解由于只要迭代完成时能得到现实问题的可行解就可以了,故,方法设计如下,保证每一个人工变量在求出最优解以前就从基可行解中消失即可 。 具体如后 。
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,含,?,约束的 L.P.问题
4,大 M 方法对每一个人工变量,为其在 o.f,中指定一个绝对值非常大的负数 － M,则：只要这个变量还在基中,就无法从根本上提高 o.f,的值,只能尽可能早地设法使之从基中消失 。 只要人工变量出基,就应尽早将其及所在列从单形表中消去 ！
如：
max 50x1 + 40x2 + 0s1 + 0s2 + 0s3 + 0s4 － Ma4
为什么不为 a4 指定一个具体的负数值作为系数呢？
答：使用抽象 － M,可以跟踪过程,在敏感性分析中有用 。
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,含,?,约束的 L.P.问题
4,大 M 方法
1） 表格形式,检验行,确定入和出基变量
B CB x1 x2 s1 s2 s3 s4 a4
50 40 0 0 0 0 － M b i
s1 0 3 5 1 0 0 0 0 150 50
s2 0 0 1 0 1 0 0 0 20 －
s3 0 8 5 0 0 1 0 0 300 37.5
a4 － M 1 1 0 0 0 -1 1 25 25
Zj － M － M 0 0 0 M － M － 25M
Cj－ Zj 50+M 40+M 0 0 0 － M 0
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,含,?,约束的 L.P.问题
4,大 M 方法
2） 第一次迭代结果 （ 既然已经出基,就尽早丢弃人工变量 ）
B CB x1 x2 s1 s2 s3 s4
50 40 0 0 0 0 b i
s1 0 0 2 1 0 0 3 75
s2 0 0 1 0 1 0 0 20
s3 0 0 -3 0 0 1 8 100
x1 50 1 1 0 0 0 -1 25
Zj 50 50 0 0 0 -50 1250
Cj－ Zj 0 -10 0 0 0 50
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,含,?,约束的 L.P.问题
4,大 M 方法
3） 第 二 次迭代结果 （ 已得到最优解 ）
B CB x1 x2 s1 s2 s3 s4
50 40 0 0 0 0 b i
x2 40 0 1 8/25 0 － 3/25 0 12
s2 0 0 0 -8/25 1 3/25 0 8
s3 0 0 0 3/25 0 2/25 1 17
x1 50 1 0 -5/25 0 5/25 0 30
Zj 50 40 14/5 0 26/5 0 1980
Cj－ Zj 0 0 -14/5 0 -26/5 0
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
二,含,＝,约束的 L.P.问题不需要松弛或剩余变量,只需加一个人工变量即可三,右手边常数项为负数约束式两边乘以 （ － 1） 即可四,求 Min 的 L.P,问题－－两种方法
1,改变入基变量的选择规则入基－－选则对应 Cj－ Zj 尽量小且为负值的变量为入基变量迭代停止：所有 Cj－ Zj 皆非负时停止迭代
2,转变成 Max 问题参见下例 。
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
求解如下模型：
Min 2x1 + 3x2
s.t.
x1? 125
x1 + x2? 350
2 x1 + x2? 600
x1,x2? 0
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
1） 表格形式
Max － 2x1 － 3x2 + 0s1 + 0s2 + 0s3 － Ma1 － Ma2
s.t.
x1 -s1 + a1 = 125
x1 + x2 -s2 +a2 = 350
2 x1 + x2 + s3 = 600
xi,si? 0
显然,应当选择 a1,a2,s3 为 基 变量 。
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
1） 初始单形表
B CB x1 x2 s1 s2 s3 a1 a2
-2 -3 0 0 0 － M － M b i b i/a i1
a1－ M 1 0 -1 0 0 1 0 125 125
a2 － M 1 1 0 1 -1 0 0 350 350
s3 0 2 1 0 0 1 0 0 600 300
Zj － 2M － M M M 0 -M － M
Cj－ Zj 2+2M -3+M -M -M 0 0 0 － 475M
显然,入基变量是 x1,出基变量是 a1。
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
2） 第一次迭代后结果
B CB x1 x2 s1 s2 s3 a2
-2 -3 0 0 0 － M b i
x1 － 2 1 0 -1 0 0 0 125
a2 － M 0 1 1 -1 0 1 225
s3 0 0 1 2 0 1 0 350
Zj － 2 － M 2-M M 0 -M
Cj－ Zj 0 -3+M -2+M -M 0 0 － 250－ 225M
显然,新入基变量是 s1,新 出基变量是 s3。
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
3） 最终单形表
B CB x1 x2 s1 s2 s3
-2 -3 0 0 0 b i
x1 － 2 1 0 0 1 1 250
x2 － 3 0 1 0 -2 -1 100
s1 0 0 0 1 1 1 125
Zj － 2 － 3 0 4 1
Cj－ Zj 0 0 0 -4 -1 － 800
显然,最优解是,x1 = 250,x2 = 100,s1 = 125,s2 = 0,s3 = 0,
o.f,＝ ＋ 800
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,无解
1,计算机输出结果显示,There is no feasible solution to this
problem.
2,当迭代停止准则表明最优解已经求得,但仍然有一个或多个 人工 变量留在 基 变量中时,L.P,模型 无解
3,例子 max 50x1 + 40x2
s.t.
3x1 + 5x2? 150
x2? 20
8x1 + 5x2? 300
x1 + x2? 50
x1,x2? 0
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
一,无解
1） 初始单形表
B CB x1 x2 s1 s2 s3 s4 a4
50 40 0 0 0 0 － M b i
s1 0 3 5 1 0 0 0 0 150
s2 0 0 1 0 1 0 0 0 20
s3 0 8 5 0 0 1 0 0 300
a4 － M 1 1 0 0 0 -1 1 50
Zj － M － M 0 0 0 M － M
Cj－ Zj 50+M 40+M 0 0 0 － M 0 － 50M
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
2） 最终单形表
B CB x1 x2 s1 s2 s3 s4 a4
50 40 0 0 0 0 － M b i
x2 40 0 1 8/25 0 -3/25 0 0 12
s2 0 0 0 -8/25 1 3/25 0 0 8
x1 50 1 0 -1/5 0 1/5 0 0 30
a4 － M 0 0 -3/25 0 -2/25 -1 1 8
Zj 50 40 (70+3M)/25 0 (130+2M)/25 M － M
Cj－ Zj 0 0 - (70+3M)/25 0 - (130+2M)/25－ M 0 1980-8M
此时,,最优解,x1 = 30,x2 = 12 仍无法满足第四约束,这是因为人工变量 a4 无法出基导致的,a4 = 8 破坏了这个约束 。
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
二,解无界
1,计算机输出结果显示,The solution to this
problem is unbounded
2,当迭代 过程中出现枢列中所有系数 a ij? 0,而 无法确定 出基 变量时,L.P,模型的解无界,这只能说明模型本身有失误之处,与单形法无关
3,例子 max 20x1 + 10x2
s.t.
x1? 2
x2? 5
x1,x2? 0。
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
二,解无界
3,例子中 x1 入基以后 （ 第一次迭代后 ） 的单形表是
B CB x1 x2 s1 s2 a1
20 10 0 0 － M b i
x1 20 1 0 -1 0 1 2
s2 0 0 1 0 1 0 5
Zj 20 0 -20 0 20
Cj－ Zj 0 10 20 0 － M-20 40
显然,新的入基变量是 s1,但因为 s1 系数列元素分别是－ 1
和 0,无法求出 b i / a i3,也就无法确定出基变量,无界 。
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
三,无穷多解
1,计算机输出结果没有异样表示,给出其中一个最优解而已
2,当一个或多个 非 基变量的检验值 Cj－ Zj = 0 时,L.P,模型有无穷多个解
3,例子
max 30x1 + 50x2
s.t.
3x1 + 5x2? 150
x2? 20
8x1 + 5x2? 300
x1,x2? 0
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
三,无穷多解上述模型最终单形表是
B CB x1 x2 s1 s2 s3
30 50 0 0 0 b i
x2 50 0 1 0 1 0 20
s3 0 0 0 -8/3 25/3 1 200/3
x1 30 1 0 1/3 -5/3 0 50/3
Zj 30 50 10 0 0
Cj－ Zj 0 0 -10 0 0 1500
非基变量 s2 之检验系数为 0,说明,s2 入基并不会改变 o.f,的值,如果试着将 s2 入基,可得下列单形表 。
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
三,无穷多解
B CB x1 x2 s1 s2 s3
30 50 0 0 0 b i
x2 50 0 1 8/25 0 -3/25 12
s2 0 0 0 -8/25 1 3/25 8
x1 30 1 0 -1/5 0 1/5 30
Zj 30 50 10 0 0
Cj－ Zj 0 0 -10 0 0 1500
由于两种情形下所有 Cj－ Zj? 0,故,都是最优解 。 这提示我们解有无穷多个 。
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
实际上,利用单形法也可以方便地对
L.P,模型进行敏感性分析 。 由于时间关系,略去 。
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
1,用单形法求解：
Max 2.5 x1 + 5 x2 + x3 + x4
s.t.
x1 + 1.4 x2 + 0.2 x3 + 0.8 x4? 1600
2 x1 + 2 x2 + 1.6 x3 + x4? 1300
1.2 x1 + x2 + x3 + 1.2 x4? 960
x1,x2,x3,x4? 0
第五章 习题布置凌晨,凌晨,
Ling Xueling
2,用单形法求解：
Min 4 x1 + 2 x2 + 33
s.t.
x1 + 3 x2? 15
x1 + 2x3? 10
2 x1 + x2? 20
x1,x2,x3? 0
第五章 习题布置凌晨,凌晨,
Ling Xueling
The End of Chapter 5
L.P,问题中变量个数多于 2 时,图解法 失 效即使是计算机求解,首先也要有 有效算法,然后才可能利用程序去实现它单形法,是 L.P,问题算法之基础 。 本质上,它是 代数方法,可以用线性代数的理论证明方法的合法性,清楚地说明算法背后的,为什么,
。 由于 课时限制我们不准备这么做,将把有限的精力和时间浅尝辄止：了解算法本身的使用
,并 不证明,为什么,。
第五章 L.P,单纯形法凌晨,凌晨,
Ling Xueling
一,例子假设 HT 公司正在计划下周两种计算机产品的生产台式机 /台：利润,50 装配工时,3 占地,8
便携机台 /：利润,40 装配工时,5 占地,5
资源限制：
下周最大可用工时,150
便携式显示器目前只有,20 pcs
仓储可用面积,300 平方英尺若以最大化利润为目标,如何安排生产？
第一节 单形法的代数说明凌晨,凌晨,
Ling Xueling
二,模型及其标准形设,x1 －计划的台式机数量 x2 － 计划的便携机数量
max 50x1 + 40x2
s.t.
3x1 + 5x2? 150 工时约束
x2? 20 便携机显示器约束
8x1 + 5x2? 300 仓储面积约束
x1,x2? 0 非负约束为了获得 标准形,分别为约束式引入 松弛 变量,s i。
第一节 单形法的代数说明凌晨,凌晨,
Ling Xueling
二,模型及其标准形
max 50x1 + 40x2 + 0s1 + 0s2 + 0s3 (5.1)
s.t.
3x1 + 5x2 + s1 = 150 (5.2)
x2 + s2 = 20 (5.3)
8x1 + 5x2 + s3 = 300 (5.4)
x1,x2,s1,s2,s3? 0
即为模型之 标准形 。 除非负约束之外,(5.2) － (5.4) 刚好构成一个 5个 变量,3 个方程的 线性方程组 。
第一节 单形法的代数说明凌晨,凌晨,
Ling Xueling
三,从代数观点思考标准形－－解题思路
1,将 (5.2) － (5.4) 线性方程组表示为增广阵,( A B ),则其一般解法是通过 初等变换 （ 保证既化简又同解 ）,
其 中 B’ 含自由变量可能有无穷多个解
2,因为不满足非负要求的线性方程组的解是 非可行 解,即使得到也要去除并重新求解 （ 换基 ）
3,从满足非负约束的线性方程组的解中找出 （ 迭代方法 ）
使得目标函数取值最好的解,即为最优解 。
第一节 单形法的代数说明凌晨,凌晨,
'
1
....
1
1
)( BAB
Ling Xueling
四,基解 （ basic solution）
1,定义：在 m 个方程,n 个变量之线性方程组中若令 n－ m 个变量为 0,然后求出的线性方程组解称为 基解,其中被令成 0 的变量称为 非基变量,没有被令成 0 的变量称为 基变量
2,上例中,m = 3,n = 5,令 （ 实际上可以任选 2
个 ）,x2 = 0,s1 = 0,代入方程组易得：
x1 = 50,x2 = 0,s1 = 0,s2 = 20,s3 = － 100
即为 L.P,问题一个基解,不过,非 可行解 ！
第一节 单形法的代数说明凌晨,凌晨,
Ling Xueling
五,基可行解
1,定义：满足非负要求的基解称为 基可行解很明显,我们要的是基可行解,是最优的基可行解
2,上例中,若令 x1 = 0,x2 = 0,则可得基解：
x1 = 0,x2 = 0,s1 = 150,s2 = 20,s3 = 300
正是一个基可行解 ！ 称之为初始基可行解
3,基可行解的几何解释作出本 L.P,问题的可行区域,可见,x1 = 0,x2 = 0 正是可行域的端点 （ 1） ！ 这不是偶然的,我们有一般的结论 。
第一节 单形法的代数说明凌晨,凌晨,
Ling Xueling
五,基可行解
4,可行域及其初始基可行解 的图形表示：
端点 （ 1） 即为初始基可行解 。
第二节 单形法用于最简单例子凌晨,凌晨,
(1) (2)
(3)
(4)
(5)
Ling Xueling
五,基可行解
5,定理一
L.P,问题中,约束线性方程组的 基可行解 就是其可行域的端点,反之亦然
6,定理二
L.P,问题最优解必是基可行解中的一个
7,单形法的迭代从任意一个初始 基可行解 出发 （ 只要令 n-m 个变量为零即可 ）,在不断改善目标函数前提下,设法将其变化 （ 迭代
） 成另一个基可行解,直至求出最优的 。
第一节 单形法的代数说明凌晨,凌晨,
Ling Xueling
一,L.P,的表格形式
1,表格形式的意义将 L.P,模型化成表格形式,可为单形法迅速提供一个 初始 基可行解 ！ 然后才开始迭代过程
2,例子
max 50x1 + 40x2 + 0s1 + 0s2 + 0s3 (5.1)
s.t.
3x1 + 5x2 + s1 = 150 (5.2)
x2 + s2 = 20 (5.3)
8x1 + 5x2 + s3 = 300 (5.4)
x1,x2,s1,s2,s3? 0
注意上例中,基变量 si 的系数阵是一个 单位阵 。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
一,L.P,的表格形式
3,表格形式定义
L.P,约束式化成线性方程组后若满足
1） 每一个方程中,某个基变量系数是 1,其余基变量系数是 0
2） 所有方程中,系数为 1 的基变量只能在一个方程中出现
3） 所有方程中,右手边值皆非负则称 L.P,问题已经表格化了,是表格形式说明：上述 1） 和 2） －－保证 基变量系数阵是单位阵
－－保证基解容易获得
L.P,中若所有约束式都是,?,且右手边值皆非负,则其标准形与表格形式一致 。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
二,建立初始单形表
1,定义将 L.P,表格形式中的系数所构成的如下形式之表格
C 行
A 矩阵 b 列称为 初始单形表例如,前述例子的初始单形表是
x1 x2 s1 s2 s3
50 40 0 0 0
3 5 1 0 0 150
0 1 0 1 0 20
8 5 0 0 1 300
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
二,建立初始单形表
2,求一个初始基可行解对表格形式来说,因为 基 变量下的系数刚好构成一个单位阵,所以 基变量的取值也就由 b 列数值所给出,
可见：在所谓表格形式中的确很容易求出基可行解单形法求解的思路：
不断 （ 令非基变量为 0） 求出新的基可行解以使 o.f.
的 值更加理想,具体来说,就是不断,换基,,选择一个当前的非基变量 入基 的同时,选择一个当前的基变量出基,逐步改善 o.f,值 。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
二,建立初始单形表
3,单形表的完善增加,1） 基的表达 ＋ 2） 设立检验行 ＋ 3） 反映出 o.f.
当前基 x1 x2 s1 s2 s3 C 行
Basic CB 50 40 0 0 0 b
s1 0 3 5 1 0 0 150
s2 0 0 1 0 1 0 20
s3 0 8 5 0 0 1 300
Zj 0 0 0 0 0 0
Cj － Zj 50 40 0 0 0
o.f.
检验行第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
二,建立初始单形表
4,完善的单形表的说明
1） Zj 行的计算
CB 列中的元素与其在 A 阵中第 j 列元素两两对应相乘后再全部相加
2） Cj － Zj 行的意义对应 A 的第 j 列变量在解中每增加一个单位时,o.f,的 净变化 －－检验行
3） o,f,的计算
CB （ 当前基之系数 ） 与 b 列系数两两相乘后相加所得 。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
三,迭代 （ iteration）
1,概念迭代－－ 换基,选入基变量,同时选出基变量是否迭代的依据：观察 Cj － Zj 值,正值,说明 xi 入基可以使得 o.f,增加,所以应当选为入基变量 。 得如下的：
2,选 入 基变量由 Cj － Zj 之意义,可知 变量是否 入基的标准是：
Cj － Zj > 0 且使 max {Cj － Zj } 对应之 j
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
三,迭代 （ iteration）
3,选 出 基变量
1） 原则要使入基变量尽可能大 ！ 以使对 o.f,的贡献尽量大
2） 求法
（ 1） 设 入 基变量在第 j 列,则对 A 之第 j 列 a i j,
对 a i j > 0（ 否则不予理会 ）,求 b i / a i j （ i = 1,2,......)
（ 2） 在诸 b i / a i j 中求出 最小的 一个,其所在的第 i 行对应的变量即为 出 基变量具体例子参见下页 。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
三,迭代 （ iteration）
x1 x2 s1 s2 s3
Basic CB 50 40 0 0 0 b bi / ai1
s1 0 3 5 1 0 0 150 150/3
s2 0 0 1 0 1 0 20 －
s3 0 8 5 0 0 1 300 300/8
Zj 0 0 0 0 0 0
Cj － Zj 50 40 0 0 0
说明：对应 入 基变量的列－－枢列；
对应 出 基变量的行－－枢行；
枢行与枢列交叉处的元素称为枢元 （ pivot） ( = 8)
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
三,迭代 （ iteration）
4,改善初始可行解的想法已得：让 s3 出基,x1 入基,可使 o.f,改善 300/8 = 37.5个单位即：当前初始可行解 x1 = 0,x2 = 0,s1 = 150,s2 = 20,s3 =
300 若 通过换基,可以使得 o.f,得到改善问题：新的基可行解是什么呢？ x1 =?
答：当基变量所对应的系数列是单位向量时,才能使在初始单形表中容易地求出 基 可行解,所以,为了方便地求出新的基 可行解,需要对 (AB) 通过初等变换使得 x1 所在 之 列 系数变成原基变量 s3 原先所在列的系数 ( 0 0 1)T 。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
三,迭代 （ iteration）
5,初等变换 改善初始可行解
1） 目标使得新的基变量对应于原来的基变量所对应的单位向量
2） 要求不管怎么变换,都要使新的表格是原约束线性方程组的等价系统
3） 初等行变换非零常数乘以任意一行,某行的倍数加至另一行注意：施用初等变换时,右手边数值 b i 也要跟着变 ！
变换从枢行除以枢元开始,如下图所示 。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
三,迭代 （ iteration）
5,初等变换 改善初始可行解 （ 续 ）
x1 x2 s1 s2 s3
Basic CB 50 40 0 0 0 b
s1 0 0 25/8 1 0 -3/8 75/2
s2 0 0 1 0 1 0 20
x1 50 1 5/8 0 0 1/8 75/2
Zj 1875
Cj － Zj
o.f.
新的基可行解,x1 = 75/2,x2 = 0,s1 = 75/2,s2 = 20,s3 = 0
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
三,迭代 （ iteration）
5,初等变换 改善初始可行解－－几何说明
（ 5） （ 4）
（ 3）
（ 1）
（ 2）
可见：初始可行解 （ 1） o.f,= 0
新的基可行解 （ 2） o.f,= 1875
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
四,向更好的解努力
1,求出新的检验行－－了解是否还能改善 o.f,？
x1 x2 s1 s2 s3
Basic CB 50 40 0 0 0 b
s1 0 0 25/8 1 0 -3/8 75/2
s2 0 0 1 0 1 0 20
x1 50 1 5/8 0 0 1/8 75/2
Zj 50 250/8 0 0 50/8 1875
Cj － Zj 0 70/8 0 0 -50/8
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
四,向更好的解努力
2,定入,出基变量因为 x2 所对应的检验值 ＝ 70/8,说明入基后可使 o.f,改善
70/8,所以 x2 应该入基出基变量：对应 x2 所在的系数列 a i2：若 a i2 > 0,求出 b i/ a i2
x1 x2 s1 s2 s3
Basic CB 50 40 0 0 0 b b i / a i2
s1 0 0 25/8 1 0 -3/8 75/2 12(小 ）
s2 0 0 1 0 1 0 20 20
x1 50 1 5/8 0 0 1/8 75/2 60
易见,25/8 是枢元,故,x2 应该入基,s1 应该出基 。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
3,初等行变换求新表格从枢行均除以枢元开始,将新入基变量 x2 的系数用初等变换改变为新出基变量 s1 的原系数列,( 1 0 0 )T
x1 x2 s1 s2 s3
Basic CB 50 40 0 0 0 b
x2 40 0 1 8/25 0 -3/25 12
s2 0 0 0 -8/25 1 3/25 8
x1 50 1 0 -5/25 0 5/25 30
Zj 50 40 14/5 0 26/5 1980
Cj － Zj 0 0 -14/5 0 -26/5
新的基可行解给出 o.f,= 1980。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
四,向更好的解努力
4,迭代停止准则对 Max 问题,Cj － Zj 对所有变量皆? 0 时,当前的基可行解即是最优解对 Min 问题,Cj － Zj 对所有变量皆? 0 时,当前的基可行解即是最优解
5,从几何上看最新的结果新的基可行解 x1 = 30,x2 = 12,s1 = 0,s2 = 8,s3 = 0
正对应着可行域的点 （ 3）,s2 = 8 表示：便携式显示器有闲置量 8。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
五,课堂练习
1,模型
Max 4x1 + 6x2 + 3x3 + x4
s.t.
3/2 x1 + 2x2 + 4x3 + 3x4? 550
4 x1 + x2 + 2x3 + x4? 700
2 x1 + 3x2 + x3 + 2x4? 200
x1,x2,x3,x4? 0
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
五,课堂练习
2,加入松弛变量变成标准形
3,将问题以表格形式给出因为,所有约束式皆,?,且 右手边值皆,?,
所以,标准形与表格形式一致
4,求检验行,定枢元
5,迭代
6,再迭代
7,停止迭代－－已经得到最优解：
x1 = 0,x2 = 25,x3 = 125,x4 = 0,s1 = 0,s2 = 425,s3 = 0
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
五,课堂练习 （ 求检验行,定枢元 ）
x1 x2 x3 x4 s1 s2 s3
B CB 4 6 3 1 0 0 0
s1 0 3/2 2 4 3 1 0 0 550
s2 0 4 1 2 1 0 1 0 700
s3 0 2 3 1 2 0 0 1 200
Zj 0 0 0 0 0 0 0
Cj － Zj 4 6 3 1 0 0 0 0
b i / a i2,550/2 = 275,700/1=700,200/3 = 66 (2/3)。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
五,课堂练习 （ 第一次迭代结果 ）
x1 x2 x3 x4 s1 s2 s3
B CB 4 6 3 1 0 0 0
s1 0 1/6 0 10/3 5/3 1 0 -2/3 416.6
s2 0 10/3 0 5/3 1/3 0 1 -1/3 633.3
x2 6 2/3 1 1/3 2/3 0 0 1/3 66.6
Zj 4 6 2 4 0 0 2
Cj － Zj 0 0 1 -3 0 0 -2 400
b i / a i3,125,380,200。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
五,课堂练习 （ 第二次迭代结果 ）
x1 x2 x3 x4 s1 s2 s3
B CB 4 6 3 1 0 0 0 b i
x3 3 1/20 0 1 1/2 3/10 0 -1/5 125
s2 0 195/60 0 0 -1/2 -1/2 1 0 425
x2 6 39/60 1 0 1/2 -1/10 0 2/5 25
Zj 81/20 6 3 9/2 3/10 0 54/30
Cj － Zj -1/20 0 0 -7/2 -3/10 0 -54/30 525
因为所有 Cj － Zj? 0,最优解是 x1 = 0,x2 = 25,x3 = 125,x4 = 0
,s1 = 0,s2 = 425,s3 = 0,o.f,= 525。
第二节 单形法用于最简单例子凌晨,凌晨,
Ling Xueling
前面讨论了用单形法求解 特殊 的 L.P,模型：
（ 只含,?,约束且目标函数为 Max L.P.问题 ）
max c1x1 + c2x2 + ………,,+ cnxn
s.t.
a11x1 + a12x2 + ………… + a1nxn? b1
a21x1 + a22x2 + …………,+ a2nxn? b2
……………………………,
am1x1 + am2x2 + ………,,+ amnxn? bm
x1,…,.,x n? 0
本节讨论一般情形下的 L.P,模型求解 。
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,含,?,约束的 L.P.问题
1,模型
max 50x1 + 40x2
s.t.
3x1 + 5x2? 150 工时约束
x2? 20 便携机显示器约束
8x1 + 5x2? 300 仓储面积约束
x1 + x2? 25 最小产量要求 (新增要求 )
x1,x2? 0 非负约束第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,含,?,约束的 L.P.问题
2,表格形式的困难
max 50x1 + 40x2 + 0s1 + 0s2 + 0s3 + 0s4
s.t.
3x1 + 5x2 + s1 = 150
x2 + s2 = 20
8x1 + 5x2 + s3 = 300
x1 + x2 － s4 = 25
x1,x2,si? 0
若同以前那样令 x1 = x2 = 0,则基解不可行 ！！ 表格形式在单形法中的便利是否无法继续了？
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,含,?,约束的 L.P.问题
3,引进人工变量 （ artificial variable） a4 的表格形式
max 50x1 + 40x2 + 0s1 + 0s2 + 0s3 + 0s4 － Ma4
s.t.
3x1 + 5x2 + s1 = 150
x2 + s2 = 20
8x1 + 5x2 + s3 = 300
x1 + x2 － s4 + a4 = 25
x1,x2,si? 0
人工变量－－本身没有实际意义,(M>0)仅仅是为了使我们能够继续享受表格形式带来的好处,方便地求出基可行解 。
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,含,?,约束的 L.P.问题
3,引进人工变量后的,基可行解,
x1 = 0,x2 = 0,s1 = 150,s2 = 20,s3 = 300,s4 = 0,a4 = 25
问题：引入人工变量以后,初始,基可行解,并不是现实世界的可行解 ！
但人工变量的确可以帮助我们方便地求出基可行解由于只要迭代完成时能得到现实问题的可行解就可以了,故,方法设计如下,保证每一个人工变量在求出最优解以前就从基可行解中消失即可 。 具体如后 。
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,含,?,约束的 L.P.问题
4,大 M 方法对每一个人工变量,为其在 o.f,中指定一个绝对值非常大的负数 － M,则：只要这个变量还在基中,就无法从根本上提高 o.f,的值,只能尽可能早地设法使之从基中消失 。 只要人工变量出基,就应尽早将其及所在列从单形表中消去 ！
如：
max 50x1 + 40x2 + 0s1 + 0s2 + 0s3 + 0s4 － Ma4
为什么不为 a4 指定一个具体的负数值作为系数呢？
答：使用抽象 － M,可以跟踪过程,在敏感性分析中有用 。
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,含,?,约束的 L.P.问题
4,大 M 方法
1） 表格形式,检验行,确定入和出基变量
B CB x1 x2 s1 s2 s3 s4 a4
50 40 0 0 0 0 － M b i
s1 0 3 5 1 0 0 0 0 150 50
s2 0 0 1 0 1 0 0 0 20 －
s3 0 8 5 0 0 1 0 0 300 37.5
a4 － M 1 1 0 0 0 -1 1 25 25
Zj － M － M 0 0 0 M － M － 25M
Cj－ Zj 50+M 40+M 0 0 0 － M 0
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,含,?,约束的 L.P.问题
4,大 M 方法
2） 第一次迭代结果 （ 既然已经出基,就尽早丢弃人工变量 ）
B CB x1 x2 s1 s2 s3 s4
50 40 0 0 0 0 b i
s1 0 0 2 1 0 0 3 75
s2 0 0 1 0 1 0 0 20
s3 0 0 -3 0 0 1 8 100
x1 50 1 1 0 0 0 -1 25
Zj 50 50 0 0 0 -50 1250
Cj－ Zj 0 -10 0 0 0 50
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,含,?,约束的 L.P.问题
4,大 M 方法
3） 第 二 次迭代结果 （ 已得到最优解 ）
B CB x1 x2 s1 s2 s3 s4
50 40 0 0 0 0 b i
x2 40 0 1 8/25 0 － 3/25 0 12
s2 0 0 0 -8/25 1 3/25 0 8
s3 0 0 0 3/25 0 2/25 1 17
x1 50 1 0 -5/25 0 5/25 0 30
Zj 50 40 14/5 0 26/5 0 1980
Cj－ Zj 0 0 -14/5 0 -26/5 0
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
二,含,＝,约束的 L.P.问题不需要松弛或剩余变量,只需加一个人工变量即可三,右手边常数项为负数约束式两边乘以 （ － 1） 即可四,求 Min 的 L.P,问题－－两种方法
1,改变入基变量的选择规则入基－－选则对应 Cj－ Zj 尽量小且为负值的变量为入基变量迭代停止：所有 Cj－ Zj 皆非负时停止迭代
2,转变成 Max 问题参见下例 。
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
求解如下模型：
Min 2x1 + 3x2
s.t.
x1? 125
x1 + x2? 350
2 x1 + x2? 600
x1,x2? 0
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
1） 表格形式
Max － 2x1 － 3x2 + 0s1 + 0s2 + 0s3 － Ma1 － Ma2
s.t.
x1 -s1 + a1 = 125
x1 + x2 -s2 +a2 = 350
2 x1 + x2 + s3 = 600
xi,si? 0
显然,应当选择 a1,a2,s3 为 基 变量 。
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
1） 初始单形表
B CB x1 x2 s1 s2 s3 a1 a2
-2 -3 0 0 0 － M － M b i b i/a i1
a1－ M 1 0 -1 0 0 1 0 125 125
a2 － M 1 1 0 1 -1 0 0 350 350
s3 0 2 1 0 0 1 0 0 600 300
Zj － 2M － M M M 0 -M － M
Cj－ Zj 2+2M -3+M -M -M 0 0 0 － 475M
显然,入基变量是 x1,出基变量是 a1。
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
2） 第一次迭代后结果
B CB x1 x2 s1 s2 s3 a2
-2 -3 0 0 0 － M b i
x1 － 2 1 0 -1 0 0 0 125
a2 － M 0 1 1 -1 0 1 225
s3 0 0 1 2 0 1 0 350
Zj － 2 － M 2-M M 0 -M
Cj－ Zj 0 -3+M -2+M -M 0 0 － 250－ 225M
显然,新入基变量是 s1,新 出基变量是 s3。
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
3） 最终单形表
B CB x1 x2 s1 s2 s3
-2 -3 0 0 0 b i
x1 － 2 1 0 0 1 1 250
x2 － 3 0 1 0 -2 -1 100
s1 0 0 0 1 1 1 125
Zj － 2 － 3 0 4 1
Cj－ Zj 0 0 0 -4 -1 － 800
显然,最优解是,x1 = 250,x2 = 100,s1 = 125,s2 = 0,s3 = 0,
o.f,＝ ＋ 800
第三节 单形法用于一般 L.P,模型凌晨,凌晨,
Ling Xueling
一,无解
1,计算机输出结果显示,There is no feasible solution to this
problem.
2,当迭代停止准则表明最优解已经求得,但仍然有一个或多个 人工 变量留在 基 变量中时,L.P,模型 无解
3,例子 max 50x1 + 40x2
s.t.
3x1 + 5x2? 150
x2? 20
8x1 + 5x2? 300
x1 + x2? 50
x1,x2? 0
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
一,无解
1） 初始单形表
B CB x1 x2 s1 s2 s3 s4 a4
50 40 0 0 0 0 － M b i
s1 0 3 5 1 0 0 0 0 150
s2 0 0 1 0 1 0 0 0 20
s3 0 8 5 0 0 1 0 0 300
a4 － M 1 1 0 0 0 -1 1 50
Zj － M － M 0 0 0 M － M
Cj－ Zj 50+M 40+M 0 0 0 － M 0 － 50M
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
2） 最终单形表
B CB x1 x2 s1 s2 s3 s4 a4
50 40 0 0 0 0 － M b i
x2 40 0 1 8/25 0 -3/25 0 0 12
s2 0 0 0 -8/25 1 3/25 0 0 8
x1 50 1 0 -1/5 0 1/5 0 0 30
a4 － M 0 0 -3/25 0 -2/25 -1 1 8
Zj 50 40 (70+3M)/25 0 (130+2M)/25 M － M
Cj－ Zj 0 0 - (70+3M)/25 0 - (130+2M)/25－ M 0 1980-8M
此时,,最优解,x1 = 30,x2 = 12 仍无法满足第四约束,这是因为人工变量 a4 无法出基导致的,a4 = 8 破坏了这个约束 。
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
二,解无界
1,计算机输出结果显示,The solution to this
problem is unbounded
2,当迭代 过程中出现枢列中所有系数 a ij? 0,而 无法确定 出基 变量时,L.P,模型的解无界,这只能说明模型本身有失误之处,与单形法无关
3,例子 max 20x1 + 10x2
s.t.
x1? 2
x2? 5
x1,x2? 0。
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
二,解无界
3,例子中 x1 入基以后 （ 第一次迭代后 ） 的单形表是
B CB x1 x2 s1 s2 a1
20 10 0 0 － M b i
x1 20 1 0 -1 0 1 2
s2 0 0 1 0 1 0 5
Zj 20 0 -20 0 20
Cj－ Zj 0 10 20 0 － M-20 40
显然,新的入基变量是 s1,但因为 s1 系数列元素分别是－ 1
和 0,无法求出 b i / a i3,也就无法确定出基变量,无界 。
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
三,无穷多解
1,计算机输出结果没有异样表示,给出其中一个最优解而已
2,当一个或多个 非 基变量的检验值 Cj－ Zj = 0 时,L.P,模型有无穷多个解
3,例子
max 30x1 + 50x2
s.t.
3x1 + 5x2? 150
x2? 20
8x1 + 5x2? 300
x1,x2? 0
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
三,无穷多解上述模型最终单形表是
B CB x1 x2 s1 s2 s3
30 50 0 0 0 b i
x2 50 0 1 0 1 0 20
s3 0 0 0 -8/3 25/3 1 200/3
x1 30 1 0 1/3 -5/3 0 50/3
Zj 30 50 10 0 0
Cj－ Zj 0 0 -10 0 0 1500
非基变量 s2 之检验系数为 0,说明,s2 入基并不会改变 o.f,的值,如果试着将 s2 入基,可得下列单形表 。
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
三,无穷多解
B CB x1 x2 s1 s2 s3
30 50 0 0 0 b i
x2 50 0 1 8/25 0 -3/25 12
s2 0 0 0 -8/25 1 3/25 8
x1 30 1 0 -1/5 0 1/5 30
Zj 30 50 10 0 0
Cj－ Zj 0 0 -10 0 0 1500
由于两种情形下所有 Cj－ Zj? 0,故,都是最优解 。 这提示我们解有无穷多个 。
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
实际上,利用单形法也可以方便地对
L.P,模型进行敏感性分析 。 由于时间关系,略去 。
第四节 单形法使用中的特殊情况凌晨,凌晨,
Ling Xueling
1,用单形法求解：
Max 2.5 x1 + 5 x2 + x3 + x4
s.t.
x1 + 1.4 x2 + 0.2 x3 + 0.8 x4? 1600
2 x1 + 2 x2 + 1.6 x3 + x4? 1300
1.2 x1 + x2 + x3 + 1.2 x4? 960
x1,x2,x3,x4? 0
第五章 习题布置凌晨,凌晨,
Ling Xueling
2,用单形法求解：
Min 4 x1 + 2 x2 + 33
s.t.
x1 + 3 x2? 15
x1 + 2x3? 10
2 x1 + x2? 20
x1,x2,x3? 0
第五章 习题布置凌晨,凌晨,
Ling Xueling
The End of Chapter 5
