5行 Zj1 0 20M 0 24M 0 22M 18.5－22M 0 0 0 0 0 －M M 21M 第三乘0 第四行乘M 6行 Zj2 7行 16－C-Zj1-Zj2 20-20M 24M 0 M －M S－21M X2入基 进行第一次迭代后的单纯形表为 1行 Cj 20 16 18.5 0 X2 X3 0 M S 注释 2行 基变量 X1 316 X2 0.2 行 4行 5行 6行 7行
M A Zj1 Zj2 15.2 3.2 15.2M K1 K2 A 1 0.6 0.2 0 0 0.5 0.5/0.2=2.5 0 7.6 -4.8 －1 1 9 9/15.2,A出基 第三乘16 第四行乘M 9.6 8 16 3.2 0 0 0 7.6M 8.9－7.6M －4.8 －M M 1.6 M 0 9M C-Zj1-Zj2 16.8-15.2M 0 S－8－X1入基
与此对应的最低成本为：1364/76＝17.95元。
第6章 运输问题
习题详解
1．将正文中图6-14到图6-15的调整补齐，试看图6-15是不是该运输问题的最优方案。
解：用修正分配法来计算各格的改进指数。教材中图6-14的R值和K值如下表： Ri Kj K1=40 到 A段 K2=80 B段 K3=160 K4=-60 C段 虚设的 采石厂生产能力 D段 0 (供应量) 76 R1=0 从 W厂 40 80 80 72 4 R2=160 X厂 160 240 160 0 41 41 R3=80 Y厂 80 160 240 0 82 77 工程段 需求量 72 57 102 41 20 20 235 235 对应于其6个空格的改进指数为 IWC=CWC – R1 – K3 = 80-0-160=-80, IWD = CWD –R1 –K4 =0-0+60=6, IXA = CXA –R2 –K1 =160-160-40=-40, IXC =CXC –R2 –K3 =160-160-160=-160, IXD =CXD –R2 –K4=0-160+60=-100, IYA =CYA –R3
–K1=80-80-40=-40。在6个空格中，以XC空格的改进指数-160为绝对值最大的负改进指数，所以我们选定XC为调整格。空格XC的闭合改进路线为：LXC =+XC-YC+YB-XB。在改进路线中，选负号格的最小运量41为调整运量。经过调整后的第二个运输方案及R值和K值如下表。 Ri Kj K1=40 到 A段 K2=80 K3=160 K4=-60 B段 C段 虚设的 采石厂生产能力 D段 0 (供应量) 76 R1=0 从 W厂 40 80 80 72 4 R2=160 X厂 160 240 160 0 82 R3=80 Y厂 80 82 0 160 240 16 41 102 41 77 工程段 需求量 72 20 20 235 235 在6个空格中，以XC空格的改进指数-160为绝对值最大的负改进指数，所以我们选定XC为调整格。空格XC的闭合改进路线为：LXC =+XC-YC+YB-XB。在改进路线中，选负号格的最小运量41为调整运量。经过调整后的第二个运输方案及R值和K值如下表。
Ri R1=0 R2=160 R3=80 Kj 到 从 W厂 X厂 Y厂 K4=-60 虚设的DA段 B段 C段 段 80 0 40 80 72 4 160 240 160 0 41 41 80 160 240 0 57 20 K1=40 K2=80 K3=0 采石厂生产能力（供应量） 76 82 77 工程段需 235 72 102 41 20 求量 235 对应于其6个空格的改进指数为： IWC＝CWC－R1－K3＝80－0－0＝80； IWD＝CWD－R1－K4＝0－0＋60＝60；
IXA＝CXA－R2－K1＝160－160－40＝－40； IXD＝CXD－R2－K4＝0－160＋60＝－100； IYA＝CYA－R3－K4＝80－80－40＝－40； IYC＝CYC－R3－K2＝240－80－0＝160。 在6个空格中，以XD空格的改进指数-100为绝对值最大的负改进指数，所以我们选定XD为调整格。空格XD的闭合改进路线为：LXD=+XD-YD+YB-XB。在改进路线中，选负号格的最小运量20为调整运量。经过调整后的第三个运输方案及R值和K值如下表。 Kj K1=40 K2=80 K3=0 K4=-160 到 虚设的D采石厂生产能Ri A段 B段 C段 从 段 力（供应量） 80 0 40 80 R1=0 W厂 76 72 4 160 240 160 0 R2=160 X厂 82 21 41 20 80 160 240 0 R3=80 Y厂 77 77 工程段需 235 72 102 41 20 求量 235 对应于其6个空格的改进指数为： IWC＝CWC－R1－K3＝80－0－0＝80； IWD＝CWD－R1－K4＝0－0＋160＝160； IXA＝CXA－R2－K1＝160－160－40＝－40； IYD＝CYD－R3－K4＝0－80＋160＝80； IYA＝CYA－R3－K1＝80－80－40＝－40； IYC＝CYC－R3－K3＝240－80－0＝160。
在6个空格中，以YA空格的改进指数-40为绝对值最大的负改进指数，所以我们选定YA为调整格。空格YA的闭合改进路线为：LYA=+YA-WA+WB-YB。在改进路线中，选负号格的最小运量72为调整运量。经过调整后的第四个运输方案及R值和K值如下表(即教材中的图6-15)。 Kj K1=40 K2=80 K3=0 K4=-160 到 虚设的D采石厂生产能Ri A段 B段 C段 从 段 力（供应量） 80 0 40 80 R1=0 W厂 76 76 160 240 160 0 R2=160 X厂 82 21 41 20 240 0 80 160 R3=80 Y厂 77 72 5 工程段需 235 72 102 41 20 求量 235 对应于其6个空格的改进指数为： IWA＝CWA－R1－K1＝40－0－0＝40； IWC＝CWC－R1－K3＝80－0-0＝80； IWD＝CWD－R1－K4＝0-0+160＝160； IXA＝CXA－R2－K1＝160-160-0＝0； IYC＝CYC－R3－K3＝240－80－0＝160； IYD＝CYD－R3－K4＝0－80+160＝80。
所有空格的改进指数均大于或等于0，表明此图已是最优的运输方案，这个最优的运输方案的总运费为：
S优=76?80+21?240+41?160+20?0+72?80+5?160=24240。
2. 将正文中图6-17到图6-18的调整过程补齐，试看运算的结果是否导致图6-18的最优运输方案。 解：用修正分配法来计算各格的改进指数，教材中图6-17的R值和K值如下表：
Kj K1=40 K2=120 K3=40 到 采石厂生产能Ri A段 B段 C段 从 力（供应量） 80 40 80 R1=0 W厂 56 56 R2=120 X厂 160 240 160 82 R3=40 R4=-200 Y厂 虚设的Z厂 工程段需求量 26 80 0 56 160 240 46 31 0 0 30 102 61 77 30 245 245 82
对应于其6个空格的改进指数为： IWB＝CWB－R1－K2＝80－0－120＝-40； IWC＝CWC－R1－K3＝80－0-200＝-120； IXC＝CXC－R2-K3＝160-120-200＝-160； IYA＝CYA－R3－K1＝80-40-40＝0； IZA＝CZA－R4－K1＝0-(-200)-40＝160； IZB＝CZB－R4－K2＝0－(-200)-120＝80。
在6个空格中，以XC空格的改进指数-160为绝对值最大的负改进指数，所以我们选定XC为调整格。空格XC的闭合改进路线为：LXC=+XC-YC+YB-XB。在改进路线中，选负号格的最小运量31为调整运量。经过调整后的第二个运输方案及R值和K值如下表：
Kj K1=40 K2=120 K3=40 到 采石厂生产能Ri A段 B段 C段 从 力（供应量） 80 40 80 R1=0 W厂 56 56 160 240 160 R2=120 X厂 82 26 25 31 80 160 240 R3=40 Y厂 77 77 0 0 0 虚设的Z R4=-40 30 厂 30 工程段需 245 82 102 61 求量 245
对应于其6个空格的改进指数为 IWB＝CWB－R1－K2＝80－0－120＝-40； IWC＝CWC－R1－K3＝80－0-40＝40； IYA＝CYA－R2-K1＝80-40-40＝0；
IYC＝CYC－R3－K3＝240-40-40＝200； IZA＝CZA－R4－K1＝0-(-40)-40＝0； IZB＝CZB－R4－K2＝0－(-40)-120＝-80。
在6个空格中，以ZB空格的改进指数-80为绝对值最大的负改进指数，所以我们选定ZB为调整格。空格ZB的闭合改进路线为：LZB=+ZB-XB+XC-ZC。