第五版运筹学基础与应用-大题模拟试题及答案

1、计算题一一1.1.下列线性规划问题化为标准型。（1010 分）mi nZx-|+5x2-2x3min Z 4为2x2+3x34x,+5x26X3=78% 9x210 x31112% 13x214X10,X2无约束，X303.3.用最小元素法求下列运输问题的一个初始基本可行解（1010 分）B1B1B2B3B4产量A110671241610&99A35410104销S52464 4 某公司有资金 1010 万元，若投资用于项目i（i 1,2,3）的投资额为x时，其收益分别为g1（x1）4禺4区）g（x3）2x3，问应如何分配投资数额才能使总收益最大？（1515 分）5 5.求图中所示网络

2、中的最短路。（1515 分）计算题二X1X2X362x1X23x35X1X210X10,X20,X3符号不限满足2 2. .写出下列问题的对偶问题（1010 分）9x2,5.5.某项工程有三个设计方案。据现有条件，这些方案不能按期完成的概率分别为0.5,0.7,0.9,0.5,0.7,0.9,1 1 某工厂拥有 A,B,CA,B,C 三种类型的设备，生产甲、乙两种产品，每件产品在生产中需要使用 的机时数，每件产品可以获得的利润，以及三种设备可利用的机时数见下表：产品甲户产品乙户设备能力/h卢铁A6SPPIP4陀设备Oh7力利渤（元伸）F15002刃 2门1求：（1 1 ）线性规划模型；（5 5

3、 分）（2 2）利用单纯形法求最优解；（1515 分）2、用对偶理论判断下面缰性规划是否存在最优解：10分）屮maxz=2孔+2x3*满足：J対+2皿叫3.判断下表中的启案能否作为恚上作业法求解运输间题的初始启宪， 说朋理由.ho分n+JB1B2B3Q+J产重门1020323020屮52直笄1知IV4S野+J105035Q4.4.如图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要 从Vl出发，经过这个交通网到达 V8，要寻求使总路程最短的线路。（1515 分）.2 14.4.用 DijkstraDijkstra 算法计算下列有向图的最短路。（1515 分）即三个方案均

4、完不成的概率为0.50.5X0.70.7X0.9=0.3150.9=0.315。为使这三个方案中至少完成一个的概率尽可能大，决定追加 2 2 万元资金。当使用追加投资后，上述方案完不成的概率见下表，问应如何分配追加投资，才能使其中至少一个方案完成的概率为最大。（1515 分）追加投资（万元）各方案完不成的概率1 12 23 30 00.500.500.700.700.900.901 10.300.300.500.500.700.702 20.250.250.300.300.400.40计算题三1 1、某工厂要制作 100 套专用钢架，每套钢架需要用长为 2.9m , 2.1m ,1.5m 的圆

5、 钢各一根。已知原料每根长 7.4m，现考虑应如何下料，可使所用的材料最省？产品甲产品乙设备能力/h/h设备 A A3 32 26565设备 B B2 21 14040设备 C C0 03 37575利润/ /（元/ /件）1500150025002500求：（1 1）写出线性规划模型（1010 分）（2 2）将上述模型化为标准型（5 5 分）2 2、求解下列线性规划问题， 并根据最优单纯形法表中的检验数，给出其对偶问题的最优解。（1515 分）max z 4x13x27x3广 为2x22x3100满足3x1X23x31000而d X2X2)( 1)022(s；Xi)所以Xi比较0,i0两个端

6、点max95*i0 9/2，与SI9/2矛盾，所以舍去。2max4xi2(sixi)0 x；10Sl i是极小值点。Xi0时，fi(i0) 2000S2当 k=1 时,X；0所以再由状态转移方程顺推：s2s；x*10 010因为S29/2所以x20，s3s2x210 0 10*因此x3s310最优投资方案为全部资金用于第 3 个项目，可获得最大收益5. 解：用 Dijkstra 算法的步骤如下，P P (vi) = 0 0T T (Vj)=(j= 2 2, 3 37 7)第一步：因为v1,v2，v1,v3A且v2,V3是 T T 标号，则修改上个点的 T T 标号分别为:T v2min T v

