运筹学课后习题

1、.运筹学课后习题参考答案（部分）第二章 线性规划1、解：模型为： 2.提示：标准问题就是收发平衡问题。3.解：其标准形式为：4.标准形式为：5.提示：建立直角坐标系，用约束方程把可行域描述出来，在通过目标直线找到最优解。6.提示：用凸集的定义。7.提示：（1）用数学归纳法先证明两个凸集的交集是凸集，再证明任意多个凸集的交仍是凸集。(2)例8略9.不能构成可行基，因为此时对应的基本解为。10.11.略12.解：13.提示：14解：首先求出该问题对应的标准形式：写出对应的单纯形表：X1X2X3X4X5RHSZ210000X32510060X41101018X53100144选取x3x4x5为基变量

2、，此时检验数最大的对应x1，做出基入基变换得到下表X1X2X3X4X5RHSZ01/300-2/3-88/3X3013/310-2/332/3X402/301-1/310/3X111/300-/344/3在经过一次出基入基变换得到：X1X2X3X4X5RHSZ000-1/21/2-31X3001-13/23/2-11X20103/2-1/25X11001/21/213所以，原问题的最优解为。15.略。16.（1）解原问题的标准形式为：Min S.t. 对应的单纯型表为： RHS2 1 -1 0 0 0 03 1 1 1 0 0 -1 2 0 1 01 1 -1 0 0 1601020经过一次旋

3、转变换之后得到： RHS0 3 5 0 -2 0 -200 4 -5 1 -3 01 -1 2 0 1 00 -3/2 0 -1/2 1/2301010在经过一次旋转变换得到： RHS0 0 -1/2 0 -1/2 -3/2 -350 0 1 1 -1 -21 0 1/2 0 1/2 1/20 1 -3/2 0 -1/2 1/210155故最优解为，最优值为。（2）原问题已经是标准形式，其对应的单纯形表为：X1X2X3X4RHSZ-3-1-1-10X3-22104X431016由于基变量对应的第零行元素非零，故不是检验数，整理得到X1X2X3X4RHSZ-220010X3-22104X4310

4、16进行一次旋转变换得到： RHS0 0 -1 06-1 1 1/2 04 0 -1 124此时已经是检验数都是非正数，故已得到最优解和最优值。最优解为：，最优值为。（3）解：原问题已经是标准形式，其对应的单纯形表为：X1X2X3X4X5X6X7RHSZ-111-10-1100X500301106X2012-100010X310000-100X400100116由于基变量对应的第零行元素非零，故不是检验数，整理得到X1X2X3X4X5X6X7RHSZ-110-31-110-10X500301106X2012-100010X310000-100X400100116由于检验数x4所对应的列元素均为

5、非正数，故此问题无界。17（1）解：先将问题标准化，得到：故先求辅助问题：其对应的单纯形为X1X2X3X4X5X6X7X8RHSG0000000-10Z-3-4-2000000X51111100030X6361-201000X8010000-114经过计算可得辅助问题的最优单纯形表为：X1X2X3X4X5X6X7X8RHSG0000000-10Z-10-3/2-4/302/300-12X55/203/2011/24-414X2010000-114X4-3/20-1/210-1/2-3312得到了原问题的一个基本可行解，去掉辅助问题，再去掉添加的人工变量，应用单纯形方法得到原问题的最优解和最优值

6、为：。（2）解：先将原问题标准化，得到：应用两阶段法求解，需要先求解以下辅助问题X1X2X3X4X5X6RHSG0000-1-10Z-2400000X52-1-10102X6-110-1013应用单纯形方法，得到辅助问题对应的最优单纯形表为：X1X2X3X4X5X6RHSG0000-1-10Z0026-2-6-22X110-1-1115X201-1-2128得到了原问题的一个基本可行解，去掉辅助问题，再去掉添加的人工变量，应用单纯形方法求解原问题，得到：X1X2X3X4RHSZ0026-22X110-1-15X201-1-28故原问题无解。（3）解：Min S.t. 研究辅助问题：Min S.

7、t. 辅助问题对应的单纯型表为： RHS-4 -1 0 0 0 0 00 0 0 0 -1 -103 1 0 04 3 -1 01 2 0 11 00 10 0363计算辅助问题的最优值： RHS-4 -1 0 0 0 0 07 4 -1 0 0 093 1 0 04 3 -1 01 2 0 11 00 10 0363经过一次旋转变换得到： RHS0 1/3 0 0 1/3 0 40 5/3 -1 0 -7/3 021 1/3 0 00 5/3 -1 00 5/3 0 11/3 0-4/3 1-1/3 0122再次进行旋转变换得到： RHS0 0 1/5 0 3/5 -1/518/50 0 0

