《运筹学》课程教学课件（讲稿）第3章 运输问题

二、一般运输问题数学模型设有m个产地，分别为A1，A2.Am;n个销地，分别是Bi，B2……Bn;从产地A,运往销地B，的单位运价是Cj，运量xia,是产地A,的总产量；b，是销地B,的总销量。2024-10-27

2024-10-27 7 设有m个产地，分别为 ; n 个销地，分别是 ； 从产地 运往销地 的单位运价是 ，运量 是产地 的总产量； 是销地 的总销量。 A A A m , ,. 1 2 B B B n , ,. 1 2 A i B j ij c ij x i a A i b j B j 二、 一般运输问题数学模型

则运输问题的模型如下：mYZminz =Ci-l j-1n>(i=1,2,...,m)=aXj=1==b(j=1,2,...,n)x.i=1Xj≥0(i=1,2,...,m, j = 1,2,..,n)Za,=Zb,说明：当时，称其为产销平衡的运输问题，i=1j-1否则产销不平衡。2024-10-278

2024-10-27 8 说明：当 时，称其为产销平衡的运输问题， 否则产销不平衡。      n j j m i i a b 1 1 1 1 min m n ij ij i j z c x     1 1 ( 1,2, , ) ( 1,2, , ) 0 ( 1,2, , ; 1, 2, , ) n ij i j m ij j i ij x a i m x b j n x i m j n                则运输问题的模型如下：

说明：从上述模型可以看出：这是一个线性规划的模型；（1）变量有mXn个；（2）约束条件有m+n个;（3）最多只有m+n-1个独立的约束条件，即系数矩阵的秩R（A）≤m+n-l;一般情况下系数矩阵的秩一般为m+n-1,即运输问题的解中的基变量个数一般为m+n-1，而非m+n。"(i =1,2,...,m)证明：m个产量的约束方程为=a,W(I)i=li=l j=1n个销量的约束方程为=b,(j=1,2,,n)1=1Zb,2Nx(2)1=I在（1）（2）两式中，左端表达式一致，而右端表达式实际存在(产销平衡)（1）（2）两式完全一致，从而说明独立方程个数少于m+n个2024-10-27q

2024-10-27 9 说明：从上述模型可以看出：这是一个线性规划的模型； （1）变量有m×n个； （2）约束条件有m+n个； （3）最多只有m+n-1个独立的约束条件，即系数矩阵的秩R（A）≤m+n-1； 一般情况下系数矩阵的秩一般为m+n-1,即运输问题的解中的基变量个数一 般为m+n-1，而非m+n 。 证明：m个产量的约束方程为 1 ( 1, 2, , ) n ij i j x a i m     1 1 1 (1) m n m ij i i j i x a        n个销量的约束方程为 1 ( 1, 2, , ) m ij j i x b j n     1 1 1 (2) n m n ij j j i j x b       在（1）（2）两式中，左端表达式一致，而右端表达式实际存在 （产销平衡） 1 1 m n i j i j a b      （1）（2）两式完全一致，从而说明独立方程个数少于m+n个

（4）系数矩阵A具有特殊结构；XinX21XmxuX12X22XmXm2(100100010X +X2+..+Xin=a0000100X2i+X22+...+X2n=a2:........000010011.Xm+Xm2++Xmm=am.01100000...X+X21+..+Xm=b....1.000010011..X21 + X22 ++ Xm2 = b2.:：.:::..:::..00001001.1Xin+X2n+..+Xmm=b.......(0)变量X,对应的系数列向量P；（约束条件）的结构特点：..1→第行Py =:→第m+j行即在约束方程的系数列向量中，只有第行和第:m+j行为1，其余均为0。0102024-10-27

2024-10-27 10 （4）系数矩阵A具有特殊结构； 11 12 1 21 22 2 1 2 11 12 1 1 21 22 2 2 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 n n m m mn n n x x x x x x x x x x x x a x x x a                                                                          1 2 11 21 1 1 21 22 2 2 1 2 m m mn m m m n n mn n x x x a x x x b x x x b x x x b                      变量xij对应的系数列向量Pij（约束条件）的结构特点： 0 1 1 0 ij i p m+ j             第 行 即在约束方程的系数列向量中，只有第i行和第 第 行 m+j行为1，其余均为0

82运输问题的表上作业法从第一节的运输问题的数学模型可知，运输问题实际上也属于线性规划，但由于运输问题的特殊性（变量个数较多，系数矩阵的特点），如果用单纯形表格方法迭代，计算量很大。今天介绍的“表上作业法”，是针对运输问题的特殊求解方法，实质还是单纯形法，但减少了计算量。表上作业法适用于求解产销平衡的运输问题。（产销不平衡的问题可转化为平衡问题）112024-10-27

2024-10-27 11 从第一节的运输问题的数学模型可知，运输问题实际上 也属于线性规划，但由于运输问题的特殊性（变量个数较多， 系数矩阵的特点），如果用单纯形表格方法迭代，计算量很 大。今天介绍的 “表上作业法” ，是针对运输问题的特殊 求 解 方 法 ， 实 质 还 是 单 纯 形 法 ， 但 减 少 了 计 算 量 。 表上作业法适用于求解产销平衡的运输问题。（产销不 平衡的问题可转化为平衡问题） §2 运输问题的表上作业法