2023《运筹学》考试题及其答案.doc

2023《运筹学》考试题及其答案 2023-2023学年第1学期《运筹学》考试题答案 要求:第一题必做〔50分〕，二三四题任选两题〔每题各25分〕 一、 考虑下面线性规划问题 minz?4x1?x2?3x1?x2?3?4x?3x?6?2s.t.?1?x1?2x2?3-x1,x2?0〔1〕 〔2〕〔3〕〔1〕 用图解法求解该问题； 〔2〕 写出该问题的标准形式； 〔3〕 求出该问题的松弛变量和剩余变量的值； 〔4〕 用单纯形法求解 【解答】(1)图中阴影局部为此线性规划问题的可行域,目的函数z?4x1?x2,即x2-4x1?z是斜率为?4的一族平行直线,由线性规划的性质知,其最值在可行域的顶点获得,将直线z?4x1?x2沿其法线方向逐渐向上平移,直至A363618点,A点的坐标为(,),所以minz?4-? 5555536此线性规划问题有唯一解x1?，x2? 55(2)给等式〔2〕左端添加剩余变量x3，给等式〔3〕左端添加松弛变量x4，那么得到该问题的标准型为： maxz-4x1?x2?0x3?0x4?3x1?x2?3,?4x?3x?x?6,?123s.t.-x1?2x2?x4?3,-x1,x2,x3,x4?0〔1〕〔2〕 〔3〕36〔3〕在上面标准型中令x1?，x2?，得到剩余变量x3=0，松弛变量x4=0。

55〔4〕先在上面标准型中约束条件(1)、〔2〕中分别参加人工变量x5,x6，得到如下数学模型， 1 maxz-4x1?x2?0x3?0x4?Mx5?Mx6?3x1?x2?x5?3,?4x?3x?x?x?6,?1236s.t.-x1?2x2?x4?3,-x1,x2,x3,x4,x5,x6?0〔1〕〔2〕 〔3〕由此列出单纯形表逐步迭代，用大M法求解计算结果如下表所示 CB Cj xj XB －4 －1 0 0 －M －M b 3 6 3 －9M ?i 1 3/2 3 3 6/5 x1 【3】 4 1 7 M－4 x2 1 3 2 4M－1 x3 0 －1 x4 0 0 1 0 x5 1 0 0 0 x6 0 1 0 0 －M －M x5 x6 x4 rj 0 －4 －M 0 －M x1 1 0 0 0 1 0 0 0 1 0 0 0 1/3 【5/3】 0 －1 0 0 1/3 －4/3 －1/3 (－7M+4)/3 0 1 0 0 1 2 2 x6 x4 0 rj(-z) －4 －1 5/3 (5M+1)/3 0 rj(-z) －4 －1 x1 x2 x4 x1 x2 0 1 0 0 0 1 0 0 0 1 －M 0 1/5 0 －3/5 0 【1】 1 1/5 0 －1/5 0 3/5 0 1 0 1 －1/5 3/5 －4/5 1 －M+8/5 2/5 －1/5 6/5 －4-2M －1/5 3/5 1/3 3/5 － 6/5 1 0 0 －M-1/5 －18/5 0 3/5 0 6/5 －1 －M －0 rj(-z) x3 1 －M+7/5 0 18/5 36表中所有检验数rj?0,根据最优解定理，问题存在唯一的最优解X?(,,0,0,0,0)T，目的函553618数的最优值maxz?4-?。

