(整理)第一章线性规划及单纯形法.

由天下分享时间：2024/12/11 17:49:02 加入收藏我要投稿点赞

精品文档

第一章

线性规划及单纯形法

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

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?