7、2,P v1w12=min ,0 55T v3min T v3,P vw1 3=min ,0 22所有 T T 标号中， T T(v3)最小，令 P P(V3)= 2 2第二步:v3是刚得到的P P 标号，考察v3v3,v4，v3,v6A，且v5，v6是T T 标号T v4min T v4,Pv3w34min ,2 79T v6min ,2 4二 6所有 T T 标号中， T T(v2)最小，令 P P(V2)= 5 5第三步:V2是刚得到的P P 标号，考察V2T v4min T v4,Pv2w24=min 9,5 27T v5min T v5,Pv2w25min ,5 712所有 T T

8、标号中， T T(v6)最小，令 P P(V6)= 6 6第四步:V6是刚得到的P P 标号，考察V6TV4min TV4,PV6w64=min 9,627TV5minTV5,P V6w65min12,617T v7min T v7,P v6w67200 万元。min ,6 612所有 T T 标号中，T T (V4), T T (v5)同时标号，令 P P (V4) =P=P(V5)=7 7第五步：同各标号点相邻的未标号只有VT v7min T v7, P v5w57=min 12,7 310至此：所有的 T T 标号全部变为 P P 标号，计算结束。故V至V7的最短路为 1010。计算题答

9、案二(1)maxz 1500% 2500 x23为2x2652为X2403x275x20CBXB1b1500 2500000X1X2X3X4X50 x3653210032.50 x4021010400X5750300125z01500 25000000X3153010-2/350 x152001-1/37.52500X22501001/3z-625001500000-2500/3-1500X15101/30-2/90X4500-2/311/92500X22501001/3z-7000000-5000-5001.解:*T最优解 X (5,25,0,5,0)最优目标值=70000 元2解：此规划存

10、在可行解x (0,1)T，其对偶规划minw 4y114y23y3满足：y13y232y12y2y32y1,y2, y30对偶规划也存在可行解y(0,1,0)T,因此原规划存在最优解。3、解：可以作为初始方案。理由如下:(1) 满足产销平衡(2) 有 m+n-1 个数值格(3) 不存在以数值格为顶点的避回路4. 解：5.解：此题目等价于求使各方案均完不成的概率最小的策略。把对第 k k 个方案追加投资看着决策过程的第 k k 个阶段，k k= 1 1, 2 2, 3 3。第 k k 个阶段，可给第 k,k, k+1k+1，3 3 个方案追加的投资额。DkUkUk0,1,2 且 UkXkXk 1

