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

温州大学试卷纸试卷第1页共5页温州大学期中考试试卷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入试根据上述决策变量和投资分析表写出该问题的线性规划模型。解：23313411213112233411121221231111122123112331341221341112212331max1.61.21.4(or0.20.20.20.50.60.4)321.2(or31.2)s.t.1.51.51.210,0,0,0,0,zxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx340得分学院--------------------------------------班级----------------------------------姓名-------------------------------------学号-------------------------------------温州大学试卷纸试卷第2页共5页2、画出下列线性规划问题的图解法可行域。1212121212max5242010s.t.20,0zxxxxxxxxxx解：x1x2505464623、将下面的线性规划问题写成标准化形式。12312312313123max22512276s.t.640,0,0zxxxxxxxxxxxxxx解：123123112313212312max'22'512'276s.t.'64'0,0,0,0,0zxxxxxxyxxxxxyxxxyy4、写出下列线性规划问题的对偶问题。12312312313123max22512276s.t.640,0,0zxxxxxxxxxxxxxx解：温州大学试卷纸试卷第3页共5页12312312123123min12642121s.t.57620,,0wyyyyyyyyyyyyyy任意5、简述单纯形法和对偶单纯形的异同点，填入下表。答：相同点：都含一个单位子矩阵，都要进行换基迭代，都用于求解线性规划问题的原问题。不同点：单纯形法对偶单纯形法初始状态常数列非负检验数非正算法结束判断准则检验数全非正，结束计算常数列全非负，结束计算换基方法检验数正者，入基，按照与常数列的最小比例选择出基变量常数列负者，出基，按照与检验数的最小比例选择入基变量6、下面命题是否正确？解释理由。（1）线性规划问题的可行解如为最优解，则该可行解一定为基可行解。（2）单纯形法迭代计算中，必须选取同最大正检验数σj对应的变量作为入基变量。（3）线性规划问题增加一个约束条件，可行域的范围一般将缩小；减少一个约束条件，可行域的范围一般将扩大。（4）如果线性规划问题的对偶问题无可行解，则原问题也一定无可行解。（5）如果X1，X2都是某个线性规划问题的最优解，则X=λ1X1+λ2X1（λ1，λ2是正实数）也是这个问题的最优解。答：（1）不正确。在存在多个最优基解的情况下，它们的凸组合不是基解，但仍为最优解。（2）不正确。只需选取正检验数σj对应的变量入基，都可以使目标值增大。（3）正确。增加约束的可行域是原可行域的子集。（4）不正确。此时原问题还可能有无界解。（5）不正确。X1，X2的凸组合才是最优解。温州大学试卷纸试卷第4页共5页二、计算题（共20分）使用单纯形法求解下列线性规划问题，写出求解步骤，并给出：（1）最优解，（2）最优值。12312312123max224..26,,0zxxxxxxstxxxxx解：参考步骤：cB基bx1x2x3x4x50x44211100x5612001j-121000x413/2011-1/22x231/21001/2j-2010-11x313/2011-1/22x231/21001/2j-7/200-1-1/2得最优解x*=(0,3,1)，最优值z*=7。三、计算题（共20分）使用对偶单纯形法求解下列线性规划问题，写出求解步骤，并给出：（1）最优解，（2）最优值。123123123123max634324s.t.4412,,0zxxxxxxxxxxxx解：先引入2个人工变量，构造单位子矩阵：1231234123512345max634324s.t.4412,,,,0zxxxxxxxxxx+xxxxxx初始单纯形表：cB基bx1x2x3x4x50x4-4-3-2-1100x5-12-41[-4]01-6-3-400因为(-4)/(-4)=min{(-6)/(-4),(-4)/(-4)}，x3进基，x5出基：得分得分温州大学试卷纸试卷第5页共5页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-4x35/20-11/811/2-3/80-7/40-1-3/4得最优解(x1,x2,x3)=(1/2,0,5/2)，最优值z*=-13。