运筹学 试卷及答案 卷4

课程名称:运筹学课程名称:运筹学题号一二三四五六七八九十总分得分评分人一、（10分）写出下面线性规划的标准形式和对偶规划：二、（20分）用单纯形法求解；并考虑若目标函数的系数变为C=(3,0.5)T后，最优解的变化情况。三、（15分）运用表上作业法求解下列运输问题，表格中间的数字为运价。产销甲乙丙丁产量A413610B23616C37518销量4938学院：专业：学号：姓名：装订线四、（15分）有5个工人，要指派去做5项工作，每人做各项工作的能力见下表。应如何指派，才能使总的得分最大？业务工人J1J2J3J4J5S1S2S3S4S51.50.51.00.71.20.51.101.20.90.31.31.300.800.80.51.30.91.21.00.60.81.2五、（25分）下图为一网络图，边上数字为边的容量或者长度：求从顶点1到顶点8的最大流（10分）；用Dijkstra算法求解从顶点1到顶点8最短路（8分）；画出最小生成树（7分）。VV1V2V4V3V5V7V6V85671446459754在如下的网络中，从起点A到终点G分六个阶段，每个阶段各有若干条可选择的道路，每条道路的长度如下图所示。试确定从A点到G点的最短路线。（15分）《运筹学》参考答案及评分细则（15分）写出下面线性规划的标准形式和对偶规划则标准形式为：设对偶变量分别为y1，y2，y3，则对偶规划为：解：首先写出线性规划问题的标准形式2分Cj→32000θCBXBbx1x2x3x4x50x341110040x42-11010-0x518[6]20013δj32000（2分）0x310[2/3]10-1/63/20x4504/3011/615/43x1311/3001/69δj0100-1/2（3分）2x23/2013/20-1/40x4300-211/23x15/210-1/201/4δj00-3/20-1/4（3分）此时，原问题得到最优解为X*=(5/2，3/2，0，3，0)T，maxZ＝21/2（2分）当目标函数系数变为（3，0.5）时，把新系数带入最终单纯型表：Cj→30.5000θCBXBbx1x2x3x4x50.5x23/201[3/2]0-1/410x4300-211/2-3x15/210-1/201/4-δj003/40-5/8（3分）0x3102/310-1/60x4504/3011/63x1311/3001/6δj0-1/200-1/2（3分）所以新的最优解为X*=(3，0，1，5，0)T，maxZ＝9（2分）三、解：方法一：（1）用最小元素法求得初始解，并计算检验数如下：甲乙丙丁产量uiA（3）91（7）100B（-1）（0）（1）662C4（4）2282销量493824vj113-1（初始方案5分，位势2分，检验数（括号中数字）2分）（2）因为σ24<0，所以此方案不是最优方案，调整的新方案并计算新检验数：甲乙丙丁产量uiA（4）91（7）100B4（0）（1）262C（1）（4）2682销量493824vj013-1（新方案3分，位势1分，检验数1分）因为所有σij≥0，所以此解为最优解，又因为有非基变量检验数δ31＝0，所以该问题有多个最优解。其中一个最优解为：A-乙：9，A-丙：1，B-甲：4，B-丁：2，C-丙：2，C-丁：6；最小运费z=9×1+1×3+4×2+2×1+2×5+6×1＝38。（1分）方法二：用沃格尔法（方法略），初始解即为最优解。（评分标准：沃格尔法求得初始方案10分，检验数4分，结果1分）四、解：首先变成最小化指派问题。B=(1.5-Cij)5×5（2分）行减（2分）行减（2分）试指派4分，划直线2分调整（2分）调整（2分）再指派2分即：S1→J1，S2→J2，S3→J3，S4→J4，S5→J5此时总得分W=1.5+1.1+1.3+1.3+1.2=6.4（1分）五、解：（1）求最大流：增广链流量调整量V1→V2→V4→V6→V84V1→V3→V5→V7→V81（4分）所以最大流量为：4+1=5（1分）最大流量图为：VV1V2V4V3V5V7V6V8(5,0)(6,1)(7,1)(1,1)(4,0)(4,0)(6,1)(4,4)(5,4)(9,4)(7,0)(5,0)(4,4)（5分）（2）求最短路。标号如下图66(8,8)(14,14)V1V2V4V3V5V7V6V8571446459754(4,4)(9,9)(13,13)(6,6)(17,15)（6分）所以V1到V8的最短路长为15。路径为：V1→V2→V5→V7→V8。（2分）（3）求最小树。最小树如下图：VV1V2V4V3V5V7V6V85144454（6分）最小树的权数为：5+5+4+4+4+4+1=27（1分）六、解：逆序法标号(13)(13)(16)(18)(13)(10)(9)(12)(8)(