设三个煤场A、B、C分别能供应煤12、14、10万吨,三个工厂X、Y、Z分别需要煤11、12、13万吨,从各煤场到各工厂运煤的单价(百元/吨)见下表方框内的数字。只要选择最优的运输方案,总的运输成本就能降到(__)百万元。

运输问题是运筹学中物资调运领域的经典优化问题,当供给总量与需求总量相等时,称为平衡运输问题,这是该类问题的基础研究场景。Vogel近似法(沃格尔法)是构造平衡运输问题初始可行解的高效方法,核心逻辑聚焦于机会成本:通过计算每行、每列的罚数——即该行/列次小运输单价与最小单价的差值,这个差值代表了若不选择当前行/列最优调运单价所产生的额外成本损失,随后优先选择罚数最高的行或列,在其对应最小单价的供需节点间优先分配最大可实现的运输量,重复该步骤直至完成全部供需匹配。相较于最小元素法仅关注当前最小单价,Vogel近似法通过考量机会成本,所得初始可行解往往更接近甚至直接就是最优解,能显著降低后续最优解调整的工作量。得到可行解后,可通过各调运量与对应运输单价的乘积之和计算总运输成本;若需验证解的最优性,可采用位势法,通过检验非基变量的检验数是否全部非负来判断。
本题考察的是运输问题的最小成本求解与最优性检验(Vogel近似法)。
供给为12、14、10,需求为11、12、13,总量相等,为标准平衡运输问题。
先用Vogel近似法构造初始可行解。行、列罚数比较后,优先在行A的最小单价1(A→Y)上分配,A供给12与Y需求12正好匹配,得到A→Y=12。划去 A行,Y 列。

余下行C罚数高,按最小单价3在C→X分配C的10万吨,得C→X=10,此时X尚缺1万吨。划去 C 行。

剩余只有B行可供,按最小单价2在B→X补足1万吨,得B→X=1。最后Z列尚需13万吨,由B行供给,按单价3得到B→Z=13。

得到可行方案:A→Y=12,C→X=10,B→X=1,B→Z=13。
按该方案的总运输成本(单位为百万元)为:B→X 1万吨×2=2,C→X 10万吨×3=30,A→Y 12万吨×1=12,B→Z 13万吨×3=39,总计2+30+12+39=83。
