1
第五章 线性规划一,线性规划的基本概念二,求解线性规划的单纯形法三,初始基本可行解
2
某厂生产甲,乙两种产品,已知,① 两种产品分别由两条生产线生产 。 第一条生产甲,每天最多生产 9件,第二条生产乙,每天最多生产 7件；
② 该厂仅有工人 24名,生产甲每件用 2工日,生产乙每件用 3工日； ③ 产品甲,乙的单件利润分别为 40元和 80元 。 问工厂如何组织生产才能获得最大利润？
一）应用实例一,线性规划的基本概念
3
日利润最大生产能力限制劳动力限制变量非负
.,21 xx解,设甲、乙两种产品的日产件数分别为
0,
2432
7
9
8040)(m a x
21
21
2
1
2
21
xx
xx
x
x
RDX
xxXF
s.t.
4
二 )线性规划的一般形式
0,...,
...
.,,,,,
...
...
...)(m i n
21
2211
22222121
11212111
2211
n
mnmnmm
nn
nn
nn
xxx
bxaxaxa
bxaxaxa
bxaxaxa
xcxcxcXF
s.t.
特点,1)为极小化问题 ; 2)约束取等号 ;
3)限定系数非负 ; 4)变量非负,
式中,— 价值系数； — 结构系数
— 限定系数
jc ija
ib
5
将数学模型化为标准型的方法
1）将极大化问题化为极小化问题
ii bXg?)()1( 若
ii bXg?)()2( 若
kx
— 松弛变量
///
jjj xxx
（开关变量）
（两边乘 -1）4）将负的限定系数化为正值
3）将任意变量化为非负变量
2）将不等式约束变为等式约束：
— 目标函数变号；
iki bxXg )(
iki bxXg )(
6
0,.,,,,
2432
7
9
8040)(m i n
521
521
42
31
5
21
xxx
xxx
xx
xx
RDX
xxXF
s.t.
化为标准型,
7
三）线性规划的基本概念
0,
2432
7
9
8040)(m a x
21
21
2
1
2
21
xx
xx
x
x
RDX
xxXF
s.t.
1.线性规划的图解 x2
x1
0
F=0
F*=620(1.5,7)
8
2,线性规划的基本概念
1）可行解
— 满足约束条件及非负条件的解。
（ D内及其边界上的解）
2）基本解
— 使 n-m个变量等于 0，解约束方程组 (共有 m个约束方程 )所得的解。
基本解对应于约束边界的交点,
3）基本可行解
— 可行域中的基本解（即 D的顶点）。
4）基本变量与非基本变量预先取为零值的 n-m个变量为非基本变量，其余 m个为基本变量。
03?x
x2
x1
0
F=0
F*=-620(1.5,7)
04?x
05?x01?x
02?x
0,.,,,,
2432
7
9
8040)(m i n
521
521
42
31
5
21
xxx
xxx
xx
xx
RDX
xxXF
s.t.
9
四）线性规划的基本性质
1）可行域 D为凸集，每个基本可行解对应于 D上的一个顶点；
2）只要可行域存在且封闭，则起码有一个基本可行解为最优点；
*ⅰ ）若最优点所在的边界线与等值线平行，则该边界线上的点均为最优点；
ⅱ ）若可行域不封闭，则可能有无界解。
3)最优点可在 D的顶点中寻找。
10
二,求解线性规划的单纯形法一 )基本思路先取 D的一个顶点作为初始点,由此出发朝可使目标函数降低最快的方向依次经过一系列的基本可行解,直至达到最优解,
*1)需获得一个初始基本可行解 ;
2)每次只更换一个非基本变量 ;
3)保证下降性和可行性,
11
二 )计算实例
6,...,2,1,...0
532
442
53224)(m i n
64321
54321
654321
jx
xxxxx
xxxxx
xxxxxxXF
j
s.t.
1.初始基本可行解取 x5,x6 为基本变量,则有,
)0(X [0 0 0 0 4 5]
T
375543)0(F
12
2.第一次变换顶点
(1)选取进基变量
① 原则,考虑下降性,且下降得最快
② 判别数,假定 x2进基,则有
52
4
62
52
xx
xx
02
0
62
52
xx
xx
取 1
2x,15x 26x
相应的目标函数变化量,
111032532 6522 xxx?
12a?
22a?
即 )(
22612522 acacc
6,...,2,1,...0
532
442
53224)(m i n
64321
54321
654321
jx
xxxxx
xxxxx
xxxxxxXF
j
13
写成一般形式,
m
i
ijBijjjj acczc
1
1515432
2035231
1125132
415134
4
3
2
1
最小,x3 应为进基变量
3?
推论,
若线性规划的一个基本可行解的所有进基判别数均为非负,则该解为最优解,
6,...,2,1,...0
532
442
53224)(m i n
64321
54321
654321
jx
xxxxx
xxxxx
xxxxxxXF
j
14
(2)确定离基变量
① 原则,考虑可行性 (该变量离基后,能使余下的基本变量为非负 )
② 判别数,
)
3
5(335
)2(224
336
335
xxx
xxx由于
ⅰ) 若取 (离基 ),则有
05?x 02 63 xx
03235 53 xx
)/(
)/(
323223
313113
xaba
xaba
ij
i
i a
b
,,...,2,1 mi? 进基变量下标j
应取 为正且其值为最小者对应的基本变量离基,
i?
6,...,2,1,...0
532
442
53224)(m i n
64321
54321
654321
jx
xxxxx
xxxxx
xxxxxxXF
j
(可行 )
(不可行 )
06?xⅱ) 若取 (离基 ),则有
15
ⅱ) 推论,若线性规划的的所有离基判别数均为负数时,则问题有无界解,
最小,x6 应为离基变量
2?
)1(X [0 0 5/3 0 2/3 0]
T
3
11
3
23
3
5)1(F
* ⅰ) 因为,故 也必须大于 0,否则不满足可行性要求 ;
0,21?bb 2313,aa
6,...,2,1,...0
532
442
53224)(m i n
64321
54321
654321
jx
xxxxx
xxxxx
xxxxxxXF
j
)
3
5
(335
)2(224
336
335
xxx
xxx
16
进基4x
3.第二次变换顶点去掉了
6x
5,.,,,2,1,.,,0
532
442
3224)(m i n
4321
54321
54321
jx
xxxx
xxxxx
xxxxxXF
j
(1)
(2)
1)确定进基变量
0
3
1
8
3
10
3
3
1
12
3
1
2
3
1
3
3
2
12
3
2
2
3
1
3
3
1
14
4
2
1
:3)2(? (3)
(4)
3
5
3
1
3
2
3
1
4321 xxxx
:)1()2()3(
3
2
3
10
3
1
3
1
5421 xxxx
m
i
ijBijj acc
1
17
2)确定离基变量
2.0
3
10
/
3
2
5
3
1
/
3
5
2
1
离基5x
(1)
(2)
4321 224)(m i n xxxxXF
3
2
3
10
3
1
3
1
3
5
3
1
3
2
3
1
421
4321
xxx
xxxx
)2(X [0 0 8/5 1/5 0 0]
T
251258)2(F
:310/)2( (3)
(4)
5
1
10
1
10
1
421 xxx
:)1()31()3( 58107103 321 xxx
35313231 4321 xxxx
323103131 5421 xxxx
18
4,第三次变换顶点
1) 确定进基变量
05.1
10
1
2
10
7
12
05.3
10
1
2
10
3
14
2
1
故 为最优点,为最优值,)2(X
)2(F
)2(* XX [0 0 8/5 1/5 0 0]
T
251258)2(* FF
5
1
10
1
10
1
421 xxx
5
8
10
7
10
3
321 xxx
4321 224)(m i n xxxxXF
19
三 )用单纯形表求解线性规划例,用初等变换法求解解,增广矩阵,?
112
545
21
21
xx
xx
1112
545
,
510
301
1112
301
1112
39013
5
3
2
1
x
x
20
6,...,2,1,...0
532
442
53224)(m i n
64321
54321
654321
jx
xxxxx
xxxxx
xxxxxxXF
j
s.t.
离基判别数进基判别数单纯形法实际上是解一系列的线性方程组,也可用初等变换方法列表求解,但需加入判别数的计算,
4 2 1 2 3 5
基变量 x1 x2 x3 x4 x5 x6
3 x5 1 1 2 4 1 0 4 2
5 x6 1 2 3 1 0 1 5 5/3
X0 0 0 0 0 4 5 F0 37
-4 -11 -20 -15
jc
Bic ib i?
j?
例 1
21
4 2 1 2 3
基变量 x1 x2 x3 x4 x5 x6
3 x5 1/3 -1/3 0 10/3 1 2/3 0.2
1 x3 1/3 2/3 1 1/3 0 5/3 5
X1 0 0 5/3 0 2/3 0 F1 11/3
8/3 7/3 -25/3
jc
Bic ib i?
j?
4 2 1 2 3 5
基变量 x1 x2 x3 x4 x5 x6
3 x5 1 1 2 4 1 0 4 2
5 x6 1 2 3 1 0 1 5 5/3
X0 0 0 0 0 4 5 F0 37
-4 -11 -20 -15
jc
Bic ib i?
j?
22
4 2 1 2 3
基变量 x1 x2 x3 x4 x5 x6
3 x5 1/3 -1/3 0 10/3 1 2/3 0.2
1 x3 1/3 2/3 1 1/3 0 5/3 5
X1 0 0 5/3 0 2/3 0 F1 11/3
8/3 7/3 -25/3
jc
Bic ib i?
j?
4 2 1 2
基变量 x1 x2 x3 x4 x5 x6
2 x4 1/10 -1/10 0 1 0.2
1 x3 3/10 7/10 1 0 1.6
X2 0 0 1.6 0.2 0 0 F2 2
3.5 1.5
jc
Bic ib i?
j?
已获得最优解
23
-2 -3 0 0
基变量 x1 x2 x3 x4
0 x3 -1 1 1 0 3 3
0 x4 1 -4 0 1 4 -1
X0 0 0 3 4 F0 0
-2 -3
jc
Bic ib i?
j?
-2 -3 0
基变量 x1 x2 x3 x4
-3 x2 -1 1 0 3 -3
0 x4 -3 0 1 16 -16/3
X1 0 3 0 16 F1 -9
-5
jc
Bic ib i?
j?
4,.,,,2,1,.,,0
44
3
32)(m i n
421
321
21
jx
xxx
xxx
xxXF
j
s.t.
例 2
问题有无界解
24
三,初始基本可行解
(1)大 M法引入一组人工变量,它们在目标函数中的系数均是非常大的正数 M;
(2) 两相法引入一组人工变量,在人工变量未完全离基前目标函数为各人工变量之和,当人工变量完全离基后恢复原目标函数。
当 A内不包含单位矩阵时,需引入由人工变量组成的单位矩阵,以方便获得初始可行解,
25
一 )采用大 M法获得初始基本可行解
543214)(m i n MxMxxxxXF
333
422
5321
4321
xxxx
xxxx
,0?jx 5,...,2,1?j
s.t.
采用大 M法,
3214)(m i n xxxXF
333
422
321
321
xxx
xxx
,0?jx 3,2,1?j
s.t.原问题,
因 M是比其他价值系数大得多的正数,且人工变量非负,迭代的结果会使人工变量趋于零,而获得原问题的基本可行解,
26
543214)(m i n MxMxxxxXF
333
422
5321
4321
xxxx
xxxx
,0?jx 5,...,2,1?j
s.t.
4 1 1 M M
基变量 x1 x2 x3 x4 x5
M x4 2 1 2 1 0 4 2
M x5 3 3 1 0 1 3 1
X0 0 0 0 4 3 F0 7M
4-5M 1-4M 1-3M
jc
Bic ib i?
j?
表一
27
4 1 1 M M
基变量 x1 x2 x3 x4 x5
M x4 2 1 2 1 0 4 2
M x5 3 3 1 0 1 3 1
X0 0 0 0 4 3 F0 7M
4-5M 1-4M 1-3M
jc
Bic ib i?
j?
4 1 1 M
基变量 x1 x2 x3 x4 x5
M x4 0 -1 4/3 1 2 1.5
4 x1 1 1 1/3 0 1 3
X1 1 0 0 2 0 F1 4+2M
-3+M -4/3-4M/3
jc
Bic ib i?
j?
表一表二
28
4 1 1
基变量 x1 x2 x3 x4 x5
1 x3 0 -3/4 1 1.5 -2
4 x1 1 5/4 0 0.5 0.4
X2 0.5 0 1.5 F2 3.5
0 -13/4 0
jc
Bic ib i?
j?
表三初始基本可行解
4 1 1 M
基变量 x1 x2 x3 x4 x5
M x4 0 -1 4/3 1 2 1.5
4 x1 1 1 1/3 0 1 3
X1 1 0 0 2 0 F1 4+2M
-3+M -4/3-4M/3
jc
Bic ib i?
j?
表二
29
4 1 1
基变量 x1 x2 x3 x4 x5
1 x3 0 -3/4 1 1.5 -2
4 x1 1 5/4 0 0.5 0.4
X2 0.5 0 1.5 F2 3.5
0 -13/4 0
jc
Bic ib i?
j?
4 1 1
基变量 x1 x2 x3 x4 x5
1 x3 0 1 1.8
1 x2 1 0 0.4
X3 0 0.4 1.8 F3 2.2
jc
Bic ib i?
j?
表三表四初始基本可行解最优解
30
二 )采用两相法获得初始基本可行解大 M法的 M是一个充分大的正数,有时在计算机上不便处理,
3214)(m in xxxXF
333
422
321
321
xxx
xxx
,0?jx 3,2,1?j
s.t.原问题：
54'm in xxF
333
422
5321
4321
xxxx
xxxx
,0?jx 3,2,1?j
s.t.相 1问题：
31
0 0 0 1 1
基变量 x1 x2 x3 x4 x5
1 x4 2 1 2 1 0 4 2
1 x5 3 3 1 0 1 3 1
X’0 0 0 0 4 3 F’0 7
-5 -4 -3
jc
Bic ib i?
j?
0 0 0 1
基变量 x1 x2 x3 x4 x5
1 x4 0 -1 4/3 1 2 1.5
0 x1 1 1 1/3 0 1 3
X’1 1 0 0 2 0 F’1 2
1 -4/3
jc
Bic ib i?
j?
表一表二
32
0 0 0
基变量 x1 x2 x3 x4 x5
0 x3 0 -3/4 1 1.5 -2
0 x1 1 5/4 0 0.5 0.4
X’2 0.5 0 1.5 F’2 0
0
jc
Bic ib i?
j?
表三初始基本可行解
4 1 1
基变量 x1 x2 x3 x4 x5
1 x3 0 -3/4 1 1.5 -2
4 x1 1 5/4 0 0.5 0.4
X0 0.5 0 1.5 F0 3.5
-13/4
jc
Bic ib i?
j?
表四初始基本可行解换相
33
4 1 1
基变量 x1 x2 x3 x4 x5
1 x3 0 1 1.8
1 x2 1 0 0.4
X1 0 0.4 1.8 F1 2.2
13/5
jc
Bic ib i?
j?
表五最优解
第五章 线性规划一,线性规划的基本概念二,求解线性规划的单纯形法三,初始基本可行解
2
某厂生产甲,乙两种产品,已知,① 两种产品分别由两条生产线生产 。 第一条生产甲,每天最多生产 9件,第二条生产乙,每天最多生产 7件；
② 该厂仅有工人 24名,生产甲每件用 2工日,生产乙每件用 3工日； ③ 产品甲,乙的单件利润分别为 40元和 80元 。 问工厂如何组织生产才能获得最大利润？
一）应用实例一,线性规划的基本概念
3
日利润最大生产能力限制劳动力限制变量非负
.,21 xx解,设甲、乙两种产品的日产件数分别为
0,
2432
7
9
8040)(m a x
21
21
2
1
2
21
xx
xx
x
x
RDX
xxXF
s.t.
4
二 )线性规划的一般形式
0,...,
...
.,,,,,
...
...
...)(m i n
21
2211
22222121
11212111
2211
n
mnmnmm
nn
nn
nn
xxx
bxaxaxa
bxaxaxa
bxaxaxa
xcxcxcXF
s.t.
特点,1)为极小化问题 ; 2)约束取等号 ;
3)限定系数非负 ; 4)变量非负,
式中,— 价值系数； — 结构系数
— 限定系数
jc ija
ib
5
将数学模型化为标准型的方法
1）将极大化问题化为极小化问题
ii bXg?)()1( 若
ii bXg?)()2( 若
kx
— 松弛变量
///
jjj xxx
（开关变量）
（两边乘 -1）4）将负的限定系数化为正值
3）将任意变量化为非负变量
2）将不等式约束变为等式约束：
— 目标函数变号；
iki bxXg )(
iki bxXg )(
6
0,.,,,,
2432
7
9
8040)(m i n
521
521
42
31
5
21
xxx
xxx
xx
xx
RDX
xxXF
s.t.
化为标准型,
7
三）线性规划的基本概念
0,
2432
7
9
8040)(m a x
21
21
2
1
2
21
xx
xx
x
x
RDX
xxXF
s.t.
1.线性规划的图解 x2
x1
0
F=0
F*=620(1.5,7)
8
2,线性规划的基本概念
1）可行解
— 满足约束条件及非负条件的解。
（ D内及其边界上的解）
2）基本解
— 使 n-m个变量等于 0，解约束方程组 (共有 m个约束方程 )所得的解。
基本解对应于约束边界的交点,
3）基本可行解
— 可行域中的基本解（即 D的顶点）。
4）基本变量与非基本变量预先取为零值的 n-m个变量为非基本变量，其余 m个为基本变量。
03?x
x2
x1
0
F=0
F*=-620(1.5,7)
04?x
05?x01?x
02?x
0,.,,,,
2432
7
9
8040)(m i n
521
521
42
31
5
21
xxx
xxx
xx
xx
RDX
xxXF
s.t.
9
四）线性规划的基本性质
1）可行域 D为凸集，每个基本可行解对应于 D上的一个顶点；
2）只要可行域存在且封闭，则起码有一个基本可行解为最优点；
*ⅰ ）若最优点所在的边界线与等值线平行，则该边界线上的点均为最优点；
ⅱ ）若可行域不封闭，则可能有无界解。
3)最优点可在 D的顶点中寻找。
10
二,求解线性规划的单纯形法一 )基本思路先取 D的一个顶点作为初始点,由此出发朝可使目标函数降低最快的方向依次经过一系列的基本可行解,直至达到最优解,
*1)需获得一个初始基本可行解 ;
2)每次只更换一个非基本变量 ;
3)保证下降性和可行性,
11
二 )计算实例
6,...,2,1,...0
532
442
53224)(m i n
64321
54321
654321
jx
xxxxx
xxxxx
xxxxxxXF
j
s.t.
1.初始基本可行解取 x5,x6 为基本变量,则有,
)0(X [0 0 0 0 4 5]
T
375543)0(F
12
2.第一次变换顶点
(1)选取进基变量
① 原则,考虑下降性,且下降得最快
② 判别数,假定 x2进基,则有
52
4
62
52
xx
xx
02
0
62
52
xx
xx
取 1
2x,15x 26x
相应的目标函数变化量,
111032532 6522 xxx?
12a?
22a?
即 )(
22612522 acacc
6,...,2,1,...0
532
442
53224)(m i n
64321
54321
654321
jx
xxxxx
xxxxx
xxxxxxXF
j
13
写成一般形式,
m
i
ijBijjjj acczc
1
1515432
2035231
1125132
415134
4
3
2
1
最小,x3 应为进基变量
3?
推论,
若线性规划的一个基本可行解的所有进基判别数均为非负,则该解为最优解,
6,...,2,1,...0
532
442
53224)(m i n
64321
54321
654321
jx
xxxxx
xxxxx
xxxxxxXF
j
14
(2)确定离基变量
① 原则,考虑可行性 (该变量离基后,能使余下的基本变量为非负 )
② 判别数,
)
3
5(335
)2(224
336
335
xxx
xxx由于
ⅰ) 若取 (离基 ),则有
05?x 02 63 xx
03235 53 xx
)/(
)/(
323223
313113
xaba
xaba
ij
i
i a
b
,,...,2,1 mi? 进基变量下标j
应取 为正且其值为最小者对应的基本变量离基,
i?
6,...,2,1,...0
532
442
53224)(m i n
64321
54321
654321
jx
xxxxx
xxxxx
xxxxxxXF
j
(可行 )
(不可行 )
06?xⅱ) 若取 (离基 ),则有
15
ⅱ) 推论,若线性规划的的所有离基判别数均为负数时,则问题有无界解,
最小,x6 应为离基变量
2?
)1(X [0 0 5/3 0 2/3 0]
T
3
11
3
23
3
5)1(F
* ⅰ) 因为,故 也必须大于 0,否则不满足可行性要求 ;
0,21?bb 2313,aa
6,...,2,1,...0
532
442
53224)(m i n
64321
54321
654321
jx
xxxxx
xxxxx
xxxxxxXF
j
)
3
5
(335
)2(224
336
335
xxx
xxx
16
进基4x
3.第二次变换顶点去掉了
6x
5,.,,,2,1,.,,0
532
442
3224)(m i n
4321
54321
54321
jx
xxxx
xxxxx
xxxxxXF
j
(1)
(2)
1)确定进基变量
0
3
1
8
3
10
3
3
1
12
3
1
2
3
1
3
3
2
12
3
2
2
3
1
3
3
1
14
4
2
1
:3)2(? (3)
(4)
3
5
3
1
3
2
3
1
4321 xxxx
:)1()2()3(
3
2
3
10
3
1
3
1
5421 xxxx
m
i
ijBijj acc
1
17
2)确定离基变量
2.0
3
10
/
3
2
5
3
1
/
3
5
2
1
离基5x
(1)
(2)
4321 224)(m i n xxxxXF
3
2
3
10
3
1
3
1
3
5
3
1
3
2
3
1
421
4321
xxx
xxxx
)2(X [0 0 8/5 1/5 0 0]
T
251258)2(F
:310/)2( (3)
(4)
5
1
10
1
10
1
421 xxx
:)1()31()3( 58107103 321 xxx
35313231 4321 xxxx
323103131 5421 xxxx
18
4,第三次变换顶点
1) 确定进基变量
05.1
10
1
2
10
7
12
05.3
10
1
2
10
3
14
2
1
故 为最优点,为最优值,)2(X
)2(F
)2(* XX [0 0 8/5 1/5 0 0]
T
251258)2(* FF
5
1
10
1
10
1
421 xxx
5
8
10
7
10
3
321 xxx
4321 224)(m i n xxxxXF
19
三 )用单纯形表求解线性规划例,用初等变换法求解解,增广矩阵,?
112
545
21
21
xx
xx
1112
545
,
510
301
1112
301
1112
39013
5
3
2
1
x
x
20
6,...,2,1,...0
532
442
53224)(m i n
64321
54321
654321
jx
xxxxx
xxxxx
xxxxxxXF
j
s.t.
离基判别数进基判别数单纯形法实际上是解一系列的线性方程组,也可用初等变换方法列表求解,但需加入判别数的计算,
4 2 1 2 3 5
基变量 x1 x2 x3 x4 x5 x6
3 x5 1 1 2 4 1 0 4 2
5 x6 1 2 3 1 0 1 5 5/3
X0 0 0 0 0 4 5 F0 37
-4 -11 -20 -15
jc
Bic ib i?
j?
例 1
21
4 2 1 2 3
基变量 x1 x2 x3 x4 x5 x6
3 x5 1/3 -1/3 0 10/3 1 2/3 0.2
1 x3 1/3 2/3 1 1/3 0 5/3 5
X1 0 0 5/3 0 2/3 0 F1 11/3
8/3 7/3 -25/3
jc
Bic ib i?
j?
4 2 1 2 3 5
基变量 x1 x2 x3 x4 x5 x6
3 x5 1 1 2 4 1 0 4 2
5 x6 1 2 3 1 0 1 5 5/3
X0 0 0 0 0 4 5 F0 37
-4 -11 -20 -15
jc
Bic ib i?
j?
22
4 2 1 2 3
基变量 x1 x2 x3 x4 x5 x6
3 x5 1/3 -1/3 0 10/3 1 2/3 0.2
1 x3 1/3 2/3 1 1/3 0 5/3 5
X1 0 0 5/3 0 2/3 0 F1 11/3
8/3 7/3 -25/3
jc
Bic ib i?
j?
4 2 1 2
基变量 x1 x2 x3 x4 x5 x6
2 x4 1/10 -1/10 0 1 0.2
1 x3 3/10 7/10 1 0 1.6
X2 0 0 1.6 0.2 0 0 F2 2
3.5 1.5
jc
Bic ib i?
j?
已获得最优解
23
-2 -3 0 0
基变量 x1 x2 x3 x4
0 x3 -1 1 1 0 3 3
0 x4 1 -4 0 1 4 -1
X0 0 0 3 4 F0 0
-2 -3
jc
Bic ib i?
j?
-2 -3 0
基变量 x1 x2 x3 x4
-3 x2 -1 1 0 3 -3
0 x4 -3 0 1 16 -16/3
X1 0 3 0 16 F1 -9
-5
jc
Bic ib i?
j?
4,.,,,2,1,.,,0
44
3
32)(m i n
421
321
21
jx
xxx
xxx
xxXF
j
s.t.
例 2
问题有无界解
24
三,初始基本可行解
(1)大 M法引入一组人工变量,它们在目标函数中的系数均是非常大的正数 M;
(2) 两相法引入一组人工变量,在人工变量未完全离基前目标函数为各人工变量之和,当人工变量完全离基后恢复原目标函数。
当 A内不包含单位矩阵时,需引入由人工变量组成的单位矩阵,以方便获得初始可行解,
25
一 )采用大 M法获得初始基本可行解
543214)(m i n MxMxxxxXF
333
422
5321
4321
xxxx
xxxx
,0?jx 5,...,2,1?j
s.t.
采用大 M法,
3214)(m i n xxxXF
333
422
321
321
xxx
xxx
,0?jx 3,2,1?j
s.t.原问题,
因 M是比其他价值系数大得多的正数,且人工变量非负,迭代的结果会使人工变量趋于零,而获得原问题的基本可行解,
26
543214)(m i n MxMxxxxXF
333
422
5321
4321
xxxx
xxxx
,0?jx 5,...,2,1?j
s.t.
4 1 1 M M
基变量 x1 x2 x3 x4 x5
M x4 2 1 2 1 0 4 2
M x5 3 3 1 0 1 3 1
X0 0 0 0 4 3 F0 7M
4-5M 1-4M 1-3M
jc
Bic ib i?
j?
表一
27
4 1 1 M M
基变量 x1 x2 x3 x4 x5
M x4 2 1 2 1 0 4 2
M x5 3 3 1 0 1 3 1
X0 0 0 0 4 3 F0 7M
4-5M 1-4M 1-3M
jc
Bic ib i?
j?
4 1 1 M
基变量 x1 x2 x3 x4 x5
M x4 0 -1 4/3 1 2 1.5
4 x1 1 1 1/3 0 1 3
X1 1 0 0 2 0 F1 4+2M
-3+M -4/3-4M/3
jc
Bic ib i?
j?
表一表二
28
4 1 1
基变量 x1 x2 x3 x4 x5
1 x3 0 -3/4 1 1.5 -2
4 x1 1 5/4 0 0.5 0.4
X2 0.5 0 1.5 F2 3.5
0 -13/4 0
jc
Bic ib i?
j?
表三初始基本可行解
4 1 1 M
基变量 x1 x2 x3 x4 x5
M x4 0 -1 4/3 1 2 1.5
4 x1 1 1 1/3 0 1 3
X1 1 0 0 2 0 F1 4+2M
-3+M -4/3-4M/3
jc
Bic ib i?
j?
表二
29
4 1 1
基变量 x1 x2 x3 x4 x5
1 x3 0 -3/4 1 1.5 -2
4 x1 1 5/4 0 0.5 0.4
X2 0.5 0 1.5 F2 3.5
0 -13/4 0
jc
Bic ib i?
j?
4 1 1
基变量 x1 x2 x3 x4 x5
1 x3 0 1 1.8
1 x2 1 0 0.4
X3 0 0.4 1.8 F3 2.2
jc
Bic ib i?
j?
表三表四初始基本可行解最优解
30
二 )采用两相法获得初始基本可行解大 M法的 M是一个充分大的正数,有时在计算机上不便处理,
3214)(m in xxxXF
333
422
321
321
xxx
xxx
,0?jx 3,2,1?j
s.t.原问题：
54'm in xxF
333
422
5321
4321
xxxx
xxxx
,0?jx 3,2,1?j
s.t.相 1问题：
31
0 0 0 1 1
基变量 x1 x2 x3 x4 x5
1 x4 2 1 2 1 0 4 2
1 x5 3 3 1 0 1 3 1
X’0 0 0 0 4 3 F’0 7
-5 -4 -3
jc
Bic ib i?
j?
0 0 0 1
基变量 x1 x2 x3 x4 x5
1 x4 0 -1 4/3 1 2 1.5
0 x1 1 1 1/3 0 1 3
X’1 1 0 0 2 0 F’1 2
1 -4/3
jc
Bic ib i?
j?
表一表二
32
0 0 0
基变量 x1 x2 x3 x4 x5
0 x3 0 -3/4 1 1.5 -2
0 x1 1 5/4 0 0.5 0.4
X’2 0.5 0 1.5 F’2 0
0
jc
Bic ib i?
j?
表三初始基本可行解
4 1 1
基变量 x1 x2 x3 x4 x5
1 x3 0 -3/4 1 1.5 -2
4 x1 1 5/4 0 0.5 0.4
X0 0.5 0 1.5 F0 3.5
-13/4
jc
Bic ib i?
j?
表四初始基本可行解换相
33
4 1 1
基变量 x1 x2 x3 x4 x5
1 x3 0 1 1.8
1 x2 1 0 0.4
X1 0 0.4 1.8 F1 2.2
13/5
jc
Bic ib i?
j?
表五最优解
