运筹学胡运权版第三章运输问题课后习题答案.doc
《运筹学胡运权版第三章运输问题课后习题答案.doc》由会员分享，可在线阅读，更多相关《运筹学胡运权版第三章运输问题课后习题答案.doc（27页珍藏版）》请在冰点文库上搜索。
P66：
8.某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点出售，各工厂A1，A2，A3的生产量、各销售点B1，B2，B3，B4的销售量（假定单位为t）以及各工厂到销售点的单位运价（元/t）示于下表中，问如何调运才能使总运费最小？
表
销地
产地
B1
B2
B3
B4
产量
A1
4
12
4
11
16
A2
2
10
3
9
10
A3
8
5
11
6
22
销量
8
14
12
14
48
解：
一、该运输问题的数学模型为：
可以证明：
约束矩阵的秩为r（A）=6.从而基变量的个数为6.
二、给出运输问题的初始可行解（初始调运方案）
1.最小元素法
思想：
优先满足运价（或运距）最小的供销业务。
销地
产地
B1
B2
B3
B4
产量
A1
4
12
4
11
16
A2
8
2
10
3
9
2
8
10
A3
8
5
11
6
22
销量
8
14
12
14
48
①
销地
产地
B1
B2
B3
B4
产量
A1
4
12
4
11
16
A2
8
2
10
2
3
9
②
8
10
A3
8
5
11
6
22
销量
①
8
14
10
14
48
销地
产地
B1
B2
B3
B4
产量
A1
4
12
10
4
10
11
166
A2
8
2
10
2
3
9
②
8
10
A3
8
5
11
6
22
销量
①
8
14
③
10
14
48
销地
产地
B1
B2
B3
B4
产量
A1
4
12
10
4
10
11
166
A2
8
2
10
2
3
9
②
8
10
A3
8
14
5
11
14
6
228
销量
①
8
④
14
③
10
14
48
销地
产地
B1
B2
B3
B4
产量
A1
4
12
10
4
10
11
166
A2
8
2
10
2
3
9
②
8
10
A3
8
14
5
11
8
14
6
⑤
220
销量
①
8
④
14
③
10
146
48
销地
产地
B1
B2
B3
B4
产量
A1
4
12
10
4
6
10
11
⑥
160
A2
8
2
10
2
3
9
②
8
100
A3
8
14
5
11
8
14
6
⑤
220
销量
①
8
④
14
③
10
⑥
140
48
此时得到一个初始调运方案（初始可行解）：
其余（非基）变量全等于零。
此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6）.
总运费为（目标函数值）
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
8
10
1
A3
8
14
5
11
14
6
22
1→2
销量
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
0
10
②
1
A3
8
14
5
11
8
14
6
22
1
销量
8
14
12
14
48
列差额
2
①
5
1
3
销地
产地
B1
B2
B3
B4
产量
行差额
A1
4
12
4
11
16
0
A2
8
2
10
3
8
9
0
102
②
1
A3
8
14
5
11
8
14
6
22
1
销量
8
14
12
14
48
列差额
③
2
①
5
1
3
销地
产地
B1
B2
B3
B4
产量
行差额
A1
4
12
12
4
12
11
164
⑤
7
A2
8
2
10
3
2
8
9
0
100
②
6
A3
8
14
5
11
8
14
6
22
1
销量
8
14
12
14
48
列差额
③
2
①
5
④
1
3
销地
产地
B1
B2
B3
B4
产量
行差额
A1
4
12
12
4
4
12
11
160
⑤
7
A2
8
2
10
3
2
8
9
0
100
②
6
A3
8
14
5
11
8
14
6
22
1
销量
8
14
12
140
48
列差额
③
2
①
5
④
1
⑥
3
此时得到一个初始调运方案（初始可行解）：
x13=12,x14=4,x21=8,x24=2,x32=14,x34=8
其余（非基）变量全等于零。
此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6）。
总运费为（目标函数值）：
三、解的最优性检验
⒈闭回路法（以下的闭回路都是顺时针方向）
看非基变量的检验数是否满足：
（1）首先对用最小元素法所确定的初始基本可行解进行检验。
参见前面的计算结果，可知非基变量分别为：
x11，x12，x22，x24，x31，x33。
销地
产地
B1
B2
B3
B4
产量
A1
X11
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
σ11=C11+C23-（C13+C21）=4+3–（4+2）=1
销地
产地
B1
B2
B3
B4
产量
A1
4
X12
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
σ12=C12+C34-（C14+C32）=12+6–（11+5）=2
销地
产地
B1
B2
B3
B4
产量
A1
4
12
10
4
6
11
16
A2
8
2
X22
10
2
3
9
10
A3
8
14
5
11
8
6
22
销量
8
14
12
14
48
σ22=C22+C13+C34-（C23+C14+C32）=10+4+6–（3+11+5）=20–19=1
销地
产地
B1
B2
B3
B4
产量
A1
X11
4
12
10
4
6
11
16
A2
8
2
10
2
3
X24
9
10
A3
8
14
5
11
8
6
22
销量
8
14
12
14
48
σ24=C24+C13-（C14+C23）=9+4–（11+3）=-1
销地
产地
B1
B2
B3
B4
产量
A1
4
12
10
4
6
11
16
A2
8
2
10
2
3
9
10
A3
X31
8
14
5
11
8
6
22
销量
8
14
12
14
48
σ31=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
11
16
A2
8
2
10
2
3
9
10
A3
8
14
5
X33
11
8
6
22
销量
8
14
12
14
48
σ33=C33+C14-（C13+C34）=11+11–（4+6）=12
由于σ24=C24+C13-（C14+C23）=9+4–（11+3）=-1<0，所以当前方案不是最优方案。
（2）然后对用伏格尔法所确定的初始基本可行解进行检验。
参见前面的计算结果，可知非基变量分别为：
x11，x12，x22，x23，x31，x33。
（伏格尔法）
销地
产地
B1
B2
B3
B4
产量
A1
X11
4
12
12
4
4
11
16
A2
8
2
10
3
2
9
10
A3
8
14
5
11
8
6
22
销量
8
14
12
14
48
σ11=C11+C24-（C14+C21）=4+9–（11+2）=0
销地
产地
B1
B2
B3
B4
产量
A1
4
X12
12
12
4
4
11
16
A2
8
2
10
3
2
9
10
A3
8
14
5
11
8
6
22
销量
8
14
12
14
48
σ12=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
10
3
2
9
10
A3
8
14
5
11
8
6
22
销量
8
14
12
14
48
σ22=C22+C34-（C24+C32）=10+6–（9+5）=16–14=2
销地
产地
B1
B2
B3
B4
产量
A1
4
12
12
4
4
11
16
A2
8
2
10
X23
3
2
9
10
A3
8
14
5
11
8
6
22
销量
8
14
12
14
48
σ23=C23+C14-（C13+C24）=3+11–（4+9）=14-13=1
销地
产地
B1
B2
B3
B4
产量
A1
4
12
12
4
4
11
16
A2
8
2
10
3
2
9
10
A3
X31
8
14
5
11
8
6
22
销量
8
14
12
14
48
σ31=C31+C24-（C21+C34）=8+9–（2+6）=17-8=9
销地
产地
B1
B2
B3
B4
产量
A1
4
12
12
4
4
11
16
A2
8
2
10
3
2
9
10
A3
8
14
5
X33
11
8
6
22
销量
8
14
12
14
48
σ33=C33+C14-（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
令自由变量u1=0，将其代入方程组，得：
u1=0，v3=4，v4=11，u3=-5，v2=10，u2=-1，v1=3，将其代入非基变量检验数：
σij=Cij-（ui+vj），得：
σ11=C11-（u1+v1）=4–（0+3）=1
σ12=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
σ33=C33-（u3+v3）=11–（-5+4）=12
与闭回路法计算的结果相同。
（2）然后对用伏格尔法所确定的初始基本可行解进行检验。
参见前面的计算结果，可知基变量分别为：
x13，x14，x21，x24，x32，x34。
销地
产地
B1
B2
B3
B4
产量
A1
4
12
12
4
4
11
16
A2
8
2
10
3
2
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+v4=c24=9
u3+v2=c32=5
u3+v4=c34=6
令自由变量u1=0，将其代入方程组，得：
u1=0，v3=4，v4=11，u3=-5，v2=10，u2=-2，v1=4，将其代入非基变量检验数：
σij=Cij-（ui+vj），得：
σ11=C11-（u1+v1）=4–（0+4）=0
σ12=C12-（u1+v2）=12–（0+10）=2
σ22=C22-（u2+v2）=10–（-2+10）=2
σ23=C23-（u2+v3）=3–（-2+4）=-1
σ31=C31-（u3+v1）=8–（-5+4）=9
σ33=C33-（u3+v3）=11–（-5+4）=12
与闭回路法计算的结果相同。
四、解的改进（用闭回路法调整）
在使用最小元素法求得的初始方案中，由于σ24<0，说明当前方案不是最优，需要改进或调整。
见表1中非基变量x24所在的闭回路，调整量为ε=min{2,6}=2。
调整过程见表2：
表1
销地
产地
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
表2
销地
产地
B1
B2
B3
B4
产量
A1
4
12
10+2
4
6-2
11
16
A2
8
2
10
2-2
3
0+2
9
10
A3
8
14
5
11
8
6
22
表3
销地
产地
B1
B2
B3
B4
产量
A1
4
12
12
4
4
11
16
A2
8
2
10
3
2
9
10
A3
8
14
5
11
8
6
22
调整后的结果如表3所示，此结果正好与使用伏格尔法求得的结果相同，因此最优性检验过程同前，由于非基变量的检验系数都大于等于零，因此该方案是最优方案，最优解为：
x13=12，x14=4，x21=8，x24=2，x32=14，x34=8。
将最优解代入到目标函数中，得总运费为（目标函数值）：
P66：
9.
解：
首先列出这一问题的产销平衡表，见表1。
表1
销地
产地
B1
B2
B3
B4
产量
A1
A2
A3
3
1
7
11
9
4
3
2
10
10
8
5
7
4
9
销量
3
6
5
6
一、该运输问题的数学模型为：
可以证明：
约束矩阵的秩为r（A）=6.从而基变量的个数为6.
二、给出运输问题的初始可行解（初始调运方案）
1.最小元素法
第1步，从表1中找出最小运价为1，表示应先将A2的产品供应B1。
在表中A2和B1的交叉格处填上3，得表2。
将表2中的B1列运价划去，得表3
表2
销地
产地
B1
B2
B3
B4
产量
A1
A2
A3
3
31
7
11
9
4
3
2
10
10
8
5
7
41
9
销量
3
6
5
6
①
表3
销地
产地
B1
B2
B3
B4
产量
A1
A2
A3
3
31
7
11
9
4
3
2
10
10
8
5
7
41
9
销量
3
6
5
6
第2步，在表3未划去的元素中再找出最小运价为2，确定A2多余的1t物资供应B3。
得表4。
将表4的A2行运价划去，得表5
表4
销地
产地
B1
B2
B3
B4
产量
A1
A2
A3
3
31
7
11
9
4
3
2
10
10
8
5
7
41
9
①
销量
3
6
5
6
表5
销地
产地
B1
B2
B3
B4
产量
A1
A2
A3
3
31
7
11
9
4
3
12
10
10
8
5
②
7
410
9
①
销量
3
6
54
6
第3步，在表5未划去的元素中再找出最小运价为3，确定A1的4t物资供应B3。
得表6。
将表6的B3列运价划去，得表7。
表
升级会员 