北京科技大学远程与成人教育学院 《 运筹学 》作业一2014.3
姓名 学号 专业 教学点 题号 得分
1、用图解法求解下列线性规划问题（15分）
maxZ?x1?x2?2x1- x2? 6?3x1+ 2x2?12 ?s.t.??x1? 3??x1,x2?0一 二 三 四 五 总分
2、用单纯形法求解以下线性规划问题（20分）
maxZ?x2?2x3?x1? 3x2? 4x3? 12 ?s.t.?2x2- x3? 12?x1,x2,x3? 0?解：
3、已知某运输问题如下（单位：百元/吨）：
单位运价 销地 B1 产地 A1 A2 A3 需求量（吨）
求：（1）使总运费最小的调运方案和最小运费。（20分）
（2）请以该问题的初始调运方案为例，说明非基变量检验数
的经济含义。（20分）
2 10 7 4 2 8 6 3 2 5 6 4 1 4 8 4 3 6 6 B2 B3 B4 供应量（吨）
5、求下图中从A到E的最短路线和最短路长（图中每条边上的数字为该条边的长度）。（25分）
6 7 B1 C1 9 6 4 3 C2 D1 3 5 A 6 6 7 D2 E 6 5 B2 5 7 C3 9
《 运筹学 》作业一参考答案2014.3
解
6A
C O 3 B 4
2、用单纯形法求解以下线性规划问题（20分）
maxZ?x2?2x3解：
?x1? 3x2? 4x3? 12 ?s.t.?2x2- x3 ?X4 ?12?x1,x2,x3,X4? 0?b' 12 12 X1 1 0 0 X2 3 2 1 X3 4 -1 -2 X4 0 1 0 初始单纯形表： XB X1 X4 -Z
迭代正确10分
XB X2 X4 -Z b' 4 4 X1 1/3 -2/3 -1/3 X2 1 0 0 X3 4/3 -11/3 -10/3 X4 0 1 0
最优解为：x1=0 x2=4 x3=0 x4=4 （2分）
最大值为z=4 （1分）
3、已知某运输问题如下（单位：百元/吨）：
单位运价 销地 B1 产地 A1 A2 A3 需求量（吨）
求：（1）使总运费最小的调运方案和最小运费。（20分）
（3）请以该问题的初始调运方案为例，说明非基变量检验数
的经济含义。（20分）
2 10 1 7 3 4 2 8 6 3 3 2 5 4 6 4 1 3 4 1 8 4 3 6 6 B2 2 8 6 3 B3 2 5 6 4 B4 供应量（吨） 1 4 8 4 3 6 6 2 10 7 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
所以检验数为：?11??5；?12?5；?13?0；?22??1；?34?7；?33?4 所以初始方案不是最优的
5、求下图中从A到E的最短路线和最短路长（图中每条边上的数字为该条边的长度）。（25分）
6
C1 7
9 B1 D1 3 6 5 4 6 A E C2 6 3
5 6 5 B D 227
7
9 C3
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.