运筹学_刘洪伟_《运筹学》试题.docx

运筹学》试题（答案）（2002-1-9, 考试时间 120 分钟）一、单项选择题下列每题给出的四个答案中只有一个是正确的，将表示正确答 案的字母填入题后的括号中20 分）1. 对一个极大化的线性规划问题用单纯形法求解，若对所有的检验数7 j -0，但对某个 非基变量"丿，有7 j = 0，则该线性规划问题（B）A. 有唯一的最优解；B.有无穷多个最优解；C.为无界解；D.无可行解2. 使用人工变量法求解极大化线性规划问题时，当所有的检验数7 j-0，在基变量中仍 含有非零的人工变量，表明该线性规划问题（ D ）A. 有唯一的最优解；B.有无穷多个最优解；C.为无界解；D.无可行解3. 在对偶问题中，若原问题与对偶问题均具有可行解，则（ A ）A. 两者均具有最优解，且它们最优解的目标函数值相等；B. 两者均具有最优解，原问题最优解的目标函数值小于对偶问题最优解的目标函数值;C. 若原问题有无界解，则对偶问题无最优解；D. 若原问题有无穷多个最优解，则对偶问题只有唯一最优解；4. 在用对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（ D ）A. b列元素不小于零；B.检验数都大于零；C.检验数都不小于零；D.检验数都不大于 零。

5. 在产销平衡运输问题中，设产地为m个，销地为n个，那么解中非零变量的个数（A ） A.不能大于（m+n-1）； B.不能小于（m+n-1）； C.等于（m+n-1）； D.不确定6. 在运输问题中，每次迭代时，如果有某非基变量的检验数等于零，则该运输问题（ B ） A.无最优解；B.有无穷多个最优解；C.有唯一最优解；D.出现退化解7. 在目标规划中，求解的基本原则是首先满足高级别的目标，但当高级别目标不能满足 时（ D ）A.其后的所有低级别目标一定不能被满足；B.其后的所有低级别目标一定能被满足； C.其后的某些低级别目标一定不能被满足；D.其后的某些低级别目标有可能被满足8. 若一个指派问题的系数矩阵的某行各元素都加上常数k得到一个新的矩阵，这一新矩 阵对应着一个新的指派问题，则（ A ）A.新问题与原问题有相同的最优解；B.新问题最优目标值大于原问题最优目标函数值； C.新问题最优解等于原问题最优解加上k ； D.新问题最优解小于原问题最优解9. 如果要使目标规划实际实现值不超过目标值，则相应的偏离变量应满足（ B ）A. d +> 0 ； b. d +二 0 ； c. d _ = 0 ； d. d _> 0, d +> 0-10. 动态规划问题中最优策略具有性质：（ C ）A.每个阶段的决策都是最优的；B. 当前阶段以前的各阶段决策是最优的；C. 无论初始状态与初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应 构成最优策略；D. 它与初始状态无关。

二、计算题1.用单纯形法求解以下线性规划问题max z = 3x + 5 x12'x < 412 x < 12s.t.< 23x + 2 x < 1812x , x > 012解： 化为标准型如下x+ x132x+ x243x+ 2 x+ x125x , x>0max z = 3x + 5 x1212121835000CBXBbx1x2x3x4x5a0x34101000x4120[2]01060x518320019c.-z.350000x341010045x260101/200x56⑶00-112c.-z.300-5/200x320011/3-1/35x260101/2032100-1/31/3Cj-Zj-5/2-1所以最优解为x1=2, x=6，最优值为z=362．已知线性规划问题：max z = x + 2 x+ 3 x+ 4 x1234x+2x+2 x +3x<201234s.t.2 x +x+3x +2x<201234x , x , x,x>01234写出其对偶问题1 ) ( 1 )(2) (2) 若已知其对偶问题最优解为yi = 1.2, y2 = 0.2 ,的最优解根据对偶理论求出原问题解：(1)其对偶问题为min wy1=20 y + 20 y+ 2 y > 122 y + y > 2123 yi + 2 y2 > 4y1,y2>0(2)将yi = 1.2,y 2 = 0.2代入到对偶问题的四个约束条件可得1*1.2+2*0.2>1; 2*1.2+0.2>1; 2*1.23*0.2=3; 3*1.2+2*0.2=4那么由互补松驰性得，X]=0; x2=0; x3 0; x4 00再由y1? y2>0得，原问题的两个约束条件均取 等号，这样联立方程求解原问题的最优解为，x1=0; x2=0; x3=4; x4=4,目标函数值z=28.3•求出下图中从A到E的最短路线及其长度。

D11B1C12AB2D2E14C23个状态解：把整个最短路线问题分为B3个介段，建立模型：A, B, C, D’lE1为 当 k=4 时，f(D1)=3, f(D2)=1, f(D3)=5 当 k=3 时，了 (Di)+ 2 ] 卩 + 2、f (C ) = min\ f (D ) + 5 > = min\ 1 + 5 > = 57 (D1)+1 f (D ) + 4 23 +1= min1 + 4 >f (D ) + 235 + 22f(D3)+ 4J5 + 44f(C2)=，相应的决策为u ；(Ci)= Di，相应的决策为U；(C2)= D1当 k =2 时，| f (D) + 4、f(B1)=mi3 + 4min< f (C ) + 4 > = min< 5 + 4 > = 71f (J" 3， 相 应 的 决 策 为 U*(B1)=D1 或u*(B ) =C2 1 2f (C)+11>f (C ) + 3' 2 JI f (D3) + 3、 |5 + 3、f (B ) = min< f (C ) + 5 > = min< 4 + 5 > = 8f (B ) = min<2I 5 +1> =min<14 + 3J 丿> =6，相应的决策为U 2( B2)= C11f (C2" 3， 相 应 的 决 策 为 U*(B3)=D3 或U * (B ) = C232当 k =1 时，f ( A) = miI + 3、min < f (B ) + 2 > = min < 6 + 2 > = 82f (B3)+ 1了 (B1) + 3、，相应的决策为U；(A) = B2 所以最短路线为：A->B2->C1->D1->E,其长度为8。

4.已知A，B两人对策时对A的赢得矩阵如下，求双方各自的最优策略及对策值 _ 2 1 4_2 0 3-1 - 2 0解：这是一个纯局势下的对策问题，A取a1，B取卩2为双方的最优纯策略A 的蠃得值的 1， B 的赢得值为-15.某一决策问题的损益矩阵如下表所示，其中矩阵元素值为年利润事件E1E2E3概率PPP万案 f123S1402002400S 2360360360S31000240200(1) (1) 若各事件发生的概率Pj是未知的，分别用悲观准则(maxmin准则)、乐观准则(maxmax准则)选出决策方案2) (2) 若Pi = °2P2 = °.7, P3 = 0.1，则用期望收益值准则会选择哪个 方案？解：参照P378-386。