c13+c14=10+3+3=16, 与最大流的流量相等。 评分标准: (1)、(2)、(3)、图1、图2各3分。若算法步骤和图不完整,可适当扣分。
八、(15分)解: 闭回路法求得表中基可行解的非基变量的检验数,填入表1中空格的左下角。 ∵?11<0,∴表中基可行解不是最优解。
表1 销地 产地 B1 -2 4 B2 5 B3 3 5 3 B4 2 7 产量 60 75 90 A1 A2 A3 需求量 10 2 50 8 2 40 0 3 8 35 8 7 4 0 70 45 70 20 70 40 用闭回路法对表中的解进行调整,闭回路为:(x11)—x12—x22—x21—(x11),调整量为min{x12,x21}=10,调整后得到一个新的基可行解,如表2。
表2 销地 产地 B1 B2 5 B3 3 5 B4 2 7 产量 60 75 90 A1 A2 A3 需求量 4 10 2 3 2 6 7 50 6 2 30 2 3 8 2 45 4 70 45 70 20 70 40 再用闭回路法求得表2中基可行解的非基变量的检验数,填入表2中空格的左下角。∵??ij>0,∴表2中的解即为问题的最优解。
最小总运费z=4?10+2?50+3?30+2?45+2?70+4?20=540。
评分标准: 两个表中的基可行解的检验和解的调整各5分。个别数据错误酌情扣分。