运筹学试卷B参考答案.doc

运筹学试卷（B）参考答案一、不定项选择题(每小题3分，共9分)1下列说法正确的是（ A C D ）A、图解法同单纯行法虽然求解的形式不同，但从几何上解释，两者是一致的；B、线性规划问题的每一个基解对应可行域的一个顶点；C、如果线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点；D、线性规划问题的任意可行解都可以用全部基可行解的线形组合来表示。2下列说法正确的是（ A ）A、线性规划问题是目标规划问题的一种特殊形式；B、正偏差变量应取正值，负偏差变量应取负值；C、目标规划模型中，应同时包含绝对约束与目标约束；D、当目标规划问题模型中存在的约束条件，则该约束为绝对约束。3下列说法错误的是（ A ）A、整数规划解的目标函数值一般优于其相应的线性规划问题解的目标函数值；B、用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值；C、指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解；D、求解0-1规划的隐枚举法是分枝定界法的特例。二、判断题（每小题2分，共10分）1若线性规划原问题有无穷多最优解，则其对偶问题也具有无穷多最优解。（）2如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。 （）3表上作业法实质上就是求解运输问题的单纯形法。 （）4用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常可任取其中一个作为下界值，再进行比较剪枝。 （）5动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已做出的决策。 （）三(20分)、考虑下列线性规划：1(7分)、化标准形式，求最优解；标准形式 - (3分)-551300020-113100901241001-5513001320/3-1/31/311/31070/346/32/30-10/30-2/32/30-13/30520-11310010160-2-4100-2-50用单纯形方法解: 最优解-(3分)最优值 100-(1分)2(4分)、写出最优基和它的逆；-(2分)最优基-(2分)3(2分)、求此线性规划的对偶问题的最优解；-(2分)4(2分)、试求在什么范围内，此线性规划的最优解不变；-(2分)5(5分)、若变为45，最优解及最优值是什么。-(2分)cj-551300CBXBbx1x2x3x4x55x245-113100x5-90160-2-4100-2-505x2-902310-53/213x345-8012-1/2-1600-1-10x418-23/5-1/501-3/1013x396/52/5101/10-103/5-1/500-13/10 -(2分)-(1分)四(10分)、已知线性规划问题：解：1(5分)、写出对偶问题；对偶问题是： -(5分)2(5分)、已知原问题的最优解为，求对偶问题的最优解。，将的值代入约束条件，得约束条件为严格等式，约束条件为严格不等式，设对偶问题的最优解为，由互补松弛性得 -(3分)且，有求解后得到，故对偶问题的最优解为, -(2分)五(13分)、已知运输问题的运价表及初始方案如下： BjCijAiB1B2B3B4BjXijAiB1B2B3B4A1512411A110616A221039A28210A385116A3148228141214要求：1（8分）、求最佳调运方案； 2（5分）、如B2的销量增加到20，试把问题化为平衡的运输问题。 解：1.初始方案的检验数表为： （ij） 3104110(2)(2)411-12(1)3(-1)-5(10)5(12)6-(3分)因，故应引入,在原方案中标出调整回路，得调整 -(1分)调整后得方案二： Xij BjAiB1B2B3B4aiA112416A28210A314822bj8141214-(2分)方案二的检验数表为： （ij） 4104110（1）（2）41122（2）（1）95（9）5（12）6故方案二为最优方案。-(2分)2.这时ai=48,bj=54,假想一产地A4，其产量a4bj-ai6，则相应的模型化为： Cij BjAi B1B2B3B4aiA151241116A22103910A38511622A400006bj820121454-(5分)六(10分)、用图解法解下列目标规划模型。解：C 100 -(5分) B40 GHA IE15 DFO 先考虑优先因子的目标的实现，在目标函数中要求实现,从图中可得：可以满足和。 此时在区域OAGFO内取值。 -(1分) 再考虑优先因子的目标的实现，在目标函数中要求实现从图中可得：可以满足。 此时在区域OAHIFO内取值。 -(1分) 再考虑优先因子的目标的实现，在目标函数中要求实现从图中可得：可以满足。 此时在线段HI内取值。 -(1分) 再考虑优先因子的目标的实现。因为的权系数大于的权系数，故先考虑取最小。从图中可以看出，可以满足。此时得到H点为满意解，坐标为(25,15)。 -(2分)七(12分)、有甲、乙、丙、丁四个人，要分别指派他们完成A、B、C、D不同的工作，每人做各项工作所消耗的时间如下表所示：ABCD甲791012乙13121517丙15161415丁11121516问：应该如何指派，才能使总的消耗时间为最少。解： -(2分) -(4分) -(2分)最优解矩阵为： -(2分)即 ：甲做C ，乙做B ，丙做D，丁做A. 总花费的时间：48 -(2分)八(8分)、用动态规划方法解下列非线性规划问题（只建模,不求解）：解 解决这一类静态规划问题，需要人为地赋予时间概念，从而将该问题转化为多阶段决策过程。按问题的变量个数划分阶段，把它看作一个三阶段决策问题，k=1，2，3-(1分)设状态变量为s1，s2，s3，s4并记s15 -(1分)取问题中的变量x1，x2，x3为决策变量 -(1分)状态转移方程为：s3=x3s3+x2=s2s2+x1=s15 -(1分)允许决策集合为：x3=s30x2s20x1s1 -(1分)各阶段指标函数为：，各指标函数以乘积方式结合，最优指标函数fk(sk)表示从第k阶段初始状态sk出发到第3阶段所得到的最大值，则动态规划基本方程为： -(3分)九(8分)、计算下图所示的从 A 到 E 的最短路问题