《运筹学》课程考试试卷及答案

1、运筹学课程考试试卷一、填空题（共 10 分，每空 1 分）1、线性规划问题的3 个要素是：、和。2、单纯形法最优性检验和解的判别，当现有顶点对应的基可行解是最优解当线性规划问题有无穷多最优解，当线性规划问题存在无界解。4、连通图的是指：。5、树图指，最小树是。6、在产销平衡运输问题中，设产地为m 个，销地为n 个，运输问题的解中的基变量为。二、简答题简算题（共20分）1、已知线性规划问题，如下：max Z=7x1-2x+5 x321 x st14x1 3x 63x833x xi请写出其对偶问题。（10 分）2、已知整数规划问题：maxz 10 x15x23x4x9s.t.125x 2x85x

2、12x0,且x x 为整数1212在解除整数约束后的非整数最优解为(x1, x2)=(1, 1.5)2 个子问题（不需求解（10 分）利用单纯形法求解上述问题（14 分，单纯形表格已给出, 如若不够, 可自行添加）三、计算题（共 70 分）（吨）现有原料1A1，A2 B1，B2，（吨）现有原料原料B1B2B3（吨）A121030A202450每吨可得利润（万元）320.5在现有原料的条件下，应如何组织生产才能使该厂获利最大？（共 20 分）写出该线性规划问题的数学模型（4 分）将上面的数学模型化为标准形式（2 分）利用单纯形法求解上述问题（14 分，单纯形表格已给出, 如若不够, 可自行添加）

3、2、考虑下列运输问题：B1B2B3产量A16424A28575销量333 分）工作34ACD（10 分）工作机器ABCD4107527633344466346 个车间的道路如下图所示，已知每条道路的的距离，求沿部分道路6 （10 圈法或破圈法均可，但必须用图或文字描述详细步骤）V28VV28V41627533616VV355用Ford-Fulkerson标号算法求解下图中VsVt 的最大流量并标出网络的最小割集。（15 分）24vv24(4,3)(3,3)vs(5,1)(1,1)(3,0)(5,3)vt(2,1)v1(2,2)v3运筹学课程考试试卷参考答案一、填空题(共 10 分，每空 1 分

4、)1、决策变量目标函数约束条件2、所有的j 0所有的j0，某个非基变量xj-cjzj=0某个j 0 ，Pj相量所有分量aij04、在一个图中，若每一对顶点之间至少存在一条链，称这样的图为连通图5、无圈的连通图树枝总长最小的部分树6、m+n-1二、简答题。简算题。（共 20 分）解：（2分）1解：（2分）（82分）（82分）解：选择 x2 进行分支，得到以下 2 个子问题：253三、计算题（70分）1（20 分）(1) 写出该线性规划问题的数学模型（4 分）将上面的数学模型化为标准形式（2分）cj320.500CB0cj320.500CB00XBB3050 x1x2x3x4x5x4x5c -zj

5、j203122040.510001030 x1x51550c -zjj1000.520.5040.50.50-1.501030.5x1x31512.5c -zjj1000.50.50.250100.50-1.500.25-0.12532x1x22.525c -zjj100010-12-0.50.50-1.5-0.250.5-0.253214） 2（15分）法求初始解（7分）B1B2B3产量A16/142/34226A28/25/375238销量333215212校验数（7分）B1B2B3uiA116A238vj0-3-4当前调运方案：x11=1，x13=3，x21=2，x22=3，其余为零，为

6、最优方案。最优值为6*1+2*3+8*2+5*3=43（1 分）3、解：41075 2763 0631 0 0 16253 0321110541（1）（2）0011（3）3344133004663 3001061u 2u1 04 1 0531（4） 0 1u2 ）（5）11 132u3 2 03v 2 v 12v 0 v434 2 110 括号对应的 xij=1，最优分配方案。最有效率值 7+2+3+3=15（以上每步 2 分）4、解：方法 1：避圈法V1V1VV，VV为(V1。边(V1是最小树内的边。VV2V，VV2V，VV间最短边为(V2。边(V2是最小树内的边。VV3V，VV3V，VV间

7、最短边为(V3。边(V3是最小树内的边。VV5V，VV5V，VV间最短边为(V5。边(V5是最小树内的边。VV4V，VV4V，VV间最短边为(V4。边(V4是最小树（或：VV间最短边为(V5。边(V5是最小树内的边）V28V41V28V416V1275336V28V416V1275336V6V3V5V3V5V28V28V416V7125336V3V5V28V416V7125336V3V56V6V28VV28V416V7125336V3V5V28V416V7125336V3V5V66或沿最终图中红线标识的边架设电话网，电话线总距离最短 1+2+3+5+6=17。上述 5 个步骤（文字描述或绘图均

8、可）各的 2 分，若最终结论没有给出或给错扣 1分。方法 2：破圈法1）(1, 2, 3, 1，去掉最大的一边1, 3，得图 1V28VV28V4162753616VV35图 11 (2, 4, 3, 2，去掉最大的一边2, 4，得图 2V2V4V2V4162753616VV35图 22 (3, 4, 5, 3，去掉最大的一边3, 4，得图 3V2V4V2V416253616VV35图 33 (4, 5, 6, 4，去掉最大的一边4, 6，得4（去掉最大的一边（5, 64）.V2V412536V2V412536V2V41625316V3V5或V3V5图 4沿最终图中的边架设电话网，电话线总距离最短 1+2+3+5+6=17。4 个步骤（文字描述或绘图均可）2.5 1 分。5、解：24vv24(4,3)(3,3)vs(5,1)(1,1)(3,0)(5,3)vt(2,1)v1(2,2)v3标号法找增广链 vs-v1-v2-v4-v