运输问题模型与性质.ppt

第三章 特殊的线性规划 运输问题,& 模型及其特点 & 求解思路及相关理论 & 求解方法表上作业法 & 运输问题的推广 产销不平衡的运输问题 转运问题,1.运输问题模型及有关概念,问题的提出 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。,1.运输问题模型及有关概念,例4.1:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,解： 产销平衡问题： 总产量 = 总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：,1.运输问题模型及有关概念,Min f = 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.运输问题模型及有关概念,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.运输问题模型及有关概念,模型系数矩阵特征 1.共有m+n行，分别表示各产地和销地；mn列，分别表示各决策变量； 2.每列只有两个 1，其余为 0，分别表示只有一个产地和一个销地被使用。,1.运输问题模型及有关概念,一般运输问题的线性规划模型及求解思路 一般运输问题的提法： 假设 A1, A2,Am 表示某物资的m个产地；B1,B2,Bn 表示某物资的n个销地；si表示产地 Ai 的产量；dj 表示销地 Bj 的销量；cij 表示把物资从产地 Ai 运往销地 Bj 的单位运价（表4-3）。如果 s1 + s2 + + sm = d1 + d2 + + dn 则称该运输问题为产销平衡问题；否则，称产销不平衡。首先讨论产销平衡问题。,1.运输问题模型及有关概念,表4-3 运输问题数据表,1.运输问题模型及有关概念,设 xij 为从产地 Ai 运往销地 Bj 的运输量，根据这个运输问题的要求，可以建立运输变量表（表 4-4）。,表4-4 运输问题变量表,1.运输问题模型及有关概念,3.1 运输问题模型与性质 一、运输问题的数学模型 1、 运输问题的一般提法： 某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？,单位根据具体问题选择确定。,表3-1 有关信息,2、运输问题的数学模型,设xij为从产地Ai运往销地Bj的物资数量（i=1，m；j=1，n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足：,同理，运到Bj的物资总量应该等于Bj的销量bj，所以xij还应满足： 总运费为：,运输问题的数学模型,（3-6）,二、运输问题的特点与性质 1约束方程组的系数矩阵具有特殊的结构 写出式（3-1）的系数矩阵A，形式如下：, 矩阵的元素均为1或0； 每一列只有两个元素为1，其余元素均为0； 列向量Pij =(0,，0，1，0，,0,1,0,0)T，其中两个元素1分别处于第i行和第m+j行。 将该矩阵分块，特点是：前m行构成m个mn阶矩阵，而且第k个矩阵只有第k行元素全为1，其余元素全为0（k=1，m）；后n行构成m个n阶单位阵。,2.运输问题的基变量总数是m + n -1 写出增广矩阵,证明系数矩阵A及其增广矩阵的秩都是m+n-1,前m行相加之和减去后n行相加之和结果是零向量，说明m+n个行向量线性相关，因此 的秩小于m+n； ？,因此 的秩恰好等于m+n-1，又D本身就含于A中，故A的秩也等于m+n-1,由 的第二至m+n行和前n列及 对应的列交叉处元素构成m+n-1阶方阵D 非奇异； ？,20,3.2 运输问题的求解方法,约束条件非常有规律，技术系数非 0 即 1 基变量的个数远小于决策变量的个数 采用表上作业法，称为位势法和踏石法 运算中涉及两个表：运费表和产销平衡表(分配表),21,3.2.1 寻找初始可行解的方法,1、西北角法 从 x11开始分配，从西北向东南方向逐个分配 xij 的分配公式,例3.2.1,22,例3.2.1 西北角法,23,2、最低费用法,采用最小费用优先分配的原则，看一步,f(x)=121，比 西北角法低 84,24,3、运费差额法,采用最大差额费用(即利用每行或列中最小费用与次最小之间的差额中选最大)优先分配的原则，看两步,f(x)=98，比 最低费用法 又低了23,25,3.2.2 利用位势法检验分配方案是否最优,不采用单纯型法，如何获得xij的检验数 找到原问题的基础可行解，保持互补松弛条件，求出对应对偶问题的解，若该对偶问题的解非可行，则原问题的解不是最优解；否则，达到最优解,26,27,位势法的原理,为满足互补松弛条件，原问题中xij被选为基变量，即xij0，则要求对偶问题中ui+vj=wij，即该行的松弛变量为0 共有m+n1个基变量xij ，因此可得m+n1个等式 ui+vj=wij m+n1个等式只能解出 m+n1个 ui 和 vj ，而一共有m+n个 ui 和 vj ，但可令任一个ui 或 vj =0，从而解出其它 m+n1个的值；这就是位势法 令 zij= ui + vj ，其相当原问题xij的机会费用 若对所有非基变量有 zij wij 0，即 ui + vj wij，表明当前ui 和 vj 是对偶问题的可行解，由互补松弛定理可知当前m+n1个基变量xij 是最优解，否则 从 zij wij 0 中找最大者，对应 xij 就是入变量,28,3.2.3 踏石法,1、找入变量 从 zij wij 0 中找最大者，对应 xij 就是入变量 2、以 xij 为起点，寻找由原基变量构成的闭合回路 该回路只在每个拐角各有一个基变量，中间允许穿越某些基变量；因此，闭合回路中必有偶数个变量(包括 xij )，且回路中每行每列只有两个变量 3、求入变量 xi*j* 的最大值及新基变量的解 从 xij出发，沿任一个方向对回路拐角上的基变量依此标“”和“+”，表示“”和“+” xij ，从而迭代后仍满足分配的平衡 标有“”的变量中最小者就是出变量xi*j* ，对应 xi*j*的值就是所求入变量 xij 的最大值 标有“”的变量减去 xi*j*，标有“+”的变量加上 xi*j* 4、用位势法求新基变量的检验数 若所有 zij wij 0，则达到最优，算法停止；否则返回 1,29,例3.2.1 踏石法，以最低费用法所得初始解开始,答：最优解如上分配表，OBJ=98,OBJ=121,OBJ=101,30,3.3 运输问题迭代中的一些具体问题,3.3.1 闭合回路的画法 从入变量xij出发，遇到某个基变量则选一个方向拐角，若不能再遇到其它基变量，则返回上一拐角，换一个方向走，采用深探法 闭合回路不一定是矩形 3.3.2 产销不平衡 供过于求，即 ai bj ，增加一个虚收点Dn+1，bn+1= ai - bj , 令 wi,n+1=0, i=1,2,m 供小于求，即 ai bj ，增加一个虚发点Wm+1，am+1= bj - ai , 令 wm+1,j=0, j=1,2,n 3.3.3 关于退化问题 1、初始解退化。即所求初始基变量的个数少于 m+n1。必须补足基变量的个数，否则不能正常解出 m+n个 ui 和 vj 所补基变量的值为 0 ，补充的原则：(1)尽量先选运费小的实变量；(2)补充后不能有某个基变量独占一行一列,31,3.3.3 关于退化问题,2、迭代过程中出现退化 闭合回路中标有“”的基变量同时有多个达到最小 变换后，有多个原基变量变为 0，选运费最大者为出变量，其余保留在新的基础解中 退化较严重时，可能会出现多次迭代只有值为 0 的基变量在转移。此时，一要耐心，二要正确选择出变量,踏石法迭代中需注意的问题：,1、错误地将分配表中基变量的解代入到运费表中 2、不能正确画闭合回路 3、初始解退化，未能补足基变量的个数。因此在位势法中多次令某个 ui 或 vj 为 0； 4、在位势法中只能令一个 ui 或 vj 为 0；若不能求出全部 ui和 vj ，说明基变量未选够数或未选对,可以证明：m+n个约束方程中的任意m+n-1个都是线性无关的。,定义3.1 凡是能排成 (3-4) 或 (3-5) 形式的变量集合称为一个闭回路,并称式中变量为该闭回路的顶点；其中 互不相同, 互不相同。,3. m+n-1个变量构成基变量的充要条件是它们不构成闭回路。,例3-1 设m=3，n=4，决策变量xij表示从产地Ai到销地Bj的调运量，列表如下，给出闭回路 在表中的表示法用折线连接起来的顶点变量。,练习3-1 请给出闭回路 和 在表中的表示法。,练习3-2 下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？为什麽？, 表中的折线构成一条封闭曲线，且所有的边都是水平或垂直的；为什麽？ 表中的每一行和每一列由折线相连的闭回路的顶点只有两个；为什麽？,有关闭回路的一些重要结果,定理3-1 设 是一个闭回路，则该闭回路中的变量所对应的系数列向量 具有下面的关系：,注意：列向量Pij =(0,0,1,0,0,1,0,0)T中两个元素1分别处于第i行和第m+j行，直接计算即可得到结果。,定理的证明可借助定理3-1和高等代数中“向量组中，若部分向量线性相关，则整个向量组就线性相关”的定理得到。,定理3-2 若变量组 中有一个部分组构成闭回路，则该变量组对应的系数列向量线性相关。,定理3-3 不包含任何闭回路的变量组中必有孤立点。 所谓孤立点是指在所在行或列中