1、12012-2013 学年第 1 学期运筹学考试题答案要求:第一题必做（50 分） ，二三四题任选两题（每题各 25 分） 。一、 考虑下面线性规划问题0, 3322641.min112xtsxz ）（ ）（ ）（1） 用图解法求解该问题；（2） 写出该问题的标准形式；（3） 求出该问题的松弛变量和剩余变量的值；（4） 用单纯形法求解。【解答】(1)图中阴影部分为此线性规划问题的可行域,目标函数 ,即 是斜率为 的一族平行直线,由线性规划214xzzx144的性质知,其最值在可行域的顶点取得,将直线 沿其法线方向逐渐向上平移,直至21xA 点,A 点的坐标为( ),所以56,358634min
2、z此线性规划问题有唯一解 。21x，(2)给等式（2 ）左端添加剩余变量 ，给等式（3）左端添加松弛变量 ，则得到该问题的4x标准型为：0, 3,32264 1,3. 0max4311432xtsxxz ）（ ）（ ）（3）在上面标准型中令 ，得到剩余变量 =0，松弛变量 =0。52， 3x4x（4）先在上面标准型中约束条件(1)、 （2）中分别加入人工变量 , ，得到如下数学模56型， 0, 3322,64,3. 0max6543151 65432xxts Mxxxz ）（ ）（ ）（由此列出单纯形表逐步迭代，用大 M 法求解计算结果如下表所示。24 1 0 0 M M1x23x45x6b
3、iM 5【3】 1 0 0 1 0 3 1 M 6x4 3 1 0 0 1 6 3/20 41 2 0 1 0 0 3 3rj 7 M 4 4M1 M 0 0 0 9M4 1x1 1/3 0 0 1/3 0 1 3M 60 【5/3】 1 0 4/3 1 2 6/50 40 5/3 0 1 1/3 0 2 6/5rj(-z) 0 (5M+1)/3 M 0 (7M+4)/3 0 4-2M4 1x1 0 1/5 0 3/5 1/5 3/5 1/31 20 1 3/5 0 4/5 3/5 6/5 0 40 0 【1】 1 1 1 0 0rj(-z) 0 0 1/5 0 M+8/5 M-1/5 18/
4、54 1x1 0 0 1/5 2/5 0 3/51 20 1 0 3/5 1/5 0 6/50 30 0 1 1 1 1 0rj(-z) 0 0 0 1/5 M+7/5 M 18/5表中所有检验数 rj0,根据最优解定理，问题存在唯一的最优解 ，目标T),56,3(X函数的最优值 。518634maxz二、 试用表上作业法求解下列运输问题的最优解。产地 销地 B1 B2 B3 B4 产量A1 4 8 8 4 6A2 9 5 6 3 4A3 3 11 4 2 12销量 6 2 7 7【解答】：显然该问题是一个供需平衡问题，利用伏格法求出初始方案，如下表所示。B1 B2 B3 B4 产量A1 6
5、4 8 8 4 6A2 9 2 5 6 2 3 4CjxjXBCB3A3 0 3 11 7 4 5 2 12销量 6 2 7 7用位势法求出各非基变量（即空格）的检验数，如下表所示。B1 B2 B3 B4 iuA1 6 4 (3) 8 (3) 8 (1) 4 =01A2 (5) 9 2 5 (1) 6 2 3 =02A3 0 3 (7) 11 7 4 5 2 = 1ujv=41v=52v=53v34v因为所有非基变量的检验数均为非负的，故表中的解为最优解。按照此种方案调运，最小费用为：64+25+23+03+74+52= 78三、 用标号算法求解下图中从 V1 到各点的最短路【解答】：此为最短
6、路问题，权数为正，用 Dijksta 算法的计算步骤如下：1v23v45v67v89v101v初始值 T( ) 0 P( )+wij 0+2 0+8 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+1T( ) 2 8 4P( )+wij 2+6 2+ 2+1 2+ 2+ 2+ 2+ 2+ 2+2T( ) 8 3 P( )+wij 3+5 3+ 3+ 3+ 3+ 3+1 3+ 3+3T( ) 8 4 P( )+wij 4+ 4+ 4+6 4+ 4+7 4+ 4+4T( ) 8 10 11 P( )+wij 8+7 8+ 8+ 8+ 8+ 8+5T( ) 15 10 11 P( )+wij 10+
7、10+4 10+ 10+ 10+6T( ) 15 14 11 P( )+wij 11+ 11+ 11+ 11+97T( ) 15 14 20P( )+wij 14+ 14+1 14+8T( ) 15 15 11P( )+wij 15+49T( ) 19由上表的迭代过程可得： ， ， ， ， ， ， ， ， ， ， qS1v259v368v7410vd( , )=2,最短路：（ , ） ； d( , )=3,最短路：（ , , ） ；1v212 1525d( , )=4,最短路：（ , , , ） ；d( , )=10,最短路：（ , , , , ） ； 9v591v61v2596vd( , )
8、=8,最短路：（ , ）或（ , , ）或（ , , , ） ； 1v313231253d( , )=11,最短路：（ , , , , ） ；d( , )=14 最短路：（ , , , , , ） ；8v2598v71v2596v7d( , )=15,最短路：（ , , ）或（ , , , ）或（ , , , , ） ；1v41341234v12534d( , )=15,最短路：（ , , , , , , ） ； 0v259670d( , )=19,最短路：（ , , , , , , , ） ；1v1v1四、 某公司面对四种自然状态的三种备选行动方案收益表如下，假定状态概率未知，试分别用悲观准
9、则、等可能性准则、后悔值准则和乐观系数准则（=0.6 ）进行决策。 1 2 3 4状 态收益 值方 案5A1 15 8 0 6A2 4 14 8 3A3 1 4 10 12【解答】：（1）应用悲观准则： S 2 为最佳方案。36,1-max,12in4038,-i5max(2)应用等可能性准则： , 417)6085(4)1AE, , 9384()(2AE 427)(3，S 2 为最佳方案。)(27,91max2（3）应用后悔值准则：先求出后悔值矩阵 S 2 为最佳方案。 01492860B 14,8min0,14ax92,6min(4)应用乐观系数准则（ =0.6）：先计算各个方案的折中益损
10、值：，6.56.)(1 ）（AE，93402，.71.)(3 S 2 为最佳方案)(6.97,.6m2AEax已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中54,为松弛变量，问题的约束为 形式（共 8 分） 1x23x45x3x5/2 0 1/2 1 1/2 15/2 1 1/2 0 1/6 1/3jzc0 0 (1)写出原线性规划问题；（4 分）6(2)写出原问题的对偶问题；（3 分）(3)直接由上表写出对偶问题的最优解。 （1 分）四、用单纯形法解下列线性规划问题（16 分）321maxxZs. t. 3 x1 + x2 + x3 60x 1- x 2 +2 x 3 10
11、x 1+ x 2- x 3 20x 1, x 2 , x 3 0 五、求解下面运输问题。 （18 分） 某公司从三个产地 A1、A 2、A 3 将物品运往四个销地 B1、B 2、B 3、B 4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示：问：应如何调运，可使得总运输费最小?销 地 产 地1B 234产 量1A231089523674768252550销 量 15 20 30 35 100六、灵敏度分析（共 8 分）线性规划 max z = 10x1 + 6x2 + 4x3s.t. x1 + x2 + x3 10010x1 +4 x2 + 5 x3 6002x1 +2 x
12、2 + 6 x3 300x1 , x2 , x3 0的最优单纯形表如下：6 x2 200/3 0 5/6 1 5/3 1/6 010 x1 100/3 1 1/6 0 -2/3 1/6 00 x6 100 0 4 0 -2 0 1j 0 8/3 0 -10/3 2/3 0(1)C1 在何范围内变化，最优计划不变？(4 分)(2)b1 在什么范围内变化，最优基不变？ (4 分)7七、试建立一个动态规划模型。 （共 8 分）某工厂购进 100 台机器，准备生产 p1 , p2 两种产品。若生产产品 p1 ，每台机器每年可收入 45 万元，损坏率为 65%；若生产产品 p2 ，每台机器 每年可收入
13、35 万元，损坏率为 35%；估计三年后将有新 的机器出现，旧的机器将全部淘汰。试问每年应如何安排生产，使在三年内收入最多？八、求解对策问题。 （共 10 分）某种子商店希望订购一批种子。据已往经验，种子的销售量可能为 500，1000，1500 或 2000 公斤。假定每公斤种子的订购价为 6 元，销售价为 9 元，剩余种子的处理价为每公斤 3 元。要求：（1）建立损益矩阵；（3 分）（2）用悲观法决定该商店应订购的种子数。 （2 分）（3）建立后悔矩阵，并用后悔值法决定商店应订购的种子数。 （5 分）九、求下列网络计划图的各时间参数并找出关键问题和关键路径。 （8 分）工序代号工序时间最早
14、开工时间最早完工时间最晚开工时间最晚完工时间机动时间1-2 81-3 71-4 62-4 32-5 53-4 23-6 34-5 368123457563793427838十、用标号法求 V1 到 V6 的最短路。 （6 分）运筹学样卷（一）答案一、判断题。共计 10 分，每小题 1 分 10X X X X 二、建线性规划模型。共计 8 分（酌情扣分）解：用 321,x分别表示大豆、玉米、麦子的种植公顷数； 54,x分别表示奶牛和鸡的饲养数；4-6 74-7 45-7 96-7 83V4V5V3V1V2V6465664384976,x分别表示秋冬季和春夏季的劳动力（人日）数，则有 765432
15、1 202904603ma xxxZ )7,21(0 )(150243.50475 )(63201.47321 51jxxxxj 鸡 舍 限 制牛 栏 限 制劳 动 力 限 制劳 动 力 限 制资 金 限 制土 地 限 制三、对偶问题。共计 8 分解：（）原线性规划问题： 3216maxxz0,3521；4 分（）原问题的对偶规划问题为：2105inyw0,6321y； 3 分（）对偶规划问题的最优解为： )2,4(YT 。1 分四、单纯形表求解线性规划。共计 16 分解：引入松弛变量 x4、 x5、 x6， 标准化得， 321maZs. t. 3 x1 + x2 + x3+ x4 = 60x
16、 1- x 2 +2 x 3 + x5 = 10x 1+ x 2- x 3 + x6 = 0x 1, x 2 , x 3， x4、 x5、 x6， 03 分建初始单纯形表，进行迭代运算： 9 分2 -1 1 0 0 0CB Xb b x1 x2 x3 x4 x5 x60 x4 60 3 1 1 1 0 0 20100 x5 10 1 -1 2 0 1 0 10*0 x6 20 1 1 -1 0 0 1 201 0 2* -1 1 0 0 00 x4 30 0 4 -5 1 -3 0 7.52 x1 10 1 -1 2 0 1 0 -0 x6 10 0 2 -3 0 -1 1 5*2 20 0
17、1* -3 0 -2 00 x4 10 0 0 1 1 -1 -22 x1 15 1 0 0.5 0 0.5 0.5-1 x2 5 0 1 -1.5 0 -0.5 0.53 25 0 0 -1.5 0 -1.5 -0.5由最优单纯形表可知，原线性规划的最优解为： ( 15 , 5 , 0 )T 2 分最优值为： z*=25。2 分五、求解运输问题。共计 18 分解：（1）最小元素法：（也可以用其他方法，酌情给分）设 xij 为由 Ai 运往 Bj 的运量（i=1,2,3; j=1,2,3,4）,列表如下：销 地产 地 123B4产 量123 1520302555252550销 量 15 20 30 35 1003 分所以，基本的初始可行解为：x 14 =25； x22=20 ； x24 =5 ；X31 =15； x33 =30； x34=5 其余的 xij=0。 3 分（2）求最优调运方案：1 会求检验数，检验解的最优性：11=2；12=2；13=3；21=1； 23=5；32= - 13 分2 会求调整量进行调整：=5 2 分销 地产 地 1B234B产 量1 25 25
