《运筹学》试卷09-答案

《《运筹学》试卷09-答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《运筹学》试卷库-试卷9答案一、单项选择题(1´5分）1.B2.B3.C4.D5.A二、判断正误（对者打“√”，错者打“×”。1´5分）1.√2.×3.×4.×5.√三、(25分）解:1.(3分）设产品Ⅰ、Ⅱ、Ⅲ在计划期内产量分别为x1、x2、x3，由题意，该问题的LP模型为：2.(15分）在约束中分别添加松弛变量x4、x5将LP化为标准形式，列单纯形表求解:cj20151800bqCBXBx1x2x3x4x500x4x523410[4]2301100805020sj201518000∴x1换入、x5换出:500x4x10[2]5/21-1/211/23/401/4602030

2、40sj0530-5-400∴x2换入、x4换出:5040x2x1015/41/2-1/4101/8-1/41/8305sj00-13/4-5/2-15/4-550∵"sj£0，∴得最优解:X*=(5,30,0,0,0)T，最优值z*=5503.∵x3是非基变量，故当s3’£0，即Dc3£-s3=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分；正确列出L

3、P模型:2分。2.化标准形式、答案各1分，第1张单纯形表3分,第2,3张单纯形表各5分；3.3分。4.正确列出对偶问题模型:3分；最优解1分。个别数据错误酌情扣分。四、(10分)解:设计划期内A、B、C三种产品的产量分别为x1,x2,x3，由题意，该问题的GP模型为:评分标准:正确设定决策变量:2分；正确列出目标规划模型:8分。个别条件列错酌情扣分。五、(15分）解:化简系数矩阵:圈出C’中的独立0元素:52W223W2105759814W6362PPP52W223W2105759814W6362-2-2+2→70202430200835311810404140=C’’C’中只

4、有4个独立0元素，需要继续变换:用最少直线数覆盖所有0元素，未被直线覆盖的元素中的最小元素是2，则未被直线覆盖的行中每个元素-2,被直线覆盖的列中每个元素+2，得到C’’。圈出C’’中的独立0元素:72W2432W835311814W414已得到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)采

5、用逆序解法(顺序解法亦可);(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,…,n(5)决策变量uk=(xk，yk)，其中xk:用于第k种产品生产的第一种资源数,yk:用于第k种产品生产的第二种资源数。(6)允许决策集合:Dk(Xk,Yk)={(xk，yk)

6、0£xk£Xk，0£yk£Yk},k=1,2,…,n(7)

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基本方程为：k=n,n-1,…,2,1评分标准:(1)～(10)项每项1分.七、(15分）解:(1)标号过程：先给vs标以(0，+∞)。检查vs的相邻未标号点，发现v1、v2符合标号条件，故给v1以标号(vs,min｛+∞,cs1-fs1｝)=(vs,2)；给v2以标号(vs,min｛+∞,cs2-fs2})=(vs,2)。继续标

8、号过程，给v3以标号(v2,min｛2,c23-f23｝)=(v2,2)；给vt以标号(v3,min｛2,c3t–f3t})=(v3,2)。至此vt已得到标号，说明存在一条可增广链：vs→v2→v3→vt，如图1。转调整过程。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)(2)调整过程：沿可增广链调整流量，调整量δ=dvt=2，即令可增广链上所有前向弧的流