运筹学期中考试卷答案

1、温州大学期中考试试卷2015-2016学年第一学期考试科目运筹学B考试形式开卷（仅允许带教材）考试对象题号一二三总分得分/60/20/20、简答题（每小题10分，共60分）1、某企业在今后三年内有4种投资机会。第种：三年内每年年初投得分资，年底可获利润20%,并将本金收回；第种：第一年年初投资，第二年年底可获利润50%,并将本金收回，但该项目投资不得超过万元；第种：第二年年初投资，第三年年底收回本金，并获利润60%,但该项目投资不得超过万元；第种：第三年年初投资，于该年年底收回本金，且获利40%,但该项目投资不得超过万元。现在该企业准备拿出万元资金，问如何制定投资计划，使到第三年年末本利和最大

2、。为此，设Xj为第i年投资到第j个方案的资金，共6个决策变量。分析投资情况见下表。年份A年初第一年底（第二年初）第二年底（第三年初）第三年底xii出入投资x21出入x31出入x12出1入额x23出入x34出入试根据上述决策变量和投资分析表写出该问题的线性规划模型。解：0.5x12 0.6x23 0.4x34)maxz1.6x231.2x311.4x34(or0.2x110.2x210.2x31X11x12x21S.t. *23x31x34xiix122x231.51.2x11 (or x11 x121.5x121.2x210, x120, x21x21x233 1.2x11)0, x230,

3、x310,x3402、画出下列线性规划问题的图解法可行域。maxz5x12x24Kx220x1x210s.t.x1x22x10,x20解：3、将下面的线性规划问题写成标准化形式。maxzx1x22x32Kx25x312x12x27x36s.t.x16x34x10,x20,x30解：maxzx1'x22x3126y2 42x1'x25x3y1x1'2x27%s.t.x1'6x3K'0,x20,x30,y10,y204、写出下列线性规划问题的对偶问题。maxzx1x22x32x1x25x312x12x27x36s.t.x16x34x10,x20,x30解:m

4、inw12yl6y24y32VlV2丫31,Vi2y21s.t.5yi7y26y32Vi0,y2任意，丫305、简述单纯形法和对偶单纯形的异同点，填入下表。答：相同点：都含一个单位子矩阵，都要进行换基迭代，都用于求解线性规划问题的原问题。不同点：单纯形法对偶单纯形法初始状态常数列非负检验数非正算法结束判断准则检验数全非正，结束计算常数列全非负，结束计算换基方法检验数正者，入基，按照与常数列的最小比例选择出基变量常数列负者，出基，按照与检验数的最小比例选择入基变量6、下面命题是否正确解释理由。(1)线性规划问题的可行解如为最优解，则该可行解一定为基可行解。(2)单纯形法迭代计算中，必须选取同最大

5、正检验数6j对应的变量作为入基变量。(3)线性规划问题增加一个约束条件，可行域的范围一般将缩小；减少一个约束条件，可行域的范围一般将扩大。(4)如果线性规划问题的对偶问题无可行解，则原问题也一定无可行解。(5)如果X1,X2都是某个线性规划问题的最优解，则X=NX1+；2X1(储M是正实数)也是这个问题的最优解。答：(1)不正确。在存在多个最优基解的情况下，它们的凸组合不是基解，但仍为最优解。(2)不正确。只需选取正检验数bj对应的变量入基，都可以使目标值增大。(3)正确。增加约束的可行域是原可行域的子集。(4)不正确。此时原问题还可能有无界解。(5)不正确。X1,X2的凸组合才是最优解。二、

6、计算题（共20分）（1）最优得分使用单纯形法求解下列线性规划问题，写出求解步骤，并给出:解，（2）最优值。maxz2x1s.tx12x1,x2解：经f少骋i：x12x2x2x3“2,x30乂346CB基bx1x2x3x4x500x4x5462111012001j-1210002x4x2133/2011-1/21/21001/2j-2010-112x3x2133/2011-1/21/21001/2j-7/200-1-1/2得最优解x*=（0,3,1）,最优值z*=7。三、计算题（共20分）使用对偶单纯形法求解下列线性规划问题，写出求解步骤，并给出：（1）最优解，（2）最优值。maxz6x13x2

7、4x33x12x2x34s.t.4x1x24x312x1,x2,x30解：得分先引入2个人工变量，构造单位子矩阵：max z3x1 2x2%s.t. 4x1 x2 4x3x1,x2,x3,x4,x54x3x44+x5120初始单纯形表:CB基bx1x2x3x4x50x4-4-3-2-1100x5-12-41-401-6-3-400因为(-4)/(-4)=min(-6)/(-4),(-4)/(-4),xx5出基：CB基bx11x2.x3x4x50X4-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