运筹学5卷答案

课程名称:运筹学考试时间:年月日(第周星期)一（15分）解：则标准形式为：设对偶变量分别为y1，y2，y3，则对偶规划为：二（20分）解：（1）首先写出线性规划问题的标准形式（2分）Cj→23100θCBXBbx1x2x3x4x50x45111105/10x54-1[2]0014/2δj23100（2分）0x43[3/2]011-1/223x22-1/21001/2—δj5/2000-3/2（3分）2x12102/32/3-1/33x23011/31/31/3δj00-4/3-7/3-1/3（2分）此时，原问题得到最优解为X*=(2，3，0，0，0)T，maxZ＝13（1分）（2）若C1=4时，代入最终单纯型表：Cj→43100θCBXBbx1x2x3x4x54x12102/32/3-1/323x23011/31/3[1/3]3δj00-8/3-11/31/3（5分）4x151111020x5903111—δj0-1-3-40（3分）所以最优解改变，X*=（5，0，0，0，9）T，Z*=20（2分）三（15分）解：方法一：（1）用最小元素法求得初始解，并计算检验数如下：B1B2B3B4产量uiA182（0）（2）100A2（4）（2）218203A3（0）2010（-1）308销量8221218vj1232（初始方案5分，位势2分，检验数2分）（2）因为σ34<0，所以此方案不是最优方案，调整的新方案并计算新检验数：B1B2B3B4产量uiA182（1）（3）100A2（3）（1）128204A3（0）20（1）10308销量8221218vj1221（新方案3分，位势1分，检验数1分）因为所有σij≥0，所以此解为最优解，又因为有非基变量检验数δ31＝0，所以，该问题有多个最优解。其中一个最优解为：A1-B1：8，A1-B2：2，A2-B3：12，A2-B4：8，A3-B2：20，A3-B4：10；最小运费z=8×1+2×2+12×6+8×5+20×10+10×9＝414。（1分）方法二：用沃格尔法（方法略），初始解即为最优解。（评分标准：沃格尔法求得初始方案10分，检验数4分，结果1分）四（15分）解：矩阵变换（4分）矩阵变换（4分）（试指派4分，划直线1分）调整（2分）所以（1分）调整（2分）（再指派2分）此时最大值W=33+19+41+35+19=147（1分）V1V2V4V1V2V4V3V5V7V6V85544454（6分）最小树的权数为：5+5+5+4+4+4+4=31（1分）（2）增广链流量调整量V1→V2→V4→V6→V84（3分）V1→V3→V5→V7→V86（3分）V1VV1V2V4V3V5V7V6V8(5,0)(6,6)(7,6)(9,6)(4,0)(4,0)(6,6)(4,4)(5,4)(9,4)(7,0)(5,0)(4,4)最大流量图为：（3分）（3）最小割为：（3分）六（15分）：分54个阶段，k=1,2,3,4,5K=5时，（1分）K=4时，（1分）（1分）（1分）K=3时，（1分）（1分）（1分）K=2时，（1分）（1分）（1分）K=1时，（1分）