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

第三章运输问题运输问题的数学模型■表上作业法2024-10-27n

2024-10-27 2 第三章 运输问题 n 运输问题的数学模型 n 表上作业法

$1运输问题的典例及数学模型引例某公司从三个产地A，A2，A,将产品运往四个销地B，B2B，B4，各产地的产量，各销地的销量，及各产地往各销地的运费单价C，如表所示。应如何调运可使运费最小？销地产量B1B3B2B4运费单价(吨)产地33A1111072A21984A37410593656销量 (吨)2024-10-27

2024-10-27 3 §1 运输问题的典例及数学模型 一 、 引例 某公司从三个产地 ， ， 将产品运往四个销地 ， ， ，各产地的产量，各销地的销量，及各产地往各销 地的运费单价 如表所示。应如何调运可使运费最小？ A1 A2 B1 B2 B3 A3 B4 销地 运费单价 产地 B1 B2 B3 B4 产量 （吨） A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 销量（吨） 3 6 5 6 Cij

解：从表中可知：总产量=总销量。这是一个产销平衡的运输问题。假设x表示从产地A运往销地B,的产品数量，i=1,2,3; j=1,2,3,4 。产销平衡和单位运价如下表格销地B1B2B3B4产量运费单价(吨)产地A13Xi13Xi371110Xi2X142A21948X21X22X23X247As94105X31X32X33X343566销量 (吨)2024-10-27

2024-10-27 4 解：从表中可知：总产量 = 总销量。这是一个产销平衡的运 输问题。假设xij表示从产地Ai运往销地Bj的产品数量， i=1,2,3; j=1,2,3,4。 产销平衡和单位运价如下表格： 销地 运费单价 产地 B1 B2 B3 B4 产量 （吨） A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 销量（吨） 3 6 5 6

目标函数：MinZ=3xi+11xi2+3xi3 +10x14+X21 +9x22+2x23 +8x24+7x31 + 4x32 +10x33 +5X34约束条件：X1+X2+X3+X4=72021+X22+X23 +24 =4产量约束31+X32+x3 +4=9Xi1 + X21 + X31 = 3X12 + X22 + X32 = 620销量约束X13+ X23+ X33 = 5X14 + X24+X34 = 6x, ≥ 0,i = 1,2,3; j = 1,2,3,42024-10-275

2024-10-27 5 目标函数： 31 32 33 34 21 22 23 24 11 12 13 14 7 4 10 5 9 2 8 3 11 3 10 x x x x x x x x MinZ x x x x             约束条件： 产量约束 销量约束 20 20 9 4 7 31 32 33 34 21 22 23 24 11 12 13 14             x x x x x x x x x x x x 0, 1,2,3; 1,2,3,4 6 5 6 3 14 24 34 13 23 33 12 22 32 11 21 31                x i j x x x x x x x x x x x x ij

则该运输问题的模型如下：34ZZminz =C.iXi=-l j-142(i=1,2,3)=a,Xij育3(j = 1, 2,3, 4)= b,XiX≥0(i = 1,2,3; j = 1,2,3, 4)a,=b,=20，所以该问题为产销平衡的运说明：i=11=输问题。2024-10-27

2024-10-27 6 说明：∵ ，所以该问题为产销平衡的运 输问题。 20 4 1 3 1      j j i i a b 3 4 1 1 min ij ij i j z c x     4 1 3 1 ( 1,2,3) ( 1,2,3,4) 0 ( 1,2,3; 1,2,3,4) ij i j ij j i ij x a i x b j x i j            则该运输问题的模型如下：

二、一般运输问题数学模型设有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 运输问题的表上作业法