运筹学基础及应用(第一二章习题解答)
运筹学基础及应用 习题解答
习题一 P46 1.1 (a)
4
12
该问题有无穷多最优解，即满足4x 1
z =3。
+6x 2=6且0≤x 2≤
的所有(x 1, x 2)，此时目标函数值
(b)
用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。 1.2
(a) 约束方程组的系数矩阵
⎛12 A = 8
3⎝
310
6-40
300
020
0⎫⎪0⎪
-1⎪⎭
T
最优解x =(0, 10, 0, 7, 0, 0)
。
(b) 约束方程组的系数矩阵
⎛1A = 2
⎝
22
3
1
4⎫⎪2⎪⎭
最优解1.3
(a)
(1) 图解法
11⎫⎛2
x = , 0, , 0⎪
5⎝5⎭
T
。
最优解即为⎨
⎧3x 1+4x 2=9⎩5x 1+2x 2=8
的解x
⎛3⎫= 1, ⎪⎝2⎭
，最大值z
=
352
(2)单纯形法
首先在各约束条件上添加松弛变量，将问题转化为标准形式
max z =10x 1+5x 2+0x 3+0x 4⎧3x 1+4x 2+x 3=9s . t . ⎨
⎩5x 1+2x 2+x 4=8
则P 3, P 4组成一个基。令x 1=x 2=0
得基可行解x =(0, 0, 9, 8)，由此列出初始单纯形表
σ1>σ2。θ=min
⎛89⎫8
, ⎪=⎝53⎭5
σ2>0，θ=min
⎛218⎫3
, ⎪=142⎭2⎝
新的单纯形表为
σ1, σ2
32
, x 3=0 , x 4=0
。最大值
z
*
=
352
(b) (1) 图解法
6x 1+2x 2x 1+x 2=
最优解即为⎨
⎩
⎧6x 1+2x 2=24
x 1+x 2=5
的解x
⎛73⎫
= , ⎪⎝22⎭
，最大值z
=
172
(2) 单纯形法
首先在各约束条件上添加松弛变量，将问题转化为标准形式 m ax z =2x 1+x 2+0x 3+0x 4+0x 55x 2+x 3=15⎧⎪
s . t . ⎨6x 1+2x 2+x 4=24
⎪x +x +x =5⎩125
则P 3，P 4，P 5组成一个基。令x 1=x 2=0
得基可行解x =(0, 0,15, 24, 5)，由此列出初始单纯形表
σ1>σ2。θ=min -,
⎛⎝
245⎫
, ⎪=4
61⎭
⎛15⎝5
, 24,
σ2>0，θ=min
3⎫3
⎪= 2⎭2
新的单纯形表为
72
，x 3=
152
σ1, σ2
值 z *=1.6
172
' ' ' ' ' '
(a) 在约束条件中添加松弛变量或剩余变量，且令x 2=x 2-x 2 (x 2≥0, x 2≥0)
，
x 3=-x 3, z ' =-z
'
该问题转化为
max z ' =-3x 1-x 2+x 2-2x 3+0x 4+0x 5
' ' ' ' ⎧2x 1+3x 2-3x 2+4x 3+x 4=12
⎪' ' ' '
⎪4x 1+x 2-x 2-2x 3-x 5=8s . t . ⎨' ' ' '
3x 1-x 2+x 2-3x 3=6⎪
' ' ' ' ⎪x 1, x 2, x 2, x 3, x 4, x 5≥0⎩
'
' '
'
其约束系数矩阵为
⎛2
A = 4
3⎝
31-1
-3-11
4-2-3
100
0⎫⎪-1⎪0⎪⎭
在A 中人为地添加两列单位向量P 7, P 8
⎛2
4 3⎝
31-1
-3-11
4-2-3
100
0-10
010
0⎫⎪0⎪ 1⎪⎭
' ' ' '
令max z ' =-3x 1-x 2+x 2-2x 3+0x 4+0x 5-Mx 6-Mx 7
得初始单纯形表
z ' =-z ，
' '' ' ''
(b) 在约束条件中添加松弛变量或剩余变量，且令x 3=x 3-x 3 (x 3≥0, x 3≥0)
该问题转化为
m ax z ' =-3x 1-5x 2+x 3-x 3+0x 4+0x 5
' ''
⎧x 1+2x 2+x 3-x 3-x 4=6⎪' ''
⎪2x 1+x 2-3x 3-3x 3+x 5=16s . t . ⎨' ''
x +x +5x -5x =101233⎪
' ''
⎪x 1, x 2, x 3, x 3, x 4, x 5≥0⎩
'
''
其约束系数矩阵为 ⎛1 A =2
1⎝
211
135
-1-3-5
-100
0⎫⎪-1 ⎪0⎪⎭
在A 中人为地添加两列单位向量P 7, P 8 ⎛1
2 1⎝
211
135
-1-3-5
-100
010
100
'
0⎫⎪0 ⎪1⎪⎭
''
令m ax z ' =-3x 1-5x 2+x 3-x 3+0x 4+0x 5-M x 6-M x 7
1.7
(a)解1：大M 法
在上述线性规划问题中分别减去剩余变量x 4, x 6, x 8, 再加上人工变量x 5, x 7, x 9, 得
max z =2x 1-x 2+2x 3+0x 4-M x 5+0x 6-M x 7+0x 8-M x 9
x 1+x 2+x 3-x 4+x 5=6⎧⎪
-2x 1+x 3-x 6+x 7=2⎪
s , t , ⎨
2x 2-x 3-x 8+x 9=0⎪⎪⎩x 1, x 2, x 3, x 4, x 5, x 6, x 7, x 8, x 9≥0
其中M 是一个任意大的正数。据此可列出单纯形表
由单纯形表计算结果可以看出，σ4>0且a i 4
现在上述线性规划问题的约束条件中分别减去剩余变量x 4, x 6, x 8, 再加上人工变量
x 5, x 7, x 9, 得第一阶段的数学模型
据此可列出单纯形表
*
377
T
*
第一阶段求得的最优解X =(, , , 0, 0, 0, 0, 0, 0) , 目标函数的最优值ω=0。
442
因人工变量x 5=x 7=x 9=0，所以X
*=
(
377T
, , , 0, 0, 0, 0, 0, 0) 是原线性规划问题的基可442
行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。
由表中计算结果可以看出，σ4>0且a i 4
(b)解1：大M 法
在上述线性规划问题中分别减去剩余变量x 4, x 6, x 8, 再加上人工变量x 5, x 7, x 9, 得
min z =2x 1+3x 2+x 3+0x 4+0x 5+M x 6-M x 7
⎧x 1+4x 2+2x 3-x 4+x 6=8⎪
3x 1+2x 2-x 5+x 7=6⎪
s , t , ⎨
⎪⎪⎩x 1, x 2, x 3, x 4, x 5, x 6, x 7, x 8, x 9≥0
其中M 是一个任意大的正数。据此可列出单纯形表
*=
(
由单纯形表计算结果可以看出，最优解X
z =2⨯
*
49T
, , 0, 0, 0, 0, 0) ，目标函数的最优解值55
45
+3⨯
95
=7。X 存在非基变量检验数σ3=0，故该线性规划问题有无穷多最优解。
解2：两阶段法。
现在上述线性规划问题的约束条件中分别减去剩余变量x 4, x 5, 再加上人工变量x 6, x 7, 得第一阶段的数学模型m in ω=x 6+x 7 ⎧x 1+4x 2+2x 3-x 4+x 6=8⎪
3x 1+2x 2-x 5+x 7=6⎪
s , t , ⎨
⎪⎪⎩x 1, x 2, x 3, x 4, x 5, x 6, x 7, x 8, x 9≥0
据此可列出单纯形表
*=
(
49T *
, , 0, 0, 0, 0, 0) , 目标函数的最优值ω=0。 55
49T
因人工变量x 6=x 7=0，所以(, , 0, 0, 0, 0, 0) 是原线性规划问题的基可行解。于是可
55
第一阶段求得的最优解X
以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。
*=
(
由单纯形表计算结果可以看出，最优解X
z =2⨯
*
49T
, , 0, 0, 0, 0, 0) ，目标函数的最优解值55
45
+3⨯
95
由于存在非基变量检验数σ3=0，故该线性规划问题有无穷多最优=7。
解。
1.8
习题二 P76 2.1 写出对偶问题 (a)
min z =2x 1+2x 2+4x 3
⎧x 1+3x 2+4x 3≥2⎪
⎪2x 1+x 2+3x 3+y 4≤3 s . t . ⎨
⎪x 1+4x 2+3x 3=5⎪x , x ≥0, x 无约束
3⎩12
max w =2y 1+3y 2+5y 3
y 1+2y 2+y 3≤2⎧
⎪
对偶问题为：⎪3y 1+y 2+4y 3≤2
s . t . ⎨
⎪4y 1+3y 2+3y 3=4⎪y ≥0, y ≤0, y 无约束
23⎩1
min w =5y 1+3y 2+8y 3
(b)
max z =5x 1+6x 2+3x 3
x 1+2x 2+2x 3=5⎧
⎪
⎪-x 1+5x 2-x 3≥3
s . t . ⎨
⎪4x 1+7x 2+3x 3≤8⎪x 无约束, x ≥0, x ≤0
23⎩1
y 1-y 2+4y 3=5⎧
⎪
⎪2y 1+5y 2+7y 3≥6s . t . ⎨
2y 1-y 2+3y 3≤3⎪
⎪y 无约束, y ≤0, y ≥0
23⎩1
对偶问题为：
2.2
(a)错误。原问题存在可行解，对偶问题可能存在可行解，也可能无可行解。
(b)错误。线性规划的对偶问题无可行解，则原问题可能无可行解，也可能为无界解。 (c)错误。 (d)正确。
2.6 对偶单纯形法 (a)
min z =4x 1+12x 2+18x 3⎧x 1 +3x 3≥3⎪
s . t . ⎨ 2x 2+2x 3≥5
⎪x , x , x ≥0⎩123
解：先将问题改写为求目标函数极大化，并化为标准形式
max z ' =-4x 1-12x 2-18x 3+0x 4+0x 5⎧-x 1 -3x 3+x 4 =-3⎪
s . t . ⎨ -2x 2-2x 3 +x 5=-5
⎪x ≥0(i =1, , 5)⎩i
列单纯形表，用对偶单纯形法求解，步骤如下
3⎫⎛
最优解为x = 0, 1, ⎪
2⎭⎝
T
， 目标值z
=39
。
(b)
min z =5x 1+2x 2+4x 3⎧3x 1+x 2 +2x 3≥4
⎪
s . t . ⎨6x 1+3x 2+5x 3≥10
⎪x , x , x ≥0⎩123
解：先将问题改写为求目标函数极大化，并化为标准形式
max z ' =-5x 1-2x 2-4x 3+0x 4+0x 5⎧-3x 1- x 2 -2x 3+x 4 =-4⎪
s . t . ⎨-6x 1-3x 2-5x 3 +x 5=-10
⎪x ≥0(i =1, , 5)⎩i
列单纯形表，用对偶单纯形法求解
最优解为x =(0, 0, 2)
T
， 目标值z =8。
2.8 将该问题化为标准形式：
max z =2x 1-x 2+x 3+0x 4+0x 5⎧x 1+x 2+x 3+x 4=6
⎪
s . t . ⎨-x 1+2x 2+x 5=4
⎪x ≥0(i =1, 5)
i ⎩
用单纯形表求解
θ=6
由于σj
(a) 令目标函数
max z =（2+λ1）x 1+（-1+λ2）x 2+（1+λ3）x 3
=12
(1)令λ2=λ3=0，将λ1反映到最终单纯形表中
表中解为最优的条件：-3-λ1≤0，- 1 -λ1≤0，-2-λ1≤0，从而λ1≥-1 (2)令λ
1=λ3=0，将λ2反映到最终单纯形表中
表中解为最优的条件：λ2-3 ≤0， 从而λ2≤3 (3) 令λ1=λ2=0，将
λ3反映到最终单纯形表中
表中解为最优的条件：λ3-1≤0， 从而λ3≤1
(b) 令线性规划问题为 max z =2x 1-x 2+x 3
⎧x 1+x 2+x 3≤6+λ4⎪
s . t . ⎨-x 1+2x 2≤4+λ5
⎪x ≥0(i =1, 3) i ⎩
(1)先分析的变化 ⎛1∆b =B ∆b = 1
⎝
*
-1
0⎫⎛λ1⎫⎛λ1⎫⎪ 0⎪⎪= λ⎪⎪ 1⎪⎭⎝⎭⎝1⎭
⎛6+λ1⎫**
使问题最优基不变的条件是b +∆b = 10+λ⎪⎪≥0，从而λ1≥-6
1⎭⎝
6⎛⎫
(2)同理有 10+λ⎪⎪≥0，从而λ2≥-10
2⎭⎝
(c) 由于x *=(6, 0, 0, 0, 10) 代入-x 1+2x 3=-6
x 1=
103
，x 3=
83
，x 5=
223
，最优值为
283
2.12
(a) 线性规划问题
max z =3x 1+x 2+4x 3⎧6x 1+3x 2+5x 3≤45⎪
s . t . ⎨3x 1+4x 2+5x 3≤30
⎪x 1, x 2, x 3≥0⎩
单纯形法求解
=27
最优解为(x 1, x 2, x 3)=(5, 0, 3) ，目标值z
max z =(3+λ)x 1+x 2+4x 3⎧6x 1+3x 2+5x 3≤45
⎪
s . t . ⎨3x 1+4x 2+5x 3≤30
⎪x 1, x 2, x 3≥0⎩
。
(a) 设产品A 的利润为3+λ，线性规划问题变为
单纯形法求解
为保持最优计划不变，应使-2+(b) 线性规划问题变为
max z =3x 1+x 2+4x 3+3x 4⎧6x 1+3x 2+5x 3+8x 4≤45
⎪
s . t . ⎨3x 1+4x 2+5x 3+2x 4≤30
⎪x 1, x 2, x 3, x 4≥0⎩
λ
3
，-
15
-
13
λ
，-
35
+
13
λ
都小于等于0，解得-
35
≤λ≤
95
。
单纯形法求解
此时最优解为(x 1, x 2, x 3)=(0, 0, 5)，目标值z 生产。
(c) 设购买材料数量为y ，则规划问题变为
max z =3x 1+x 2+4x 3-0. 4y ⎧6x 1+3x 2+5x 3≤45⎪
s . t . ⎨3x 1+4x 2+5x 3-y ≤30
⎪x 1, x 2, x 3, y ≥0⎩
=20
，小于原最优值，因此该种产品不值得
单纯形法求解
此时最优解为(x 1, x 2, x 3, y )=(0, 0, 9, 15)，目标值z 材料扩大生产，以购材料15单位为宜。 =30，大于原最优值，因此应该购进原