资源描述
运筹学基础及应用 习题解答
习题一 P46
1.1
(a)
0
1
2
3
4
1
3
2
该问题有无穷多最优解，即满足的所有，此时目标函数值。
(b)
0
1
4
2
3
用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解。
1.2
(a) 约束方程组的系数矩阵
基
基解
是否基可行解
目标函数值
否
是
10
是
3
否
否
是
3
否
是
0
否
最优解。
(b) 约束方程组的系数矩阵
基
基解
是否基可行解
目标函数值
否
是
否
是
5
否
是
5
最优解。
1.3
(a)
(1) 图解法
0
1
2
3
4
1
3
2
最优解即为的解，最大值
(2)单纯形法
首先在各约束条件上添加松弛变量，将问题转化为标准形式
则组成一个基。令
得基可行解，由此列出初始单纯形表
基
。
基
，
新的单纯形表为
基
，表明已找到问题最优解。最大值
(b)
(1) 图解法
0
3
6
9
12
3
9
6
最优解即为的解，最大值
(2) 单纯形法
首先在各约束条件上添加松弛变量，将问题转化为标准形式
则，，组成一个基。令
得基可行解，由此列出初始单纯形表
2 1 0 0 0
基
0 15
0 24
0 5
0 5 1 0 0
[6] 2 0 1 0
1 1 0 0 1
2 1 0 0 0
。
2 1 0 0 0
基
0 15
2 4
0 1
0 5 1 0 0
1 0 0
0 0 1
0 0 0
，
新的单纯形表为
2 1 0 0 0
基
0
2
0
0 0 1
1 0 0
0 1 0
0 0 0
，表明已找到问题最优解，，，，。最大值
1.6
(a) 在约束条件中添加松弛变量或剩余变量，且令，
该问题转化为
其约束系数矩阵为
在中人为地添加两列单位向量
令
得初始单纯形表
基
(b) 在约束条件中添加松弛变量或剩余变量，且令，
该问题转化为
其约束系数矩阵为
在中人为地添加两列单位向量
令
得初始单纯形表
基
1.7
(a)解1：大M法
在上述线性规划问题中分别减去剩余变量再加上人工变量得
其中M是一个任意大的正数。据此可列出单纯形表
由单纯形表计算结果可以看出，且，所以该线性规划问题有无界解
解2：两阶段法。
现在上述线性规划问题的约束条件中分别减去剩余变量再加上人工变量得第一阶段的数学模型
据此可列出单纯形表
第一阶段求得的最优解,目标函数的最优值。
因人工变量，所以是原线性规划问题的基可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。
由表中计算结果可以看出，且，所以原线性规划问题有无界解。
(b)解1：大M法
在上述线性规划问题中分别减去剩余变量再加上人工变量得
其中M是一个任意大的正数。据此可列出单纯形表
由单纯形表计算结果可以看出，最优解，目标函数的最优解值X存在非基变量检验数，故该线性规划问题有无穷多最优解。
解2：两阶段法。
现在上述线性规划问题的约束条件中分别减去剩余变量再加上人工变量得第一阶段的数学模型
据此可列出单纯形表
第一阶段求得的最优解,目标函数的最优值。
因人工变量，所以是原线性规划问题的基可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，并填入原问题的目标函数的系数，进行第二阶段的运算，见下表。
由单纯形表计算结果可以看出，最优解，目标函数的最优解值由于存在非基变量检验数，故该线性规划问题有无穷多最优解。
1.8
表1-23
表1-24
1.10
最后一个表为所求。
习题二 P76
2.1 写出对偶问题
(a)
对偶问题为：
(b)
对偶问题为：
2.2
(a)错误。原问题存在可行解，对偶问题可能存在可行解，也可能无可行解。
(b)错误。线性规划的对偶问题无可行解，则原问题可能无可行解，也可能为无界解。
(c)错误。
(d)正确。
2.6 对偶单纯形法
(a)
解：先将问题改写为求目标函数极大化，并化为标准形式
列单纯形表，用对偶单纯形法求解，步骤如下
基
最优解为， 目标值。
(b)
解：先将问题改写为求目标函数极大化，并化为标准形式
列单纯形表，用对偶单纯形法求解
基
最优解为， 目标值。
2.8 将该问题化为标准形式：
用单纯形表求解
基
基
由于，所以已找到最优解，目标函数值
(a) 令目标函数
(1)令，将反映到最终单纯形表中
基
表中解为最优的条件：，，，从而
(2)令，将反映到最终单纯形表中
基
表中解为最优的条件：， 从而
(3) 令，将反映到最终单纯形表中
基
表中解为最优的条件：， 从而
(b) 令线性规划问题为
(1)先分析的变化
使问题最优基不变的条件是，从而
(2)同理有，从而
(c) 由于代入，所以将约束条件减去剩余变量后的方程直接反映到最终单纯形表中
2 -1 1 0 0 0
基
2 6
0 10
1 1 1 1 0 0
0 3 1 1 1 0
0 -2
1 0 -2 0 0 1
0 -3 -1 -2 0 0
对表中系数矩阵进行初等变换，得
2 -1 1 0 0 0
基
2 6
0 10
1 1 0 0
0 3 1 1 1 0
0 -8
0 -1 [-3] -1 0 1
0 -3 -1 -2 0 0
2 -1 1 0 0 0
基
2
0
1 0 0
0 0 1
0
0 1 0
0 0 0
因此增加约束条件后，新的最优解为
，，，最优值为
2.12
(a) 线性规划问题
单纯形法求解
基
最优解为 ，目标值。
(a) 设产品A的利润为，线性规划问题变为
单纯形法求解
基
为保持最优计划不变，应使，，都小于等于0，解得。
(b) 线性规划问题变为
单纯形法求解
基
此时最优解为，目标值，小于原最优值，因此该种产品不值得生产。
(c) 设购买材料数量为，则规划问题变为
单纯形法求解
基
此时最优解为，目标值，大于原最优值，因此应该购进原材料扩大生产，以购材料15单位为宜。
第三章
3.1 表3.36
产地
销地
B1 B2 B3 B4
产量
A1
A2
A3
A4
9 8 12 13
10 10 12 14
8 9 11 12
10 10 11 12
18
24
6
12
销量
6 14 35 5
用vogel法求解得
B
A
B1 B2 B3 B4
A1
A2
A3
A4
14 4
24
6 0
11
用位势法检验，把上表中有数字的地方换成运价
B
A
B1 B2 B3 B4
Ui
A1
A2
A3
A4
8 13
12
8 11
11 12
8
8
7
7
Vj
1 0 4 5
令v1=1
则u1+v2=8 所以u3=7
u1+v4=13 v3=4
u2+v3=12 u4=7
u3+v1=8 v5=8
u3+v3=11 u2=8
u4+v3=11 v2=0
u4+v4=12
得检验数表
B
A
B1 B2 B3 B4
A1
A2
A3
A4
0 0
1 2 1
2 0
2 3
表中所有的数字均大于等于零，故所求方案为最优方案
3.3
解：（a）用运价代替表3.39中有数字的地方，求出位势和检验数
B
A
B1 B2 B3 B4
Ui
A1
A2
A3
1 11
12 k 9
2
12-k
11
1
Vj
1 k-11 -2 k-1
令v1=1则u1+v2=1 故v3=-2
u1+v4=11 u2=11
u2+v1=12 v2=k-11
u2+v2=k u1=12-k
u2+v3=9 v4=k-1
u3+v1=2 u3=1
得检验数表
B
A
B1 B2 B3 B4
A1
A2
A3
k-3 10-k
30-k
24-k 15 18-k
令表中所有的检验数均大于等于零，得3≤k≤10
(b)由表3.39和表3.40计算出位势和检验数，令C24=M
位势表
B
A
B1 B2 B3 B4
Ui
A1
A2
A3
1 11
12 7 9
2
5
11
1
Vj
1 -4 -2 6
检验数表
B
A
B1 B2 B3 B4
A1
A2
A3
4 17
M-17
17 17 11
当存在某非基变量的检验数大于等于零的时候有无穷多最优解
则M-17=0 所以M=17 故运价C24=17
3.5
销地
产地
A1 A2 A3
供应量
B1
B1’
B2
B2’
B3
B3’
S
500 540 580
570 610 650
M 600 640
M 670 710
M M 550
M M 620
40 80 120
2
3
4
2
1
3
2
销量
3 3 4
由于产大于销，设有一个理想的销地A4，则
销地
产地
A1 A2 A3 A4
供应量
B1
B1’
B2
B2’
B3
B3’
S
500 540 580 0
570 610 650 0
M 600 640 0
M 670 710 0
M M 550 0
M M 620 0
40 80 120 0
2
3
4
2
1
3
2
销量
3 3 4 7
第四章
略
第五章
5.4 解：
Min z=P1 d1- +P2(d2-+d2+)
s.t. 11x1+3x2≥25
100 x1+50x2 + d1- - d1+ =1900
10x1+16x2 + d2- - d2+ =200
x1,x2, d1- ,d1+ , d2- ,d2+ ≥0
5.6 解：
目标规划模型为
Min z = P1 d1- +P2(d2-+d2+) +P2(d3-+d3+) +P3(d4-+d4+) +P3d5+
s.t. 300 x1+450x2 + d1- - d1+ =10000
x1+ d2- - d2+ =10
x2 + d3- - d3+ =15
4x1+6x2 + d4- - d4+ =150
3x1+2x2 + d5- - d5+ =75
x1,x2, d1- ,di+ , di- ≥0 ,i=1，…，5
快乐
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