11、XkUk阶段指标函数CXk,UkPXk,Uk，这里的PXk,Uk是表中已知的概率值。 过程指标函数Xk_Uk_对第 k k 个方案的投资额T(V9=+QOP(V8J=12半可=：*P(VB)=103fkXkminC Xk,UkukDk以上的 k k = 1 1, 2 2, 3 3用逆序算法求解k k= 3 3 时，忖x3minCx3u3U3D3得表:4J4-aCIS羊pnwri.722屮0,4卩0.42卩表2*去 5UU2 P240.7X0.冲单0,(530.7X070 5X0 90.450 7X0.40.5X0.70.3X0 90.2TPA/zbuip+冷Aa0.5X0.27O.3XC.45

12、0J5Xad3m对匕2最优策略：U1= 1 1,u2=1,=1,U3=0=0 或U1= 0 0,U2=2,=2,U3=0=0,至少有一个方案完成的最大概率为1-0.135=0.8651-0.135=0.865计算题答案三1解 分析：利用 7.4m 长的圆钢截成 2.9m , 2.1 m ,1.5m 的圆钢共有如下表所 示的 8中下料方案。万案毛胚/m方案1方案2方案3方案4方案5方案6方案7方案82.921110000,3CXkUkVk 1,3fk 1xk 1f4X42.1021032101.5101302p4合计7.37.16.57.46.37.26.66.0剩余料 头 0.10.30.90

13、1.10.20.81.4设X1,X2,冷,X4,X5,X6,X7,冷分别为上面 8 中方案下料的原材料根数min zX1X2X3X4X5X6X7X82眄 +乃 + 码+x4100满足2花-+碍+3陌+2心+可仝100罚十兀十3曲十2為;十孑可十4心三1002解：引入松弛变量X4，X5将模型化为标准型，经求解后得到其最优单纯型表:最优单纯型表基变量bXX2X3X4X5X2253/4103/41/2X3255/4011/41/2i-25010/4001/22*T由此表可知，原问题的最优解X(0,25,25)，最优值为 250.表中两个 松弛变量的检验数分别为一 1/2 , 2，由上面的分析可知，对

14、偶问题的 最优解为(1/2,2)O3.3.解：不能作为初始方案，因为应该有n+m-1=5+4-1=8 有数值的格。4.4. 解：P P (vi)= 0 0T T (Vj)=(j= 2 2，3 37 7)第一步：因为Vi,V2，Vi,V3，Vi,V4A且V2，V3，v4是 T T 标号，则修改上个点的 T T 标号分别为:T v2min T v2,Pv-iw12= =min ,0 22T v3min T v3, P v1w13=min ,0 5 5T v4min T v4,P v1w14=min ,0 3 3所有 T T 标号中，T T (v2)最小，令 P P (v2)= 2 2第二步：V2是

15、刚得到的 P P 标号，考察v2V2,V3,V2,V6A，且V3，V6是 T T 标号T V3min T V3,P V2w23=min 5,2 2 4T V min ,2+7=9所有 T T 标号中，T T (V4)最小，令 P P (V4)= 3 3第三步：V是刚得到的 P P 标号，考察VT V5min T V5,P V4w45=min ,3 58所有 T T 标号中，T T (V3)最小，令 P P (V3)= 4 4第四步：V3是刚得到的 P P 标号，考察V3T V5min T V5,P V3w35=min 8,4 3 7T V6min T V6,P V3w36=min 9,4 5

16、9所有 T T 标号中， T T(V5)最小，令 P P(V5)= 7 7 第五步：V5是刚得到的 P P 标号，考察V5T V6min T V6,P V5w56=min 9,7 18T V7min T V7,P V5w57=min ,7 7 14所有 T T 标号中，T T ( ( % % )最小，令 P P ( % )= 8 8第 6 6 步：V6是刚得到的 P P 标号，考察V6T V7min T V7,P V6w67=min 14,8 5 13T(V7)= P P(V7)= 1313至此：所有的 T T 标号全部变为 P P 标号，计算结束。故V1至V7的最短路 为 1313。5.5.

17、解：第一步： 构造求对三个企业的最有投资分配， 使总利润额最大的动态规划 模型。(1) 阶段 k ：按 A 、B、C 的顺序，每投资一个企业作为一个阶段,k= 1, 2, 3, 4（2）状态变量Xk：投资第 k 个企业前的资金数（3）决策变量dk:对第 k 个企业的投资。（4）决策允许集合：dkXk。（5）状态转移方程：xkixkdk。（6）阶段指标：Vk（Xk,dk）见表中所示。（7）动态规划基本方程：fk（xQ maxVk（Xkd） fk侶i）0（终端条件）第二步：解动态规划基本方程，求最有值。k=4,彳心）k=3, daX3,x4X3daX2D2（X2）X3V2（X2,d2）V2（X2,d2）3（X3） f2（X2）*d221133+4= 77131233+7= 101012I 1 I55 + 4 = 941333+9= 1214322 5 :5+7= 123I 1 I310+4= 1451433+14= 17171, 3, 42：3 155+9= 14321010+7= 17X3D3（X3）X4V3（X3,d3）V3（X3,d3）f4（X4）f3（X3）*d311044+ 0= 44121044+0=4722r :77+0= 731244+0=4932177+ 0= 73；0 :99+0= 941344+ 0= 41442277+ 0= 73p99+ 0= 9401