运筹学作业及答案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
显示全部