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

计算题一一1.下列线性规划问题化为标准型。

（10分）mi nZx-|+5x 2-2x 3min Z 4为 2x 2+3x 3 4x ,+5x 2 6X 3=7 8% 9x 2 10x 3 11 12% 13x 214X 1 0,X 2 无约束，X 3B1B2 B3 B4 产量A110 6 7 12 416 10& 9 9A35410104销S5 24 6i （i 1,2,3）的投资额为x 时，其收益分别为 g 1（x 1） 4禺4区） g （x3） 2x3，问应如何分配投资数额才能使总收益最大？（15分）5.求图中所示网络中的最短路。

（15分）计算题二X 1 X 2X 3 6 2x 1 X 2 3x 3 5 X 1 X 210X 1 0,X 2 0,X 3符号不限满足 〈2. 写出下列问题的对偶问题 （10分）9x 2,5.某项工程有三个设计方案。

据现有条件，这些方案不能按期完成的概率分别为 0.5,0.7,0.9,1某工厂拥有 A,B,C 三种类型的设备，生产甲、乙两种产品，每件产品在生产中需要使用 的机时数，（2）利用单纯形法求最优解；（15分）2、用对偶理论判断下面缰性规划是否存在最优解：〔10分）屮 maxz = 2孔 +2x 3*满足： J 対+ 2皿叫3. 判断下表中的启案能否作为恚上作业法求解运输间题的初始启宪，说朋理由.ho 分n4.如图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。

现在有一个人要 从V l 出发，经过这个交通网到达 V8，要寻求使总路程最短的线路。

（15分）■.■'2 1即三个方案均完不成的概率为0.5X 0.7 X 0.9=0.315。

为使这三个方案中至少完成一个的概率尽可能大，决定追加2万元资金。

当使用追加投资后，上述方案完不成的概率见下表，问应如何分配追加投资，才能使其中至少一个方案完成的概率为最大。

（15分）计算题三1、某工厂要制作100套专用钢架，每套钢架需要用长为 2.9m , 2.1m ,1.5m的圆钢各一根。

已知原料每根长7.4m，现考虑应如何下料，可使所用的材料最省？求：（1（2）将上述模型化为标准型（5分）2、求解下列线性规划问题，并根据最优单纯形法表中的检验数，给出其对偶问题的最优解。

（15 分）max z 4x1 3x2 7x3广为2x2 2x3100满足3x1 X2 3x3 100< X1, X2, X3 03.断下表中方案是否可作为运输问题的初始方案，为什么？（10 分）4.用Dijkstra算法计算下列有向图的最短路。

（15分）5•某集团公司拟将 6千万资金用于改造扩建所属的 A 、B 、C 三个企业。

每个企业的利润增长额与所分配到的投资额有关，各企业在获得不同的投资额时所能增加的利润如下表所 示。

集团公司考虑要给各企业都投资。

问应如何分配这些资金可使公司总的利润增长额最 大？ （ 15分）业ABC L34C~ 5 ~ -7「 3 一11 10 -94151314v2v71、max(-z)=Xl 5x22(X 3 X3)2科 +*； + 3（坊一迟）一码 =52、写出对偶问题4•解：状态变量S k为第k 阶段初拥有的可以分配给第k 到底3个项目的资金额； 决策变量X k 为决定给第k 个项目的资金额；状态转移方程为S k 1 S k兀；最优 指标函数f k（Sk ）表示第k 阶段初始状态为Sk时，从第k 到第3个项目所获得的最大收益，fk （S k）即为所求的总收益。

递推方程为：maxgk（X k ） f k（Sk 1） （k 1,2,3）0 X k S k3、解:7yi 11y 2 14y 3f 3（S 3）当X 3 S3时，取得极大值 max2x 3x 3 S 32 2 S3 厶?f 3(s 3)max2x30 x 3 S 3即: 2x 2当k=2时有：f 2(s 2)max 9X20 X 2 S 2 max 9X 22S 3f 3（S 3）0 x 2 S 2max9x 2 2($0 x 2 S 2X 2)计算题答案f k (S k )f 4（S 4） 当k=3时有2h 2(s 2,x 2) 9X 2 2(s 2 x 2)用经典解析方法求其极值点dh 2 292(S 2 X 2)( 1) 0由dx 29X 2 S 2—解得：4d 2®,I c. 24 0而d X 2r9X 2S 2所以 4是极小值点。

极大值点可能在［0, s2］端点取得：2f 2(0) 2S 2 f 2(S 2) 9S 2当 f 2(0) f 2(S 2)时，解得 S29/2当 9/2 时，f 2(0) f 2(S 2)，此时，X ； 当虽 1 9/2时，f 2(0)彳 f 2(S 2)，此时，X2f i(Si )max 纠 f2(S2)0 X i S ；X ； i0 时，f i (i0)40X ；所以再由状态转移方程顺推：s 2 s ； x *10 010因为S2>9/2当 f 2(S 2) 9S 2时f l (§)max4xi9SI 9xi0 X S9s但此时 s 2 s ； x ；10 0c 2f i (10)I 当 f (S )r1 2s时，令 h i (S i ,X i )4X idh i/-4 4(S 2 由 dx i 解得： x 2S ； 1茫i>0 而 d X 2X 2)( 1)22(s ； X i )所以Xi比较［0,i0］两个端点 max 9' 5*i0 9/2，与S ^I 9/2矛盾，所以舍去。

2max 4x i 2(s i x i )0 x ； 10Sl i是极小值点。

