1、1计算题一1. 下列线性规划问题化为标准型。(10 分)123min+5-Zx12360,x符 号 不 限2. 写出下列问题的对偶问题 (10 分)12min4+Zx312356=789014,xx无 约 束 ，3. 用最小元素法求下列运输问题的一个初始基本可行解(10 分)4某公司有资金 10 万元，若投资用于项目 (1,23)ii x的 投 资 额 为 时 ， 其 收 益 分 别 为112(),()9,gxx3问应如何分配投资数额才能使总收益最大？(15 分)5 求图中所示网络中的最短路。 （15 分）计算题二满足满足21、某工厂拥有 A,B,C 三种类型的设备，生产甲、乙两种产品，每件产
2、品在生产中需要使用的机时数，每件产品可以获得的利润，以及三种设备可利用的机时数见下表：求：（1）线性规划模型；（5 分）（2）利用单纯形法求最优解；（15 分）4. 如图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从 1v出发，经过这个交通网到达 8v，要寻求使总路程最短的线路。 （15 分）5. 某项工程有三个设计方案。据现有条件，这些方案不能按期完成的概率分别为30.5,0.7,0.9,即三个方案均完不成的概率为 0.50.70.9=0.315。为使这三个方案中至少完成一个的概率尽可能大，决定追加 2 万元资金。当使用追加投资后，上述方案完不成的概率见下表，问应
3、如何分配追加投资，才能使其中至少一个方案完成的概率为最大。(15 分)计算题三1、某工厂要制作 100 套专用钢架，每套钢架需要用长为 2.9m , 2.1m , 1.5m 的圆钢各一根。已知原料每根长 7.4m ，现考虑应如何下料，可使所用的材料最省？产品甲 产品乙 设备能力/h设备 A 3 2 65设备 B 2 1 40设备 C 0 3 75利润/(元/件) 1500 2500求：（1）写出线性规划模型（10 分）（2）将上述模型化为标准型（5 分）2、求解下列线性规划问题，并根据最优单纯形法表中的检验数，给出其对偶问题的最优解。（15 分）123ax47mzx10123,3 断下表中方案
4、是否可作为运输问题的初始方案，为什么？（10 分）4. 用 Dijkstra 算法计算下列有向图的最短路。 （15 分）各方案完不成的概率追加投资（万元） 1 2 30120.500.300.250.700.500.300.900.700.40满足4v2 v6v1v4 v5 v7v3235 21 735 1 7555某集团公司拟将 6 千万资金用于改造扩建所属的 A、B、C 三个企业。每个企业的利润增长额与所分配到的投资额有关，各企业在获得不同的投资额时所能增加的利润如下表所示。集团公司考虑要给各企业都投资。问应如何分配这些资金可使公司总的利润增长额最大？（15 分） 5计算题答案一1、max
5、(-z)= 1235()xx2、写出对偶问题maxW= 12374yy3、解： 4解：状态变量 ks为第 k 阶段初拥有的可以分配给第 k 到底 3 个项目的资金额；决策变量 kx为决定给第 k 个项目的资金额；状态转移方程为 1kksx；最优指标函数 ()f表示第 k 阶段初始状态为 ks时，从第 k 到第 3 个项目所获得的最大收益，fs即为所求的总收益。递推方程为：10()()(),2)makkkkxsfgfs4当 k=3 时有3230()xsf当 3xs时，取得极大值 2 ，即：3230()axsf当 k=2 时有： 2230()9()mxsffs2xs2220()a6令 222(,)
6、9()hsxsx用经典解析方法求其极值点。由 2210d解得： 94xs而 20dh所以 294xs是极小值点。极大值点可能在0， 2端点取得：2(0)f， 2()9fs当 s时，解得 /当 29/s时， 22ff，此时， *20x当 时， ()s，此时， s当 k=1 时， 11204()maxsff当 22()9fs时， 11()9sx105xss但此时 21/2x，与 2/矛盾，所以舍去。当 ()fs时，110()4()axf x令 21,()hss由 24dx解得： 21s而 20hdx所以 1xs是极小值点。比较0,10两个端点 1时， (0)2f时， 14*1x所以再由状态转移方程
7、顺推：*210s因为 9/所以 *20x， *321x因此 3s7最优投资方案为全部资金用于第 3 个项目，可获得最大收益 200 万元。5. 解：用 Dijkstra 算法的步骤如下，P（ 1v）0T（ jv） （ j2，37）第一步：因为 1,， 1,vA且 2， 3是 T 标号，则修改上个点的 T 标号分别为：122,minwPv= 051333,iv= 所有 T 标号中，T（ 3）最小，令 P（ 3v）2第二步： 3v是刚得到的 P 标号，考察34,， 6,A，且 5， 6是 T 标号434min,vw= 2796i,Tv 所有 T 标号中，T（ 2v）最小，令 P（ 2v）5第三步：
8、 2是刚得到的 P 标号，考察4424min,vw= 957525i,Tv n1所有 T 标号中，T（ 6）最小，令 P（ 6v）6第四步： 6v是刚得到的 P 标号，考察4464mi,vw= n9275565i,Tv 17767in,vPw m2所有 T 标号中，T（ 4） ，T （ 5）同时标号，令 P（ 4v） =P（ 5）78第五步：同各标号点相邻的未标号只有 7v5777,minwvPTv 1230至此：所有的 T 标号全部变为 P 标号，计算结束。故 1v至 7的最短路为 10。计算题答案二1. 解：（1） 12ax50zx236满足 1427x1,0（2）1500 2500 0
9、0 0Bcxb1x23x45x0 365 3 2 1 0 0 32.50 4x40 2 1 0 1 0 400 575 0 3 0 0 1 25z0 1500 2500 0 0 00 3x15 3 0 1 0 -2/3 50 415 2 0 0 1 -1/3 7.52500 2x25 0 1 0 0 1/3 _z-62500 1500 0 0 0 -2500/3 -1500 15 1 0 1/3 0 -2/9 _0 4x5 0 0 -2/3 1 1/9 _2500 225 0 1 0 0 1/3 _z-70000 0 0 -500 0 -500最优解 *(5,)Tx 最优目标值 = 70000
10、 元2. 解：此规划存在可行解 (,1x，其对偶规划123min4wyy满足： 9123y123,0对偶规划也存在可行解 (,)T，因此原规划存在最优解。3、解：可以作为初始方案。理由如下：（1）满足产销平衡（2）有 m+n-1 个数值格（3）不存在以数值格为顶点的避回路4.解： 5.解：此题目等价于求使各方案均完不成的概率最小的策略。把对第 k 个方案追加投资看着决策过程的第 k 个阶段，k1，2，3。kx-第 k 个阶段，可给第 k, k+1，3 个方案追加的投资额。u-对第 k 个方案的投资额kk kxxuD1,0且阶段指标函数 kkpC,这里的 kuxp,是表中已知的概率值。过程指标函
11、数 1, 413,13,minxffuxxfVVkkDukikk以上的 k1，2，3用逆序算法求解k3 时，3,i3CfDu得表：10最优策略： 1u1， 2=1, 3u=0 或1 0， 2=2, 3=0，至少有一个方案完成的最大概率为 1-0.135=0.865计算题答案三1. 解 分析：利用 7.4m 长的圆钢截成 2.9m , 2.1 m ,1.5m 的圆钢共有如下表所示的 8 中下料方案。方案毛胚/m方案1方案2方案3方案4方案5方案6方案7方案82.9 2 1 1 1 0 0 0 02.1 0 2 1 0 3 2 1 01.5 1 0 1 3 0 2 3 4合计 7.3 7.1 6.5 7.4 6.3 7.2 6.6 6.0剩余料头0.1 0.3 0.9 0 1.1 0.2 0.8 1.4设 1x， 2， 3， 4x， 5， 6， 7x， 8分别为上面 8 中方案下料的原材料根数。
