最新运筹学胡运权版第三章运输问题课后习题答案.docx
- 文档编号:1934746
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:55
- 大小:153.69KB
最新运筹学胡运权版第三章运输问题课后习题答案.docx
《最新运筹学胡运权版第三章运输问题课后习题答案.docx》由会员分享,可在线阅读,更多相关《最新运筹学胡运权版第三章运输问题课后习题答案.docx(55页珍藏版)》请在冰点文库上搜索。
最新运筹学胡运权版第三章运输问题课后习题答案
P66:
8•某部门有3个生产同类产品的工厂(产地),生产的产品由4个销售点出售,各工厂Ai,A,A3的生产量、各销售点Bi,B2,B3,B4的销售量(假定单位为t)以及各工厂到销售点的单位运价(元/t)示于下表中,问如何调运才能使总运费最小?
解:
一、该运输问题的数学模型为:
34
minz八'、•q乂耳=4x1112x124x1311x142x21
i4j4
10x223x239x248x315x3211x336X34
%
+X12
+X13
+X14
=16
X21
+X22
+X23
+X24
=10
X31
+X32
+X33
+X34
=22
X11
+X21
+X31
=8
X12
+X22
+X32
=14
X13
+X23
+X33
=12
X14
+X24
+X34
=14
Xij
X0,
i=1.
2,3;
j=1,2,3,4
X11
XI2
X13
X14
X21
X22
X23
X24
X31
X32
X33
X34
(1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
I
1
1
1
1
1
I
1
1
1丿
7旳2
可以证明
约束矩阵的秩为
r(A)=
:
6.
从而基变量的个数为
6.
二、给出运输问题的初始可行解(初始调运方案)
1.最小元素法
思想:
优先满足运价(或运距)最小的供销业务。
销地
产地
Bi
—
1
1
-
B2
B3
B4
产量
Ai
4
12
4
11
16
A2
8
|2
10
3
9
10
82
~厂
1
1
A3
;8
5
11
6
22
1
1
1
销量
8
14
12
14
48
销地
产地
—=1
Bi
B4
产量
Ai
4
;12
10
1
11
166
10
L
A
2-
J
1-0-
1
9-
_1_n
A2
8
10
9-
10
8
2
A3
8
14
5
8
6
220
~1
「'
14
销量
8
―
14
10
146
48
③
④
①
⑤
②
产地
销地
B1
Bl
1
1
B3!
1
1
1
B4
1
产量
A1
4
12
4
11
160
—
1
10
1
1
6
1
1
1
10
⑥
2_
1
3
-J9
T\2
8
TlU
3
9
8
1UXJ
II
2
1
I
1
1
②
A3
8
14
—
1
1
5
11
8
|6
220
1
・■■丄■■■■
1
1
I
i
«
14
⑤
销量
8
14-
10
14;0
48
①
④
⑥T
1
此时得到一个初始调运方案(初始可行解):
X13=10,X14=6,X21=8,X23=2,X32=14,X34=8,
其余(非基)变量全等于零。
此解满足所有约束条件,且基变量(非零变量)的个数为6(等
于m+n-仁3+4-仁6).
总运费为(目标函数值)
34
z-二CjXj
ij=1
=104611822314586=246
2.伏格尔(Vogel)法
伏格尔法的基本思想:
运输表中各行各列的最小运价与次小运价之差值(罚数)应尽可能地
小。
或者说:
优先供应罚数最大行(或列)中最小运费的方格,以避免将运量分配到该行(或该列)次小运距的方格中。
销地
产地
B1
B2
B3
B4
产量
行差额
A1
4
12
4
11
16
0
A2
2
10
3
9
10
1
A3
8
5
11
6
22
1
销量
8
14
12
14
48
列差额
2
5
1
3
销地
产地
B1
B2
B3
B4
产量
行差额
A1
4
—
12
4
11
16
0
A2
2
10
3
9
10
1
A3
8
14
~1
5
11
6
228
14
1~2
1
销量
8
14
12
14
48
列差额
2
5
1
3
①
产地
销地
B1
1
B2;
1
B3
B4
产量
行差额
A1
4
12
4
11
16
0
~1~
1
1
A2
2
10
3
9
10
1
1
1
1
A3
8
J5
11
6
0
T4_
1
1
1
8
22
14
'~1
销量
8
14'
1
12
14
48
列差额
2
51
1
3
①
②
销地
产地
Bi丨
||
II
I
B2
B3丨
ii
ii
ii
B4
产量
行差额
⑤
Ai
4
12
12
4
11
164
12
7
1
1
1
1 A2 2 I10 9 100 6 「8 2 8 ② 1II 1 ~1~ 1 1 I A3 ~1~ 8 14 5 11 6 “0 r 1 1 1 r~ r 11 * 8 22 14 1 销量 8! 1 14 12! L 14 48 列差额 2! 1 5 1! 1 3 ③①④ IlI 销地 产地 B1 B2 B3 B4 产量 行差额 A1 1 4 12 12 4 1 1 160 12 7 A 4 2 10 9 1Q0. 6 8 2 8 A3 5 —1 6 CC0 L 14 r\ ] r" 为 22 14 1 销量 8 14 12 14( 48 列差额 2 5 — 1 3 ③ ① ④ ⑥ 此时得到一个初始调运方案(初始可行解): X13=12,X14=4,X21=8,X24=2,X32=14,X34=8 其余(非基)变量全等于零。 此解满足所有约束条件,且基变量(非零变量)的个数为6(等 于m+n-仁3+4-仁6)。 总运费为(目标函数值): 34 Z=、「、「CjXj=124411822914586=244三、解的最优性检验 1•闭回路法(以下的闭回路都是顺时针方向) 看非基变量的检验数是否满足: Gj_0. (1)首先对用最小元素法所确定的初始基本可行解进行检验。 参见前面的计算结果,可知 非基变量分别为: Xii,X12,X22,X24,X31,X33。 产地 销地 B1 B2 B3 B4 产量 A1 X11 4 12 10 4 6 11 16 厂 A2 1 81 2 10 1 II 2 3 9 10 1 A3 8 14 5 11 8 6 22 销量 8 14 12 14 48 5i=C11+C23-(C13+C21)=4+3—4+2)=1 销地 产地 B1 B2 B3 B4 产量 A1 4 X12厂. 12 一10- 4 6 1 1 11 16 A2 8 2 1r 1 1 10 2 3 1 1 1 1 9 10 A3 8 14- <_C L1斗 」 8 6 22 销量 8 14 12 14 48 (712=Cl2+C34-(Cl4+C32)=12+6-11+5)=2 产地 销地 B1 B2 B3 B4 产量 A1 4 12 10 4 6 1 11 16 |! |j A2 8 2 X22. 一10-- 2 3 1|| 9 10 1 1 1 1 A3 8 f 141 5 ———^―= 一一— 11 1 __|| 8 6 22 销量 8 14 12 14 48 C22=C22+Cl3+C34-(C23+C14+C32)=10+4+6-(3+11+5)=20T9=1 销地 产地 Bi B2 B3 B4 产量 Ai X11 4 12 10 6 -11 16 T 1 1 1 A2 8 2 10 2 13 X24 ! 9 10 l_ A3 8 14 5 11 8 6 22 销量 8 14 12 14 48 C24=C24+C13-(C14+C23)=9+4—11+3)=-1 销地 产地 B1 B2 B3 B4 产量 A1 4 12 10 厂4 6 -|11 16 1 li 1 1 A2 8 2 10 2 ri- 3 II 19 10 T 1 1 1 1 A3 X31 8! 14 5 11 8 I6 22 1 jj 销量 8 14 12 14 48 c31=C31+C14+C23-(C34+C13+C21)=8+11+3—(6+4+2)=22-12=10 销地 产地 B1 B2 B3 B4 产量 A1 4 12 10 厂.4一 6 -111 16 1 L 1 A2 8 2 10 2 ! 3 ! 9 10 厂 1 1 1 A3 8 14 5 X33 V十- 8 」6 22 销量 8 14 12 14 48 C33=C33+C14-(C13+C34)=11+11—4+6)=12 由于024=C24+C13-(C14+C23)=9+4-11+3)=-1<0,所以当前方案不是最优方案。 (2)然后对用伏格尔法所确定的初始基本可行解进行检验。 参见前面的计算结果,可知非 基变量分别为: Xu,X12,X22,X23,X31,X33。 (伏格尔法) 产地 销地 Bi B2 B3 B4 产量 Ai X11 4 12 12 4 4 11 16 L A2 8' 2 10 3 2 : 9 10 H -■ -—— 1 A3 8 14 5 11 8 6 22 销量 8 14 12 14 48 (711=C11+C24-(Cl4+C21)=4+9-11+2)=0 销地 产地 B1 B2 B3 B4 产量 A1 4 X12 7 12 12 4 4 11 16 — 1 A2 8 2 1 1 1 1 10 3 2 ! 9 10 1 1 A3 8 14丄 5— '——— 11 8 」6 22 销量 8 14 12 14 48 52=C12+C34-(C14+C31)=12+6-11+5)=2 销地 产地 B1 B2 B3 B4 产量 A1 4 12 12 4 4 11 16 A2 8 2 X22 —— 2 9 10 1i I|| A3 8 14 ;5 11 8 ;6 1 22 L.■ 1 销量 8 14 12 14 48 C22=C22+C34-(C24+C32)=10+6-(9+5)=16T4=2 产地 销地 B1 B2 B3 B4 产量 A1 4 12 12 4 亠4_ 11 1 16 1 1 ! 1 A2 8 2 10 X23 : 3 2_ : 9 10 —1 A3 8 14 5 11 8 6 22 销量 8 14 12 14 48 C23=C23+C14-(C13+C24)=3+11_(4+9)=14-13=1 销地 产地 B1 B2 B3 B4 产量 A1 4 12 12 4 4 11 16 A 8| f 1 2 10 r-3 2 9 10 1i A3 X31: 8 14 5 - 11 8 6 22 销量 8 14 12 14 48 o3i=C31+C24-(C21+C34)=8+9—(2+6)=17-8=9 销地 产地 B1 B2 B3 B4 产量 A1 4 12 12 4 4 11 ―I 16 1L A2 8 2 10 : 3 2 9 10 1] A3 8 14 5 X33 ! .11 8 6 22 销量 8 14 12 14 48 C33=C33+Ci4-(C13+C34)=11+11_(4+6)=22-10=12 由于所有非基变量的检验数都大于零,说明当前方案是最优方案,最优解为: X11=12,X14=4,X21=8,X24=2,X32=14,X34=8。 2位势法 (1)首先对用最小元素法所确定的初始基本可行解进行检验。 参见前面的计算结果,可知基变量分别为: X13,X14,X21,X23,X32,X34。 产地 销地 B1 B2 B3 B4 产量 A1 4 12 10 4 6 11 16 A2 8 2 10 2 3 9 10 A3 8 14 5 11 8 6 22 销量 8 14 12 14 48 构造方程组: 广U1+V3=C13=4 U1+V4=C14=11 U2+V1=C21=2 U2+V3=C23=3 U3+V2=C32=5 U3+V4=C34=6 令自由变量ui=0,将其代入方程组,得: U1=0,V3=4,V4=11,U3=-5,V2=10,U2=-1,Vi=3,将其代入非基变量检验数: qj=Cij-(Ui+Vj),得: oi1=C11-(U1+V1)=4-(0+3)=1 Of2=C12-(U1+V2)=12-(0+10)=2 (22=C22-(U2+V2)=10-(-1+10)=1 (24=C24-(U2+V4)=9一(-1+11)=-1 (31=C31-(U3+V1)=8_(-5+3)=10 C33=C33-(U3+V3)=11-(-5+4)=12 与闭回路法计算的结果相同。 (2)然后对用伏格尔法所确定的初始基本可行解进行检验。 参见前面的计算结果,可知基 变量分别为: x13,x14,x21,x24,x32,x34o 产地 7地 B1 B2 B3 B4 产量 A1 4 12 12 4 4 11 16 A2 8 2 10 3 2 9 10 A 8 14 5 11 8 6 22 销量 8 14 12 14 48 构造方程组: 厂U1+V3=C13=4 U1+V4=C14=11 U2+V1=C21=2 ]U2+V4=C24=9 U3+V2=C32=5 LU3+V4=C34=6 令自由变量U1=0,将其代入方程组,得: U1=0,V3=4,V4=11,U3=-5,V2=10,U2=-2,V1=4,将其代入非基变量检验数: (j=Cij-(Ui+Vj),得: (5f1=C11-(U1+V1)=4-(0+4)=0 Ot2=C12-(U1+V2)=12-(0+10)=2 (2=C22-(U2+V2)=10-(-2+10)=2 (3=C23-(U2+V3)=3-(-2+4)=-1 (1=C31-(U3+V1)=8-(-5+4)=9 C83=C33-(U3+V3)=11-(-5+4)=12 与闭回路法计算的结果相同。 四、解的改进(用闭回路法调整) 在使用最小元素法求得的初始方案中,由于024<0,说明当前方案不是最优,需要改进或调 整。 见表1中非基变量X24所在的闭回路,调整量为£=min{2,6}=2。 调整过程见表2: 表1 销地 产地 B1 B2 B3 B4 产量 A1 4 12 10 厂
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最新 运筹学 胡运权版 第三 运输 问题 课后 习题 答案
![提示](https://static.bingdoc.com/images/bang_tan.gif)