《运筹学课后习题》word版.docx
《《运筹学课后习题》word版.docx》由会员分享，可在线阅读，更多相关《《运筹学课后习题》word版.docx（27页珍藏版）》请在冰点文库上搜索。
《运筹学课后习题》word版
运筹学课后习题参考答案（部分）
第二章线性规划
1、解：
模型为：
2.提示：
标准问题就是收发平衡问题。
3.解：
其标准形式为：
4.标准形式为：
5.提示：
建立直角坐标系，用约束方程把可行域描述出来，在通过目标直线找到最优解。
6.提示：
用凸集的定义。
7.提示：
（1）用数学归纳法先证明两个凸集的交集是凸集，再证明任意多个凸集的交仍是凸集。
（2）例
8．略
9.不能构成可行基，因为此时对应的基本解为。
10.11.略
12.解：
13.提示：
14解：
首先求出该问题对应的标准形式：
写出对应的单纯形表：
X1
X2
X3
X4
X5
RHS
Z
2
1
0
0
0
0
X3
2
5
1
0
0
60
X4
1
1
0
1
0
18
X5
3
1
0
0
1
44
选取x3x4x5为基变量，此时检验数最大的对应x1，做出基入基变换得到下表
X1
X2
X3
X4
X5
RHS
Z
0
1/3
0
0
-2/3
-88/3
X3
0
13/3
1
0
-2/3
32/3
X4
0
2/3
0
1
-1/3
10/3
X1
1
1/3
0
0
-/3
44/3
在经过一次出基入基变换得到：
X1
X2
X3
X4
X5
RHS
Z
0
0
0
-1/2
1/2
-31
X3
0
0
1
-13/2
3/2
-11
X2
0
1
0
3/2
-1/2
5
X1
1
0
0
1/2
1/2
13
所以，原问题的最优解为。
15.略。
16.
（1）解原问题的标准形式为：
Min
S.t.
对应的单纯型表为：
RHS
21-1000
0
311100
-12010
11-1001
60
10
20
经过一次旋转变换之后得到：
RHS
0350-20
-20
04-51-30
1-12010
0-3/20-1/21/2
30
10
10
在经过一次旋转变换得到：
RHS
00-1/20-1/2-3/2
-35
0011-1-2
101/201/21/2
01-3/20-1/21/2
10
15
5
故最优解为，最优值为。
（2）原问题已经是标准形式，其对应的单纯形表为：
X1
X2
X3
X4
RHS
Z
-3
-1
-1
-1
0
X3
-2
2
1
0
4
X4
3
1
0
1
6
由于基变量对应的第零行元素非零，故不是检验数，整理得到
X1
X2
X3
X4
RHS
Z
-2
2
0
0
10
X3
-2
2
1
0
4
X4
3
1
0
1
6
进行一次旋转变换得到：
RHS
00-10
6
-111/20
40-11
2
4
此时已经是检验数都是非正数，故已得到最优解和最优值。
最优解为：
，最优值为。
（3）解：
原问题已经是标准形式，其对应的单纯形表为：
X1
X2
X3
X4
X5
X6
X7
RHS
Z
-11
1
-1
0
-1
1
0
0
X5
0
0
3
0
1
1
0
6
X2
0
1
2
-1
0
0
0
10
X3
1
0
0
0
0
-1
0
0
X4
0
0
1
0
0
1
1
6
由于基变量对应的第零行元素非零，故不是检验数，整理得到
X1
X2
X3
X4
X5
X6
X7
RHS
Z
-11
0
-3
1
-1
1
0
-10
X5
0
0
3
0
1
1
0
6
X2
0
1
2
-1
0
0
0
10
X3
1
0
0
0
0
-1
0
0
X4
0
0
1
0
0
1
1
6
由于检验数x4所对应的列元素均为非正数，故此问题无界。
17．
（1）解：
先将问题标准化，得到：
故先求辅助问题：
其对应的单纯形为
X1
X2
X3
X4
X5
X6
X7
X8
RHS
G
0
0
0
0
0
0
0
-1
0
Z
-3
-4
-2
0
0
0
0
0
0
X5
1
1
1
1
1
0
0
0
30
X6
3
6
1
-2
0
1
0
0
0
X8
0
1
0
0
0
0
-1
1
4
经过计算可得辅助问题的最优单纯形表为：
X1
X2
X3
X4
X5
X6
X7
X8
RHS
G
0
0
0
0
0
0
0
-1
0
Z
-1
0
-3/2
-4/3
0
2/3
0
0
-12
X5
5/2
0
3/2
0
1
1/2
4
-4
14
X2
0
1
0
0
0
0
-1
1
4
X4
-3/2
0
-1/2
1
0
-1/2
-3
3
12
得到了原问题的一个基本可行解，去掉辅助问题，再去掉添加的人工变量，应用单纯形方法得到原问题的最优解和最优值为：
。
（2）解：
先将原问题标准化，得到：
应用两阶段法求解，需要先求解以下辅助问题
X1
X2
X3
X4
X5
X6
RHS
G
0
0
0
0
-1
-1
0
Z
-2
4
0
0
0
0
0
X5
2
-1
-1
0
1
0
2
X6
-1
1
0
-1
0
1
3
应用单纯形方法，得到辅助问题对应的最优单纯形表为：
X1
X2
X3
X4
X5
X6
RHS
G
0
0
0
0
-1
-1
0
Z
0
0
2
6
-2
-6
-22
X1
1
0
-1
-1
1
1
5
X2
0
1
-1
-2
1
2
8
得到了原问题的一个基本可行解，去掉辅助问题，再去掉添加的人工变量，应用单纯形方法求解原问题，得到：
X1
X2
X3
X4
RHS
Z
0
0
2
6
-22
X1
1
0
-1
-1
5
X2
0
1
-1
-2
8
故原问题无解。
（3）解：
Min
S.t.
研究辅助问题：
Min
S.t.
辅助问题对应的单纯型表为：
RHS
-4-100
00
0
0000
-1-1
0
3100
43-10
1201
10
01
00
3
6
3
计算辅助问题的最优值：
RHS
-4-100
00
0
74-10
00
9
3100
43-10
1201
10
01
00
3
6
3
经过一次旋转变换得到：
RHS
01/300
1/30
4
05/3-10
-7/30
2
11/300
05/3-10
05/301
1/30
-4/31
-1/30
1
2
2
再次进行旋转变换得到：
RHS
001/50
3/5-1/5
18/5
0000
-1-1
0
101/50
011/50
0011
3/5-1/5
-4/151/5
1-1
3/5
2/5
0
去掉辅助问题，得到原问题的一个基本可行解，应用单纯型方法得：
RHS
000-1/5
18/5
1000
0100
0011
3/5
2/5
0
得到原问题的最优解为：
，最优值为：
。
（4）解：
先将原问题标准化，得到：
故所求问题的辅助问题为：
其对应的单纯形表为：
X1
X2
X3
X4
X5
X6
RHS
G
0
0
0
0
-1
-1
0
Z
2
-4
5
-6
0
0
0
X5
1
4
-2
8
1
0
2
X6
-1
2
3
4
0
1
1
应用单纯形方法求出辅助问题的最优单纯形表为：
X1
X2
X3
X4
X5
X6
RHS
G
0
0
0
0
-1
-1
0
Z
0
-1
23/3
0
-1/6
2
3/2
X5
1
0
-8/3
0
1/3
-1
0
X6
0
1/2
1/12
1
1/12
0
1/4
得到了原问题的一个基本可行解，去掉辅助问题，再去掉添加的人工变量，应用单纯形方法求解原问题，得到原问题的最优解和最优值为：
。
18.
（1）
（2）
（3）
19.证明：
给定一个一般形式的线性规划问题：
其对应的对偶问题为：
则所给规划的目标函数是上面两个规划的和，约束条件是上面两个规划的约束条件的交集。
故由对偶理论可知当原始问题和对偶问题只有一个有解存在时所给问题无解。
当原始问题和对偶问题都有解时所给问题有解，且此时目标函数值为零。
20
（1）将原问题化为标准型：
其对应的单纯形表为：
X1
X2
X3
X4
RHS
Z
-1
0
-1
0
0
X3
1
2
0
1
5
X1
0
1/2
1
0
3
经过计算可得最优单纯形表为：
X1
X2
X3
X4
RHS
Z
-5/4
0
0
-5/4
7/4
X2
1/2
1
0
1/2
5/2
X1
-1/4
0
1
-1/4
7/4
故最优解和最优值为：
（2）对偶问题为：
（3）互补松紧条件为，所以。
21.解：
该问题的对偶问题为：
提示：
用互补松紧条件证明。
22.解：
（1）原问题对应的标准型为：
故其所对应的单纯形表为：
X1
X2
X3
X4
X5
RHS
Z
-2
-3
-4
0
0
0
X4
-1
-2
-1
1
0
-3
X5
-2
1
-3
0
1
-4
应用对偶单纯形方法，得到新的单纯形表：
X1
X2
X3
X4
X5
RHS
Z
0
-4
-1
0
-1
4
X4
0
-5/2
1/2
1
-1/2
-1
X1
1
-1/2
3/2
0
-1/2
2
再应用一次对偶单纯形方法，得到最优单纯形表：
X1
X2
X3
X4
X5
RHS
Z
0
0
-9/5
-8/5
-1/5
28/5
X2
0
1
-1/5
-2/5
1/5
2/5
X1
1
0
7/5
-1/5
-2/5
11/5a
所以原问题对应的最优解和最优值为：
。
（2）解：
原问题对应的标准形式为：
故其所对应的单纯形表为：
X1
X2
X3
X4
X5
X6
RHS
Z
-3
-2
-1
0
0
0
0
X4
1
1
1
1
0
0
6
X5
-1
0
1
0
1
0
-4
X6
0
-1
1
0
0
1
-3
应用对偶单纯形方法，得到新的单纯形表：
X1
X2
X3
X4
X5
X6
RHS
Z
0
-2
-4
0
-3
0
12
X4
0
1
2
1
0
0
2
X1
1
0
-1
0
-1
0
4
X6
0
-1
1
0
0
1
-3
再应用一次对偶单纯形方法，得到最优单纯形表：
X1
X2
X3
X4
X5
X6
RHS
Z
0
0
-6
0
-3
-2
-18
X4
0
0
3
1
0
1
-1
X1
1
0
-1
0
-1
0
4
X2
0
1
-1
0
0
-1
3
此时，由于第一行的前n个数都是非负数，故原问题无解。
（3）原问题对应的标准型为：
故其所对应的单纯形表为：
X1
X2
X3
X4
X5
X6
RHS
Z
-2
-3
-5
-6
0
0
0
X4
-1
-2
-3
-1
1
0
-2
X5
-2
1
-1
3
0
1
-3
应用对偶单纯形方法，得到新的单纯形表：
X1
X2
X3
X4
X5
X6
RHS
Z
0
-4
-4
-9
0
-1
3
X4
0
-5/2
-5/2
-5/2
1
-1/2
-1/2
X1
1
-1/2
1/2
-3/2
0
-1/2
3/2
再应用一次对偶单纯形方法，得到最优单纯形表：
X1
X2
X3
X4
X5
X6
RHS
Z
0
0
0
-5
-8/5
-1/5
19/5
X2
0
1
1
1
-2/5
1/5
1/5
X1
1
0
1
-1
-1/5
-2/5
8/5
所以原问题对应的最优解和最优值为：
。
23.解：
（1）在20题的最优单纯形表中，由于是非基变量，故需要计算出新的检验数向量为：
，将其代入20题的最优单纯形表中，得到：
X1
X2
X3
X4
RHS
Z
1
0
0
-5/4
7/4
X2
1/2
1
0
1/2
5/2
X1
-1/4
0
1
-1/4
7/4
再应用单纯形方法，得到最优单纯形表如下：
X1
X2
X3
X4
RHS
Z
0
-2
0
-9/4
-13/4
X1
1
2
0
1
5
X3
0
1/2
1
1/4
3
故此时的最优解和最优值为：
。
（2）此时新的检验数向量为：
，所以此时的最优解不变，最优值变为：
。
（3）新的右端向量变为：
24.
（1）最优解和最优值为：
（2）
25.略。
第三章整数线性规划
1.设A、B产品的生产量非别为件，该问题的数学模型为：
2.设0-1变量表示
其数学模型为：
3.可行解集合为
，最优解，最优值为。
割平面法：
先求出松弛问题的最优单纯形表如下表：
4.
5.证明：
由3.2.9式得到：
，又由于，两式相减得到：
由于，所以令结论成立。
第四章非线性规划
1.
2.设产品A生产（百箱），产品B生产（百箱），则模型为：
最优解为。
3.
（1）整体最优解为，最优值为；
（2）整体最优解为，最优值为；
（3）整体最优解为，最优值为；
4.提示：
必要性：
二次函数的Hesse矩阵为A，故由定理4.2.4可知，当A为正定矩阵时，二次函数为严格凸函数；
充分性：
由于二次函数是严格凸函数，则由定理4.2.3可知：
5.
（1）函数的Hesse矩阵为正定矩阵，故此函数为严格凸函数。
（2）函数的Hesse矩阵为负定矩阵，故此函数为严格凹函数。
（3）函数的Hesse矩阵为正定矩阵，故此函数为严格凸函数。
6.证明：
设为任意可行解，对满足条件的，对任意正数，为可行解。
因为，且由于为可微凸函数，则
又，所以
故为可行解。
而目标函数为，而，所以，当足够大时，目标函数可以无限小。
7.
（1）目标函数的Hesse矩阵，由于，所以此矩阵为正定矩阵，又约束方程为凸函数方程，所以此规划为凸规划。
存在最优解，最优解为。
（2）目标函数为，所以其Hesse矩阵为，由于，所以正定，故目标函数是严格凸函数，又约束方程为凸函数方程，所以此规划为凸规划。
8.解：
，则，所以当时取得最小值。
9.解：
0
1
2
3
4
a
0.5
1.646
1.646
1.646
b
3.5
3.5
2.7918
2.354
1.646
2.354
2.0837
2.354
2.7918
2.354
-0.7834
-0.9609
-0.9609
2.6497
-1.938
-0.9609
换a
换b
换a
换b
换b
此时，故此时已达到停止条件，所以。
10.解：
1
6
344
276
2
4.7356
85.4592
145.0742
3
4.1645
14.81
96.1687
4
4.0105
0.8860
84.7573
5
4.0003
11.
12.解：
我们有，并且，因为，
，令，选取新的探索点：
，并计算，，
，故已同时满足规则的两个要求，停止迭代，得到非精确解。
13.（反证法）证明：
假设，不妨取，则：
由于，所以，当t足够小时成立，这与为局部最小点矛盾（因为）。
14.
（1）解：
，令，得到：
，由于Hesse矩阵为正定矩阵，故整体最优解为。
（2）解：
，令，得到：
，由于Hesse矩阵只有当时为正定矩阵，故该函数具有局部最优解。
15.解：
由于函数的Hesse矩阵为，由定理4.4.4可知在点处Hesse矩阵，故当时正定。
所以的取值范围是。
16.
（1）解：
，
第一轮：
，用一维搜索得到，
第二轮：
，用一维搜索得到，
第三轮：
，用一维搜索得到，
。
（2）解：
，
第一轮：
，用一维搜索得到，
第二轮：
，用一维搜索得到，
第三轮：
，用一维搜索得到，
。
17.提示：
因为，所以，对任意点y0应用最速下降法第一轮都要取下降方向，用解析法计算出此时，故为最优点。
18.
19.提示：
沿着与
共轭的方向前进。
20.
21.解：
K-T条件为：
22.解：
K-T条件为：
经过讨论可知最优解为最优值为。
23.
（1）解：
该问题的lagrange函数是：
故K-T条件为：
作为K-T点，除了满足上述条件，还要满足。
经过讨论可知K-T点为，故该问题的最优解为：
（2）该问题的lagrange函数是：
故K-T条件为：
作为K-T点，除了满足上述条件，还要满足。
经过讨论可知K-T点为；；。
24.
（1）解：
和当时，。
（2）解：
当时，和当时，。
（3）解：
当时，，和当时，。
第五章动态规划
1.解：
，，；
，
；
，
，
；
。
所以最短路线为，最短路程为8.
2.解：
设则：
3.解：
4.解：
。
应用公式：
得到最优路线为：
，最短路程为37。
5.解：
（方法同1题）
应用以上递推公式，可得：
解得最短路线为：
最短路程为11.
6.解：
由题意可知，，显然都是凸函数
所以最优决策为，总收益为2680。
7.解：
函数空间迭代法：
首先构造函数：
，
即：
，所以最短路线及路程为：
函数空间迭代法：
略。
第六章图与网络分析
1.证明：
充分性：
由于G是简单图，则G没有重边和环，又完全图任意两个顶点之间都有边连接，故边数为。
必要性：
图的边数为,由于图G是简单图，故G没有重边和环，所以图G是完全图。
2.证明：
（反证法）假设图中次为奇数的顶点为奇数个，则在该图中必有某一条边只有一个顶点，这和边的定义不符，故次为奇数的顶点个数不能为奇数个。
3.证明：
设任意点集是完全图G的一个非空点集，由于图G是完全图，则在图G中任意两点之间都有边连接。
由点导出子图定义可知在中任意两点之间都有边连接，故该子图一定是完全图。
4.证明：
（反证法）假设图中不存在回路，那么在图中必定存在
5.提示：
6.证明：
设次为1的顶点为s个，
则此树各顶点次的和，其中N为顶点个数，
如果，则，这与树的性质矛盾，故，也就是次为1的顶点至少有k个。
7.最小树如下：
8.提示：
9.
243
13
224
16
352
45
10.
243
13
224
16
352
45
11.最小费用流为。
第七章网络计划技术
1.
2.参见教科书P349.
3.
1
2
3
4
5
6
7
8
9
10
11
最早时间
0
2
4
2
4
6
7
3
7
5
12
最晚时间
0
3
4
5
4
9
7
6
10
8
12
关键线路为：
4.
1
2
3
4
5
6
7
8
9
最早时间
0
2
4
8
8
12
13
15
20
最晚时间
0
5
5
8
8
13
18
15
20
关键线路为：
第八章排队论
1.解：
密度函数为：
，
所以：
，。
2.解：
，
3.提示：
用条件概率分布公式。
4.解：
即，所以有（人/小时）。
5.解：
，
，，。
6.解：
7.解：
8.解:
系统的空闲概率、等待概率、等待队长、队长、等待时间、逗留时间都不小于系统。
9.解：
方案一的费用为万，方案二的费用为万，所以用方案二好。
10.略。
第九章决策分析
1.解：
最大可能法：
选择一般加固。
期望值法：
，
，所以选择一般加固。
效用函数法：
，故选择常规加固。
2.
0.252000
30000.732000
0.0252000
0.25
4000
4000
0.734000
0
升级会员 