8、 0 -1 -101 0 1/5 00 1 1/5 00 0 1 13/5 -1/5-4/15 1/51 -13/52/50去掉辅助问题，得到原问题的一个基本可行解，应用单纯型方法得： RHS0 0 0 -1/5 18/51 0 0 00 1 0 00 0 1 13/52/50得到原问题的最优解为：，最优值为：。（4）解：先将原问题标准化，得到：故所求问题的辅助问题为：其对应的单纯形表为：X1X2X3X4X5X6RHSG0000-1-10Z2-45-6000X514-28102X6-1234011应用单纯形方法求出辅助问题的最优单纯形表为：X1X2X3X4X5X6RHSG0000-1-10Z0

9、-123/30-1/623/2X510-8/301/3-10X601/21/1211/1201/4得到了原问题的一个基本可行解，去掉辅助问题，再去掉添加的人工变量，应用单纯形方法求解原问题，得到原问题的最优解和最优值为：。18.（1）（2）（3）19.证明：给定一个一般形式的线性规划问题：其对应的对偶问题为：则所给规划的目标函数是上面两个规划的和，约束条件是上面两个规划的约束条件的交集。故由对偶理论可知当原始问题和对偶问题只有一个有解存在时所给问题无解。当原始问题和对偶问题都有解时所给问题有解，且此时目标函数值为零。20（1）将原问题化为标准型：其对应的单纯形表为：X1X2X3X4RHSZ-1

10、0-100X312015X101/2103经过计算可得最优单纯形表为：X1X2X3X4RHSZ-5/400-5/47/4X21/2101/25/2X1-1/401-1/47/4故最优解和最优值为：（2）对偶问题为：（3）互补松紧条件为，所以。21.解：该问题的对偶问题为：提示：用互补松紧条件证明。22.解：（1）原问题对应的标准型为：故其所对应的单纯形表为：X1X2X3X4X5RHSZ-2-3-4000X4-1-2-110-3X5-21-301-4应用对偶单纯形方法，得到新的单纯形表：X1X2X3X4X5RHSZ0-4-10-14X40-5/21/21-1/2-1X11-1/23/20-1/2

11、2再应用一次对偶单纯形方法，得到最优单纯形表：X1X2X3X4X5RHSZ00-9/5-8/5-1/528/5X201-1/5-2/51/52/5X1107/5-1/5-2/511/5a所以原问题对应的最优解和最优值为：。（2）解：原问题对应的标准形式为：故其所对应的单纯形表为：X1X2X3X4X5X6RHSZ-3-2-10000X41111006X5-101010-4X60-11001-3应用对偶单纯形方法，得到新的单纯形表：X1X2X3X4X5X6RHSZ0-2-40-3012X40121002X110-10-104X60-11001-3再应用一次对偶单纯形方法，得到最优单纯形表：X1X2

12、X3X4X5X6RHSZ00-60-3-2-18X4003101-1X110-10-104X201-100-13此时，由于第一行的前n个数都是非负数，故原问题无解。（3）原问题对应的标准型为：故其所对应的单纯形表为：X1X2X3X4X5X6RHSZ-2-3-5-6000X4-1-2-3-110-2X5-21-1301-3应用对偶单纯形方法，得到新的单纯形表：X1X2X3X4X5X6RHSZ0-4-4-90-13X40-5/2-5/2-5/21-1/2-1/2X11-1/21/2-3/20-1/23/2再应用一次对偶单纯形方法，得到最优单纯形表：X1X2X3X4X5X6RHSZ000-5-8/5

13、-1/519/5X20111-2/51/51/5X1101-1-1/5-2/58/5所以原问题对应的最优解和最优值为：。23.解：（1）在20题的最优单纯形表中，由于是非基变量，故需要计算出新的检验数向量为：，将其代入20题的最优单纯形表中，得到：X1X2X3X4RHSZ100-5/47/4X21/2101/25/2X1-1/401-1/47/4再应用单纯形方法，得到最优单纯形表如下：X1X2X3X4RHSZ0-20-9/4-13/4X112015X301/211/43故此时的最优解和最优值为：。（2）此时新的检验数向量为：，所以此时的最优解不变，最优值变为：。（3）新的右端向量变为：24.（

14、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为正定矩阵时，二次函数为严格凸函数

