《运筹学》试卷09答案

《运筹学》试卷库-试卷9答案一、单项选择题(15分）1.B2.B3.C4.D5.A二、判断正误（对者打“√”，错者打“×”。15分）1.√2.×3.×4.×5.√三、(25分）解:1.(3分）设产品Ⅰ、Ⅱ、Ⅲ在计划期内产量分别为x1、x2、x3，由题意，该问题的LP模型为：3,2,1,080324100432..181520max321321321jxxxxxxxtsxxxzj2.(15分）在约束中分别添加松弛变量x4、x5将LP化为标准形式，列单纯形表求解:cj20151800bCBXBx1x2x3x4x500x4x523410[4]2301100805020j201518000∴x1换入、x5换出:500x4x10[2]5/21-1/211/23/401/460203040j0530-5-400∴x2换入、x4换出:5040x2x1015/41/2-1/4101/8-1/41/8305j00-13/4-5/2-15/4-550∵j0，∴得最优解:X*=(5,30,0,0,0)T，最优值z*=5503.∵x3是非基变量，故当3’0，即c3-3=13/4，亦即c3’85/4时，原最优解仍是最优解。4.对偶问题为：minw=100y1+80y22y1+4y3203y1+2y2154y1+3y218y1,y20对偶问题最优解：Y*=(5/2,15/4)T，最优值w*=550评分标准:1.正确设定决策变量:1分；正确列出LP模型:2分。2.化标准形式、答案各1分，第1张单纯形表3分,第2,3张单纯形表各5分；3.3分。4.正确列出对偶问题模型:3分；最优解1分。个别数据错误酌情扣分。四、(10分)解:设计划期内A、B、C三种产品的产量分别为x1,x2,x3，由题意，该问题的GP模型为:6,,1,0,,3,2,1,04048035.2230000200180150507090..},,),(min{665553214432133322211164534232111iddjxdddddxxxddxxxddxddxddxtsdPdPdPddddPiij评分标准:正确设定决策变量:2分；正确列出目标规划模型:8分。个别条件列错酌情扣分。五、(15分）解:化简系数矩阵:'2636040189575100020322020548582734111291191443536564649CC圈出C’中的独立0元素:C’中只有4个独立0元素，需要继续变换:用最少直线数覆盖所有0元素，未被直线覆盖的元素中的最小元素是2，则未被直线覆盖的行中每个元素-2,被直线覆盖的列中每个元素+2，得到C’’。圈出C’’中的独立0元素:已得到5个独立0元素。∴最优指派方案为:I做B工作；II做C工作；III做A工作；IV做D工作；V做E工作。总耗时为4+3+4+3+4=18（天）。评分标准:变换系数矩阵得到C’：3分；进一步变换系数矩阵得到C’’：7分；圈出5个独立0元素、给出最优指派方案：5分。个别数据错误酌情扣分。六、(10分)解:建立该问题的动态规划模型如下:(1)采用逆序解法(顺序解法亦可);(2)阶段：按产品划分阶段,每种产品为一个阶段，k＝1,2,…,n(3)状态变量状态变量sk＝(Xk,Yk)，其中：Xk：分配用于生产第k至第n种产品的第一种资源数;Yk：分配用于生产第k至第n种产品的第二种资源数。(4)状态集合:S1=(a,b)，Sn+1=(0，0),(0，0)Sk(a,b)，k=2,3,…,n72243283531181441470202430200835311810404140=C’’5222321057598146362-2-2+2→5222321057598146362(5)决策变量uk=(xk，yk)，其中xk:用于第k种产品生产的第一种资源数,yk:用于第k种产品生产的第二种资源数。(6)允许决策集合:Dk(Xk,Yk)={(xk，yk)|0xkXk，0ykYk},k=1,2,…,n(7)状态转移方程：Xk+1=Xk-xk,Yk+1=Yk-yk，k＝1,2,…,n(8)阶段指标:gk(xk,yk)，k＝1,2,…,n(9)最优指标函数f(Xk,Yk)表示表示当分配于第k种产品至第n种产品两种资源数量为Xk和Yk时的最大收益。(10)DP基本方程为：评分标准:(1)～(10)项每项1分.七、(15分）解:(1)标号过程：先给vs标以(0，+∞)。检查vs的相邻未标号点，发现v1、v2符合标号条件，故给v1以标号(vs,min｛+∞,cs1-fs1｝)=(vs,2)；给v2以标号(vs,min｛+∞,cs2-fs2})=(vs,2)。继续标号过程，给v3以标号(v2,min｛2,c23-f23｝)=(v2,2)；给vt以标号(v3,min｛2,c3t–f3t})=(v3,2)。至此vt已得到标号，说明存在一条可增广链：vs→v2→v3→vt，如图1。转调整过程。(2)调整过程：沿可增广链调整流量，调整量δ=vt=2，即令可增广链上所有前向弧的流量增加2。调整后得到的可行流如图2：(3)重新标号：去掉所有标号，对新的可行流重新标号。给vs标（0,+∞）,给v1以标号(vs,min｛+∞,cs1-fs1})=(vs,2)。至此标号进行不下去，而vt未得到标号，说明图中的流已是最大流。最大流量w(f*)=f4t+f3t=16。最小割集SS,={(vs,v2),(v1,v3),(v1,v4)},如图2中的虚线所示。最小割集的容量为：c(S,Ŝ)=cs1+c13+c14=10+3+3=16,与最大流的流量相等。vsvtv3v1v2v3(8,6)(10,8)(6,0)(6,6)(5,2)(3,3)(8,5)(3,3)(9,9)图1图1(0,+∞)(vs,2)(vs,2)(v2,2)(v3,2)0)(),(),(),(11100maxnnkkkkkkkkYyXxkkksfyYxXfyxgYXfKkkkk=n,n-1,…,2,1vsvtv3v1v2v4(8,6)(10,10)(6,0)(6,6)(5,4)(3,3)(8,7)(3,3)(9,9)图1图2(0,+∞）(vs,2)评分标准:(1)、(2)、（3）、图1、图2各3分。若算法步骤和图不完整,可适当扣分。八、(15分）解:闭回路法求得表中基可行解的非基变量的检验数，填入表1中空格的左下角。∵110，∴表中基可行解不是最优解。用闭回路法对表中的解进行调整，闭回路为：（x11）—x12—x22—x21—（x11），调整量为min{x12，x21}=10，调整后得到一个新的基可行解,如表2。再用闭回路法求得表2中基可行解的非基变量的检验数，填入表2中空格的左下角。∵ij0，∴表2中的解即为问题的最优解。最小总运费z=410+250+330+245+270+420=540。评分标准:两个表中的基可行解的检验和解的调整各5分。个别数据错误酌情扣分。表1销地产地B1B2B3B4产量4532A1-210350603257A2403588758724A300702090需求量40457070表2销地产地B1B2B3B4产量4532A1102350603257A2304566758724A322702090需求量40457070