555 二、 试用表上作业法求解以下运输问题的最优解 产地 销地 A1 A2 B1 4 9 B2 8 5 2 B3 8 6 B4 4 3 产量 6 4 A3 销量 3 6 11 2 4 7 2 7 12 【解答】：显然该问题是一个供需平衡问题，利用伏格法求出初始方案，如下表所示 A1 A2 A3 6 0 6 B1 4 9 3 2 2 B2 8 5 11 7 7 B3 8 6 4 2 5 7 B4 4 3 2 产量 6 4 12 销量 用位势法求出各非基变量〔即空格〕的检验数，如下表所示 A1 A2 A3 6 (5) 0 B1 4 9 3 B2 (3) 2 (7) 8 5 11 (3) (1) 7 B3 8 6 4 B4 ui 4 3 2 (1) 2 5 u1=0 u2=0 u3=－1 vj v1=4 v2=5 v3=5 v4?3 因为所有非基变量的检验数均为非负的，故表中的解为最优解按照此种方案调运，最小费用为：6×4+2×5+2×3+0×3+7×4+5×2= 78 三、 用标号算法求解以下图中从V1到各点的最短路 3 【解答】：此为最短路问题，权数为正，用Dijksta算法的计算步骤如下： v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 初始值 1 2 3 4 5 6 7 8 9 T( ) P( )+wij T( ) P( )+wij T( ) P( )+wij T( ) P( )+wij T( ) P( )+wij T( ) P( )+wij T( ) P( )+wij T( ) P( )+wij T( ) P( )+wij T( ) {0} ∞ 0+2 {2} ∞ 0+8 8 2+6 8 3+5 8 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 3+∞ ∞ 0+∞ 0+∞ 0+∞ 0+∞ 0+∞ 0+∞ 0+∞ 0+∞ 2+∞ 2+1 2+∞ 2+∞ 2+∞ 2+∞ 2+∞ 3+∞ 3+∞ 3+∞ 3+1 ∞ 2+∞ {3} 3+∞ ∞ 4+∞ 4+∞ {8} ∞ 8+7 15 10+∞ 15 11+∞ 15 14+∞ {15} ∞ 3+∞ {4} 4+6 4+∞ 4+7 10 11 ∞ 8+∞ 8+∞ 8+∞ {10} ∞ 11 10+4 10+∞ 14 {11} 11+∞ {14} ∞ 4+∞ ∞ 4+∞ ∞ 8+∞ ∞ 8+∞ ∞ 10+∞ ∞ 10+∞ ∞ 11+∞ ∞ 11+9 ∞ 14+1 {15} 20 14+∞ 11 15+4 {19} 由上表的迭代过程可得：Sq?{v1， v2，v5，v9，v3，v6，v8， v7，v4， v10，v11} d(v1,v2)=2,最短路：〔v1,v2〕； d(v1,v5)=3,最短路：〔v1,v2,v5〕； d(v1,v9)=4,最短路：〔v1,v2,v5,v9〕；d(v1,v6)=10,最短路：〔v1,v2,v5,v9,v6〕； d(v1,v3)=8,最短路：〔v1,v3〕或〔v1,v2,v3〕或〔v1,v2,v5,v3〕； d(v1,v8)=11,最短路：〔v1,v2,v5,v9,v8〕；d(v1,v7)=14最短路：〔v1,v2,v5,v9,v6,v7〕； d(v1,v4)=15,最短路：〔v1,v3,v4〕或〔v1,v2,v3,v4〕或〔v1,v2,v5,v3,v4〕； d(v1,v10)=15,最短路：〔v1,v2,v5,v9,v6,v7,v10〕； d(v1,v11)=19,最短路：〔v1,v2,v5,v9,v6,v7,v10,v11〕； 四、 某公司面对四种自然状态的三种备选行动方案收益表如下，假定状态概率未知，试分别用悲观准那么、等可能性准那么、懊悔值准那么和乐观系数准那么〔α=0.6〕进展决策。

4 收 益 方 案 状 值 态 θ1 15 4 1 θ2 8 14 4 θ3 0 8 10 θ4 －6 A1 A2 A3 【解答】：〔1〕应用悲观准那么： 3 12 ,-6}-min{15,8,0--3∴S2为最正确方案 ,3}-max?-6,3,1∵max?min{4,14,8?min{1,4,10,12}-?(2)应用等可能性准那么：∵E(A1)?117(15?8?0?6)?, 44129127E(A2)?(4?14?8?3)?, E(A3)?(1?4?10?12)? , 444417292729max{,,}-E(A2) ，∴S2为最正确方案 4444〔3〕应用懊悔值准那么：先求出懊悔值矩阵 0,6,10,18}-max{?068--?B-11029?∵min?max{11,0,2,9}-min{18,11,14}?11 ∴S2为最正确方案 ?141000-max{14,10,0,0}--?(4)应用乐观系数准那么〔α=0.6〕：先计算各个方案的折中益损值： E(A1)?0.6?15?0.4?〔?6〕?6.6， E(A2)?0.6?14?0.4?3?9.6， E(A3)?0.6?12?0.4?1?7.6， ∵max{6.6,9.6,7.6}?9.6?E(A2) ∴S2为最正确方案 下表为求解某目的函数为极大化线性规划问题的最终单纯形表，表中x4,x5为松弛变量，问题的约束为 ? 形式〔共8分〕 x1 x2 1/2 －1/2 x3 1 0 x4 1/2 －1/6 x5 ０ 1/3 x3 x1 5/2 5/2 0 1 5 第 页 共 页。