第二部分线性规划应用 第二章运输问题和指派问题（书第三章，§5.5) 运输问题和指派问题都是具有特殊结构的线性规划问题，除了可直接用单纯形法求解外，我们可以 根据其特征构造更简易有效的方法进行求解。本章将介绍求解运输问题的表上作业法和求解指派问题的 匈牙利算法。 §2.1运输问题的数学模型 2.1.1运输问题 设某种物质有m个产地A1,…,Am,产量分别为a1,…,am,有n个销地B1,…,Bn,销量分别为b1,…,bn。 己知A到B的运价为c,则应如何安排运输方案，使在满足各销点的销量的前提下，使总运费最小。 设由4，到，B,的运输量为x,则可建立如下运输模型： l 1 SIt. ,≤a,i=l,m =1 (2.1.1) ∑=j=ln xg≥0，i=1,…,m,j=1,…,n 其中a,20,i=1,…,m,b,之0，j=1,…,n, a-立和b-产多分别为21游总产量和8箱量.eL山的可 行解记作x={x}。我们将(2.11)中数据用如下运输表表示： B1 … B … Bn ai A C11 Clj CIn a A Cil Ci Cin ai Am Cml C网 Cmn am ∑a, b b bn ∑b, 表2.1.1运输问题(2.1.1)的运输表 如有如下运输表（右上方为运价）。1 第二部分 线性规划应用 第二章 运输问题和指派问题（书第三章，§5.5） 运输问题和指派问题都是具有特殊结构的线性规划问题，除了可直接用单纯形法求解外，我们可以 根据其特征构造更简易有效的方法进行求解。本章将介绍求解运输问题的表上作业法和求解指派问题的 匈牙利算法。 §2．1 运输问题的数学模型 2．1．1 运输问题 设某种物质有 m 个产地 A1,…,Am，产量分别为 a1,…,am，有 n 个销地 B1,…,Bn，销量分别为 b1,…,bn。 已知 Ai 到 Bj的运价为 cij，则应如何安排运输方案，使在满足各销点的销量的前提下，使总运费最小。 设由 Ai 到,Bj的运输量为 xij，则可建立如下运输模型： 1 1 1 1 min . . , 1, , , 1, , 0, 1, , , 1, , m n ij ij i j n ij i j m ij j i ij z cx st x a i m x bj n x i mj n = = = = = ≤ = = = ≥= = ∑∑ ∑ ∑ " " " " (2.1.1) 其中 0, 1, , , 0, 1, , i j a i mb j n ≥= ≥ = " " ， 1 m i i a a = = ∑ 和 1 n j j b b = = ∑ 分别为(2.1.1)的总产量和总销量。(2.1.1)的可 行解记作 { }ij x = x 。我们将(2.1.1)中数据用如下运输表表示： B1 … Bj … Bn ai A1 c11 c1j c1n a1 ┆ Ai ci1 cij cin ai ┆ Am cm1 cmj cmn am bj b1 bj bn i ∑a j ∑b 表 2.1.1 运输问题(2.1.1)的运输表 如有如下运输表(右上方为运价)