15、；充分性：由于二次函数是严格凸函数，则由定理4.2.3可知：5.（1）函数的Hesse矩阵为正定矩阵，故此函数为严格凸函数。（2）函数的Hesse矩阵为负定矩阵，故此函数为严格凹函数。（3）函数的Hesse矩阵为正定矩阵，故此函数为严格凸函数。6.证明：设为任意可行解，对满足条件的，对任意正数，为可行解。因为，且由于为可微凸函数，则又，所以故为可行解。而目标函数为，而，所以，当足够大时，目标函数可以无限小。7.（1）目标函数的Hesse矩阵，由于，所以此矩阵为正定矩阵，又约束方程为凸函数方程，所以此规划为凸规划。存在最优解，最优解为。（2）目标函数为，所以其Hesse矩阵为，由于，所以正定，故

16、目标函数是严格凸函数，又约束方程为凸函数方程，所以此规划为凸规划。8.解：，则，所以当时取得最小值。9.解：01234a0.51.6461.6461.646b3.53.52.79182.3541.6462.3542.08372.3542.79182.354-0.7834-0.9609-0.96092.6497-1.938-0.9609换a换b换a换b换b此时，故此时已达到停止条件，所以。10.解：16 34427624.735685.4592145.074234.164514.8196.168744.01050.886084.757354.000311.12.解：我们有，并且，因为，令，选取新

17、的探索点：，并计算，故已同时满足规则的两个要求，停止迭代，得到非精确解。13.（反证法）证明：假设，不妨取，则：由于，所以，当t足够小时成立，这与为局部最小点矛盾（因为）。14.（1）解：，令，得到：，由于Hesse矩阵为正定矩阵，故整体最优解为。（2）解：，令，得到：，由于Hesse矩阵只有当时为正定矩阵，故该函数具有局部最优解。15.解：由于函数的Hesse矩阵为，由定理4.4.4可知在点处Hesse矩阵，故当时正定。所以的取值范围是。16.（1）解：，第一轮：，用一维搜索得到，第二轮：，用一维搜索得到，第三轮：，用一维搜索得到，。（2）解：，第一轮：，用一维搜索得到，第二轮：，用一维搜索

18、得到，第三轮：，用一维搜索得到，。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）解：

19、当时，和当时，。第五章 动态规划1.解：，；，；，；。所以最短路线为，最短路程为8.2.解：设则：3.解：4.解：。应用公式：得到最优路线为：，最短路程为37。5.解：（方法同1题）应用以上递推公式，可得：解得最短路线为：,最短路程为11.6.解：由题意可知，显然都是凸函数 所以最优决策为，总收益为2680。7.解：函数空间迭代法：首先构造函数：，即：，所以最短路线及路程为：函数空间迭代法：略。第六章 图与网络分析1.证明：充分性：由于G是简单图，则G没有重边和环，又完全图任意两个顶点之间都有边连接，故边数为。必要性：图的边数为,由于图G是简单图，故G没有重边和环，所以图G是完全图。2.证明：

20、（反证法）假设图中次为奇数的顶点为奇数个，则在该图中必有某一条边只有一个顶点，这和边的定义不符，故次为奇数的顶点个数不能为奇数个。3.证明：设任意点集是完全图G的一个非空点集，由于图G是完全图，则在图G中任意两点之间都有边连接。由点导出子图定义可知在中任意两点之间都有边连接，故该子图一定是完全图。4.证明：（反证法）假设图中不存在回路，那么在图中必定存在5.提示：6.证明：设次为1的顶点为s个，则此树各顶点次的和，其中N为顶点个数，如果，则，这与树的性质矛盾，故，也就是次为1的顶点至少有k个。7.最小树如下：134528.提示：9. 2 4 3 1 3 2 2 4 1 6 3 5 2 4 51

21、0. 2 4 3 1 3 2 2 4 1 6 3 5 2 4 511.最小费用流为。第七章 网络计划技术1.02648102.参见教科书P349.3.1234567891011最早时间024246737512最晚时间0345497610812关键线路为：4.123456789最早时间0248812131520最晚时间0558813181520关键线路为：第八章 排队论1.解：密度函数为：，所以：，。2.解：，3.提示：用条件概率分布公式。4.解：即，所以有（人/小时）。5.解：，。6.解：7.解： 8.解:系统的空闲概率、等待概率、等待队长、队长、等待时间、逗留时间都不小于系统。9.解：方案一的费用为万，方案二的费用为万，所以用方案二好。10.略。第九章 决策分析1.解：最大可能法：选择一般加固。期望值法：， ，所以选择一般加固。 效用函数法：，故选择常规加固。2. 0.25 2000 3000 0.73 2000 0.02 52000 0.25 4000 4000 0.73 4000 0.02 4000 0.25 1500 2700 0.73 1500 0.02 61500 0.25 10000 3700 0.73 0 0.02 60000所以