1 2 3 4 5 0 0 1 0 1 2 0 1 2 0 1 2 3 1 2 0.5 3 1.5 0 4 2.5 1 5 3.5 2 0.5 6 4.5 3 1.5 0 0+0=0 0+1.5=1.5 1.5+0=1.5 0+3=3 1.5+1.5=3 3+0=3 0+3=3 1.5+1.5=3 3+0=3 0+4.5=4.5 1.5+3=4.5 3+1.5=4.5 4.5+0=4.5 0+6=6 1.5+4.5=6 3+3=6 4.5+1.5=6 6+0=6 0 1.5 3 3 4.5 6 0 1 2 3 4 6
第三阶段：计算装入第3种2吨货物的价值，见下表3。 表3 第三阶段价值计算表 车辆可利用载重量假设 第3种2吨货物装入件数 装入第3种2吨货物后的车辆剩余载重量 W-W3X3 0 1 2 0 3 1 4 2 0 5 3 1 6 4 2 0 装入第3种货物的价值与剩余所装第2种货物的价值之和 P3X3+F2(W-W2X2) 0+0=0 0+0=0 0+1.5=1.5 2+0=2 0+3=3 2+0=2 0+3=3 2+1.5=3.5 4+0=4 0+4.5=4.5 2+3=5 4+0=4 0+6=6 2+3+5 4+1.5=5.5 6+0=6 6 5 4 3 装入第3种货物X3件时，其最大价值 F3(W) 0 0 2 W 0 1 2 3 4 5 6 X3 0 0 0 1 0 1 0 1 2 0 1 2 0 1 2 3
10
第四阶段：计算装入第4种3吨货物的价值，见下表4。 表4 第四阶段价值计算表 车辆可利用载重量假设 第4种3吨货物装入件数 装入第4种3吨货物后的车辆剩余载重量 W-W4X4 0 1 2 3 0 4 1 5 2 6 3 0 装入第4种货物的价值与剩余所装第3种货物的价值之和 P4X4+F3(W-W3X3) 0+0=0 0+0=0 0+2=2 0+3=3 3+0=3 0+4=4 3+0=3 0+5=5 3+2=5 0+6=6 3+3+6 6+0=6 6 5 4 装入第4种货物X4件时，其最大价值 F4(W) 0 0 2 3 W 0 1 2 3 4 5 6 X4 0 0 0 0 1 0 1 0 1 0 1 2 寻求最优解方案与计算顺序相反，由第四阶段向第一阶段进行。 Ⅰ.在第四阶段计算表中
价值（本例为载重量）最大值F4(W)=6,对应三组数据，其中一组X4=0，一组X4=1，另一组X4=2。
当X4=1时，即第四种3吨货物装入一件。表中第3列数字表示其余种类货物的装载量。当X4=1时，其它三种货物装载重量为3吨。
Ⅱ.在第三阶段计算表中
查W=3时装载重量最大值F3(W)=3对应X3=0，即其余两类货物装入重量为3吨。 Ⅲ.在第二阶段计算表中
查W=3，F2(W)=3,对应三组数据：X2=0、X2=1或X2=2，其余量为3、1.5或0，即第一种货物装入量为3吨、1.5吨、或0吨。
Ⅳ.在第一阶段计算表中 当W=3时，对应X1=2， 当W=1.5时，对应X1=1, 当W=0时，对应X1=0。
得到三组最优解
① X1=0，X2=2,X3=0，X4=1， ② X1=1，X2=1,X3=0，X4=1, ③ X1=2，X2=0，X3=0，X4=1，
如果在四阶段计算表中取X4=0，则余项W=W4X4=6；
在第三阶段计算表中，查W=6一栏，F3（W）=6对应X3=0或X3=3，即其它两种货物装入量为6吨或0吨；
在第二阶段计算表中，当W=6时，F2（W）=6对应X2=0、X2=1、X2=2、X2=3、X2=4，其余量为6、4.5、3、1.5、0，即第一种货物装入量为6吨、4.5吨、3吨、1.5吨、0吨。在第一阶段计算表中，
11
当W=6时，对应X1=4， 当W=4.5时，对应X1=3， 当W=3时，对应X1=2， 当W=1.5时，对应X1=1， 当W=0时，对应X1=0； 因此又总共得到六组最优解
④ X1=0，X2=0，X3=3，X4=0； ⑤ X1=0,X2=4，X3=0，X4=0； ⑥ X1=1，X2=3，X3=0,X4=0； ⑦ X1=2，X2=2，X3=0，X4=0； ⑧ X1=3，X2=1，X3=0,X4=0； ⑨ X1=4，X2=0，X3=0，X4=0；
若在第四阶段计算表中取X4=2，则余项W-W4X4=0；又得到一组最优解
⑩ X1=0，X2=0，X3=0，X4=2；
这十组解，都是装载重量达到汽车的最大载重量值6吨。
（3）中国邮路问题优化计算过程
湘潭某超市门店分布线路图1-1
基建营店 熙春路店 板塘店 金湘潭店 广云店 V1 3 V8 4 V7 白石店 解放路店 宝塔店 4 步步高广场店 3 4.3 V2 1.5 V9 2.5 V6 钢城店 步行街店 岳塘店 东方红店 配送中心 2.8 2.2 3.8 金侨店 V3 1 V4 2.5 V5
第一步：确定一个可行方案。由于任何一个线路中，奇点个数必为偶数个，因此以配对，又
因为图是连通的，故每一对奇点之间都有一条链，我们把所有边作为重复边加到图中去图中必无奇点，既得出第一个可行方案。
12
如图1-2：
V1 V8 V7
V2 V9 V6
V3 V4 V5 于是得V2，V4，V6，V8四个奇点。我们分别将之分成两对，比如V2，V4成对，V6，V8成对。V2，V4的链有好几条，任取一条，如V2-V1-V8-V7-V6-V5-V4，作重复边加入图中。同理，将V6，V8之间的链：V8-V1-V2-V3-V4-V5-V6，取重复边加到图中去，在这个图中，没有奇点，故又称欧拉图。得一个可行方案。重复边权为： 2D12+D23+2D45+2D56+D67+2D18 =8+2.8+1+5+7.6+4.3+4+6 =38.7公里 如图所示：1-3
V1 V8 V7 V2 V9 V3 V4 V5
第二步：调整可行方案，使重复边总长度下降：
从图中可看出：[V1-V2]有两条重复边，如去掉，图仍没奇点，剩下的重复边还有
V6 13
一个可行方案。而总长度却有所下降。[V1-V8]，[V4-V5]，[V5-V6]，
同理得到图1-4
V1 V8 V7
V2 V9 V6 V3 V4 V5
方案调整的标准有两个：
(1)在最优方案中，图的每一边上最多有一条重复边，无奇点，图1-2，本例图中无奇点，重复边总权下降到12.1
(2)在最优方案中，图中每一圈的重复边的总权长不大于该圈总权的一半，在题中，V2-V3-V4-V9-V2的总长度是7.5公里。但V2-V3-V4总权为3.8大于一半。因此，作为一次调整。以V2-V9，V9-V4上的重复边代替V2-V3，V3-V4上的重复边。 如图1-5所示
V1 V8 V7
V2 V9 V6
V3 V4 V5
在查V1-V2-V9-V6-V7-V8-V1圈中的重复边总权为8.8，而圈长为15.3大于圈长的一半。因此做一次调整以V8-V9，V9-V6，上的重复边代替V8-V7，V7-V6，
14