运筹学：第三章 运输问题.ppt

1,第三章 运输问题,运输问题与有关概念运输问题的求解表上作业法运输问题应用建模,本章内容重点,2,1.运输问题模型及有关概念,问题的提出 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案3,1.运输问题模型及有关概念,例4.1:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,4,解： 产销平衡问题： 总产量 = 总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：,1.运输问题模型及有关概念,5,Min Z = 6x11+4x12+6x13+6x21+5x22+5x23,s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij0(i=1,2；j=1,2,3）,1.运输问题模型及有关概念,6,1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1,系数矩阵,1.运输问题模型及有关概念,7,模型系数矩阵特征 1.共有m+n行，分别表示各产地和销地；mn列，分别表示各决策变量； 2.每列只有两个 1，其余为 0，分别表示只有一个产地和一个销地被使用。

1.运输问题模型及有关概念,8,一般运输问题的线性规划模型及求解思路 一般运输问题的提法： 假设 A1, A2,Am 表示某物资的m个产地；B1,B2,Bn 表示某物资的n个销地；ai表示产地 Ai 的产量；bj 表示销地 Bj 的销量；cij 表示把物资从产地 Ai 运往销地 Bj 的单位运价（表4-3）如果 a1 + a2 + + am = b1 + b2 + + bn则称该运输问题为产销平衡问题；否则，称产销不平衡首先讨论产销平衡问题1.运输问题模型及有关概念,9,表4-3 运输问题数据表,1.运输问题模型及有关概念,设 xij 为从产地 Ai 运往销地 Bj 的运输量，根据这个运输问题的要求，可以建立运输变量表（表 4-4）10,表4-4 运输问题变量表,1.运输问题模型及有关概念,11,m nMin Z = cij xij （4-1） i=1 j=1 n s.t. xij ai i = 1,2,m （4-2） j=1 m xij (=,)bj j = 1,2,n （4-3） i=1 xij 0 (i=1,2,m;j=1,2,n)（4-4）,1.运输问题模型及有关概念,于是得到下列一般运输问题的模型：,在模型（4-1）（4-4）中，式（4-2）为 m 个产地的产量约束；式（4-3）为 n 个销地的销量约束。

12,m n Min Z = cij xij i=1 j=1 n s.t. xij = ai i = 1,2,m (4-5) j=1 m xij = bj j = 1,2,n (4-6) i=1 xij0(i=1,2,m;j=1,2,n),1.运输问题模型及有关概念,对于产销平衡问题，可得到下列运输问题的模型：,13,在产销平衡问题中，仔细观察式（4-2）、 （4-3）分别变为（4-5）、（4-6），约束条件成 为等式 在实际问题建模时，还会出现如下一 些变化： （1）有时目标函数求最大，如求利润最 大或营业额最大等； （2）当某些运输线路上的能力有限制时， 模型中可直接加入（等式或不等式）约束；,1.运输问题模型及有关概念,14,(3)产销不平衡的情况当销量大于产量时可加入一个虚设的产地去生产不足的物资，这相当于在式（4-2）每一式中加上 1 个松弛变量，共 m 个；当产量大于销量时可加入一个虚设的销地去消化多余的物资，这相当于在式（4-3）每一式中加上 1 个松弛变量，共 n 个1.运输问题模型及有关概念,15,运输问题是一种特殊的线性规划问题，在求解时依然可以采用单纯形法的思路，如图4-1所示。

由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法在这里需要讨论基本可行解、检验数以及基的转换等问题1.运输问题模型及有关概念,16,1.运输问题模型及有关概念,图4-1 运输问题的求解思路,17,运输问题求解的有关概念 考虑产销平衡问题，由于我们关心的量均在表4-3与表4-4中，因此考虑把表4-3与表4-4合成一个表, 如下表4-5表4-5 运输问题求解作业数据表(下页）,1.运输问题模型及有关概念,18,1.运输问题模型及有关概念,19,中任意m+n阶子式等于零，取第一行到m+n1行与对应的列（共m+n-1列）组成的m+n1阶子式,20,故r(A)=m+n1所以运输问题有m+n1个基变量21,运输问题的基变量共有 m + n -1 个，A的秩为 m + n -1 运输问题的 m + n -1 个变量构成基变量的充分必要条件是不含闭回路 重要概念: 闭回路、闭回路的顶点,特点,运输问题基变量的,1.运输问题模型及有关概念,22,定义4.1 在表4-5的决策变量格中，凡是能够排列成下列形式的 xab ,xac ,xdc ,xde ,xst ,xsb (4-7)或 xab ,xcb ,xcd ,xed ,xst ,xat (4-8) 其中，a,d,s 各不相同；b,c,t 各不相同，我们称之为变量集合的一个闭回路，并将式（4-7）、式（4-8）中的变量称为这个闭回路的顶点。

为了说明这个特征，我们不加证明的给出一些概念和结论下面的讨论建立在表4-5中决策变量格的基础上1.运输问题模型及有关概念,23,例如，x13, x16, x36, x34, x24, x23 ； x23, x53, x55, x45, x41, x21 ； x11, x14, x34, x31等都是闭回路 若把闭回路的各变量格看作节点，在表中可以画出如下形式的闭回路：,1.运输问题模型及有关概念,24,根据定义可以看出闭回路的一些明显特点： (1)闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的； (2)闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量格）1.运输问题模型及有关概念,25,x23,x43,x11,x12,x25,x31,x42,表33,表33中闭回路的变量集合是x11,x12,x42, x 43, x 23, x 25, x 35, x 31共有8个顶点， 这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路26,表34,一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接，表33中的变量x 32及x33不是回闭路的顶点，只是连线的交点。

表34中闭回路是,例如变量组,A不能组成一条闭回路，但A中包含有闭回路,B的变量数是奇数，显然不是闭回路，也不含有闭回路；,27,C是一条闭回路，若把C重新写成 就不难看出C仍是一条闭回路定理1】 若变量组B 包含有闭回路 ，则B中的变量对应的例向量线性相关证】由线性代数知，向量组中部分向量组线性相关则该向量组线性相关，显然，将C中列向量分别乘以正负号线性组合后等于零，即,因而C中的列向量线性相关，所以B中列向量线性相关定理2】若变量组 中包含一个部分组构成闭回路，那么该变量组所对应的系数列向量 线性相关28,定理3 变量组 xab , xcd , xef , xst 所对应的系数列向量pab , pcd , pef , pst 线性无关的充分必要条件是这个变量组中不包含闭回路 推论 产销平衡运输问题的 m + n -1 个变量构成基变量的充分必要条件是它不含闭回路 这个推论给出了运输问题基本解的重要性质，也为寻求基本可行解提供了依据这个推论告诉了一个求基变量的简单方法，同时也可以判断一组变量是否可以作为某个运输问题的基变量这种方法是直接在运价表中进行的，不需要在系数矩阵A中去寻找，从而给运输问题求初始基可行解带来极大的方便。

29,例如，m=3,n=4，在运价表Cij的格子的右上方填上相应的xij，如表3-5所示表35,30,这个运输问题的基变量数目是3+41=6变量组中有7个变量，显然不能构成一组基变量，又如中有6个变量，但包含有一条闭回路故不能构成一组基变量变量组有6个变量且不含有任何闭回路，故可以构成此问题的一组基变量31,2.运输问题求解 表上作业法,上一节已经分析了，对于产销平衡问题，我们关心的量均可以表示在表4-5中因此可以建立基于表4-5的求解运输问题的方法表上作业法这里求解运输问题的思想和单纯形法完全类似，即首先确定一个初始基本可行解，然后根据最优性判别准则来检查这个基本可行解是不是最优的如果是则计算结束；如果不是，则进行换基，直至求出最优解为止32,2.运输问题求解 表上作业法,一、初始基本可行解的确定 根据上面的讨论，要求得运输问题的初始基本可行解，必须保证找到 m + n 1 个不构成闭回路的基变量一般的方法步骤如下： (1)在运输问题求解作业数据表中任选一个单元格 xij ( Ai 行 Bj 列交叉位置上的格),令 xij = min ai , bj ,即从 Ai 向 Bj 运最大量(使行或列在允许的范围内尽量饱和，即使一个约 束方程得以满足),填入 xij 的相应位 置；,33,2.运输问题求解 表上作业法,(2)从 ai 或 bj 中分别减去 xij 的值，即调整 Ai 的拥有量及 Bj 的需求量；,(3)若 ai = 0，则划去对应的行（把拥有的量全部运走），若 bj = 0 则划去对应的列（把需要的量全部运来），且每次只划去一行或一列（即每次要去掉且只去掉一个约束）； (4)若运输平衡表中所有的行与列均被划去，则得到了一个初始基本可行解。

否则在剩下的运输平衡表中选下一个变量，转(4)34,上述计算过程可用流程图描述如下（图4-2）,35,2.运输问题求解 表上作业法,按照上述方法所产生的一组变量的取值将满足下面条件：(1)所得的变量均为非负，且变量总数恰好为 m + n 1 个；(2)所有的约束条件均得到满足；(3)所得的变量不构成闭回路因此，根据定理4.1及其推论，所得的解一定是运输问题的基本可行解 在上面的方法中，xij 的选取方法并没有给予限制，若采取不同的规则来选取 xij ，则得到不同的方法，较常用的方法有西北角法和最小元素法下面分别举例予以说明36,2.运输问题求解 表上作业法,1、初始基本可行解的确定 （1）西北角法：从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数然后按行（列）标下一格的数若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去如此进行下去，直至得到一个基本可行解37,例1：设有运输问题如下表所示，求其最优解38,第一次,第二次,第三次,第四次,39,2.运输问题求解 表上作业法,（2）最小元素法：从运价最小的格开始，在格内的右下角标上允许取得的最大数然后按运价从小到大顺序填数。

若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去如此进行下去，直至得到一个基本可行解最小元素法的思想是就近优先运送，即最小运价Cij对应的变量xij优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后一个初始基可行解40,【例2】求表36所示的运输问题的初始基可行解表36,41,0,0,0,【解】,30,15,10,25,20,15,45,20,20,0,0,0,产地,销地,42,注:应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有最后一个元例外（同时划去。