X i 0 时，f i (i0) 2000 S2当k=1时,所以x2 0，s3 s2 x2 10 0 10*因此x3 s3 10最优投资方案为全部资金用于第 3 个项目，可获得最大收益5. 解：用Dijkstra 算法的步骤如下，P ( v i) = 0T ( Vj)= ( j= 2, 3…7)第一步：因为v1,v2 ，v1,v3 A且v2 , V3是T标号，则修改上个点的T标号分别为:T v2 min T v2 ,P v 1w 12=min ,0 5 5T v3 min T v3 ,P v w1 3=min ,0 2 2所有T标号中，T( v3)最小，令P((V3 )= 2第二步:v3是刚得到的P 标号，考察v3v3,v4 ，v3,v6 A ，且v5 ，v6是T 标号T v4 min T v4 ,P v3 w34—m in ,2 7 9T v6 min ,2＋4 二 6所有T标号中，T( v2)最小，令P((V2 )= 5第三步:V2是刚得到的P 标号，考察V2T v4 min T v4 ,P v2 w24 =min 9,5 2 7T v5 min T v5 ,P v2 w25min ,5 7 12所有T标号中，T( v6)最小，令P((V6 )= 6第四步:V6是刚得到的P 标号，考察V6T V4 min T V4 ,P V6 w64=min 9,6 2 7T V5 min T V5 ,P V6 w65min 12,6 1 7T v7 min T v7 ,P v6 w67200 万元。

min ,6 612所有T 标号中，T ( V 4), T ( v 5 )同时标号，令P ( V 4 ) =P ( V 5 )=7第五步：同各标号点相邻的未标号只有VT v 7 min T v 7 , P v 5w 57=min 12,7 310至此：所有的T 标号全部变为P 标号，计算结束。

故V至V7的最短路 为10。

计算题答案二(1) maxz 1500% 2500x 23为 2x 2652为 X 2 40 3x 2 75 x 2 01.解:满足(2)* T最优解X (5,25,0,5,0)最优目标值=70000元2•解：此规划存在可行解x (0,1)T ，其对偶规划minw 4y 1 14y 23y 3满足：y 1 3y232y 1 2y 2 y 3 2y 1,y 2, y 3 0对偶规划也存在可行解y (0,1,0)T,因此原规划存在最优解。

3、解：可以作为初始方案。

理由如下:(1) 满足产销平衡 (2) 有m+n-1个数值格(3) 不存在以数值格为顶点的避回路 4. 解：5.解：此题目等价于求使各方案均完不成的概率最小的策略。

把对第k 个方案追加投资看着决策过程的第k 个阶段，k = 1, 2, 3。

第k 个阶段，可给第k, k+1，…，3个方案追加的投资额。

D k U k U k 0,1,2且U k X kX k 1 X k U k阶段指标函数C Xk,Uk P Xk,U k ，这里的P Xk,U k 是表中已知的概率值。

过程指标函数Xk _____Uk _____ 对第k 个方案的投资额T(V9}=+QOP(V8J=12半可=：：*P(VB)=103f k X kmin C X k,Uku k D k以上的k = 1, 2, 3 用逆序算法求解k = 3 时，忖 x 3min Cx 3> u3U3 D 3得表:最优策略：U1 = 1, u2=1, U3=0或U 1= 0, U 2 =2, U3=0,至少有一个方案完成的最大概率为1-0.135=0.865计算题答案三1•解 分析：利用7.4m 长的圆钢截成2.9m , 2.1 m ,1.5m 的圆钢共有如下表所 示的8中下料方案。

,3C X k > U kVk 1,3fk 1 x k 1f 4 X 4设X1, X 2 ,冷,X 4 , X 5, X 6 , X 7 ,冷分别为上面8中方案下料的原材料根数min z X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 82眄+乃 + 码 +x 4 >100满足2花-+碍+3陌+ 2心+可仝100罚十兀十3曲十2為;十孑可十4心三1002•解：引入松弛变量X 4，X 5将模型化为标准型，经求解后得到其最优单纯型表: 最优单纯型表*T由此表可知，原问题的最优解X(0,25,25)，最优值为250.表中两个 松弛变量的检验数分别为一1/2 , — 2，由上面的分析可知，对偶问题的 最优解为(1/2,2)O3.解：不能作为初始方案，因为应该有 n +m-1=5+4-1=8有数值的格。

4. 解：P ( v i )= 0T ( Vj )=( j = 2，3…7)第一步：因为 V i ,V 2， V i ,V 3， V i ,V 4 A且V 2，V3，v 4是T 标号，则修改上个点的 T 标号分别为: T v 2 min T v 2 ,P v-iw 12=min ,0 22T v 3min T v 3 , P v 1w 13min ,0 5 5=T v4 min T v4 ,P v1 w14 =min ,0 3 3所有T标号中，T ( v2 )最小，令P ( v2 )= 2第二步：V2是刚得到的P标号，考察v2V2,V3 , V2,V6 A，且V3，V6 是T 标号T V3 min T V3 ,P V2 w23 =min 5,2 2 4T V min ,2+ 7 = 9所有T标号中，T ( V4 )最小，令P ( V4 )= 3第三步：V是刚得到的P标号，考察VT V5 min T V5 ,P V4 w45=min ,3 5 8所有T标号中，T ( V3 )最小，令P ( V3 )= 4第四步：V3是刚得到的P标号，考察V3T V5 min T V5 ,P V3 w35 =min 8,4 3 7T V6 min T V6 ,P V3 w36 =min 9,4 5 9所有T 标号中，T( V5 )最小，令P( V5)= 7 第五步：V5是刚得到的P 标号，考察V5T V6 min T V6 ,P V5 w56 =min 9,7 1 8T V7 min T V7 ,P V5 w57 =min ,7 7 14所有T标号中，T ( % )最小，令P ( % )= 8第6步：V6是刚得到的P标号，考察V6T V7 min T V7 ,P V6 w67 =min 14,8 5 13T(V7 )= P( V7)= 13至此：所有的T标号全部变为P标号，计算结束。