《运筹学》期中考试卷答案.doc

温州大学试卷纸学院- 班级- 姓名- 学号- 温州大学期中考试试卷 2015-2016 学年第 一 学期考试科目运筹学B试卷类型考试形式开卷（仅允许带教材）考试对象题号一二三总分得分/60/20/20得分一、简答题（每小题10分，共60分）1、某企业在今后三年内有4种投资机会。第种：三年内每年年初投资，年底可获利润20%，并将本金收回；第种：第一年年初投资，第二年年底可获利润50%，并将本金收回，但该项目投资不得超过2.0万元；第种：第二年年初投资，第三年年底收回本金，并获利润60%，但该项目投资不得超过1.5万元；第种：第三年年初投资，于该年年底收回本金，且获利40%，但该项目投资不得超过1.0万元。现在该企业准备拿出3.0万元资金，问如何制定投资计划，使到第三年年末本利和最大。为此，设xij为第i年投资到第j个方案的资金，共6个决策变量。分析投资情况见下表。年份第一年初第一年底（第二年初）第二年底（第三年初）第三年底投资额x11出1.2x11入x21出1.2x21入x31出1.2x31入x12出1.5x12入x23出1.6x23入x34出1.4x34入试根据上述决策变量和投资分析表写出该问题的线性规划模型。解：2、画出下列线性规划问题的图解法可行域。解：3、将下面的线性规划问题写成标准化形式。解：4、写出下列线性规划问题的对偶问题。解：5、简述单纯形法和对偶单纯形的异同点，填入下表。答：相同点： 都含一个单位子矩阵，都要进行换基迭代，都用于求解线性规划问题的原问题。 不同点：单纯形法对偶单纯形法初始状态常数列非负检验数非正算法结束判断准则检验数全非正，结束计算常数列全非负，结束计算换基方法检验数正者，入基，按照与常数列的最小比例选择出基变量常数列负者，出基，按照与检验数的最小比例选择入基变量6、下面命题是否正确？解释理由。（1）线性规划问题的可行解如为最优解，则该可行解一定为基可行解。（2）单纯形法迭代计算中，必须选取同最大正检验数j对应的变量作为入基变量。（3）线性规划问题增加一个约束条件，可行域的范围一般将缩小；减少一个约束条件，可行域的范围一般将扩大。（4）如果线性规划问题的对偶问题无可行解，则原问题也一定无可行解。（5）如果X1，X2都是某个线性规划问题的最优解，则X=1X1+2X1（1，2是正实数）也是这个问题的最优解。答：（1）不正确。在存在多个最优基解的情况下，它们的凸组合不是基解，但仍为最优解。（2）不正确。只需选取正检验数j对应的变量入基，都可以使目标值增大。（3）正确。增加约束的可行域是原可行域的子集。（4）不正确。此时原问题还可能有无界解。（5）不正确。X1，X2的凸组合才是最优解。得分二、计算题（共20分）使用单纯形法求解下列线性规划问题，写出求解步骤，并给出：（1）最优解，（2）最优值。解：参考步骤：cB基bx1x2x3x4x50x44211100x5612001sj-121000x413/2011-1/22x231/21001/2sj-2010-11x313/2011-1/22x231/21001/2sj-7/200-1-1/2得最优解x*=(0,3,1)，最优值z*=7。得分三、计算题（共20分）使用对偶单纯形法求解下列线性规划问题，写出求解步骤，并给出：（1）最优解，（2）最优值。解：先引入2个人工变量，构造单位子矩阵：初始单纯形表：cB基bx1x2x3x4x50x4-4-3-2-1100x5-12-41 -4 01-6-3-400因为(-4)/(-4)=min(-6)/(-4), (-4)/(-4)，x3进基，x5出基：cB基bx1x2x3x4x50x4-1 -2 -9/401-1/4-4x331-1/410-1/4-2-400-1因为(-2)/(-2)=min(-2)/(-2), (-4)/(-9/4), (-1)/(-1/4)，x1进基，x4出基：cB基bx1x2x3x4x5-6x11/219/80-1/21/8-