物流运筹学试卷运筹学7卷答案.docx

4x + 七 + 2/ + X；-芍=2s.<x1 + X2 - 3 巧一巧 + X： + %=142X1 + 2/ +巧 + 2 芍2 芍xfi=2石，2，鼻，名，8，&5，6 分分分分分H 1 1 1 1课程名称：运筹学一（10分）解：令巧=-X3,X4二与一芍，x；，x；No则标准形式为：maxz'=3X-4x2-2巧-5/+5芍设对偶变量分别为y,y2,y三,则对偶规划为:max69=-2y1+14>,2+2yi4,+丫2-2%-3.-yl+y2+24s,t.2%+3%一为一2一弘一为+2=5M无约束,必,y3之0，二（15分）解：首先变成最小化指派问题。B="5436054343521行减32452436=>302254522分O32401534O11分0.汾0.吩0.5分0.汾2分(7-Cij)5×53分6O-54250"1O列减323OO14=>3O1O43O1分O312O53_4OO43_三（20分）解：此问题可分为三个阶段，分别在地区A、B、C设销售点，k=l,2,3;决策变量iik：表示在地区k可设置的销售点数；状态变量sk:表示k阶段出可在第k到第c个地区设置销售点的个数；状态转移方程：Sk+1=Sk-Uk表示：4分因为此问题为离散确定性多阶段决策，所以可用图表示。图形：8分此问题求总利润最大，相当于求状态Sl到状态S4的最长路，采用逆序法标号标号：6分则最长路径为：4210,最长路为47。即地区A设2个销售点，地区B设1个销售点，地区C设1个销售点。结果：2分四（15分）解：由最小元素法得初始运输方案如下表所示：（初始解5分，检验数4分）甲乙丙产量UiA564(-4)8(4)856OB(O)16412441168212C1686116(16)24774销量7210241Vj4124因为。hV0,所以该方案不是最优方案。进行调整：（新方案3分，检验数2分）甲乙丙产量UjA(4)4568(8)856OB(O)16412441168216C728516(16)24778销量7210241VjO8O因为0,所以该方案是最优方案。总运费为2744。（1分）五（20分）解：（1）首先写出线性规划问题的标准形式mas,t.<Xz=2x1÷3x2+X3%+勺+与+七=5（2分）-xi+2x2+x5=4x1,x2,x3,x4,X5OCj23100CbXbbXiX2X3X4X5OX45111105/1OX54-120014/223100（2分）OX433/2011-1/223X22-1/21001/25/2000-3/2（3分）2Xl21O2/32/3-1/33X23011/31/31/3¾00-4/3-7/3-1/3（2分）此时，原问题得到最1（2）当右边向量b:=B=D代入最终单纯型表继2尤解为X*=（2,3,C为（3,7尸时,3-13Y3'J/31/3X7实迭代：）,O,O）,maxZ=13（1分）（-3八、=（5分）U3jGT23100CbXb1）XiX2X3X4XS2Xi-1/3102/32/3-133X210/3O11/31/31/3O0-4/3-7/3-1/3（2分）OX51-30-2-213X2311110-10-2-30（2分）所以X*=（0,3,0,0,1）,Z*=9（1分）六（20分）解：（1）用DijkSIra算法求顶点Vl到顶点V7的最短路，标号见下表：由图知V到V7的最短路长为12,路径为ViV2V5-V7（2分）（2）求最大流:增广链流量调整量(1)V1V4V6V74(2)VV2V3V5V73(3)VV2V5V71(4分)(4)VV3V6V73(5)VV4V3V6V71(6)VjV4V3V5V71(7)ViV4V3V6V5V71所以最大流量为：4+3+1+3+1+1+1=14（1分）（3分）最大流量图为:（4分）最小割为：（S,S）=（匕，彩），。2，%），（”，匕），。4，口3），（以，丫6）