运筹学讲义 §5.1运输问题 运输问题(TP, Transportation Problem):从m个发点A1,A2…,An往n个收点B1,B2…,B 运输货物,有关数据如下图所示: A B 单位运费 供应量a4 B;|b,需求量 发点 收点 其中>a=>b(供需平衡) 或见如下的供需-运费表 单位收点 运费 12 供应量 m2……C 需求量 6. b 问:应如何组织运输,才能既满足供需关系,又使得运费最省? 解:令x=从发点A运往收点B的货物的数量,i=1,2,…,m,J=12,…,n,则可建立如下线 性规划模型
运 筹 学 讲 义 1 §5.1 运输问题 运输问题（TP，Transportation Problem）：从 m 个发点 A A Am , , , 1 2 往 n 个收点 B B Bn , , , 1 2 运输货物，有关数据如下图所示： 其中 = = = n j j m i ai b 1 1 （供需平衡）. 或见如下的供需-运费表： 问：应如何组织运输，才能既满足供需关系，又使得运费最省？ 解：令 ij x = 从发点 Ai 运往收点 Bj 的货物的数量， i = 1,2, ,m, j = 1,2, ,n ，则可建立如下线 性规划模型
运筹学讲义 min a.i=1.2..m b,j=1,2,…,n x20.=1,2,…,m=1,2,…n 其中∑a=∑∑x=∑∑x=∑b,a,b∈z,=12…mj=12…n 运输问题有供需平衡型(∑a=∑b)运输问题和供需不平衡型(∑a≠∑b)运输问题 其中,供需不平衡又可分为供大于需(∑a1>∑b)和需大于供(∑a1<∑b)两种本章将主 要介绍供需平衡型运输问题 ( cost matrix,费用矩阵),d=(a12a2…,an,b,b2,…,bn) 0:…:00 0!1 0 0:00 0 m+2|01 0:01 0::01 0 m+n00 l:00 00 其中e=(1,1…,1,07=(0,0.0.…,0)
运 筹 学 讲 义 2 = = = = = = = = = = = x i m j n x b j n st x a i m f c x TP ij m i ij j i n j ij m i n j ij ij 0, 1,2, , ; 1,2, , , 1,2, , . . , 1,2, , min ( ) : 1 1 1 1 ， 其中 = = = = = = = = = n j j n j m i ij m i n j ij m i ai x x b 1 1 1 1 1 1 ， ai ,bj Z ,i =1,2, ,m; j =1,2, ,n + .▍ 运输问题有供需平衡型（ = = = n j j m i ai b 1 1 ）运输问题和供需不平衡型（ = = n j j m i ai b 1 1 ）运输问题. 其中，供需不平衡又可分为供大于需（ = = n j j m i ai b 1 1 ）和需大于供（ = = n j j m i ai b 1 1 ）两种.本章将主 要介绍供需平衡型运输问题. 令 T n n m m mn x (x , x , , x , x , x , , x , , x , x , , x ) = 11 12 1 21 22 2 1 2 ， = m m mn n n c c c c c c c c c c 1 2 21 22 2 11 12 1 （cost matrix，费用矩阵）， T d a a am b b bn ( , , , , , , , ) = 1 2 1 2 ， = + + + = n n n T T T T T T T T T n n m m m n I I I e e e m n m m m D x x x x x x x x x 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 2 1 2 1 1 1 1 2 1 2 1 2 2 2 1 2 ， 其中 = (1,1,1, ,1),0 = (0,0,0, ,0) T T e
运筹学讲义 则(TP)的矩阵和向量形式为 min 2=Cx Dx=d > 注:此处,z=cx,Dx=d的形式纯粹是为讨论问题的便利而作的硬性规定,并不符合线性代 数中的矩阵和向量的有关运算的定义 显然,(TP)是一种线性规划问题,当然可用求解线性规划问题的一般方法(如单纯形法、对偶 单纯形法等)来解;但是,如下所述,(P)作为一种特殊的线性规划问题,其求解亦有特殊的方法. 令Pn:D中变量x对应的列向量;d:D的第k个行向量 Th(TP)的特性: (1)r(D)=r(D,d)=m+n-1 (2)(TP)中恰有一个多余的约束方程 (3)(TP)总可行; (4)D是全幺模阵; (5)(TP)的任一基本解均为整数解 (6)(TP)总有最优解 证明:(1):∑-(d)+∑d*=0,D的行向量组d,d2,…,dm,dm1,dm2…,dm线性 相关,于是,r(D)≤m+n-1 易证,VD的m+n-1阶子矩阵D1,有r(D)=m+n-1 故r(D)=r(D,d)=m+n-1
运 筹 学 讲 义 3 则 (TP) 的矩阵和向量形式为 = = 0 . . min ( ) : x st Dx d z c x TP T . 注：此处， z c x Dx d T = , = 的形式纯粹是为讨论问题的便利而作的硬性规定，并不符合线性代 数中的矩阵和向量的有关运算的定义. 显然， (TP) 是一种线性规划问题，当然可用求解线性规划问题的一般方法（如单纯形法、对偶 单纯形法等）来解；但是，如下所述， (TP) 作为一种特殊的线性规划问题，其求解亦有特殊的方法. 令 Pij： D 中变量 ij x 对应的列向量； k d ： D 的第 k 个行向量； Th1 (TP) 的特性： （1） r(D) = r(D,d) = m + n −1 ； （2） (TP) 中恰有一个多余的约束方程； （3） (TP) 总可行； （4） D 是全幺模阵； （5） (TP) 的任一基本解均为整数解； （6） (TP) 总有最优解. 证明：（1） ( ) 0 1 1 − + = + = = + m n k m k m k k d d ， D 的行向量组 m m m m n d d d d d d + + + , , , , , , 1 2 1 2 线性 相关.于是， r(D) m + n −1. 易证， D 的 m+ n −1 阶子矩阵 D1 ，有 r(D1 ) = m+ n −1. 故 r(D) = r(D,d) = m + n −1
运筹学讲义 (2)由(1)知,D的行向量组d1,d2,…,dm,dm+1,dm+2…,dm线性相关,且其中恰有一个 行向量可由其余行向量线性表出故对应地,(TP)中恰有一个多余的约束方程. (3)由(1)知,约束方程组Dx=d总有解;而且,易证K(TP)={x|Dx=d,x≥0}≠Φ (4)令l1={12,…,m}212=仞m+1m+2,…,m+m},则由§6.2Th2知,D是全幺模阵 (5)由(4)知,D是全单模阵;又d是整数向量,故由§6.2Th1知,(TP)的任一基本解必为 整数解. (6)令=mn{n},则:=∑∑x2∑∑x=c∑∑x1=c∑a,即TP)有下 界;又由(3)知,(TP)可行,∴(7P)必有最优解■ (TP的基:D(m+n-1xm的任一m+n-1阶非奇异子矩阵 类似地,可定义基变量:非基变量等 命题(1)(TP)的任一个基均为幺模阵 (2)((TP)的基的构造)从D中删去任一行,再从剩下的矩阵中选取m+n-1个线性无关的列 向量,则所得矩阵B即为(TP)的一个基 证明:(1)由(4)知,D是全单模阵.(2)由(1)及基的定义得证l (TP)的单纯形表 mmn二=cx max W.L.0.G.设(P):1sDx=d1s.Dx=d的一个基为B=(P,P2…,P x≥0 令N=A\B,xB={x1P∈B,x={x|1∈N}, cB={cn|xn∈xB},cN={cn|xn∈x}
运 筹 学 讲 义 4 （2）由（1）知， D 的行向量组 m m m m n d d d d d d + + + , , , , , , 1 2 1 2 线性相关，且其中恰有一个 行向量可由其余行向量线性表出.故对应地， (TP) 中恰有一个多余的约束方程. （3）由（1）知，约束方程组 Dx = d 总有解；而且，易证 K(TP) = {x | Dx = d, x 0} . （4）令 {1,2, , }, { 1, 2, , } I 1 = m I 2 = m+ m+ m+ n ，则由§6.2 Th2 知， D 是全幺模阵. （5）由（4）知， D 是全单模阵；又 d 是整数向量，故由§6.2 Th1 知, (TP) 的任一基本解必为 整数解. （6）令 min { } 1 1 0 ij j n i m c c = ，则 = = = = = = = = = = m i i m i n j ij m i n j ij m i n j z cij xij c x c x c a 1 0 1 1 0 1 1 0 1 1 ，即 (TP) 有下 界；又由（3）知， (TP) 可行， (TP) 必有最优解.▍ (TP) 的基： D(m+n−1)mn 的任一 m+ n −1 阶非奇异子矩阵 B . 类似地，可定义基变量；非基变量等. 命题（1） (TP) 的任一个基均为幺模阵； （2）（ (TP) 的基的构造）从 D 中删去任一行，再从剩下的矩阵中选取 m+ n −1 个线性无关的列 向量，则所得矩阵 B 即为 (TP) 的一个基. 证明：（1）由（4）知， D 是全单模阵.（2）由（1）及基的定义得证.▍ (TP) 的单纯形表： W.L.O.G.设 = = − = = 0 . . max 0 . . min ( ) : x st Dx d f c x x st Dx d z c x TP T T 的一个基为 ( , , , ) B = P1 P2 Pm ， 令 N = A\ B， x {x | P B} B = ij ij ， x {x | P N} N = ij ij ， { | } B ij ij B c = c x x ， { | } N ij ij N c = c x x
运筹学讲义 则Dx=d台(B,N=d台Bx+Nx=d台x1=B-d-B-Mx 代入目标函数得 =-cX= --Cpxp -Cyx -cB(B d-B- Nxn)-cNxN=-cbB d-(CN-CBB" N)xN 联立得 x=b-d-B-N f=-cEB-d-(CN-CBB-IN)XN 作典式 +B-INx=B-d f +(c-cBB-MxN=-cBB-ld 作单纯形表 lm BN B-d 0 -cgBIN-cEBd 由单纯形表易见,(TP)关于基B的基本解为x= 相应的目标函数值为 f=-cBB- d B-d 注:(1)(TP)关于基B的检验数为r=c-cB-N(与标准形(LP)的检验数反号!) (2)在实际计算时,鉴于运输问题的特殊性质,其求解过程并不借助于单纯形表,而是借助于运 输表来实现
运 筹 学 讲 义 5 则 B N B N N B d Bx Nx d x B d B Nx x x Dx d B N 1 1 ( , ) − − = + = = − = . 代入目标函数得 N T B T N T N B T N N T B N T B N T B N T B N T B N B T N T B c B d B Nx c x c B d c c B N x c x c x x x c c x x c c f c x ( ) ( ) ( , ) −1 −1 −1 −1 = − − − = − − − = − − = − = − = − 联立得 = − − − = − − − − − N T B T N T B B N f c B d c c B N x x B d B Nx ( ) 1 1 1 1 作典式 + − = − + = − − − − f c c B N x c B d x B Nx B d T N B T B T N B N 1 1 1 1 ( ) 作单纯形表 由 单 纯 形 表 易 见 ， (TP) 关于基 B 的 基 本 解 为 = − 0 1 B d x ， 相 应 的 目 标 函 数 值 为 f c B d z c B d T B T B −1 −1 = − = . 注：(1) (TP) 关于基 B 的检验数为 r c c B N T B T N T N −1 = − （与标准形 (LP) 的检验数反号！）. (2)在实际计算时，鉴于运输问题的特殊性质，其求解过程并不借助于单纯形表，而是借助于运． 输表．．来实现
运筹学讲义 运输表 格子(mesh) 对(TP)的每一个变量x,作一个格子t与之对应,得格子表(集) 112…|41 =12=12…m,j=12…,n 显然,有如下一一对应关系:格子表T中的格子t分(TP的变量x分D的列向量P ≠SsT,令Ds={Pt∈Sh 规定:格子集S线性无(相)关D中的各列向量线性无(相)关 定义|SFm+n-1的线性无关的格子集S称为基本格子集,记作:△ 易见,当△是基本格子集时,D={P1∈A}中的m+n-1个列向量作成的矩阵去掉一个多 Dx =d 余的行即为(P)的一个基B,基变量为x(tn∈△),非基变量为x(g△).厘x=0.vg△ 即得(TP关于基B的基本解x=/) 定义设tn∈SsT,若Vk≠j,有tk∈S,则称l为行孤立格子;若Vk≠i,有t∈S 则称L为列孤立格子.二者合称孤立格子( isolated mesh)
运 筹 学 讲 义 6 格子（mesh） 对 (TP) 的每一个变量 ij x ，作一个格子 ij t 与之对应，得格子表（集） 显然，有如下一一对应关系：格子表 T 中的格子 ij t (TP) 的变量 ij x D 的列向量 Pij . S T ,令 D {P | t S} S = ij ij . 规定：格子集 S 线性无（相）关 DS 中的各列向量线性无（相）关. 定义 | S |= m + n −1 的线性无关的格子集 S 称为基本格子集，记作： . 易见，当 是基本格子集时， = { | } ij ij D P t 中的 m+ n −1 个列向量作成的矩阵去掉一个多 余的行即为 (TP) 的一个基 B ，基变量为 ( ) ij ij x t ，非基变量为 ( ) ij ij x t .令 = = ij ij x t Dx d 0, ， 即得 (TP) 关于基 B 的基本解 = − 0 1 B d x . 定义 设 t ij S T ，若 k j ，有 t ik S ，则称 ij t 为行孤立格子；若 k i ，有 t kj S ， 则称 ij t 为列孤立格子.二者合称孤立格子（isolated mesh）
运筹学讲义 孤立格子集的递归定义: 设SsT,|S2,若S满足条件:(1)单个格子构成的格子集是孤立格子集;(2)当tn∈S是 一个孤立格子时,S-{}仍是一个孤立格子集,则称S是一个孤立格子集 例如,给定格子集T={n|=12,3,=1,2,34},令S={12,14,1,124,213},则S是一个 孤立格子集 这是因为:(孤立格子集的递归定义)21,t24,14,12,l2,l3依次为孤立格子 命题|S=m+n-1的孤立格子集S必是基本格子集 7
运 筹 学 讲 义 7 孤立格子集的递归定义： 设 S T ，| S | 2 ，若 S 满足条件：（1）单个格子构成的格子集是孤立格子集；（2）当 t ij S 是 一个孤立格子时， { }ij S − t 仍是一个孤立格子集，则称 S 是一个孤立格子集. 例如，给定格子集 T = {t | i = 1,2,3; j = 1,2,3,4} ij ，令 { , , , , , } 12 14 21 24 32 33 S = t t t t t t ，则 S 是一个 孤立格子集. 这是因为：（孤立格子集的递归定义） 21 24 14 12 32 33 t ,t ,t ,t ,t ,t 依次为孤立格子. 命题 | S |= m + n −1 的孤立格子集 S 必是基本格子集.▍