OR--西安财经学院汇总课件.ppt
第一节 运输问题的模型,精品课程运筹学,第一节 运输问题的模型精品课程运筹学,问题的提出,一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。,精品课程运筹学,问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运,例1:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,精品课程运筹学,例1:某公司从两个产地A1、A2将物品运往三个销地B1、B,解： 产销平衡问题：总产量 = 总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：,精品课程运筹学,解： 精品课程运筹学,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）,精品课程运筹学,min f = 6x11+4x12+6x13+6x2,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.共有m+n行，分别表示各产地和销地；mn列，分别表示各决策变量； 2.每列只有两个 1，其余为 0，分别表示只有一个产地和一个销地被使用。,精品课程运筹学,模型系数矩阵特征精品课程运筹学,一般运输问题的提法： 假设 A1, A2, , Am 表示某物资的m个产地；B1,B2,Bn 表示某物资的n个销地；si表示产地 Ai 的产量；dj 表示销地 Bj 的销量；cij 表示把物资从产地 Ai 运往销地 Bj 的单位运价。如果 s1 + s2 + + sm = d1 + d2 + + dn 则称该运输问题为产销平衡问题；否则，称产销不平衡。,精品课程运筹学,一般运输问题的提法：精品课程运筹学,运输问题数据表,设 xij 为从产地 Ai 运往销地 Bj 的运输量，根据这个运输问题的要求，可以建立运输变量表。,精品课程运筹学,运输问题数据表 设 xij 为从产地 Ai 运往销地,运输问题变量表,精品课程运筹学,运输问题变量表 销地B1 B2 Bn产,m n min f = cij xij （1） i=1 j=1 n s.t. xij si i = 1,2,m （2） j=1 m xij (=,)dj j = 1,2,n （3） i=1 xij 0 (i=1,2,m;j=1,2,n) （4）,于是得到下列一般运输问题的模型：,在模型（1）（4）中，式（2）为 m 个产地的产量约束；式（3）为 n 个销地的销量约束。,精品课程运筹学,m,m n min f = cij xij i=1 j=1 n s.t. xij = si i = 1,2,m (5) j =1 m xij = dj j = 1,2,n (6) i =1 xij 0 (i=1,2,m; j=1,2,n),对于产销平衡问题，可得到下列运输问题的模型：,精品课程运筹学,在产销平衡问题中，式（2）、（3）分别变为（5）、（6），约束条件成为等式。 在实际问题建模时，还会出现如下一些变化： （1）有时目标函数求最大，如求利润最大或营业额最大等； （2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；,精品课程运筹学,在产销平衡问题中，式（2）、（3）分别变为（5）,(3)产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，这相当于在式（2）每一式中加上 1 个松弛变量，共 m 个；当产量大于销量时可加入一个虚设的销地去消化多余的物资，这相当于在式（3）每一式中加上 1 个松弛变量，共 n 个。,精品课程运筹学,(3)产销不平衡的情况。当销量大于产量时可加入一个,运输问题是一种特殊的线性规划问题，在求解时依然可以采用单纯形法的思路，如图所示（下页）。由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。下面主要讨论基本可行解、检验数以及基的转换等问题。,精品课程运筹学,运输问题是一种特殊的线性规划问题，在求解时依然可以采用单纯形,运输问题的求解思路,精品课程运筹学,基本可行解是否最优解结束换基是否运输问题的求解思路精品课程,运输问题求解的有关概念 考虑产销平衡问题，由于我们关心的量均在表（运输问题数据表）与表（运输问题变量表）中，因此考虑把这两个表合成一个表, 如下表所示。,精品课程运筹学,运输问题求解的有关概念精品课程运筹学,精品课程运筹学,销地B1B2Bn产量A1 c11c12c1na1,运输问题的基变量共有 m + n -1 个，A的秩为 m + n -1。 运输问题的 m + n -1 个变量构成基变量的充分必要条件是不含闭回路。 重要概念：闭回路、闭回路的顶点,特点,运输问题基变量的,精品课程运筹学,运输问题的基变量共有 m + n -1 个，A的秩为 m,定义 在上表的决策变量格中，凡是能够排列成下列形式的 xab ,xac ,xdc ,xde ,xst ,xsb (7)或 xab ,xcb ,xcd ,xed ,xst ,xat (8) 其中，a, d, , s 各不相同；b, c, , t 各不相同，我们称之为变量集合的一个闭回路，并将式（7）、式（8）中的变量称为这个闭回路的顶点。,为了说明这个特征，我们不加证明的给出一些概念和结论。下面的讨论建立在表4-5中决策变量格的基础上。,精品课程运筹学,定义 在上表的决策变量格中，凡是能够排列成下列形式的,例如，x13, x16, x36, x34, x24, x23 ； x23, x53, x55, x45, x41, x21 ； x11, x14, x34, x31等都是闭回路。 若把闭回路的各变量格看作节点，在表中可以画出如下形式的闭回路：,闭回路示意图,精品课程运筹学,例如，x13, x16, x36, x34, x24, x2,根据定义可以看出闭回路的一些明显特点： (1)闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的； (2)闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量格）。,精品课程运筹学,根据定义可以看出闭回路的一些明显特点：精品课程,关于闭回路有如下的一些重要结论： (1) 设 xab , xac , xdc , xde , xst , xsb 是一个闭回路，那么该闭回路中变量所对应的系数列向量 pab , pac , pdc , pde , pst , psb 线性相关； (2) 若变量组 xab , xcd , xef , xst 中包含一个部分组构成闭回路，那么该变量组所对应的系数列向量 pab , pcd, pef , pst 线性相关。 根据上述结论以及线性规划基变量的特点，可以得到下面重要定理及其推论。,精品课程运筹学,关于闭回路有如下的一些重要结论：精品课程运筹学,定理1 变量组 xab , xcd , xef , xst 所对应的系数列向量 pab , pcd , pef , pst 线性无关的充分必要条件是这个变量组中不包含闭回路。推论 产销平衡运输问题的 m + n -1 个变量构成基变量的充分必要条件是它不含闭回路。这个推论给出了运输问题基本解的重要性质，也为寻求基本可行解提供了依据。,精品课程运筹学,定理1 变量组 xab , xcd , xef , xs,
