《运筹学课后习题》由会员分享，可在线阅读，更多相关《运筹学课后习题（32页珍藏版）》请在金锄头文库上搜索。
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-22104X43101
4、6进行一次旋转变换得到： 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.t
7、. 辅助问题对应的单纯型表为： 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-123/30-1/623/2X510-8/301/3-10X601/21/1211/1201/4得到了原问题的一个基本可行解，去掉辅助问题，再去掉添加的人工变量，应用单纯形方法求解原问题，得到原问题的最优解和最优值为：。18.（1）（2）（3）19.证明：给定一个一般形式的线性规划问题：其对应的对偶问题为：则所给规划的目标函数是上面两个规划的和，约束条件是上面两个规划的约束条件的交集。故由对偶理论可知当原始问题和对偶问题只有一个有解存在时所给问题无解。当原始问题和对偶问题都有解时所给问题有解，且此时目标函数值为零。
