精品文档
第一章
线性规划及单纯形法
1.1 用图解法求解下列线性规划问题。并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。 (a) min z=2x1+3x2 s.t. 4x1+6x2≥6
4x1+2x2≥4 x1, x2≥0
(b) max z=3x1+2x2 3x1+4x2≥12
x1,x2≥0
s.t. 2x1+x2≤2
(c) max z=x1+x2
5≤x1≤10 3≤x2≤8
(d) max z=5x1+6x2
s.t. 2x1-x2≥2
-2x1+3x2≤2
x1,x2≥0
s.t. 6x1+10x2≥120
解:
x2 3 (a) 2 L1 Lz 1 L2 1 2 x1 1 2 3 4 L1 Lz L2 x2 3 (b) x1
x2 x2 2 Lz x1 -1 x1 10 20 -2 1 2 (d) (c) 15 10 Lz 5
如图所示:(a) 有无穷多最优解;(b) 无可行解;(c) 有唯一最优解; (d) 无界解
精品文档
精品文档
1.3 用单纯形法求解下述线性规划问题
max z=10x1+5x2 s.t. 3x1+4x2≤9
5x1+2x2≤8 x1, x2≥0
解:
将此问题化成标准形式,
max z=10x1+5x2+0x3+0x4 s.t. 3x1+4x2+x3 =9
5x1+2x2
+x4=8
x1, x2, x3, x4≥0
P1P2P3P4?3410? ?5201???其约束系数矩阵:
单纯形法求解的过程见表如下 CB 0 0
由于10>5, 选择x1作为换入基的变量。对于P1有:
θ=min{ b1/a11, b2/a21 | a11,a21>0 }=min{9/3, 8/5 }=8/5. 确定x4为换出基变量。5为主元素 CB 0 10
精品文档
Cj→ 基 X3 X4 Cj-zj 单纯形法的求解过程 b 9 8 10 X1 3 5 10 5 X2 4 2 5 0 X3 1 0 0 0 X4 0 1 0 Cj→ 基 X3 X1 Cj-zj 单纯形法的求解过程 b 21/5 8/5 0 1 0 14/5 2/5 1 10 X1 X2 5 0 X3 1 0 0 0 X4 -3/5 1/5 -2 精品文档
由于1>0, 选择x2作为换入基的变量。对于P2有:
θ=min{ b1/a12, b2/a22 | a12,a22>0 }=min{(21/5)/(14/5),(8/5)/(2/5) }=21/14. 确定x3为换出基变量。2/5为主元素 CB 5 10
至此,所有检验数σj≤0,表明已找到最优解x1=1, x2=1.5, x3=0, x4=0 max z=10x1+5x2=17.5
x2 Lz 3 2 L2 Cj→ 基 X2 X1 Cj-zj 单纯形法的求解过程 b 3/2 1 10 X1 0 1 0 5 X2 1 0 0 0 X3 5/14 -1/7 -5/14 0 X4 -3/14 10/35 -25/14 (c) 1 L1 x1 2 4
1.8 已知某线性规划问题的初始单纯性表(1-23)和用单纯形法迭代后得到的表(1-24)如下,试求括弧中未知数q~l的值。 x4 x5 cj-zj x1 精品文档
表1-23 6 1 表1-24 (f) x1 (g) x1 (b) -1 (a) x2 (c) 3 -1 x2 2 x3 (d) (e) 2 x3 -1 x4 1 0 0 x4 1/2 x5 0 1 0 x5 0 精品文档
x5 cj-zj 解:
4 (h) 0 (i) -7 1 (j) 1/2 (k) 1 (l) 由表1-23和1-24可知换出变量为x4,换入变量为x1。又因为a21=-1<0 所以,主元只能是b。所以有g=1, h=0, c/b=2, d/b=-1, 1/b=1/2. 6/b=f 于是b=2, c=4, d=-2, f=3。将这些数值代入相应参数,表1-23变成 x4 x5 cj-zj x1 x5 cj-zj x1 x5 cj-zj 表1-23d 3 4 x1 1 0 0 x2 2 5 -2a-1 x3 -1 x4 1/2 1/2 -a/2 x5 0 1 0 表1-23b 6 1 表1-23c 3 1 x1 1 -1 (a) x1 2 -1 (a) x2 2 3 -1 x2 4 3 -1 x3 -1 (e) 2 x3 -2 (e) 2 x4 1/2 0 0 x4 1 0 0 x5 0 1 0 x5 0 1 0 主元所在行除2得:
由表1-23c将a21化为0得
(e-1) a+2 将表1-23d与表1-24比较后有:
e-1=1, e=2, i=5. 由检验数关系得-2a-1=-7,a=3; j=a+2=5; k=-a/2=-3/2; l=0 最终表2-24结果为 x1 x5 cj-zj
精品文档
表1-24a 3 4 x1 1 0 0 x2 2 5 -7 x3 -1 1 5 x4 1/2 1/2 -3/2 x5 0 1 0 精品文档
1.12 已知线性规划问题 x2 x3 cj-zj
max z=c1x1+c2x2+c3x3 s.t. x1+2x2+x3≤b
2x1+x2+3x3≤2b xj≥0 (j=1,2,3) 表1-25 1 3 x1 1/5 3/5 -7/10 x2 1 0 0 x3 0 1 0 x4 3/5 -1/5 -3/5 x5 -1/5 2/5 -4/5 用单纯形法求解得最终单纯形表1-25,表中x4, x5为松弛变量
试计算确定c1, c2, c3和b的值。
解:因为x4, x5为松弛变量,所以c4=c5=0. 由书中式1-23,对应x1,x4,x5检验数计算可有
?1?c1?137ciai1?c1?(c2a11?c3a21)?c1?[c2?c3]?? i?15510m??4?c4??5?c5???313ciai4?c4?(c2a14?c3a24)?0?[c2?c3]?? i?1555m
124ciai5?c5?(c2a15?c3a25)?0?[(?)c2?c3]?? i?1555m?1?1/5?3/5?7/10??3/5?其增广矩阵:??0?3/51/5?
??01/5?2/5?4/5???1001.5??0102??? ??0013??经初等变换得:
即c1=1.5, c2=2, c3=3,下面利用矩阵初等变换使x2,x3对应列向量构成一组基 ??→?2213012b???→??12110b??1/211/21/20b/2?→
13012b???1/211/21/20b/2??3/205/2?1/213b/2? ??0b/2??1/211/21/2?1/5103/5?1/5b/5?→??? 3/501?1/52/53b/53/501?1/52/53b/5????精品文档
(整理)第一章 线性规划及单纯形法.
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)