运筹学作业及答案1..doc

北京科技大学远程与成人教育学院 《 运筹学 》作业一2014.3 姓名 学号 专业 教学点 题号 一 二 三 四 五 总分 得分 1、用图解法求解下列线性规划问题（15分） 2、用单纯形法求解以下线性规划问题（20分） 解： 3、已知某运输问题如下（单位：百元/吨）： 单位运价 销地 产地 B1 B2 B3 B4 供应量（吨） A1 2 2 2 1 3 A2 10 8 5 4 6 A3 7 6 6 8 6 需求量（吨） 4 3 4 4 求：（1）使总运费最小的调运方案和最小运费。（20分） 请以该问题的初始调运方案为例，说明非基变量检验数的经济含义。（20分） 5、求下图中从A到E的最短路线和最短路长（图中每条边上的数字为该条边的长度）。（25分） 《 运筹学 》作业一参考答案2014.3 解 6A C O 3 B 4 2、用单纯形法求解以下线性规划问题（20分） 解： 初始单纯形表： XB b X1 X2 X3 X4 X1 12 1 3 4 0 X4 12 0 2 -1 1 -Z 0 1 -2 0 迭代正确10分 XB b X1 X2 X3 X4 X2 4 1/3 1 4/3 0 X4 4 -2/3 0 -11/3 1 -Z -1/3 0 -10/3 0 最优解为：x1=0 x2=4 x3=0 x4=4 （2分） 最大值为z=4 （1分） 3、已知某运输问题如下（单位：百元/吨）： 单位运价 销地 产地 B1 B2 B3 B4 供应量（吨） A1 2 2 2 1 3 A2 10 8 5 4 6 A3 7 6 6 8 6 需求量（吨） 4 3 4 4 求：（1）使总运费最小的调运方案和最小运费。（20分） 请以该问题的初始调运方案为例，说明非基变量检验数的经济含义。（20分） 2 2 2 1 3 3 10 1 8 5 4 4 1 6 7 3 6 3 6 8 6 4 3 4 4 用最小元素法得出初始运输方案为： X14=3； x21=1； x23=4； x24=1； x31=3；x32=3 由位势法求检验数：U1+v4=1 u2+v1=10 u2+v3=5 u2+v4=4 U3+v1=7 u3+v2=6 令u2=0得v1=10 v3=5 v4=4 u3=-3 v2=9 u1= -3 所以检验数为：；；；；； 所以初始方案不是最优的 5、求下图中从A到E的最短路线和最短路长（图中每条边上的数字为该条边的长度）。（25分） 5、解： （假设A、B1、B2、C1、C2、C3、D1、D2、E分别为1、2、3、4、5、6、7、8、9） A(0，S)（即1） S12=0+5=5，S13=0+6=6 min=5 S24=5+7=12, S25=5+6=11, S26=5+4=9, S34=6+3=9, S35=6+5=11, S36=6+7=13 min=9 S47=9+6=15, S48=9+9=18, S67=9+7=16, S68=9+9=18, min=15 S79=15+3=18 最短路线为A—B2---C1---D1---E。最短路长为18.  A B2 B1 C3 C2 C1 D1 D2 E 5 6 7 6 4 3 5 7 6 9 6 6 7 9 3 5 A B2 B1 C3 C2 C1 D1 D2 E 5 6 7 6 4 3 5 7 6 9 6 6 7 9 3 5